hphp/hhbbc/cfg.h

   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 #pragma once
  17
  18 #include <vector>
  19
  20 #include <boost/variant/static_visitor.hpp>
  21 #include <boost/container/flat_set.hpp>
  22
  23 #include "hphp/hhbbc/bc.h"
  24 #include "hphp/hhbbc/misc.h"
  25 #include "hphp/hhbbc/representation.h"
  26
  27 namespace HPHP { namespace HHBBC {
  28
  29 //////////////////////////////////////////////////////////////////////
  30
  31 namespace detail {
  32
  33 template<class Fun>
  34 void visitExnLeaves(const php::Func& func, const php::ExnNode& n, Fun f) {
  35   if (n.idx == NoExnNodeId) return;
  36   for (auto& c : n.children) visitExnLeaves(func, func.exnNodes[c], f);
  37   f(n);
  38 }
  39
  40 }
  41
  42 //////////////////////////////////////////////////////////////////////
  43
  44 /*
  45  * Returns whether a block consists of a single Nop instruction.
  46  */
  47 inline bool is_single_nop(const php::Block& b) {
  48   return b.hhbcs.size() == 1 && b.hhbcs.back().op == Op::Nop;
  49 }
  50
  51 /*
  52  * Returns whether a block consists of a single Throw instruction.
  53  */
  54 inline bool is_single_throw(const php::Block& b) {
  55   return b.hhbcs.size() == 1 && b.hhbcs.back().op == Op::Throw;
  56 }
  57
  58 /*
  59  * Walk through single_nop blocks to the next block that actually does
  60  * something.
  61  */
  62 BlockId next_real_block(const php::WideFunc& func, BlockId id);
  63
  64 /*
  65  * Walk through catch blocks, stopping at the first block which does
  66  * something other than just immediately throw.
  67  */
  68 std::pair<BlockId, ExnNodeId>
  69 next_catch_block(const php::WideFunc& func, BlockId id, ExnNodeId exnId);
  70
  71 /*
  72  * Call a function for every jump target of a given bytecode, or Op.
  73  * If the bytecode has no targets, the function is not called.
  74  */
  75 template<typename Bc, class Fun>
  76 void forEachTakenEdge(Bc& b, Fun f) {
  77   b.forEachTarget(f);
  78 }
  79
  80 /*
  81  * Call a function for every successor of `block'.
  82  *
  83  * Order unspecified, and the types of successor edges are not
  84  * distinguished.
  85  *
  86  * Exit edges are traversed only if the block consists of
  87  * more than a single Nop instruction.
  88  */
  89 template<class Fun>
  90 void forEachSuccessor(const php::Block& block, Fun f) {
  91   if (!is_single_nop(block)) {
  92     forEachTakenEdge(block.hhbcs.back(), f);
  93     if (block.throwExit != NoBlockId) f(block.throwExit);
  94   }
  95   if (block.fallthrough != NoBlockId) f(block.fallthrough);
  96 }
  97
  98 /*
  99  * Call a function for every successor of `block' that is reachable
 100  * through a fallthrough or taken edge.
 101  */
 102 template<class Block, class Fun>
 103 void forEachNormalSuccessor(Block& block, Fun f) {
 104   forEachTakenEdge(block.hhbcs.back(), f);
 105   if (block.fallthrough != NoBlockId) f(block.fallthrough);
 106 }
 107
 108 /*
 109  * Call a function for every successor of `block' that is reachable
 110  * through a non-throw edge.
 111  */
 112 template<class Fun>
 113 void forEachNonThrowSuccessor(const php::Block& block, Fun f) {
 114   forEachTakenEdge(block.hhbcs.back(), f);
 115   if (block.fallthrough != NoBlockId) f(block.fallthrough);
 116 }
 117
 118 /*
 119  * Obtain the blocks for a function in a reverse post order, starting
 120  * with the specified block.  The exact order is not specified.
 121  */
 122 std::vector<BlockId> rpoSortFromBlock(const php::WideFunc&, BlockId);
 123
 124 /*
 125  * Obtain the blocks for a function in a reverse post order, starting
 126  * with the main entry point.  The exact order is not specified.
 127  *
 128  * DV initializer blocks will not appear in this list.
 129  */
 130 std::vector<BlockId> rpoSortFromMain(const php::WideFunc&);
 131
 132 /*
 133  * Obtain the blocks for a function in a reverse post order, taking
 134  * into account all entry points.
 135  *
 136  * This can be thought of as an RPO on the CFG of Func starting from a
 137  * virtual empty "entry" block, with edges to each DV entry point and
 138  * an edge to the main entry point.
 139  */
 140 std::vector<BlockId> rpoSortAddDVs(const php::WideFunc&);
 141
 142 /*
 143  * Mappings from blocks to sets of blocks.
 144  *
 145  * The first level is indexed by block id.  The second is a set of
 146  * block pointers.
 147  */
 148 using BlockToBlocks = std::vector<
 149   boost::container::flat_set<BlockId>
 150 >;
 151
 152 /*
 153  * Find the immediate non-throw predecessors for each block in
 154  * an RPO-sorted list of blocks.
 155  *
 156  * The BlockToBlocks map returned will have any entry for each block
 157  * in the input array, but may not have entries for blocks that aren't
 158  * in the list.
 159  */
 160 BlockToBlocks
 161 computeNonThrowPreds(const php::WideFunc&, const std::vector<BlockId>&);
 162
 163 /*
 164  * Find the immediate throw predecessors for each block in an
 165  * RPO-sorted list of blocks.
 166  *
 167  * The BlockToBlocks map returned will have any entry for each block
 168  * in the input array, but may not have entries for blocks that aren't
 169  * in the list.
 170  */
 171 BlockToBlocks
 172 computeThrowPreds(const php::WideFunc&, const std::vector<BlockId>&);
 173
 174 /*
 175  * Visit each leaf in the ExnNode tree.
 176  */
 177 template<class Fun>
 178 void visitExnLeaves(const php::Func& func, Fun f) {
 179   for (auto& n : func.exnNodes) {
 180     detail::visitExnLeaves(func, n, f);
 181   }
 182 }
 183
 184 //////////////////////////////////////////////////////////////////////
 185
 186 }}