New linear scan allocator.

runtime/vm/locations.h

Index: runtime/vm/locations.h
diff --git a/runtime/vm/locations.h b/runtime/vm/locations.h
index fc65d01968db6c7dbbb1b83204cb44f84dfd85db..bfac8aefd0aaff25491f168f50ebbdb81fbd472b 100644
--- a/runtime/vm/locations.h
+++ b/runtime/vm/locations.h
@@ -36,7 +36,9 @@ class Location : public ValueObject {
     kUnallocated = 2,
 
     // Register location represents a fixed register.
-    kRegister = 3
+    kRegister = 3,
+
+    kSpillSlot = 4
   };
 
   static const uword kInvalidLocation = 0;
@@ -68,7 +70,10 @@ class Location : public ValueObject {
   }
 
   // Unallocated locations.
+  // TODO(vegorov): writable register policy?
   enum Policy {
+    kAny,
+    kPrefersRegister,
     kRequiresRegister,
     kSameAsFirstInput,
   };
@@ -77,11 +82,23 @@ class Location : public ValueObject {
     return kind() == kUnallocated;
   }
 
+  bool IsRegisterBeneficial() {
+    return !Equals(Any());
+  }
+
   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 PrefersRegister() {
+    return UnallocatedLocation(kPrefersRegister);
+  }
+
   static Location RequiresRegister() {
     return UnallocatedLocation(kRequiresRegister);
   }
@@ -116,7 +133,22 @@ class Location : public ValueObject {
     return static_cast<Register>(payload());
   }
 
+  // Spill slots.
+  static Location SpillSlot(intptr_t spill_index) {
+    return Location(kSpillSlot, static_cast<uword>(spill_index));
+  }
+
+  bool IsSpillSlot() const {
+    return kind() == kSpillSlot;
+  }
+
+  intptr_t spill_index() const {
+    ASSERT(IsSpillSlot());
+    return static_cast<uword>(payload());
+  }
+
   const char* Name() const;
+  void PrintTo(BufferFormatter* f) const;
 
   // Compare two non-constant locations.
   bool Equals(Location other) const {
@@ -140,11 +172,11 @@ class Location : public ValueObject {
     return KindField::decode(value_);
   }
 
-  typedef BitField<Kind, 0, 2> KindField;
-  typedef BitField<uword, 2, kWordSize * kBitsPerByte - 2> PayloadField;
+  typedef BitField<Kind, 0, 3> KindField;
+  typedef BitField<uword, 3, kWordSize * kBitsPerByte - 2> PayloadField;
 
   // Layout for kUnallocated locations payload.
-  typedef BitField<Policy, 0, 1> PolicyField;
+  typedef BitField<Policy, 0, 2> PolicyField;
 
   // Location either contains kind and payload fields or a tagged handle for
   // a constant locations. Values of enumeration Kind are selected in such a