OLD | NEW |
---|---|
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 18 matching lines...) Expand all Loading... | |
29 #define V8_FLOW_GRAPH_H_ | 29 #define V8_FLOW_GRAPH_H_ |
30 | 30 |
31 #include "v8.h" | 31 #include "v8.h" |
32 | 32 |
33 #include "data-flow.h" | 33 #include "data-flow.h" |
34 #include "zone.h" | 34 #include "zone.h" |
35 | 35 |
36 namespace v8 { | 36 namespace v8 { |
37 namespace internal { | 37 namespace internal { |
38 | 38 |
39 // Flow-graph nodes. | 39 // The nodes of a flow graph are basic blocks. Basic blocks consist of |
40 class Node: public ZoneObject { | 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 { | |
41 public: | 50 public: |
42 Node() : number_(-1), mark_(false) {} | 51 // Construct a basic block with a given predecessor. NULL indicates no |
52 // predecessor or that the predecessor will be set later. | |
53 BasicBlock(BasicBlock* predecessor) | |
fschneider
2010/03/29 13:49:59
explicit for 1-argument constructors?
Kevin Millikin (Chromium)
2010/03/29 14:22:53
Done.
| |
54 : predecessors_(2), | |
55 instructions_(8), | |
56 left_successor_(NULL), | |
57 right_successor_(NULL), | |
58 mark_(false) { | |
59 if (predecessor != NULL) AddPredecessor(predecessor); | |
60 } | |
43 | 61 |
44 virtual ~Node() {} | 62 bool HasPredecessor() { return !predecessors_.is_empty(); } |
63 bool HasSuccessor() { return left_successor_ != NULL; } | |
45 | 64 |
46 virtual bool IsExitNode() { return false; } | 65 // Add a given basic block as a predecessor of this block. This function |
47 virtual bool IsBlockNode() { return false; } | 66 // also adds this block as a successor of the given block. |
48 virtual bool IsBranchNode() { return false; } | 67 void AddPredecessor(BasicBlock* predecessor) { |
49 virtual bool IsJoinNode() { return false; } | 68 ASSERT(predecessor != NULL); |
69 predecessors_.Add(predecessor); | |
70 predecessor->AddSuccessor(this); | |
71 } | |
50 | 72 |
51 virtual void AddPredecessor(Node* predecessor) = 0; | 73 // Add an instruction to the end of this block. The block must be "open" |
52 virtual void AddSuccessor(Node* successor) = 0; | 74 // by not having a successor yet. |
75 void AddInstruction(AstNode* instruction) { | |
76 ASSERT(!HasSuccessor() && instruction != NULL); | |
77 instructions_.Add(instruction); | |
78 } | |
53 | 79 |
54 bool IsMarkedWith(bool mark) { return mark_ == mark; } | 80 // Perform a depth-first traversal of graph rooted at this node, |
55 void MarkWith(bool mark) { mark_ = mark; } | 81 // accumulating pre- and postorder traversal orders. Visited nodes are |
56 | 82 // marked with mark. |
57 // Perform a depth first search and record preorder and postorder | 83 void BuildTraversalOrder(ZoneList<BasicBlock*>* preorder, |
58 // traversal orders. | 84 ZoneList<BasicBlock*>* postorder, |
59 virtual void Traverse(bool mark, | 85 bool mark); |
60 ZoneList<Node*>* preorder, | 86 bool GetMark() { return mark_; } |
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 | 87 |
81 #ifdef DEBUG | 88 #ifdef DEBUG |
82 void AssignNodeNumber(); | 89 // In debug mode, blocks are numbered in reverse postorder to help with |
83 void PrintReachingDefinitions(); | 90 // printing. |
84 virtual void PrintText() = 0; | 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); | |
85 #endif | 97 #endif |
86 | 98 |
87 protected: | 99 private: |
88 ReachingDefinitionsData rd_; | 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 } | |
89 | 111 |
90 private: | 112 ZoneList<BasicBlock*> predecessors_; |
91 int number_; | 113 ZoneList<AstNode*> instructions_; |
fschneider
2010/03/29 13:49:59
We probably need an accessor for instructions_. Bu
| |
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. | |
92 bool mark_; | 121 bool mark_; |
93 | 122 |
94 DISALLOW_COPY_AND_ASSIGN(Node); | 123 #ifdef DEBUG |
124 int number_; | |
125 #endif | |
126 | |
127 DISALLOW_COPY_AND_ASSIGN(BasicBlock); | |
95 }; | 128 }; |
96 | 129 |
97 | 130 |
98 // An exit node has a arbitrarily many predecessors and no successors. | 131 // A flow graph has distinguished entry and exit blocks. The entry block is |
99 class ExitNode: public Node { | 132 // the only one with no predecessors and the exit block is the only one with |
133 // no successors. | |
134 class FlowGraph: public ZoneObject { | |
100 public: | 135 public: |
101 ExitNode() : predecessors_(4) {} | 136 FlowGraph(BasicBlock* entry, BasicBlock* exit) |
102 | 137 : entry_(entry), exit_(exit), preorder_(8), postorder_(8) { |
103 virtual bool IsExitNode() { return true; } | |
104 | |
105 virtual void AddPredecessor(Node* predecessor) { | |
106 ASSERT(predecessor != NULL); | |
107 predecessors_.Add(predecessor); | |
108 } | 138 } |
109 | 139 |
110 virtual void AddSuccessor(Node* successor) { UNREACHABLE(); } | 140 ZoneList<BasicBlock*>* preorder() { return &preorder_; } |
111 | 141 ZoneList<BasicBlock*>* postorder() { return &postorder_; } |
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 | 142 |
119 #ifdef DEBUG | 143 #ifdef DEBUG |
120 virtual void PrintText(); | 144 void PrintAsText(Handle<String> name); |
121 #endif | 145 #endif |
122 | 146 |
123 private: | 147 private: |
124 ZoneList<Node*> predecessors_; | 148 BasicBlock* entry_; |
125 | 149 BasicBlock* exit_; |
126 DISALLOW_COPY_AND_ASSIGN(ExitNode); | 150 ZoneList<BasicBlock*> preorder_; |
151 ZoneList<BasicBlock*> postorder_; | |
127 }; | 152 }; |
128 | 153 |
129 | 154 |
130 // Block nodes have a single successor and predecessor and a list of | 155 // The flow graph builder walks the AST adding reachable AST nodes to the |
131 // instructions. | 156 // flow graph as instructions. It remembers the entry and exit nodes of the |
132 class BlockNode: public Node { | 157 // graph, and keeps a pointer to the current block being constructed. |
158 class FlowGraphBuilder: public AstVisitor { | |
133 public: | 159 public: |
134 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} | 160 FlowGraphBuilder() {} |
135 | 161 |
136 static BlockNode* cast(Node* node) { | 162 FlowGraph* Build(FunctionLiteral* lit); |
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 | 163 |
182 private: | 164 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. | 165 // AST node visit functions. |
356 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); | 166 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); |
357 AST_NODE_LIST(DECLARE_VISIT) | 167 AST_NODE_LIST(DECLARE_VISIT) |
358 #undef DECLARE_VISIT | 168 #undef DECLARE_VISIT |
359 | 169 |
360 FlowGraph graph_; | 170 BasicBlock* entry_; |
361 ExitNode* global_exit_; | 171 BasicBlock* exit_; |
362 ZoneList<Node*> preorder_; | 172 BasicBlock* current_; |
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 | 173 |
373 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); | 174 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); |
374 }; | 175 }; |
375 | 176 |
376 | 177 |
377 } } // namespace v8::internal | 178 } } // namespace v8::internal |
378 | 179 |
379 #endif // V8_FLOW_GRAPH_H_ | 180 #endif // V8_FLOW_GRAPH_H_ |
OLD | NEW |