Skeleton of a linear scan register allocator.

runtime/vm/locations.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_LOCATIONS_H_
 #define VM_LOCATIONS_H_
 
 #include "vm/allocation.h"
 #include "vm/assembler.h"
 #include "vm/bitfield.h"
 
 namespace dart {
 
+class BufferFormatter;
 
 // Location objects are used to connect register allocator and code generator.
 // Instruction templates used by code generator have a corresponding
 // LocationSummary object which specifies expected location for every input
 // and output.
 // Each location is encoded as a single word: low 2 bits denote location kind,
 // rest is kind specific location payload e.g. for REGISTER kind payload is
 // 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());
+  }
 
-  Kind kind() const { return KindField::decode(value_); }
+  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;
+  }
+
+  const Object& constant() {
+    ASSERT(IsConstant());
+    return *reinterpret_cast<const Object*>(value_ & ~kConstantMask);
+  }
 
   // Unallocated locations.
   enum Policy {
     kRequiresRegister,
     kSameAsFirstInput,
   };
 
+  bool IsUnallocated() const {
+    return kind() == kUnallocated;
+  }
+
   static Location UnallocatedLocation(Policy policy) {
     return Location(kUnallocated, PolicyField::encode(policy));
   }
 
   // Any free register is suitable to replace this unallocated location.
   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);
   }
 
   // Empty location. Used if there the location should be ignored.
   static Location NoLocation() {
     return Location();
   }
 
   Policy policy() const {
-    ASSERT(kind() == kUnallocated);
+    ASSERT(IsUnallocated());
     return PolicyField::decode(payload());
   }
 
   // Register locations.
   static Location RegisterLocation(Register reg) {
     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)) { }
 
   uword payload() const {
     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;
 
   // Layout for kUnallocated locations payload.
   typedef BitField<Policy, 0, 1> PolicyField;
 
   // TODO(vegorov): choose fixed size for this field.
   uword value_;

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

Explain that this can be Kind or an encoded Object handle

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

Done.

 };
 
 
 // Specification of locations for inputs and output.
 class LocationSummary : public ZoneAllocated {
  public:
   enum ContainsCall {
     kNoCall,
     kCall,
   };
@@ skipping 22 matching lines @@
   }
 
   intptr_t input_count() const {
     return input_locations_.length();
   }
 
   Location in(intptr_t index) const {
     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;
   }
 
   intptr_t temp_count() const {
     return temp_locations_.length();
   }
 
   Location temp(intptr_t index) const {
     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;
   }
 
   Location out() const {
     return output_location_;
   }
 
+  Location* out_slot() {
+    return &output_location_;
+  }
+
+
   void set_out(Location loc) {
     output_location_ = loc;
   }
 
   bool is_call() const {
     return is_call_;
   }
 
   // TODO(vegorov): this is a temporary solution. Once we will start removing
   // comparison operations from the flow graph when they are fused with a branch
   // we should eliminate this.
   bool is_branch() const {
     return is_branch_;
   }
 
+  void PrintTo(BufferFormatter* f) const;
+
   static LocationSummary* Make(intptr_t input_count,
                                Location out,
                                ContainsCall contains_call = kNoCall,
                                ContainsBranch contains_branch = kNoBranch);
 
  private:
   // TODO(vegorov): replace with ZoneArray.
   GrowableArray<Location> input_locations_;
   GrowableArray<Location> temp_locations_;
   Location output_location_;
 
   const bool is_call_;
   const bool is_branch_;
 };
 
 
 }  // namespace dart
 
 #endif  // VM_LOCATIONS_H_