Add a Transform to SSA phase to the optimizing compiler.
Change-Id: Ia9700756a0396d797a00b529896487d52c989329
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 3da9ed9..581c1d5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -24,9 +24,11 @@
namespace art {
class HBasicBlock;
+class HEnvironment;
class HInstruction;
class HIntConstant;
class HGraphVisitor;
+class HPhi;
class LocationSummary;
static const int kDefaultNumberOfBlocks = 8;
@@ -34,6 +36,23 @@
static const int kDefaultNumberOfPredecessors = 2;
static const int kDefaultNumberOfBackEdges = 1;
+class HInstructionList {
+ public:
+ HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
+
+ void AddInstruction(HInstruction* instruction);
+ void RemoveInstruction(HInstruction* instruction);
+
+ private:
+ HInstruction* first_instruction_;
+ HInstruction* last_instruction_;
+
+ friend class HBasicBlock;
+ friend class HInstructionIterator;
+
+ DISALLOW_COPY_AND_ASSIGN(HInstructionList);
+};
+
// Control-flow graph of a method. Contains a list of basic blocks.
class HGraph : public ArenaObject {
public:
@@ -56,7 +75,10 @@
void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
void AddBlock(HBasicBlock* block);
+
void BuildDominatorTree();
+ void TransformToSSA();
+ void SimplifyCFG();
int GetNextInstructionId() {
return current_instruction_id_++;
@@ -86,6 +108,9 @@
return number_of_in_vregs_;
}
+ GrowableArray<HBasicBlock*>* GetDominatorOrder() {
+ return &dominator_order_;
+ }
private:
HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -138,7 +163,18 @@
return back_edges_.Size();
}
+ void SetPreHeader(HBasicBlock* block);
+
+ HBasicBlock* GetPreHeader() const {
+ return pre_header_;
+ }
+
+ const GrowableArray<HBasicBlock*>* GetBackEdges() const {
+ return &back_edges_;
+ }
+
private:
+ HBasicBlock* pre_header_;
HBasicBlock* header_;
GrowableArray<HBasicBlock*> back_edges_;
@@ -154,8 +190,6 @@
: graph_(graph),
predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
- first_instruction_(nullptr),
- last_instruction_(nullptr),
loop_information_(nullptr),
dominator_(nullptr),
block_id_(-1) { }
@@ -189,26 +223,42 @@
: loop_information_->NumberOfBackEdges();
}
- HInstruction* GetFirstInstruction() const { return first_instruction_; }
- HInstruction* GetLastInstruction() const { return last_instruction_; }
+ HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
+ HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
+ HInstructionList const* GetInstructions() const { return &instructions_; }
+ HInstructionList const* GetPhis() const { return &phis_; }
void AddSuccessor(HBasicBlock* block) {
successors_.Add(block);
block->predecessors_.Add(this);
}
- void RemovePredecessor(HBasicBlock* block) {
+ void RemovePredecessor(HBasicBlock* block, bool remove_in_successor = true) {
predecessors_.Delete(block);
+ if (remove_in_successor) {
+ block->successors_.Delete(this);
+ }
}
void AddInstruction(HInstruction* instruction);
+ void RemoveInstruction(HInstruction* instruction);
+ void AddPhi(HPhi* phi);
+ void RemovePhi(HPhi* phi);
+
+ bool IsLoopHeader() const {
+ return loop_information_ != nullptr;
+ }
+
+ HLoopInformation* GetLoopInformation() const {
+ return loop_information_;
+ }
private:
HGraph* const graph_;
GrowableArray<HBasicBlock*> predecessors_;
GrowableArray<HBasicBlock*> successors_;
- HInstruction* first_instruction_;
- HInstruction* last_instruction_;
+ HInstructionList instructions_;
+ HInstructionList phis_;
HLoopInformation* loop_information_;
HBasicBlock* dominator_;
int block_id_;
@@ -230,6 +280,7 @@
M(NewInstance) \
M(Not) \
M(ParameterValue) \
+ M(Phi) \
M(Return) \
M(ReturnVoid) \
M(StoreLocal) \
@@ -244,17 +295,22 @@
virtual const char* DebugName() const { return #type; } \
virtual H##type* As##type() { return this; } \
+template <typename T>
class HUseListNode : public ArenaObject {
public:
- HUseListNode(HInstruction* instruction, HUseListNode* tail)
- : instruction_(instruction), tail_(tail) { }
+ HUseListNode(T* user, size_t index, HUseListNode* tail)
+ : user_(user), index_(index), tail_(tail) { }
HUseListNode* GetTail() const { return tail_; }
- HInstruction* GetInstruction() const { return instruction_; }
+ T* GetUser() const { return user_; }
+ size_t GetIndex() const { return index_; }
+
+ void SetTail(HUseListNode<T>* node) { tail_ = node; }
private:
- HInstruction* const instruction_;
- HUseListNode* const tail_;
+ T* const user_;
+ const size_t index_;
+ HUseListNode<T>* tail_;
DISALLOW_COPY_AND_ASSIGN(HUseListNode);
};
@@ -267,6 +323,8 @@
block_(nullptr),
id_(-1),
uses_(nullptr),
+ env_uses_(nullptr),
+ environment_(nullptr),
locations_(nullptr) { }
virtual ~HInstruction() { }
@@ -277,28 +335,43 @@
HBasicBlock* GetBlock() const { return block_; }
void SetBlock(HBasicBlock* block) { block_ = block; }
- virtual intptr_t InputCount() const = 0;
- virtual HInstruction* InputAt(intptr_t i) const = 0;
+ virtual size_t InputCount() const = 0;
+ virtual HInstruction* InputAt(size_t i) const = 0;
virtual void Accept(HGraphVisitor* visitor) = 0;
virtual const char* DebugName() const = 0;
virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
+ virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
- void AddUse(HInstruction* user) {
- uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, uses_);
+ virtual bool NeedsEnvironment() const { return false; }
+
+ void AddUseAt(HInstruction* user, size_t index) {
+ uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
}
- HUseListNode* GetUses() const { return uses_; }
+ void AddEnvUseAt(HEnvironment* user, size_t index) {
+ env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
+ user, index, env_uses_);
+ }
+
+ void RemoveUser(HInstruction* user, size_t index);
+
+ HUseListNode<HInstruction>* GetUses() const { return uses_; }
+ HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
bool HasUses() const { return uses_ != nullptr; }
int GetId() const { return id_; }
void SetId(int id) { id_ = id; }
+ void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
+
LocationSummary* GetLocations() const { return locations_; }
void SetLocations(LocationSummary* locations) { locations_ = locations; }
+ void ReplaceWith(HInstruction* instruction);
+
#define INSTRUCTION_TYPE_CHECK(type) \
virtual H##type* As##type() { return nullptr; }
@@ -315,19 +388,27 @@
// has not beed added to the graph.
int id_;
- HUseListNode* uses_;
+ // List of instructions that have this instruction as input.
+ HUseListNode<HInstruction>* uses_;
+
+ // List of environments that contain this instruction.
+ HUseListNode<HEnvironment>* env_uses_;
+
+ HEnvironment* environment_;
// Set by the code generator.
LocationSummary* locations_;
friend class HBasicBlock;
+ friend class HInstructionList;
DISALLOW_COPY_AND_ASSIGN(HInstruction);
};
+template<typename T>
class HUseIterator : public ValueObject {
public:
- explicit HUseIterator(HInstruction* instruction) : current_(instruction->GetUses()) { }
+ explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {}
bool Done() const { return current_ == nullptr; }
@@ -336,17 +417,51 @@
current_ = current_->GetTail();
}
- HInstruction* Current() const {
+ HUseListNode<T>* Current() const {
DCHECK(!Done());
- return current_->GetInstruction();
+ return current_;
}
private:
- HUseListNode* current_;
+ HUseListNode<T>* current_;
friend class HValue;
};
+// A HEnvironment object contains the values of virtual registers at a given location.
+class HEnvironment : public ArenaObject {
+ public:
+ HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) {
+ vregs_.SetSize(number_of_vregs);
+ for (size_t i = 0; i < number_of_vregs; i++) {
+ vregs_.Put(i, nullptr);
+ }
+ }
+
+ void Populate(const GrowableArray<HInstruction*>& env) {
+ for (size_t i = 0; i < env.Size(); i++) {
+ HInstruction* instruction = env.Get(i);
+ vregs_.Put(i, instruction);
+ if (instruction != nullptr) {
+ instruction->AddEnvUseAt(this, i);
+ }
+ }
+ }
+
+ void SetRawEnvAt(size_t index, HInstruction* instruction) {
+ vregs_.Put(index, instruction);
+ }
+
+ GrowableArray<HInstruction*>* GetVRegs() {
+ return &vregs_;
+ }
+
+ private:
+ GrowableArray<HInstruction*> vregs_;
+
+ DISALLOW_COPY_AND_ASSIGN(HEnvironment);
+};
+
class HInputIterator : public ValueObject {
public:
explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { }
@@ -357,15 +472,15 @@
private:
HInstruction* instruction_;
- int index_;
+ size_t index_;
DISALLOW_COPY_AND_ASSIGN(HInputIterator);
};
class HInstructionIterator : public ValueObject {
public:
- explicit HInstructionIterator(HBasicBlock* block)
- : instruction_(block->GetFirstInstruction()) {
+ explicit HInstructionIterator(const HInstructionList& instructions)
+ : instruction_(instructions.first_instruction_) {
next_ = Done() ? nullptr : instruction_->GetNext();
}
@@ -434,16 +549,18 @@
HTemplateInstruction<N>() : inputs_() { }
virtual ~HTemplateInstruction() { }
- virtual intptr_t InputCount() const { return N; }
- virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; }
+ virtual size_t InputCount() const { return N; }
+ virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
protected:
- void SetRawInputAt(intptr_t i, HInstruction* instruction) {
+ virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
inputs_[i] = instruction;
}
private:
EmbeddedArray<HInstruction*, N> inputs_;
+
+ friend class SsaBuilder;
};
// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
@@ -658,11 +775,19 @@
inputs_.SetSize(number_of_arguments);
}
- virtual intptr_t InputCount() const { return inputs_.Size(); }
- virtual HInstruction* InputAt(intptr_t i) const { return inputs_.Get(i); }
+ virtual size_t InputCount() const { return inputs_.Size(); }
+ virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+
+ // Runtime needs to walk the stack, so Dex -> Dex calls need to
+ // know their environment.
+ virtual bool NeedsEnvironment() const { return true; }
void SetArgumentAt(size_t index, HInstruction* argument) {
- inputs_.Put(index, argument);
+ SetRawInputAt(index, argument);
+ }
+
+ virtual void SetRawInputAt(size_t index, HInstruction* input) {
+ inputs_.Put(index, input);
}
virtual Primitive::Type GetType() const { return return_type_; }
@@ -707,6 +832,9 @@
virtual Primitive::Type GetType() const { return Primitive::kPrimNot; }
+ // Calls runtime so needs an environment.
+ virtual bool NeedsEnvironment() const { return true; }
+
DECLARE_INSTRUCTION(NewInstance)
private:
@@ -779,6 +907,39 @@
DISALLOW_COPY_AND_ASSIGN(HNot);
};
+class HPhi : public HInstruction {
+ public:
+ HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
+ : inputs_(arena, number_of_inputs),
+ reg_number_(reg_number),
+ type_(type) {
+ inputs_.SetSize(number_of_inputs);
+ }
+
+ virtual size_t InputCount() const { return inputs_.Size(); }
+ virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+
+ virtual void SetRawInputAt(size_t index, HInstruction* input) {
+ inputs_.Put(index, input);
+ }
+
+ void AddInput(HInstruction* input);
+
+ virtual Primitive::Type GetType() const { return type_; }
+
+ uint32_t GetRegNumber() const { return reg_number_; }
+
+ DECLARE_INSTRUCTION(Phi)
+
+ protected:
+ GrowableArray<HInstruction*> inputs_;
+ const uint32_t reg_number_;
+ const Primitive::Type type_;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HPhi);
+};
+
class HGraphVisitor : public ValueObject {
public:
explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }