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 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
88 int length() const { return length_; } | 88 int length() const { return length_; } |
89 | 89 |
90 private: | 90 private: |
91 int length_; | 91 int length_; |
92 Vector<uint32_t> bits_; | 92 Vector<uint32_t> bits_; |
93 | 93 |
94 DISALLOW_COPY_AND_ASSIGN(BitVector); | 94 DISALLOW_COPY_AND_ASSIGN(BitVector); |
95 }; | 95 }; |
96 | 96 |
97 | 97 |
98 // Forward declarations of Node types. | |
99 class Node; | |
100 class BranchNode; | |
101 class JoinNode; | |
102 | |
103 // Flow graphs have a single entry and single exit. The empty flowgraph is | |
104 // represented by both entry and exit being NULL. | |
105 class FlowGraph BASE_EMBEDDED { | |
106 public: | |
107 FlowGraph() : entry_(NULL), exit_(NULL) {} | |
108 | |
109 static FlowGraph Empty() { return FlowGraph(); } | |
110 | |
111 bool is_empty() const { return entry_ == NULL; } | |
112 Node* entry() const { return entry_; } | |
113 Node* exit() const { return exit_; } | |
114 | |
115 // Add a single instruction to the end of this flowgraph. | |
116 void Append(AstNode* instruction); | |
fschneider
2010/03/08 12:14:27
I'm not sure if overloading the name Append helps
| |
117 | |
118 // Add a single node to the end of this flow graph. | |
119 void Append(Node* node); | |
120 | |
121 // Add a flow graph fragment to the end of this one. | |
122 void Append(FlowGraph* graph); | |
123 | |
124 // Concatenate an if-then-else flow-graph to this one. Control is split | |
125 // and merged, so the graph remains single-entry, single-exit. | |
fschneider
2010/03/08 12:14:27
Maybe mentions that left is always the true-branch
| |
126 void Split(BranchNode* branch, | |
127 FlowGraph* left, | |
128 FlowGraph* right, | |
129 JoinNode* merge); | |
130 | |
131 // Concatenate a forward loop (e.g., while or for loop) flow-graph to this | |
132 // one. Control is split by the condition and merged back from the back | |
133 // edge at end of the body to the beginning of the condition. The single | |
134 // (free) exit of the result graph is the right (false) arm of the branch | |
135 // node. | |
136 void Loop(JoinNode* merge, | |
137 FlowGraph* condition, | |
138 BranchNode* branch, | |
139 FlowGraph* body); | |
140 | |
141 #ifdef DEBUG | |
142 void PrintText(ZoneList<Node*>* postorder); | |
143 #endif | |
144 | |
145 private: | |
146 Node* entry_; | |
147 Node* exit_; | |
148 }; | |
149 | |
150 | |
151 // Flow-graph nodes. | |
152 class Node: public ZoneObject { | |
153 public: | |
154 Node() : number_(-1), mark_(false) {} | |
155 | |
156 virtual ~Node() {} | |
157 | |
158 virtual bool IsBlockNode() { return false; } | |
159 virtual bool IsJoinNode() { return false; } | |
160 | |
161 virtual void AddPredecessor(Node* predecessor) = 0; | |
162 virtual void AddSuccessor(Node* successor) = 0; | |
163 | |
164 bool IsMarkedWith(bool mark) { return mark_ == mark; } | |
165 void MarkWith(bool mark) { mark_ = mark; } | |
fschneider
2010/03/08 12:14:27
Name this functions consistently with other access
| |
166 | |
167 // Perform a depth first search and record preorder and postorder | |
168 // traversal orders. | |
169 virtual void Traverse(bool mark, | |
170 ZoneList<Node*>* preorder, | |
171 ZoneList<Node*>* postorder) = 0; | |
172 | |
173 int number() { return number_; } | |
174 void set_number(int number) { number_ = number; } | |
175 | |
176 #ifdef DEBUG | |
177 virtual void AssignNumbers(); | |
178 virtual void PrintText() = 0; | |
179 #endif | |
180 | |
181 private: | |
182 int number_; | |
183 bool mark_; | |
184 | |
185 DISALLOW_COPY_AND_ASSIGN(Node); | |
186 }; | |
187 | |
188 | |
189 // An entry node has no predecessors and a single successor. | |
190 class EntryNode: public Node { | |
191 public: | |
192 EntryNode() : successor_(NULL) {} | |
193 | |
194 void AddPredecessor(Node* predecessor) { UNREACHABLE(); } | |
195 | |
196 void AddSuccessor(Node* successor) { | |
197 ASSERT(successor_ == NULL && successor != NULL); | |
198 successor_ = successor; | |
199 } | |
200 | |
201 void Traverse(bool mark, | |
202 ZoneList<Node*>* preorder, | |
203 ZoneList<Node*>* postorder); | |
204 | |
205 #ifdef DEBUG | |
206 void PrintText(); | |
207 #endif | |
208 | |
209 private: | |
210 Node* successor_; | |
211 | |
212 DISALLOW_COPY_AND_ASSIGN(EntryNode); | |
213 }; | |
214 | |
215 | |
216 // An exit node has a arbitrarily many predecessors and no successors. | |
217 class ExitNode: public Node { | |
218 public: | |
219 ExitNode() : predecessors_(4) {} | |
220 | |
221 void AddPredecessor(Node* predecessor) { | |
222 ASSERT(predecessor != NULL); | |
223 predecessors_.Add(predecessor); | |
224 } | |
225 | |
226 void AddSuccessor(Node* successor) { /* Do nothing. */ } | |
227 | |
228 void Traverse(bool mark, | |
229 ZoneList<Node*>* preorder, | |
230 ZoneList<Node*>* postorder); | |
231 | |
232 #ifdef DEBUG | |
233 void PrintText(); | |
234 #endif | |
235 | |
236 private: | |
237 ZoneList<Node*> predecessors_; | |
238 | |
239 DISALLOW_COPY_AND_ASSIGN(ExitNode); | |
240 }; | |
241 | |
242 | |
243 // Block nodes have a single successor and predecessor and a list of | |
244 // instructions. | |
245 class BlockNode: public Node { | |
246 public: | |
247 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} | |
248 | |
249 static BlockNode* cast(Node* node) { | |
250 ASSERT(node->IsBlockNode()); | |
251 return reinterpret_cast<BlockNode*>(node); | |
252 } | |
253 | |
254 bool IsBlockNode() { return true; } | |
255 | |
256 void AddPredecessor(Node* predecessor) { | |
257 ASSERT(predecessor_ == NULL && predecessor != NULL); | |
258 predecessor_ = predecessor; | |
259 } | |
260 | |
261 void AddSuccessor(Node* successor) { | |
262 ASSERT(successor_ == NULL && successor != NULL); | |
263 successor_ = successor; | |
264 } | |
265 | |
266 void AddInstruction(AstNode* instruction) { | |
267 instructions_.Add(instruction); | |
268 } | |
269 | |
270 void Traverse(bool mark, | |
271 ZoneList<Node*>* preorder, | |
272 ZoneList<Node*>* postorder); | |
273 | |
274 #ifdef DEBUG | |
275 void AssignNumbers(); | |
276 void PrintText(); | |
277 #endif | |
278 | |
279 private: | |
280 Node* predecessor_; | |
281 Node* successor_; | |
282 ZoneList<AstNode*> instructions_; | |
283 | |
284 DISALLOW_COPY_AND_ASSIGN(BlockNode); | |
285 }; | |
286 | |
287 | |
288 // Branch nodes have a single predecessor and a pair of successors. | |
289 class BranchNode: public Node { | |
290 public: | |
291 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} | |
292 | |
293 void AddPredecessor(Node* predecessor) { | |
294 ASSERT(predecessor_ == NULL && predecessor != NULL); | |
295 predecessor_ = predecessor; | |
296 } | |
297 | |
298 void AddSuccessor(Node* successor) { | |
299 ASSERT(successor1_ == NULL && successor != NULL); | |
300 if (successor0_ == NULL) { | |
301 successor0_ = successor; | |
302 } else { | |
303 successor1_ = successor; | |
304 } | |
305 } | |
306 | |
307 void Traverse(bool mark, | |
308 ZoneList<Node*>* preorder, | |
309 ZoneList<Node*>* postorder); | |
310 | |
311 #ifdef DEBUG | |
312 void PrintText(); | |
313 #endif | |
314 | |
315 private: | |
316 Node* predecessor_; | |
317 Node* successor0_; | |
318 Node* successor1_; | |
319 | |
320 DISALLOW_COPY_AND_ASSIGN(BranchNode); | |
321 }; | |
322 | |
323 | |
324 // Join nodes have arbitrarily many predecessors and a single successor. | |
325 class JoinNode: public Node { | |
326 public: | |
327 JoinNode() : predecessors_(2), successor_(NULL) {} | |
328 | |
329 static JoinNode* cast(Node* node) { | |
330 ASSERT(node->IsJoinNode()); | |
331 return reinterpret_cast<JoinNode*>(node); | |
332 } | |
333 | |
334 bool IsJoinNode() { return true; } | |
335 | |
336 void AddPredecessor(Node* predecessor) { | |
337 ASSERT(predecessor != NULL); | |
338 predecessors_.Add(predecessor); | |
339 } | |
340 | |
341 void AddSuccessor(Node* successor) { | |
342 ASSERT(successor_ == NULL && successor != NULL); | |
343 successor_ = successor; | |
344 } | |
345 | |
346 void Traverse(bool mark, | |
347 ZoneList<Node*>* preorder, | |
348 ZoneList<Node*>* postorder); | |
349 | |
350 #ifdef DEBUG | |
351 void PrintText(); | |
352 #endif | |
353 | |
354 private: | |
355 ZoneList<Node*> predecessors_; | |
356 Node* successor_; | |
357 | |
358 DISALLOW_COPY_AND_ASSIGN(JoinNode); | |
359 }; | |
360 | |
361 | |
362 // Construct a flow graph from a function literal. Build pre- and postorder | |
363 // traversal orders as a byproduct. | |
364 class FlowGraphBuilder: public AstVisitor { | |
365 public: | |
366 FlowGraphBuilder() : global_exit_(NULL), preorder_(4), postorder_(4) {} | |
367 | |
368 void Build(FunctionLiteral* lit); | |
369 | |
370 FlowGraph* graph() { return &graph_; } | |
371 | |
372 ZoneList<Node*>* postorder() { return &postorder_; } | |
373 | |
374 private: | |
375 ExitNode* global_exit() { return global_exit_; } | |
376 | |
377 // AST node visit functions. | |
378 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); | |
379 AST_NODE_LIST(DECLARE_VISIT) | |
380 #undef DECLARE_VISIT | |
381 | |
382 FlowGraph graph_; | |
383 ExitNode* global_exit_; | |
384 ZoneList<Node*> preorder_; | |
385 ZoneList<Node*> postorder_; | |
386 | |
387 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); | |
388 }; | |
389 | |
390 | |
98 // This class is used to number all expressions in the AST according to | 391 // This class is used to number all expressions in the AST according to |
99 // their evaluation order (post-order left-to-right traversal). | 392 // their evaluation order (post-order left-to-right traversal). |
100 class AstLabeler: public AstVisitor { | 393 class AstLabeler: public AstVisitor { |
101 public: | 394 public: |
102 AstLabeler() : next_number_(0) {} | 395 AstLabeler() : next_number_(0) {} |
103 | 396 |
104 void Label(CompilationInfo* info); | 397 void Label(CompilationInfo* info); |
105 | 398 |
106 private: | 399 private: |
107 CompilationInfo* info() { return info_; } | 400 CompilationInfo* info() { return info_; } |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
169 VarUseMap live_vars_; | 462 VarUseMap live_vars_; |
170 | 463 |
171 DISALLOW_COPY_AND_ASSIGN(LivenessAnalyzer); | 464 DISALLOW_COPY_AND_ASSIGN(LivenessAnalyzer); |
172 }; | 465 }; |
173 | 466 |
174 | 467 |
175 } } // namespace v8::internal | 468 } } // namespace v8::internal |
176 | 469 |
177 | 470 |
178 #endif // V8_DATAFLOW_H_ | 471 #endif // V8_DATAFLOW_H_ |
OLD | NEW |