OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #ifndef RUNTIME_VM_FLOW_GRAPH_H_ | 5 #ifndef RUNTIME_VM_FLOW_GRAPH_H_ |
6 #define RUNTIME_VM_FLOW_GRAPH_H_ | 6 #define RUNTIME_VM_FLOW_GRAPH_H_ |
7 | 7 |
8 #include "vm/bit_vector.h" | 8 #include "vm/bit_vector.h" |
9 #include "vm/growable_array.h" | 9 #include "vm/growable_array.h" |
10 #include "vm/hash_map.h" | 10 #include "vm/hash_map.h" |
(...skipping 25 matching lines...) Expand all Loading... |
36 | 36 |
37 bool Done() const { return current_ >= block_order_.length(); } | 37 bool Done() const { return current_ >= block_order_.length(); } |
38 | 38 |
39 BlockEntryInstr* Current() const { return block_order_[current_]; } | 39 BlockEntryInstr* Current() const { return block_order_[current_]; } |
40 | 40 |
41 private: | 41 private: |
42 const GrowableArray<BlockEntryInstr*>& block_order_; | 42 const GrowableArray<BlockEntryInstr*>& block_order_; |
43 intptr_t current_; | 43 intptr_t current_; |
44 }; | 44 }; |
45 | 45 |
46 | |
47 struct ConstantPoolTrait { | 46 struct ConstantPoolTrait { |
48 typedef ConstantInstr* Value; | 47 typedef ConstantInstr* Value; |
49 typedef const Object& Key; | 48 typedef const Object& Key; |
50 typedef ConstantInstr* Pair; | 49 typedef ConstantInstr* Pair; |
51 | 50 |
52 static Key KeyOf(Pair kv) { return kv->value(); } | 51 static Key KeyOf(Pair kv) { return kv->value(); } |
53 | 52 |
54 static Value ValueOf(Pair kv) { return kv; } | 53 static Value ValueOf(Pair kv) { return kv; } |
55 | 54 |
56 static inline intptr_t Hashcode(Key key) { | 55 static inline intptr_t Hashcode(Key key) { |
(...skipping 11 matching lines...) Expand all Loading... |
68 return String::Cast(key).Hash(); | 67 return String::Cast(key).Hash(); |
69 } | 68 } |
70 return key.GetClassId(); | 69 return key.GetClassId(); |
71 } | 70 } |
72 | 71 |
73 static inline bool IsKeyEqual(Pair kv, Key key) { | 72 static inline bool IsKeyEqual(Pair kv, Key key) { |
74 return kv->value().raw() == key.raw(); | 73 return kv->value().raw() == key.raw(); |
75 } | 74 } |
76 }; | 75 }; |
77 | 76 |
78 | |
79 // Class to encapsulate the construction and manipulation of the flow graph. | 77 // Class to encapsulate the construction and manipulation of the flow graph. |
80 class FlowGraph : public ZoneAllocated { | 78 class FlowGraph : public ZoneAllocated { |
81 public: | 79 public: |
82 FlowGraph(const ParsedFunction& parsed_function, | 80 FlowGraph(const ParsedFunction& parsed_function, |
83 GraphEntryInstr* graph_entry, | 81 GraphEntryInstr* graph_entry, |
84 intptr_t max_block_id); | 82 intptr_t max_block_id); |
85 | 83 |
86 // Function properties. | 84 // Function properties. |
87 const ParsedFunction& parsed_function() const { return parsed_function_; } | 85 const ParsedFunction& parsed_function() const { return parsed_function_; } |
88 const Function& function() const { return parsed_function_.function(); } | 86 const Function& function() const { return parsed_function_.function(); } |
(...skipping 324 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
413 ZoneGrowableArray<BlockEntryInstr*>* loop_headers_; | 411 ZoneGrowableArray<BlockEntryInstr*>* loop_headers_; |
414 ZoneGrowableArray<BitVector*>* loop_invariant_loads_; | 412 ZoneGrowableArray<BitVector*>* loop_invariant_loads_; |
415 ZoneGrowableArray<const LibraryPrefix*>* deferred_prefixes_; | 413 ZoneGrowableArray<const LibraryPrefix*>* deferred_prefixes_; |
416 ZoneGrowableArray<TokenPosition>* await_token_positions_; | 414 ZoneGrowableArray<TokenPosition>* await_token_positions_; |
417 DirectChainedHashMap<ConstantPoolTrait> constant_instr_pool_; | 415 DirectChainedHashMap<ConstantPoolTrait> constant_instr_pool_; |
418 BitVector* captured_parameters_; | 416 BitVector* captured_parameters_; |
419 | 417 |
420 intptr_t inlining_id_; | 418 intptr_t inlining_id_; |
421 }; | 419 }; |
422 | 420 |
423 | |
424 class LivenessAnalysis : public ValueObject { | 421 class LivenessAnalysis : public ValueObject { |
425 public: | 422 public: |
426 LivenessAnalysis(intptr_t variable_count, | 423 LivenessAnalysis(intptr_t variable_count, |
427 const GrowableArray<BlockEntryInstr*>& postorder); | 424 const GrowableArray<BlockEntryInstr*>& postorder); |
428 | 425 |
429 void Analyze(); | 426 void Analyze(); |
430 | 427 |
431 virtual ~LivenessAnalysis() {} | 428 virtual ~LivenessAnalysis() {} |
432 | 429 |
433 BitVector* GetLiveInSetAt(intptr_t postorder_number) const { | 430 BitVector* GetLiveInSetAt(intptr_t postorder_number) const { |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
488 | 485 |
489 // Kill sets for each block. They contain indices of variables that | 486 // Kill sets for each block. They contain indices of variables that |
490 // are defined by this block. | 487 // are defined by this block. |
491 GrowableArray<BitVector*> kill_; | 488 GrowableArray<BitVector*> kill_; |
492 | 489 |
493 // Live-in sets for each block. They contain indices of variables | 490 // Live-in sets for each block. They contain indices of variables |
494 // that are used by this block or its successors. | 491 // that are used by this block or its successors. |
495 GrowableArray<BitVector*> live_in_; | 492 GrowableArray<BitVector*> live_in_; |
496 }; | 493 }; |
497 | 494 |
498 | |
499 // Information about side effect free paths between blocks. | 495 // Information about side effect free paths between blocks. |
500 class BlockEffects : public ZoneAllocated { | 496 class BlockEffects : public ZoneAllocated { |
501 public: | 497 public: |
502 explicit BlockEffects(FlowGraph* flow_graph); | 498 explicit BlockEffects(FlowGraph* flow_graph); |
503 | 499 |
504 // Return true if the given instruction is not affected by anything between | 500 // Return true if the given instruction is not affected by anything between |
505 // its current block and target block. Used by CSE to determine if | 501 // its current block and target block. Used by CSE to determine if |
506 // a computation is available in the given block. | 502 // a computation is available in the given block. |
507 bool IsAvailableAt(Instruction* instr, BlockEntryInstr* block) const; | 503 bool IsAvailableAt(Instruction* instr, BlockEntryInstr* block) const; |
508 | 504 |
509 // Return true if the given instruction is not affected by anything between | 505 // Return true if the given instruction is not affected by anything between |
510 // the given block and its current block. Used by LICM to determine if | 506 // the given block and its current block. Used by LICM to determine if |
511 // a computation can be moved to loop's preheader and remain available at | 507 // a computation can be moved to loop's preheader and remain available at |
512 // its current location. | 508 // its current location. |
513 bool CanBeMovedTo(Instruction* instr, BlockEntryInstr* block) const; | 509 bool CanBeMovedTo(Instruction* instr, BlockEntryInstr* block) const; |
514 | 510 |
515 private: | 511 private: |
516 // Returns true if from dominates to and all paths between from and to are | 512 // Returns true if from dominates to and all paths between from and to are |
517 // free of side effects. | 513 // free of side effects. |
518 bool IsSideEffectFreePath(BlockEntryInstr* from, BlockEntryInstr* to) const; | 514 bool IsSideEffectFreePath(BlockEntryInstr* from, BlockEntryInstr* to) const; |
519 | 515 |
520 // Per block sets of available blocks. Block A is available at the block B if | 516 // Per block sets of available blocks. Block A is available at the block B if |
521 // and only if A dominates B and all paths from A to B are free of side | 517 // and only if A dominates B and all paths from A to B are free of side |
522 // effects. | 518 // effects. |
523 GrowableArray<BitVector*> available_at_; | 519 GrowableArray<BitVector*> available_at_; |
524 }; | 520 }; |
525 | 521 |
526 | |
527 class DefinitionWorklist : public ValueObject { | 522 class DefinitionWorklist : public ValueObject { |
528 public: | 523 public: |
529 DefinitionWorklist(FlowGraph* flow_graph, intptr_t initial_capacity) | 524 DefinitionWorklist(FlowGraph* flow_graph, intptr_t initial_capacity) |
530 : defs_(initial_capacity), | 525 : defs_(initial_capacity), |
531 contains_vector_(new BitVector(flow_graph->zone(), | 526 contains_vector_(new BitVector(flow_graph->zone(), |
532 flow_graph->current_ssa_temp_index())) {} | 527 flow_graph->current_ssa_temp_index())) {} |
533 | 528 |
534 void Add(Definition* defn) { | 529 void Add(Definition* defn) { |
535 if (!Contains(defn)) { | 530 if (!Contains(defn)) { |
536 defs_.Add(defn); | 531 defs_.Add(defn); |
(...skipping 20 matching lines...) Expand all Loading... |
557 void Clear() { | 552 void Clear() { |
558 defs_.TruncateTo(0); | 553 defs_.TruncateTo(0); |
559 contains_vector_->Clear(); | 554 contains_vector_->Clear(); |
560 } | 555 } |
561 | 556 |
562 private: | 557 private: |
563 GrowableArray<Definition*> defs_; | 558 GrowableArray<Definition*> defs_; |
564 BitVector* contains_vector_; | 559 BitVector* contains_vector_; |
565 }; | 560 }; |
566 | 561 |
567 | |
568 } // namespace dart | 562 } // namespace dart |
569 | 563 |
570 #endif // RUNTIME_VM_FLOW_GRAPH_H_ | 564 #endif // RUNTIME_VM_FLOW_GRAPH_H_ |
OLD | NEW |