hphp/runtime/vm/jit/trans-cfg.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2016 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/trans-cfg.h"
  18 #include <algorithm>
  19
  20 #include <folly/MapUtil.h>
  21
  22 #include "hphp/runtime/vm/jit/prof-data.h"
  23 #include "hphp/runtime/vm/jit/region-selection.h"
  24
  25 namespace HPHP { namespace jit {
  26
  27 TRACE_SET_MOD(pgo);
  28
  29 static TransIDSet findPredTrans(TransID dstID,
  30                                 const ProfData* profData,
  31                                 const SrcDB& srcDB) {
  32   auto const dstRec = profData->transRec(dstID);
  33   auto const dstSK = dstRec->srcKey();
  34   const SrcRec* dstSR = srcDB.find(dstSK);
  35   assertx(dstSR);
  36   TransIDSet predSet;
  37
  38   for (auto& inBr : dstSR->incomingBranches()) {
  39     auto const srcID = profData->jmpTransID(inBr.toSmash());
  40     if (srcID == kInvalidTransID) continue;
  41
  42     auto const srcRec = profData->transRec(srcID);
  43     if (!srcRec || !srcRec->isProfile()) continue;
  44
  45     FTRACE(5, "findPredTrans: toSmash = {}   srcID = {}\n",
  46            inBr.toSmash(), srcID);
  47     auto srcSuccOffsets = srcRec->lastSrcKey().succOffsets();
  48     if (srcSuccOffsets.count(dstSK.offset())) {
  49       predSet.insert(srcID);
  50     } else {
  51       FTRACE(5, "findPredTrans: WARNING: incoming branch with impossible "
  52              "control flow between translations: {} -> {}"
  53              "(probably due to side exit)\n", srcID, dstID);
  54     }
  55   }
  56
  57   return predSet;
  58 }
  59
  60 /**
  61  * This function tries to infer the weight of any arc in the arcVec given the
  62  * weights of other arcs in the list and totalWeight, which is the
  63  * known sum of all their weights.
  64  * Returns whether or not the weight of any arc was inferred and, in case of
  65  * success, the weight of such arc is updated.
  66  */
  67 static bool inferredArcWeight(const TransCFG::ArcPtrVec& arcVec,
  68                               int64_t totalWeight) {
  69   int64_t arcWeight = totalWeight;
  70   TransCFG::Arc* unknownArc = nullptr;
  71   for (auto arc : arcVec) {
  72     if (arc->weight() == TransCFG::Arc::kUnknownWeight) {
  73       if (unknownArc != nullptr) {
  74         // More than one arc with unknown weight, so can't infer
  75         return false;
  76       }
  77       unknownArc = arc;
  78     } else {
  79       arcWeight -= arc->weight();
  80     }
  81   }
  82   if (unknownArc == nullptr) return false;
  83   // Avoid creating negative-weight arcs. Node weights are not required to be
  84   // accurate and, since arc weights are derived from nodes' weights, they
  85   // aren't accurate either.  This can result in arcWeight to be negative here.
  86   if (arcWeight < 0) arcWeight = 0;
  87   unknownArc->setWeight(arcWeight);
  88   return true;
  89 }
  90
  91 TransCFG::TransCFG(FuncId funcId,
  92                    const ProfData* profData,
  93                    const SrcDB& srcDB,
  94                    bool inlining /* = false */) {
  95   assertx(profData);
  96
  97   // add nodes
  98   for (auto const tid : profData->funcProfTransIDs(funcId)) {
  99     auto const rec = profData->transRec(tid);
 100     assertx(rec->region() != nullptr);
 101     // This will skip DV Funclets if they were already
 102     // retranslated w/ the prologues:
 103     if (inlining || !profData->optimized(rec->srcKey())) {
 104       int64_t weight = profData->transCounter(tid);
 105       addNode(tid, weight);
 106     }
 107   }
 108
 109   // add arcs
 110   for (auto const dstId : nodes()) {
 111     auto const rec = profData->transRec(dstId);
 112     auto const dstSK = rec->srcKey();
 113     auto const dstBlock = rec->region()->entry();
 114     FTRACE(5, "TransCFG: adding incoming arcs in dstId = {}\n", dstId);
 115     TransIDSet predIDs = findPredTrans(dstId, profData, srcDB);
 116     for (auto predId : predIDs) {
 117       if (hasNode(predId)) {
 118         auto const predRec = profData->transRec(predId);
 119         auto const predBlock = predRec->region()->blocks().back();
 120         auto const& postConds = predBlock->postConds();
 121         auto predPostConds = postConds.changed;
 122         predPostConds.insert(predPostConds.end(), postConds.refined.begin(),
 123                              postConds.refined.end());
 124         auto const predSK = predRec->srcKey();
 125         if (preCondsAreSatisfied(dstBlock, predPostConds) &&
 126             predSK.resumed() == dstSK.resumed()) {
 127           FTRACE(5, "TransCFG: adding arc {} -> {} ({} -> {})\n",
 128                  predId, dstId, showShort(predSK), showShort(dstSK));
 129           addArc(predId, dstId, TransCFG::Arc::kUnknownWeight);
 130         }
 131       }
 132     }
 133   }
 134
 135   // infer arc weights
 136   bool changed;
 137   do {
 138     changed = false;
 139     for (auto const tid : nodes()) {
 140       auto const nodeWeight = weight(tid);
 141       if (inferredArcWeight(inArcs(tid),  nodeWeight)) changed = true;
 142       if (inferredArcWeight(outArcs(tid), nodeWeight)) changed = true;
 143     }
 144   } while (changed);
 145
 146   // guess weight for non-inferred arcs
 147   for (auto const tid : nodes()) {
 148     for (auto arc : outArcs(tid)) {
 149       if (arc->weight() == Arc::kUnknownWeight) {
 150         arc->setGuessed();
 151         auto arcWgt = std::min(weight(arc->src()), weight(arc->dst())) / 2;
 152         arc->setWeight(arcWgt);
 153       }
 154     }
 155   }
 156 }
 157
 158 int64_t TransCFG::weight(TransID id) const {
 159   assertx(hasNode(id));
 160   auto const idx = folly::get_default(m_idToIdx, id);
 161   return m_nodeInfo[idx].weight();
 162 }
 163
 164 const TransCFG::ArcPtrVec& TransCFG::inArcs(TransID id) const {
 165   assertx(hasNode(id));
 166   auto const idx = folly::get_default(m_idToIdx, id);
 167   return m_nodeInfo[idx].inArcs();
 168 }
 169
 170 const TransCFG::ArcPtrVec& TransCFG::outArcs(TransID id) const {
 171   assertx(hasNode(id));
 172   auto const idx = folly::get_default(m_idToIdx, id);
 173   return m_nodeInfo[idx].outArcs();
 174 }
 175
 176 TransCFG::Node::~Node() {
 177   for (auto arc : m_outArcs) {
 178     delete arc;
 179   }
 180 }
 181
 182 void TransCFG::addNode(TransID id, int64_t weight) {
 183   auto const idx = m_transIds.size();
 184   m_transIds.push_back(id);
 185   m_idToIdx[id] = idx;
 186   m_nodeInfo.push_back(Node(id, weight));
 187 }
 188
 189 bool TransCFG::hasNode(TransID id) const {
 190   return m_idToIdx.find(id) != m_idToIdx.end();
 191 }
 192
 193 TransCFG::ArcPtrVec TransCFG::arcs() const {
 194   ArcPtrVec arcs;
 195   for (auto node : nodes()) {
 196     const ArcPtrVec& nodeOutArcs = outArcs(node);
 197     arcs.insert(arcs.end(), nodeOutArcs.begin(), nodeOutArcs.end());
 198   }
 199   return arcs;
 200 }
 201
 202 void TransCFG::addArc(TransID srcId, TransID dstId, int64_t weight) {
 203   assertx(hasNode(srcId));
 204   assertx(hasNode(dstId));
 205   auto const srcIdx = m_idToIdx[srcId];
 206   auto const dstIdx = m_idToIdx[dstId];
 207   Arc* arc = new Arc(srcId, dstId, weight);
 208   m_nodeInfo[srcIdx].addOutArc(arc);
 209   m_nodeInfo[dstIdx].addInArc(arc);
 210 }
 211
 212 bool TransCFG::hasArc(TransID srcId, TransID dstId) const {
 213   assertx(hasNode(srcId));
 214   assertx(hasNode(dstId));
 215   for (auto arc : outArcs(srcId)) {
 216     if (arc->dst() == dstId) return true;
 217   }
 218   return false;
 219 }
 220
 221 void TransCFG::print(std::ostream& out, FuncId funcId,
 222                      const ProfData* profData) const {
 223   out << "digraph TransCFG { // function: "
 224       << Func::fromFuncId(funcId)->fullName()->data() << "\n";
 225
 226   // find max node weight
 227   int64_t maxWeight = 1; // 1 to avoid div by 0
 228   for (auto tid : nodes()) {
 229     auto w = weight(tid);
 230     if (w > maxWeight) maxWeight = w;
 231   }
 232
 233   // print nodes
 234   for (auto const tid : nodes()) {
 235     auto const w = weight(tid);
 236     uint32_t coldness  = 255 - (255 * w / maxWeight);
 237     auto const rec = profData->transRec(tid);
 238     auto const bcStart = rec->startBcOff();
 239     auto const bcStop  = rec->lastBcOff();
 240     auto const shape = "box";
 241     out << folly::sformat(
 242       "t{} [shape={},label=\"T: {}\\np: {}\\n"
 243       "bc: [{}-{})\",style=filled,fillcolor=\"#ff{:02x}{:02x}\"];\n",
 244       tid, shape, tid, w, bcStart, bcStop, coldness, coldness);
 245   }
 246
 247   // print arcs
 248   for (auto srcId : nodes()) {
 249     for (auto arc : outArcs(srcId)) {
 250       auto const w = arc->weight();
 251       out << folly::sformat("t{} -> t{} [color=\"{}\",label=\"{}\"] ;\n",
 252                             srcId,
 253                             arc->dst(),
 254                             arc->guessed() ? "red" : "green4",
 255                             w);
 256     }
 257   }
 258
 259   out << "}\n";
 260 }
 261
 262 }}