From 312eb25273dc0e2f8880d80f00c5b0998febaf7b Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Tue, 7 Oct 2014 15:01:57 +0100 Subject: [PATCH] Quick: Improve the BBCombine pass. Eliminate exception edges for insns that cannot throw even when inside a try-block. Run the BBCombine pass before the SSA transformation to reduce the compilation time. Bug: 16398693 Change-Id: I8e91df593e316c994679b9d482b0ae20700b9499 --- compiler/dex/bb_optimizations.h | 3 +- compiler/dex/mir_dataflow.cc | 2 +- compiler/dex/mir_graph.cc | 75 +++++++++++++++++--- compiler/dex/mir_graph.h | 16 ++++- compiler/dex/mir_optimization.cc | 121 ++++++++++++++++++++++++-------- compiler/dex/pass_driver_me_opts.cc | 2 +- compiler/dex/pass_driver_me_post_opt.cc | 1 + compiler/dex/post_opt_passes.h | 7 ++ compiler/dex/ssa_transformation.cc | 3 +- 9 files changed, 189 insertions(+), 41 deletions(-) diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h index 3b1be514d..fba086369 100644 --- a/compiler/dex/bb_optimizations.h +++ b/compiler/dex/bb_optimizations.h @@ -271,7 +271,8 @@ class BBCombine : public PassME { DCHECK(data != nullptr); CompilationUnit* c_unit = down_cast(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 6d3f229c7..0a6924cbc 100644 --- a/compiler/dex/mir_dataflow.cc +++ b/compiler/dex/mir_dataflow.cc @@ -1403,7 +1403,7 @@ bool MIRGraph::VerifyPredInfo(BasicBlock* bb) { 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 f0c985862..8dded79aa 100644 --- a/compiler/dex/mir_graph.cc +++ b/compiler/dex/mir_graph.cc @@ -86,6 +86,7 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 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::ResetOptimizationFlags(uint16_t reset_flags) { } } -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 @@ void BasicBlock::Hide(CompilationUnit* c_unit) { 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 @@ void BasicBlock::Hide(CompilationUnit* c_unit) { 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 @@ bool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { 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(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(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 a7069b00e..80303f675 100644 --- a/compiler/dex/mir_graph.h +++ b/compiler/dex/mir_graph.h @@ -415,7 +415,12 @@ struct BasicBlock { * 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 @@ class MIRGraph { 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 @@ class MIRGraph { 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 @@ class MIRGraph { ArenaVector raw_use_counts_; // Not weighted unsigned int num_reachable_blocks_; unsigned int max_num_reachable_blocks_; + bool dfs_orders_up_to_date_; ArenaVector dfs_order_; ArenaVector dfs_post_order_; ArenaVector dom_post_order_traversal_; diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc index 2a958532a..00528e5f4 100644 --- a/compiler/dex/mir_optimization.cc +++ b/compiler/dex/mir_optimization.cc @@ -752,51 +752,101 @@ bool MIRGraph::LayoutBlocks(BasicBlock* bb) { /* 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(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) { - break; - } - - // Test the kMirOpCheck instruction + while ((bb->block_type == kDalvikByteCode) && + (bb->last_mir_insn != nullptr) && + (static_cast(bb->last_mir_insn->dalvikInsn.opcode) == kMirOpCheck)) { MIR* mir = bb->last_mir_insn; - // Grab the attributes from the paired opcode + 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); - bool can_combine = true; - if (df_attributes & DF_HAS_NULL_CHKS) { - can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0); + + // 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; } - if (df_attributes & DF_HAS_RANGE_CHKS) { - can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0); + // 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 (). + 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(throw_insn->dalvikInsn.opcode) == kMirOpNullCheck) { + // No more checks for these (null check was processed above). + ok = true; } - if (!can_combine) { + if (!ok) { 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 @@ void MIRGraph::CombineBlocks(struct BasicBlock* bb) { 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 f83b96caf..a2bf8b4aa 100644 --- a/compiler/dex/pass_driver_me_opts.cc +++ b/compiler/dex/pass_driver_me_opts.cc @@ -41,10 +41,10 @@ const Pass* const PassDriver::g_passes[] = { GetPassInstance(), GetPassInstance(), GetPassInstance(), + GetPassInstance(), GetPassInstance(), GetPassInstance(), GetPassInstance(), - GetPassInstance(), GetPassInstance(), }; diff --git a/compiler/dex/pass_driver_me_post_opt.cc b/compiler/dex/pass_driver_me_post_opt.cc index e767139f9..e6238e9f2 100644 --- a/compiler/dex/pass_driver_me_post_opt.cc +++ b/compiler/dex/pass_driver_me_post_opt.cc @@ -33,6 +33,7 @@ template<> const Pass* const PassDriver::g_passes[] = { GetPassInstance(), GetPassInstance(), + GetPassInstance(), GetPassInstance(), GetPassInstance(), GetPassInstance(), diff --git a/compiler/dex/post_opt_passes.h b/compiler/dex/post_opt_passes.h index e7805bae6..02833be2c 100644 --- a/compiler/dex/post_opt_passes.h +++ b/compiler/dex/post_opt_passes.h @@ -91,6 +91,13 @@ class DFSOrders : public PassME { DFSOrders() : PassME("DFSOrders") { } + bool Gate(const PassDataHolder* data) const { + DCHECK(data != nullptr); + CompilationUnit* c_unit = down_cast(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(data)->c_unit; diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc index dd7497624..412f85d5d 100644 --- a/compiler/dex/ssa_transformation.cc +++ b/compiler/dex/ssa_transformation.cc @@ -108,10 +108,11 @@ void MIRGraph::ComputeDFSOrders() { 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; } /* -- 2.11.0