| 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 |