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 VM_FLOW_GRAPH_H_ | 5 #ifndef VM_FLOW_GRAPH_H_ |
6 #define VM_FLOW_GRAPH_H_ | 6 #define 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 | 14 |
14 namespace dart { | 15 namespace dart { |
15 | 16 |
16 class BlockEffects; | 17 class BlockEffects; |
17 class FlowGraphBuilder; | 18 class FlowGraphBuilder; |
18 class ValueInliningContext; | 19 class ValueInliningContext; |
19 class VariableLivenessAnalysis; | 20 class VariableLivenessAnalysis; |
20 | 21 |
21 class BlockIterator : public ValueObject { | 22 class BlockIterator : public ValueObject { |
22 public: | 23 public: |
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
142 | 143 |
143 intptr_t current_ssa_temp_index() const { return current_ssa_temp_index_; } | 144 intptr_t current_ssa_temp_index() const { return current_ssa_temp_index_; } |
144 void set_current_ssa_temp_index(intptr_t index) { | 145 void set_current_ssa_temp_index(intptr_t index) { |
145 current_ssa_temp_index_ = index; | 146 current_ssa_temp_index_ = index; |
146 } | 147 } |
147 | 148 |
148 intptr_t max_virtual_register_number() const { | 149 intptr_t max_virtual_register_number() const { |
149 return current_ssa_temp_index(); | 150 return current_ssa_temp_index(); |
150 } | 151 } |
151 | 152 |
152 Isolate* isolate() const { return isolate_; } | 153 Thread* thread() const { return thread_; } |
| 154 Zone* zone() const { return thread()->zone(); } |
| 155 Isolate* isolate() const { return thread()->isolate(); } |
153 | 156 |
154 intptr_t max_block_id() const { return max_block_id_; } | 157 intptr_t max_block_id() const { return max_block_id_; } |
155 void set_max_block_id(intptr_t id) { max_block_id_ = id; } | 158 void set_max_block_id(intptr_t id) { max_block_id_ = id; } |
156 intptr_t allocate_block_id() { return ++max_block_id_; } | 159 intptr_t allocate_block_id() { return ++max_block_id_; } |
157 | 160 |
158 GraphEntryInstr* graph_entry() const { | 161 GraphEntryInstr* graph_entry() const { |
159 return graph_entry_; | 162 return graph_entry_; |
160 } | 163 } |
161 | 164 |
162 ConstantInstr* constant_null() const { | 165 ConstantInstr* constant_null() const { |
(...skipping 155 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
318 void ReplacePredecessor(BlockEntryInstr* old_block, | 321 void ReplacePredecessor(BlockEntryInstr* old_block, |
319 BlockEntryInstr* new_block); | 322 BlockEntryInstr* new_block); |
320 | 323 |
321 // Find the natural loop for the back edge m->n and attach loop | 324 // Find the natural loop for the back edge m->n and attach loop |
322 // information to block n (loop header). The algorithm is described in | 325 // information to block n (loop header). The algorithm is described in |
323 // "Advanced Compiler Design & Implementation" (Muchnick) p192. | 326 // "Advanced Compiler Design & Implementation" (Muchnick) p192. |
324 // Returns a BitVector indexed by block pre-order number where each bit | 327 // Returns a BitVector indexed by block pre-order number where each bit |
325 // indicates membership in the loop. | 328 // indicates membership in the loop. |
326 BitVector* FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const; | 329 BitVector* FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const; |
327 | 330 |
328 Isolate* isolate_; | 331 Thread* thread_; |
329 | 332 |
330 // DiscoverBlocks computes parent_ and assigned_vars_ which are then used | 333 // DiscoverBlocks computes parent_ and assigned_vars_ which are then used |
331 // if/when computing SSA. | 334 // if/when computing SSA. |
332 GrowableArray<intptr_t> parent_; | 335 GrowableArray<intptr_t> parent_; |
333 GrowableArray<BitVector*> assigned_vars_; | 336 GrowableArray<BitVector*> assigned_vars_; |
334 | 337 |
335 intptr_t current_ssa_temp_index_; | 338 intptr_t current_ssa_temp_index_; |
336 intptr_t max_block_id_; | 339 intptr_t max_block_id_; |
337 | 340 |
338 // Flow graph fields. | 341 // Flow graph fields. |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
404 // Update live-in set for the given block: live-in should contain | 407 // Update live-in set for the given block: live-in should contain |
405 // all values that are live-out from the block and are not defined | 408 // all values that are live-out from the block and are not defined |
406 // by this block. | 409 // by this block. |
407 // Returns true if live-in set was changed. | 410 // Returns true if live-in set was changed. |
408 bool UpdateLiveIn(const BlockEntryInstr& instr); | 411 bool UpdateLiveIn(const BlockEntryInstr& instr); |
409 | 412 |
410 // Perform fix-point iteration updating live-out and live-in sets | 413 // Perform fix-point iteration updating live-out and live-in sets |
411 // for blocks until they stop changing. | 414 // for blocks until they stop changing. |
412 void ComputeLiveInAndLiveOutSets(); | 415 void ComputeLiveInAndLiveOutSets(); |
413 | 416 |
414 Isolate* isolate() const { return isolate_; } | 417 Zone* zone() const { return zone_; } |
415 | 418 |
416 Isolate* isolate_; | 419 Zone* zone_; |
417 | 420 |
418 const intptr_t variable_count_; | 421 const intptr_t variable_count_; |
419 | 422 |
420 const GrowableArray<BlockEntryInstr*>& postorder_; | 423 const GrowableArray<BlockEntryInstr*>& postorder_; |
421 | 424 |
422 // Live-out sets for each block. They contain indices of variables | 425 // Live-out sets for each block. They contain indices of variables |
423 // that are live out from this block: that is values that were either | 426 // that are live out from this block: that is values that were either |
424 // defined in this block or live into it and that are used in some | 427 // defined in this block or live into it and that are used in some |
425 // successor block. | 428 // successor block. |
426 GrowableArray<BitVector*> live_out_; | 429 GrowableArray<BitVector*> live_out_; |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
462 GrowableArray<BitVector*> available_at_; | 465 GrowableArray<BitVector*> available_at_; |
463 }; | 466 }; |
464 | 467 |
465 | 468 |
466 class DefinitionWorklist : public ValueObject { | 469 class DefinitionWorklist : public ValueObject { |
467 public: | 470 public: |
468 DefinitionWorklist(FlowGraph* flow_graph, | 471 DefinitionWorklist(FlowGraph* flow_graph, |
469 intptr_t initial_capacity) | 472 intptr_t initial_capacity) |
470 : defs_(initial_capacity), | 473 : defs_(initial_capacity), |
471 contains_vector_( | 474 contains_vector_( |
472 new BitVector(flow_graph->isolate(), | 475 new BitVector(flow_graph->zone(), |
473 flow_graph->current_ssa_temp_index())) { | 476 flow_graph->current_ssa_temp_index())) { |
474 } | 477 } |
475 | 478 |
476 void Add(Definition* defn) { | 479 void Add(Definition* defn) { |
477 if (!Contains(defn)) { | 480 if (!Contains(defn)) { |
478 defs_.Add(defn); | 481 defs_.Add(defn); |
479 contains_vector_->Add(defn->ssa_temp_index()); | 482 contains_vector_->Add(defn->ssa_temp_index()); |
480 } | 483 } |
481 } | 484 } |
482 | 485 |
(...skipping 22 matching lines...) Expand all Loading... |
505 | 508 |
506 private: | 509 private: |
507 GrowableArray<Definition*> defs_; | 510 GrowableArray<Definition*> defs_; |
508 BitVector* contains_vector_; | 511 BitVector* contains_vector_; |
509 }; | 512 }; |
510 | 513 |
511 | 514 |
512 } // namespace dart | 515 } // namespace dart |
513 | 516 |
514 #endif // VM_FLOW_GRAPH_H_ | 517 #endif // VM_FLOW_GRAPH_H_ |
OLD | NEW |