Null check elimination improvement
See b/10862777
Improves the null check elimination pass by tracking visibility
of object definitions, rather than successful uses of object
dereferences. For boot class path, increases static null
check elimination success rate from 98.4% to 98.6%. Reduces
size of boot.oat by ~300K bytes.
Fixes loop nesting depth computation, which is used by register
promotion, and tweaked the heuristics.
Fixes a bug in verbose listing output in which a basic block
id is directly dereferenced, rather than first being converted
to a pointer.
Change-Id: Id01c20b533cdb12ea8fc4be576438407d0a34cec
diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index 9c8ce23..11e19dc 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -1243,7 +1243,8 @@
if (mir->ssa_rep == NULL) {
continue;
}
- uint32_t weight = std::min(16U, static_cast<uint32_t>(bb->nesting_depth));
+ // Each level of nesting adds *16 to count, up to 3 levels deep.
+ uint32_t weight = std::min(3U, static_cast<uint32_t>(bb->nesting_depth) * 4);
for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
int s_reg = mir->ssa_rep->uses[i];
raw_use_counts_.Increment(s_reg);
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 3cd158f..0b453b1 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -629,10 +629,15 @@
*/
if ((bb->block_type == kEntryBlock) | bb->catch_entry) {
temp_ssa_register_v_->ClearAllBits();
+ // Assume all ins are objects.
+ for (uint16_t in_reg = cu_->num_dalvik_registers - cu_->num_ins;
+ in_reg < cu_->num_dalvik_registers; in_reg++) {
+ temp_ssa_register_v_->SetBit(in_reg);
+ }
if ((cu_->access_flags & kAccStatic) == 0) {
// If non-static method, mark "this" as non-null
int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
- temp_ssa_register_v_->SetBit(this_reg);
+ temp_ssa_register_v_->ClearBit(this_reg);
}
} else if (bb->predecessors->Size() == 1) {
BasicBlock* pred_bb = GetBasicBlock(bb->predecessors->Get(0));
@@ -645,18 +650,18 @@
if (pred_bb->fall_through == bb->id) {
// The fall-through of a block following a IF_EQZ, set the vA of the IF_EQZ to show that
// it can't be null.
- temp_ssa_register_v_->SetBit(last_insn->ssa_rep->uses[0]);
+ temp_ssa_register_v_->ClearBit(last_insn->ssa_rep->uses[0]);
}
} else if (last_opcode == Instruction::IF_NEZ) {
if (pred_bb->taken == bb->id) {
// The taken block following a IF_NEZ, set the vA of the IF_NEZ to show that it can't be
// null.
- temp_ssa_register_v_->SetBit(last_insn->ssa_rep->uses[0]);
+ temp_ssa_register_v_->ClearBit(last_insn->ssa_rep->uses[0]);
}
}
}
} else {
- // Starting state is intersection of all incoming arcs
+ // Starting state is union of all incoming arcs
GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
BasicBlock* pred_bb = GetBasicBlock(iter.Next());
DCHECK(pred_bb != NULL);
@@ -668,10 +673,13 @@
(pred_bb->data_flow_info->ending_null_check_v == NULL)) {
continue;
}
- temp_ssa_register_v_->Intersect(pred_bb->data_flow_info->ending_null_check_v);
+ temp_ssa_register_v_->Union(pred_bb->data_flow_info->ending_null_check_v);
}
}
+ // At this point, temp_ssa_register_v_ shows which sregs have an object definition with
+ // no intervening uses.
+
// Walk through the instruction in the block, updating as necessary
for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
if (mir->ssa_rep == NULL) {
@@ -679,11 +687,41 @@
}
int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
- // Mark target of NEW* as non-null
- if (df_attributes & DF_NON_NULL_DST) {
+ // Already nullchecked?
+ if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
+ int src_idx;
+ if (df_attributes & DF_NULL_CHK_1) {
+ src_idx = 1;
+ } else if (df_attributes & DF_NULL_CHK_2) {
+ src_idx = 2;
+ } else {
+ src_idx = 0;
+ }
+ int src_sreg = mir->ssa_rep->uses[src_idx];
+ if (!temp_ssa_register_v_->IsBitSet(src_sreg)) {
+ // Eliminate the null check
+ mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+ } else {
+ // Mark s_reg as null-checked
+ temp_ssa_register_v_->ClearBit(src_sreg);
+ }
+ }
+
+ if ((df_attributes & (DF_REF_A | DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) == 0) {
+ continue;
+ }
+
+ // First, mark all object definitions as requiring null check.
+ if ((df_attributes & (DF_DA | DF_REF_A)) == (DF_DA | DF_REF_A)) {
temp_ssa_register_v_->SetBit(mir->ssa_rep->defs[0]);
}
+ // Now, remove mark from all object definitions we know are non-null.
+ if (df_attributes & DF_NON_NULL_DST) {
+ // Mark target of NEW* as non-null
+ temp_ssa_register_v_->ClearBit(mir->ssa_rep->defs[0]);
+ }
+
// Mark non-null returns from invoke-style NEW*
if (df_attributes & DF_NON_NULL_RET) {
MIR* next_mir = mir->next;
@@ -691,7 +729,7 @@
if (next_mir &&
next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
// Mark as null checked
- temp_ssa_register_v_->SetBit(next_mir->ssa_rep->defs[0]);
+ temp_ssa_register_v_->ClearBit(next_mir->ssa_rep->defs[0]);
} else {
if (next_mir) {
LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
@@ -706,7 +744,7 @@
// First non-pseudo should be MOVE_RESULT_OBJECT
if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
// Mark as null checked
- temp_ssa_register_v_->SetBit(tmir->ssa_rep->defs[0]);
+ temp_ssa_register_v_->ClearBit(tmir->ssa_rep->defs[0]);
} else {
LOG(WARNING) << "Unexpected op after new: " << tmir->dalvikInsn.opcode;
}
@@ -719,40 +757,22 @@
/*
* Propagate nullcheck state on register copies (including
* Phi pseudo copies. For the latter, nullcheck state is
- * the "and" of all the Phi's operands.
+ * the "or" of all the Phi's operands.
*/
if (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
int tgt_sreg = mir->ssa_rep->defs[0];
int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
mir->ssa_rep->num_uses;
- bool null_checked = true;
+ bool needs_null_check = false;
for (int i = 0; i < operands; i++) {
- null_checked &= temp_ssa_register_v_->IsBitSet(mir->ssa_rep->uses[i]);
+ needs_null_check |= temp_ssa_register_v_->IsBitSet(mir->ssa_rep->uses[i]);
}
- if (null_checked) {
+ if (needs_null_check) {
temp_ssa_register_v_->SetBit(tgt_sreg);
+ } else {
+ temp_ssa_register_v_->ClearBit(tgt_sreg);
}
}
-
- // Already nullchecked?
- if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
- int src_idx;
- if (df_attributes & DF_NULL_CHK_1) {
- src_idx = 1;
- } else if (df_attributes & DF_NULL_CHK_2) {
- src_idx = 2;
- } else {
- src_idx = 0;
- }
- int src_sreg = mir->ssa_rep->uses[src_idx];
- if (temp_ssa_register_v_->IsBitSet(src_sreg)) {
- // Eliminate the null check
- mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
- } else {
- // Mark s_reg as null-checked
- temp_ssa_register_v_->SetBit(src_sreg);
- }
- }
}
// Did anything change?
diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index 2ce8f58..cc185f5 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -164,7 +164,8 @@
lir->operands[0] = WrapPointer(ArenaStrdup("No instruction string"));
}
LOG(INFO) << "-------- dalvik offset: 0x" << std::hex
- << lir->dalvik_offset << " @ " << reinterpret_cast<char*>(lir->operands[0]);
+ << lir->dalvik_offset << " @ "
+ << reinterpret_cast<char*>(UnwrapPointer(lir->operands[0]));
break;
case kPseudoExitBlock:
LOG(INFO) << "-------- exit offset: 0x" << std::hex << dest;
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index eb0d412..c86a788 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -206,6 +206,7 @@
/* hacky loop detection */
if ((curr_bb->taken != NullBasicBlockId) && curr_bb->dominators->IsBitSet(curr_bb->taken)) {
+ curr_bb->nesting_depth++;
attributes_ |= METHOD_HAS_LOOP;
}
}
