Introduce locations based code generation.

runtime/vm/intermediate_language.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_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
 #include "vm/handles_impl.h"
 #include "vm/object.h"
 
 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.
 #define FOR_EACH_VALUE(M)                                                      \
   M(Use, UseVal)                                                               \
   M(Constant, ConstantVal)                                                     \
 
 
 // M is a two argument macro.  It is applied to each concrete instruction's
 // (including the values) typename and classname.
@@ skipping 72 matching lines @@
   // frame-allocated locals assigned to by the computation.
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
   virtual const char* DebugName() const = 0;
 
   // Printing support. These functions are sometimes overridden for custom
   // formatting. Otherwise, it prints in the format "opcode(op1, op2, op3)".
   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) {
     intptr_t tmp = isolate->computation_id();
     isolate->set_computation_id(tmp + 1);
     return tmp;
   }
   static ICData* GetICDataForCid(intptr_t cid, Isolate* isolate) {
     if (isolate->ic_data_array() == Array::null()) {
       return NULL;
@@ skipping 321 matching lines @@
 };
 
 
 class StrictCompareComp : public TemplateComputation<2> {
  public:
   StrictCompareComp(Token::Kind kind, Value* left, Value* right)
       : kind_(kind) {
     ASSERT((kind_ == Token::kEQ_STRICT) || (kind_ == Token::kNE_STRICT));
     inputs_[0] = left;
     inputs_[1] = right;
+    location_summary_ = MakeLocationSummary();
   }
 
   DECLARE_COMPUTATION(StrictCompare)
 
   Token::Kind kind() const { return kind_; }
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
   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);
 };
 
 
 class EqualityCompareComp : public TemplateComputation<2> {
  public:
   EqualityCompareComp(intptr_t token_index,
                       intptr_t try_index,
                       Value* left,
                       Value* right)
@@ skipping 881 matching lines @@
   virtual type##Instr* As##type() { return NULL; }
 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
   // Static type of the instruction.
   virtual RawAbstractType* StaticType() const {
     UNREACHABLE();
     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_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 // Basic block entries are administrative nodes.  There is a distinguished
 // graph entry with no predecessor.  Joins are the only nodes with multiple
 // predecessors.  Targets are all other basic block entries.  The types
@@ skipping 184 matching lines @@
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
+  virtual LocationSummary* GetLocationSummary() const {
+    return computation()->GetLocationSummary();
+  }
+
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
 class Definition : public Instruction {
  public:
@@ skipping 28 matching lines @@
     successor_ = instr;
   }
 
   // Static type of the underlying computation.
   virtual RawAbstractType* StaticType() const {
     return computation()->StaticType();
   }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
+  virtual LocationSummary* GetLocationSummary() const {
+    return computation()->GetLocationSummary();
+  }
+
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class ReturnInstr : public Instruction {
  public:
@@ skipping 165 matching lines @@
   // block_order for reverse iterations.
   intptr_t reverse_index(intptr_t index) {
     return block_order_.length() - index - 1;
   }
 
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 

[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_