hphp/runtime/vm/jit/region-hot-trace.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 "hphp/runtime/vm/jit/region-selection.h"
  18
  19 #include "hphp/runtime/vm/jit/location.h"
  20 #include "hphp/runtime/vm/jit/prof-data.h"
  21 #include "hphp/runtime/vm/jit/trans-cfg.h"
  22 #include "hphp/runtime/vm/jit/translator-inline.h"
  23
  24 #include <limits>
  25
  26 namespace HPHP { namespace jit {
  27
  28 TRACE_SET_MOD(pgo);
  29
  30 /**
  31  * Remove from pConds the elements that correspond to stack positions
  32  * that have been popped given the current SP offset from FP.
  33  */
  34 static void discardPoppedTypes(TypedLocations& pConds,
  35                                SBInvOffset curSpOffset) {
  36   for (auto it = pConds.begin(); it != pConds.end(); ) {
  37     if (it->location.tag() == LTag::Stack &&
  38         it->location.stackIdx() > curSpOffset) {
  39       it = pConds.erase(it);
  40     } else {
  41       it++;
  42     }
  43   }
  44 }
  45
  46 static void mergePostConds(TypedLocations& dst,
  47                            const PostConditions& src) {
  48   for (const auto &post : src.changed) {
  49     bool replace = false;
  50     for (auto it = dst.begin(); it != dst.end(); ++it) {
  51       if (post.location == it->location) {
  52         *it = post;
  53         replace = true;
  54       }
  55     }
  56     if (!replace) {
  57       dst.emplace_back(post);
  58     }
  59   }
  60 }
  61
  62 RegionDescPtr selectHotTrace(HotTransContext& ctx) {
  63   auto region = std::make_shared<RegionDesc>();
  64   assertx(ctx.entries.size() == 1);
  65   TransID tid    = *ctx.entries.begin();
  66   TransID prevId = kInvalidTransID;
  67   TransIDSet selectedSet;
  68   TypedLocations accumPostConds;
  69
  70   // Maps from BlockIds to accumulated post conditions for that block.
  71   // Used to determine if we can add branch-over edges by checking the
  72   // pre-conditions of the successor block.
  73   hphp_hash_map<RegionDesc::BlockId, TypedLocations> blockPostConds;
  74
  75   auto numBCInstrs = ctx.maxBCInstrs;
  76   FTRACE(1, "selectHotTrace: starting with maxBCInstrs = {}\n", numBCInstrs);
  77
  78   while (!selectedSet.count(tid)) {
  79     auto rec = ctx.profData->transRec(tid);
  80     auto blockRegion = rec->region();
  81     if (blockRegion == nullptr) break;
  82
  83     // Break if region would be larger than the specified limit.
  84     if (blockRegion->instrSize() > numBCInstrs) {
  85       FTRACE(2, "selectHotTrace: breaking region at Translation {} because "
  86              "size would exceed of maximum translation limit\n", tid);
  87       break;
  88     }
  89
  90     // If the debugger is attached, only allow single-block regions.
  91     if (prevId != kInvalidTransID && isDebuggerAttachedProcess()) {
  92       FTRACE(2, "selectHotTrace: breaking region at Translation {} "
  93              "because of debugger is attached\n", tid);
  94       break;
  95     }
  96
  97     // Break if block is not the first and it corresponds to the main
  98     // function body entry.  This is to prevent creating multiple
  99     // large regions containing the function body (starting at various
 100     // DV funclets).
 101     if (prevId != kInvalidTransID) {
 102       auto const sk = rec->srcKey();
 103       if (!sk.funcEntry() && sk.offset() == 0) {
 104         FTRACE(2, "selectHotTrace: breaking region because reached the main "
 105                "function body entry at Translation {} (BC offset 0)\n",
 106                tid);
 107         break;
 108       }
 109     }
 110
 111     if (prevId != kInvalidTransID) {
 112       auto sk = rec->srcKey();
 113       if (ctx.profData->optimized(sk)) {
 114         FTRACE(2, "selectHotTrace: breaking region because next sk already "
 115                "optimized, for Translation {}\n", tid);
 116         break;
 117       }
 118     }
 119
 120     bool hasPredBlock = !region->empty();
 121     RegionDesc::BlockId predBlockId = (hasPredBlock ?
 122                                        region->blocks().back().get()->id() : 0);
 123     auto const& newFirstBlock = blockRegion->entry();
 124     auto newFirstBlockId = newFirstBlock->id();
 125
 126     // Add blockRegion's blocks and arcs to region.
 127     region->append(*blockRegion);
 128     numBCInstrs -= blockRegion->instrSize();
 129     assertx(numBCInstrs >= 0);
 130
 131     if (hasPredBlock) {
 132       region->addArc(predBlockId, newFirstBlockId);
 133     }
 134     selectedSet.insert(tid);
 135
 136     const auto lastSk = rec->lastSrcKey();
 137     if (breaksRegion(lastSk)) {
 138       FTRACE(2, "selectHotTrace: breaking region because of last instruction "
 139              "in Translation {}: {}\n", tid, opcodeToName(lastSk.op()));
 140       break;
 141     }
 142
 143     auto outArcs = ctx.cfg->outArcs(tid);
 144     if (outArcs.size() == 0) {
 145       FTRACE(2, "selectHotTrace: breaking region because there's no successor "
 146              "for Translation {}\n", tid);
 147       break;
 148     }
 149
 150     auto newLastBlock = blockRegion->blocks().back();
 151     discardPoppedTypes(accumPostConds,
 152                        blockRegion->entry()->initialSpOffset());
 153     mergePostConds(accumPostConds, newLastBlock->postConds());
 154     blockPostConds[newLastBlock->id()] = accumPostConds;
 155
 156     TransCFG::ArcPtrVec possibleOutArcs;
 157     for (auto arc : outArcs) {
 158       auto dstRec = ctx.profData->transRec(arc->dst());
 159       auto possibleNext = dstRec->region()->entry();
 160       if (preCondsAreSatisfied(possibleNext, accumPostConds)) {
 161         possibleOutArcs.emplace_back(arc);
 162       }
 163     }
 164
 165     if (possibleOutArcs.size() == 0) {
 166       FTRACE(2, "selectHotTrace: breaking region because postcondition check "
 167              "pruned all successors of Translation {}\n", tid);
 168       break;
 169     }
 170
 171     auto maxWeight = std::numeric_limits<int64_t>::min();
 172     TransCFG::Arc* maxArc = nullptr;
 173     for (auto arc : possibleOutArcs) {
 174       if (arc->weight() >= maxWeight) {
 175         maxWeight = arc->weight();
 176         maxArc = arc;
 177       }
 178     }
 179     assertx(maxArc != nullptr);
 180     prevId = tid;
 181     tid = maxArc->dst();
 182   }
 183
 184   FTRACE(3, "selectHotTrace: before chainRetransBlocks:\n{}\n", show(*region));
 185   region->chainRetransBlocks();
 186   FTRACE(3, "selectHotTrace: after chainRetransBlocks:\n{}\n", show(*region));
 187
 188   return region;
 189 }
 190
 191 } }