Merge "Quick: Improve the BBCombine pass."
diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h
index 3b1be51..fba0863 100644
--- a/compiler/dex/bb_optimizations.h
+++ b/compiler/dex/bb_optimizations.h
@@ -271,7 +271,8 @@
DCHECK(data != nullptr);
CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
DCHECK(c_unit != nullptr);
- return ((c_unit->disable_opt & (1 << kSuppressExceptionEdges)) != 0);
+ return c_unit->mir_graph->HasTryCatchBlocks() ||
+ ((c_unit->disable_opt & (1 << kSuppressExceptionEdges)) != 0);
}
bool Worker(PassDataHolder* data) const;
diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index 6d3f229..0a6924c 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -1403,7 +1403,7 @@
GetBlockName(bb, block_name1);
GetBlockName(pred_bb, block_name2);
DumpCFG("/sdcard/cfg/", false);
- LOG(FATAL) << "Successor " << block_name1 << "not found from "
+ LOG(FATAL) << "Successor " << block_name1 << " not found from "
<< block_name2;
}
}
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index f0c9858..8dded79 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -86,6 +86,7 @@
raw_use_counts_(arena->Adapter()),
num_reachable_blocks_(0),
max_num_reachable_blocks_(0),
+ dfs_orders_up_to_date_(false),
dfs_order_(arena->Adapter(kArenaAllocDfsPreOrder)),
dfs_post_order_(arena->Adapter(kArenaAllocDfsPostOrder)),
dom_post_order_traversal_(arena->Adapter(kArenaAllocDomPostOrder)),
@@ -2224,7 +2225,7 @@
}
}
-void BasicBlock::Hide(CompilationUnit* c_unit) {
+void BasicBlock::Hide(MIRGraph* mir_graph) {
// First lets make it a dalvik bytecode block so it doesn't have any special meaning.
block_type = kDalvikByteCode;
@@ -2239,7 +2240,6 @@
first_mir_insn = nullptr;
last_mir_insn = nullptr;
- MIRGraph* mir_graph = c_unit->mir_graph.get();
for (BasicBlockId pred_id : predecessors) {
BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id);
DCHECK(pred_bb != nullptr);
@@ -2262,6 +2262,48 @@
successor_block_list_type = kNotUsed;
}
+/*
+ * Kill an unreachable block and all blocks that become unreachable by killing this one.
+ */
+void BasicBlock::KillUnreachable(MIRGraph* mir_graph) {
+ DCHECK(predecessors.empty()); // Unreachable.
+
+ // Mark as dead and hidden.
+ block_type = kDead;
+ hidden = true;
+
+ // Detach it from its MIRs so we don't generate code for them. Also detached MIRs
+ // are updated to know that they no longer have a parent.
+ for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+ mir->bb = NullBasicBlockId;
+ }
+ first_mir_insn = nullptr;
+ last_mir_insn = nullptr;
+
+ data_flow_info = nullptr;
+
+ // Erase this bb from all children's predecessors and kill unreachable children.
+ ChildBlockIterator iter(this, mir_graph);
+ for (BasicBlock* succ_bb = iter.Next(); succ_bb != nullptr; succ_bb = iter.Next()) {
+ succ_bb->ErasePredecessor(id);
+ if (succ_bb->predecessors.empty()) {
+ succ_bb->KillUnreachable(mir_graph);
+ }
+ }
+
+ // Remove links to children.
+ fall_through = NullBasicBlockId;
+ taken = NullBasicBlockId;
+ successor_block_list_type = kNotUsed;
+
+ if (kIsDebugBuild) {
+ if (catch_entry) {
+ DCHECK_EQ(mir_graph->catches_.count(start_offset), 1u);
+ mir_graph->catches_.erase(start_offset);
+ }
+ }
+}
+
bool BasicBlock::IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg) {
// In order to determine if the ssa reg is live out, we scan all the MIRs. We remember
// the last SSA number of the same dalvik register. At the end, if it is different than ssa_reg,
@@ -2333,17 +2375,34 @@
void BasicBlock::ErasePredecessor(BasicBlockId old_pred) {
auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
DCHECK(pos != predecessors.end());
- predecessors.erase(pos);
+ // It's faster to move the back() to *pos than erase(pos).
+ *pos = predecessors.back();
+ predecessors.pop_back();
+ size_t idx = std::distance(predecessors.begin(), pos);
+ for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+ if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) {
+ break;
+ }
+ DCHECK_EQ(mir->ssa_rep->num_uses - 1u, predecessors.size());
+ DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred);
+ mir->meta.phi_incoming[idx] = mir->meta.phi_incoming[predecessors.size()];
+ mir->ssa_rep->uses[idx] = mir->ssa_rep->uses[predecessors.size()];
+ mir->ssa_rep->num_uses = predecessors.size();
+ }
}
void BasicBlock::UpdatePredecessor(BasicBlockId old_pred, BasicBlockId new_pred) {
DCHECK_NE(new_pred, NullBasicBlockId);
auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
- if (pos != predecessors.end()) {
- *pos = new_pred;
- } else {
- // If not found, add it.
- predecessors.push_back(new_pred);
+ DCHECK(pos != predecessors.end());
+ *pos = new_pred;
+ size_t idx = std::distance(predecessors.begin(), pos);
+ for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+ if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) {
+ break;
+ }
+ DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred);
+ mir->meta.phi_incoming[idx] = new_pred;
}
}
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index a7069b0..80303f6 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -415,7 +415,12 @@
* remove itself from any predecessor edges, remove itself from any
* child's predecessor array.
*/
- void Hide(CompilationUnit* c_unit);
+ void Hide(MIRGraph* mir_graph);
+
+ /**
+ * @brief Kill the unreachable block and all blocks that become unreachable by killing this one.
+ */
+ void KillUnreachable(MIRGraph* mir_graph);
/**
* @brief Is ssa_reg the last SSA definition of that VR in the block?
@@ -1008,6 +1013,10 @@
return GetFirstSpecialTempVR() + max_available_special_compiler_temps_;
}
+ bool HasTryCatchBlocks() const {
+ return current_code_item_->tries_size_ != 0;
+ }
+
void DumpCheckStats();
MIR* FindMoveResult(BasicBlock* bb, MIR* mir);
int SRegToVReg(int ssa_reg) const;
@@ -1143,6 +1152,10 @@
void InsertPhiNodes();
void DoDFSPreOrderSSARename(BasicBlock* block);
+ bool DfsOrdersUpToDate() const {
+ return dfs_orders_up_to_date_;
+ }
+
/*
* IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on
* we can verify that all catch entries have native PC entries.
@@ -1239,6 +1252,7 @@
ArenaVector<uint32_t> raw_use_counts_; // Not weighted
unsigned int num_reachable_blocks_;
unsigned int max_num_reachable_blocks_;
+ bool dfs_orders_up_to_date_;
ArenaVector<BasicBlockId> dfs_order_;
ArenaVector<BasicBlockId> dfs_post_order_;
ArenaVector<BasicBlockId> dom_post_order_traversal_;
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 2a95853..00528e5 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -752,51 +752,101 @@
/* Combine any basic blocks terminated by instructions that we now know can't throw */
void MIRGraph::CombineBlocks(struct BasicBlock* bb) {
// Loop here to allow combining a sequence of blocks
- while (true) {
- // Check termination conditions
- if ((bb->first_mir_insn == NULL)
- || (bb->data_flow_info == NULL)
- || (bb->block_type == kExceptionHandling)
- || (bb->block_type == kExitBlock)
- || (bb->block_type == kDead)
- || (bb->taken == NullBasicBlockId)
- || (GetBasicBlock(bb->taken)->block_type != kExceptionHandling)
- || (bb->successor_block_list_type != kNotUsed)
- || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
+ while ((bb->block_type == kDalvikByteCode) &&
+ (bb->last_mir_insn != nullptr) &&
+ (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) == kMirOpCheck)) {
+ MIR* mir = bb->last_mir_insn;
+ DCHECK(bb->first_mir_insn != nullptr);
+
+ // Grab the attributes from the paired opcode.
+ MIR* throw_insn = mir->meta.throw_insn;
+ uint64_t df_attributes = GetDataFlowAttributes(throw_insn);
+
+ // Don't combine if the throw_insn can still throw NPE.
+ if ((df_attributes & DF_HAS_NULL_CHKS) != 0 &&
+ (throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0) {
+ break;
+ }
+ // Now whitelist specific instructions.
+ bool ok = false;
+ if ((df_attributes & DF_IFIELD) != 0) {
+ // Combine only if fast, otherwise weird things can happen.
+ const MirIFieldLoweringInfo& field_info = GetIFieldLoweringInfo(throw_insn);
+ ok = (df_attributes & DF_DA) ? field_info.FastPut() : field_info.FastGet();
+ } else if ((df_attributes & DF_SFIELD) != 0) {
+ // Combine only if fast, otherwise weird things can happen.
+ const MirSFieldLoweringInfo& field_info = GetSFieldLoweringInfo(throw_insn);
+ bool fast = ((df_attributes & DF_DA) ? field_info.FastPut() : field_info.FastGet());
+ // Don't combine if the SGET/SPUT can call <clinit>().
+ bool clinit = !field_info.IsInitialized() &&
+ (throw_insn->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0;
+ ok = fast && !clinit;
+ } else if ((df_attributes & DF_HAS_RANGE_CHKS) != 0) {
+ // Only AGET/APUT have range checks. We have processed the AGET/APUT null check above.
+ DCHECK_NE(throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK, 0);
+ ok = ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
+ } else if ((throw_insn->dalvikInsn.FlagsOf() & Instruction::kThrow) == 0) {
+ // We can encounter a non-throwing insn here thanks to inlining or other optimizations.
+ ok = true;
+ } else if (throw_insn->dalvikInsn.opcode == Instruction::ARRAY_LENGTH ||
+ throw_insn->dalvikInsn.opcode == Instruction::FILL_ARRAY_DATA ||
+ static_cast<int>(throw_insn->dalvikInsn.opcode) == kMirOpNullCheck) {
+ // No more checks for these (null check was processed above).
+ ok = true;
+ }
+ if (!ok) {
break;
}
- // Test the kMirOpCheck instruction
- MIR* mir = bb->last_mir_insn;
- // Grab the attributes from the paired opcode
- MIR* throw_insn = mir->meta.throw_insn;
- uint64_t df_attributes = GetDataFlowAttributes(throw_insn);
- bool can_combine = true;
- if (df_attributes & DF_HAS_NULL_CHKS) {
- can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
- }
- if (df_attributes & DF_HAS_RANGE_CHKS) {
- can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
- }
- if (!can_combine) {
- break;
- }
// OK - got one. Combine
BasicBlock* bb_next = GetBasicBlock(bb->fall_through);
DCHECK(!bb_next->catch_entry);
- DCHECK_EQ(Predecessors(bb_next), 1U);
- // Overwrite the kOpCheck insn with the paired opcode
+ DCHECK_EQ(bb_next->predecessors.size(), 1u);
+ // Overwrite the kMirOpCheck insn with the paired opcode.
DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
*bb->last_mir_insn = *throw_insn;
+ // And grab the rest of the instructions from bb_next.
+ bb->last_mir_insn = bb_next->last_mir_insn;
+ throw_insn->next = nullptr;
+ bb_next->last_mir_insn = throw_insn;
+ // Mark acquired instructions as belonging to bb.
+ for (MIR* insn = mir; insn != nullptr; insn = insn->next) {
+ insn->bb = bb->id;
+ }
+ // Before we overwrite successors, remove their predecessor links to bb.
+ bb_next->ErasePredecessor(bb->id);
+ if (bb->taken != NullBasicBlockId) {
+ DCHECK_EQ(bb->successor_block_list_type, kNotUsed);
+ BasicBlock* bb_taken = GetBasicBlock(bb->taken);
+ // bb->taken will be overwritten below.
+ DCHECK_EQ(bb_taken->block_type, kExceptionHandling);
+ DCHECK_EQ(bb_taken->predecessors.size(), 1u);
+ DCHECK_EQ(bb_taken->predecessors[0], bb->id);
+ bb_taken->predecessors.clear();
+ bb_taken->block_type = kDead;
+ DCHECK(bb_taken->data_flow_info == nullptr);
+ } else {
+ DCHECK_EQ(bb->successor_block_list_type, kCatch);
+ for (SuccessorBlockInfo* succ_info : bb->successor_blocks) {
+ if (succ_info->block != NullBasicBlockId) {
+ BasicBlock* succ_bb = GetBasicBlock(succ_info->block);
+ DCHECK(succ_bb->catch_entry);
+ succ_bb->ErasePredecessor(bb->id);
+ if (succ_bb->predecessors.empty()) {
+ succ_bb->KillUnreachable(this);
+ }
+ }
+ }
+ }
// Use the successor info from the next block
bb->successor_block_list_type = bb_next->successor_block_list_type;
bb->successor_blocks.swap(bb_next->successor_blocks); // Swap instead of copying.
+ bb_next->successor_block_list_type = kNotUsed;
// Use the ending block linkage from the next block
bb->fall_through = bb_next->fall_through;
- GetBasicBlock(bb->taken)->block_type = kDead; // Kill the unused exception block
+ bb_next->fall_through = NullBasicBlockId;
bb->taken = bb_next->taken;
- // Include the rest of the instructions
- bb->last_mir_insn = bb_next->last_mir_insn;
+ bb_next->taken = NullBasicBlockId;
/*
* If lower-half of pair of blocks to combine contained
* a return or a conditional branch or an explicit throw,
@@ -805,15 +855,30 @@
bb->terminated_by_return = bb_next->terminated_by_return;
bb->conditional_branch = bb_next->conditional_branch;
bb->explicit_throw = bb_next->explicit_throw;
+ // Merge the use_lvn flag.
+ bb->use_lvn |= bb_next->use_lvn;
+
+ // Kill the unused block.
+ bb_next->data_flow_info = nullptr;
/*
* NOTE: we aren't updating all dataflow info here. Should either make sure this pass
* happens after uses of i_dominated, dom_frontier or update the dataflow info here.
+ * NOTE: GVN uses bb->data_flow_info->live_in_v which is unaffected by the block merge.
*/
- // Kill bb_next and remap now-dead id to parent
+ // Kill bb_next and remap now-dead id to parent.
bb_next->block_type = kDead;
+ bb_next->data_flow_info = nullptr; // Must be null for dead blocks. (Relied on by the GVN.)
block_id_map_.Overwrite(bb_next->id, bb->id);
+ // Update predecessors in children.
+ ChildBlockIterator iter(bb, this);
+ for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
+ child->UpdatePredecessor(bb_next->id, bb->id);
+ }
+
+ // DFS orders are not up to date anymore.
+ dfs_orders_up_to_date_ = false;
// Now, loop back and see if we can keep going
}
diff --git a/compiler/dex/pass_driver_me_opts.cc b/compiler/dex/pass_driver_me_opts.cc
index f83b96c..a2bf8b4 100644
--- a/compiler/dex/pass_driver_me_opts.cc
+++ b/compiler/dex/pass_driver_me_opts.cc
@@ -41,10 +41,10 @@
GetPassInstance<ClassInitCheckElimination>(),
GetPassInstance<SpecialMethodInliner>(),
GetPassInstance<NullCheckElimination>(),
+ GetPassInstance<BBCombine>(),
GetPassInstance<CodeLayout>(),
GetPassInstance<TypeInference>(),
GetPassInstance<GlobalValueNumberingPass>(),
- GetPassInstance<BBCombine>(),
GetPassInstance<BBOptimizations>(),
};
diff --git a/compiler/dex/pass_driver_me_post_opt.cc b/compiler/dex/pass_driver_me_post_opt.cc
index e767139..e6238e9 100644
--- a/compiler/dex/pass_driver_me_post_opt.cc
+++ b/compiler/dex/pass_driver_me_post_opt.cc
@@ -33,6 +33,7 @@
const Pass* const PassDriver<PassDriverMEPostOpt>::g_passes[] = {
GetPassInstance<InitializeData>(),
GetPassInstance<ClearPhiInstructions>(),
+ GetPassInstance<DFSOrders>(),
GetPassInstance<BuildDomination>(),
GetPassInstance<TopologicalSortOrders>(),
GetPassInstance<DefBlockMatrix>(),
diff --git a/compiler/dex/post_opt_passes.h b/compiler/dex/post_opt_passes.h
index e7805ba..02833be 100644
--- a/compiler/dex/post_opt_passes.h
+++ b/compiler/dex/post_opt_passes.h
@@ -91,6 +91,13 @@
DFSOrders() : PassME("DFSOrders") {
}
+ bool Gate(const PassDataHolder* data) const {
+ DCHECK(data != nullptr);
+ CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
+ DCHECK(c_unit != nullptr);
+ return !c_unit->mir_graph->DfsOrdersUpToDate();
+ }
+
void Start(PassDataHolder* data) const {
DCHECK(data != nullptr);
CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index dd74976..412f85d 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -108,10 +108,11 @@
AllNodesIterator iter(this);
for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
if (!bb->visited) {
- bb->Hide(cu_);
+ bb->Hide(this);
}
}
}
+ dfs_orders_up_to_date_ = true;
}
/*