Import Dart's parallel move resolver.
And write a few tests while at it.
A parallel move resolver will be needed for performing multiple moves
that are conceptually parallel, for example moves at a block
exit that branches to a block with phi nodes.
Change-Id: Ib95b247b4fc3f2c2fcab3b8c8d032abbd6104cd7
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index aafd801..e18902f 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -20,6 +20,7 @@
#include "base/bit_field.h"
#include "globals.h"
#include "instruction_set.h"
+#include "locations.h"
#include "memory_region.h"
#include "nodes.h"
#include "utils/assembler.h"
@@ -46,267 +47,6 @@
uintptr_t native_pc;
};
-/**
- * A Location is an abstraction over the potential location
- * of an instruction. It could be in register or stack.
- */
-class Location : public ValueObject {
- public:
- enum Kind {
- kInvalid = 0,
- kStackSlot = 1, // Word size slot.
- kDoubleStackSlot = 2, // 64bit stack slot.
- kRegister = 3,
- // On 32bits architectures, quick can pass a long where the
- // low bits are in the last parameter register, and the high
- // 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) {
- DCHECK(!IsValid());
- }
-
- Location(const Location& other) : ValueObject(), value_(other.value_) {}
-
- Location& operator=(const Location& other) {
- value_ = other.value_;
- return *this;
- }
-
- bool IsValid() const {
- return value_ != kInvalid;
- }
-
- // Register locations.
- static Location RegisterLocation(ManagedRegister reg) {
- return Location(kRegister, reg.RegId());
- }
-
- bool IsRegister() const {
- return GetKind() == kRegister;
- }
-
- ManagedRegister reg() const {
- DCHECK(IsRegister());
- return static_cast<ManagedRegister>(GetPayload());
- }
-
- static uword EncodeStackIndex(intptr_t stack_index) {
- DCHECK(-kStackIndexBias <= stack_index);
- DCHECK(stack_index < kStackIndexBias);
- return static_cast<uword>(kStackIndexBias + stack_index);
- }
-
- static Location StackSlot(intptr_t stack_index) {
- uword payload = EncodeStackIndex(stack_index);
- Location loc(kStackSlot, payload);
- // Ensure that sign is preserved.
- DCHECK_EQ(loc.GetStackIndex(), stack_index);
- return loc;
- }
-
- bool IsStackSlot() const {
- return GetKind() == kStackSlot;
- }
-
- static Location DoubleStackSlot(intptr_t stack_index) {
- uword payload = EncodeStackIndex(stack_index);
- Location loc(kDoubleStackSlot, payload);
- // Ensure that sign is preserved.
- DCHECK_EQ(loc.GetStackIndex(), stack_index);
- return loc;
- }
-
- bool IsDoubleStackSlot() const {
- return GetKind() == kDoubleStackSlot;
- }
-
- intptr_t GetStackIndex() const {
- DCHECK(IsStackSlot() || IsDoubleStackSlot());
- // Decode stack index manually to preserve sign.
- return GetPayload() - kStackIndexBias;
- }
-
- intptr_t GetHighStackIndex(uintptr_t word_size) const {
- DCHECK(IsDoubleStackSlot());
- // Decode stack index manually to preserve sign.
- return GetPayload() - kStackIndexBias + word_size;
- }
-
- static Location QuickParameter(uint32_t parameter_index) {
- return Location(kQuickParameter, parameter_index);
- }
-
- uint32_t GetQuickParameterIndex() const {
- DCHECK(IsQuickParameter());
- return GetPayload();
- }
-
- bool IsQuickParameter() const {
- return GetKind() == kQuickParameter;
- }
-
- arm::ArmManagedRegister AsArm() const;
- x86::X86ManagedRegister AsX86() const;
-
- Kind GetKind() const {
- return KindField::Decode(value_);
- }
-
- bool Equals(Location other) const {
- return value_ == other.value_;
- }
-
- const char* DebugString() const {
- switch (GetKind()) {
- case kInvalid: return "?";
- case kRegister: return "R";
- 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;
- static constexpr uint32_t kBitsForPayload = kWordSize * kBitsPerByte - kBitsForKind;
-
- explicit Location(uword value) : value_(value) {}
-
- Location(Kind kind, uword payload)
- : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {}
-
- uword GetPayload() const {
- return PayloadField::Decode(value_);
- }
-
- 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);
-
- // Location either contains kind and payload fields or a tagged handle for
- // a constant locations. Values of enumeration Kind are selected in such a
- // way that none of them can be interpreted as a kConstant tag.
- uword value_;
-};
-
-/**
- * The code generator computes LocationSummary for each instruction so that
- * the instruction itself knows what code to generate: where to find the inputs
- * and where to place the result.
- *
- * The intent is to have the code for generating the instruction independent of
- * register allocation. A register allocator just has to provide a LocationSummary.
- */
-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 (size_t i = 0; i < instruction->InputCount(); i++) {
- inputs_.Put(i, Location());
- }
- }
-
- void SetInAt(uint32_t at, Location location) {
- inputs_.Put(at, location);
- }
-
- Location InAt(uint32_t at) const {
- return inputs_.Get(at);
- }
-
- size_t GetInputCount() const {
- return inputs_.Size();
- }
-
- void SetOut(Location location) {
- output_ = Location(location);
- }
-
- void AddTemp(Location location) {
- temps_.Add(location);
- }
-
- Location GetTemp(uint32_t at) const {
- return temps_.Get(at);
- }
-
- void SetTempAt(uint32_t at, Location location) {
- temps_.Put(at, location);
- }
-
- size_t GetTempCount() const {
- return temps_.Size();
- }
-
- Location Out() const { return output_; }
-
- private:
- GrowableArray<Location> inputs_;
- GrowableArray<Location> temps_;
- Location output_;
-
- DISALLOW_COPY_AND_ASSIGN(LocationSummary);
-};
-
class CodeGenerator : public ArenaObject {
public:
// Compiles the graph to executable instructions. Returns whether the compilation