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