hphp/runtime/vm/verifier/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
  17 #include "hphp/runtime/vm/verifier/cfg.h"
  18 #include "hphp/runtime/vm/verifier/util.h"
  19 #include <boost/dynamic_bitset.hpp>
  20
  21 namespace HPHP {
  22 namespace Verifier {
  23
  24 /**
  25  * Create all blocks and edges for one Func.
  26  */
  27 Graph* GraphBuilder::build() {
  28   assertx(!funcInstrs(m_func).empty());
  29   m_graph = new (m_arena) Graph();
  30   createBlocks();
  31   createExBlocks();
  32   linkBlocks();
  33   linkExBlocks();
  34   return m_graph;
  35 }
  36
  37 /**
  38  * Create blocks for each entry point as well as ordinary control
  39  * flow boundaries.  Calls are not treated as basic-block ends.
  40  */
  41 void GraphBuilder::createBlocks() {
  42   PC bc = m_unit->entry();
  43   m_graph->param_count = m_func->params().size();
  44   m_graph->first_linear = createBlock(m_func->base());
  45   // DV entry points
  46   m_graph->entries = new (m_arena) Block*[m_graph->param_count + 1];
  47   int dv_index = 0;
  48   for (auto& param : m_func->params()) {
  49     m_graph->entries[dv_index++] = !param.hasDefaultValue() ? 0 :
  50                                    createBlock(param.funcletOff);
  51   }
  52   // main entry point
  53   assertx(dv_index == m_graph->param_count);
  54   m_graph->entries[dv_index] = createBlock(m_func->base());
  55   // ordinary basic block boundaries
  56   for (InstrRange i = funcInstrs(m_func); !i.empty(); ) {
  57     PC pc = i.popFront();
  58     if ((isCF(pc) || isTF(pc)) && !i.empty()) createBlock(i.front());
  59     if (isSwitch(peek_op(pc))) {
  60       foreachSwitchTarget(pc, [&](Offset o) { createBlock(pc + o); });
  61     } else {
  62       Offset target = instrJumpTarget(bc, pc - bc);
  63       if (target != InvalidAbsoluteOffset) createBlock(target);
  64     }
  65   }
  66 }
  67
  68 /**
  69  * Link ordinary blocks with ordinary edges and set their last instruction
  70  * and end offsets
  71  */
  72 void GraphBuilder::linkBlocks() {
  73   PC bc = m_unit->entry();
  74   Block* block = m_graph->first_linear;
  75   block->id = m_graph->block_count++;
  76   for (InstrRange i = funcInstrs(m_func); !i.empty(); ) {
  77     PC pc = i.popFront();
  78     block->last = pc;
  79     if (isCF(pc)) {
  80       if (isSwitch(peek_op(pc))) {
  81         int i = 0;
  82         foreachSwitchTarget(pc, [&](Offset o) {
  83           succs(block)[i++] = at(pc + o);
  84         });
  85       } else {
  86         Offset target = instrJumpTarget(bc, pc - bc);
  87         if (target != InvalidAbsoluteOffset) {
  88           assertx(numSuccBlocks(block) > 0);
  89           succs(block)[numSuccBlocks(block) - 1] = at(target);
  90         }
  91       }
  92     }
  93     PC next_pc = !i.empty() ? i.front() : m_unit->at(m_func->past());
  94     Block* next = at(next_pc);
  95     if (peek_op(pc) == Op::Unwind) { // exn block
  96       if (auto const eh = m_func->findEHbyHandler(offset(pc))) {
  97         // link the end of each fault handler to the beginning of its parent
  98         succs(block)[0] = eh->m_parentIndex >= 0 ?
  99           at(m_func->ehtab()[eh->m_parentIndex].m_handler) : nullptr;
 100       }
 101     }
 102     if (next) {
 103       block->next_linear = next;
 104       block->end = next_pc;
 105       if (!isTF(pc)) {
 106         assertx(numSuccBlocks(block) > 0);
 107         succs(block)[0] = next;
 108       }
 109       block = next;
 110       block->id = m_graph->block_count++;
 111     }
 112   }
 113   block->end = m_unit->at(m_func->past());
 114 }
 115
 116 /**
 117  * Create blocks from exception handler boundaries; the start and end of
 118  * each protected region is a boundary, and the catch or fault entrypoint
 119  * of each handler is also a boundary.
 120  */
 121 void GraphBuilder::createExBlocks() {
 122   for (auto& handler : m_func->ehtab()) {
 123     createBlock(handler.m_base);
 124     if (handler.m_past != m_func->past()) {
 125       createBlock(handler.m_past);
 126     }
 127     createBlock(handler.m_handler);
 128   }
 129 }
 130
 131 /**
 132  * return the next outermost handler or 0 if there aren't any
 133  */
 134 const EHEnt* nextOuter(const Func::EHEntVec& ehtab, const EHEnt* eh) {
 135   return eh->m_parentIndex != -1 ? &ehtab[eh->m_parentIndex] : 0;
 136 }
 137
 138 /**
 139  * Link primary body blocks to exception handler blocks as follows:
 140  * 1. For each block in the body, traverse from the innermost to
 141  *    outermost exception handler that includes the block.  For
 142  *    catch handlers, add an edge to each handler entry point. For
 143  *    fault handlers, add an edge to the fault handler and stop.
 144  * 2. For each fault handler block ending in Unwind, find the EH
 145  *    entry for the funclet, then traverse outwards starting from the
 146  *    next outermost.  Add any catch edges found, and stop at the first
 147  *    enclosing fault funclet, as in step 1.
 148  * The resulting linkage reflects exception control-flow; fault funclets
 149  * unconditionally handle any exception in their protected region, so they
 150  * "dominate" outer-more handlers.
 151  */
 152 void GraphBuilder::linkExBlocks() {
 153   // For every block, add edges to reachable fault and catch handlers.
 154   for (LinearBlocks i = linearBlocks(m_graph); !i.empty(); ) {
 155     Block* b = i.popFront();
 156     assertx(m_func->findEH(offset(b->start)) ==
 157             m_func->findEH(offset(b->last)));
 158     Offset off = offset(b->start);
 159     const EHEnt* eh = m_func->findEH(off);
 160     if (eh != nullptr) {
 161       assertx(eh->m_base <= off && off < eh->m_past);
 162       // the innermost exception handler is reachable from b
 163       b->exn = at(eh->m_handler);
 164     }
 165   }
 166 }
 167
 168 Block** GraphBuilder::succs(Block* b) {
 169   if (!b->succs) {
 170     int num_succs = numSuccBlocks(b);
 171     Block** s = b->succs = new (m_arena) Block*[num_succs];
 172     memset(s, 0, sizeof(*s) * num_succs);
 173   }
 174   return b->succs;
 175 }
 176
 177 Block* GraphBuilder::createBlock(PC pc) {
 178   BlockMap::iterator i = m_blocks.find(pc);
 179   if (i != m_blocks.end()) return i->second;
 180
 181   Block* b = new (m_arena) Block(pc);
 182   m_blocks.insert(std::pair<PC,Block*>(pc, b));
 183   return b;
 184 }
 185
 186 Block* GraphBuilder::at(PC target) const {
 187   auto const i = m_blocks.find(target);
 188   return i == m_blocks.end() ? 0 : i->second;
 189 }
 190
 191 bool Block::reachable(Block* from, Block* to,
 192                       boost::dynamic_bitset<>& visited) {
 193    if (!from || !to) return false;
 194    if (visited[from->id]) return false;
 195    visited[from->id] = true;
 196    if (from->id == to->id) return true;
 197    for (int i = 0; i < numSuccBlocks(from); i++) {
 198      if (reachable(from->succs[i], to, visited)) return true;
 199    }
 200    if (from->exn) return reachable(from->exn, to, visited);
 201    return false;
 202 }
 203
 204 /**
 205  * RpoSort does a depth-first search over successor and exception edges
 206  * of a Graph, visits blocks in postorder, and builds the reverse-postorder
 207  * list of blocks in-place.  Each block's rpo_id is the reverse-postorder
 208  * number (entry starts at 0, and so-on).
 209  *
 210  * Note that in functions with optional parameters, the lowest-numbered
 211  * DV entry point is typically the "entry" since it falls through to
 212  * higher-numbered DV entry points, the last of which ultimately jumps to
 213  * the primary function body.
 214  */
 215 struct RpoSort {
 216   explicit RpoSort(Graph* g);
 217  private:
 218   void visit(Block* b);
 219  private:
 220   Graph* g;
 221   bool* visited;
 222   int rpo_id;
 223 };
 224
 225 RpoSort::RpoSort(Graph* g) : g(g), rpo_id(0) {
 226   Arena scratch;
 227   visited = new (scratch) bool[g->block_count];
 228   memset(visited, 0, sizeof(bool) * g->block_count);
 229   g->first_rpo = 0;
 230   for (BlockPtrRange i = entryBlocks(g); !i.empty(); ) {
 231     visit(i.popFront());
 232   }
 233 }
 234
 235 /**
 236  * Recursively visit b and its successors.  We search exception edges
 237  * first in a weak attempt to put exception blocks later in the final
 238  * reverse-postorder numbering, but it shouldn't matter and anyone
 239  * counting on that has a bug.
 240  */
 241 void RpoSort::visit(Block* b) {
 242   if (visited[b->id]) return;
 243   visited[b->id] = true;
 244   if (b->exn) visit(b->exn);
 245   for (BlockPtrRange i = succBlocks(b); !i.empty(); ) visit(i.popBack());
 246   b->next_rpo = g->first_rpo;
 247   g->first_rpo = b;
 248   rpo_id++;
 249   b->rpo_id = g->block_count - rpo_id;
 250 }
 251
 252 void sortRpo(Graph* g) {
 253   RpoSort _(g);
 254 }
 255
 256 }}