Introduce locations based code generation.

runtime/vm/locations.h

Index: runtime/vm/locations.h
diff --git a/runtime/vm/locations.h b/runtime/vm/locations.h
new file mode 100644
index 0000000000000000000000000000000000000000..19154f62e652997b54fd0182831d908125407959
--- /dev/null
+++ b/runtime/vm/locations.h
@@ -0,0 +1,162 @@
+// 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 UnallocatedLocation;
+
+// 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 number).

[srdjan, 2012/05/21 16:05:22]

What is register number? CPU register-number, for now, I guess.

[Vyacheslav Egorov (Google), 2012/05/21 19:53:46]

changed to register code and added reference to Register enum

+class Location : public ValueObject {
+ public:
+  enum Kind {
+    kInvalid,
+    kUnallocated,
+    kRegister
+  };
+
+  Location() : value_(KindField::encode(kInvalid)) { }
+
+  Kind kind() const { return KindField::decode(value_); }
+
+  uword value() const { return value_; }
+
+  inline Register AsRegister() const;
+
+ protected:
+  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_); }
+
+ private:
+  typedef BitField<Kind, 0, 2> KindField;
+  typedef BitField<uword, 2, kWordSize * kBitsPerByte - 2> PayloadField;
+
+  uword value_;

[Florian Schneider, 2012/05/21 18:33:38]

I think Location should be the same size on all platforms. Maybe use uint64_t
instead?

[srdjan, 2012/05/21 19:49:43]

What is the advantage of having them the same size on all platforms? 
The advantage of using uword is that it makes it much more efficient to pass
around on 32-bit architectures.

[Vyacheslav Egorov (Google), 2012/05/21 19:53:46]

Added a TODO, we will select size once we know the encoding (and how big
bitfields are better be).

[Vyacheslav Egorov (Google), 2012/05/21 19:53:46]

Fixed size is less error prone (it is easier to reason individual size of
bit-fields that constitute uword). For now I left it uword and added
TODO-comment that we can resolve later.

+};
+
+
+// UnallocatedLocation 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.
+class UnallocatedLocation : public Location {
+ public:
+  enum Policy {
+    kRegister,
+    kSameAsFirstInput
+  };
+
+  explicit UnallocatedLocation(Policy policy)
+      : Location(kUnallocated, PolicyField::encode(policy)) {
+  }
+
+  Policy policy() { return PolicyField::decode(payload()); }

[srdjan, 2012/05/21 16:05:22]

const?

[Vyacheslav Egorov (Google), 2012/05/21 19:53:46]

Done.

+
+  static UnallocatedLocation Cast(Location loc) {
+    ASSERT(loc.kind() == kUnallocated);
+    return UnallocatedLocation(loc.value());
+  }
+
+  // Any free register is suitable to replace this unallocated location.
+  static UnallocatedLocation Register() {
+    return UnallocatedLocation(kRegister);
+  }
+
+  // The location of the first input to the instruction will be
+  // used to replace this unallocated location.
+  static UnallocatedLocation SameAsFirstInput() {
+    return UnallocatedLocation(kSameAsFirstInput);
+  }
+
+ private:
+  explicit UnallocatedLocation(uword value) : Location(value) { }
+
+  typedef BitField<Policy, 0, 1> PolicyField;
+};
+
+
+// RegisterLocation represents a fixed register.
+class RegisterLocation : public Location {
+ public:
+  explicit RegisterLocation(Register reg)
+      : Location(kRegister, reg) { }
+
+  Register reg() const {
+    return static_cast<Register>(payload());
+  }
+
+  static RegisterLocation Cast(Location loc) {
+    ASSERT(loc.kind() == kRegister);
+    return RegisterLocation(loc.value());
+  }
+
+ private:
+  explicit RegisterLocation(uword value) : Location(value) { }
+};
+
+
+// Specification of locations for inputs and output.
+class LocationSummary : public ZoneAllocated {
+ public:
+  explicit LocationSummary(intptr_t count)
+      : input_locations_(count), output_location_() {
+    for (intptr_t i = 0; i < count; i++) {
+      input_locations_.Add(Location());
+    }
+  }
+
+  intptr_t count() const {
+    return input_locations_.length();
+  }
+
+  Location in(intptr_t index) const {
+    return input_locations_[index];
+  }
+
+  void set_in(intptr_t index, Location loc) {
+    input_locations_[index] = loc;
+  }
+
+  Location out() const {
+    return output_location_;
+  }
+
+  void set_out(Location loc) {
+    output_location_ = loc;
+  }
+
+  // Perform a greedy local register allocation.  Consider all register free.
+  void AllocateRegisters();
+
+ private:
+  // TODO(vegorov): replace with ZoneArray.
+  ZoneGrowableArray<Location> input_locations_;

[srdjan, 2012/05/21 16:05:22]

This is a value object -> GrowableArray  instead of ZoneGrowableArray.

[Vyacheslav Egorov (Google), 2012/05/21 19:53:46]

Done.

+  Location output_location_;
+};
+
+
+inline Register Location::AsRegister() const {
+  return RegisterLocation::Cast(*this).reg();
+}
+
+
+}  // namespace dart
+
+#endif  // VM_LOCATIONS_H_