Plug code generator into liveness analysis.
Also implement spill slot support.
Change-Id: If5e28811e9fbbf3842a258772c633318a2f4fafc
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 733535e..7903ad6 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -21,6 +21,8 @@
namespace art {
+class CodeGenerator;
+
class BlockInfo : public ArenaObject {
public:
BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
@@ -87,9 +89,17 @@
*/
class UsePosition : public ArenaObject {
public:
- UsePosition(HInstruction* user, size_t position, UsePosition* next)
- : user_(user), position_(position), next_(next) {
- DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition());
+ UsePosition(HInstruction* user,
+ size_t input_index,
+ bool is_environment,
+ size_t position,
+ UsePosition* next)
+ : user_(user),
+ input_index_(input_index),
+ is_environment_(is_environment),
+ position_(position),
+ next_(next) {
+ DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1);
DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
}
@@ -99,12 +109,18 @@
HInstruction* GetUser() const { return user_; }
+ bool GetIsEnvironment() const { return is_environment_; }
+
+ size_t GetInputIndex() const { return input_index_; }
+
void Dump(std::ostream& stream) const {
stream << position_;
}
private:
HInstruction* const user_;
+ const size_t input_index_;
+ const bool is_environment_;
const size_t position_;
UsePosition* const next_;
@@ -117,17 +133,33 @@
*/
class LiveInterval : public ArenaObject {
public:
- LiveInterval(ArenaAllocator* allocator, Primitive::Type type)
+ LiveInterval(ArenaAllocator* allocator, Primitive::Type type, HInstruction* defined_by = nullptr)
: allocator_(allocator),
first_range_(nullptr),
last_range_(nullptr),
first_use_(nullptr),
type_(type),
next_sibling_(nullptr),
- register_(kNoRegister) {}
+ parent_(this),
+ register_(kNoRegister),
+ spill_slot_(kNoSpillSlot),
+ is_fixed_(false),
+ defined_by_(defined_by) {}
- void AddUse(HInstruction* instruction) {
- size_t position = instruction->GetLifetimePosition();
+ static LiveInterval* MakeFixedInterval(ArenaAllocator* allocator, int reg, Primitive::Type type) {
+ LiveInterval* interval = new (allocator) LiveInterval(allocator, type);
+ interval->SetRegister(reg);
+ interval->is_fixed_ = true;
+ return interval;
+ }
+
+ bool IsFixed() const { return is_fixed_; }
+
+ void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
+ // Set the use within the instruction.
+ // TODO: Use the instruction's location to know whether the instruction can die
+ // at entry, or needs to say alive within the user.
+ size_t position = instruction->GetLifetimePosition() + 1;
size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
if (first_range_ == nullptr) {
@@ -143,12 +175,14 @@
// There is a hole in the interval. Create a new range.
first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_);
}
- first_use_ = new (allocator_) UsePosition(instruction, position, first_use_);
+ first_use_ = new (allocator_) UsePosition(
+ instruction, input_index, is_environment, position, first_use_);
}
- void AddPhiUse(HInstruction* instruction, HBasicBlock* block) {
+ void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
DCHECK(instruction->AsPhi() != nullptr);
- first_use_ = new (allocator_) UsePosition(instruction, block->GetLifetimeEnd(), first_use_);
+ first_use_ = new (allocator_) UsePosition(
+ instruction, input_index, false, block->GetLifetimeEnd(), first_use_);
}
void AddRange(size_t start, size_t end) {
@@ -178,11 +212,23 @@
}
}
+ bool HasSpillSlot() const { return spill_slot_ != kNoSpillSlot; }
+ void SetSpillSlot(int slot) { spill_slot_ = slot; }
+ int GetSpillSlot() const { return spill_slot_; }
+
void SetFrom(size_t from) {
- DCHECK(first_range_ != nullptr);
- first_range_->start_ = from;
+ if (first_range_ != nullptr) {
+ first_range_->start_ = from;
+ } else {
+ // Instruction without uses.
+ DCHECK(!defined_by_->HasUses());
+ DCHECK(from == defined_by_->GetLifetimePosition());
+ first_range_ = last_range_ = new (allocator_) LiveRange(from, from + 2, nullptr);
+ }
}
+ LiveInterval* GetParent() const { return parent_; }
+
LiveRange* GetFirstRange() const { return first_range_; }
int GetRegister() const { return register_; }
@@ -190,11 +236,11 @@
void ClearRegister() { register_ = kNoRegister; }
bool HasRegister() const { return register_ != kNoRegister; }
- bool IsDeadAt(size_t position) {
+ bool IsDeadAt(size_t position) const {
return last_range_->GetEnd() <= position;
}
- bool Covers(size_t position) {
+ bool Covers(size_t position) const {
LiveRange* current = first_range_;
while (current != nullptr) {
if (position >= current->GetStart() && position < current->GetEnd()) {
@@ -208,27 +254,10 @@
/**
* Returns the first intersection of this interval with `other`.
*/
- size_t FirstIntersectionWith(LiveInterval* other) {
- // We only call this method if there is a lifetime hole in this interval
- // at the start of `other`.
- DCHECK(!Covers(other->GetStart()));
- DCHECK_LE(GetStart(), other->GetStart());
- // Move to the range in this interval that starts after the other interval.
- size_t other_start = other->GetStart();
- LiveRange* my_range = first_range_;
- while (my_range != nullptr) {
- if (my_range->GetStart() >= other_start) {
- break;
- } else {
- my_range = my_range->GetNext();
- }
- }
- if (my_range == nullptr) {
- return kNoLifetime;
- }
-
+ size_t FirstIntersectionWith(LiveInterval* other) const {
// Advance both intervals and find the first matching range start in
// this interval.
+ LiveRange* my_range = first_range_;
LiveRange* other_range = other->first_range_;
do {
if (my_range->IntersectsWith(*other_range)) {
@@ -252,16 +281,33 @@
return first_range_->GetStart();
}
+ size_t GetEnd() const {
+ return last_range_->GetEnd();
+ }
+
size_t FirstRegisterUseAfter(size_t position) const {
+ if (position == GetStart() && defined_by_ != nullptr) {
+ Location location = defined_by_->GetLocations()->Out();
+ // This interval is the first interval of the instruction. If the output
+ // of the instruction requires a register, we return the position of that instruction
+ // as the first register use.
+ if (location.IsUnallocated()) {
+ if ((location.GetPolicy() == Location::kRequiresRegister)
+ || (location.GetPolicy() == Location::kSameAsFirstInput
+ && defined_by_->GetLocations()->InAt(0).GetPolicy() == Location::kRequiresRegister)) {
+ return position;
+ }
+ }
+ }
+
UsePosition* use = first_use_;
while (use != nullptr) {
size_t use_position = use->GetPosition();
- // TODO: Once we plug the Locations builder of the code generator
- // to the register allocator, this method must be adjusted. We
- // test if there is an environment, because these are currently the only
- // instructions that could have more uses than the number of registers.
- if (use_position >= position && !use->GetUser()->NeedsEnvironment()) {
- return use_position;
+ if (use_position >= position && !use->GetIsEnvironment()) {
+ Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
+ if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) {
+ return use_position;
+ }
}
use = use->GetNext();
}
@@ -272,10 +318,18 @@
return FirstRegisterUseAfter(GetStart());
}
+ UsePosition* GetFirstUse() const {
+ return first_use_;
+ }
+
Primitive::Type GetType() const {
return type_;
}
+ HInstruction* GetDefinedBy() const {
+ return defined_by_;
+ }
+
/**
* Split this interval at `position`. This interval is changed to:
* [start ... position).
@@ -284,7 +338,7 @@
* [position ... end)
*/
LiveInterval* SplitAt(size_t position) {
- DCHECK(next_sibling_ == nullptr);
+ DCHECK(!is_fixed_);
DCHECK_GT(position, GetStart());
if (last_range_->GetEnd() <= position) {
@@ -293,7 +347,9 @@
}
LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_);
+ new_interval->next_sibling_ = next_sibling_;
next_sibling_ = new_interval;
+ new_interval->parent_ = parent_;
new_interval->first_use_ = first_use_;
LiveRange* current = first_range_;
@@ -383,21 +439,36 @@
// Live interval that is the result of a split.
LiveInterval* next_sibling_;
+ // The first interval from which split intervals come from.
+ LiveInterval* parent_;
+
// The register allocated to this interval.
int register_;
+ // The spill slot allocated to this interval.
+ int spill_slot_;
+
+ // Whether the interval is for a fixed register.
+ bool is_fixed_;
+
+ // The instruction represented by this interval.
+ HInstruction* const defined_by_;
+
static constexpr int kNoRegister = -1;
+ static constexpr int kNoSpillSlot = -1;
DISALLOW_COPY_AND_ASSIGN(LiveInterval);
};
class SsaLivenessAnalysis : public ValueObject {
public:
- explicit SsaLivenessAnalysis(const HGraph& graph)
+ SsaLivenessAnalysis(const HGraph& graph, CodeGenerator* codegen)
: graph_(graph),
+ codegen_(codegen),
linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
instructions_from_ssa_index_(graph.GetArena(), 0),
+ instructions_from_lifetime_position_(graph.GetArena(), 0),
number_of_ssa_values_(0) {
block_infos_.SetSize(graph.GetBlocks().Size());
}
@@ -424,6 +495,14 @@
return instructions_from_ssa_index_.Get(index);
}
+ HInstruction* GetInstructionFromPosition(size_t index) const {
+ return instructions_from_lifetime_position_.Get(index);
+ }
+
+ size_t GetMaxLifetimePosition() const {
+ return instructions_from_lifetime_position_.Size() * 2 - 1;
+ }
+
size_t GetNumberOfSsaValues() const {
return number_of_ssa_values_;
}
@@ -458,14 +537,52 @@
bool UpdateLiveOut(const HBasicBlock& block);
const HGraph& graph_;
+ CodeGenerator* const codegen_;
GrowableArray<HBasicBlock*> linear_post_order_;
GrowableArray<BlockInfo*> block_infos_;
+
+ // Temporary array used when computing live_in, live_out, and kill sets.
GrowableArray<HInstruction*> instructions_from_ssa_index_;
+
+ // Temporary array used when inserting moves in the graph.
+ GrowableArray<HInstruction*> instructions_from_lifetime_position_;
size_t number_of_ssa_values_;
DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};
+class HLinearOrderIterator : public ValueObject {
+ public:
+ explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
+ : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().Size()) {}
+
+ bool Done() const { return index_ == 0; }
+ HBasicBlock* Current() const { return post_order_.Get(index_ -1); }
+ void Advance() { --index_; DCHECK_GE(index_, 0U); }
+
+ private:
+ const GrowableArray<HBasicBlock*>& post_order_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+};
+
+class HLinearPostOrderIterator : public ValueObject {
+ public:
+ explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness)
+ : post_order_(liveness.GetLinearPostOrder()), index_(0) {}
+
+ bool Done() const { return index_ == post_order_.Size(); }
+ HBasicBlock* Current() const { return post_order_.Get(index_); }
+ void Advance() { ++index_; }
+
+ private:
+ const GrowableArray<HBasicBlock*>& post_order_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_