Exploit non-null control dependence.
Rationale:
Using the fact that object is non-null in a taken branch
of a object != null test enables the removal of null checks
(as well as some other related optimizations). This CL exposes
many more cases than were detected by the builder alone.
This is in particular useful for Kotlin programs, where the
non-nullable library calls (together with the new always-throws
detection) introduce many dominating object != null tests!
Test: test-art-host test-art-target
Bug: b/63711884
Change-Id: I8df8a750a4184b11f8758e978f09c5181d93ea25
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index cca1055..9fa0f72 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -146,6 +146,65 @@
}
}
+static bool RemoveNonNullControlDependences(HBasicBlock* block, HBasicBlock* throws) {
+ // Test for an if as last statement.
+ if (!block->EndsWithIf()) {
+ return false;
+ }
+ HIf* ifs = block->GetLastInstruction()->AsIf();
+ // Find either:
+ // if obj == null
+ // throws
+ // else
+ // not_throws
+ // or:
+ // if obj != null
+ // not_throws
+ // else
+ // throws
+ HInstruction* cond = ifs->InputAt(0);
+ HBasicBlock* not_throws = nullptr;
+ if (throws == ifs->IfTrueSuccessor() && cond->IsEqual()) {
+ not_throws = ifs->IfFalseSuccessor();
+ } else if (throws == ifs->IfFalseSuccessor() && cond->IsNotEqual()) {
+ not_throws = ifs->IfTrueSuccessor();
+ } else {
+ return false;
+ }
+ DCHECK(cond->IsEqual() || cond->IsNotEqual());
+ HInstruction* obj = cond->InputAt(1);
+ if (obj->IsNullConstant()) {
+ obj = cond->InputAt(0);
+ } else if (!cond->InputAt(0)->IsNullConstant()) {
+ return false;
+ }
+ // Scan all uses of obj and find null check under control dependence.
+ HBoundType* bound = nullptr;
+ const HUseList<HInstruction*>& uses = obj->GetUses();
+ for (auto it = uses.begin(), end = uses.end(); it != end;) {
+ HInstruction* user = it->GetUser();
+ ++it; // increment before possibly replacing
+ if (user->IsNullCheck()) {
+ HBasicBlock* user_block = user->GetBlock();
+ if (user_block != block &&
+ user_block != throws &&
+ block->Dominates(user_block)) {
+ if (bound == nullptr) {
+ ReferenceTypeInfo ti = obj->GetReferenceTypeInfo();
+ bound = new (obj->GetBlock()->GetGraph()->GetAllocator()) HBoundType(obj);
+ bound->SetUpperBound(ti, /*can_be_null*/ false);
+ bound->SetReferenceTypeInfo(ti);
+ bound->SetCanBeNull(false);
+ not_throws->InsertInstructionBefore(bound, not_throws->GetFirstInstruction());
+ }
+ user->ReplaceWith(bound);
+ user_block->RemoveInstruction(user);
+ }
+ }
+ }
+ return bound != nullptr;
+}
+
// Simplify the pattern:
//
// B1
@@ -203,6 +262,11 @@
block->ReplaceSuccessor(succ, exit);
rerun_dominance_and_loop_analysis = true;
MaybeRecordStat(stats_, MethodCompilationStat::kSimplifyThrowingInvoke);
+ // Perform a quick follow up optimization on object != null control dependences
+ // that is much cheaper to perform now than in a later phase.
+ if (RemoveNonNullControlDependences(pred, block)) {
+ MaybeRecordStat(stats_, MethodCompilationStat::kRemovedNullCheck);
+ }
}
}
}
diff --git a/test/672-checker-throw-method/src/Main.java b/test/672-checker-throw-method/src/Main.java
index ceb5eb7..a507133 100644
--- a/test/672-checker-throw-method/src/Main.java
+++ b/test/672-checker-throw-method/src/Main.java
@@ -37,6 +37,12 @@
doThrow(par);
}
+ static private void checkNotNullSplitAlt(Object obj, String par) {
+ if (obj != null)
+ return;
+ doThrow(par);
+ }
+
//
// Various ways of enforcing non-null parameter.
// In all cases, par should be subject to code sinking.
@@ -174,6 +180,60 @@
}
//
+ // Various ways of exploiting non-null parameter.
+ // In all cases, implicit null checks are redundant.
+ //
+
+ /// CHECK-START: int Main.deleteNullCheck(int[]) dead_code_elimination$after_inlining (before)
+ /// CHECK: <<Par:l\d+>> ParameterValue
+ /// CHECK: <<Zero:i\d+>> IntConstant 0
+ /// CHECK: <<Null:l\d+>> NullCheck [<<Par>>]
+ /// CHECK: <<Len:i\d+>> ArrayLength [<<Null>>]
+ /// CHECK: <<Check:i\d+>> BoundsCheck [<<Zero>>,<<Len>>]
+ /// CHECK: <<Get:i\d+>> ArrayGet [<<Null>>,<<Check>>]
+ /// CHECK: Return [<<Get>>]
+ //
+ /// CHECK-START: int Main.deleteNullCheck(int[]) dead_code_elimination$after_inlining (after)
+ /// CHECK: <<Par:l\d+>> ParameterValue
+ /// CHECK: <<Zero:i\d+>> IntConstant 0
+ /// CHECK: <<BT:l\d+>> BoundType [<<Par>>]
+ /// CHECK: <<Len:i\d+>> ArrayLength [<<BT>>]
+ /// CHECK: <<Check:i\d+>> BoundsCheck [<<Zero>>,<<Len>>]
+ /// CHECK: <<Get:i\d+>> ArrayGet [<<BT>>,<<Check>>]
+ /// CHECK: Return [<<Get>>]
+ //
+ /// CHECK-START: int Main.deleteNullCheck(int[]) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: NullCheck
+ static public int deleteNullCheck(int[] a) {
+ checkNotNullSplit(a, "a");
+ return a[0];
+ }
+
+ /// CHECK-START: int Main.deleteNullCheckAlt(int[]) dead_code_elimination$after_inlining (before)
+ /// CHECK: NullCheck
+ //
+ /// CHECK-START: int Main.deleteNullCheckAlt(int[]) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: NullCheck
+ static public int deleteNullCheckAlt(int[] a) {
+ checkNotNullSplitAlt(a, "a");
+ return a[0];
+ }
+
+ /// CHECK-START: int Main.deleteNullChecks3(int[], int[], int[]) dead_code_elimination$after_inlining (before)
+ /// CHECK: NullCheck
+ /// CHECK: NullCheck
+ /// CHECK: NullCheck
+ //
+ /// CHECK-START: int Main.deleteNullChecks3(int[], int[], int[]) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: NullCheck
+ static public int deleteNullChecks3(int[] a, int[] b, int[] c) {
+ checkNotNullSplit(a, "a");
+ checkNotNullSplit(b, "b");
+ checkNotNullSplit(c, "c");
+ return a[0] + b[0] + c[0];
+ }
+
+ //
// Test driver.
//
@@ -233,6 +293,18 @@
expectEquals(5, a[i]);
}
+ int[] x = { 11 } ;
+ expectEquals(11, deleteNullCheck(x));
+ int[] y = { 55 } ;
+ int[] z = { 22 } ;
+ expectEquals(88, deleteNullChecks3(x, y, z));
+
+ try {
+ deleteNullCheck(null);
+ System.out.println("should not reach this!");
+ } catch (Error e) {
+ }
+
System.out.println("passed");
}