Quick: Rewrite Phi node insertion.

Delay Phi node insertion to the SSAConversion pass to allow
updating the vreg_to_ssa_map_ with INVALID_SREG when we omit
a Phi in the pruned SSA form.

Change-Id: I450dee21f7dc4353d25fc66f4d0ee01671de6e0e

7 files changed, 48 insertions, 42 deletions

diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index f09d1ae6d0..a1f4294355 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -1198,11 +1198,30 @@ void MIRGraph::DataFlowSSAFormatExtended(MIR* mir) {
 
 /* Entry function to convert a block into SSA representation */
 bool MIRGraph::DoSSAConversion(BasicBlock* bb) {
-  MIR* mir;
-
   if (bb->data_flow_info == NULL) return false;
 
-  for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+  /*
+   * Pruned SSA form: Insert phi nodes for each dalvik register marked in phi_node_blocks
+   * only if the dalvik register is in the live-in set.
+   */
+  BasicBlockId bb_id = bb->id;
+  for (int dalvik_reg = GetNumOfCodeAndTempVRs() - 1; dalvik_reg >= 0; dalvik_reg--) {
+    if (temp_.ssa.phi_node_blocks[dalvik_reg]->IsBitSet(bb_id)) {
+      if (!bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) {
+        /* Variable will be clobbered before being used - no need for phi */
+        vreg_to_ssa_map_[dalvik_reg] = INVALID_SREG;
+        continue;
+      }
+      MIR *phi = NewMIR();
+      phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
+      phi->dalvikInsn.vA = dalvik_reg;
+      phi->offset = bb->start_offset;
+      phi->m_unit_index = 0;  // Arbitrarily assign all Phi nodes to outermost method.
+      bb->PrependMIR(phi);
+    }
+  }
+
+  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
     mir->ssa_rep =
         static_cast<struct SSARepresentation *>(arena_->Alloc(sizeof(SSARepresentation),
                                                               kArenaAllocDFInfo));
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 93a31e921a..92f960eb4c 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -1798,7 +1798,8 @@ void MIRGraph::SSATransformationEnd() {
 
   temp_.ssa.num_vregs = 0u;
   temp_.ssa.work_live_vregs = nullptr;
-  temp_.ssa.def_block_matrix = nullptr;
+  DCHECK(temp_.ssa.def_block_matrix == nullptr);
+  temp_.ssa.phi_node_blocks = nullptr;
   DCHECK(temp_scoped_alloc_.get() != nullptr);
   temp_scoped_alloc_.reset();
 
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index 5914245f5b..27dca658e8 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -1201,7 +1201,7 @@ class MIRGraph {
   void ComputeDominators();
   void CompilerInitializeSSAConversion();
   virtual void InitializeBasicBlockDataFlow();
-  void InsertPhiNodes();
+  void FindPhiNodeBlocks();
   void DoDFSPreOrderSSARename(BasicBlock* block);
 
   bool DfsOrdersUpToDate() const {
@@ -1378,6 +1378,7 @@ class MIRGraph {
       size_t num_vregs;
       ArenaBitVector* work_live_vregs;
       ArenaBitVector** def_block_matrix;  // num_vregs x num_blocks_.
+      ArenaBitVector** phi_node_blocks;  // num_vregs x num_blocks_.
     } ssa;
     // Global value numbering.
     struct {
diff --git a/compiler/dex/pass_driver_me_post_opt.cc b/compiler/dex/pass_driver_me_post_opt.cc
index 4e1322702f..a8b8a54033 100644
--- a/compiler/dex/pass_driver_me_post_opt.cc
+++ b/compiler/dex/pass_driver_me_post_opt.cc
@@ -37,7 +37,7 @@ void PassDriverMEPostOpt::SetupPasses(PassManager* pass_manager) {
   pass_manager->AddPass(new InitializeSSATransformation);
   pass_manager->AddPass(new ClearPhiInstructions);
   pass_manager->AddPass(new DefBlockMatrix);
-  pass_manager->AddPass(new CreatePhiNodes);
+  pass_manager->AddPass(new FindPhiNodeBlocksPass);
   pass_manager->AddPass(new SSAConversion);
   pass_manager->AddPass(new PhiNodeOperands);
   pass_manager->AddPass(new PerformInitRegLocations);
diff --git a/compiler/dex/post_opt_passes.h b/compiler/dex/post_opt_passes.h
index a3dbc5a273..1ab862503b 100644
--- a/compiler/dex/post_opt_passes.h
+++ b/compiler/dex/post_opt_passes.h
@@ -189,19 +189,19 @@ class DefBlockMatrix : public PassMEMirSsaRep {
 };
 
 /**
- * @class CreatePhiNodes
- * @brief Pass to create the phi nodes after SSA calculation
+ * @class FindPhiNodeBlocksPass
+ * @brief Pass to find out where we need to insert the phi nodes for the SSA conversion.
  */
-class CreatePhiNodes : public PassMEMirSsaRep {
+class FindPhiNodeBlocksPass : public PassMEMirSsaRep {
  public:
-  CreatePhiNodes() : PassMEMirSsaRep("CreatePhiNodes", kNoNodes) {
+  FindPhiNodeBlocksPass() : PassMEMirSsaRep("FindPhiNodeBlocks", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
     DCHECK(data != nullptr);
     CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
     DCHECK(c_unit != nullptr);
-    c_unit->mir_graph.get()->InsertPhiNodes();
+    c_unit->mir_graph.get()->FindPhiNodeBlocks();
   }
 };
 
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index 6bd49de989..f15f9be6ed 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -463,24 +463,28 @@ bool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) {
   return false;
 }
 
-/* Insert phi nodes to for each variable to the dominance frontiers */
-void MIRGraph::InsertPhiNodes() {
-  int dalvik_reg;
-  ArenaBitVector* phi_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
-      temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapPhi);
-  ArenaBitVector* input_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
-      temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapInputBlocks);
-
+/* For each dalvik reg, find blocks that need phi nodes according to the dominance frontiers. */
+void MIRGraph::FindPhiNodeBlocks() {
   RepeatingPostOrderDfsIterator iter(this);
   bool change = false;
   for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
     change = ComputeBlockLiveIns(bb);
   }
 
+  ArenaBitVector* phi_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
+      temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapBMatrix);
+
+  // Reuse the def_block_matrix storage for phi_node_blocks.
+  ArenaBitVector** def_block_matrix = temp_.ssa.def_block_matrix;
+  ArenaBitVector** phi_node_blocks = def_block_matrix;
+  DCHECK(temp_.ssa.phi_node_blocks == nullptr);
+  temp_.ssa.phi_node_blocks = phi_node_blocks;
+  temp_.ssa.def_block_matrix = nullptr;
+
   /* Iterate through each Dalvik register */
-  for (dalvik_reg = GetNumOfCodeAndTempVRs() - 1; dalvik_reg >= 0; dalvik_reg--) {
-    input_blocks->Copy(temp_.ssa.def_block_matrix[dalvik_reg]);
+  for (int dalvik_reg = GetNumOfCodeAndTempVRs() - 1; dalvik_reg >= 0; dalvik_reg--) {
     phi_blocks->ClearAllBits();
+    ArenaBitVector* input_blocks = def_block_matrix[dalvik_reg];
     do {
       // TUNING: When we repeat this, we could skip indexes from the previous pass.
       for (uint32_t idx : input_blocks->Indexes()) {
@@ -491,23 +495,8 @@ void MIRGraph::InsertPhiNodes() {
       }
     } while (input_blocks->Union(phi_blocks));
 
-    /*
-     * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik
-     * register is in the live-in set.
-     */
-    for (uint32_t idx : phi_blocks->Indexes()) {
-      BasicBlock* phi_bb = GetBasicBlock(idx);
-      /* Variable will be clobbered before being used - no need for phi */
-      if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) {
-        continue;
-      }
-      MIR *phi = NewMIR();
-      phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
-      phi->dalvikInsn.vA = dalvik_reg;
-      phi->offset = phi_bb->start_offset;
-      phi->m_unit_index = 0;  // Arbitrarily assign all Phi nodes to outermost method.
-      phi_bb->PrependMIR(phi);
-    }
+    def_block_matrix[dalvik_reg] = phi_blocks;
+    phi_blocks = input_blocks;  // Reuse the bit vector in next iteration.
   }
 }
 
diff --git a/compiler/utils/arena_bit_vector.h b/compiler/utils/arena_bit_vector.h
index 34f1ca9129..e5e1b709e9 100644
--- a/compiler/utils/arena_bit_vector.h
+++ b/compiler/utils/arena_bit_vector.h
@@ -35,14 +35,10 @@ enum OatBitMapKind {
   kBitMapDominators,
   kBitMapIDominated,
   kBitMapDomFrontier,
-  kBitMapPhi,
-  kBitMapTmpBlocks,
-  kBitMapInputBlocks,
   kBitMapRegisterV,
   kBitMapTempSSARegisterV,
   kBitMapNullCheck,
   kBitMapClInitCheck,
-  kBitMapTmpBlockV,
   kBitMapPredecessors,
   kNumBitMapKinds
 };