hphp/runtime/vm/jit/regionize-func.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include <algorithm>
  18 #include <fstream>
  19 #include <sstream>
  20 #include <vector>
  21
  22 #include "hphp/util/assertions.h"
  23 #include "hphp/runtime/base/runtime-option.h"
  24 #include "hphp/runtime/vm/jit/mcgen.h"
  25 #include "hphp/runtime/vm/jit/prof-data.h"
  26 #include "hphp/runtime/vm/jit/region-selection.h"
  27 #include "hphp/runtime/vm/jit/tc.h"
  28 #include "hphp/runtime/vm/jit/timer.h"
  29 #include "hphp/runtime/vm/jit/trans-cfg.h"
  30 #include "hphp/runtime/vm/jit/translator-inline.h"
  31 #include "hphp/runtime/vm/jit/translator.h"
  32
  33 namespace HPHP { namespace jit {
  34
  35 TRACE_SET_MOD(pgo);
  36
  37 //////////////////////////////////////////////////////////////////////
  38
  39 namespace {
  40
  41 using TransIDToRegionMap = hphp_hash_map<TransID, RegionDescPtr>;
  42 using RegionToTransIDsMap = hphp_hash_map<
  43   RegionDescPtr,
  44   TransIDVec,
  45   smart_pointer_hash<RegionDescPtr>
  46 >;
  47
  48 /**
  49  * Returns the set of of TransIDs that are in `bid's retranslation
  50  * chain in `region'.
  51  */
  52 TransIDSet findRetransSet(const RegionDesc& region, RegionDesc::BlockId bid) {
  53   TransIDSet set;
  54   auto insert = [&](RegionDesc::BlockId id) {
  55     set.insert(id);
  56     auto& merged = region.merged(id);
  57     set.insert(merged.begin(), merged.end());
  58   };
  59   insert(bid);
  60   while (auto next = region.nextRetrans(bid)) {
  61     bid = next.value();
  62     insert(bid);
  63   }
  64   return set;
  65 }
  66
  67 /**
  68  * Add to `coveredArcs' all `cfg's arcs going from `src' to 'dst' or
  69  * any of `dst's retranslations in `dstRegion'.
  70  */
  71 void markCoveredArc(TransID src,
  72                     TransID dst,
  73                     const TransCFG& cfg,
  74                     const RegionDesc& dstRegion,
  75                     TransCFG::ArcPtrSet& coveredArcs) {
  76   auto dstRetransSet = findRetransSet(dstRegion, dst);
  77   for (auto outArc : cfg.outArcs(src)) {
  78     if (dstRetransSet.count(outArc->dst())) {
  79       coveredArcs.insert(outArc);
  80     }
  81   }
  82 }
  83
  84 /**
  85  * Add to sets coveredNodes and coveredArcs the cfg arcs that are now
  86  * covered given the new region containing the translations in `region'.
  87  */
  88 void markCovered(const TransCFG& cfg, const RegionDescPtr region,
  89                  TransIDSet& heads,
  90                  TransIDToRegionMap& headToRegion,
  91                  TransIDSet& coveredNodes,
  92                  TransCFG::ArcPtrSet& coveredArcs) {
  93   assertx(!region->empty());
  94   const auto entryId = region->entry()->id();
  95
  96   // Mark all region's nodes as covered.
  97   for (auto& b : region->blocks()) {
  98     coveredNodes.insert(b->id());
  99     const auto& merged = region->merged(b->id());
 100     coveredNodes.insert(merged.begin(), merged.end());
 101   }
 102
 103   // Mark as covered all incoming arcs from already covered nodes into the entry
 104   // of the region or one of its retranslations/merged blocks.
 105   for (auto newHead : findRetransSet(*region, entryId)) {
 106     heads.insert(newHead);
 107     headToRegion[newHead] = region;
 108     for (auto arc : cfg.inArcs(newHead)) {
 109       const auto src = arc->src();
 110       if (coveredNodes.count(src)) {
 111         markCoveredArc(src, entryId, cfg, *region, coveredArcs);
 112       }
 113     }
 114   }
 115
 116   // Mark all CFG arcs within the region as covered.
 117   region->forEachArc([&](RegionDesc::BlockId src, RegionDesc::BlockId dst) {
 118     auto const srcIds = findRetransSet(*region, src);
 119     auto const dstIds = findRetransSet(*region, dst);
 120
 121     for (auto srcId : srcIds) {
 122       for (auto arc : cfg.outArcs(srcId)) {
 123         if (dstIds.count(arc->dst())) {
 124           coveredArcs.insert(arc);
 125         }
 126       }
 127     }
 128   });
 129
 130   // Mark all outgoing arcs from the region to a head node as covered.
 131   for (auto& b : region->blocks()) {
 132     for (auto srcId : findRetransSet(*region, b->id())) {
 133       for (auto arc : cfg.outArcs(srcId)) {
 134         if (heads.count(arc->dst())) {
 135           auto dstRegionEntryId = headToRegion[arc->dst()]->entry()->id();
 136           markCoveredArc(arc->src(), dstRegionEntryId, cfg,
 137                          *headToRegion[arc->dst()], coveredArcs);
 138         }
 139       }
 140     }
 141   }
 142 }
 143
 144 /**
 145  * Returns the sum of the weights of the arcs going from srcs to dst.
 146  */
 147 int64_t interRegionWeight(const TransIDVec& srcs,
 148                           TransID           dst,
 149                           const TransCFG&   cfg) {
 150   int64_t totalWeight = 0;
 151   for (auto src : srcs) {
 152     for (auto arc : cfg.outArcs(src)) {
 153       if (arc->dst() == dst) {
 154         totalWeight += arc->weight();
 155       }
 156     }
 157   }
 158   return totalWeight;
 159 }
 160
 161 const TransIDVec& getRegionTransIDVec(const RegionToTransIDsMap& map,
 162                                       RegionDescPtr region) {
 163   auto it = map.find(region);
 164   assertx(it != map.end());
 165   return it->second;
 166 }
 167
 168 /**
 169  * Sorts the regions vector in a linear order to be used for
 170  * translation.  The goal is to obtain an order that improves locality
 171  * when the function is executed.  Each region is translated separately.
 172  */
 173 void sortRegions(RegionVec& regions, const Func* /*func*/, const TransCFG& cfg,
 174                  const ProfData* profData,
 175                  const TransIDToRegionMap& /*headToRegion*/,
 176                  const RegionToTransIDsMap& regionToTransIds) {
 177   if (regions.empty()) return;
 178
 179   // First, pick the region starting at the lowest bytecode offset.
 180   // This will normally correspond to the main function entry (for
 181   // normal, regular bytecode), but it may not be for irregular
 182   // functions written in hhas (like array_map and array_filter).  If
 183   // there multiple regions starting at the lowest bytecode offset,
 184   // pick the one with the largest profile weight.
 185   RegionDescPtr entryRegion = nullptr;
 186   int64_t maxEntryWeight = -1;
 187   auto lowestOffset = kInvalidOffset;
 188   for (const auto& pair : regionToTransIds) {
 189     auto r    = pair.first;
 190     auto& tids = pair.second;
 191     auto const firstTid = tids[0];
 192     auto const firstOffset = profData->transRec(firstTid)->srcKey().offset();
 193     auto const weight = cfg.weight(firstTid);
 194     if (lowestOffset == kInvalidOffset || firstOffset < lowestOffset ||
 195         (firstOffset == lowestOffset && weight > maxEntryWeight)) {
 196       entryRegion = r;
 197       maxEntryWeight = weight;
 198       lowestOffset = firstOffset;
 199     }
 200   }
 201
 202   assertx(entryRegion);
 203   RegionVec sorted {entryRegion};
 204   RegionSet selected;
 205   selected.insert(entryRegion);
 206
 207   RegionDescPtr region = entryRegion;
 208   // Select the remaining regions, iteratively picking the most likely
 209   // region to execute next.
 210   for (auto i = 1; i < regions.size(); i++) {
 211     int64_t      maxWeight = -1;
 212     int64_t  maxHeadWeight = -1;
 213     RegionDescPtr bestNext = nullptr;
 214     auto    regionTransIds = getRegionTransIDVec(regionToTransIds, region);
 215     for (auto next : regions) {
 216       if (selected.count(next)) continue;
 217       auto nextTransIds = getRegionTransIDVec(regionToTransIds, next);
 218       int64_t weight = interRegionWeight(regionTransIds, nextTransIds[0], cfg);
 219       int64_t headWeight = cfg.weight(nextTransIds[0]);
 220       if ((weight >  maxWeight) ||
 221           (weight == maxWeight && headWeight > maxHeadWeight)) {
 222         maxWeight     = weight;
 223         maxHeadWeight = headWeight;
 224         bestNext      = next;
 225       }
 226     }
 227     assertx(bestNext);
 228     sorted.push_back(bestNext);
 229     selected.insert(bestNext);
 230     region = bestNext;
 231   }
 232
 233   assertx(sorted.size() == regions.size());
 234   regions = sorted;
 235
 236   if (debug && Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
 237     for (size_t i = 0; i < regions.size(); i++) {
 238       auto r = regions[i];
 239       auto tids = getRegionTransIDVec(regionToTransIds, r);
 240       std::string transIds = folly::join(", ", tids);
 241       FTRACE(6, "sortRegions: region[{}]: {}\n", i, transIds);
 242     }
 243   }
 244 }
 245
 246 bool allArcsCovered(const TransCFG::ArcPtrVec& arcs,
 247                     const TransCFG::ArcPtrSet& coveredArcs) {
 248   for (auto arc : arcs) {
 249     if (!coveredArcs.count(arc)) {
 250       return false;
 251     }
 252   }
 253   return true;
 254 }
 255
 256 }
 257
 258 //////////////////////////////////////////////////////////////////////
 259
 260 /**
 261  * Regionize a func, so that each node and each arc in its TransCFG is
 262  * "covered".  A node is covered if any region contains it.  An arc T1->T2
 263  * is covered if either:
 264  *
 265  *   a) T1 and T2 are in the same region R and R contains arc T1->T2.
 266  *   b) T2 is the head (first translation) of a region.
 267  *
 268  * Basic algorithm:
 269  *
 270  *   1) sort nodes in decreasing weight order
 271  *   2) for each node N:
 272  *      2.1) if N and all its incoming arcs are covered, then continue
 273  *      2.2) select a region starting at this node and mark nodes/arcs as
 274  *           covered appropriately
 275  */
 276 RegionVec regionizeFunc(const Func* func, std::string& transCFGAnnot) {
 277   const Timer rf_timer(Timer::regionizeFunc);
 278   assertx(profData());
 279
 280   tracing::Block _{"regionize-func", [&] { return traceProps(func); }};
 281
 282   auto regionMode = pgoRegionMode(*func);
 283
 284   auto const funcId = func->getFuncId();
 285   auto const profData = jit::profData();
 286   TransCFG cfg(funcId, profData);
 287
 288   if (Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
 289     auto dotFileName = folly::to<std::string>(
 290       "/tmp/func-cfg-", funcId.toInt(), ".dot");
 291     std::ofstream outFile(dotFileName);
 292     if (outFile.is_open()) {
 293       cfg.print(outFile, funcId, profData);
 294       FTRACE(5, "regionizeFunc: initial CFG for func {} saved to file {}\n",
 295              funcId, dotFileName);
 296       outFile.close();
 297     }
 298   }
 299   if (mcgen::dumpTCAnnotation(TransKind::Optimize) &&
 300       RuntimeOption::EvalDumpRegion >= 2) {
 301     std::ostringstream cfgStream;
 302     cfg.print(cfgStream, funcId, profData);
 303     transCFGAnnot = cfgStream.str();
 304   }
 305
 306   auto arcs = cfg.arcs();
 307   auto nodes = cfg.nodes();
 308
 309   std::sort(
 310     nodes.begin(),
 311     nodes.end(),
 312     [&](TransID tid1, TransID tid2) -> bool {
 313       if (regionMode == PGORegionMode::WholeCFG ||
 314           regionMode == PGORegionMode::HotCFG) {
 315         auto sk1 = profData->transRec(tid1)->srcKey();
 316         auto sk2 = profData->transRec(tid2)->srcKey();
 317         if (sk1 != sk2) return sk1.offset() < sk2.offset();
 318       }
 319       if (cfg.weight(tid1) != cfg.weight(tid2)) {
 320         return cfg.weight(tid1) > cfg.weight(tid2);
 321       }
 322       // In case of ties, pick older translations first, in an attempt to start
 323       // loops at their headers.
 324       return tid1 < tid2;
 325     }
 326   );
 327
 328   TransCFG::ArcPtrSet coveredArcs;
 329   TransIDSet coveredNodes;
 330   TransIDSet heads;
 331   TransIDToRegionMap headToRegion;
 332   RegionToTransIDsMap regionToTransIds;
 333   RegionVec regions;
 334
 335   for (auto node : nodes) {
 336     if (!coveredNodes.count(node) ||
 337         !allArcsCovered(cfg.inArcs(node),  coveredArcs)) {
 338       auto newHead = node;
 339       // If the weight of node is too low, we mark it and its incoming arcs as
 340       // covered but skip generating a region starting at it to reduce code
 341       // size.  This node will probably trigger a live translation instead.
 342       auto const minBlkPerc = RuntimeOption::EvalJitPGOMinBlockCountPercent;
 343       if (cfg.weight(node) < cfg.weight(nodes[0]) * minBlkPerc / 100) {
 344         FTRACE(3, "regionizeFunc: skipping forming a region to cover node {}\n",
 345                newHead);
 346         coveredNodes.insert(node);
 347         auto const& inArcs = cfg.inArcs(node);
 348         coveredArcs.insert(inArcs.begin(), inArcs.end());
 349         for (auto outArc : cfg.outArcs(node)) {
 350           if (heads.count(outArc->dst())) {
 351             coveredArcs.insert(outArc);
 352           }
 353         }
 354         continue;
 355       }
 356       FTRACE(6, "regionizeFunc: selecting trace to cover node {}\n", newHead);
 357       RegionDescPtr region;
 358       HotTransContext ctx;
 359       ctx.cfg = &cfg;
 360       ctx.profData = profData;
 361       ctx.entries = {newHead};
 362       ctx.maxBCInstrs = RuntimeOption::EvalJitMaxRegionInstrs;
 363       switch (regionMode) {
 364         case PGORegionMode::Hottrace:
 365           region = selectHotTrace(ctx);
 366           break;
 367
 368         case PGORegionMode::WholeCFG:
 369         case PGORegionMode::HotCFG:
 370           region = selectHotCFG(ctx);
 371           break;
 372
 373         case PGORegionMode::Hotblock:
 374           always_assert(0 && "Invalid value for EvalJitPGORegionSelector");
 375       }
 376       FTRACE(6, "regionizeFunc: selected region to cover node {}\n{}\n",
 377              newHead, show(*region));
 378       profData->setOptimized(profData->transRec(newHead)->srcKey());
 379
 380       for (auto& b : region->blocks()) {
 381         const auto bid = b->id();
 382         assertx(hasTransID(bid) &&
 383                 bid == getTransID(bid) &&
 384                 bid == b->profTransID());
 385         regionToTransIds[region].push_back(bid);
 386       }
 387
 388       regions.emplace_back(region);
 389       markCovered(cfg, region, heads, headToRegion, coveredNodes, coveredArcs);
 390     }
 391   }
 392
 393   assertx(coveredNodes.size() == cfg.nodes().size());
 394   assertx(coveredArcs.size() == arcs.size());
 395
 396   sortRegions(regions, func, cfg, profData, headToRegion, regionToTransIds);
 397
 398   if (debug && Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
 399     FTRACE(5, "\n--------------------------------------------\n"
 400            "regionizeFunc({}): computed regions:\n", funcId);
 401     for (auto region : regions) {
 402       FTRACE(5, "{}\n\n", show(*region));
 403     }
 404   }
 405
 406   return regions;
 407 }
 408
 409 }}