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

2 files changed, 136 insertions, 0 deletions

diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index cca1055ac8..9fa0f72e80 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -146,6 +146,65 @@ static HConstant* Evaluate(HCondition* condition, HInstruction* left, HInstructi
   }
 }
 
+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 @@ bool HDeadCodeElimination::SimplifyAlwaysThrows() {
         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 ceb5eb784c..a507133b91 100644
--- a/test/672-checker-throw-method/src/Main.java
+++ b/test/672-checker-throw-method/src/Main.java
@@ -37,6 +37,12 @@ public class Main {
       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 @@ public class Main {
   }
 
   //
+  // 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 @@ public class Main {
       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");
   }