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" |
11 #include "vm/intermediate_language.h" | 11 #include "vm/intermediate_language.h" |
12 #include "vm/parser.h" | 12 #include "vm/parser.h" |
13 #include "vm/thread.h" | 13 #include "vm/thread.h" |
14 | 14 |
15 namespace dart { | 15 namespace dart { |
16 | 16 |
17 class BlockEffects; | |
18 class FlowGraphBuilder; | 17 class FlowGraphBuilder; |
19 class ValueInliningContext; | 18 class ValueInliningContext; |
20 class VariableLivenessAnalysis; | 19 class VariableLivenessAnalysis; |
21 | 20 |
22 class BlockIterator : public ValueObject { | 21 class BlockIterator : public ValueObject { |
23 public: | 22 public: |
24 explicit BlockIterator(const GrowableArray<BlockEntryInstr*>& block_order) | 23 explicit BlockIterator(const GrowableArray<BlockEntryInstr*>& block_order) |
25 : block_order_(block_order), current_(0) {} | 24 : block_order_(block_order), current_(0) {} |
26 | 25 |
27 BlockIterator(const BlockIterator& other) | 26 BlockIterator(const BlockIterator& other) |
(...skipping 173 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
201 ZoneGrowableArray<Definition*>* inlining_parameters); | 200 ZoneGrowableArray<Definition*>* inlining_parameters); |
202 | 201 |
203 // Verification methods for debugging. | 202 // Verification methods for debugging. |
204 bool VerifyUseLists(); | 203 bool VerifyUseLists(); |
205 bool VerifyRedefinitions(); | 204 bool VerifyRedefinitions(); |
206 | 205 |
207 void DiscoverBlocks(); | 206 void DiscoverBlocks(); |
208 | 207 |
209 void MergeBlocks(); | 208 void MergeBlocks(); |
210 | 209 |
211 // Compute information about effects occurring in different blocks and | |
212 // discover side-effect free paths. | |
213 void ComputeBlockEffects(); | |
214 BlockEffects* block_effects() const { return block_effects_; } | |
215 | |
216 // Insert a redefinition of an original definition after prev and rename all | 210 // Insert a redefinition of an original definition after prev and rename all |
217 // dominated uses of the original. If an equivalent redefinition is already | 211 // dominated uses of the original. If an equivalent redefinition is already |
218 // present, nothing is inserted. | 212 // present, nothing is inserted. |
219 // Returns the redefinition, if a redefinition was inserted, NULL otherwise. | 213 // Returns the redefinition, if a redefinition was inserted, NULL otherwise. |
220 RedefinitionInstr* EnsureRedefinition(Instruction* prev, | 214 RedefinitionInstr* EnsureRedefinition(Instruction* prev, |
221 Definition* original, | 215 Definition* original, |
222 CompileType compile_type); | 216 CompileType compile_type); |
223 | 217 |
224 // Remove the redefinition instructions inserted to inhibit code motion. | 218 // Remove the redefinition instructions inserted to inhibit code motion. |
225 void RemoveRedefinitions(); | 219 void RemoveRedefinitions(); |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
398 const intptr_t num_non_copied_params_; | 392 const intptr_t num_non_copied_params_; |
399 GraphEntryInstr* graph_entry_; | 393 GraphEntryInstr* graph_entry_; |
400 GrowableArray<BlockEntryInstr*> preorder_; | 394 GrowableArray<BlockEntryInstr*> preorder_; |
401 GrowableArray<BlockEntryInstr*> postorder_; | 395 GrowableArray<BlockEntryInstr*> postorder_; |
402 GrowableArray<BlockEntryInstr*> reverse_postorder_; | 396 GrowableArray<BlockEntryInstr*> reverse_postorder_; |
403 GrowableArray<BlockEntryInstr*> optimized_block_order_; | 397 GrowableArray<BlockEntryInstr*> optimized_block_order_; |
404 ConstantInstr* constant_null_; | 398 ConstantInstr* constant_null_; |
405 ConstantInstr* constant_dead_; | 399 ConstantInstr* constant_dead_; |
406 ConstantInstr* constant_empty_context_; | 400 ConstantInstr* constant_empty_context_; |
407 | 401 |
408 BlockEffects* block_effects_; | |
409 bool licm_allowed_; | 402 bool licm_allowed_; |
410 | 403 |
411 ZoneGrowableArray<BlockEntryInstr*>* loop_headers_; | 404 ZoneGrowableArray<BlockEntryInstr*>* loop_headers_; |
412 ZoneGrowableArray<BitVector*>* loop_invariant_loads_; | 405 ZoneGrowableArray<BitVector*>* loop_invariant_loads_; |
413 ZoneGrowableArray<const LibraryPrefix*>* deferred_prefixes_; | 406 ZoneGrowableArray<const LibraryPrefix*>* deferred_prefixes_; |
414 ZoneGrowableArray<TokenPosition>* await_token_positions_; | 407 ZoneGrowableArray<TokenPosition>* await_token_positions_; |
415 DirectChainedHashMap<ConstantPoolTrait> constant_instr_pool_; | 408 DirectChainedHashMap<ConstantPoolTrait> constant_instr_pool_; |
416 BitVector* captured_parameters_; | 409 BitVector* captured_parameters_; |
417 | 410 |
418 intptr_t inlining_id_; | 411 intptr_t inlining_id_; |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
485 | 478 |
486 // Kill sets for each block. They contain indices of variables that | 479 // Kill sets for each block. They contain indices of variables that |
487 // are defined by this block. | 480 // are defined by this block. |
488 GrowableArray<BitVector*> kill_; | 481 GrowableArray<BitVector*> kill_; |
489 | 482 |
490 // Live-in sets for each block. They contain indices of variables | 483 // Live-in sets for each block. They contain indices of variables |
491 // that are used by this block or its successors. | 484 // that are used by this block or its successors. |
492 GrowableArray<BitVector*> live_in_; | 485 GrowableArray<BitVector*> live_in_; |
493 }; | 486 }; |
494 | 487 |
495 // Information about side effect free paths between blocks. | |
496 class BlockEffects : public ZoneAllocated { | |
497 public: | |
498 explicit BlockEffects(FlowGraph* flow_graph); | |
499 | |
500 // Return true if the given instruction is not affected by anything between | |
501 // its current block and target block. Used by CSE to determine if | |
502 // a computation is available in the given block. | |
503 bool IsAvailableAt(Instruction* instr, BlockEntryInstr* block) const; | |
504 | |
505 // Return true if the given instruction is not affected by anything between | |
506 // the given block and its current block. Used by LICM to determine if | |
507 // a computation can be moved to loop's preheader and remain available at | |
508 // its current location. | |
509 bool CanBeMovedTo(Instruction* instr, BlockEntryInstr* block) const; | |
510 | |
511 private: | |
512 // Returns true if from dominates to and all paths between from and to are | |
513 // free of side effects. | |
514 bool IsSideEffectFreePath(BlockEntryInstr* from, BlockEntryInstr* to) const; | |
515 | |
516 // Per block sets of available blocks. Block A is available at the block B if | |
517 // and only if A dominates B and all paths from A to B are free of side | |
518 // effects. | |
519 GrowableArray<BitVector*> available_at_; | |
520 }; | |
521 | |
522 class DefinitionWorklist : public ValueObject { | 488 class DefinitionWorklist : public ValueObject { |
523 public: | 489 public: |
524 DefinitionWorklist(FlowGraph* flow_graph, intptr_t initial_capacity) | 490 DefinitionWorklist(FlowGraph* flow_graph, intptr_t initial_capacity) |
525 : defs_(initial_capacity), | 491 : defs_(initial_capacity), |
526 contains_vector_(new BitVector(flow_graph->zone(), | 492 contains_vector_(new BitVector(flow_graph->zone(), |
527 flow_graph->current_ssa_temp_index())) {} | 493 flow_graph->current_ssa_temp_index())) {} |
528 | 494 |
529 void Add(Definition* defn) { | 495 void Add(Definition* defn) { |
530 if (!Contains(defn)) { | 496 if (!Contains(defn)) { |
531 defs_.Add(defn); | 497 defs_.Add(defn); |
(...skipping 23 matching lines...) Expand all Loading... |
555 } | 521 } |
556 | 522 |
557 private: | 523 private: |
558 GrowableArray<Definition*> defs_; | 524 GrowableArray<Definition*> defs_; |
559 BitVector* contains_vector_; | 525 BitVector* contains_vector_; |
560 }; | 526 }; |
561 | 527 |
562 } // namespace dart | 528 } // namespace dart |
563 | 529 |
564 #endif // RUNTIME_VM_FLOW_GRAPH_H_ | 530 #endif // RUNTIME_VM_FLOW_GRAPH_H_ |
OLD | NEW |