OLD | NEW |
(Empty) | |
| 1 // Copyright 2010 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are |
| 4 // met: |
| 5 // |
| 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided |
| 11 // with the distribution. |
| 12 // * Neither the name of Google Inc. nor the names of its |
| 13 // contributors may be used to endorse or promote products derived |
| 14 // from this software without specific prior written permission. |
| 15 // |
| 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 |
| 28 #ifndef V8_FLOW_GRAPH_H_ |
| 29 #define V8_FLOW_GRAPH_H_ |
| 30 |
| 31 #include "v8.h" |
| 32 |
| 33 #include "data-flow.h" |
| 34 #include "zone.h" |
| 35 |
| 36 namespace v8 { |
| 37 namespace internal { |
| 38 |
| 39 // Flow-graph nodes. |
| 40 class Node: public ZoneObject { |
| 41 public: |
| 42 Node() : number_(-1), mark_(false) {} |
| 43 |
| 44 virtual ~Node() {} |
| 45 |
| 46 virtual bool IsExitNode() { return false; } |
| 47 virtual bool IsBlockNode() { return false; } |
| 48 virtual bool IsBranchNode() { return false; } |
| 49 virtual bool IsJoinNode() { return false; } |
| 50 |
| 51 virtual void AddPredecessor(Node* predecessor) = 0; |
| 52 virtual void AddSuccessor(Node* successor) = 0; |
| 53 |
| 54 bool IsMarkedWith(bool mark) { return mark_ == mark; } |
| 55 void MarkWith(bool mark) { mark_ = mark; } |
| 56 |
| 57 // Perform a depth first search and record preorder and postorder |
| 58 // traversal orders. |
| 59 virtual void Traverse(bool mark, |
| 60 ZoneList<Node*>* preorder, |
| 61 ZoneList<Node*>* postorder) = 0; |
| 62 |
| 63 int number() { return number_; } |
| 64 void set_number(int number) { number_ = number; } |
| 65 |
| 66 // Functions used by data-flow analyses. |
| 67 virtual void InitializeReachingDefinitions(int definition_count, |
| 68 List<BitVector*>* variables, |
| 69 WorkList<Node>* worklist, |
| 70 bool mark); |
| 71 virtual void ComputeRDOut(BitVector* result) = 0; |
| 72 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0; |
| 73 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); |
| 74 |
| 75 // Functions used by dead-code elimination. |
| 76 virtual void MarkCriticalInstructions( |
| 77 List<AstNode*>* stack, |
| 78 ZoneList<Expression*>* body_definitions, |
| 79 int variable_count); |
| 80 |
| 81 #ifdef DEBUG |
| 82 void AssignNodeNumber(); |
| 83 void PrintReachingDefinitions(); |
| 84 virtual void PrintText() = 0; |
| 85 #endif |
| 86 |
| 87 protected: |
| 88 ReachingDefinitionsData rd_; |
| 89 |
| 90 private: |
| 91 int number_; |
| 92 bool mark_; |
| 93 |
| 94 DISALLOW_COPY_AND_ASSIGN(Node); |
| 95 }; |
| 96 |
| 97 |
| 98 // An exit node has a arbitrarily many predecessors and no successors. |
| 99 class ExitNode: public Node { |
| 100 public: |
| 101 ExitNode() : predecessors_(4) {} |
| 102 |
| 103 virtual bool IsExitNode() { return true; } |
| 104 |
| 105 virtual void AddPredecessor(Node* predecessor) { |
| 106 ASSERT(predecessor != NULL); |
| 107 predecessors_.Add(predecessor); |
| 108 } |
| 109 |
| 110 virtual void AddSuccessor(Node* successor) { UNREACHABLE(); } |
| 111 |
| 112 virtual void Traverse(bool mark, |
| 113 ZoneList<Node*>* preorder, |
| 114 ZoneList<Node*>* postorder); |
| 115 |
| 116 virtual void ComputeRDOut(BitVector* result); |
| 117 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 118 |
| 119 #ifdef DEBUG |
| 120 virtual void PrintText(); |
| 121 #endif |
| 122 |
| 123 private: |
| 124 ZoneList<Node*> predecessors_; |
| 125 |
| 126 DISALLOW_COPY_AND_ASSIGN(ExitNode); |
| 127 }; |
| 128 |
| 129 |
| 130 // Block nodes have a single successor and predecessor and a list of |
| 131 // instructions. |
| 132 class BlockNode: public Node { |
| 133 public: |
| 134 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} |
| 135 |
| 136 static BlockNode* cast(Node* node) { |
| 137 ASSERT(node->IsBlockNode()); |
| 138 return reinterpret_cast<BlockNode*>(node); |
| 139 } |
| 140 |
| 141 virtual bool IsBlockNode() { return true; } |
| 142 |
| 143 bool is_empty() { return instructions_.is_empty(); } |
| 144 |
| 145 ZoneList<AstNode*>* instructions() { return &instructions_; } |
| 146 |
| 147 virtual void AddPredecessor(Node* predecessor) { |
| 148 ASSERT(predecessor_ == NULL && predecessor != NULL); |
| 149 predecessor_ = predecessor; |
| 150 } |
| 151 |
| 152 virtual void AddSuccessor(Node* successor) { |
| 153 ASSERT(successor_ == NULL && successor != NULL); |
| 154 successor_ = successor; |
| 155 } |
| 156 |
| 157 void AddInstruction(AstNode* instruction) { |
| 158 instructions_.Add(instruction); |
| 159 } |
| 160 |
| 161 virtual void Traverse(bool mark, |
| 162 ZoneList<Node*>* preorder, |
| 163 ZoneList<Node*>* postorder); |
| 164 |
| 165 virtual void InitializeReachingDefinitions(int definition_count, |
| 166 List<BitVector*>* variables, |
| 167 WorkList<Node>* worklist, |
| 168 bool mark); |
| 169 virtual void ComputeRDOut(BitVector* result); |
| 170 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 171 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); |
| 172 |
| 173 virtual void MarkCriticalInstructions( |
| 174 List<AstNode*>* stack, |
| 175 ZoneList<Expression*>* body_definitions, |
| 176 int variable_count); |
| 177 |
| 178 #ifdef DEBUG |
| 179 virtual void PrintText(); |
| 180 #endif |
| 181 |
| 182 private: |
| 183 Node* predecessor_; |
| 184 Node* successor_; |
| 185 ZoneList<AstNode*> instructions_; |
| 186 |
| 187 DISALLOW_COPY_AND_ASSIGN(BlockNode); |
| 188 }; |
| 189 |
| 190 |
| 191 // Branch nodes have a single predecessor and a pair of successors. |
| 192 class BranchNode: public Node { |
| 193 public: |
| 194 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} |
| 195 |
| 196 virtual bool IsBranchNode() { return true; } |
| 197 |
| 198 virtual void AddPredecessor(Node* predecessor) { |
| 199 ASSERT(predecessor_ == NULL && predecessor != NULL); |
| 200 predecessor_ = predecessor; |
| 201 } |
| 202 |
| 203 virtual void AddSuccessor(Node* successor) { |
| 204 ASSERT(successor1_ == NULL && successor != NULL); |
| 205 if (successor0_ == NULL) { |
| 206 successor0_ = successor; |
| 207 } else { |
| 208 successor1_ = successor; |
| 209 } |
| 210 } |
| 211 |
| 212 virtual void Traverse(bool mark, |
| 213 ZoneList<Node*>* preorder, |
| 214 ZoneList<Node*>* postorder); |
| 215 |
| 216 virtual void ComputeRDOut(BitVector* result); |
| 217 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 218 |
| 219 #ifdef DEBUG |
| 220 virtual void PrintText(); |
| 221 #endif |
| 222 |
| 223 private: |
| 224 Node* predecessor_; |
| 225 Node* successor0_; |
| 226 Node* successor1_; |
| 227 |
| 228 DISALLOW_COPY_AND_ASSIGN(BranchNode); |
| 229 }; |
| 230 |
| 231 |
| 232 // Join nodes have arbitrarily many predecessors and a single successor. |
| 233 class JoinNode: public Node { |
| 234 public: |
| 235 JoinNode() : predecessors_(2), successor_(NULL) {} |
| 236 |
| 237 static JoinNode* cast(Node* node) { |
| 238 ASSERT(node->IsJoinNode()); |
| 239 return reinterpret_cast<JoinNode*>(node); |
| 240 } |
| 241 |
| 242 virtual bool IsJoinNode() { return true; } |
| 243 |
| 244 virtual void AddPredecessor(Node* predecessor) { |
| 245 ASSERT(predecessor != NULL); |
| 246 predecessors_.Add(predecessor); |
| 247 } |
| 248 |
| 249 virtual void AddSuccessor(Node* successor) { |
| 250 ASSERT(successor_ == NULL && successor != NULL); |
| 251 successor_ = successor; |
| 252 } |
| 253 |
| 254 virtual void Traverse(bool mark, |
| 255 ZoneList<Node*>* preorder, |
| 256 ZoneList<Node*>* postorder); |
| 257 |
| 258 virtual void ComputeRDOut(BitVector* result); |
| 259 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 260 |
| 261 #ifdef DEBUG |
| 262 virtual void PrintText(); |
| 263 #endif |
| 264 |
| 265 private: |
| 266 ZoneList<Node*> predecessors_; |
| 267 Node* successor_; |
| 268 |
| 269 DISALLOW_COPY_AND_ASSIGN(JoinNode); |
| 270 }; |
| 271 |
| 272 |
| 273 // Flow graphs have a single entry and single exit. The empty flowgraph is |
| 274 // represented by both entry and exit being NULL. |
| 275 class FlowGraph BASE_EMBEDDED { |
| 276 public: |
| 277 static FlowGraph Empty() { |
| 278 FlowGraph graph; |
| 279 graph.entry_ = new BlockNode(); |
| 280 graph.exit_ = graph.entry_; |
| 281 return graph; |
| 282 } |
| 283 |
| 284 bool is_empty() const { |
| 285 return entry_ == exit_ && BlockNode::cast(entry_)->is_empty(); |
| 286 } |
| 287 Node* entry() const { return entry_; } |
| 288 Node* exit() const { return exit_; } |
| 289 |
| 290 // Add a single instruction to the end of this flowgraph. |
| 291 void AppendInstruction(AstNode* instruction); |
| 292 |
| 293 // Add a single node to the end of this flow graph. |
| 294 void AppendNode(Node* node); |
| 295 |
| 296 // Add a flow graph fragment to the end of this one. |
| 297 void AppendGraph(FlowGraph* graph); |
| 298 |
| 299 // Concatenate an if-then-else flow-graph to this one. Control is split |
| 300 // and merged, so the graph remains single-entry, single-exit. |
| 301 void Split(BranchNode* branch, |
| 302 FlowGraph* left, |
| 303 FlowGraph* right, |
| 304 JoinNode* merge); |
| 305 |
| 306 // Concatenate a forward loop (e.g., while or for loop) flow-graph to this |
| 307 // one. Control is split by the condition and merged back from the back |
| 308 // edge at end of the body to the beginning of the condition. The single |
| 309 // (free) exit of the result graph is the right (false) arm of the branch |
| 310 // node. |
| 311 void Loop(JoinNode* merge, |
| 312 FlowGraph* condition, |
| 313 BranchNode* branch, |
| 314 FlowGraph* body); |
| 315 |
| 316 #ifdef DEBUG |
| 317 void PrintText(FunctionLiteral* fun, ZoneList<Node*>* postorder); |
| 318 #endif |
| 319 |
| 320 private: |
| 321 FlowGraph() : entry_(NULL), exit_(NULL) {} |
| 322 |
| 323 Node* entry_; |
| 324 Node* exit_; |
| 325 }; |
| 326 |
| 327 |
| 328 // Construct a flow graph from a function literal. Build pre- and postorder |
| 329 // traversal orders as a byproduct. |
| 330 class FlowGraphBuilder: public AstVisitor { |
| 331 public: |
| 332 explicit FlowGraphBuilder(int variable_count) |
| 333 : graph_(FlowGraph::Empty()), |
| 334 global_exit_(NULL), |
| 335 preorder_(4), |
| 336 postorder_(4), |
| 337 variable_count_(variable_count), |
| 338 body_definitions_(4) { |
| 339 } |
| 340 |
| 341 void Build(FunctionLiteral* lit); |
| 342 |
| 343 FlowGraph* graph() { return &graph_; } |
| 344 ZoneList<Node*>* preorder() { return &preorder_; } |
| 345 ZoneList<Node*>* postorder() { return &postorder_; } |
| 346 ZoneList<Expression*>* body_definitions() { return &body_definitions_; } |
| 347 |
| 348 private: |
| 349 ExitNode* global_exit() { return global_exit_; } |
| 350 |
| 351 // Helpers to allow tranforming the ast during flow graph construction. |
| 352 void VisitStatements(ZoneList<Statement*>* stmts); |
| 353 Statement* ProcessStatement(Statement* stmt); |
| 354 |
| 355 // AST node visit functions. |
| 356 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); |
| 357 AST_NODE_LIST(DECLARE_VISIT) |
| 358 #undef DECLARE_VISIT |
| 359 |
| 360 FlowGraph graph_; |
| 361 ExitNode* global_exit_; |
| 362 ZoneList<Node*> preorder_; |
| 363 ZoneList<Node*> postorder_; |
| 364 |
| 365 // The flow graph builder collects a list of explicit definitions |
| 366 // (assignments and count operations) to stack-allocated variables to use |
| 367 // for reaching definitions analysis. It does not count the implicit |
| 368 // definition at function entry. AST node numbers in the AST are used to |
| 369 // refer into this list. |
| 370 int variable_count_; |
| 371 ZoneList<Expression*> body_definitions_; |
| 372 |
| 373 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); |
| 374 }; |
| 375 |
| 376 |
| 377 } } // namespace v8::internal |
| 378 |
| 379 #endif // V8_FLOW_GRAPH_H_ |
OLD | NEW |