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 void postorderWalk(const php::Func& func,
  29                    std::vector<borrowed_ptr<php::Block>>& out,
  30                    boost::dynamic_bitset<>& visited,
  31                    php::Block& blk) {
  32   if (visited[blk.id]) return;
  33   visited[blk.id] = true;
  34   forEachSuccessor(blk, [&] (BlockId next) {
  35       postorderWalk(func, out, visited, *func.blocks[next]);
  36   });
  37   out.push_back(&blk);
  38 }
  39
  40 }
  41
  42 //////////////////////////////////////////////////////////////////////
  43
  44 std::vector<borrowed_ptr<php::Block>> rpoSortFromMain(const php::Func& func) {
  45   boost::dynamic_bitset<> visited(func.blocks.size());
  46   std::vector<borrowed_ptr<php::Block>> ret;
  47   ret.reserve(func.blocks.size());
  48   postorderWalk(func, ret, visited, *func.blocks[func.mainEntry]);
  49   std::reverse(begin(ret), end(ret));
  50   return ret;
  51 }
  52
  53 std::vector<borrowed_ptr<php::Block>> rpoSortAddDVs(const php::Func& func) {
  54   boost::dynamic_bitset<> visited(func.blocks.size());
  55   std::vector<borrowed_ptr<php::Block>> ret;
  56   ret.reserve(func.blocks.size());
  57   postorderWalk(func, ret, visited, *func.blocks[func.mainEntry]);
  58
  59   /*
  60    * We've already marked the blocks reachable from the main entry
  61    * point.  Do post order walks from each DV entry with the same
  62    * visited set (so we'll stop if they chain to the main entry, which
  63    * is the normal case).
  64    */
  65   for (auto it = func.params.end(); it != func.params.begin(); ) {
  66     --it;
  67     if (it->dvEntryPoint == NoBlockId) continue;
  68     postorderWalk(func, ret, visited, *func.blocks[it->dvEntryPoint]);
  69   }
  70   std::reverse(begin(ret), end(ret));
  71   return ret;
  72 }
  73
  74 BlockToBlocks
  75 computeNormalPreds(const std::vector<borrowed_ptr<php::Block>>& rpoBlocks) {
  76   auto preds = BlockToBlocks{};
  77   preds.reserve(rpoBlocks.size());
  78   for (auto& b : rpoBlocks) {
  79     if (preds.size() < b->id + 1) {
  80       preds.resize(b->id + 1);
  81     }
  82     forEachNormalSuccessor(*b, [&] (BlockId blkId) {
  83       if (preds.size() < blkId + 1) {
  84         preds.resize(blkId + 1);
  85       }
  86       preds[blkId].insert(b);
  87     });
  88   }
  89   return preds;
  90 }
  91
  92 BlockToBlocks
  93 computeFactoredPreds(const std::vector<borrowed_ptr<php::Block>>& rpoBlocks) {
  94   auto preds = BlockToBlocks{};
  95   preds.reserve(rpoBlocks.size());
  96   for (auto& b : rpoBlocks) {
  97     if (preds.size() < b->id + 1) {
  98       preds.resize(b->id + 1);
  99     }
 100     for (auto& ex : b->factoredExits) {
 101       if (preds.size() < ex + 1) {
 102         preds.resize(ex + 1);
 103       }
 104       preds[ex].insert(b);
 105     }
 106   }
 107   return preds;
 108 }
 109
 110 /*
 111  * Walk forward through no-op blocks. To avoid cycles we don't take
 112  * "backward" branches unless its to the lowest numbered block seen to
 113  * date (this is just a heuristic to avoid having to keep a seen set,
 114  * because we don't expect long cyclic chains of no-op blocks).
 115  */
 116 BlockId next_real_block(const php::Func& func, BlockId id) {
 117   auto blk = borrow(func.blocks[id]);
 118   auto min = id;
 119   while (is_single_nop(*blk)) {
 120     if (blk->fallthrough == id || blk->fallthrough == NoBlockId) break;
 121     if (blk->fallthrough < id) {
 122       if (blk->fallthrough >= min) {
 123         // we may be in a cycle, but take one more hop anyway,
 124         // in case we're not.
 125         id = blk->fallthrough;
 126         break;
 127       }
 128       min = blk->fallthrough;
 129     }
 130     id = blk->fallthrough;
 131     blk = borrow(func.blocks[id]);
 132   }
 133   return id;
 134 }
 135
 136 //////////////////////////////////////////////////////////////////////
 137
 138 }}