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