Skeleton of a linear scan register allocator.

runtime/vm/locations.h

Index: runtime/vm/locations.h
diff --git a/runtime/vm/locations.h b/runtime/vm/locations.h
index 8a869b3d0c2f416673896692ea14f916571122b9..e1b28b8e0216cd2bbeaa46231cbab12e19d84854 100644
--- a/runtime/vm/locations.h
+++ b/runtime/vm/locations.h
@@ -11,6 +11,7 @@
 
 namespace dart {
 
+class BufferFormatter;
 
 // Location objects are used to connect register allocator and code generator.
 // Instruction templates used by code generator have a corresponding
@@ -21,21 +22,50 @@ namespace dart {
 // register code (value of the Register enumeration).
 class Location : public ValueObject {
  public:
+  static const intptr_t kInvalidLocation = 0;
+
+  // Contant payload can overlap with kind field so Kind values
+  // have to be choosen in a way that their last 2 bits are never
+  // the same as kConstant.
   enum Kind {
-    kInvalid,
+    kInvalid = 0,
+
+    kConstant = 1,
 
     // 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.
-    kUnallocated,
+    kUnallocated = 2,
 
     // Register location represents a fixed register.
-    kRegister
+    kRegister = 3
   };
 
-  Location() : value_(KindField::encode(kInvalid)) { }
+  Location() : value_(kInvalidLocation) {
+    ASSERT(IsInvalid());
+  }
+
+  bool IsInvalid() const {
+    return value_ == 0;

[srdjan, 2012/07/10 23:27:54]

s/0/kInvalidLocation/

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Done.

+  }
+
+  // Constants.
+  static const intptr_t kConstantMask = 0x3;

[srdjan, 2012/07/10 23:27:54]

Eventually move this definition between the comment and enum Kind.

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Done.

+  bool IsConstant() const {
+    ASSERT((kConstant & kConstantMask) == kConstant);
+    return (value_ & kConstantMask) == kConstant;
+  }
+
+  static Location Constant(const Object& obj) {
+    Location loc(reinterpret_cast<intptr_t>(&obj) | kConstant);

[srdjan, 2012/07/10 23:27:54]

Why no uword instead of intptr_t?

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Fixed! Thanks.

+    ASSERT(&obj == &loc.constant());
+    return loc;
+  }
 
-  Kind kind() const { return KindField::decode(value_); }
+  const Object& constant() {
+    ASSERT(IsConstant());
+    return *reinterpret_cast<const Object*>(value_ & ~kConstantMask);
+  }
 
   // Unallocated locations.
   enum Policy {
@@ -43,6 +73,10 @@ class Location : public ValueObject {
     kSameAsFirstInput,
   };
 
+  bool IsUnallocated() const {
+    return kind() == kUnallocated;
+  }
+
   static Location UnallocatedLocation(Policy policy) {
     return Location(kUnallocated, PolicyField::encode(policy));
   }
@@ -64,7 +98,7 @@ class Location : public ValueObject {
   }
 
   Policy policy() const {
-    ASSERT(kind() == kUnallocated);
+    ASSERT(IsUnallocated());
     return PolicyField::decode(payload());
   }
 
@@ -73,12 +107,24 @@ class Location : public ValueObject {
     return Location(kRegister, static_cast<uword>(reg));
   }
 
+  bool IsRegister() const {
+    return kind() == kRegister;
+  }
+
   Register reg() const {
-    ASSERT(kind() == kRegister);
+    ASSERT(IsRegister());
     return static_cast<Register>(payload());
   }
 
+  const char* Name() const;
+
+  bool Equals(Location other) const {
+    return value_ == other.value_;

[srdjan, 2012/07/10 23:27:54]

This does not work for kConstant. Should two constants with two identical
RawObjects, but different handles be the same? Please add comment.

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Added a comment and assertion. Constants are really encoded into locations only
because we need to have them as sources in parallel moves. Alternative would be
to leave locations for real locations and somehow fit constants into
MoveOperands instead. [might be a cleaner solution actually]. 

+  }
+
  private:
+  explicit Location(intptr_t value) : value_(value) { }

[srdjan, 2012/07/10 23:27:54]

Why not uword value?

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Mea culpa! Compiler did not complain and I already forgot that value_ is uword.

Fixed. 

+
   Location(Kind kind, uword payload)
       : value_(KindField::encode(kind) | PayloadField::encode(payload)) { }
 
@@ -86,6 +132,12 @@ class Location : public ValueObject {
     return PayloadField::decode(value_);
   }
 
+  // If current location is constant might return something that
+  // is not equal to any Kind.
+  Kind kind() const {
+    return KindField::decode(value_);
+  }
+
   typedef BitField<Kind, 0, 2> KindField;
   typedef BitField<uword, 2, kWordSize * kBitsPerByte - 2> PayloadField;
 
@@ -136,6 +188,10 @@ class LocationSummary : public ZoneAllocated {
     return input_locations_[index];
   }
 
+  Location* in_slot(intptr_t index) {
+    return &input_locations_[index];
+  }
+
   void set_in(intptr_t index, Location loc) {
     input_locations_[index] = loc;
   }
@@ -148,6 +204,10 @@ class LocationSummary : public ZoneAllocated {
     return temp_locations_[index];
   }
 
+  Location* temp_slot(intptr_t index) {
+    return &temp_locations_[index];
+  }
+
   void set_temp(intptr_t index, Location loc) {
     temp_locations_[index] = loc;
   }
@@ -156,6 +216,11 @@ class LocationSummary : public ZoneAllocated {
     return output_location_;
   }
 
+  Location* out_slot() {
+    return &output_location_;
+  }
+
+
   void set_out(Location loc) {
     output_location_ = loc;
   }
@@ -171,6 +236,8 @@ class LocationSummary : public ZoneAllocated {
     return is_branch_;
   }
 
+  void PrintTo(BufferFormatter* f) const;
+
   static LocationSummary* Make(intptr_t input_count,
                                Location out,
                                ContainsCall contains_call = kNoCall,