New linear scan 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,

[srdjan, 2012/07/22 23:27:33]

It seems that you are now using 3 bits with SpillSlot, however that does not
allow for merging kConstant with a handle. I see why it still works (spill slot
overlaps with kInvalid) but the comment is not clear enough. An alternative is
to merge spill-slots and registers, and a negative payload denotes spil-slot, a
positive a register.

[Vyacheslav Egorov (Google), 2012/07/23 11:48:39]

It works because no location kind has the same lower two bits as kConstant which
is intentional and declared below.

[srdjan, 2012/07/23 17:02:50]

I think the improved documentation in the other split off CL is good enough.

 // 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:
   // Constant payload can overlap with kind field so Kind values
   // have to be chosen in a way that their last 2 bits are never
   // the same as kConstant.

[srdjan, 2012/07/22 23:27:33]

Describe also what is the payload of each kind, and if it has any.

[Vyacheslav Egorov (Google), 2012/07/23 11:48:39]

Done.

   enum Kind {
     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 = 2,
 
     // Register location represents a fixed register.
-    kRegister = 3
+    kRegister = 3,
+
+    kSpillSlot = 4
   };
 
   static const uword kInvalidLocation = 0;
   static const uword kConstantMask = 0x3;
 
   Location() : value_(kInvalidLocation) {
     ASSERT(IsInvalid());
   }
 
   bool IsInvalid() const {
@@ skipping 11 matching lines @@
     ASSERT(&obj == &loc.constant());
     return loc;
   }
 
   const Object& constant() const {
     ASSERT(IsConstant());
     return *reinterpret_cast<const Object*>(value_ & ~kConstantMask);
   }
 
   // Unallocated locations.
+  // TODO(vegorov): writable register policy?
   enum Policy {
+    kAny,
+    kPrefersRegister,
     kRequiresRegister,
     kSameAsFirstInput,
   };
 
   bool IsUnallocated() const {
     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);
   }
 
   // The location of the first input to the instruction will be
   // used to replace this unallocated location.
   static Location SameAsFirstInput() {
     return UnallocatedLocation(kSameAsFirstInput);
   }
 
@@ skipping 14 matching lines @@
 
   bool IsRegister() const {
     return kind() == kRegister;
   }
 
   Register reg() const {
     ASSERT(IsRegister());
     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 {
     ASSERT(!IsConstant() && !other.IsConstant());
     return value_ == other.value_;
   }
 
  private:
   explicit Location(uword value) : value_(value) { }
 
   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;
+  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
   // way that none of them can be interpreted as a kConstant tag.
   uword value_;
 };
 
 
 // Specification of locations for inputs and output.
 class LocationSummary : public ZoneAllocated {
@@ skipping 69 matching lines @@
   GrowableArray<Location> temp_locations_;
   Location output_location_;
 
   const bool is_call_;
 };
 
 
 }  // namespace dart
 
 #endif  // VM_LOCATIONS_H_