hphp/hhbbc/cfg.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 #include "hphp/hhbbc/cfg.h"
  17
  18 #include <boost/dynamic_bitset.hpp>
  19 #include <algorithm>
  20 #include <vector>
  21
  22 namespace HPHP { namespace HHBBC {
  23
  24 //////////////////////////////////////////////////////////////////////
  25
  26 namespace {
  27
  28 /*
  29  * Note: Our style is generally to use lambdas, rather than helper
  30  * classes. postOrderWalk was originally written using a lambda,
  31  * rather than a helper class, but that ended up taking nearly 1k per
  32  * recursive call, which means it only takes about 10000 blocks to
  33  * overflow the stack.
  34  *
  35  * By putting everything in a helper class, we get that down to ~128
  36  * bytes per recursive call, which is a lot less likely to hit issues.
  37  *
  38  */
  39 struct PostOrderWalker {
  40   const php::Func& func;
  41   std::vector<BlockId>& out;
  42   boost::dynamic_bitset<>& visited;
  43   const hphp_fast_map<BlockId, std::vector<BlockId>>* extraIds;
  44
  45   void walk(BlockId blk) {
  46     if (visited[blk]) return;
  47     visited[blk] = true;
  48     forEachSuccessor(
  49       *func.blocks[blk],
  50       [this] (BlockId next) {
  51         walk(next);
  52       }
  53     );
  54     if (extraIds) {
  55       auto const it = extraIds->find(blk);
  56       if (it != extraIds->end()) {
  57         for (auto next : it->second) walk(next);
  58       }
  59     }
  60     out.push_back(blk);
  61   }
  62 };
  63
  64 void postorderWalk(
  65     const php::Func& func,
  66     std::vector<BlockId>& out,
  67     boost::dynamic_bitset<>& visited,
  68     BlockId blk,
  69     hphp_fast_map<BlockId, std::vector<BlockId>>* extraIds = nullptr) {
  70   auto walker = PostOrderWalker { func, out, visited, extraIds };
  71   walker.walk(blk);
  72 }
  73
  74 }
  75
  76 //////////////////////////////////////////////////////////////////////
  77
  78 std::vector<BlockId> rpoSortFromBlock(
  79     const php::Func& func,
  80     BlockId start,
  81     hphp_fast_map<BlockId, std::vector<BlockId>>* extraIds) {
  82   boost::dynamic_bitset<> visited(func.blocks.size());
  83   std::vector<BlockId> ret;
  84   ret.reserve(func.blocks.size());
  85   postorderWalk(func, ret, visited, start, extraIds);
  86   std::reverse(begin(ret), end(ret));
  87   return ret;
  88 }
  89
  90 std::vector<BlockId> rpoSortFromMain(
  91     const php::Func& func,
  92     hphp_fast_map<BlockId, std::vector<BlockId>>* extraIds) {
  93   return rpoSortFromBlock(func, func.mainEntry, extraIds);
  94 }
  95
  96 std::vector<BlockId> rpoSortAddDVs(const php::Func& func) {
  97   boost::dynamic_bitset<> visited(func.blocks.size());
  98   std::vector<BlockId> ret;
  99   ret.reserve(func.blocks.size());
 100   postorderWalk(func, ret, visited, func.mainEntry);
 101
 102   /*
 103    * We've already marked the blocks reachable from the main entry
 104    * point.  Do post order walks from each DV entry with the same
 105    * visited set (so we'll stop if they chain to the main entry, which
 106    * is the normal case).
 107    */
 108   for (auto it = func.params.end(); it != func.params.begin(); ) {
 109     --it;
 110     if (it->dvEntryPoint == NoBlockId) continue;
 111     postorderWalk(func, ret, visited, it->dvEntryPoint);
 112   }
 113   std::reverse(begin(ret), end(ret));
 114   return ret;
 115 }
 116
 117 BlockToBlocks
 118 computeNonThrowPreds(const php::Func& func,
 119                      const std::vector<BlockId>& rpoBlocks) {
 120   auto preds = BlockToBlocks{};
 121   preds.reserve(rpoBlocks.size());
 122   for (auto const bid : rpoBlocks) {
 123     if (preds.size() < bid + 1) {
 124       preds.resize(bid + 1);
 125     }
 126     auto const b = func.blocks[bid].get();
 127     forEachNonThrowSuccessor(*b, [&] (BlockId blkId) {
 128       if (preds.size() < blkId + 1) {
 129         preds.resize(blkId + 1);
 130       }
 131       preds[blkId].insert(bid);
 132     });
 133   }
 134   return preds;
 135 }
 136
 137 BlockToBlocks
 138 computeThrowPreds(const php::Func& func,
 139                   const std::vector<BlockId>& rpoBlocks) {
 140   auto preds = BlockToBlocks{};
 141   preds.reserve(rpoBlocks.size());
 142   for (auto const bid : rpoBlocks) {
 143     if (preds.size() < bid + 1) {
 144       preds.resize(bid + 1);
 145     }
 146     auto const b = func.blocks[bid].get();
 147     if (b->throwExit != NoBlockId) {
 148       if (preds.size() < b->throwExit + 1) {
 149         preds.resize(b->throwExit + 1);
 150       }
 151       preds[b->throwExit].insert(bid);
 152     }
 153   }
 154   return preds;
 155 }
 156
 157 /*
 158  * Walk forward through no-op blocks. To avoid cycles we don't take
 159  * "backward" branches unless its to the lowest numbered block seen to
 160  * date (this is just a heuristic to avoid having to keep a seen set,
 161  * because we don't expect long cyclic chains of no-op blocks).
 162  */
 163 BlockId next_real_block(const php::Func& func, BlockId id) {
 164   auto blk = func.blocks[id].get();
 165   auto min = id;
 166   while (is_single_nop(*blk)) {
 167     if (blk->fallthrough == id || blk->fallthrough == NoBlockId) break;
 168     if (blk->fallthrough < id) {
 169       if (blk->fallthrough >= min) {
 170         // we may be in a cycle, but take one more hop anyway,
 171         // in case we're not.
 172         id = blk->fallthrough;
 173         break;
 174       }
 175       min = blk->fallthrough;
 176     }
 177     id = blk->fallthrough;
 178     blk = func.blocks[id].get();
 179   }
 180   return id;
 181 }
 182
 183 //////////////////////////////////////////////////////////////////////
 184
 185 }}