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_func.entry();
  43   m_graph->param_count = m_func.numParams();
  44   m_graph->first_linear = createBlock(0);
  45   // DV entry points
  46   m_graph->entries = new (m_arena) Block*[m_graph->param_count + 1];
  47   int dv_index = 0;
  48   for (size_t i = 0; i < m_func.numParams(); i++) {
  49     auto& param = m_func.param(i);
  50     m_graph->entries[dv_index++] = !param.hasDefaultValue() ? 0 :
  51                                    createBlock(param.funcletOff);
  52   }
  53   // main entry point
  54   assertx(dv_index == m_graph->param_count);
  55   m_graph->entries[dv_index] = createBlock(0);
  56   // ordinary basic block boundaries
  57   for (InstrRange i = funcInstrs(m_func); !i.empty(); ) {
  58     PC pc = i.popFront();
  59     if ((isCF(pc) || isTF(pc)) && !i.empty()) createBlock(i.front());
  60     auto const targets = instrJumpTargets(bc, pc - bc);
  61     for (auto const target : targets) createBlock(target);
  62   }
  63 }
  64
  65 /**
  66  * Link ordinary blocks with ordinary edges and set their last instruction
  67  * and end offsets
  68  */
  69 void GraphBuilder::linkBlocks() {
  70   PC bc = m_func.entry();
  71   Block* block = m_graph->first_linear;
  72   block->id = m_graph->block_count++;
  73   for (InstrRange i = funcInstrs(m_func); !i.empty(); ) {
  74     PC pc = i.popFront();
  75     PC next_pc = !i.empty() ? i.front() : m_func.at(m_func.past());
  76     Block* next = at(next_pc);
  77     if (!i.empty() && next == nullptr) continue;
  78
  79     block->last = pc;
  80     block->end = next_pc;
  81     block->next_linear = next;
  82
  83     auto const targets = instrJumpTargets(bc, pc - bc);
  84     block->succ_count = (!isTF(pc) ? 1 : 0) + targets.size();
  85     block->succs = new (m_arena) Block*[block->succ_count];
  86     auto succs = block->succs;
  87
  88     if (!isTF(pc)) {
  89       assertx(next);
  90       *(succs++) = next;
  91     }
  92
  93     for (auto target : targets) {
  94       assertx(at(target));
  95       *(succs++) = at(target);
  96     }
  97
  98     assertx(block->succs + block->succ_count == succs);
  99
 100     block = next;
 101     if (block) block->id = m_graph->block_count++;
 102   }
 103 }
 104
 105 /**
 106  * Create blocks from exception handler boundaries; the start and end of
 107  * each protected region is a boundary, and the catch or fault entrypoint
 108  * of each handler is also a boundary.
 109  */
 110 void GraphBuilder::createExBlocks() {
 111   for (size_t i = 0; i < m_func.numEHEnts(); i++) {
 112     auto& handler = m_func.ehent(i);
 113     createBlock(handler.m_base);
 114     if (handler.m_past != m_func.past()) {
 115       createBlock(handler.m_past);
 116     }
 117     createBlock(handler.m_handler);
 118   }
 119 }
 120
 121 /**
 122  * Link primary body blocks to exception handler blocks as follows:
 123  *
 124  * For each block in the body, traverse from the innermost to outermost
 125  * exception handler that includes the block. For each handler, add an edge
 126  * to each handler entry point.
 127  *
 128  * The resulting linkage reflects exception control-flow.
 129  */
 130 void GraphBuilder::linkExBlocks() {
 131   // For every block, add edges to reachable fault and catch handlers.
 132   for (LinearBlocks i = linearBlocks(m_graph); !i.empty(); ) {
 133     Block* b = i.popFront();
 134     assertx(m_func.findEH(offset(b->start)) ==
 135             m_func.findEH(offset(b->last)));
 136     Offset off = offset(b->start);
 137     const EHEnt* eh = m_func.findEH(off);
 138     if (eh != nullptr) {
 139       assertx(eh->m_base <= off && off < eh->m_past);
 140       // the innermost exception handler is reachable from b
 141       b->exn = at(eh->m_handler);
 142     }
 143   }
 144 }
 145
 146 Block* GraphBuilder::createBlock(PC pc) {
 147   BlockMap::iterator i = m_blocks.find(pc);
 148   if (i != m_blocks.end()) return i->second;
 149
 150   Block* b = new (m_arena) Block(pc);
 151   m_blocks.insert(std::pair<PC,Block*>(pc, b));
 152   return b;
 153 }
 154
 155 Block* GraphBuilder::at(PC target) const {
 156   auto const i = m_blocks.find(target);
 157   return i == m_blocks.end() ? 0 : i->second;
 158 }
 159
 160 bool Block::reachable(Block* from, Block* to,
 161                       boost::dynamic_bitset<>& visited) {
 162    if (!from || !to) return false;
 163    if (visited[from->id]) return false;
 164    visited[from->id] = true;
 165    if (from->id == to->id) return true;
 166    for (int i = 0; i < from->succ_count; i++) {
 167      if (reachable(from->succs[i], to, visited)) return true;
 168    }
 169    if (from->exn) return reachable(from->exn, to, visited);
 170    return false;
 171 }
 172
 173 /**
 174  * RpoSort does a depth-first search over successor and exception edges
 175  * of a Graph, visits blocks in postorder, and builds the reverse-postorder
 176  * list of blocks in-place.  Each block's rpo_id is the reverse-postorder
 177  * number (entry starts at 0, and so-on).
 178  *
 179  * Note that in functions with optional parameters, the lowest-numbered
 180  * DV entry point is typically the "entry" since it falls through to
 181  * higher-numbered DV entry points, the last of which ultimately jumps to
 182  * the primary function body.
 183  */
 184 struct RpoSort {
 185   explicit RpoSort(Graph* g);
 186  private:
 187   void visit(Block* b);
 188  private:
 189   Graph* g;
 190   bool* visited;
 191   int rpo_id;
 192 };
 193
 194 RpoSort::RpoSort(Graph* g) : g(g), rpo_id(0) {
 195   Arena scratch;
 196   visited = new (scratch) bool[g->block_count];
 197   memset(visited, 0, sizeof(bool) * g->block_count);
 198   g->first_rpo = 0;
 199   for (BlockPtrRange i = entryBlocks(g); !i.empty(); ) {
 200     visit(i.popFront());
 201   }
 202 }
 203
 204 /**
 205  * Recursively visit b and its successors.  We search exception edges
 206  * first in a weak attempt to put exception blocks later in the final
 207  * reverse-postorder numbering, but it shouldn't matter and anyone
 208  * counting on that has a bug.
 209  */
 210 void RpoSort::visit(Block* b) {
 211   if (visited[b->id]) return;
 212   visited[b->id] = true;
 213   if (b->exn) visit(b->exn);
 214   for (BlockPtrRange i = succBlocks(b); !i.empty(); ) visit(i.popBack());
 215   b->next_rpo = g->first_rpo;
 216   g->first_rpo = b;
 217   rpo_id++;
 218   b->rpo_id = g->block_count - rpo_id;
 219 }
 220
 221 void sortRpo(Graph* g) {
 222   RpoSort _(g);
 223 }
 224
 225 }}