Introduce locations based code generation.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index e5bd8d199788445cfba6b9f1a5d31cd08788015f..fa3817521976c66db0f667989a6d52b5f9153fe8 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -16,6 +16,7 @@ namespace dart {
 class BitVector;
 class FlowGraphVisitor;
 class LocalVariable;
+class LocationSummary;
 
 // M is a two argument macro.  It is applied to each concrete value's
 // typename and classname.
@@ -108,6 +109,15 @@ class Computation : public ZoneAllocated {
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
+  // Returns structure describing location constraints required
+  // to emit native code for this computation.
+  virtual LocationSummary* GetLocationSummary() const {
+    // TODO(vegorov): This should be pure virtual method.
+    // However we are temporary using NULL for instructions that
+    // were not converted to the location based code generation yet.
+    return NULL;
+  }
+
  private:
   friend class Instruction;
   static intptr_t GetNextCid(Isolate* isolate) {
@@ -449,6 +459,7 @@ class StrictCompareComp : public TemplateComputation<2> {
     ASSERT((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kNE_STRICT));
     inputs_[0] = left;
     inputs_[1] = right;
+    location_summary_ = MakeLocationSummary();
   }
 
   DECLARE_COMPUTATION(StrictCompare)
@@ -459,9 +470,18 @@ class StrictCompareComp : public TemplateComputation<2> {
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
+  virtual LocationSummary* GetLocationSummary() const {
+    return location_summary_;
+  }
+
+  // Platform specific summary factory for this instruction.
+  LocationSummary* MakeLocationSummary();
+
  private:
   const Token::Kind kind_;
 
+  LocationSummary* location_summary_;
+
   DISALLOW_COPY_AND_ASSIGN(StrictCompareComp);
 };
 
@@ -1363,6 +1383,15 @@ FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
     return AbstractType::null();
   }
 
+  // Returns structure describing location constraints required
+  // to emit native code for this instruction.
+  virtual LocationSummary* GetLocationSummary() const {
+    // TODO(vegorov): This should be pure virtual method.
+    // However we are temporary using NULL for instructions that
+    // were not converted to the location based code generation yet.
+    return NULL;

[srdjan, 2012/05/18 18:00:14]

Will we need this? I would guess that we are only interested in the output(s) of
LocationSummary.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Some instructions also pop and push things (see for example ReThrow). Thus is
seems that they need a full location information not just output.

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

Please add comment why this is needed (essentially what you replied)

+  }
+
  private:
   intptr_t cid_;
   ICData* ic_data_;
@@ -1567,6 +1596,10 @@ class DoInstr : public Instruction {
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
+  virtual LocationSummary* GetLocationSummary() const {
+    return computation()->GetLocationSummary();
+  }
+
  private:
   Computation* computation_;
   Instruction* successor_;
@@ -1615,6 +1648,10 @@ class BindInstr : public Definition {
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
+  virtual LocationSummary* GetLocationSummary() const {
+    return computation()->GetLocationSummary();
+  }
+
  private:
   Computation* computation_;
   Instruction* successor_;
@@ -1802,6 +1839,118 @@ class FlowGraphVisitor : public ValueObject {
 };
 

[srdjan, 2012/05/18 18:00:14]

All these classes need a small amount of comment, describing their intent.
Without them I am not certain what they are supposed to do.
Also, they seem complex enough to be located in their own file.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Commented, moved to location.{cc,h}

 
+class Location : public ValueObject {

[srdjan, 2012/05/18 18:00:14]

Add comment about formatting.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Done.

+ public:
+  enum Kind {
+    INVALID,
+    UNALLOCATED,
+    REGISTER

[srdjan, 2012/05/18 18:00:14]

enums are typically named kInvalid, kUnallocated etc. Should it also contain
kStack or kAddress?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Renamed to match style. 

Did not add kStack/kAddress because I think that I should not add anything that
would not be used (and thus tested) in this CL. We should try to grow Location
functionality organically (it definitely will become more rich as we add more
sofisticated instructions/register allocation)

+  };
+
+  Location() : value_(KindField::encode(INVALID)) { }
+
+  Kind kind() const { return KindField::decode(value_); }
+
+  uword value() const { return value_; }

[srdjan, 2012/05/18 18:00:14]

This belongs in protected?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Can't be in the protected because it is used from static methods in derived
classes which does not work. 

[this is a very strange part of C++: derived classes have access to protected
members if and only if access is performed through an object of derived type. if
method on derived class tries to call a protected method on an object of base
class then compiler will complain, more information is in standard itself: see
section 11.5]

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

Ha!

+
+ protected:
+  explicit Location(uword value) : value_(value) { }

[srdjan, 2012/05/18 18:00:14]

Do you need this constructor?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

It is called by similar constructors of children which are used in Cast methods.

+
+  Location(Kind kind, uword payload)
+      : value_(KindField::encode(kind) | PayloadField::encode(payload)) { }

[srdjan, 2012/05/18 18:00:14]

BitField::encode needs range checks.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

It does use is_valid(), I think that should be enough. 

+
+  uword payload() const { return PayloadField::decode(value_); }
+
+ private:
+  typedef BitField<Kind, 0, 2> KindField;
+  typedef BitField<uword, 2, kWordSize * kBitsPerByte - 2> PayloadField;
+
+  uword value_;

[srdjan, 2012/05/18 18:00:14]

const

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

If I put const here I would need to implement my own assignment operator which
writes into a const field. I don't think it's worth it. There is no public
setter should nobody would modify it.

+};
+
+
+class UnallocatedLocation : public Location {
+ public:
+  enum Policy {
+    REGISTER,
+    SAME_AS_FIRST_INPUT
+  };
+
+  explicit UnallocatedLocation(Policy policy)
+      : Location(UNALLOCATED, PolicyField::encode(policy)) {
+  }
+
+  Policy policy() { return PolicyField::decode(payload()); }
+
+  static UnallocatedLocation Cast(Location loc) {

[srdjan, 2012/05/18 18:00:14]

Maybe AsUnaloocatedLocation instead of Cast? And doesn't it belong into
Location?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

I can put helper methods into Location but then I will still need Cast methods
to implement casting in a sane way. I don't want to implement it as:

*reinterpret_cast<UnallocatedLocation*>(this)

Alternative approach would be to use fake this pointers and pass Location*
everywhere instead of Location (in a similar fashion to V8's tagged pointers)
but this is very ugly.

+    ASSERT(loc.kind() == UNALLOCATED);
+    return UnallocatedLocation(loc.value());
+  }
+
+ private:
+  explicit UnallocatedLocation(uword value) : Location(value) { }
+
+  typedef BitField<Policy, 0, 1> PolicyField;
+};
+
+
+class RegisterLocation : public Location {
+ public:
+  explicit RegisterLocation(Register reg)

[srdjan, 2012/05/18 18:00:14]

This cannot handle XMMRegisters, maybe add the register kind?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

see above about organically growing Location as we start using more complicated
functionality.

+      : Location(REGISTER, reg) { }
+
+  Register reg() const {
+    return static_cast<Register>(payload());
+  }
+
+  static RegisterLocation Cast(Location loc) {
+    ASSERT(loc.kind() == REGISTER);
+    return RegisterLocation(loc.value());
+  }
+
+ private:
+  explicit RegisterLocation(uword value) : Location(value) { }
+};
+
+
+class LocationSummary : public ZoneAllocated {

[srdjan, 2012/05/18 18:00:14]

I am not too happy with the name LocationSummary as it sounds like the result of
an aggregation. Maybe ComputationLocations?

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

ComputationLocations does not work because instructions can also have one.

+ public:
+  explicit LocationSummary(intptr_t count)
+      : count_(count) {
+    Zone* zone = Isolate::Current()->current_zone();

[srdjan, 2012/05/18 18:00:14]

Use ZoneGrowableArray fro now, and we can replace it with newly to be added
ZoneArray which does all the range checks and correct allocation.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Using ZoneGrowableArray. Added TODO to use ZoneArray.

+    input_locations_ = reinterpret_cast<Location*>(
+        zone->Allocate(sizeof(Location) * count));
+  }
+
+  intptr_t InputLocationsCount() const {
+    return count_;
+  }
+
+  Location InputLocationAt(intptr_t index) const {
+    ASSERT(0 <= index && index < count_);
+    return input_locations_[index];
+  }
+
+  void SetInputLocationAt(intptr_t index, Location loc) {
+    ASSERT(0 <= index && index < count_);
+    input_locations_[index] = loc;
+  }
+
+  Location result_location() const {
+    return result_location_;
+  }
+
+  void set_result_location(Location loc) {
+    result_location_ = loc;
+  }
+
+ private:
+  intptr_t count_;
+  Location* input_locations_;
+  Location result_location_;
+};
+
+
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_