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

1 files changed, 32 insertions, 7 deletions

diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index c501ccf80f..55fcb12fa8 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -87,11 +87,12 @@ HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
     : HOptimization(graph, kInductionPassName),
       global_depth_(0),
       stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
-      scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
       map_(std::less<HInstruction*>(),
            graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+      scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
       cycle_(std::less<HInstruction*>(),
              graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+      type_(Primitive::kPrimVoid),
       induction_(std::less<HLoopInformation*>(),
                  graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) {
 }
@@ -103,7 +104,6 @@ void HInductionVarAnalysis::Run() {
   for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
     HBasicBlock* graph_block = it_graph.Current();
     // Don't analyze irreducible loops.
-    // TODO(ajcbik): could/should we remove this restriction?
     if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) {
       VisitLoop(graph_block->GetLoopInformation());
     }
@@ -121,7 +121,7 @@ void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
     HBasicBlock* loop_block = it_loop.Current();
     DCHECK(loop_block->IsInLoop());
     if (loop_block->GetLoopInformation() != loop) {
-      continue;  // Inner loops already visited.
+      continue;  // Inner loops visited later.
     }
     // Visit phi-operations and instructions.
     for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
@@ -285,6 +285,9 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
     } else if (instruction->IsSub()) {
       update = SolveAddSub(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
+    } else if (instruction->IsXor()) {
+      update = SolveXor(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), true);
     } else if (instruction->IsTypeConversion()) {
       update = SolveCnv(instruction->AsTypeConversion());
     }
@@ -553,6 +556,27 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn
   return nullptr;
 }
 
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveXor(HLoopInformation* loop,
+                                                                      HInstruction* entry_phi,
+                                                                      HInstruction* instruction,
+                                                                      HInstruction* x,
+                                                                      HInstruction* y,
+                                                                      bool is_first_call) {
+  InductionInfo* b = LookupInfo(loop, y);
+  // Solve within a tight cycle on x = x ^ c.
+  if (b != nullptr && b->induction_class == kInvariant) {
+    if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
+      InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+      return CreateInduction(kPeriodic, CreateInvariantOp(kXor, initial, b), initial, type_);
+    }
+  }
+  // Try the other way around if considered for first time.
+  if (is_first_call) {
+    return SolveXor(loop, entry_phi, instruction, y, x, false);
+  }
+  return nullptr;
+}
+
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveCnv(HTypeConversion* conversion) {
   Primitive::Type from = conversion->GetInputType();
   Primitive::Type to = conversion->GetResultType();
@@ -850,8 +874,8 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv
   int64_t value = -1;
   if (IsExact(a, &value)) {
     if (value == 0) {
-      // Simplify 0 + b = b, 0 * b = 0.
-      if (op == kAdd) {
+      // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0.
+      if (op == kAdd || op == kXor) {
         return b;
       } else if (op == kMul) {
         return a;
@@ -867,8 +891,8 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv
   }
   if (IsExact(b, &value)) {
     if (value == 0) {
-      // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0.
-      if (op == kAdd || op == kSub) {
+      // Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0.
+      if (op == kAdd || op == kSub || op == kXor) {
         return a;
       } else if (op == kMul || op == kNeg) {
         return b;
@@ -939,6 +963,7 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
         case kNeg:   inv += " - ";  break;
         case kMul:   inv += " * ";  break;
         case kDiv:   inv += " / ";  break;
+        case kXor:   inv += " ^ ";  break;
         case kLT:    inv += " < ";  break;
         case kLE:    inv += " <= "; break;
         case kGT:    inv += " > ";  break;