hphp/runtime/vm/jit/region-whole-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 <stack>
  18
  19 #include <folly/MapUtil.h>
  20
  21 #include "hphp/runtime/vm/jit/prof-data.h"
  22 #include "hphp/runtime/vm/jit/region-selection.h"
  23 #include "hphp/runtime/vm/jit/trans-cfg.h"
  24 #include "hphp/util/trace.h"
  25
  26 namespace HPHP { namespace jit {
  27
  28 TRACE_SET_MOD(pgo);
  29
  30 struct DFS {
  31   DFS(const ProfData* p, const TransCFG& c, TransIDSet& ts, TransIDVec* tv)
  32       : m_profData(p)
  33       , m_cfg(c)
  34       , m_selectedSet(ts)
  35       , m_selectedVec(tv)
  36       , m_numBCInstrs(0)
  37     {}
  38
  39   RegionDescPtr formRegion(TransID head) {
  40     m_region = std::make_shared<RegionDesc>();
  41     m_selectedSet.clear();
  42     if (m_selectedVec) m_selectedVec->clear();
  43     visit(head);
  44     if (m_selectedVec) {
  45       std::reverse(m_selectedVec->begin(), m_selectedVec->end());
  46     }
  47     for (auto& arc : m_arcs) {
  48       m_region->addArc(arc.src, arc.dst);
  49     }
  50     return m_region;
  51   }
  52
  53  private:
  54
  55   void visit(TransID tid) {
  56     auto tidRegion = m_profData->transRegion(tid);
  57     auto tidInstrs = tidRegion->instrSize();
  58     if (m_numBCInstrs + tidInstrs > RuntimeOption::EvalJitMaxRegionInstrs) {
  59       return;
  60     }
  61
  62     if (m_visited.count(tid)) return;
  63     m_visited.insert(tid);
  64     m_visiting.insert(tid);
  65
  66     auto sk = m_profData->transSrcKey(tid);
  67     m_srcKeyToTransID[sk] = tid;
  68
  69     if (!breaksRegion(*(m_profData->transLastInstr(tid)))) {
  70
  71       auto srcBlockId = tidRegion->blocks().back().get()->id();
  72
  73       for (auto const arc : m_cfg.outArcs(tid)) {
  74         auto dst = arc->dst();
  75
  76         // If dst is in the visiting set then this arc forms a cycle. Don't
  77         // include it unless we've asked for loops.
  78         if (!RuntimeOption::EvalJitLoops && m_visiting.count(dst)) continue;
  79
  80         // Skip dst if region already has another block with the same SrcKey.
  81         // Task #4157613: add support for regions with multiple blocks with
  82         // the same SrcKey.
  83         auto dstSK = m_profData->transSrcKey(dst);
  84         if (folly::get_default(m_srcKeyToTransID, dstSK, dst) != dst) continue;
  85
  86         // Skip dst if we already generated a region starting at that SrcKey.
  87         if (m_profData->optimized(dstSK)) continue;
  88
  89         auto dstBlockId = m_profData->transRegion(dst)->entry()->id();
  90         m_arcs.push_back({srcBlockId, dstBlockId});
  91
  92         visit(dst);
  93       }
  94     }
  95
  96     // Now insert the region for tid in the front of m_region.  We do
  97     // this last so that the region ends up in (quasi-)topological order
  98     // (it'll be in topological order for acyclic regions).
  99     m_region->prepend(*tidRegion);
 100     m_selectedSet.insert(tid);
 101     if (m_selectedVec) m_selectedVec->push_back(tid);
 102     m_numBCInstrs += tidRegion->instrSize();
 103     always_assert(m_numBCInstrs <= RuntimeOption::EvalJitMaxRegionInstrs);
 104
 105     m_visiting.erase(tid);
 106   }
 107
 108
 109  private:
 110   const ProfData*                m_profData;
 111   const TransCFG&                m_cfg;
 112   TransIDSet&                    m_selectedSet;
 113   TransIDVec*                    m_selectedVec;
 114   RegionDescPtr                  m_region;
 115   uint32_t                       m_numBCInstrs;
 116   jit::hash_set<TransID>         m_visiting;
 117   jit::hash_set<TransID>         m_visited;
 118   jit::flat_map<SrcKey, TransID> m_srcKeyToTransID;
 119   jit::vector<RegionDesc::Arc>   m_arcs;
 120 };
 121
 122 /*
 123  * Constructs a region, beginning with triggerId, that includes as much of the
 124  * TransCFG as possible.  Excludes multiple translations of the same SrcKey.
 125  */
 126 RegionDescPtr selectWholeCFG(TransID triggerId,
 127                              const ProfData* profData,
 128                              const TransCFG& cfg,
 129                              TransIDSet& selectedSet,
 130                              TransIDVec* selectedVec) {
 131   return DFS(profData, cfg, selectedSet, selectedVec).formRegion(triggerId);
 132 }
 133
 134 }}