Make GVN handle HDeoptimize better

The GVN system didn't handle the deoptimization very well since
deoptimize is a predicated operation. This means that HDeoptimize
needs to prevent some code motion but if it isn't taken the operation
has no effect. This confused the GVN system into thinking that it
cannot merge deoptimizations. To fix this we special cased the side
effects GVN considers deoptimizations to have.

Test: ./test.py --host
Change-Id: Ic79d975f9ae584a07026647cee2768ed1105e5a9

3 files changed, 55 insertions, 2 deletions

diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index e8460a843f..c7cd223b51 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -126,7 +126,7 @@ class ValueSet : public ArenaObject<kArenaAllocGvn> {
   // Removes all instructions in the set affected by the given side effects.
   void Kill(SideEffects side_effects) {
     DeleteAllImpureWhich([side_effects](Node* node) {
-      return node->GetInstruction()->GetSideEffects().MayDependOn(side_effects);
+      return node->GetSideEffects().MayDependOn(side_effects);
     });
   }
 
@@ -197,6 +197,21 @@ class ValueSet : public ArenaObject<kArenaAllocGvn> {
       return new (allocator) Node(instruction_, hash_code_, new_next);
     }
 
+    SideEffects GetSideEffects() const {
+      // Deoptimize is a weird instruction since it's predicated and
+      // never-return. Its side-effects are to prevent the splitting of dex
+      // instructions across it (which could cause inconsistencies once we begin
+      // interpreting again). In the context of GVN the 'perform-deopt' branch is not
+      // relevant and we only need to care about the no-op case, in which case there are
+      // no side-effects. By doing this we are able to eliminate redundant (i.e.
+      // dominated deopts with GVNd conditions) deoptimizations.
+      if (instruction_->IsDeoptimize()) {
+        return SideEffects::None();
+      } else {
+        return instruction_->GetSideEffects();
+      }
+    }
+
    private:
     HInstruction* const instruction_;
     const size_t hash_code_;
@@ -479,7 +494,10 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
     //
     // BoundType is a special case example of an instruction which shouldn't be moved but can be
     // GVN'ed.
-    if (current->CanBeMoved() || current->IsBoundType()) {
+    //
+    // Deoptimize is a special case since even though we don't want to move it we can still remove
+    // it for GVN.
+    if (current->CanBeMoved() || current->IsBoundType() || current->IsDeoptimize()) {
       if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) {
         // For commutative ops, (x op y) will be treated the same as (y op x)
         // after fixed ordering.
diff --git a/test/455-checker-gvn/expected.txt b/test/455-checker-gvn/expected.txt
index c1679c72e8..32dd8f5ab1 100644
--- a/test/455-checker-gvn/expected.txt
+++ b/test/455-checker-gvn/expected.txt
@@ -1,3 +1,4 @@
 14
 0
 10
+45
diff --git a/test/455-checker-gvn/src/Main.java b/test/455-checker-gvn/src/Main.java
index 76b3d42df5..1177e40562 100644
--- a/test/455-checker-gvn/src/Main.java
+++ b/test/455-checker-gvn/src/Main.java
@@ -24,6 +24,7 @@ public class Main {
     System.out.println($noinline$foo(3, 4));
     System.out.println($noinline$mulAndIntrinsic());
     System.out.println($noinline$directIntrinsic(-5));
+    System.out.println($noinline$deoptimizeArray(new int[100]));
   }
 
   private static int $inline$add(int a, int b) {
@@ -90,4 +91,37 @@ public class Main {
     int abs2 = Math.abs(x);
     return abs1 + abs2;
   }
+
+  public static class MyList {
+    public int[] arr;
+  }
+
+  // The 4 deoptimize are pairs of checking for null and array-length. The
+  // repetition is due to the two loops.
+  // NB This is a very degenerate example and improvements to our analysis could
+  // allow for this entire function to be removed.
+  /// CHECK-START: int Main.$noinline$deoptimizeArray(int[]) GVN$after_arch (before)
+  /// CHECK: Deoptimize
+  /// CHECK: Deoptimize
+  /// CHECK: Deoptimize
+  /// CHECK: Deoptimize
+  /// CHECK-NOT: Deoptimize
+  // Get rid of redundant deoptimizes
+  /// CHECK-START: int Main.$noinline$deoptimizeArray(int[]) GVN$after_arch (after)
+  /// CHECK: Deoptimize
+  /// CHECK: Deoptimize
+  /// CHECK-NOT: Deoptimize
+  public static int $noinline$deoptimizeArray(int[] arr) {
+    if (arr == null) {
+      arr = new int[100];
+    }
+    for (int i = 0; i < 10; i++) {
+      arr[i] = i;
+    }
+    int sum = 0;
+    for (int i = 0; i < 10; i++) {
+      sum += arr[i];
+    }
+    return sum;
+  }
 }