ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 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 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 39 | // The nodes of a flow graph are basic blocks. Basic blocks consist of |
| 40 | // instructions represented as pointers to AST nodes in the order that they |
| 41 | // would be visited by the code generator. A block can have arbitrarily many |
| 42 | // (even zero) predecessors and up to two successors. Blocks with multiple |
| 43 | // predecessors are "join nodes" and blocks with multiple successors are |
| 44 | // "branch nodes". A block can be both a branch and a join node. |
| 45 | // |
| 46 | // Flow graphs are in edge split form: a branch node is never the |
| 47 | // predecessor of a merge node. Empty basic blocks are inserted to maintain |
| 48 | // edge split form. |
| 49 | class BasicBlock: public ZoneObject { |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 50 | public: |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 51 | // Construct a basic block with a given predecessor. NULL indicates no |
| 52 | // predecessor or that the predecessor will be set later. |
| 53 | explicit BasicBlock(BasicBlock* predecessor) |
| 54 | : predecessors_(2), |
| 55 | instructions_(8), |
| 56 | left_successor_(NULL), |
| 57 | right_successor_(NULL), |
| 58 | mark_(false) { |
| 59 | if (predecessor != NULL) AddPredecessor(predecessor); |
| 60 | } |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 61 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 62 | bool HasPredecessor() { return !predecessors_.is_empty(); } |
| 63 | bool HasSuccessor() { return left_successor_ != NULL; } |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 64 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 65 | // Add a given basic block as a predecessor of this block. This function |
| 66 | // also adds this block as a successor of the given block. |
| 67 | void AddPredecessor(BasicBlock* predecessor) { |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 68 | ASSERT(predecessor != NULL); |
| 69 | predecessors_.Add(predecessor); |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 70 | predecessor->AddSuccessor(this); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 71 | } |
| 72 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 73 | // Add an instruction to the end of this block. The block must be "open" |
| 74 | // by not having a successor yet. |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 75 | void AddInstruction(AstNode* instruction) { |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 76 | ASSERT(!HasSuccessor() && instruction != NULL); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 77 | instructions_.Add(instruction); |
| 78 | } |
| 79 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 80 | // Perform a depth-first traversal of graph rooted at this node, |
| 81 | // accumulating pre- and postorder traversal orders. Visited nodes are |
| 82 | // marked with mark. |
| 83 | void BuildTraversalOrder(ZoneList<BasicBlock*>* preorder, |
| 84 | ZoneList<BasicBlock*>* postorder, |
| 85 | bool mark); |
| 86 | bool GetMark() { return mark_; } |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 87 | |
| 88 | #ifdef DEBUG |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 89 | // In debug mode, blocks are numbered in reverse postorder to help with |
| 90 | // printing. |
| 91 | int number() { return number_; } |
| 92 | void set_number(int n) { number_ = n; } |
| 93 | |
| 94 | // Print a basic block, given the number of the first instruction. |
| 95 | // Returns the next number after the number of the last instruction. |
| 96 | int PrintAsText(int instruction_number); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 97 | #endif |
| 98 | |
| 99 | private: |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 100 | // Add a given basic block as successor to this block. This function does |
| 101 | // not add this block as a predecessor of the given block so as to avoid |
| 102 | // circularity. |
| 103 | void AddSuccessor(BasicBlock* successor) { |
| 104 | ASSERT(right_successor_ == NULL && successor != NULL); |
| 105 | if (HasSuccessor()) { |
| 106 | right_successor_ = successor; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 107 | } else { |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 108 | left_successor_ = successor; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 109 | } |
| 110 | } |
| 111 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 112 | ZoneList<BasicBlock*> predecessors_; |
| 113 | ZoneList<AstNode*> instructions_; |
| 114 | BasicBlock* left_successor_; |
| 115 | BasicBlock* right_successor_; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 116 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 117 | // Support for graph traversal. Before traversal, all nodes in the graph |
| 118 | // have the same mark (true or false). Traversal marks already-visited |
| 119 | // nodes with the opposite mark. After traversal, all nodes again have |
| 120 | // the same mark. Traversal of the same graph is not reentrant. |
| 121 | bool mark_; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 122 | |
| 123 | #ifdef DEBUG |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 124 | int number_; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 125 | #endif |
| 126 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 127 | DISALLOW_COPY_AND_ASSIGN(BasicBlock); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 128 | }; |
| 129 | |
| 130 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 131 | // A flow graph has distinguished entry and exit blocks. The entry block is |
| 132 | // the only one with no predecessors and the exit block is the only one with |
| 133 | // no successors. |
| 134 | class FlowGraph: public ZoneObject { |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 135 | public: |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 136 | FlowGraph(BasicBlock* entry, BasicBlock* exit) |
| 137 | : entry_(entry), exit_(exit), preorder_(8), postorder_(8) { |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 138 | } |
| 139 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 140 | ZoneList<BasicBlock*>* preorder() { return &preorder_; } |
| 141 | ZoneList<BasicBlock*>* postorder() { return &postorder_; } |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 142 | |
| 143 | #ifdef DEBUG |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 144 | void PrintAsText(Handle<String> name); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 145 | #endif |
| 146 | |
| 147 | private: |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 148 | BasicBlock* entry_; |
| 149 | BasicBlock* exit_; |
| 150 | ZoneList<BasicBlock*> preorder_; |
| 151 | ZoneList<BasicBlock*> postorder_; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 152 | }; |
| 153 | |
| 154 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 155 | // The flow graph builder walks the AST adding reachable AST nodes to the |
| 156 | // flow graph as instructions. It remembers the entry and exit nodes of the |
| 157 | // graph, and keeps a pointer to the current block being constructed. |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 158 | class FlowGraphBuilder: public AstVisitor { |
| 159 | public: |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 160 | FlowGraphBuilder() {} |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 161 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 162 | FlowGraph* Build(FunctionLiteral* lit); |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 163 | |
| 164 | private: |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 165 | // AST node visit functions. |
| 166 | #define DECLARE_VISIT(type) virtual void Visit##type(type* node); |
| 167 | AST_NODE_LIST(DECLARE_VISIT) |
| 168 | #undef DECLARE_VISIT |
| 169 | |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame^] | 170 | BasicBlock* entry_; |
| 171 | BasicBlock* exit_; |
| 172 | BasicBlock* current_; |
ager@chromium.org | b26c50a | 2010-03-26 09:27:16 +0000 | [diff] [blame] | 173 | |
| 174 | DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); |
| 175 | }; |
| 176 | |
| 177 | |
| 178 | } } // namespace v8::internal |
| 179 | |
| 180 | #endif // V8_FLOW_GRAPH_H_ |