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 223 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
234 | 234 |
235 // Functions used by data-flow analyses. | 235 // Functions used by data-flow analyses. |
236 virtual void InitializeReachingDefinitions(int definition_count, | 236 virtual void InitializeReachingDefinitions(int definition_count, |
237 List<BitVector*>* variables, | 237 List<BitVector*>* variables, |
238 WorkList<Node>* worklist, | 238 WorkList<Node>* worklist, |
239 bool mark); | 239 bool mark); |
240 virtual void ComputeRDOut(BitVector* result) = 0; | 240 virtual void ComputeRDOut(BitVector* result) = 0; |
241 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0; | 241 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0; |
242 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); | 242 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); |
243 | 243 |
| 244 // Functions used by dead-code elimination. |
| 245 virtual void MarkCriticalInstructions( |
| 246 List<AstNode*>* stack, |
| 247 ZoneList<Expression*>* body_definitions, |
| 248 int variable_count); |
| 249 |
244 #ifdef DEBUG | 250 #ifdef DEBUG |
245 void AssignNodeNumber(); | 251 void AssignNodeNumber(); |
246 void PrintReachingDefinitions(); | 252 void PrintReachingDefinitions(); |
247 virtual void PrintText() = 0; | 253 virtual void PrintText() = 0; |
248 #endif | 254 #endif |
249 | 255 |
250 protected: | 256 protected: |
251 ReachingDefinitionsData rd_; | 257 ReachingDefinitionsData rd_; |
252 | 258 |
253 private: | 259 private: |
254 int number_; | 260 int number_; |
255 bool mark_; | 261 bool mark_; |
256 | 262 |
257 DISALLOW_COPY_AND_ASSIGN(Node); | 263 DISALLOW_COPY_AND_ASSIGN(Node); |
258 }; | 264 }; |
259 | 265 |
260 | 266 |
261 // An exit node has a arbitrarily many predecessors and no successors. | 267 // An exit node has a arbitrarily many predecessors and no successors. |
262 class ExitNode: public Node { | 268 class ExitNode: public Node { |
263 public: | 269 public: |
264 ExitNode() : predecessors_(4) {} | 270 ExitNode() : predecessors_(4) {} |
265 | 271 |
266 bool IsExitNode() { return true; } | 272 virtual bool IsExitNode() { return true; } |
267 | 273 |
268 void AddPredecessor(Node* predecessor) { | 274 virtual void AddPredecessor(Node* predecessor) { |
269 ASSERT(predecessor != NULL); | 275 ASSERT(predecessor != NULL); |
270 predecessors_.Add(predecessor); | 276 predecessors_.Add(predecessor); |
271 } | 277 } |
272 | 278 |
273 void AddSuccessor(Node* successor) { UNREACHABLE(); } | 279 virtual void AddSuccessor(Node* successor) { UNREACHABLE(); } |
274 | 280 |
275 void Traverse(bool mark, | 281 virtual void Traverse(bool mark, |
276 ZoneList<Node*>* preorder, | 282 ZoneList<Node*>* preorder, |
277 ZoneList<Node*>* postorder); | 283 ZoneList<Node*>* postorder); |
278 | 284 |
279 void ComputeRDOut(BitVector* result); | 285 virtual void ComputeRDOut(BitVector* result); |
280 void UpdateRDIn(WorkList<Node>* worklist, bool mark); | 286 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
281 | 287 |
282 #ifdef DEBUG | 288 #ifdef DEBUG |
283 void PrintText(); | 289 virtual void PrintText(); |
284 #endif | 290 #endif |
285 | 291 |
286 private: | 292 private: |
287 ZoneList<Node*> predecessors_; | 293 ZoneList<Node*> predecessors_; |
288 | 294 |
289 DISALLOW_COPY_AND_ASSIGN(ExitNode); | 295 DISALLOW_COPY_AND_ASSIGN(ExitNode); |
290 }; | 296 }; |
291 | 297 |
292 | 298 |
293 // Block nodes have a single successor and predecessor and a list of | 299 // Block nodes have a single successor and predecessor and a list of |
294 // instructions. | 300 // instructions. |
295 class BlockNode: public Node { | 301 class BlockNode: public Node { |
296 public: | 302 public: |
297 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} | 303 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} |
298 | 304 |
299 static BlockNode* cast(Node* node) { | 305 static BlockNode* cast(Node* node) { |
300 ASSERT(node->IsBlockNode()); | 306 ASSERT(node->IsBlockNode()); |
301 return reinterpret_cast<BlockNode*>(node); | 307 return reinterpret_cast<BlockNode*>(node); |
302 } | 308 } |
303 | 309 |
304 bool IsBlockNode() { return true; } | 310 virtual bool IsBlockNode() { return true; } |
305 | 311 |
306 bool is_empty() { return instructions_.is_empty(); } | 312 bool is_empty() { return instructions_.is_empty(); } |
307 | 313 |
308 ZoneList<AstNode*>* instructions() { return &instructions_; } | 314 ZoneList<AstNode*>* instructions() { return &instructions_; } |
309 | 315 |
310 void AddPredecessor(Node* predecessor) { | 316 virtual void AddPredecessor(Node* predecessor) { |
311 ASSERT(predecessor_ == NULL && predecessor != NULL); | 317 ASSERT(predecessor_ == NULL && predecessor != NULL); |
312 predecessor_ = predecessor; | 318 predecessor_ = predecessor; |
313 } | 319 } |
314 | 320 |
315 void AddSuccessor(Node* successor) { | 321 virtual void AddSuccessor(Node* successor) { |
316 ASSERT(successor_ == NULL && successor != NULL); | 322 ASSERT(successor_ == NULL && successor != NULL); |
317 successor_ = successor; | 323 successor_ = successor; |
318 } | 324 } |
319 | 325 |
320 void AddInstruction(AstNode* instruction) { | 326 void AddInstruction(AstNode* instruction) { |
321 instructions_.Add(instruction); | 327 instructions_.Add(instruction); |
322 } | 328 } |
323 | 329 |
324 void Traverse(bool mark, | 330 virtual void Traverse(bool mark, |
325 ZoneList<Node*>* preorder, | 331 ZoneList<Node*>* preorder, |
326 ZoneList<Node*>* postorder); | 332 ZoneList<Node*>* postorder); |
327 | 333 |
328 void InitializeReachingDefinitions(int definition_count, | 334 virtual void InitializeReachingDefinitions(int definition_count, |
329 List<BitVector*>* variables, | 335 List<BitVector*>* variables, |
330 WorkList<Node>* worklist, | 336 WorkList<Node>* worklist, |
331 bool mark); | 337 bool mark); |
332 void ComputeRDOut(BitVector* result); | 338 virtual void ComputeRDOut(BitVector* result); |
333 void UpdateRDIn(WorkList<Node>* worklist, bool mark); | 339 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
334 void PropagateReachingDefinitions(List<BitVector*>* variables); | 340 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); |
| 341 |
| 342 virtual void MarkCriticalInstructions( |
| 343 List<AstNode*>* stack, |
| 344 ZoneList<Expression*>* body_definitions, |
| 345 int variable_count); |
335 | 346 |
336 #ifdef DEBUG | 347 #ifdef DEBUG |
337 void PrintText(); | 348 virtual void PrintText(); |
338 #endif | 349 #endif |
339 | 350 |
340 private: | 351 private: |
341 Node* predecessor_; | 352 Node* predecessor_; |
342 Node* successor_; | 353 Node* successor_; |
343 ZoneList<AstNode*> instructions_; | 354 ZoneList<AstNode*> instructions_; |
344 | 355 |
345 DISALLOW_COPY_AND_ASSIGN(BlockNode); | 356 DISALLOW_COPY_AND_ASSIGN(BlockNode); |
346 }; | 357 }; |
347 | 358 |
348 | 359 |
349 // Branch nodes have a single predecessor and a pair of successors. | 360 // Branch nodes have a single predecessor and a pair of successors. |
350 class BranchNode: public Node { | 361 class BranchNode: public Node { |
351 public: | 362 public: |
352 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} | 363 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} |
353 | 364 |
354 bool IsBranchNode() { return true; } | 365 virtual bool IsBranchNode() { return true; } |
355 | 366 |
356 void AddPredecessor(Node* predecessor) { | 367 virtual void AddPredecessor(Node* predecessor) { |
357 ASSERT(predecessor_ == NULL && predecessor != NULL); | 368 ASSERT(predecessor_ == NULL && predecessor != NULL); |
358 predecessor_ = predecessor; | 369 predecessor_ = predecessor; |
359 } | 370 } |
360 | 371 |
361 void AddSuccessor(Node* successor) { | 372 virtual void AddSuccessor(Node* successor) { |
362 ASSERT(successor1_ == NULL && successor != NULL); | 373 ASSERT(successor1_ == NULL && successor != NULL); |
363 if (successor0_ == NULL) { | 374 if (successor0_ == NULL) { |
364 successor0_ = successor; | 375 successor0_ = successor; |
365 } else { | 376 } else { |
366 successor1_ = successor; | 377 successor1_ = successor; |
367 } | 378 } |
368 } | 379 } |
369 | 380 |
370 void Traverse(bool mark, | 381 virtual void Traverse(bool mark, |
371 ZoneList<Node*>* preorder, | 382 ZoneList<Node*>* preorder, |
372 ZoneList<Node*>* postorder); | 383 ZoneList<Node*>* postorder); |
373 | 384 |
374 void ComputeRDOut(BitVector* result); | 385 virtual void ComputeRDOut(BitVector* result); |
375 void UpdateRDIn(WorkList<Node>* worklist, bool mark); | 386 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
376 | 387 |
377 #ifdef DEBUG | 388 #ifdef DEBUG |
378 void PrintText(); | 389 virtual void PrintText(); |
379 #endif | 390 #endif |
380 | 391 |
381 private: | 392 private: |
382 Node* predecessor_; | 393 Node* predecessor_; |
383 Node* successor0_; | 394 Node* successor0_; |
384 Node* successor1_; | 395 Node* successor1_; |
385 | 396 |
386 DISALLOW_COPY_AND_ASSIGN(BranchNode); | 397 DISALLOW_COPY_AND_ASSIGN(BranchNode); |
387 }; | 398 }; |
388 | 399 |
389 | 400 |
390 // Join nodes have arbitrarily many predecessors and a single successor. | 401 // Join nodes have arbitrarily many predecessors and a single successor. |
391 class JoinNode: public Node { | 402 class JoinNode: public Node { |
392 public: | 403 public: |
393 JoinNode() : predecessors_(2), successor_(NULL) {} | 404 JoinNode() : predecessors_(2), successor_(NULL) {} |
394 | 405 |
395 static JoinNode* cast(Node* node) { | 406 static JoinNode* cast(Node* node) { |
396 ASSERT(node->IsJoinNode()); | 407 ASSERT(node->IsJoinNode()); |
397 return reinterpret_cast<JoinNode*>(node); | 408 return reinterpret_cast<JoinNode*>(node); |
398 } | 409 } |
399 | 410 |
400 bool IsJoinNode() { return true; } | 411 virtual bool IsJoinNode() { return true; } |
401 | 412 |
402 void AddPredecessor(Node* predecessor) { | 413 virtual void AddPredecessor(Node* predecessor) { |
403 ASSERT(predecessor != NULL); | 414 ASSERT(predecessor != NULL); |
404 predecessors_.Add(predecessor); | 415 predecessors_.Add(predecessor); |
405 } | 416 } |
406 | 417 |
407 void AddSuccessor(Node* successor) { | 418 virtual void AddSuccessor(Node* successor) { |
408 ASSERT(successor_ == NULL && successor != NULL); | 419 ASSERT(successor_ == NULL && successor != NULL); |
409 successor_ = successor; | 420 successor_ = successor; |
410 } | 421 } |
411 | 422 |
412 void Traverse(bool mark, | 423 virtual void Traverse(bool mark, |
413 ZoneList<Node*>* preorder, | 424 ZoneList<Node*>* preorder, |
414 ZoneList<Node*>* postorder); | 425 ZoneList<Node*>* postorder); |
415 | 426 |
416 void ComputeRDOut(BitVector* result); | 427 virtual void ComputeRDOut(BitVector* result); |
417 void UpdateRDIn(WorkList<Node>* worklist, bool mark); | 428 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
418 | 429 |
419 #ifdef DEBUG | 430 #ifdef DEBUG |
420 void PrintText(); | 431 virtual void PrintText(); |
421 #endif | 432 #endif |
422 | 433 |
423 private: | 434 private: |
424 ZoneList<Node*> predecessors_; | 435 ZoneList<Node*> predecessors_; |
425 Node* successor_; | 436 Node* successor_; |
426 | 437 |
427 DISALLOW_COPY_AND_ASSIGN(JoinNode); | 438 DISALLOW_COPY_AND_ASSIGN(JoinNode); |
428 }; | 439 }; |
429 | 440 |
430 | 441 |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
492 global_exit_(NULL), | 503 global_exit_(NULL), |
493 preorder_(4), | 504 preorder_(4), |
494 postorder_(4), | 505 postorder_(4), |
495 variable_count_(variable_count), | 506 variable_count_(variable_count), |
496 body_definitions_(4) { | 507 body_definitions_(4) { |
497 } | 508 } |
498 | 509 |
499 void Build(FunctionLiteral* lit); | 510 void Build(FunctionLiteral* lit); |
500 | 511 |
501 FlowGraph* graph() { return &graph_; } | 512 FlowGraph* graph() { return &graph_; } |
| 513 ZoneList<Node*>* preorder() { return &preorder_; } |
502 ZoneList<Node*>* postorder() { return &postorder_; } | 514 ZoneList<Node*>* postorder() { return &postorder_; } |
503 ZoneList<Expression*>* body_definitions() { return &body_definitions_; } | 515 ZoneList<Expression*>* body_definitions() { return &body_definitions_; } |
504 | 516 |
505 private: | 517 private: |
506 ExitNode* global_exit() { return global_exit_; } | 518 ExitNode* global_exit() { return global_exit_; } |
507 | 519 |
508 // Helpers to allow tranforming the ast during flow graph construction. | 520 // Helpers to allow tranforming the ast during flow graph construction. |
509 void VisitStatements(ZoneList<Statement*>* stmts); | 521 void VisitStatements(ZoneList<Statement*>* stmts); |
510 Statement* ProcessStatement(Statement* stmt); | 522 Statement* ProcessStatement(Statement* stmt); |
511 | 523 |
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
615 | 627 |
616 // A list of all the definitions in the body. | 628 // A list of all the definitions in the body. |
617 ZoneList<Expression*>* body_definitions_; | 629 ZoneList<Expression*>* body_definitions_; |
618 | 630 |
619 int variable_count_; | 631 int variable_count_; |
620 | 632 |
621 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); | 633 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); |
622 }; | 634 }; |
623 | 635 |
624 | 636 |
625 | |
626 class TypeAnalyzer BASE_EMBEDDED { | 637 class TypeAnalyzer BASE_EMBEDDED { |
627 public: | 638 public: |
628 TypeAnalyzer(ZoneList<Node*>* postorder, | 639 TypeAnalyzer(ZoneList<Node*>* postorder, |
629 ZoneList<Expression*>* body_definitions, | 640 ZoneList<Expression*>* body_definitions, |
630 int variable_count, | 641 int variable_count, |
631 int param_count) | 642 int param_count) |
632 : postorder_(postorder), | 643 : postorder_(postorder), |
633 body_definitions_(body_definitions), | 644 body_definitions_(body_definitions), |
634 variable_count_(variable_count), | 645 variable_count_(variable_count), |
635 param_count_(param_count) {} | 646 param_count_(param_count) {} |
636 | 647 |
637 void Compute(); | 648 void Compute(); |
638 | 649 |
639 private: | 650 private: |
640 // Get the primitity of definition number i. Definitions are numbered | 651 // Get the primitity of definition number i. Definitions are numbered |
641 // by the flow graph builder. | 652 // by the flow graph builder. |
642 bool IsPrimitiveDef(int def_num); | 653 bool IsPrimitiveDef(int def_num); |
643 | 654 |
644 ZoneList<Node*>* postorder_; | 655 ZoneList<Node*>* postorder_; |
645 ZoneList<Expression*>* body_definitions_; | 656 ZoneList<Expression*>* body_definitions_; |
646 int variable_count_; | 657 int variable_count_; |
647 int param_count_; | 658 int param_count_; |
| 659 |
| 660 DISALLOW_COPY_AND_ASSIGN(TypeAnalyzer); |
648 }; | 661 }; |
649 | 662 |
| 663 |
| 664 void MarkLiveCode(ZoneList<Node*>* nodes, |
| 665 ZoneList<Expression*>* body_definitions, |
| 666 int variable_count); |
| 667 |
| 668 |
650 } } // namespace v8::internal | 669 } } // namespace v8::internal |
651 | 670 |
652 | 671 |
653 #endif // V8_DATAFLOW_H_ | 672 #endif // V8_DATAFLOW_H_ |
OLD | NEW |