Quick: Redefine the notion of back-egdes.
Redefine a back-edge to really mean an edge to a loop head
instead of comparing instruction offsets. Generate suspend
checks also on fall-through to a loop head; insert an extra
GOTO for these edges.
Add suspend checks to fused cmp instructions.
Rewrite suspend check elimination to track whether there is
an invoke on each path from the loop head to a given back
edge, instead of using domination info to look for a basic
block with invoke that must be on each path. Ignore invokes
to intrinsics and move the optimization to a its own pass.
The new loops in 109-suspend-check should prevent intrinsics
and fused cmp-related regressions.
Bug: 18522004
Change-Id: I96ac818f76ccf9419a6e70e9ec00555f9d487a9e
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 55f2abc..5c4790a 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -539,28 +539,6 @@
}
}
break;
- case Instruction::RETURN_VOID:
- case Instruction::RETURN:
- case Instruction::RETURN_WIDE:
- case Instruction::RETURN_OBJECT:
- if (bb->GetFirstNonPhiInsn() == mir) {
- // This is a simple return BB. Eliminate suspend checks on predecessor back-edges.
- for (BasicBlockId pred_id : bb->predecessors) {
- BasicBlock* pred_bb = GetBasicBlock(pred_id);
- DCHECK(pred_bb != nullptr);
- if (IsBackedge(pred_bb, bb->id) && pred_bb->last_mir_insn != nullptr &&
- (IsInstructionIfCc(pred_bb->last_mir_insn->dalvikInsn.opcode) ||
- IsInstructionIfCcZ(pred_bb->last_mir_insn->dalvikInsn.opcode) ||
- IsInstructionGoto(pred_bb->last_mir_insn->dalvikInsn.opcode))) {
- pred_bb->last_mir_insn->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
- if (cu_->verbose) {
- LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex
- << pred_bb->last_mir_insn->offset;
- }
- }
- }
- }
- break;
default:
break;
}
@@ -589,12 +567,8 @@
if ((tk_ft == NULL) && (ft_tk == NULL) && (tk_tk == ft_ft) &&
(Predecessors(tk) == 1) && (Predecessors(ft) == 1)) {
/*
- * Okay - we have the basic diamond shape. At the very least, we can eliminate the
- * suspend check on the taken-taken branch back to the join point.
+ * Okay - we have the basic diamond shape.
*/
- if (SelectKind(tk->last_mir_insn) == kSelectGoto) {
- tk->last_mir_insn->optimization_flags |= (MIR_IGNORE_SUSPEND_CHECK);
- }
// TODO: Add logic for LONG.
// Are the block bodies something we can handle?
@@ -1637,4 +1611,103 @@
temp_scoped_alloc_.reset();
}
+bool MIRGraph::EliminateSuspendChecksGate() {
+ if ((cu_->disable_opt & (1 << kSuspendCheckElimination)) != 0 || // Disabled.
+ GetMaxNestedLoops() == 0u || // Nothing to do.
+ GetMaxNestedLoops() >= 32u || // Only 32 bits in suspend_checks_in_loops_[.].
+ // Exclude 32 as well to keep bit shifts well-defined.
+ !HasInvokes()) { // No invokes to actually eliminate any suspend checks.
+ return false;
+ }
+ if (cu_->compiler_driver != nullptr && cu_->compiler_driver->GetMethodInlinerMap() != nullptr) {
+ temp_.sce.inliner =
+ cu_->compiler_driver->GetMethodInlinerMap()->GetMethodInliner(cu_->dex_file);
+ }
+ suspend_checks_in_loops_ = static_cast<uint32_t*>(
+ arena_->Alloc(GetNumBlocks() * sizeof(*suspend_checks_in_loops_), kArenaAllocMisc));
+ return true;
+}
+
+bool MIRGraph::EliminateSuspendChecks(BasicBlock* bb) {
+ if (bb->block_type != kDalvikByteCode) {
+ return false;
+ }
+ DCHECK_EQ(GetTopologicalSortOrderLoopHeadStack()->size(), bb->nesting_depth);
+ if (bb->nesting_depth == 0u) {
+ // Out of loops.
+ DCHECK_EQ(suspend_checks_in_loops_[bb->id], 0u); // The array was zero-initialized.
+ return false;
+ }
+ uint32_t suspend_checks_in_loops = (1u << bb->nesting_depth) - 1u; // Start with all loop heads.
+ bool found_invoke = false;
+ for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+ if (IsInstructionInvoke(mir->dalvikInsn.opcode) &&
+ (temp_.sce.inliner == nullptr ||
+ !temp_.sce.inliner->IsIntrinsic(mir->dalvikInsn.vB, nullptr))) {
+ // Non-intrinsic invoke, rely on a suspend point in the invoked method.
+ found_invoke = true;
+ break;
+ }
+ }
+ if (!found_invoke) {
+ // Intersect suspend checks from predecessors.
+ uint16_t bb_topo_idx = topological_order_indexes_[bb->id];
+ uint32_t pred_mask_union = 0u;
+ for (BasicBlockId pred_id : bb->predecessors) {
+ uint16_t pred_topo_idx = topological_order_indexes_[pred_id];
+ if (pred_topo_idx < bb_topo_idx) {
+ // Determine the loop depth of the predecessors relative to this block.
+ size_t pred_loop_depth = topological_order_loop_head_stack_.size();
+ while (pred_loop_depth != 0u &&
+ pred_topo_idx < topological_order_loop_head_stack_[pred_loop_depth - 1].first) {
+ --pred_loop_depth;
+ }
+ DCHECK_LE(pred_loop_depth, GetBasicBlock(pred_id)->nesting_depth);
+ uint32_t pred_mask = (1u << pred_loop_depth) - 1u;
+ // Intersect pred_mask bits in suspend_checks_in_loops with
+ // suspend_checks_in_loops_[pred_id].
+ uint32_t pred_loops_without_checks = pred_mask & ~suspend_checks_in_loops_[pred_id];
+ suspend_checks_in_loops = suspend_checks_in_loops & ~pred_loops_without_checks;
+ pred_mask_union |= pred_mask;
+ }
+ }
+ DCHECK_EQ(((1u << (IsLoopHead(bb->id) ? bb->nesting_depth - 1u: bb->nesting_depth)) - 1u),
+ pred_mask_union);
+ suspend_checks_in_loops &= pred_mask_union;
+ }
+ suspend_checks_in_loops_[bb->id] = suspend_checks_in_loops;
+ if (suspend_checks_in_loops == 0u) {
+ return false;
+ }
+ // Apply MIR_IGNORE_SUSPEND_CHECK if appropriate.
+ if (bb->taken != NullBasicBlockId) {
+ DCHECK(bb->last_mir_insn != nullptr);
+ DCHECK(IsInstructionIfCc(bb->last_mir_insn->dalvikInsn.opcode) ||
+ IsInstructionIfCcZ(bb->last_mir_insn->dalvikInsn.opcode) ||
+ IsInstructionGoto(bb->last_mir_insn->dalvikInsn.opcode) ||
+ (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) >= kMirOpFusedCmplFloat &&
+ static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) <= kMirOpFusedCmpLong));
+ if (!IsSuspendCheckEdge(bb, bb->taken) &&
+ (bb->fall_through == NullBasicBlockId || !IsSuspendCheckEdge(bb, bb->fall_through))) {
+ bb->last_mir_insn->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
+ }
+ } else if (bb->fall_through != NullBasicBlockId && IsSuspendCheckEdge(bb, bb->fall_through)) {
+ // We've got a fall-through suspend edge. Add an artificial GOTO to force suspend check.
+ MIR* mir = NewMIR();
+ mir->dalvikInsn.opcode = Instruction::GOTO;
+ mir->dalvikInsn.vA = 0; // Branch offset.
+ mir->offset = GetBasicBlock(bb->fall_through)->start_offset;
+ mir->m_unit_index = current_method_;
+ mir->ssa_rep = reinterpret_cast<SSARepresentation*>(
+ arena_->Alloc(sizeof(SSARepresentation), kArenaAllocDFInfo)); // Zero-initialized.
+ bb->AppendMIR(mir);
+ std::swap(bb->fall_through, bb->taken); // The fall-through has become taken.
+ }
+ return true;
+}
+
+void MIRGraph::EliminateSuspendChecksEnd() {
+ temp_.sce.inliner = nullptr;
+}
+
} // namespace art