commit 7dc96932491dde6b5b58998254d5837dbcbbde03
author Aart Bik <ajcbik@google.com> Wed Oct 12 10:01:05 2016 -0700
committer Aart Bik <ajcbik@google.com> Wed Oct 12 14:10:11 2016 -0700
tree b2b0c7a133738823eb61871e5482aa657f2f8a2a
parent f0ab2ec6008bbd495e59bb9bf81ac399d864f38b

Recognize XOR-based periodic induction.

Rationale:
This is a commonly used construct (e.g. x = !x for booleans
and x ^= 1 for integers). This CL prepares some upcoming
optimizations that exploit such inductions.

Change-Id: I46edffb9de1075a836995daf5c2dfff7891f3034
Test: 530-checker-loops2 and induction_var_analysis_test

test/530-checker-loops2/src/Main.java

diff --git a/test/530-checker-loops2/src/Main.java b/test/530-checker-loops2/src/Main.java
index 7acf008..dca00bd 100644
--- a/test/530-checker-loops2/src/Main.java
+++ b/test/530-checker-loops2/src/Main.java
@@ -111,6 +111,24 @@
     return result;
   }
 
+  /// CHECK-START: int Main.periodicXorSequence(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: int Main.periodicXorSequence(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  /// CHECK-NOT: Deoptimize
+  private static int periodicXorSequence(int tc) {
+    int[] x = { 1, 3 };
+    // Loop with periodic sequence (0, 1).
+    int k = 0;
+    int result = 0;
+    for (int i = 0; i < tc; i++) {
+      result += x[k];
+      k ^= 1;
+    }
+    return result;
+  }
+
   /// CHECK-START: int Main.justRightUp1() BCE (before)
   /// CHECK-DAG: BoundsCheck
   //
@@ -895,8 +913,9 @@
     expectEquals(0, periodicIdiom(-1));
     for (int tc = 0; tc < 32; tc++) {
       int expected = (tc >> 1) << 2;
-      if ((tc & 1) != 0)
+      if ((tc & 1) != 0) {
         expected += 1;
+      }
       expectEquals(expected, periodicIdiom(tc));
     }
 
@@ -904,8 +923,9 @@
     expectEquals(0, periodicSequence2(-1));
     for (int tc = 0; tc < 32; tc++) {
       int expected = (tc >> 1) << 2;
-      if ((tc & 1) != 0)
+      if ((tc & 1) != 0) {
         expected += 1;
+      }
       expectEquals(expected, periodicSequence2(tc));
     }
 
@@ -915,6 +935,16 @@
       expectEquals(tc * 16, periodicSequence4(tc));
     }
 
+    // Periodic adds (1, 3), one at the time.
+    expectEquals(0, periodicXorSequence(-1));
+    for (int tc = 0; tc < 32; tc++) {
+      int expected = (tc >> 1) << 2;
+      if ((tc & 1) != 0) {
+        expected += 1;
+      }
+      expectEquals(expected, periodicXorSequence(tc));
+    }
+
     // Large bounds.
     expectEquals(55, justRightUp1());
     expectEquals(55, justRightUp2());