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

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