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

1 files changed, 1 insertions, 261 deletions

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 @@ struct PcInfo {
   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