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::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 inline bool is_unsetl_throw(const php::Block& b) {
  59   if (b.hhbcs.empty() || b.hhbcs.back().op != Op::Throw) return false;
  60   for (auto const& bc : b.hhbcs) {
  61     switch (bc.op) {
  62       case Op::Nop:
  63       case Op::UnsetL:
  64       case Op::Throw:
  65         break;
  66       default:
  67         return false;
  68     }
  69   }
  70   return true;
  71 }
  72
  73 /*
  74  * Walk through single_nop blocks to the next block that actually does
  75  * something.
  76  */
  77 BlockId next_real_block(const php::WideFunc& func, BlockId id);
  78
  79 /*
  80  * Walk through catch blocks, stopping at the first block which does
  81  * something other than just immediately throw.
  82  */
  83 std::pair<BlockId, ExnNodeId>
  84 next_catch_block(const php::WideFunc& func, BlockId id, ExnNodeId exnId);
  85
  86 /*
  87  * Call a function for every jump target of a given bytecode, or Op.
  88  * If the bytecode has no targets, the function is not called.
  89  */
  90 template<typename Bc, class Fun>
  91 void forEachTakenEdge(Bc& b, Fun f) {
  92   b.forEachTarget(f);
  93 }
  94
  95 /*
  96  * Call a function for every successor of `block'.
  97  *
  98  * Order unspecified, and the types of successor edges are not
  99  * distinguished.
 100  *
 101  * Exit edges are traversed only if the block consists of
 102  * more than a single Nop instruction.
 103  */
 104 template<class Fun>
 105 void forEachSuccessor(const php::Block& block, Fun f) {
 106   if (!is_single_nop(block)) {
 107     forEachTakenEdge(block.hhbcs.back(), f);
 108     if (block.throwExit != NoBlockId) f(block.throwExit);
 109   }
 110   if (block.fallthrough != NoBlockId) f(block.fallthrough);
 111 }
 112
 113 /*
 114  * Call a function for every successor of `block' that is reachable
 115  * through a fallthrough or taken edge.
 116  */
 117 template<class Block, class Fun>
 118 void forEachNormalSuccessor(Block& block, Fun f) {
 119   forEachTakenEdge(block.hhbcs.back(), f);
 120   if (block.fallthrough != NoBlockId) f(block.fallthrough);
 121 }
 122
 123 /*
 124  * Call a function for every successor of `block' that is reachable
 125  * through a non-throw edge.
 126  */
 127 template<class Fun>
 128 void forEachNonThrowSuccessor(const php::Block& block, Fun f) {
 129   forEachTakenEdge(block.hhbcs.back(), f);
 130   if (block.fallthrough != NoBlockId) f(block.fallthrough);
 131 }
 132
 133 /*
 134  * Obtain the blocks for a function in a reverse post order, starting
 135  * with the specified block.  The exact order is not specified.
 136  */
 137 std::vector<BlockId> rpoSortFromBlock(const php::WideFunc&, BlockId);
 138
 139 /*
 140  * Obtain the blocks for a function in a reverse post order, starting
 141  * with the main entry point.  The exact order is not specified.
 142  *
 143  * DV initializer blocks will not appear in this list.
 144  */
 145 std::vector<BlockId> rpoSortFromMain(const php::WideFunc&);
 146
 147 /*
 148  * Obtain the blocks for a function in a reverse post order, taking
 149  * into account all entry points.
 150  *
 151  * This can be thought of as an RPO on the CFG of Func starting from a
 152  * virtual empty "entry" block, with edges to each DV entry point and
 153  * an edge to the main entry point.
 154  */
 155 std::vector<BlockId> rpoSortAddDVs(const php::WideFunc&);
 156
 157 /*
 158  * Mappings from blocks to sets of blocks.
 159  *
 160  * The first level is indexed by block id.  The second is a set of
 161  * block pointers.
 162  */
 163 using BlockToBlocks = std::vector<
 164   boost::container::flat_set<BlockId>
 165 >;
 166
 167 /*
 168  * Find the immediate non-throw predecessors for each block in
 169  * an RPO-sorted list of blocks.
 170  *
 171  * The BlockToBlocks map returned will have any entry for each block
 172  * in the input array, but may not have entries for blocks that aren't
 173  * in the list.
 174  */
 175 BlockToBlocks
 176 computeNonThrowPreds(const php::WideFunc&, const std::vector<BlockId>&);
 177
 178 /*
 179  * Find the immediate throw predecessors for each block in an
 180  * RPO-sorted list of blocks.
 181  *
 182  * The BlockToBlocks map returned will have any entry for each block
 183  * in the input array, but may not have entries for blocks that aren't
 184  * in the list.
 185  */
 186 BlockToBlocks
 187 computeThrowPreds(const php::WideFunc&, const std::vector<BlockId>&);
 188
 189 /*
 190  * Visit each leaf in the ExnNode tree.
 191  */
 192 template<class Fun>
 193 void visitExnLeaves(const php::Func& func, Fun f) {
 194   for (auto& n : func.exnNodes) {
 195     detail::visitExnLeaves(func, n, f);
 196   }
 197 }
 198
 199 //////////////////////////////////////////////////////////////////////
 200
 201 }