summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/code_generator.cc102
-rw-r--r--compiler/optimizing/code_generator.h114
-rw-r--r--compiler/optimizing/code_generator_arm.cc163
-rw-r--r--compiler/optimizing/code_generator_arm.h11
-rw-r--r--compiler/optimizing/code_generator_x86.cc226
-rw-r--r--compiler/optimizing/code_generator_x86.h11
-rw-r--r--compiler/optimizing/nodes.cc167
-rw-r--r--compiler/optimizing/nodes.h223
-rw-r--r--compiler/optimizing/optimizing_compiler.cc4
-rw-r--r--compiler/optimizing/pretty_printer.h14
-rw-r--r--compiler/optimizing/ssa_builder.cc134
-rw-r--r--compiler/optimizing/ssa_builder.h71
-rw-r--r--compiler/optimizing/ssa_test.cc444
13 files changed, 1532 insertions, 152 deletions
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 7e63c69f5c..ff316e5b04 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -47,7 +47,7 @@ void CodeGenerator::CompileBlock(HBasicBlock* block) {
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);
@@ -55,9 +55,105 @@ void CodeGenerator::CompileBlock(HBasicBlock* block) {
}
}
+size_t CodeGenerator::AllocateFreeRegisterInternal(
+ bool* blocked_registers, size_t number_of_registers) const {
+ for (size_t regno = 0; regno < number_of_registers; regno++) {
+ if (!blocked_registers[regno]) {
+ blocked_registers[regno] = true;
+ return regno;
+ }
+ }
+ LOG(FATAL) << "Unreachable";
+ return -1;
+}
+
+
+void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
+ LocationSummary* locations = instruction->GetLocations();
+ if (locations == nullptr) return;
+
+ for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) {
+ blocked_registers_[i] = false;
+ }
+
+ // Mark all fixed input, temp and output registers as used.
+ for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
+ Location loc = locations->InAt(i);
+ if (loc.IsRegister()) {
+ // Check that a register is not specified twice in the summary.
+ DCHECK(!blocked_registers_[loc.GetEncoding()]);
+ blocked_registers_[loc.GetEncoding()] = true;
+ }
+ }
+
+ for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
+ Location loc = locations->GetTemp(i);
+ if (loc.IsRegister()) {
+ // Check that a register is not specified twice in the summary.
+ DCHECK(!blocked_registers_[loc.GetEncoding()]);
+ blocked_registers_[loc.GetEncoding()] = true;
+ }
+ }
+
+ SetupBlockedRegisters(blocked_registers_);
+
+ // Allocate all unallocated input locations.
+ for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
+ Location loc = locations->InAt(i);
+ HInstruction* input = instruction->InputAt(i);
+ if (loc.IsUnallocated()) {
+ if (loc.GetPolicy() == Location::kRequiresRegister) {
+ loc = Location::RegisterLocation(
+ AllocateFreeRegister(input->GetType(), blocked_registers_));
+ } else {
+ DCHECK_EQ(loc.GetPolicy(), Location::kAny);
+ HLoadLocal* load = input->AsLoadLocal();
+ if (load != nullptr) {
+ loc = GetStackLocation(load);
+ } else {
+ loc = Location::RegisterLocation(
+ AllocateFreeRegister(input->GetType(), blocked_registers_));
+ }
+ }
+ locations->SetInAt(i, loc);
+ }
+ }
+
+ // Allocate all unallocated temp locations.
+ for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
+ Location loc = locations->GetTemp(i);
+ if (loc.IsUnallocated()) {
+ DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
+ // TODO: Adjust handling of temps. We currently consider temps to use
+ // core registers. They may also use floating point registers at some point.
+ loc = Location::RegisterLocation(static_cast<ManagedRegister>(
+ AllocateFreeRegister(Primitive::kPrimInt, blocked_registers_)));
+ locations->SetTempAt(i, loc);
+ }
+ }
+
+ Location result_location = locations->Out();
+ if (result_location.IsUnallocated()) {
+ switch (result_location.GetPolicy()) {
+ case Location::kAny:
+ case Location::kRequiresRegister:
+ result_location = Location::RegisterLocation(
+ AllocateFreeRegister(instruction->GetType(), blocked_registers_));
+ break;
+ case Location::kSameAsFirstInput:
+ result_location = locations->InAt(0);
+ break;
+ }
+ locations->SetOut(result_location);
+ }
+}
+
void CodeGenerator::InitLocations(HInstruction* instruction) {
- if (instruction->GetLocations() == nullptr) return;
- for (int i = 0; i < instruction->InputCount(); i++) {
+ if (instruction->GetLocations() == nullptr) {
+ return;
+ }
+ AllocateRegistersLocally(instruction);
+ for (size_t i = 0, e = instruction->InputCount(); i < e; ++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 5c7cac1e5c..74cbccc4b8 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -62,6 +62,12 @@ class Location : public ValueObject {
// bits are in a stack slot. The kQuickParameter kind is for
// handling this special case.
kQuickParameter = 4,
+
+ // Unallocated location represents a location that is not fixed and can be
+ // allocated by a register allocator. Each unallocated location has
+ // a policy that specifies what kind of location is suitable. Payload
+ // contains register allocation policy.
+ kUnallocated = 5,
};
Location() : value_(kInvalid) {
@@ -166,10 +172,50 @@ class Location : public ValueObject {
case kStackSlot: return "S";
case kDoubleStackSlot: return "DS";
case kQuickParameter: return "Q";
+ case kUnallocated: return "U";
}
return "?";
}
+ // Unallocated locations.
+ enum Policy {
+ kAny,
+ kRequiresRegister,
+ kSameAsFirstInput,
+ };
+
+ bool IsUnallocated() const {
+ return GetKind() == kUnallocated;
+ }
+
+ static Location UnallocatedLocation(Policy policy) {
+ return Location(kUnallocated, PolicyField::Encode(policy));
+ }
+
+ // Any free register is suitable to replace this unallocated location.
+ static Location Any() {
+ return UnallocatedLocation(kAny);
+ }
+
+ static Location RequiresRegister() {
+ return UnallocatedLocation(kRequiresRegister);
+ }
+
+ // The location of the first input to the instruction will be
+ // used to replace this unallocated location.
+ static Location SameAsFirstInput() {
+ return UnallocatedLocation(kSameAsFirstInput);
+ }
+
+ Policy GetPolicy() const {
+ DCHECK(IsUnallocated());
+ return PolicyField::Decode(GetPayload());
+ }
+
+ uword GetEncoding() const {
+ return GetPayload();
+ }
+
private:
// Number of bits required to encode Kind value.
static constexpr uint32_t kBitsForKind = 4;
@@ -187,6 +233,9 @@ class Location : public ValueObject {
typedef BitField<Kind, 0, kBitsForKind> KindField;
typedef BitField<uword, kBitsForKind, kBitsForPayload> PayloadField;
+ // Layout for kUnallocated locations payload.
+ typedef BitField<Policy, 0, 3> PolicyField;
+
// Layout for stack slots.
static const intptr_t kStackIndexBias =
static_cast<intptr_t>(1) << (kBitsForPayload - 1);
@@ -208,40 +257,52 @@ class Location : public ValueObject {
class LocationSummary : public ArenaObject {
public:
explicit LocationSummary(HInstruction* instruction)
- : 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++) {
- inputs.Put(i, Location());
+ : inputs_(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()),
+ temps_(instruction->GetBlock()->GetGraph()->GetArena(), 0) {
+ inputs_.SetSize(instruction->InputCount());
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
+ inputs_.Put(i, Location());
}
}
void SetInAt(uint32_t at, Location location) {
- inputs.Put(at, location);
+ inputs_.Put(at, location);
}
Location InAt(uint32_t at) const {
- return inputs.Get(at);
+ return inputs_.Get(at);
+ }
+
+ size_t GetInputCount() const {
+ return inputs_.Size();
}
void SetOut(Location location) {
- output = Location(location);
+ output_ = Location(location);
}
void AddTemp(Location location) {
- temps.Add(location);
+ temps_.Add(location);
}
Location GetTemp(uint32_t at) const {
- return temps.Get(at);
+ return temps_.Get(at);
+ }
+
+ void SetTempAt(uint32_t at, Location location) {
+ temps_.Put(at, location);
}
- Location Out() const { return output; }
+ size_t GetTempCount() const {
+ return temps_.Size();
+ }
+
+ Location Out() const { return output_; }
private:
- GrowableArray<Location> inputs;
- GrowableArray<Location> temps;
- Location output;
+ GrowableArray<Location> inputs_;
+ GrowableArray<Location> temps_;
+ Location output_;
DISALLOW_COPY_AND_ASSIGN(LocationSummary);
};
@@ -286,15 +347,33 @@ class CodeGenerator : public ArenaObject {
std::vector<uint8_t>* vector, const DexCompilationUnit& dex_compilation_unit) const;
protected:
- explicit CodeGenerator(HGraph* graph)
+ CodeGenerator(HGraph* graph, size_t number_of_registers)
: frame_size_(0),
graph_(graph),
block_labels_(graph->GetArena(), 0),
- pc_infos_(graph->GetArena(), 32) {
+ pc_infos_(graph->GetArena(), 32),
+ blocked_registers_(static_cast<bool*>(
+ graph->GetArena()->Alloc(number_of_registers * sizeof(bool), kArenaAllocData))) {
block_labels_.SetSize(graph->GetBlocks()->Size());
}
~CodeGenerator() { }
+ // Register allocation logic.
+ void AllocateRegistersLocally(HInstruction* instruction) const;
+
+ // Backend specific implementation for allocating a register.
+ virtual ManagedRegister AllocateFreeRegister(Primitive::Type type,
+ bool* blocked_registers) const = 0;
+
+ // Raw implementation of allocating a register: loops over blocked_registers to find
+ // the first available register.
+ size_t AllocateFreeRegisterInternal(bool* blocked_registers, size_t number_of_registers) const;
+
+ virtual void SetupBlockedRegisters(bool* blocked_registers) const = 0;
+ virtual size_t GetNumberOfRegisters() const = 0;
+
+ virtual Location GetStackLocation(HLoadLocal* load) const = 0;
+
// Frame size required for this method.
uint32_t frame_size_;
uint32_t core_spill_mask_;
@@ -309,6 +388,9 @@ class CodeGenerator : public ArenaObject {
GrowableArray<Label> block_labels_;
GrowableArray<PcInfo> pc_infos_;
+ // Temporary data structure used when doing register allocation.
+ bool* const blocked_registers_;
+
DISALLOW_COPY_AND_ASSIGN(CodeGenerator);
};
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 27691ac080..a446701b39 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -35,6 +35,81 @@ namespace arm {
static constexpr int kNumberOfPushedRegistersAtEntry = 1;
static constexpr int kCurrentMethodStackOffset = 0;
+CodeGeneratorARM::CodeGeneratorARM(HGraph* graph)
+ : CodeGenerator(graph, kNumberOfRegIds),
+ location_builder_(graph, this),
+ instruction_visitor_(graph, this) {}
+
+static bool* GetBlockedRegisterPairs(bool* blocked_registers) {
+ return blocked_registers + kNumberOfAllocIds;
+}
+
+ManagedRegister CodeGeneratorARM::AllocateFreeRegister(Primitive::Type type,
+ bool* blocked_registers) const {
+ switch (type) {
+ case Primitive::kPrimLong: {
+ size_t reg = AllocateFreeRegisterInternal(
+ GetBlockedRegisterPairs(blocked_registers), kNumberOfRegisterPairs);
+ ArmManagedRegister pair =
+ ArmManagedRegister::FromRegisterPair(static_cast<RegisterPair>(reg));
+ blocked_registers[pair.AsRegisterPairLow()] = true;
+ blocked_registers[pair.AsRegisterPairHigh()] = true;
+ return pair;
+ }
+
+ case Primitive::kPrimByte:
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimInt:
+ case Primitive::kPrimNot: {
+ size_t reg = AllocateFreeRegisterInternal(blocked_registers, kNumberOfCoreRegisters);
+ return ArmManagedRegister::FromCoreRegister(static_cast<Register>(reg));
+ }
+
+ case Primitive::kPrimFloat:
+ case Primitive::kPrimDouble:
+ LOG(FATAL) << "Unimplemented register type " << type;
+
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unreachable type " << type;
+ }
+
+ return ManagedRegister::NoRegister();
+}
+
+void CodeGeneratorARM::SetupBlockedRegisters(bool* blocked_registers) const {
+ bool* blocked_register_pairs = GetBlockedRegisterPairs(blocked_registers);
+
+ // Don't allocate the dalvik style register pair passing.
+ blocked_register_pairs[R1_R2] = true;
+
+ // Stack register, LR and PC are always reserved.
+ blocked_registers[SP] = true;
+ blocked_registers[LR] = true;
+ blocked_registers[PC] = true;
+
+ // Reserve R4 for suspend check.
+ blocked_registers[R4] = true;
+ blocked_register_pairs[R4_R5] = true;
+
+ // Reserve thread register.
+ blocked_registers[TR] = true;
+
+ // TODO: We currently don't use Quick's callee saved registers.
+ blocked_registers[R5] = true;
+ blocked_registers[R6] = true;
+ blocked_registers[R7] = true;
+ blocked_registers[R8] = true;
+ blocked_registers[R10] = true;
+ blocked_registers[R11] = true;
+ blocked_register_pairs[R6_R7] = true;
+}
+
+size_t CodeGeneratorARM::GetNumberOfRegisters() const {
+ return kNumberOfRegIds;
+}
+
static Location ArmCoreLocation(Register reg) {
return Location::RegisterLocation(ArmManagedRegister::FromCoreRegister(reg));
}
@@ -85,6 +160,32 @@ int32_t CodeGeneratorARM::GetStackSlot(HLocal* local) const {
}
}
+Location CodeGeneratorARM::GetStackLocation(HLoadLocal* load) const {
+ switch (load->GetType()) {
+ case Primitive::kPrimLong:
+ return Location::DoubleStackSlot(GetStackSlot(load->GetLocal()));
+ break;
+
+ case Primitive::kPrimInt:
+ case Primitive::kPrimNot:
+ return Location::StackSlot(GetStackSlot(load->GetLocal()));
+
+ case Primitive::kPrimFloat:
+ case Primitive::kPrimDouble:
+ LOG(FATAL) << "Unimplemented type " << load->GetType();
+
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unexpected type " << load->GetType();
+ }
+
+ LOG(FATAL) << "Unreachable";
+ return Location();
+}
+
Location InvokeDexCallingConventionVisitor::GetNextLocation(Primitive::Type type) {
switch (type) {
case Primitive::kPrimBoolean:
@@ -302,7 +403,7 @@ void InstructionCodeGeneratorARM::VisitExit(HExit* exit) {
void LocationsBuilderARM::VisitIf(HIf* if_instr) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(if_instr);
- locations->SetInAt(0, ArmCoreLocation(R0));
+ locations->SetInAt(0, Location::RequiresRegister());
if_instr->SetLocations(locations);
}
@@ -317,9 +418,9 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
void LocationsBuilderARM::VisitEqual(HEqual* equal) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(equal);
- locations->SetInAt(0, ArmCoreLocation(R0));
- locations->SetInAt(1, ArmCoreLocation(R1));
- locations->SetOut(ArmCoreLocation(R0));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::RequiresRegister());
+ locations->SetOut(Location::RequiresRegister());
equal->SetLocations(locations);
}
@@ -409,7 +510,8 @@ void LocationsBuilderARM::VisitReturn(HReturn* ret) {
break;
case Primitive::kPrimLong:
- locations->SetInAt(0, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
+ locations->SetInAt(
+ 0, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
break;
default:
@@ -444,10 +546,10 @@ void InstructionCodeGeneratorARM::VisitReturn(HReturn* ret) {
void LocationsBuilderARM::VisitInvokeStatic(HInvokeStatic* invoke) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(invoke);
- locations->AddTemp(ArmCoreLocation(R0));
+ locations->AddTemp(Location::RequiresRegister());
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()));
}
@@ -512,19 +614,11 @@ void InstructionCodeGeneratorARM::VisitInvokeStatic(HInvokeStatic* invoke) {
void LocationsBuilderARM::VisitAdd(HAdd* add) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(add);
switch (add->GetResultType()) {
- case Primitive::kPrimInt: {
- locations->SetInAt(0, ArmCoreLocation(R0));
- locations->SetInAt(1, ArmCoreLocation(R1));
- locations->SetOut(ArmCoreLocation(R0));
- break;
- }
-
+ case Primitive::kPrimInt:
case Primitive::kPrimLong: {
- locations->SetInAt(
- 0, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
- locations->SetInAt(
- 1, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R2_R3)));
- locations->SetOut(Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::RequiresRegister());
+ locations->SetOut(Location::RequiresRegister());
break;
}
@@ -574,19 +668,11 @@ void InstructionCodeGeneratorARM::VisitAdd(HAdd* add) {
void LocationsBuilderARM::VisitSub(HSub* sub) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(sub);
switch (sub->GetResultType()) {
- case Primitive::kPrimInt: {
- locations->SetInAt(0, ArmCoreLocation(R0));
- locations->SetInAt(1, ArmCoreLocation(R1));
- locations->SetOut(ArmCoreLocation(R0));
- break;
- }
-
+ case Primitive::kPrimInt:
case Primitive::kPrimLong: {
- locations->SetInAt(
- 0, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
- locations->SetInAt(
- 1, Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R2_R3)));
- locations->SetOut(Location::RegisterLocation(ArmManagedRegister::FromRegisterPair(R0_R1)));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::RequiresRegister());
+ locations->SetOut(Location::RequiresRegister());
break;
}
@@ -649,6 +735,9 @@ class InvokeRuntimeCallingConvention : public CallingConvention<Register> {
void LocationsBuilderARM::VisitNewInstance(HNewInstance* instruction) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
+ InvokeRuntimeCallingConvention calling_convention;
+ locations->AddTemp(ArmCoreLocation(calling_convention.GetRegisterAt(0)));
+ locations->AddTemp(ArmCoreLocation(calling_convention.GetRegisterAt(1)));
locations->SetOut(ArmCoreLocation(R0));
instruction->SetLocations(locations);
}
@@ -683,8 +772,8 @@ void InstructionCodeGeneratorARM::VisitParameterValue(HParameterValue* instructi
void LocationsBuilderARM::VisitNot(HNot* instruction) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
- locations->SetInAt(0, ArmCoreLocation(R0));
- locations->SetOut(ArmCoreLocation(R0));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetOut(Location::RequiresRegister());
instruction->SetLocations(locations);
}
@@ -694,5 +783,13 @@ void InstructionCodeGeneratorARM::VisitNot(HNot* instruction) {
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_arm.h b/compiler/optimizing/code_generator_arm.h
index ed35f94e2b..2405d4b5a6 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -101,10 +101,7 @@ class InstructionCodeGeneratorARM : public HGraphVisitor {
class CodeGeneratorARM : public CodeGenerator {
public:
- explicit CodeGeneratorARM(HGraph* graph)
- : CodeGenerator(graph),
- location_builder_(graph, this),
- instruction_visitor_(graph, this) { }
+ explicit CodeGeneratorARM(HGraph* graph);
virtual ~CodeGeneratorARM() { }
virtual void GenerateFrameEntry() OVERRIDE;
@@ -128,7 +125,13 @@ class CodeGeneratorARM : public CodeGenerator {
return &assembler_;
}
+ virtual void SetupBlockedRegisters(bool* blocked_registers) const OVERRIDE;
+ virtual ManagedRegister AllocateFreeRegister(
+ Primitive::Type type, bool* blocked_registers) const OVERRIDE;
+ virtual size_t GetNumberOfRegisters() const OVERRIDE;
+
int32_t GetStackSlot(HLocal* local) const;
+ virtual Location GetStackLocation(HLoadLocal* load) const OVERRIDE;
private:
// Helper method to move a 32bits value between two locations.
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 114263161d..fbb054ae88 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -35,6 +35,72 @@ namespace x86 {
static constexpr int kNumberOfPushedRegistersAtEntry = 1;
static constexpr int kCurrentMethodStackOffset = 0;
+CodeGeneratorX86::CodeGeneratorX86(HGraph* graph)
+ : CodeGenerator(graph, kNumberOfRegIds),
+ location_builder_(graph, this),
+ instruction_visitor_(graph, this) {}
+
+static bool* GetBlockedRegisterPairs(bool* blocked_registers) {
+ return blocked_registers + kNumberOfAllocIds;
+}
+
+ManagedRegister CodeGeneratorX86::AllocateFreeRegister(Primitive::Type type,
+ bool* blocked_registers) const {
+ switch (type) {
+ case Primitive::kPrimLong: {
+ size_t reg = AllocateFreeRegisterInternal(
+ GetBlockedRegisterPairs(blocked_registers), kNumberOfRegisterPairs);
+ X86ManagedRegister pair =
+ X86ManagedRegister::FromRegisterPair(static_cast<RegisterPair>(reg));
+ blocked_registers[pair.AsRegisterPairLow()] = true;
+ blocked_registers[pair.AsRegisterPairHigh()] = true;
+ return pair;
+ }
+
+ case Primitive::kPrimByte:
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimInt:
+ case Primitive::kPrimNot: {
+ size_t reg = AllocateFreeRegisterInternal(blocked_registers, kNumberOfCpuRegisters);
+ return X86ManagedRegister::FromCpuRegister(static_cast<Register>(reg));
+ }
+
+ case Primitive::kPrimFloat:
+ case Primitive::kPrimDouble:
+ LOG(FATAL) << "Unimplemented register type " << type;
+
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unreachable type " << type;
+ }
+
+ return ManagedRegister::NoRegister();
+}
+
+void CodeGeneratorX86::SetupBlockedRegisters(bool* blocked_registers) const {
+ bool* blocked_register_pairs = GetBlockedRegisterPairs(blocked_registers);
+
+ // Don't allocate the dalvik style register pair passing.
+ blocked_register_pairs[ECX_EDX] = true;
+
+ // Stack register is always reserved.
+ blocked_registers[ESP] = true;
+
+ // TODO: We currently don't use Quick's callee saved registers.
+ blocked_registers[EBP] = true;
+ blocked_registers[ESI] = true;
+ blocked_registers[EDI] = true;
+ blocked_register_pairs[EAX_EDI] = true;
+ blocked_register_pairs[EDX_EDI] = true;
+ blocked_register_pairs[ECX_EDI] = true;
+ blocked_register_pairs[EBX_EDI] = true;
+}
+
+size_t CodeGeneratorX86::GetNumberOfRegisters() const {
+ return kNumberOfRegIds;
+}
+
static Location X86CpuLocation(Register reg) {
return Location::RegisterLocation(X86ManagedRegister::FromCpuRegister(reg));
}
@@ -90,6 +156,33 @@ int32_t CodeGeneratorX86::GetStackSlot(HLocal* local) const {
}
}
+
+Location CodeGeneratorX86::GetStackLocation(HLoadLocal* load) const {
+ switch (load->GetType()) {
+ case Primitive::kPrimLong:
+ return Location::DoubleStackSlot(GetStackSlot(load->GetLocal()));
+ break;
+
+ case Primitive::kPrimInt:
+ case Primitive::kPrimNot:
+ return Location::StackSlot(GetStackSlot(load->GetLocal()));
+
+ case Primitive::kPrimFloat:
+ case Primitive::kPrimDouble:
+ LOG(FATAL) << "Unimplemented type " << load->GetType();
+
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unexpected type " << load->GetType();
+ }
+
+ LOG(FATAL) << "Unreachable";
+ return Location();
+}
+
static constexpr Register kRuntimeParameterCoreRegisters[] = { EAX, ECX, EDX };
static constexpr size_t kRuntimeParameterCoreRegistersLength =
arraysize(kRuntimeParameterCoreRegisters);
@@ -311,13 +404,18 @@ void InstructionCodeGeneratorX86::VisitExit(HExit* exit) {
void LocationsBuilderX86::VisitIf(HIf* if_instr) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(if_instr);
- locations->SetInAt(0, X86CpuLocation(EAX));
+ locations->SetInAt(0, Location::Any());
if_instr->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
// TODO: Generate the input as a condition, instead of materializing in a register.
- __ cmpl(if_instr->GetLocations()->InAt(0).AsX86().AsCpuRegister(), Immediate(0));
+ Location location = if_instr->GetLocations()->InAt(0);
+ if (location.IsRegister()) {
+ __ cmpl(location.AsX86().AsCpuRegister(), Immediate(0));
+ } else {
+ __ cmpl(Address(ESP, location.GetStackIndex()), Immediate(0));
+ }
__ j(kEqual, codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfTrueSuccessor())) {
__ jmp(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
@@ -367,16 +465,22 @@ void InstructionCodeGeneratorX86::VisitStoreLocal(HStoreLocal* store) {
void LocationsBuilderX86::VisitEqual(HEqual* equal) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(equal);
- locations->SetInAt(0, X86CpuLocation(EAX));
- locations->SetInAt(1, X86CpuLocation(ECX));
- locations->SetOut(X86CpuLocation(EAX));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::Any());
+ locations->SetOut(Location::SameAsFirstInput());
equal->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitEqual(HEqual* equal) {
- __ cmpl(equal->GetLocations()->InAt(0).AsX86().AsCpuRegister(),
- equal->GetLocations()->InAt(1).AsX86().AsCpuRegister());
- __ setb(kEqual, equal->GetLocations()->Out().AsX86().AsCpuRegister());
+ LocationSummary* locations = equal->GetLocations();
+ if (locations->InAt(1).IsRegister()) {
+ __ cmpl(locations->InAt(0).AsX86().AsCpuRegister(),
+ locations->InAt(1).AsX86().AsCpuRegister());
+ } else {
+ __ cmpl(locations->InAt(0).AsX86().AsCpuRegister(),
+ Address(ESP, locations->InAt(1).GetStackIndex()));
+ }
+ __ setb(kEqual, locations->Out().AsX86().AsCpuRegister());
}
void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) {
@@ -453,10 +557,10 @@ void InstructionCodeGeneratorX86::VisitReturn(HReturn* ret) {
void LocationsBuilderX86::VisitInvokeStatic(HInvokeStatic* invoke) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(invoke);
- locations->AddTemp(X86CpuLocation(EAX));
+ locations->AddTemp(Location::RequiresRegister());
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()));
}
@@ -514,18 +618,11 @@ void InstructionCodeGeneratorX86::VisitInvokeStatic(HInvokeStatic* invoke) {
void LocationsBuilderX86::VisitAdd(HAdd* add) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(add);
switch (add->GetResultType()) {
- case Primitive::kPrimInt: {
- locations->SetInAt(0, X86CpuLocation(EAX));
- locations->SetInAt(1, X86CpuLocation(ECX));
- locations->SetOut(X86CpuLocation(EAX));
- break;
- }
+ case Primitive::kPrimInt:
case Primitive::kPrimLong: {
- locations->SetInAt(
- 0, Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(EAX_EDX)));
- locations->SetInAt(
- 1, Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(ECX_EBX)));
- locations->SetOut(Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(EAX_EDX)));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::Any());
+ locations->SetOut(Location::SameAsFirstInput());
break;
}
@@ -548,18 +645,30 @@ void InstructionCodeGeneratorX86::VisitAdd(HAdd* add) {
case Primitive::kPrimInt: {
DCHECK_EQ(locations->InAt(0).AsX86().AsCpuRegister(),
locations->Out().AsX86().AsCpuRegister());
- __ addl(locations->InAt(0).AsX86().AsCpuRegister(),
- locations->InAt(1).AsX86().AsCpuRegister());
+ if (locations->InAt(1).IsRegister()) {
+ __ addl(locations->InAt(0).AsX86().AsCpuRegister(),
+ locations->InAt(1).AsX86().AsCpuRegister());
+ } else {
+ __ addl(locations->InAt(0).AsX86().AsCpuRegister(),
+ Address(ESP, locations->InAt(1).GetStackIndex()));
+ }
break;
}
case Primitive::kPrimLong: {
DCHECK_EQ(locations->InAt(0).AsX86().AsRegisterPair(),
locations->Out().AsX86().AsRegisterPair());
- __ addl(locations->InAt(0).AsX86().AsRegisterPairLow(),
- locations->InAt(1).AsX86().AsRegisterPairLow());
- __ adcl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
- locations->InAt(1).AsX86().AsRegisterPairHigh());
+ if (locations->InAt(1).IsRegister()) {
+ __ addl(locations->InAt(0).AsX86().AsRegisterPairLow(),
+ locations->InAt(1).AsX86().AsRegisterPairLow());
+ __ adcl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
+ locations->InAt(1).AsX86().AsRegisterPairHigh());
+ } else {
+ __ addl(locations->InAt(0).AsX86().AsRegisterPairLow(),
+ Address(ESP, locations->InAt(1).GetStackIndex()));
+ __ adcl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
+ Address(ESP, locations->InAt(1).GetHighStackIndex(kX86WordSize)));
+ }
break;
}
@@ -578,19 +687,11 @@ void InstructionCodeGeneratorX86::VisitAdd(HAdd* add) {
void LocationsBuilderX86::VisitSub(HSub* sub) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(sub);
switch (sub->GetResultType()) {
- case Primitive::kPrimInt: {
- locations->SetInAt(0, X86CpuLocation(EAX));
- locations->SetInAt(1, X86CpuLocation(ECX));
- locations->SetOut(X86CpuLocation(EAX));
- break;
- }
-
+ case Primitive::kPrimInt:
case Primitive::kPrimLong: {
- locations->SetInAt(
- 0, Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(EAX_EDX)));
- locations->SetInAt(
- 1, Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(ECX_EBX)));
- locations->SetOut(Location::RegisterLocation(X86ManagedRegister::FromRegisterPair(EAX_EDX)));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetInAt(1, Location::Any());
+ locations->SetOut(Location::SameAsFirstInput());
break;
}
@@ -613,18 +714,30 @@ void InstructionCodeGeneratorX86::VisitSub(HSub* sub) {
case Primitive::kPrimInt: {
DCHECK_EQ(locations->InAt(0).AsX86().AsCpuRegister(),
locations->Out().AsX86().AsCpuRegister());
- __ subl(locations->InAt(0).AsX86().AsCpuRegister(),
- locations->InAt(1).AsX86().AsCpuRegister());
+ if (locations->InAt(1).IsRegister()) {
+ __ subl(locations->InAt(0).AsX86().AsCpuRegister(),
+ locations->InAt(1).AsX86().AsCpuRegister());
+ } else {
+ __ subl(locations->InAt(0).AsX86().AsCpuRegister(),
+ Address(ESP, locations->InAt(1).GetStackIndex()));
+ }
break;
}
case Primitive::kPrimLong: {
DCHECK_EQ(locations->InAt(0).AsX86().AsRegisterPair(),
locations->Out().AsX86().AsRegisterPair());
- __ subl(locations->InAt(0).AsX86().AsRegisterPairLow(),
- locations->InAt(1).AsX86().AsRegisterPairLow());
- __ sbbl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
- locations->InAt(1).AsX86().AsRegisterPairHigh());
+ if (locations->InAt(1).IsRegister()) {
+ __ subl(locations->InAt(0).AsX86().AsRegisterPairLow(),
+ locations->InAt(1).AsX86().AsRegisterPairLow());
+ __ sbbl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
+ locations->InAt(1).AsX86().AsRegisterPairHigh());
+ } else {
+ __ subl(locations->InAt(0).AsX86().AsRegisterPairLow(),
+ Address(ESP, locations->InAt(1).GetStackIndex()));
+ __ sbbl(locations->InAt(0).AsX86().AsRegisterPairHigh(),
+ Address(ESP, locations->InAt(1).GetHighStackIndex(kX86WordSize)));
+ }
break;
}
@@ -643,14 +756,16 @@ void InstructionCodeGeneratorX86::VisitSub(HSub* sub) {
void LocationsBuilderX86::VisitNewInstance(HNewInstance* instruction) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
locations->SetOut(X86CpuLocation(EAX));
+ InvokeRuntimeCallingConvention calling_convention;
+ locations->AddTemp(X86CpuLocation(calling_convention.GetRegisterAt(0)));
+ locations->AddTemp(X86CpuLocation(calling_convention.GetRegisterAt(1)));
instruction->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitNewInstance(HNewInstance* instruction) {
InvokeRuntimeCallingConvention calling_convention;
LoadCurrentMethod(calling_convention.GetRegisterAt(1));
- __ movl(calling_convention.GetRegisterAt(0),
- Immediate(instruction->GetTypeIndex()));
+ __ movl(calling_convention.GetRegisterAt(0), Immediate(instruction->GetTypeIndex()));
__ fs()->call(
Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pAllocObjectWithAccessCheck)));
@@ -676,15 +791,24 @@ void InstructionCodeGeneratorX86::VisitParameterValue(HParameterValue* instructi
void LocationsBuilderX86::VisitNot(HNot* instruction) {
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
- locations->SetInAt(0, X86CpuLocation(EAX));
- locations->SetOut(X86CpuLocation(EAX));
+ locations->SetInAt(0, Location::RequiresRegister());
+ locations->SetOut(Location::SameAsFirstInput());
instruction->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitNot(HNot* instruction) {
LocationSummary* locations = instruction->GetLocations();
- DCHECK_EQ(locations->InAt(0).AsX86().AsCpuRegister(), locations->Out().AsX86().AsCpuRegister());
- __ xorl(locations->Out().AsX86().AsCpuRegister(), Immediate(1));
+ Location out = locations->Out();
+ DCHECK_EQ(locations->InAt(0).AsX86().AsCpuRegister(), out.AsX86().AsCpuRegister());
+ __ xorl(out.AsX86().AsCpuRegister(), Immediate(1));
+}
+
+void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
+}
+
+void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) {
+ LOG(FATAL) << "Unimplemented";
}
} // namespace x86
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index f22890e708..1ee11bf0e8 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -102,10 +102,7 @@ class InstructionCodeGeneratorX86 : public HGraphVisitor {
class CodeGeneratorX86 : public CodeGenerator {
public:
- explicit CodeGeneratorX86(HGraph* graph)
- : CodeGenerator(graph),
- location_builder_(graph, this),
- instruction_visitor_(graph, this) { }
+ explicit CodeGeneratorX86(HGraph* graph);
virtual ~CodeGeneratorX86() { }
virtual void GenerateFrameEntry() OVERRIDE;
@@ -129,7 +126,13 @@ class CodeGeneratorX86 : public CodeGenerator {
return &assembler_;
}
+ virtual size_t GetNumberOfRegisters() const OVERRIDE;
+ virtual void SetupBlockedRegisters(bool* blocked_registers) const OVERRIDE;
+ virtual ManagedRegister AllocateFreeRegister(
+ Primitive::Type type, bool* blocked_registers) const OVERRIDE;
+
int32_t GetStackSlot(HLocal* local) const;
+ virtual Location GetStackLocation(HLoadLocal* load) const OVERRIDE;
private:
// Helper method to move a 32bits value between two locations.
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 498deba2b4..3d6aeb7300 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 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
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 HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
}
}
-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,9 +241,51 @@ void HBasicBlock::AddInstruction(HInstruction* instruction) {
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) \
@@ -155,7 +305,10 @@ void HGraphVisitor::VisitInsertionOrder() {
}
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 3da9ed9461..581c1d56f2 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 kDefaultNumberOfSuccessors = 2;
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 @@ class HGraph : public ArenaObject {
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 @@ class HGraph : public ArenaObject {
return number_of_in_vregs_;
}
+ GrowableArray<HBasicBlock*>* GetDominatorOrder() {
+ return &dominator_order_;
+ }
private:
HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -138,7 +163,18 @@ class HLoopInformation : public ArenaObject {
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 @@ class HBasicBlock : public ArenaObject {
: 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 @@ class HBasicBlock : public ArenaObject {
: 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 @@ class HBasicBlock : public ArenaObject {
M(NewInstance) \
M(Not) \
M(ParameterValue) \
+ M(Phi) \
M(Return) \
M(ReturnVoid) \
M(StoreLocal) \
@@ -244,17 +295,22 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
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 @@ class HInstruction : public ArenaObject {
block_(nullptr),
id_(-1),
uses_(nullptr),
+ env_uses_(nullptr),
+ environment_(nullptr),
locations_(nullptr) { }
virtual ~HInstruction() { }
@@ -277,28 +335,43 @@ class HInstruction : public ArenaObject {
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;
+
+ virtual bool NeedsEnvironment() const { return false; }
- void AddUse(HInstruction* user) {
- uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, uses_);
+ 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 @@ class HInstruction : public ArenaObject {
// 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 @@ class HUseIterator : public ValueObject {
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 @@ class HInputIterator : public ValueObject {
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 @@ class HTemplateInstruction: public HInstruction {
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 @@ class HInvoke : public HInstruction {
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 @@ class HNewInstance : public HTemplateInstruction<0> {
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 @@ class HNot : public HTemplateInstruction<1> {
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 d19c40c291..9438890941 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -100,6 +100,10 @@ CompiledMethod* OptimizingCompiler::TryCompile(CompilerDriver& driver,
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 606c91519e..c82d0cc6a4 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -25,11 +25,19 @@ class HPrettyPrinter : public HGraphVisitor {
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 @@ class HPrettyPrinter : public HGraphVisitor {
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 0000000000..bfb4f38f50
--- /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 0000000000..b6c6c0b658
--- /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 0000000000..7c3633b5e9
--- /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
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-24 19:49:39 +0000