hphp/runtime/vm/jit/regionize-func.cpp
/**
 * Sorts the regions vector in a linear order to be used for
 * translation.  The goal is to obtain an order that improves locality
 * when the function is executed.
 */
Sorts the regions vector in a linear order to be used for
translation.  The goal is to obtain an order that improves locality
when the function is executed.
Sorts the regions vector in a linear order to be used for translation . The goal is to obtain an order that improves locality when the function is executed .
static void sortRegion(RegionVec&                  regions,
                       const Func*                 func,
                       const TransCFG&             cfg,
                       const ProfData*             profData,
                       const TransIDToRegionMap&   headToRegion,
                       const RegionToTransIDsMap&  regionToTransIds) {
  RegionVec sorted;
  RegionSet selected;
  if (regions.size() == 0) return;
  RegionDescPtr entryRegion = nullptr;
  int64_t    maxEntryWeight = -1;
  Offset     lowestOffset   = kInvalidOffset;
  for (const auto& pair : regionToTransIds) {
    auto  r    = pair.first;
    auto& tids = pair.second;
    TransID firstTid = tids[0];
    Offset firstOffset = profData->transSrcKey(firstTid).offset();
    int64_t weight = cfg.weight(firstTid);
    if (lowestOffset == kInvalidOffset || firstOffset < lowestOffset ||
        (firstOffset == lowestOffset && weight > maxEntryWeight)) {
      entryRegion    = r;
      maxEntryWeight = weight;
      lowestOffset   = firstOffset;
    }
  }
  assert(entryRegion);
  sorted.push_back(entryRegion);
  selected.insert(entryRegion);
  RegionDescPtr region = entryRegion;
  for (auto i = 1; i < regions.size(); i++) {
    int64_t      maxWeight = -1;
    int64_t  maxHeadWeight = -1;
    RegionDescPtr bestNext = nullptr;
    auto    regionTransIds = getRegionTransIDVec(regionToTransIds, region);
    for (auto next : regions) {
      if (selected.count(next)) continue;
      auto nextTransIds = getRegionTransIDVec(regionToTransIds, next);
      int64_t weight = interRegionWeight(regionTransIds, nextTransIds[0], cfg);
      int64_t headWeight = cfg.weight(nextTransIds[0]);
      if ((weight >  maxWeight) ||
          (weight == maxWeight && headWeight > maxHeadWeight)) {
        maxWeight     = weight;
        maxHeadWeight = headWeight;
        bestNext      = next;
      }
    }
    assert(bestNext);
    sorted.push_back(bestNext);
    selected.insert(bestNext);
    region = bestNext;
  }
  assert(sorted.size() == regions.size());
  regions = sorted;
  if (debug && Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
    for (size_t i = 0; i < regions.size(); i++) {
      auto r = regions[i];
      auto tids = getRegionTransIDVec(regionToTransIds, r);
      std::string transIds = folly::join(", ", tids);
      FTRACE(6, "sortRegion: region[{}]: {}\n", i, transIds);
    }
  }
}
static void sortRegion ( RegionVec & regions , const Func * func , const TransCFG & cfg , const ProfData * profData , const TransIDToRegionMap & headToRegion , const RegionToTransIDsMap & regionToTransIds ) { RegionVec sorted ; RegionSet selected ; if ( regions . size ( ) == 0 ) return ; RegionDescPtr entryRegion = nullptr ; int64_t maxEntryWeight = -1 ; Offset lowestOffset = kInvalidOffset ; for ( const auto & pair : regionToTransIds ) { auto r = pair . first ; auto & tids = pair . second ; TransID firstTid = tids [ 0 ] ; Offset firstOffset = profData -> transSrcKey ( firstTid ) . offset ( ) ; int64_t weight = cfg . weight ( firstTid ) ; if ( lowestOffset == kInvalidOffset || firstOffset < lowestOffset || ( firstOffset == lowestOffset && weight > maxEntryWeight ) ) { entryRegion = r ; maxEntryWeight = weight ; lowestOffset = firstOffset ; } } assert ( entryRegion ) ; sorted . push_back ( entryRegion ) ; selected . insert ( entryRegion ) ; RegionDescPtr region = entryRegion ; for ( auto i = 1 ; i < regions . size ( ) ; i ++ ) { int64_t maxWeight = -1 ; int64_t maxHeadWeight = -1 ; RegionDescPtr bestNext = nullptr ; auto regionTransIds = getRegionTransIDVec ( regionToTransIds , region ) ; for ( auto next : regions ) { if ( selected . count ( next ) ) continue ; auto nextTransIds = getRegionTransIDVec ( regionToTransIds , next ) ; int64_t weight = interRegionWeight ( regionTransIds , nextTransIds [ 0 ] , cfg ) ; int64_t headWeight = cfg . weight ( nextTransIds [ 0 ] ) ; if ( ( weight > maxWeight ) || ( weight == maxWeight && headWeight > maxHeadWeight ) ) { maxWeight = weight ; maxHeadWeight = headWeight ; bestNext = next ; } } assert ( bestNext ) ; sorted . push_back ( bestNext ) ; selected . insert ( bestNext ) ; region = bestNext ; } assert ( sorted . size ( ) == regions . size ( ) ) ; regions = sorted ; if ( debug && Trace :: moduleEnabled ( HPHP :: Trace :: pgo , 5 ) ) { for ( size_t i = 0 ; i < regions . size ( ) ; i ++ ) { auto r = regions [ i ] ; auto tids = getRegionTransIDVec ( regionToTransIds , r ) ; std :: string transIds = folly :: join ( " " , tids ) ; FTRACE ( 6 , " \n " , i , transIds ) ; } } }
Sorts the regions vector in a linear order to be used for
 translation.
Sorts the regions vector in a linear order to be used for translation .
// First, pick the region starting at the lowest bytecode offset. // This will normally correspond to the main function entry (for // normal, regular bytecode), but it may not be for irregular // functions written in hhas (like array_map and array_filter).  If // there multiple regions starting at the lowest bytecode offset, // pick the one with the largest profile weight. // Select the remaining regions, iteratively picking the most likely // region to execute next.