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 104 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
115 | 115 |
116 int length() const { return length_; } | 116 int length() const { return length_; } |
117 | 117 |
118 private: | 118 private: |
119 int length_; | 119 int length_; |
120 int data_length_; | 120 int data_length_; |
121 uint32_t* data_; | 121 uint32_t* data_; |
122 }; | 122 }; |
123 | 123 |
124 | 124 |
125 // Forward declarations of Node types. | |
126 class Node; | |
127 class BranchNode; | |
128 class JoinNode; | |
129 | |
130 // Flow graphs have a single entry and single exit. The empty flowgraph is | |
131 // represented by both entry and exit being NULL. | |
132 class FlowGraph BASE_EMBEDDED { | |
133 public: | |
134 FlowGraph() : entry_(NULL), exit_(NULL) {} | |
135 | |
136 static FlowGraph Empty() { return FlowGraph(); } | |
137 | |
138 bool is_empty() const { return entry_ == NULL; } | |
139 Node* entry() const { return entry_; } | |
140 Node* exit() const { return exit_; } | |
141 | |
142 // Add a single instruction to the end of this flowgraph. | |
143 void AppendInstruction(AstNode* instruction); | |
144 | |
145 // Add a single node to the end of this flow graph. | |
146 void AppendNode(Node* node); | |
147 | |
148 // Add a flow graph fragment to the end of this one. | |
149 void AppendGraph(FlowGraph* graph); | |
150 | |
151 // Concatenate an if-then-else flow-graph to this one. Control is split | |
152 // and merged, so the graph remains single-entry, single-exit. | |
153 void Split(BranchNode* branch, | |
154 FlowGraph* left, | |
155 FlowGraph* right, | |
156 JoinNode* merge); | |
157 | |
158 // Concatenate a forward loop (e.g., while or for loop) flow-graph to this | |
159 // one. Control is split by the condition and merged back from the back | |
160 // edge at end of the body to the beginning of the condition. The single | |
161 // (free) exit of the result graph is the right (false) arm of the branch | |
162 // node. | |
163 void Loop(JoinNode* merge, | |
164 FlowGraph* condition, | |
165 BranchNode* branch, | |
166 FlowGraph* body); | |
167 | |
168 #ifdef DEBUG | |
169 void PrintText(ZoneList<Node*>* postorder); | |
170 #endif | |
171 | |
172 private: | |
173 Node* entry_; | |
174 Node* exit_; | |
175 }; | |
176 | |
177 | |
178 // Flow-graph nodes. | 125 // Flow-graph nodes. |
179 class Node: public ZoneObject { | 126 class Node: public ZoneObject { |
180 public: | 127 public: |
181 Node() : number_(-1), mark_(false) {} | 128 Node() : number_(-1), mark_(false) {} |
182 | 129 |
183 virtual ~Node() {} | 130 virtual ~Node() {} |
184 | 131 |
| 132 virtual bool IsExitNode() { return false; } |
185 virtual bool IsBlockNode() { return false; } | 133 virtual bool IsBlockNode() { return false; } |
| 134 virtual bool IsBranchNode() { return false; } |
186 virtual bool IsJoinNode() { return false; } | 135 virtual bool IsJoinNode() { return false; } |
187 | 136 |
188 virtual void AddPredecessor(Node* predecessor) = 0; | 137 virtual void AddPredecessor(Node* predecessor) = 0; |
189 virtual void AddSuccessor(Node* successor) = 0; | 138 virtual void AddSuccessor(Node* successor) = 0; |
190 | 139 |
191 bool IsMarkedWith(bool mark) { return mark_ == mark; } | 140 bool IsMarkedWith(bool mark) { return mark_ == mark; } |
192 void MarkWith(bool mark) { mark_ = mark; } | 141 void MarkWith(bool mark) { mark_ = mark; } |
193 | 142 |
194 // Perform a depth first search and record preorder and postorder | 143 // Perform a depth first search and record preorder and postorder |
195 // traversal orders. | 144 // traversal orders. |
(...skipping 10 matching lines...) Expand all Loading... |
206 #endif | 155 #endif |
207 | 156 |
208 private: | 157 private: |
209 int number_; | 158 int number_; |
210 bool mark_; | 159 bool mark_; |
211 | 160 |
212 DISALLOW_COPY_AND_ASSIGN(Node); | 161 DISALLOW_COPY_AND_ASSIGN(Node); |
213 }; | 162 }; |
214 | 163 |
215 | 164 |
216 // An entry node has no predecessors and a single successor. | |
217 class EntryNode: public Node { | |
218 public: | |
219 EntryNode() : successor_(NULL) {} | |
220 | |
221 void AddPredecessor(Node* predecessor) { UNREACHABLE(); } | |
222 | |
223 void AddSuccessor(Node* successor) { | |
224 ASSERT(successor_ == NULL && successor != NULL); | |
225 successor_ = successor; | |
226 } | |
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 Node* successor_; | |
238 | |
239 DISALLOW_COPY_AND_ASSIGN(EntryNode); | |
240 }; | |
241 | |
242 | |
243 // An exit node has a arbitrarily many predecessors and no successors. | 165 // An exit node has a arbitrarily many predecessors and no successors. |
244 class ExitNode: public Node { | 166 class ExitNode: public Node { |
245 public: | 167 public: |
246 ExitNode() : predecessors_(4) {} | 168 ExitNode() : predecessors_(4) {} |
247 | 169 |
| 170 bool IsExitNode() { return true; } |
| 171 |
248 void AddPredecessor(Node* predecessor) { | 172 void AddPredecessor(Node* predecessor) { |
249 ASSERT(predecessor != NULL); | 173 ASSERT(predecessor != NULL); |
250 predecessors_.Add(predecessor); | 174 predecessors_.Add(predecessor); |
251 } | 175 } |
252 | 176 |
253 void AddSuccessor(Node* successor) { /* Do nothing. */ } | 177 void AddSuccessor(Node* successor) { UNREACHABLE(); } |
254 | 178 |
255 void Traverse(bool mark, | 179 void Traverse(bool mark, |
256 ZoneList<Node*>* preorder, | 180 ZoneList<Node*>* preorder, |
257 ZoneList<Node*>* postorder); | 181 ZoneList<Node*>* postorder); |
258 | 182 |
259 #ifdef DEBUG | 183 #ifdef DEBUG |
260 void PrintText(); | 184 void PrintText(); |
261 #endif | 185 #endif |
262 | 186 |
263 private: | 187 private: |
264 ZoneList<Node*> predecessors_; | 188 ZoneList<Node*> predecessors_; |
265 | 189 |
266 DISALLOW_COPY_AND_ASSIGN(ExitNode); | 190 DISALLOW_COPY_AND_ASSIGN(ExitNode); |
267 }; | 191 }; |
268 | 192 |
269 | 193 |
270 // Block nodes have a single successor and predecessor and a list of | 194 // Block nodes have a single successor and predecessor and a list of |
271 // instructions. | 195 // instructions. |
272 class BlockNode: public Node { | 196 class BlockNode: public Node { |
273 public: | 197 public: |
274 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} | 198 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} |
275 | 199 |
276 static BlockNode* cast(Node* node) { | 200 static BlockNode* cast(Node* node) { |
277 ASSERT(node->IsBlockNode()); | 201 ASSERT(node->IsBlockNode()); |
278 return reinterpret_cast<BlockNode*>(node); | 202 return reinterpret_cast<BlockNode*>(node); |
279 } | 203 } |
280 | 204 |
281 bool IsBlockNode() { return true; } | 205 bool IsBlockNode() { return true; } |
282 | 206 |
| 207 bool is_empty() { return instructions_.is_empty(); } |
| 208 |
283 void AddPredecessor(Node* predecessor) { | 209 void AddPredecessor(Node* predecessor) { |
284 ASSERT(predecessor_ == NULL && predecessor != NULL); | 210 ASSERT(predecessor_ == NULL && predecessor != NULL); |
285 predecessor_ = predecessor; | 211 predecessor_ = predecessor; |
286 } | 212 } |
287 | 213 |
288 void AddSuccessor(Node* successor) { | 214 void AddSuccessor(Node* successor) { |
289 ASSERT(successor_ == NULL && successor != NULL); | 215 ASSERT(successor_ == NULL && successor != NULL); |
290 successor_ = successor; | 216 successor_ = successor; |
291 } | 217 } |
292 | 218 |
(...skipping 17 matching lines...) Expand all Loading... |
310 | 236 |
311 DISALLOW_COPY_AND_ASSIGN(BlockNode); | 237 DISALLOW_COPY_AND_ASSIGN(BlockNode); |
312 }; | 238 }; |
313 | 239 |
314 | 240 |
315 // Branch nodes have a single predecessor and a pair of successors. | 241 // Branch nodes have a single predecessor and a pair of successors. |
316 class BranchNode: public Node { | 242 class BranchNode: public Node { |
317 public: | 243 public: |
318 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} | 244 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} |
319 | 245 |
| 246 bool IsBranchNode() { return true; } |
| 247 |
320 void AddPredecessor(Node* predecessor) { | 248 void AddPredecessor(Node* predecessor) { |
321 ASSERT(predecessor_ == NULL && predecessor != NULL); | 249 ASSERT(predecessor_ == NULL && predecessor != NULL); |
322 predecessor_ = predecessor; | 250 predecessor_ = predecessor; |
323 } | 251 } |
324 | 252 |
325 void AddSuccessor(Node* successor) { | 253 void AddSuccessor(Node* successor) { |
326 ASSERT(successor1_ == NULL && successor != NULL); | 254 ASSERT(successor1_ == NULL && successor != NULL); |
327 if (successor0_ == NULL) { | 255 if (successor0_ == NULL) { |
328 successor0_ = successor; | 256 successor0_ = successor; |
329 } else { | 257 } else { |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
379 #endif | 307 #endif |
380 | 308 |
381 private: | 309 private: |
382 ZoneList<Node*> predecessors_; | 310 ZoneList<Node*> predecessors_; |
383 Node* successor_; | 311 Node* successor_; |
384 | 312 |
385 DISALLOW_COPY_AND_ASSIGN(JoinNode); | 313 DISALLOW_COPY_AND_ASSIGN(JoinNode); |
386 }; | 314 }; |
387 | 315 |
388 | 316 |
| 317 // Flow graphs have a single entry and single exit. The empty flowgraph is |
| 318 // represented by both entry and exit being NULL. |
| 319 class FlowGraph BASE_EMBEDDED { |
| 320 public: |
| 321 static FlowGraph Empty() { |
| 322 FlowGraph graph; |
| 323 graph.entry_ = new BlockNode(); |
| 324 graph.exit_ = graph.entry_; |
| 325 return graph; |
| 326 } |
| 327 |
| 328 bool is_empty() const { |
| 329 return entry_ == exit_ && BlockNode::cast(entry_)->is_empty(); |
| 330 } |
| 331 Node* entry() const { return entry_; } |
| 332 Node* exit() const { return exit_; } |
| 333 |
| 334 // Add a single instruction to the end of this flowgraph. |
| 335 void AppendInstruction(AstNode* instruction); |
| 336 |
| 337 // Add a single node to the end of this flow graph. |
| 338 void AppendNode(Node* node); |
| 339 |
| 340 // Add a flow graph fragment to the end of this one. |
| 341 void AppendGraph(FlowGraph* graph); |
| 342 |
| 343 // Concatenate an if-then-else flow-graph to this one. Control is split |
| 344 // and merged, so the graph remains single-entry, single-exit. |
| 345 void Split(BranchNode* branch, |
| 346 FlowGraph* left, |
| 347 FlowGraph* right, |
| 348 JoinNode* merge); |
| 349 |
| 350 // Concatenate a forward loop (e.g., while or for loop) flow-graph to this |
| 351 // one. Control is split by the condition and merged back from the back |
| 352 // edge at end of the body to the beginning of the condition. The single |
| 353 // (free) exit of the result graph is the right (false) arm of the branch |
| 354 // node. |
| 355 void Loop(JoinNode* merge, |
| 356 FlowGraph* condition, |
| 357 BranchNode* branch, |
| 358 FlowGraph* body); |
| 359 |
| 360 #ifdef DEBUG |
| 361 void PrintText(ZoneList<Node*>* postorder); |
| 362 #endif |
| 363 |
| 364 private: |
| 365 FlowGraph() : entry_(NULL), exit_(NULL) {} |
| 366 |
| 367 Node* entry_; |
| 368 Node* exit_; |
| 369 }; |
| 370 |
| 371 |
389 // Construct a flow graph from a function literal. Build pre- and postorder | 372 // Construct a flow graph from a function literal. Build pre- and postorder |
390 // traversal orders as a byproduct. | 373 // traversal orders as a byproduct. |
391 class FlowGraphBuilder: public AstVisitor { | 374 class FlowGraphBuilder: public AstVisitor { |
392 public: | 375 public: |
393 FlowGraphBuilder() | 376 FlowGraphBuilder() |
394 : global_exit_(NULL), | 377 : graph_(FlowGraph::Empty()), |
| 378 global_exit_(NULL), |
395 preorder_(4), | 379 preorder_(4), |
396 postorder_(4), | 380 postorder_(4), |
397 definitions_(4) { | 381 definitions_(4) { |
398 } | 382 } |
399 | 383 |
400 void Build(FunctionLiteral* lit); | 384 void Build(FunctionLiteral* lit); |
401 | 385 |
402 FlowGraph* graph() { return &graph_; } | 386 FlowGraph* graph() { return &graph_; } |
403 | 387 |
404 ZoneList<Node*>* postorder() { return &postorder_; } | 388 ZoneList<Node*>* postorder() { return &postorder_; } |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
499 VarUseMap live_vars_; | 483 VarUseMap live_vars_; |
500 | 484 |
501 DISALLOW_COPY_AND_ASSIGN(LivenessAnalyzer); | 485 DISALLOW_COPY_AND_ASSIGN(LivenessAnalyzer); |
502 }; | 486 }; |
503 | 487 |
504 | 488 |
505 } } // namespace v8::internal | 489 } } // namespace v8::internal |
506 | 490 |
507 | 491 |
508 #endif // V8_DATAFLOW_H_ | 492 #endif // V8_DATAFLOW_H_ |
OLD | NEW |