diff options
Diffstat (limited to 'compiler/optimizing/ssa_liveness_analysis.h')
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 110 |
1 files changed, 104 insertions, 6 deletions
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index b8695ba..2d91436 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -44,12 +44,104 @@ class BlockInfo : public ArenaObject { DISALLOW_COPY_AND_ASSIGN(BlockInfo); }; +/** + * A live range contains the start and end of a range where an instruction + * is live. + */ +class LiveRange : public ValueObject { + public: + LiveRange(size_t start, size_t end) : start_(start), end_(end) { + DCHECK_LT(start, end); + } + + size_t GetStart() const { return start_; } + size_t GetEnd() const { return end_; } + + private: + size_t start_; + size_t end_; +}; + +static constexpr int kDefaultNumberOfRanges = 3; + +/** + * An interval is a list of disjoint live ranges where an instruction is live. + * Each instruction that has uses gets an interval. + */ +class LiveInterval : public ArenaObject { + public: + explicit LiveInterval(ArenaAllocator* allocator) : ranges_(allocator, kDefaultNumberOfRanges) {} + + void AddUse(HInstruction* instruction) { + size_t position = instruction->GetLifetimePosition(); + size_t start_block_position = instruction->GetBlock()->GetLifetimeStart(); + size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd(); + if (ranges_.IsEmpty()) { + // First time we see a use of that interval. + ranges_.Add(LiveRange(start_block_position, position)); + } else if (ranges_.Peek().GetStart() == start_block_position) { + // There is a use later in the same block. + DCHECK_LE(position, ranges_.Peek().GetEnd()); + } else if (ranges_.Peek().GetStart() == end_block_position + 1) { + // Last use is in a following block. + LiveRange existing = ranges_.Pop(); + ranges_.Add(LiveRange(start_block_position, existing.GetEnd())); + } else { + // There is a hole in the interval. Create a new range. + ranges_.Add(LiveRange(start_block_position, position)); + } + } + + void AddRange(size_t start, size_t end) { + if (ranges_.IsEmpty()) { + ranges_.Add(LiveRange(start, end)); + } else if (ranges_.Peek().GetStart() == end + 1) { + // There is a use in the following block. + LiveRange existing = ranges_.Pop(); + ranges_.Add(LiveRange(start, existing.GetEnd())); + } else { + // There is a hole in the interval. Create a new range. + ranges_.Add(LiveRange(start, end)); + } + } + + void AddLoopRange(size_t start, size_t end) { + DCHECK(!ranges_.IsEmpty()); + while (!ranges_.IsEmpty() && ranges_.Peek().GetEnd() < end) { + DCHECK_LE(start, ranges_.Peek().GetStart()); + ranges_.Pop(); + } + if (ranges_.IsEmpty()) { + // Uses are only in the loop. + ranges_.Add(LiveRange(start, end)); + } else { + // There are uses after the loop. + LiveRange range = ranges_.Pop(); + ranges_.Add(LiveRange(start, range.GetEnd())); + } + } + + void SetFrom(size_t from) { + DCHECK(!ranges_.IsEmpty()); + LiveRange existing = ranges_.Pop(); + ranges_.Add(LiveRange(from, existing.GetEnd())); + } + + const GrowableArray<LiveRange>& GetRanges() const { return ranges_; } + + private: + GrowableArray<LiveRange> ranges_; + + DISALLOW_COPY_AND_ASSIGN(LiveInterval); +}; + class SsaLivenessAnalysis : public ValueObject { public: explicit SsaLivenessAnalysis(const HGraph& graph) : graph_(graph), linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()), block_infos_(graph.GetArena(), graph.GetBlocks().Size()), + instructions_from_ssa_index_(graph.GetArena(), 0), number_of_ssa_values_(0) { block_infos_.SetSize(graph.GetBlocks().Size()); } @@ -72,6 +164,10 @@ class SsaLivenessAnalysis : public ValueObject { return linear_post_order_; } + HInstruction* GetInstructionFromSsaIndex(size_t index) { + return instructions_from_ssa_index_.Get(index); + } + private: // Linearize the graph so that: // (1): a block is always after its dominator, @@ -79,15 +175,16 @@ class SsaLivenessAnalysis : public ValueObject { // This creates a natural and efficient ordering when visualizing live ranges. void LinearizeGraph(); - // Give an SSA number to each instruction that defines a value used by another instruction. + // Give an SSA number to each instruction that defines a value used by another instruction, + // and setup the lifetime information of each instruction and block. void NumberInstructions(); - // Compute live_in, live_out and kill sets. - void ComputeSets(); + // Compute live ranges of instructions, as well as live_in, live_out and kill sets. + void ComputeLiveness(); - // Compute the initial live_in, live_out and kill sets, without analyzing - // backward branches. - void ComputeInitialSets(); + // Compute the live ranges of instructions, as well as the initial live_in, live_out and + // kill sets, that do not take into account backward branches. + void ComputeLiveRanges(); // After computing the initial sets, this method does a fixed point // calculation over the live_in and live_out set to take into account @@ -103,6 +200,7 @@ class SsaLivenessAnalysis : public ValueObject { const HGraph& graph_; GrowableArray<HBasicBlock*> linear_post_order_; GrowableArray<BlockInfo*> block_infos_; + GrowableArray<HInstruction*> instructions_from_ssa_index_; size_t number_of_ssa_values_; DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); |