Add a Transform to SSA phase to the optimizing compiler.
Change-Id: Ia9700756a0396d797a00b529896487d52c989329
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 4b655b5..ced7e36 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -76,6 +76,7 @@
compiler/optimizing/codegen_test.cc \
compiler/optimizing/dominator_test.cc \
compiler/optimizing/pretty_printer_test.cc \
+ compiler/optimizing/ssa_test.cc \
compiler/output_stream_test.cc \
compiler/utils/arena_allocator_test.cc \
compiler/utils/dedupe_set_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 6d656e6..e3201e7 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -78,6 +78,7 @@
optimizing/code_generator_x86.cc \
optimizing/nodes.cc \
optimizing/optimizing_compiler.cc \
+ optimizing/ssa_builder.cc \
trampolines/trampoline_compiler.cc \
utils/arena_allocator.cc \
utils/arena_bit_vector.cc \
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 7e63c69..babb1f5 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -47,7 +47,7 @@
Bind(GetLabelOf(block));
HGraphVisitor* location_builder = GetLocationBuilder();
HGraphVisitor* instruction_visitor = GetInstructionVisitor();
- for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
current->Accept(location_builder);
InitLocations(current);
@@ -57,7 +57,7 @@
void CodeGenerator::InitLocations(HInstruction* instruction) {
if (instruction->GetLocations() == nullptr) return;
- for (int i = 0; i < instruction->InputCount(); i++) {
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
Location location = instruction->GetLocations()->InAt(i);
if (location.IsValid()) {
// Move the input to the desired location.
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 5c7cac1..54f9e70 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -211,7 +211,7 @@
: inputs(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()),
temps(instruction->GetBlock()->GetGraph()->GetArena(), 0) {
inputs.SetSize(instruction->InputCount());
- for (int i = 0; i < instruction->InputCount(); i++) {
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
inputs.Put(i, Location());
}
}
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 27691ac..6e528f9 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -447,7 +447,7 @@
locations->AddTemp(ArmCoreLocation(R0));
InvokeDexCallingConventionVisitor calling_convention_visitor;
- for (int i = 0; i < invoke->InputCount(); i++) {
+ for (size_t i = 0; i < invoke->InputCount(); i++) {
HInstruction* input = invoke->InputAt(i);
locations->SetInAt(i, calling_convention_visitor.GetNextLocation(input->GetType()));
}
@@ -694,5 +694,13 @@
locations->InAt(0).AsArm().AsCoreRegister(), ShifterOperand(1));
}
+void LocationsBuilderARM::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
+}
+
+void InstructionCodeGeneratorARM::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
+}
+
} // namespace arm
} // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 1142631..dc10830 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -456,7 +456,7 @@
locations->AddTemp(X86CpuLocation(EAX));
InvokeDexCallingConventionVisitor calling_convention_visitor;
- for (int i = 0; i < invoke->InputCount(); i++) {
+ for (size_t i = 0; i < invoke->InputCount(); i++) {
HInstruction* input = invoke->InputAt(i);
locations->SetInAt(i, calling_convention_visitor.GetNextLocation(input->GetType()));
}
@@ -687,5 +687,13 @@
__ xorl(locations->Out().AsX86().AsCpuRegister(), Immediate(1));
}
+void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
+}
+
+void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
+}
+
} // namespace x86
} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 498deba..3d6aeb7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -15,6 +15,7 @@
*/
#include "nodes.h"
+#include "ssa_builder.h"
#include "utils/growable_array.h"
namespace art {
@@ -34,7 +35,13 @@
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_.Get(i);
for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
- block->GetSuccessors()->Get(j)->RemovePredecessor(block);
+ block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+ }
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ block->RemovePhi(it.Current()->AsPhi());
+ }
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+ block->RemoveInstruction(it.Current());
}
}
}
@@ -120,11 +127,112 @@
}
}
-void HBasicBlock::AddInstruction(HInstruction* instruction) {
+void HGraph::TransformToSSA() {
+ DCHECK(!dominator_order_.IsEmpty());
+ SimplifyCFG();
+ SsaBuilder ssa_builder(this);
+ ssa_builder.BuildSsa();
+}
+
+void HGraph::SimplifyCFG() {
+ for (size_t i = 0; i < dominator_order_.Size(); i++) {
+ HBasicBlock* current = dominator_order_.Get(i);
+ if (current->IsLoopHeader()) {
+ // Make sure the loop has only one pre header. This simplifies SSA building by having
+ // to just look at the pre header to know which locals are initialized at entry of the
+ // loop.
+ HLoopInformation* info = current->GetLoopInformation();
+ size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
+ if (number_of_incomings != 1) {
+ HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+ AddBlock(pre_header);
+ pre_header->AddInstruction(new (arena_) HGoto());
+ pre_header->SetDominator(current->GetDominator());
+ current->SetDominator(pre_header);
+ dominator_order_.InsertAt(i, pre_header);
+ i++;
+
+ ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false);
+ for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
+ back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
+ }
+ for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
+ HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
+ if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
+ current->RemovePredecessor(predecessor);
+ pred--;
+ predecessor->AddSuccessor(pre_header);
+ }
+ }
+ pre_header->AddSuccessor(current);
+ }
+ info->SetPreHeader(current->GetDominator());
+ }
+ }
+}
+
+void HLoopInformation::SetPreHeader(HBasicBlock* block) {
+ DCHECK_EQ(header_->GetDominator(), block);
+ pre_header_ = block;
+}
+
+static void Add(HInstructionList* instruction_list,
+ HBasicBlock* block,
+ HInstruction* instruction) {
DCHECK(instruction->GetBlock() == nullptr);
DCHECK_EQ(instruction->GetId(), -1);
- instruction->SetBlock(this);
- instruction->SetId(GetGraph()->GetNextInstructionId());
+ instruction->SetBlock(block);
+ instruction->SetId(block->GetGraph()->GetNextInstructionId());
+ instruction_list->AddInstruction(instruction);
+}
+
+void HBasicBlock::AddInstruction(HInstruction* instruction) {
+ Add(&instructions_, this, instruction);
+}
+
+void HBasicBlock::AddPhi(HPhi* phi) {
+ Add(&phis_, this, phi);
+}
+
+static void Remove(HInstructionList* instruction_list,
+ HBasicBlock* block,
+ HInstruction* instruction) {
+ DCHECK_EQ(block, instruction->GetBlock());
+ DCHECK(instruction->GetUses() == nullptr);
+ DCHECK(instruction->GetEnvUses() == nullptr);
+ instruction->SetBlock(nullptr);
+ instruction_list->RemoveInstruction(instruction);
+
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
+ instruction->InputAt(i)->RemoveUser(instruction, i);
+ }
+}
+
+void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
+ Remove(&instructions_, this, instruction);
+}
+
+void HBasicBlock::RemovePhi(HPhi* phi) {
+ Remove(&phis_, this, phi);
+}
+
+void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
+ HUseListNode<HInstruction>* previous = nullptr;
+ HUseListNode<HInstruction>* current = uses_;
+ while (current != nullptr) {
+ if (current->GetUser() == user && current->GetIndex() == input_index) {
+ if (previous == NULL) {
+ uses_ = current->GetTail();
+ } else {
+ previous->SetTail(current->GetTail());
+ }
+ }
+ previous = current;
+ current = current->GetTail();
+ }
+}
+
+void HInstructionList::AddInstruction(HInstruction* instruction) {
if (first_instruction_ == nullptr) {
DCHECK(last_instruction_ == nullptr);
first_instruction_ = last_instruction_ = instruction;
@@ -133,11 +241,53 @@
instruction->previous_ = last_instruction_;
last_instruction_ = instruction;
}
- for (int i = 0; i < instruction->InputCount(); i++) {
- instruction->InputAt(i)->AddUse(instruction);
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
+ instruction->InputAt(i)->AddUseAt(instruction, i);
}
}
+void HInstructionList::RemoveInstruction(HInstruction* instruction) {
+ if (instruction->previous_ != nullptr) {
+ instruction->previous_->next_ = instruction->next_;
+ }
+ if (instruction->next_ != nullptr) {
+ instruction->next_->previous_ = instruction->previous_;
+ }
+ if (instruction == first_instruction_) {
+ first_instruction_ = instruction->next_;
+ }
+ if (instruction == last_instruction_) {
+ last_instruction_ = instruction->previous_;
+ }
+}
+
+void HInstruction::ReplaceWith(HInstruction* other) {
+ for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HInstruction>* current = it.Current();
+ HInstruction* user = current->GetUser();
+ size_t input_index = current->GetIndex();
+ user->SetRawInputAt(input_index, other);
+ other->AddUseAt(user, input_index);
+ }
+
+ for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HEnvironment>* current = it.Current();
+ HEnvironment* user = current->GetUser();
+ size_t input_index = current->GetIndex();
+ user->SetRawEnvAt(input_index, other);
+ other->AddEnvUseAt(user, input_index);
+ }
+
+ uses_ = nullptr;
+ env_uses_ = nullptr;
+}
+
+void HPhi::AddInput(HInstruction* input) {
+ DCHECK(input->GetBlock() != nullptr);
+ inputs_.Add(input);
+ input->AddUseAt(this, inputs_.Size() - 1);
+}
+
#define DEFINE_ACCEPT(name) \
void H##name::Accept(HGraphVisitor* visitor) { \
visitor->Visit##name(this); \
@@ -155,7 +305,10 @@
}
void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
- for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ it.Current()->Accept(this);
+ }
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
it.Current()->Accept(this);
}
}
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) { }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index d19c40c..9438890 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -100,6 +100,10 @@
std::vector<uint8_t> gc_map;
codegen->BuildNativeGCMap(&gc_map, dex_compilation_unit);
+ // Run these phases to get some test coverage.
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+
return new CompiledMethod(driver,
instruction_set,
allocator.GetMemory(),
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index 606c915..c82d0cc 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -25,11 +25,19 @@
public:
explicit HPrettyPrinter(HGraph* graph) : HGraphVisitor(graph) { }
- virtual void VisitInstruction(HInstruction* instruction) {
+ void PrintPreInstruction(HInstruction* instruction) {
PrintString(" ");
PrintInt(instruction->GetId());
PrintString(": ");
+ }
+
+ virtual void VisitInstruction(HInstruction* instruction) {
+ PrintPreInstruction(instruction);
PrintString(instruction->DebugName());
+ PrintPostInstruction(instruction);
+ }
+
+ void PrintPostInstruction(HInstruction* instruction) {
if (instruction->InputCount() != 0) {
PrintString("(");
bool first = true;
@@ -46,13 +54,13 @@
if (instruction->HasUses()) {
PrintString(" [");
bool first = true;
- for (HUseIterator it(instruction); !it.Done(); it.Advance()) {
+ for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) {
if (first) {
first = false;
} else {
PrintString(", ");
}
- PrintInt(it.Current()->GetId());
+ PrintInt(it.Current()->GetUser()->GetId());
}
PrintString("]");
}
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
new file mode 100644
index 0000000..bfb4f38
--- /dev/null
+++ b/compiler/optimizing/ssa_builder.cc
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ssa_builder.h"
+#include "nodes.h"
+
+namespace art {
+
+void SsaBuilder::BuildSsa() {
+ // 1) Visit in dominator order. We need to have all predecessors of a block visited
+ // (with the exception of loops) in order to create the right environment for that
+ // block. For loops, we create phis whose inputs will be set in 2).
+ for (size_t i = 0; i < GetGraph()->GetDominatorOrder()->Size(); i++) {
+ VisitBasicBlock(GetGraph()->GetDominatorOrder()->Get(i));
+ }
+
+ // 2) Set inputs of loop phis.
+ for (size_t i = 0; i < loop_headers_.Size(); i++) {
+ HBasicBlock* block = loop_headers_.Get(i);
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* phi = it.Current()->AsPhi();
+ for (size_t pred = 0; pred < block->GetPredecessors()->Size(); pred++) {
+ phi->AddInput(ValueOfLocal(block->GetPredecessors()->Get(pred), phi->GetRegNumber()));
+ }
+ }
+ }
+
+ // 3) Clear locals.
+ // TODO: Move this to a dead code eliminator phase.
+ for (HInstructionIterator it(*GetGraph()->GetEntryBlock()->GetInstructions());
+ !it.Done();
+ it.Advance()) {
+ HInstruction* current = it.Current();
+ if (current->AsLocal() != nullptr) {
+ current->GetBlock()->RemoveInstruction(current);
+ }
+ }
+}
+
+HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
+ return GetLocalsFor(block)->Get(local);
+}
+
+void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
+ current_locals_ = GetLocalsFor(block);
+
+ if (block->IsLoopHeader()) {
+ // If the block is a loop header, we know we only have visited the pre header
+ // because we are visiting in dominator order. We create phis for all initialized
+ // locals from the pre header. Their inputs will be populated at the end of
+ // the analysis.
+ for (size_t local = 0; local < current_locals_->Size(); local++) {
+ HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local);
+ if (incoming != nullptr) {
+ // TODO: Compute union type.
+ HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+ GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid);
+ block->AddPhi(phi);
+ current_locals_->Put(local, phi);
+ }
+ }
+ // Save the loop header so that the last phase of the analysis knows which
+ // blocks need to be updated.
+ loop_headers_.Add(block);
+ } else if (block->GetPredecessors()->Size() > 0) {
+ // All predecessors have already been visited because we are visiting in dominator order.
+ // We merge the values of all locals, creating phis if those values differ.
+ for (size_t local = 0; local < current_locals_->Size(); local++) {
+ bool is_different = false;
+ HInstruction* value = ValueOfLocal(block->GetPredecessors()->Get(0), local);
+ for (size_t i = 1; i < block->GetPredecessors()->Size(); i++) {
+ if (ValueOfLocal(block->GetPredecessors()->Get(i), local) != value) {
+ is_different = true;
+ break;
+ }
+ }
+ if (is_different) {
+ // TODO: Compute union type.
+ HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+ GetGraph()->GetArena(), local, block->GetPredecessors()->Size(), Primitive::kPrimVoid);
+ for (size_t i = 0; i < block->GetPredecessors()->Size(); i++) {
+ phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors()->Get(i), local));
+ }
+ block->AddPhi(phi);
+ value = phi;
+ }
+ current_locals_->Put(local, value);
+ }
+ }
+
+ // Visit all instructions. The instructions of interest are:
+ // - HLoadLocal: replace them with the current value of the local.
+ // - HStoreLocal: update current value of the local and remove the instruction.
+ // - Instructions that require an environment: populate their environment
+ // with the current values of the locals.
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+ it.Current()->Accept(this);
+ }
+}
+
+void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
+ load->ReplaceWith(current_locals_->Get(load->GetLocal()->GetRegNumber()));
+ load->GetBlock()->RemoveInstruction(load);
+}
+
+void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
+ current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1));
+ store->GetBlock()->RemoveInstruction(store);
+}
+
+void SsaBuilder::VisitInstruction(HInstruction* instruction) {
+ if (!instruction->NeedsEnvironment()) {
+ return;
+ }
+ HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
+ GetGraph()->GetArena(), current_locals_->Size());
+ environment->Populate(*current_locals_);
+ instruction->SetEnvironment(environment);
+}
+
+} // namespace art
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
new file mode 100644
index 0000000..b6c6c0b
--- /dev/null
+++ b/compiler/optimizing/ssa_builder.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
+#define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
+
+#include "nodes.h"
+
+namespace art {
+
+static constexpr int kDefaultNumberOfLoops = 2;
+
+class SsaBuilder : public HGraphVisitor {
+ public:
+ explicit SsaBuilder(HGraph* graph)
+ : HGraphVisitor(graph),
+ current_locals_(nullptr),
+ loop_headers_(graph->GetArena(), kDefaultNumberOfLoops),
+ locals_for_(graph->GetArena(), graph->GetBlocks()->Size()) {
+ locals_for_.SetSize(graph->GetBlocks()->Size());
+ }
+
+ void BuildSsa();
+
+ GrowableArray<HInstruction*>* GetLocalsFor(HBasicBlock* block) {
+ HEnvironment* env = locals_for_.Get(block->GetBlockId());
+ if (env == nullptr) {
+ env = new (GetGraph()->GetArena()) HEnvironment(
+ GetGraph()->GetArena(), GetGraph()->GetNumberOfVRegs());
+ locals_for_.Put(block->GetBlockId(), env);
+ }
+ return env->GetVRegs();
+ }
+
+ HInstruction* ValueOfLocal(HBasicBlock* block, size_t local);
+
+ void VisitBasicBlock(HBasicBlock* block);
+ void VisitLoadLocal(HLoadLocal* load);
+ void VisitStoreLocal(HStoreLocal* store);
+ void VisitInstruction(HInstruction* instruction);
+
+ private:
+ // Locals for the current block being visited.
+ GrowableArray<HInstruction*>* current_locals_;
+
+ // Keep track of loop headers found. The last phase of the analysis iterates
+ // over these blocks to set the inputs of their phis.
+ GrowableArray<HBasicBlock*> loop_headers_;
+
+ // HEnvironment for each block.
+ GrowableArray<HEnvironment*> locals_for_;
+
+ DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
new file mode 100644
index 0000000..7c3633b
--- /dev/null
+++ b/compiler/optimizing/ssa_test.cc
@@ -0,0 +1,444 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "base/stringprintf.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "ssa_builder.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+ explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
+
+ virtual void PrintInt(int value) {
+ str_ += StringPrintf("%d", value);
+ }
+
+ virtual void PrintString(const char* value) {
+ str_ += value;
+ }
+
+ virtual void PrintNewLine() {
+ str_ += '\n';
+ }
+
+ void Clear() { str_.clear(); }
+
+ std::string str() const { return str_; }
+
+ virtual void VisitIntConstant(HIntConstant* constant) {
+ PrintPreInstruction(constant);
+ str_ += constant->DebugName();
+ str_ += " ";
+ PrintInt(constant->GetValue());
+ PrintPostInstruction(constant);
+ }
+
+ private:
+ std::string str_;
+
+ DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
+static void ReNumberInstructions(HGraph* graph) {
+ int id = 0;
+ for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) {
+ HBasicBlock* block = graph->GetBlocks()->Get(i);
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ it.Current()->SetId(id++);
+ }
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+ it.Current()->SetId(id++);
+ }
+ }
+}
+
+static void TestCode(const uint16_t* data, const char* expected) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraphBuilder builder(&allocator);
+ const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ ASSERT_NE(graph, nullptr);
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ ReNumberInstructions(graph);
+
+ StringPrettyPrinter printer(graph);
+ printer.VisitInsertionOrder();
+
+ ASSERT_STREQ(expected, printer.str().c_str());
+}
+
+TEST(SsaTest, CFG1) {
+ // Test that we get rid of loads and stores.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [2, 2]\n"
+ " 1: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ " 2: Equal(0, 0) [3]\n"
+ " 3: If(2)\n"
+ "BasicBlock 2, pred: 1, succ: 3\n"
+ " 4: Goto\n"
+ "BasicBlock 3, pred: 1, 2, succ: 4\n"
+ " 5: ReturnVoid\n"
+ "BasicBlock 4, pred: 3\n"
+ " 6: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN_VOID);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, CFG2) {
+ // Test that we create a phi for the join block of an if control flow instruction
+ // when there is only code in the else branch.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [6, 3, 3]\n"
+ " 1: IntConstant 4 [6]\n"
+ " 2: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ " 3: Equal(0, 0) [4]\n"
+ " 4: If(3)\n"
+ "BasicBlock 2, pred: 1, succ: 3\n"
+ " 5: Goto\n"
+ "BasicBlock 3, pred: 1, 2, succ: 4\n"
+ " 6: Phi(0, 1) [7]\n"
+ " 7: Return(6)\n"
+ "BasicBlock 4, pred: 3\n"
+ " 8: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, CFG3) {
+ // Test that we create a phi for the join block of an if control flow instruction
+ // when there both branches update a local.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [4, 4]\n"
+ " 1: IntConstant 4 [8]\n"
+ " 2: IntConstant 5 [8]\n"
+ " 3: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ " 4: Equal(0, 0) [5]\n"
+ " 5: If(4)\n"
+ "BasicBlock 2, pred: 1, succ: 4\n"
+ " 6: Goto\n"
+ "BasicBlock 3, pred: 1, succ: 4\n"
+ " 7: Goto\n"
+ "BasicBlock 4, pred: 2, 3, succ: 5\n"
+ " 8: Phi(1, 2) [9]\n"
+ " 9: Return(8)\n"
+ "BasicBlock 5, pred: 4\n"
+ " 10: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0x200,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop1) {
+ // Test that we create a phi for an initialized local at entry of a loop.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [6, 4, 2, 2]\n"
+ " 1: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ " 2: Equal(0, 0) [3]\n"
+ " 3: If(2)\n"
+ "BasicBlock 2, pred: 1, 3, succ: 3\n"
+ " 4: Phi(0, 6) [6]\n"
+ " 5: Goto\n"
+ "BasicBlock 3, pred: 1, 2, succ: 2\n"
+ " 6: Phi(0, 4) [4]\n"
+ " 7: Goto\n"
+ "BasicBlock 4\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x100,
+ Instruction::GOTO | 0xFF00);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop2) {
+ // Simple loop with one preheader and one back edge.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [4]\n"
+ " 1: IntConstant 4 [4]\n"
+ " 2: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 3: Goto\n"
+ "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+ " 4: Phi(0, 1) [5, 5]\n"
+ " 5: Equal(4, 4) [6]\n"
+ " 6: If(5)\n"
+ "BasicBlock 3, pred: 2, succ: 2\n"
+ " 7: Goto\n"
+ "BasicBlock 4, pred: 2, succ: 5\n"
+ " 8: ReturnVoid\n"
+ "BasicBlock 5, pred: 4\n"
+ " 9: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::RETURN_VOID);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop3) {
+ // Test that a local not yet defined at the entry of a loop is handled properly.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [5]\n"
+ " 1: IntConstant 4 [5]\n"
+ " 2: IntConstant 5 [9]\n"
+ " 3: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 4: Goto\n"
+ "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+ " 5: Phi(0, 1) [6, 6]\n"
+ " 6: Equal(5, 5) [7]\n"
+ " 7: If(6)\n"
+ "BasicBlock 3, pred: 2, succ: 2\n"
+ " 8: Goto\n"
+ "BasicBlock 4, pred: 2, succ: 5\n"
+ " 9: Return(2)\n"
+ "BasicBlock 5, pred: 4\n"
+ " 10: Exit\n";
+
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::CONST_4 | 5 << 12 | 1 << 8,
+ Instruction::RETURN | 1 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop4) {
+ // Make sure we support a preheader of a loop not being the first predecessor
+ // in the predecessor list of the header.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [4]\n"
+ " 1: IntConstant 4 [4]\n"
+ " 2: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 4\n"
+ " 3: Goto\n"
+ "BasicBlock 2, pred: 3, 4, succ: 5, 3\n"
+ " 4: Phi(1, 0) [9, 5, 5]\n"
+ " 5: Equal(4, 4) [6]\n"
+ " 6: If(5)\n"
+ "BasicBlock 3, pred: 2, succ: 2\n"
+ " 7: Goto\n"
+ "BasicBlock 4, pred: 1, succ: 2\n"
+ " 8: Goto\n"
+ "BasicBlock 5, pred: 2, succ: 6\n"
+ " 9: Return(4)\n"
+ "BasicBlock 6, pred: 5\n"
+ " 10: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x500,
+ Instruction::IF_EQ, 5,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::GOTO | 0xFC00,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop5) {
+ // Make sure we create a preheader of a loop when a header originally has two
+ // incoming blocks and one back edge.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [4, 4]\n"
+ " 1: IntConstant 4 [14]\n"
+ " 2: IntConstant 5 [14]\n"
+ " 3: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ " 4: Equal(0, 0) [5]\n"
+ " 5: If(4)\n"
+ "BasicBlock 2, pred: 1, succ: 8\n"
+ " 6: Goto\n"
+ "BasicBlock 3, pred: 1, succ: 8\n"
+ " 7: Goto\n"
+ "BasicBlock 4, pred: 5, 8, succ: 6, 5\n"
+ " 8: Phi(8, 14) [8, 12, 9, 9]\n"
+ " 9: Equal(8, 8) [10]\n"
+ " 10: If(9)\n"
+ "BasicBlock 5, pred: 4, succ: 4\n"
+ " 11: Goto\n"
+ "BasicBlock 6, pred: 4, succ: 7\n"
+ " 12: Return(8)\n"
+ "BasicBlock 7, pred: 6\n"
+ " 13: Exit\n"
+ "BasicBlock 8, pred: 2, 3, succ: 4\n"
+ " 14: Phi(1, 2) [8]\n"
+ " 15: Goto\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0x200,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop6) {
+ // Test a loop with one preheader and two back edges (e.g. continue).
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [5]\n"
+ " 1: IntConstant 4 [5, 8, 8]\n"
+ " 2: IntConstant 5 [5]\n"
+ " 3: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 4: Goto\n"
+ "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
+ " 5: Phi(0, 2, 1) [12, 6, 6]\n"
+ " 6: Equal(5, 5) [7]\n"
+ " 7: If(6)\n"
+ "BasicBlock 3, pred: 2, succ: 5, 4\n"
+ " 8: Equal(1, 1) [9]\n"
+ " 9: If(8)\n"
+ "BasicBlock 4, pred: 3, succ: 2\n"
+ " 10: Goto\n"
+ "BasicBlock 5, pred: 3, succ: 2\n"
+ " 11: Goto\n"
+ "BasicBlock 6, pred: 2, succ: 7\n"
+ " 12: Return(5)\n"
+ "BasicBlock 7, pred: 6\n"
+ " 13: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 8,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::GOTO | 0xFA00,
+ Instruction::GOTO | 0xF900,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop7) {
+ // Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0 [5]\n"
+ " 1: IntConstant 4 [5, 8, 8]\n"
+ " 2: IntConstant 5 [12]\n"
+ " 3: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 4: Goto\n"
+ "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+ " 5: Phi(0, 1) [12, 6, 6]\n"
+ " 6: Equal(5, 5) [7]\n"
+ " 7: If(6)\n"
+ "BasicBlock 3, pred: 2, succ: 5, 4\n"
+ " 8: Equal(1, 1) [9]\n"
+ " 9: If(8)\n"
+ "BasicBlock 4, pred: 3, succ: 6\n"
+ " 10: Goto\n"
+ "BasicBlock 5, pred: 3, succ: 2\n"
+ " 11: Goto\n"
+ "BasicBlock 6, pred: 2, 4, succ: 7\n"
+ " 12: Phi(5, 2) [13]\n"
+ " 13: Return(12)\n"
+ "BasicBlock 7, pred: 6\n"
+ " 14: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 8,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::GOTO | 0x0200,
+ Instruction::GOTO | 0xF900,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(SsaTest, DeadLocal) {
+ // Test that we correctly handle a local not being used.
+ const char* expected =
+ "BasicBlock 0, succ: 1\n"
+ " 0: IntConstant 0\n"
+ " 1: Goto\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 2: ReturnVoid\n"
+ "BasicBlock 2, pred: 1\n"
+ " 3: Exit\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN_VOID);
+
+ TestCode(data, expected);
+}
+
+} // namespace art