Add a linear scan register allocator to the optimizing compiler.

This is a "by-the-book" implementation. It currently only deals
with allocating registers, with no hint optimizations.

The changes remaining to make it functional are:
- Allocate spill slots.
- Resolution and placements of Move instructions.
- Connect it to the code generator.

Change-Id: Ie0b2f6ba1b98da85425be721ce4afecd6b4012a4

1 files changed, 19 insertions, 17 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 476f24e..b1c8016 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -276,6 +276,7 @@ class HBasicBlock : public ArenaObject {
   HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
   const HInstructionList& GetInstructions() const { return instructions_; }
   const HInstructionList& GetPhis() const { return phis_; }
+  HInstruction* GetFirstPhi() const { return phis_.first_instruction_; }
 
   void AddSuccessor(HBasicBlock* block) {
     successors_.Add(block);
@@ -397,9 +398,9 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 #define DECLARE_INSTRUCTION(type)                          \
-  virtual void Accept(HGraphVisitor* visitor);             \
   virtual const char* DebugName() const { return #type; }  \
   virtual H##type* As##type() { return this; }             \
+  virtual void Accept(HGraphVisitor* visitor)              \
 
 template <typename T>
 class HUseListNode : public ArenaObject {
@@ -734,7 +735,7 @@ class HReturnVoid : public HTemplateInstruction<0> {
  public:
   HReturnVoid() { }
 
-  DECLARE_INSTRUCTION(ReturnVoid)
+  DECLARE_INSTRUCTION(ReturnVoid);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
@@ -748,7 +749,7 @@ class HReturn : public HTemplateInstruction<1> {
     SetRawInputAt(0, value);
   }
 
-  DECLARE_INSTRUCTION(Return)
+  DECLARE_INSTRUCTION(Return);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HReturn);
@@ -761,7 +762,7 @@ class HExit : public HTemplateInstruction<0> {
  public:
   HExit() { }
 
-  DECLARE_INSTRUCTION(Exit)
+  DECLARE_INSTRUCTION(Exit);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HExit);
@@ -776,7 +777,7 @@ class HGoto : public HTemplateInstruction<0> {
     return GetBlock()->GetSuccessors().Get(0);
   }
 
-  DECLARE_INSTRUCTION(Goto)
+  DECLARE_INSTRUCTION(Goto);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HGoto);
@@ -798,7 +799,7 @@ class HIf : public HTemplateInstruction<1> {
     return GetBlock()->GetSuccessors().Get(1);
   }
 
-  DECLARE_INSTRUCTION(If)
+  DECLARE_INSTRUCTION(If);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HIf);
@@ -837,7 +838,7 @@ class HEqual : public HBinaryOperation {
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimBoolean; }
 
-  DECLARE_INSTRUCTION(Equal)
+  DECLARE_INSTRUCTION(Equal);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HEqual);
@@ -848,7 +849,7 @@ class HLocal : public HTemplateInstruction<0> {
  public:
   explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { }
 
-  DECLARE_INSTRUCTION(Local)
+  DECLARE_INSTRUCTION(Local);
 
   uint16_t GetRegNumber() const { return reg_number_; }
 
@@ -870,7 +871,7 @@ class HLoadLocal : public HTemplateInstruction<1> {
 
   HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
 
-  DECLARE_INSTRUCTION(LoadLocal)
+  DECLARE_INSTRUCTION(LoadLocal);
 
  private:
   const Primitive::Type type_;
@@ -889,7 +890,7 @@ class HStoreLocal : public HTemplateInstruction<2> {
 
   HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
 
-  DECLARE_INSTRUCTION(StoreLocal)
+  DECLARE_INSTRUCTION(StoreLocal);
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HStoreLocal);
@@ -904,7 +905,7 @@ class HIntConstant : public HTemplateInstruction<0> {
   int32_t GetValue() const { return value_; }
   virtual Primitive::Type GetType() const { return Primitive::kPrimInt; }
 
-  DECLARE_INSTRUCTION(IntConstant)
+  DECLARE_INSTRUCTION(IntConstant);
 
  private:
   const int32_t value_;
@@ -920,7 +921,7 @@ class HLongConstant : public HTemplateInstruction<0> {
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimLong; }
 
-  DECLARE_INSTRUCTION(LongConstant)
+  DECLARE_INSTRUCTION(LongConstant);
 
  private:
   const int64_t value_;
@@ -980,7 +981,7 @@ class HInvokeStatic : public HInvoke {
 
   uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; }
 
-  DECLARE_INSTRUCTION(InvokeStatic)
+  DECLARE_INSTRUCTION(InvokeStatic);
 
  private:
   const uint32_t index_in_dex_cache_;
@@ -1000,7 +1001,7 @@ class HNewInstance : public HTemplateInstruction<0> {
   // Calls runtime so needs an environment.
   virtual bool NeedsEnvironment() const { return true; }
 
-  DECLARE_INSTRUCTION(NewInstance)
+  DECLARE_INSTRUCTION(NewInstance);
 
  private:
   const uint32_t dex_pc_;
@@ -1091,15 +1092,16 @@ class HPhi : public HInstruction {
   void AddInput(HInstruction* input);
 
   virtual Primitive::Type GetType() const { return type_; }
+  void SetType(Primitive::Type type) { type_ = type; }
 
   uint32_t GetRegNumber() const { return reg_number_; }
 
-  DECLARE_INSTRUCTION(Phi)
+  DECLARE_INSTRUCTION(Phi);
 
  protected:
   GrowableArray<HInstruction*> inputs_;
   const uint32_t reg_number_;
-  const Primitive::Type type_;
+  Primitive::Type type_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HPhi);
@@ -1179,7 +1181,7 @@ class HParallelMove : public HTemplateInstruction<0> {
 
   size_t NumMoves() const { return moves_.Size(); }
 
-  DECLARE_INSTRUCTION(ParallelMove)
+  DECLARE_INSTRUCTION(ParallelMove);
 
  private:
   GrowableArray<MoveOperands*> moves_;