hphp/compiler/analysis/control_flow.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- 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 #ifndef incl_HPHP_CONTROL_FLOW_H_
  18 #define incl_HPHP_CONTROL_FLOW_H_
  19
  20 #include <boost/graph/properties.hpp>
  21 #include <boost/graph/adjacency_iterator.hpp>
  22 #include <boost/graph/adjacency_list.hpp>
  23
  24 #include <compiler/hphp.h>
  25
  26 #include <compiler/analysis/ast_walker.h>
  27 #include <compiler/analysis/bit_set_vec.h>
  28
  29 namespace HPHP {
  30 ///////////////////////////////////////////////////////////////////////////////
  31
  32 class ControlBlock;
  33 class ControlFlowGraph;
  34 class ControlEdge;
  35 class AdjacencyIterator;
  36 class InvAdjdacencyIterator;
  37
  38 ///////////////////////////////////////////////////////////////////////////////
  39 }
  40
  41 namespace boost {
  42 ///////////////////////////////////////////////////////////////////////////////
  43
  44 template <>
  45 struct graph_traits<HPHP::ControlFlowGraph> {
  46   typedef HPHP::ControlBlock *vertex_descriptor;
  47   typedef HPHP::ControlEdge *edge_descriptor;
  48
  49   typedef std::list<HPHP::ControlEdge*>::const_iterator in_edge_iterator;
  50   typedef std::list<HPHP::ControlEdge*>::const_iterator out_edge_iterator;
  51   typedef std::list<HPHP::ControlBlock*>::const_iterator vertex_iterator;
  52   typedef std::list<HPHP::ControlEdge*>::const_iterator edge_iterator;
  53   typedef adjacency_iterator_generator<
  54     HPHP::ControlFlowGraph,
  55     vertex_descriptor,
  56     out_edge_iterator>::type adjacency_iterator;
  57   typedef inv_adjacency_iterator_generator<
  58     HPHP::ControlFlowGraph,
  59     vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
  60
  61   typedef directed_tag directed_category;
  62   typedef disallow_parallel_edge_tag edge_parallel_category;
  63   typedef bidirectional_graph_tag traversal_category;
  64
  65   typedef int vertices_size_type;
  66   typedef int edges_size_type;
  67   typedef std::list<HPHP::ControlEdge*>::size_type degree_size_type;
  68 };
  69
  70 template<>
  71 struct property_traits<vertex_color_t> {
  72   typedef default_color_type value_type;
  73   typedef HPHP::ControlBlock *key_type;
  74   typedef default_color_type &reference;
  75   typedef lvalue_property_map_tag category;
  76 };
  77
  78 ///////////////////////////////////////////////////////////////////////////////
  79 }
  80
  81 namespace HPHP {
  82 ///////////////////////////////////////////////////////////////////////////////
  83
  84 DECLARE_BOOST_TYPES(Construct);
  85 DECLARE_BOOST_TYPES(Expression);
  86 DECLARE_BOOST_TYPES(Statement);
  87 DECLARE_BOOST_TYPES(MethodStatement);
  88 DECLARE_BOOST_TYPES(FunctionScope);
  89 DECLARE_BOOST_TYPES(AnalysisResult);
  90
  91 class ControlFlowGraph {
  92 public:
  93   typedef boost::graph_traits<ControlFlowGraph> graph_traits;
  94   typedef graph_traits::vertex_descriptor vertex_descriptor;
  95   typedef graph_traits::adjacency_iterator adjacency_iterator;
  96   typedef graph_traits::vertex_iterator vertex_iterator;
  97   typedef graph_traits::edge_iterator edge_iterator;
  98   typedef graph_traits::out_edge_iterator out_edge_iterator;
  99   typedef graph_traits::in_edge_iterator in_edge_iterator;
 100
 101   static ControlFlowGraph *buildControlFlow(MethodStatementPtr m);
 102   ~ControlFlowGraph();
 103
 104   void                  dump(AnalysisResultConstPtr ar);
 105   void                  allocateDataFlow(size_t width, int rows, int *rowIds);
 106   ControlBlock          *getDfBlock(int dfn) const {
 107     return m_depthFirstBlocks.at(dfn - 1);
 108   }
 109   BitOps::Bits          *getTempBits(int id) const {
 110     return m_bitSetVec.getTempBits(id);
 111   }
 112   bool                  rowExists(int row) const {
 113     return m_bitSetVec.rowExists(row);
 114   }
 115   size_t                bitWidth() const { return m_bitSetVec.width(); }
 116   int                   getNumBlocks() const { return m_nextDfn - 1; }
 117   void                  dfnAdd(ControlBlock *cb);
 118   vertex_iterator       vbegin() const { return m_blocks.begin(); }
 119   vertex_iterator       vend() const { return m_blocks.end(); }
 120   edge_iterator         ebegin() const { return m_edges.begin(); }
 121   edge_iterator         eend() const { return m_edges.end(); }
 122   ControlBlock          *add_vertex(AstWalkerStateVec &s);
 123   ControlEdge           *add_edge(ControlBlock *a, ControlBlock *b);
 124   MethodStatementPtr    getMethod() { return m_stmt; }
 125 private:
 126   MethodStatementPtr         m_stmt;
 127   BitSetVec                  m_bitSetVec;
 128   int                        m_nextDfn;
 129   std::list<ControlEdge*>    m_edges;
 130   std::list<ControlBlock*>   m_blocks;
 131   std::vector<ControlBlock*> m_depthFirstBlocks;
 132 };
 133
 134 class ControlEdge : public std::pair<ControlBlock*,ControlBlock*> {
 135 public:
 136   ControlEdge(ControlBlock *from, ControlBlock *to) :
 137       std::pair<ControlBlock*,ControlBlock*>(from, to) {}
 138 };
 139
 140 class ControlBlock {
 141   typedef ControlFlowGraph::graph_traits graph_traits;
 142   typedef boost::default_color_type color_type;
 143 public:
 144   ControlBlock(const AstWalkerStateVec &s, ControlBlock *prev);
 145
 146   void                  setDfn(int n) { m_dfn = n; }
 147   int                   getDfn() const { return m_dfn; }
 148   BitOps::Bits          *getRow(int row) { return m_bitBlock.getRow(row); }
 149
 150   void                  setBit(int row, int id, bool flag = true) {
 151     m_bitBlock.setBit(row, id, flag);
 152   }
 153   bool                  getBit(int row, int id) const {
 154     return m_bitBlock.getBit(row, id);
 155   }
 156   void                  setBlock(const BitSetBlock &b) { m_bitBlock = b; }
 157   void                  setEndBefore(ConstructRawPtr e) { m_endBefore = e; }
 158   void                  setEndAfter(ConstructRawPtr e) { m_endAfter = e; }
 159   ConstructRawPtr       getStartNode() const { return m_start.back().cp; }
 160   const AstWalkerStateVec &getStartState() const { return m_start; }
 161   ConstructRawPtr       getEndBefore() const { return m_endBefore; }
 162   ConstructRawPtr       getEndAfter() const { return m_endAfter; }
 163   void                  dump(int spc, AnalysisResultConstPtr ar,
 164                              const ControlFlowGraph *graph);
 165
 166   graph_traits::in_edge_iterator ibegin() const { return m_preds.begin(); }
 167   graph_traits::in_edge_iterator iend() const { return m_preds.end(); }
 168   graph_traits::out_edge_iterator obegin() const { return m_succs.begin(); }
 169   graph_traits::out_edge_iterator oend() const { return m_succs.end(); }
 170   graph_traits::adjacency_iterator abegin(const ControlFlowGraph &g) const {
 171     return graph_traits::adjacency_iterator(m_succs.begin(), &g);
 172   }
 173   graph_traits::adjacency_iterator aend(const ControlFlowGraph &g) const {
 174     return graph_traits::adjacency_iterator(m_succs.end(), &g);
 175   }
 176   graph_traits::inv_adjacency_iterator iabegin(const ControlFlowGraph &g) {
 177     return graph_traits::inv_adjacency_iterator(m_preds.begin(), &g);
 178   }
 179   graph_traits::inv_adjacency_iterator iaend(const ControlFlowGraph &g) {
 180     return graph_traits::inv_adjacency_iterator(m_preds.end(), &g);
 181   }
 182   ControlEdge             *find_to(ControlBlock *to);
 183   ControlEdge             *find_from(ControlBlock *from);
 184   static void             add_edge(ControlEdge *e);
 185   int in_size() const { return m_preds.size(); }
 186   int out_size() const { return m_succs.size(); }
 187   color_type get_color() { return m_color; }
 188   void set_color(color_type c) { m_color = c; }
 189   ControlBlock            *next() const { return m_next; }
 190 private:
 191   int                     m_dfn;
 192   AstWalkerStateVec       m_start;
 193   ConstructRawPtr         m_endBefore;
 194   ConstructRawPtr         m_endAfter;
 195   BitSetBlock             m_bitBlock;
 196   std::list<ControlEdge*> m_preds;
 197   std::list<ControlEdge*> m_succs;
 198   color_type              m_color;
 199   ControlBlock            *m_next;
 200 };
 201
 202 ///////////////////////////////////////////////////////////////////////////////
 203
 204 inline boost::graph_traits<ControlFlowGraph>::vertex_descriptor
 205 source(boost::graph_traits<ControlFlowGraph>::edge_descriptor e,
 206        const ControlFlowGraph& g) {
 207   return e->first;
 208 }
 209
 210 inline boost::graph_traits<ControlFlowGraph>::vertex_descriptor
 211 target(boost::graph_traits<ControlFlowGraph>::edge_descriptor e,
 212        const ControlFlowGraph& g) {
 213   return e->second;
 214 }
 215
 216 inline std::pair<
 217   boost::graph_traits<ControlFlowGraph>::vertex_iterator,
 218   boost::graph_traits<ControlFlowGraph>::vertex_iterator>
 219 vertices(const ControlFlowGraph &g) {
 220   return std::make_pair(g.vbegin(), g.vend());
 221 }
 222
 223 inline std::pair<
 224   boost::graph_traits<ControlFlowGraph>::edge_iterator,
 225   boost::graph_traits<ControlFlowGraph>::edge_iterator>
 226 edges(const ControlFlowGraph &g) {
 227   return std::make_pair(g.ebegin(), g.eend());
 228 }
 229
 230 inline std::pair<
 231   boost::graph_traits<ControlFlowGraph>::out_edge_iterator,
 232   boost::graph_traits<ControlFlowGraph>::out_edge_iterator>
 233 in_edges(
 234   boost::graph_traits<ControlFlowGraph>::vertex_descriptor u,
 235   const ControlFlowGraph &g) {
 236   return std::make_pair(u->ibegin(), u->iend());
 237 }
 238
 239 inline std::pair<
 240   boost::graph_traits<ControlFlowGraph>::out_edge_iterator,
 241   boost::graph_traits<ControlFlowGraph>::out_edge_iterator>
 242 out_edges(
 243   boost::graph_traits<ControlFlowGraph>::vertex_descriptor u,
 244   const ControlFlowGraph &g) {
 245   return std::make_pair(u->obegin(), u->oend());
 246 }
 247
 248 inline std::pair<
 249   boost::graph_traits<ControlFlowGraph>::adjacency_iterator,
 250   boost::graph_traits<ControlFlowGraph>::adjacency_iterator>
 251 adjacent_vertices(
 252   boost::graph_traits<ControlFlowGraph>::vertex_descriptor u,
 253   const ControlFlowGraph &g) {
 254   return std::make_pair(u->abegin(g), u->aend(g));
 255 }
 256
 257 inline std::pair<
 258   boost::graph_traits<ControlFlowGraph>::inv_adjacency_iterator,
 259   boost::graph_traits<ControlFlowGraph>::inv_adjacency_iterator>
 260 inv_adjacent_vertices(
 261   boost::graph_traits<ControlFlowGraph>::vertex_descriptor u,
 262   const ControlFlowGraph &g) {
 263   return std::make_pair(u->iabegin(g), u->iaend(g));
 264 }
 265
 266 inline std::pair<
 267   boost::graph_traits<ControlFlowGraph>::edge_descriptor, bool>
 268 edge(boost::graph_traits<ControlFlowGraph>::vertex_descriptor a,
 269      boost::graph_traits<ControlFlowGraph>::vertex_descriptor b,
 270      const ControlFlowGraph &g) {
 271   boost::graph_traits<ControlFlowGraph>::edge_descriptor e = a->find_to(b);
 272   return std::make_pair(e, e != 0);
 273 }
 274
 275 inline void add_edge(boost::graph_traits<ControlFlowGraph>::vertex_descriptor a,
 276                      boost::graph_traits<ControlFlowGraph>::vertex_descriptor b,
 277                      ControlFlowGraph &g) {
 278   g.add_edge(a, b);
 279 }
 280
 281 inline int in_degree(boost::graph_traits<ControlFlowGraph>::vertex_descriptor a,
 282                      const ControlFlowGraph &g) {
 283   return a->in_size();
 284 }
 285
 286 inline int out_degree(boost::graph_traits<ControlFlowGraph>::vertex_descriptor a,
 287                       const ControlFlowGraph &g) {
 288   return a->out_size();
 289 }
 290
 291 template <typename P>
 292 inline P get(P p, ControlFlowGraph &g) {
 293   return p;
 294 }
 295
 296 inline boost::default_color_type get(
 297   boost::vertex_color_t c,
 298   boost::graph_traits<ControlFlowGraph>::vertex_descriptor a) {
 299   return a->get_color();
 300 }
 301
 302 inline void put(boost::vertex_color_t c,
 303                 boost::graph_traits<ControlFlowGraph>::vertex_descriptor a,
 304                 boost::default_color_type value) {
 305   a->set_color(value);
 306 }
 307
 308 ///////////////////////////////////////////////////////////////////////////////
 309
 310 class ControlFlowGraphWalker : public FunctionWalker {
 311 public:
 312   explicit ControlFlowGraphWalker(ControlFlowGraph *g)
 313     : m_block(0)
 314     , m_graph(*g)
 315   {}
 316   template <class T>
 317   void walk(T &t) {
 318     std::pair<ControlFlowGraph::vertex_iterator,
 319       ControlFlowGraph::vertex_iterator> v(vertices(m_graph));
 320     while (v.first != v.second) {
 321       ControlBlock *b = *v.first;
 322       m_block = b;
 323       AstWalkerStateVec s = b->getStartState();
 324       beforeBlock(b);
 325       AstWalker::walk(t, s, b->getEndBefore(), b->getEndAfter());
 326       afterBlock(b);
 327       ++v.first;
 328     }
 329   }
 330   virtual void beforeBlock(ControlBlock *b) {}
 331   virtual void afterBlock(ControlBlock *b) {}
 332 protected:
 333   ControlBlock *m_block;
 334   ControlFlowGraph &m_graph;
 335 };
 336
 337 ///////////////////////////////////////////////////////////////////////////////
 338 }
 339 #endif // incl_HPHP_CONTROL_FLOW_H_