Compile-time tuning: register/bb utilities

This CL yeilds about a 4% improvement in the compilation phase
of dex2oat (single-threaded; multi-threaded compilation is
more difficult to accurately measure).  The register utilities
could stand to be completely rewritten, but this gets most of the
easy benefit.

Next up: the assembly phase.

Change-Id: Ife5a474e9b1a6d9e501e888dda6749d34eb77e96

13 files changed, 52 insertions, 53 deletions

diff --git a/compiler/dex/growable_array.h b/compiler/dex/growable_array.h
index 8e2abfbaf1..639120a2ba 100644
--- a/compiler/dex/growable_array.h
+++ b/compiler/dex/growable_array.h
@@ -131,6 +131,11 @@ class GrowableArray {
       elem_list_[index]++;
     }
 
+    /*
+     * Remove an existing element from list.  If there are more than one copy
+     * of the element, only the first one encountered will be deleted.
+     */
+    // TODO: consider renaming this.
     void Delete(T element) {
       bool found = false;
       for (size_t i = 0; i < num_used_ - 1; i++) {
@@ -150,6 +155,11 @@ class GrowableArray {
 
     size_t Size() const { return num_used_; }
 
+    void SetSize(size_t new_size) {
+      Resize(new_size);
+      num_used_ = new_size;
+    }
+
     T* GetRawStorage() const { return elem_list_; }
 
     static void* operator new(size_t size, ArenaAllocator* arena) {
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 81702e3842..c72283e689 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -99,6 +99,7 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena)
       cur_block_(NULL),
       num_blocks_(0),
       current_code_item_(NULL),
+      block_map_(arena, 0, kGrowableArrayMisc),
       current_method_(kInvalidEntry),
       current_offset_(kInvalidEntry),
       def_count_(0),
@@ -210,18 +211,18 @@ BasicBlock* MIRGraph::FindBlock(unsigned int code_offset, bool split, bool creat
                                 BasicBlock** immed_pred_block_p) {
   BasicBlock* bb;
   unsigned int i;
-  SafeMap<unsigned int, BasicBlock*>::iterator it;
 
-  it = block_map_.find(code_offset);
-  if (it != block_map_.end()) {
-    return it->second;
-  } else if (!create) {
+  if (code_offset >= cu_->code_item->insns_size_in_code_units_) {
     return NULL;
   }
+  bb = block_map_.Get(code_offset);
+  if ((bb != NULL) || !create) {
+    return bb;
+  }
 
   if (split) {
-    for (i = 0; i < block_list_.Size(); i++) {
-      bb = block_list_.Get(i);
+    for (i = block_list_.Size(); i > 0; i--) {
+      bb = block_list_.Get(i - 1);
       if (bb->block_type != kDalvikByteCode) continue;
       /* Check if a branch jumps into the middle of an existing block */
       if ((code_offset > bb->start_offset) && (bb->last_mir_insn != NULL) &&
@@ -518,6 +519,8 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_
 
   // TODO: need to rework expansion of block list & try_block_addr when inlining activated.
   block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_);
+  block_map_.SetSize(block_map_.Size() + current_code_item_->insns_size_in_code_units_);
+
   // TODO: replace with explicit resize routine.  Using automatic extension side effect for now.
   try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_);
   try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_);
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index 15e15c380f..0244daec9d 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -728,7 +728,7 @@ class MIRGraph {
   BasicBlock* cur_block_;
   int num_blocks_;
   const DexFile::CodeItem* current_code_item_;
-  SafeMap<unsigned int, BasicBlock*> block_map_;  // FindBlock lookup cache.
+  GrowableArray<BasicBlock*> block_map_;         // FindBlock lookup cache.
   std::vector<DexCompilationUnit*> m_units_;     // List of methods included in this graph
   typedef std::pair<int, int> MIRLocation;       // Insert point, (m_unit_ index, offset)
   std::vector<MIRLocation> method_stack_;        // Include stack
diff --git a/compiler/dex/quick/arm/codegen_arm.h b/compiler/dex/quick/arm/codegen_arm.h
index 291319f258..1954fbac51 100644
--- a/compiler/dex/quick/arm/codegen_arm.h
+++ b/compiler/dex/quick/arm/codegen_arm.h
@@ -51,7 +51,6 @@ class ArmMir2Lir : public Mir2Lir {
     int AllocTypedTempPair(bool fp_hint, int reg_class);
     int S2d(int low_reg, int high_reg);
     int TargetReg(SpecialTargetRegister reg);
-    RegisterInfo* GetRegInfo(int reg);
     RegLocation GetReturnAlt();
     RegLocation GetReturnWideAlt();
     RegLocation LocCReturn();
diff --git a/compiler/dex/quick/arm/target_arm.cc b/compiler/dex/quick/arm/target_arm.cc
index 6cc3052da1..203a8cc55d 100644
--- a/compiler/dex/quick/arm/target_arm.cc
+++ b/compiler/dex/quick/arm/target_arm.cc
@@ -691,11 +691,6 @@ RegLocation ArmMir2Lir::GetReturnAlt() {
   return res;
 }
 
-ArmMir2Lir::RegisterInfo* ArmMir2Lir::GetRegInfo(int reg) {
-  return ARM_FPREG(reg) ? &reg_pool_->FPRegs[reg & ARM_FP_REG_MASK]
-      : &reg_pool_->core_regs[reg];
-}
-
 /* To be used when explicitly managing register use */
 void ArmMir2Lir::LockCallTemps() {
   LockTemp(r0);
diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index 3aa2f647c2..f13ab2db01 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -956,6 +956,8 @@ Mir2Lir::Mir2Lir(CompilationUnit* cu, MIRGraph* mir_graph, ArenaAllocator* arena
       throw_launchpads_(arena, 2048, kGrowableArrayThrowLaunchPads),
       suspend_launchpads_(arena, 4, kGrowableArraySuspendLaunchPads),
       intrinsic_launchpads_(arena, 2048, kGrowableArrayMisc),
+      tempreg_info_(arena, 20, kGrowableArrayMisc),
+      reginfo_map_(arena, 64, kGrowableArrayMisc),
       data_offset_(0),
       total_size_(0),
       block_label_list_(NULL),
diff --git a/compiler/dex/quick/mips/codegen_mips.h b/compiler/dex/quick/mips/codegen_mips.h
index b9cb720962..8d0b347a34 100644
--- a/compiler/dex/quick/mips/codegen_mips.h
+++ b/compiler/dex/quick/mips/codegen_mips.h
@@ -52,7 +52,6 @@ class MipsMir2Lir : public Mir2Lir {
     int AllocTypedTempPair(bool fp_hint, int reg_class);
     int S2d(int low_reg, int high_reg);
     int TargetReg(SpecialTargetRegister reg);
-    RegisterInfo* GetRegInfo(int reg);
     RegLocation GetReturnAlt();
     RegLocation GetReturnWideAlt();
     RegLocation LocCReturn();
diff --git a/compiler/dex/quick/mips/target_mips.cc b/compiler/dex/quick/mips/target_mips.cc
index 4ee5b23eb9..8e768dcf18 100644
--- a/compiler/dex/quick/mips/target_mips.cc
+++ b/compiler/dex/quick/mips/target_mips.cc
@@ -399,11 +399,6 @@ RegLocation MipsMir2Lir::GetReturnAlt() {
   return res;
 }
 
-MipsMir2Lir::RegisterInfo* MipsMir2Lir::GetRegInfo(int reg) {
-  return MIPS_FPREG(reg) ? &reg_pool_->FPRegs[reg & MIPS_FP_REG_MASK]
-            : &reg_pool_->core_regs[reg];
-}
-
 /* To be used when explicitly managing register use */
 void MipsMir2Lir::LockCallTemps() {
   LockTemp(rMIPS_ARG0);
diff --git a/compiler/dex/quick/mir_to_lir-inl.h b/compiler/dex/quick/mir_to_lir-inl.h
index f9ec19951e..0ca8d8de11 100644
--- a/compiler/dex/quick/mir_to_lir-inl.h
+++ b/compiler/dex/quick/mir_to_lir-inl.h
@@ -201,6 +201,11 @@ inline void Mir2Lir::SetupResourceMasks(LIR* lir) {
   SetupTargetResourceMasks(lir);
 }
 
+inline art::Mir2Lir::RegisterInfo* Mir2Lir::GetRegInfo(int reg) {
+  DCHECK(reginfo_map_.Get(reg) != NULL);
+  return reginfo_map_.Get(reg);
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_DEX_QUICK_MIR_TO_LIR_INL_H_
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index 5b4813416b..fdbc1d02b3 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -374,6 +374,7 @@ class Mir2Lir : public Backend {
     int SRegOffset(int s_reg);
     RegLocation GetReturnWide(bool is_double);
     RegLocation GetReturn(bool is_float);
+    RegisterInfo* GetRegInfo(int reg);
 
     // Shared by all targets - implemented in gen_common.cc.
     bool HandleEasyDivRem(Instruction::Code dalvik_opcode, bool is_div,
@@ -550,7 +551,6 @@ class Mir2Lir : public Backend {
     virtual int AllocTypedTempPair(bool fp_hint, int reg_class) = 0;
     virtual int S2d(int low_reg, int high_reg) = 0;
     virtual int TargetReg(SpecialTargetRegister reg) = 0;
-    virtual RegisterInfo* GetRegInfo(int reg) = 0;
     virtual RegLocation GetReturnAlt() = 0;
     virtual RegLocation GetReturnWideAlt() = 0;
     virtual RegLocation LocCReturn() = 0;
@@ -727,6 +727,8 @@ class Mir2Lir : public Backend {
     GrowableArray<LIR*> throw_launchpads_;
     GrowableArray<LIR*> suspend_launchpads_;
     GrowableArray<LIR*> intrinsic_launchpads_;
+    GrowableArray<RegisterInfo*> tempreg_info_;
+    GrowableArray<RegisterInfo*> reginfo_map_;
     /*
      * Holds mapping from native PC to dex PC for safepoints where we may deoptimize.
      * Native PC is on the return address of the safepointed operation.  Dex PC is for
diff --git a/compiler/dex/quick/ralloc_util.cc b/compiler/dex/quick/ralloc_util.cc
index db110aabd5..a0f22fc576 100644
--- a/compiler/dex/quick/ralloc_util.cc
+++ b/compiler/dex/quick/ralloc_util.cc
@@ -28,13 +28,9 @@ namespace art {
  * live until it is either explicitly killed or reallocated.
  */
 void Mir2Lir::ResetRegPool() {
-  for (int i = 0; i < reg_pool_->num_core_regs; i++) {
-    if (reg_pool_->core_regs[i].is_temp)
-      reg_pool_->core_regs[i].in_use = false;
-  }
-  for (int i = 0; i < reg_pool_->num_fp_regs; i++) {
-    if (reg_pool_->FPRegs[i].is_temp)
-      reg_pool_->FPRegs[i].in_use = false;
+  GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
+  for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
+    info->in_use = false;
   }
   // Reset temp tracking sanity check.
   if (kIsDebugBuild) {
@@ -48,13 +44,21 @@ void Mir2Lir::ResetRegPool() {
   */
 void Mir2Lir::CompilerInitPool(RegisterInfo* regs, int* reg_nums, int num) {
   for (int i = 0; i < num; i++) {
-    regs[i].reg = reg_nums[i];
+    uint32_t reg_number = reg_nums[i];
+    regs[i].reg = reg_number;
     regs[i].in_use = false;
     regs[i].is_temp = false;
     regs[i].pair = false;
     regs[i].live = false;
     regs[i].dirty = false;
     regs[i].s_reg = INVALID_SREG;
+    size_t map_size = reginfo_map_.Size();
+    if (reg_number >= map_size) {
+      for (uint32_t i = 0; i < ((reg_number - map_size) + 1); i++) {
+        reginfo_map_.Insert(NULL);
+      }
+    }
+    reginfo_map_.Put(reg_number, &regs[i]);
   }
 }
 
@@ -551,24 +555,13 @@ void Mir2Lir::ResetDefTracking() {
 }
 
 void Mir2Lir::ClobberAllRegs() {
-  RegisterInfo* p;
-  for (p = reg_pool_->core_regs; p < reg_pool_->core_regs + reg_pool_->num_core_regs; p++) {
-    if (p->is_temp) {
-      p->live = false;
-      p->s_reg = INVALID_SREG;
-      p->def_start = NULL;
-      p->def_end = NULL;
-      p->pair = false;
-    }
-  }
-  for (p = reg_pool_->FPRegs; p < reg_pool_->FPRegs + reg_pool_->num_fp_regs; p++) {
-    if (p->is_temp) {
-      p->live = false;
-      p->s_reg = INVALID_SREG;
-      p->def_start = NULL;
-      p->def_end = NULL;
-      p->pair = false;
-    }
+  GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
+  for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
+    info->live = false;
+    info->s_reg = INVALID_SREG;
+    info->def_start = NULL;
+    info->def_end = NULL;
+    info->pair = false;
   }
 }
 
@@ -624,11 +617,13 @@ void Mir2Lir::MarkLive(int reg, int s_reg) {
 
 void Mir2Lir::MarkTemp(int reg) {
   RegisterInfo* info = GetRegInfo(reg);
+  tempreg_info_.Insert(info);
   info->is_temp = true;
 }
 
 void Mir2Lir::UnmarkTemp(int reg) {
   RegisterInfo* info = GetRegInfo(reg);
+  tempreg_info_.Delete(info);
   info->is_temp = false;
 }
 
diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h
index 478654d0b4..0f281106b2 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -52,7 +52,6 @@ class X86Mir2Lir : public Mir2Lir {
     int AllocTypedTempPair(bool fp_hint, int reg_class);
     int S2d(int low_reg, int high_reg);
     int TargetReg(SpecialTargetRegister reg);
-    RegisterInfo* GetRegInfo(int reg);
     RegLocation GetReturnAlt();
     RegLocation GetReturnWideAlt();
     RegLocation LocCReturn();
diff --git a/compiler/dex/quick/x86/target_x86.cc b/compiler/dex/quick/x86/target_x86.cc
index 26accab360..94dd759e91 100644
--- a/compiler/dex/quick/x86/target_x86.cc
+++ b/compiler/dex/quick/x86/target_x86.cc
@@ -375,11 +375,6 @@ RegLocation X86Mir2Lir::GetReturnAlt() {
   return res;
 }
 
-X86Mir2Lir::RegisterInfo* X86Mir2Lir::GetRegInfo(int reg) {
-  return X86_FPREG(reg) ? &reg_pool_->FPRegs[reg & X86_FP_REG_MASK]
-                    : &reg_pool_->core_regs[reg];
-}
-
 /* To be used when explicitly managing register use */
 void X86Mir2Lir::LockCallTemps() {
   LockTemp(rX86_ARG0);