Merge "Quick: Rewrite Phi node insertion."
diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index f09d1ae..a1f4294 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -1198,11 +1198,30 @@
/* 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 93a31e9..92f960e 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -1798,7 +1798,8 @@
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 5914245..27dca65 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -1201,7 +1201,7 @@
void ComputeDominators();
void CompilerInitializeSSAConversion();
virtual void InitializeBasicBlockDataFlow();
- void InsertPhiNodes();
+ void FindPhiNodeBlocks();
void DoDFSPreOrderSSARename(BasicBlock* block);
bool DfsOrdersUpToDate() const {
@@ -1378,6 +1378,7 @@
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 4e13227..a8b8a54 100644
--- a/compiler/dex/pass_driver_me_post_opt.cc
+++ b/compiler/dex/pass_driver_me_post_opt.cc
@@ -37,7 +37,7 @@
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 a3dbc5a..1ab8625 100644
--- a/compiler/dex/post_opt_passes.h
+++ b/compiler/dex/post_opt_passes.h
@@ -189,19 +189,19 @@
};
/**
- * @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 6bd49de..f15f9be 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -463,24 +463,28 @@
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 @@
}
} 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 34f1ca9..e5e1b70 100644
--- a/compiler/utils/arena_bit_vector.h
+++ b/compiler/utils/arena_bit_vector.h
@@ -35,14 +35,10 @@
kBitMapDominators,
kBitMapIDominated,
kBitMapDomFrontier,
- kBitMapPhi,
- kBitMapTmpBlocks,
- kBitMapInputBlocks,
kBitMapRegisterV,
kBitMapTempSSARegisterV,
kBitMapNullCheck,
kBitMapClInitCheck,
- kBitMapTmpBlockV,
kBitMapPredecessors,
kNumBitMapKinds
};
