Revert "Revert "Null check elimination improvement""
This reverts commit 31aa97cfec5ee76b2f2496464e1b6f9e11d21a29.
..and thereby brings back change 380165, which was reverted
because it was buggy.
Three problems with the original CL:
1. The author ran the pre-submit tests, but used -j24 and
failed to search the output for fail messages.
2. The new null check analysis pass uses an interative
approach to identify whether a null check is needed. It
is possible that the null-check-required state may
oscillate, and a logic error caused it to stick in the
"no check needed" state.
3. Our old nemesis Dalvik untyped constants, in which 0 values
can be used both as object reference and non-object references.
This CL conservatively treats all CONST definitions as
potential object definitions for the purposes of null
check elimination.
Change-Id: I3c1744e44318276e42989502a314585e56ac57a0
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_graph.h b/compiler/dex/mir_graph.h
index 8dda7c4..a69dde0 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -149,7 +149,7 @@
#define DF_C_IS_REG (DF_UC)
#define DF_IS_GETTER_OR_SETTER (DF_IS_GETTER | DF_IS_SETTER)
#define DF_USES_FP (DF_FP_A | DF_FP_B | DF_FP_C)
-
+#define DF_NULL_TRANSFER (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)
enum OatMethodAttributes {
kIsLeaf, // Method is leaf.
kHasLoop, // Method contains simple loop.
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 3cd158f..f5913a5 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,49 @@
}
int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
- // Mark target of NEW* as non-null
- if (df_attributes & DF_NON_NULL_DST) {
+ // Might need a null check?
+ if (df_attributes & DF_HAS_NULL_CHKS) {
+ 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 {
+ // Do the null check.
+ mir->optimization_flags &= ~MIR_IGNORE_NULL_CHECK;
+ // Mark s_reg as null-checked
+ temp_ssa_register_v_->ClearBit(src_sreg);
+ }
+ }
+
+ if ((df_attributes & DF_A_WIDE) ||
+ (df_attributes & (DF_REF_A | DF_SETS_CONST | DF_NULL_TRANSFER)) == 0) {
+ continue;
+ }
+
+ /*
+ * First, mark all object definitions as requiring null check.
+ * Note: we can't tell if a CONST definition might be used as an object, so treat
+ * them all as object definitions.
+ */
+ if (((df_attributes & (DF_DA | DF_REF_A)) == (DF_DA | DF_REF_A)) ||
+ (df_attributes & DF_SETS_CONST)) {
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 +737,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 +752,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 +765,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 a6653fa..dfbc887 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 b6c8922..0d8bd07 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;
}
}
