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 // 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 { | |
50 public: | |
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 } | |
61 | |
62 bool HasPredecessor() { return !predecessors_.is_empty(); } | |
63 bool HasSuccessor() { return left_successor_ != NULL; } | |
64 | |
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) { | |
68 ASSERT(predecessor != NULL); | |
69 predecessors_.Add(predecessor); | |
70 predecessor->AddSuccessor(this); | |
71 } | |
72 | |
73 // Add an instruction to the end of this block. The block must be "open" | |
74 // by not having a successor yet. | |
75 void AddInstruction(AstNode* instruction) { | |
76 ASSERT(!HasSuccessor() && instruction != NULL); | |
77 instructions_.Add(instruction); | |
78 } | |
79 | |
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_; } | |
87 | |
88 #ifdef DEBUG | |
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); | |
97 #endif | |
98 | |
99 private: | |
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; | |
107 } else { | |
108 left_successor_ = successor; | |
109 } | |
110 } | |
111 | |
112 ZoneList<BasicBlock*> predecessors_; | |
113 ZoneList<AstNode*> instructions_; | |
114 BasicBlock* left_successor_; | |
115 BasicBlock* right_successor_; | |
116 | |
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_; | |
122 | |
123 #ifdef DEBUG | |
124 int number_; | |
125 #endif | |
126 | |
127 DISALLOW_COPY_AND_ASSIGN(BasicBlock); | |
128 }; | |
129 | |
130 | |
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 { | |
135 public: | |
136 FlowGraph(BasicBlock* entry, BasicBlock* exit) | |
137 : entry_(entry), exit_(exit), preorder_(8), postorder_(8) { | |
138 } | |
139 | |
140 ZoneList<BasicBlock*>* preorder() { return &preorder_; } | |
141 ZoneList<BasicBlock*>* postorder() { return &postorder_; } | |
142 | |
143 #ifdef DEBUG | |
144 void PrintAsText(Handle<String> name); | |
145 #endif | |
146 | |
147 private: | |
148 BasicBlock* entry_; | |
149 BasicBlock* exit_; | |
150 ZoneList<BasicBlock*> preorder_; | |
151 ZoneList<BasicBlock*> postorder_; | |
152 }; | |
153 | |
154 | |
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. | |
158 class FlowGraphBuilder: public AstVisitor { | |
159 public: | |
160 FlowGraphBuilder() {} | |
161 | |
162 FlowGraph* Build(FunctionLiteral* lit); | |
163 | |
164 private: | |
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 | |
170 BasicBlock* entry_; | |
171 BasicBlock* exit_; | |
172 BasicBlock* current_; | |
173 | |
174 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); | |
175 }; | |
176 | |
177 | |
178 } } // namespace v8::internal | |
179 | |
180 #endif // V8_FLOW_GRAPH_H_ | |
OLD | NEW |