compiler/optimizing/induction_var_analysis.cc - LeafOS-Project/android_art - Gitiles

 /*
  * Copyright (C) 2015 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "induction_var_analysis.h"

 namespace art {

 /**
  * Returns true if instruction is invariant within the given loop.
  */
 static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
   HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
   if (other_loop != loop) {
     // If instruction does not occur in same loop, it is invariant
     // if it appears in an outer loop (including no loop at all).
     return other_loop == nullptr || loop->IsIn(*other_loop);
   }
   return false;
 }

 /**
  * Returns true if instruction is proper entry-phi-operation for given loop
  * (referred to as mu-operation in Gerlek's paper).
  */
 static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
   return
       instruction->IsPhi() &&
       instruction->InputCount() == 2 &&
       instruction->GetBlock() == loop->GetHeader();
 }

 //
 // Class methods.
 //

 HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
     : HOptimization(graph, kInductionPassName),
       global_depth_(0),
       stack_(graph->GetArena()->Adapter()),
       scc_(graph->GetArena()->Adapter()),
       map_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
       cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
       induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter()) {
 }

 void HInductionVarAnalysis::Run() {
   // Detects sequence variables (generalized induction variables) during an inner-loop-first
   // traversal of all loops using Gerlek's algorithm. The order is only relevant if outer
   // loops would use induction information of inner loops (not currently done).
   for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
     HBasicBlock* graph_block = it_graph.Current();
     if (graph_block->IsLoopHeader()) {
       VisitLoop(graph_block->GetLoopInformation());
     }
   }
 }

 void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
   // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
   // algorithm. Due to the descendant-first nature, classification happens "on-demand".
   global_depth_ = 0;
   DCHECK(stack_.empty());
   map_.clear();

   for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
     HBasicBlock* loop_block = it_loop.Current();
     DCHECK(loop_block->IsInLoop());
     if (loop_block->GetLoopInformation() != loop) {
       continue;  // Inner loops already visited.
     }
     // Visit phi-operations and instructions.
     for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
       HInstruction* instruction = it.Current();
       if (!IsVisitedNode(instruction)) {
         VisitNode(loop, instruction);
       }
     }
     for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* instruction = it.Current();
       if (!IsVisitedNode(instruction)) {
         VisitNode(loop, instruction);
       }
     }
   }

   DCHECK(stack_.empty());
   map_.clear();
 }

 void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
   const uint32_t d1 = ++global_depth_;
   map_.Put(instruction, NodeInfo(d1));
   stack_.push_back(instruction);

   // Visit all descendants.
   uint32_t low = d1;
   for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
     low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
   }

   // Lower or found SCC?
   if (low < d1) {
     map_.find(instruction)->second.depth = low;
   } else {
     scc_.clear();
     cycle_.clear();

     // Pop the stack to build the SCC for classification.
     while (!stack_.empty()) {
       HInstruction* x = stack_.back();
       scc_.push_back(x);
       stack_.pop_back();
       map_.find(x)->second.done = true;
       if (x == instruction) {
         break;
       }
     }

     // Classify the SCC.
     if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
       ClassifyTrivial(loop, scc_[0]);
     } else {
       ClassifyNonTrivial(loop);
     }

     scc_.clear();
     cycle_.clear();
   }
 }

 uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
   // If the definition is either outside the loop (loop invariant entry value)
   // or assigned in inner loop (inner exit value), the traversal stops.
   HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
   if (otherLoop != loop) {
     return global_depth_;
   }

   // Inspect descendant node.
   if (!IsVisitedNode(instruction)) {
     VisitNode(loop, instruction);
     return map_.find(instruction)->second.depth;
   } else {
     auto it = map_.find(instruction);
     return it->second.done ? global_depth_ : it->second.depth;
   }
 }

 void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
   InductionInfo* info = nullptr;
   if (instruction->IsPhi()) {
     for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
       info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
                          LookupInfo(loop, instruction->InputAt(i)));
     }
   } else if (instruction->IsAdd()) {
     info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
                           LookupInfo(loop, instruction->InputAt(1)), kAdd);
   } else if (instruction->IsSub()) {
     info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
                           LookupInfo(loop, instruction->InputAt(1)), kSub);
   } else if (instruction->IsMul()) {
     info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
                        LookupInfo(loop, instruction->InputAt(1)));
   } else if (instruction->IsShl()) {
     info = TransferShl(LookupInfo(loop, instruction->InputAt(0)),
                        LookupInfo(loop, instruction->InputAt(1)),
                        instruction->InputAt(0)->GetType());
   } else if (instruction->IsNeg()) {
     info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
   } else if (instruction->IsBoundsCheck()) {
     info = LookupInfo(loop, instruction->InputAt(0));  // Pass-through.
   } else if (instruction->IsTypeConversion()) {
     HTypeConversion* conversion = instruction->AsTypeConversion();
     // TODO: accept different conversion scenarios.
     if (conversion->GetResultType() == conversion->GetInputType()) {
       info = LookupInfo(loop, conversion->GetInput());
     }
   }

   // Successfully classified?
   if (info != nullptr) {
     AssignInfo(loop, instruction, info);
   }
 }

 void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
   const size_t size = scc_.size();
   DCHECK_GE(size, 1u);
   HInstruction* phi = scc_[size - 1];
   if (!IsEntryPhi(loop, phi)) {
     return;
   }
   HInstruction* external = phi->InputAt(0);
   HInstruction* internal = phi->InputAt(1);
   InductionInfo* initial = LookupInfo(loop, external);
   if (initial == nullptr || initial->induction_class != kInvariant) {
     return;
   }

   // Singleton entry-phi-operation may be a wrap-around induction.
   if (size == 1) {
     InductionInfo* update = LookupInfo(loop, internal);
     if (update != nullptr) {
       AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update));
     }
     return;
   }

   // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
   // temporary meaning to its nodes, seeded from the phi instruction and back.
   for (size_t i = 0; i < size - 1; i++) {
     HInstruction* instruction = scc_[i];
     InductionInfo* update = nullptr;
     if (instruction->IsPhi()) {
       update = SolvePhi(loop, phi, instruction);
     } else if (instruction->IsAdd()) {
       update = SolveAddSub(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
     } else if (instruction->IsSub()) {
       update = SolveAddSub(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
     }
     if (update == nullptr) {
       return;
     }
     cycle_.Put(instruction, update);
   }

   // Success if the internal link received a meaning.
   auto it = cycle_.find(internal);
   if (it != cycle_.end()) {
     InductionInfo* induction = it->second;
     switch (induction->induction_class) {
       case kInvariant:
         // Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
         // Statements are scanned in the Tarjan SCC order, with phi first.
         AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial));
         for (size_t i = 0; i < size - 1; i++) {
           ClassifyTrivial(loop, scc_[i]);
         }
         break;
       case kPeriodic:
         // Classify all elements in the cycle with the found periodic induction while rotating
         // each first element to the end. Lastly, phi (last element in scc_) is classified.
         // Statements are scanned in the reverse Tarjan SCC order, with phi last.
         for (size_t i = 2; i <= size; i++) {
           AssignInfo(loop, scc_[size - i], induction);
           induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
         }
         AssignInfo(loop, phi, induction);
         break;
       default:
         break;
     }
   }
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
     InductionInfo* induction,
     InductionInfo* last) {
   // Rotates a periodic induction of the form
   //   (a, b, c, d, e)
   // into
   //   (b, c, d, e, a)
   // in preparation of assigning this to the previous variable in the sequence.
   if (induction->induction_class == kInvariant) {
     return CreateInduction(kPeriodic, induction, last);
   }
   return CreateInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
                                                                          InductionInfo* b) {
   // Transfer over a phi: if both inputs are identical, result is input.
   if (InductionEqual(a, b)) {
     return a;
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
                                                                             InductionInfo* b,
                                                                             InductionOp op) {
   // Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic
   // can be combined with an invariant to yield a similar result. Even two linear inputs can
   // be combined. All other combinations fail, however.
   if (a != nullptr && b != nullptr) {
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
       return CreateInvariantOp(op, a, b);
     } else if (a->induction_class == kLinear && b->induction_class == kLinear) {
       return CreateInduction(
           kLinear, TransferAddSub(a->op_a, b->op_a, op), TransferAddSub(a->op_b, b->op_b, op));
     } else if (a->induction_class == kInvariant) {
       InductionInfo* new_a = b->op_a;
       InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
       if (b->induction_class != kLinear) {
         DCHECK(b->induction_class == kWrapAround || b->induction_class == kPeriodic);
         new_a = TransferAddSub(a, new_a, op);
       } else if (op == kSub) {  // Negation required.
         new_a = TransferNeg(new_a);
       }
       return CreateInduction(b->induction_class, new_a, new_b);
     } else if (b->induction_class == kInvariant) {
       InductionInfo* new_a = a->op_a;
       InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
       if (a->induction_class != kLinear) {
         DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic);
         new_a = TransferAddSub(new_a, b, op);
       }
       return CreateInduction(a->induction_class, new_a, new_b);
     }
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
                                                                          InductionInfo* b) {
   // Transfer over a multiplication: any invariant, linear, wrap-around, or periodic
   // can be multiplied with an invariant to yield a similar but multiplied result.
   // Two non-invariant inputs cannot be multiplied, however.
   if (a != nullptr && b != nullptr) {
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
       return CreateInvariantOp(kMul, a, b);
     } else if (a->induction_class == kInvariant) {
       return CreateInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
     } else if (b->induction_class == kInvariant) {
       return CreateInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
     }
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
                                                                          InductionInfo* b,
                                                                          Primitive::Type t) {
   // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
   int64_t value = -1;
   if (a != nullptr && IsIntAndGet(b, &value)) {
     // Obtain the constant needed for the multiplication. This yields an existing instruction
     // if the constants is already there. Otherwise, this has a side effect on the HIR.
     // The restriction on the shift factor avoids generating a negative constant
     // (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization
     // for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
     if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
       return TransferMul(a, CreateInvariantFetch(graph_->GetIntConstant(1 << value)));
     } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
       return TransferMul(a, CreateInvariantFetch(graph_->GetLongConstant(1L << value)));
     }
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
   // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
   // yields a similar but negated induction as result.
   if (a != nullptr) {
     if (a->induction_class == kInvariant) {
       return CreateInvariantOp(kNeg, nullptr, a);
     }
     return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HLoopInformation* loop,
                                                                       HInstruction* phi,
                                                                       HInstruction* instruction) {
   // Solve within a cycle over a phi: identical inputs are combined into that input as result.
   const size_t count = instruction->InputCount();
   DCHECK_GT(count, 0u);
   auto ita = cycle_.find(instruction->InputAt(0));
   if (ita != cycle_.end()) {
     InductionInfo* a = ita->second;
     for (size_t i = 1; i < count; i++) {
       auto itb = cycle_.find(instruction->InputAt(i));
       if (itb == cycle_.end() || !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
         return nullptr;
       }
     }
     return a;
   }

   // Solve within a cycle over another entry-phi: add invariants into a periodic.
   if (IsEntryPhi(loop, instruction)) {
     InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
     if (a != nullptr && a->induction_class == kInvariant) {
       if (instruction->InputAt(1) == phi) {
         InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
         return CreateInduction(kPeriodic, a, initial);
       }
       auto it = cycle_.find(instruction->InputAt(1));
       if (it != cycle_.end()) {
         InductionInfo* b = it->second;
         if (b->induction_class == kPeriodic) {
           return CreateInduction(kPeriodic, a, b);
         }
       }
     }
   }

   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
                                                                          HInstruction* phi,
                                                                          HInstruction* instruction,
                                                                          HInstruction* x,
                                                                          HInstruction* y,
                                                                          InductionOp op,
                                                                          bool is_first_call) {
   // Solve within a cycle over an addition or subtraction: adding or subtracting an
   // invariant value, seeded from phi, keeps adding to the stride of the induction.
   InductionInfo* b = LookupInfo(loop, y);
   if (b != nullptr && b->induction_class == kInvariant) {
     if (x == phi) {
       return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
     }
     auto it = cycle_.find(x);
     if (it != cycle_.end()) {
       InductionInfo* a = it->second;
       if (a->induction_class == kInvariant) {
         return CreateInvariantOp(op, a, b);
       }
     }
   }

   // Try some alternatives before failing.
   if (op == kAdd) {
     // Try the other way around for an addition if considered for first time.
     if (is_first_call) {
       return SolveAddSub(loop, phi, instruction, y, x, op, false);
     }
   } else if (op == kSub) {
     // Solve within a tight cycle for a periodic idiom k = c - k;
     if (y == phi && instruction == phi->InputAt(1)) {
       InductionInfo* a = LookupInfo(loop, x);
       if (a != nullptr && a->induction_class == kInvariant) {
         InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
         return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial);
       }
     }
   }

   return nullptr;
 }

 void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
                                        HInstruction* instruction,
                                        InductionInfo* info) {
   auto it = induction_.find(loop);
   if (it == induction_.end()) {
     it = induction_.Put(loop,
                         ArenaSafeMap<HInstruction*, InductionInfo*>(
                             std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
   }
   it->second.Put(instruction, info);
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
                                                                         HInstruction* instruction) {
   auto it = induction_.find(loop);
   if (it != induction_.end()) {
     auto loop_it = it->second.find(instruction);
     if (loop_it != it->second.end()) {
       return loop_it->second;
     }
   }
   if (IsLoopInvariant(loop, instruction)) {
     InductionInfo* info = CreateInvariantFetch(instruction);
     AssignInfo(loop, instruction, info);
     return info;
   }
   return nullptr;
 }

 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
     InductionOp op,
     InductionInfo* a,
     InductionInfo* b) {
   // Perform some light-weight simplifications during construction of a new invariant.
   // This often safes memory and yields a more concise representation of the induction.
   // More exhaustive simplifications are done by later phases once induction nodes are
   // translated back into HIR code (e.g. by loop optimizations or BCE).
   int64_t value = -1;
   if (IsIntAndGet(a, &value)) {
     if (value == 0) {
       // Simplify 0 + b = b, 0 * b = 0.
       if (op == kAdd) {
         return b;
       } else if (op == kMul) {
         return a;
       }
     } else if (value == 1 && op == kMul) {
       // Simplify 1 * b = b.
       return b;
     }
   }
   if (IsIntAndGet(b, &value)) {
     if (value == 0) {
       // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, - 0 = 0.
       if (op == kAdd || op == kSub) {
         return a;
       } else if (op == kMul || op == kNeg) {
         return b;
       }
     } else if (value == 1 && (op == kMul || op == kDiv)) {
       // Simplify a * 1 = a, a / 1 = a.
       return a;
     }
   } else if (b->operation == kNeg) {
     // Simplify a + (-b) = a - b, a - (-b) = a + b, - (-b) = b.
     switch (op) {
       case kAdd: op = kSub; b = b->op_b; break;
       case kSub: op = kAdd; b = b->op_b; break;
       case kNeg: return b->op_b;
       default:   break;
     }
   }
   return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
 }

 bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
                                            InductionInfo* info2) {
   // Test structural equality only, without accounting for simplifications.
   if (info1 != nullptr && info2 != nullptr) {
     return
         info1->induction_class == info2->induction_class &&
         info1->operation       == info2->operation       &&
         info1->fetch           == info2->fetch           &&
         InductionEqual(info1->op_a, info2->op_a)         &&
         InductionEqual(info1->op_b, info2->op_b);
   }
   // Otherwise only two nullptrs are considered equal.
   return info1 == info2;
 }

 bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) {
   if (info != nullptr && info->induction_class == kInvariant && info->operation == kFetch) {
     DCHECK(info->fetch);
     if (info->fetch->IsIntConstant()) {
       *value = info->fetch->AsIntConstant()->GetValue();
       return true;
     } else if (info->fetch->IsLongConstant()) {
       *value = info->fetch->AsLongConstant()->GetValue();
       return true;
     }
   }
   return false;
 }

 std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
   if (info != nullptr) {
     if (info->induction_class == kInvariant) {
       int64_t value = -1;
       std::string inv = "(";
       inv += InductionToString(info->op_a);
       switch (info->operation) {
         case kNop:   inv += " @ "; break;
         case kAdd:   inv += " + "; break;
         case kSub:
         case kNeg:   inv += " - "; break;
         case kMul:   inv += " * "; break;
         case kDiv:   inv += " / "; break;
         case kFetch:
           DCHECK(info->fetch);
           if (IsIntAndGet(info, &value)) {
             inv += std::to_string(value);
           } else {
             inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
           }
           break;
       }
       inv += InductionToString(info->op_b);
       return inv + ")";
     } else {
       DCHECK(info->operation == kNop);
       if (info->induction_class == kLinear) {
         return "(" + InductionToString(info->op_a) + " * i + " +
                      InductionToString(info->op_b) + ")";
       } else if (info->induction_class == kWrapAround) {
         return "wrap(" + InductionToString(info->op_a) + ", " +
                          InductionToString(info->op_b) + ")";
       } else if (info->induction_class == kPeriodic) {
         return "periodic(" + InductionToString(info->op_a) + ", " +
                              InductionToString(info->op_b) + ")";
       }
     }
   }
   return "";
 }

 }  // namespace art
	/*
	* Copyright (C) 2015 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "induction_var_analysis.h"

	namespace art {

	/**
	* Returns true if instruction is invariant within the given loop.
	*/
	static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
	HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
	if (other_loop != loop) {
	// If instruction does not occur in same loop, it is invariant
	// if it appears in an outer loop (including no loop at all).
	return other_loop == nullptr \|\| loop->IsIn(*other_loop);
	}
	return false;
	}

	/**
	* Returns true if instruction is proper entry-phi-operation for given loop
	* (referred to as mu-operation in Gerlek's paper).
	*/
	static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
	return
	instruction->IsPhi() &&
	instruction->InputCount() == 2 &&
	instruction->GetBlock() == loop->GetHeader();
	}

	//
	// Class methods.
	//

	HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
	: HOptimization(graph, kInductionPassName),
	global_depth_(0),
	stack_(graph->GetArena()->Adapter()),
	scc_(graph->GetArena()->Adapter()),
	map_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
	cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
	induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter()) {
	}

	void HInductionVarAnalysis::Run() {
	// Detects sequence variables (generalized induction variables) during an inner-loop-first
	// traversal of all loops using Gerlek's algorithm. The order is only relevant if outer
	// loops would use induction information of inner loops (not currently done).
	for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
	HBasicBlock* graph_block = it_graph.Current();
	if (graph_block->IsLoopHeader()) {
	VisitLoop(graph_block->GetLoopInformation());
	}
	}
	}

	void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
	// Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
	// algorithm. Due to the descendant-first nature, classification happens "on-demand".
	global_depth_ = 0;
	DCHECK(stack_.empty());
	map_.clear();

	for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
	HBasicBlock* loop_block = it_loop.Current();
	DCHECK(loop_block->IsInLoop());
	if (loop_block->GetLoopInformation() != loop) {
	continue; // Inner loops already visited.
	}
	// Visit phi-operations and instructions.
	for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
	HInstruction* instruction = it.Current();
	if (!IsVisitedNode(instruction)) {
	VisitNode(loop, instruction);
	}
	}
	for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
	HInstruction* instruction = it.Current();
	if (!IsVisitedNode(instruction)) {
	VisitNode(loop, instruction);
	}
	}
	}

	DCHECK(stack_.empty());
	map_.clear();
	}

	void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
	const uint32_t d1 = ++global_depth_;
	map_.Put(instruction, NodeInfo(d1));
	stack_.push_back(instruction);

	// Visit all descendants.
	uint32_t low = d1;
	for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
	low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
	}

	// Lower or found SCC?
	if (low < d1) {
	map_.find(instruction)->second.depth = low;
	} else {
	scc_.clear();
	cycle_.clear();

	// Pop the stack to build the SCC for classification.
	while (!stack_.empty()) {
	HInstruction* x = stack_.back();
	scc_.push_back(x);
	stack_.pop_back();
	map_.find(x)->second.done = true;
	if (x == instruction) {
	break;
	}
	}

	// Classify the SCC.
	if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
	ClassifyTrivial(loop, scc_[0]);
	} else {
	ClassifyNonTrivial(loop);
	}

	scc_.clear();
	cycle_.clear();
	}
	}

	uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
	// If the definition is either outside the loop (loop invariant entry value)
	// or assigned in inner loop (inner exit value), the traversal stops.
	HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
	if (otherLoop != loop) {
	return global_depth_;
	}

	// Inspect descendant node.
	if (!IsVisitedNode(instruction)) {
	VisitNode(loop, instruction);
	return map_.find(instruction)->second.depth;
	} else {
	auto it = map_.find(instruction);
	return it->second.done ? global_depth_ : it->second.depth;
	}
	}

	void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
	InductionInfo* info = nullptr;
	if (instruction->IsPhi()) {
	for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
	info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
	LookupInfo(loop, instruction->InputAt(i)));
	}
	} else if (instruction->IsAdd()) {
	info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
	LookupInfo(loop, instruction->InputAt(1)), kAdd);
	} else if (instruction->IsSub()) {
	info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
	LookupInfo(loop, instruction->InputAt(1)), kSub);
	} else if (instruction->IsMul()) {
	info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
	LookupInfo(loop, instruction->InputAt(1)));
	} else if (instruction->IsShl()) {
	info = TransferShl(LookupInfo(loop, instruction->InputAt(0)),
	LookupInfo(loop, instruction->InputAt(1)),
	instruction->InputAt(0)->GetType());
	} else if (instruction->IsNeg()) {
	info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
	} else if (instruction->IsBoundsCheck()) {
	info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through.
	} else if (instruction->IsTypeConversion()) {
	HTypeConversion* conversion = instruction->AsTypeConversion();
	// TODO: accept different conversion scenarios.
	if (conversion->GetResultType() == conversion->GetInputType()) {
	info = LookupInfo(loop, conversion->GetInput());
	}
	}

	// Successfully classified?
	if (info != nullptr) {
	AssignInfo(loop, instruction, info);
	}
	}

	void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
	const size_t size = scc_.size();
	DCHECK_GE(size, 1u);
	HInstruction* phi = scc_[size - 1];
	if (!IsEntryPhi(loop, phi)) {
	return;
	}
	HInstruction* external = phi->InputAt(0);
	HInstruction* internal = phi->InputAt(1);
	InductionInfo* initial = LookupInfo(loop, external);
	if (initial == nullptr \|\| initial->induction_class != kInvariant) {
	return;
	}

	// Singleton entry-phi-operation may be a wrap-around induction.
	if (size == 1) {
	InductionInfo* update = LookupInfo(loop, internal);
	if (update != nullptr) {
	AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update));
	}
	return;
	}

	// Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
	// temporary meaning to its nodes, seeded from the phi instruction and back.
	for (size_t i = 0; i < size - 1; i++) {
	HInstruction* instruction = scc_[i];
	InductionInfo* update = nullptr;
	if (instruction->IsPhi()) {
	update = SolvePhi(loop, phi, instruction);
	} else if (instruction->IsAdd()) {
	update = SolveAddSub(
	loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
	} else if (instruction->IsSub()) {
	update = SolveAddSub(
	loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
	}
	if (update == nullptr) {
	return;
	}
	cycle_.Put(instruction, update);
	}

	// Success if the internal link received a meaning.
	auto it = cycle_.find(internal);
	if (it != cycle_.end()) {
	InductionInfo* induction = it->second;
	switch (induction->induction_class) {
	case kInvariant:
	// Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
	// Statements are scanned in the Tarjan SCC order, with phi first.
	AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial));
	for (size_t i = 0; i < size - 1; i++) {
	ClassifyTrivial(loop, scc_[i]);
	}
	break;
	case kPeriodic:
	// Classify all elements in the cycle with the found periodic induction while rotating
	// each first element to the end. Lastly, phi (last element in scc_) is classified.
	// Statements are scanned in the reverse Tarjan SCC order, with phi last.
	for (size_t i = 2; i <= size; i++) {
	AssignInfo(loop, scc_[size - i], induction);
	induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
	}
	AssignInfo(loop, phi, induction);
	break;
	default:
	break;
	}
	}
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
	InductionInfo* induction,
	InductionInfo* last) {
	// Rotates a periodic induction of the form
	// (a, b, c, d, e)
	// into
	// (b, c, d, e, a)
	// in preparation of assigning this to the previous variable in the sequence.
	if (induction->induction_class == kInvariant) {
	return CreateInduction(kPeriodic, induction, last);
	}
	return CreateInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
	InductionInfo* b) {
	// Transfer over a phi: if both inputs are identical, result is input.
	if (InductionEqual(a, b)) {
	return a;
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
	InductionInfo* b,
	InductionOp op) {
	// Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic
	// can be combined with an invariant to yield a similar result. Even two linear inputs can
	// be combined. All other combinations fail, however.
	if (a != nullptr && b != nullptr) {
	if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
	return CreateInvariantOp(op, a, b);
	} else if (a->induction_class == kLinear && b->induction_class == kLinear) {
	return CreateInduction(
	kLinear, TransferAddSub(a->op_a, b->op_a, op), TransferAddSub(a->op_b, b->op_b, op));
	} else if (a->induction_class == kInvariant) {
	InductionInfo* new_a = b->op_a;
	InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
	if (b->induction_class != kLinear) {
	DCHECK(b->induction_class == kWrapAround \|\| b->induction_class == kPeriodic);
	new_a = TransferAddSub(a, new_a, op);
	} else if (op == kSub) { // Negation required.
	new_a = TransferNeg(new_a);
	}
	return CreateInduction(b->induction_class, new_a, new_b);
	} else if (b->induction_class == kInvariant) {
	InductionInfo* new_a = a->op_a;
	InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
	if (a->induction_class != kLinear) {
	DCHECK(a->induction_class == kWrapAround \|\| a->induction_class == kPeriodic);
	new_a = TransferAddSub(new_a, b, op);
	}
	return CreateInduction(a->induction_class, new_a, new_b);
	}
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
	InductionInfo* b) {
	// Transfer over a multiplication: any invariant, linear, wrap-around, or periodic
	// can be multiplied with an invariant to yield a similar but multiplied result.
	// Two non-invariant inputs cannot be multiplied, however.
	if (a != nullptr && b != nullptr) {
	if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
	return CreateInvariantOp(kMul, a, b);
	} else if (a->induction_class == kInvariant) {
	return CreateInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
	} else if (b->induction_class == kInvariant) {
	return CreateInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
	}
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
	InductionInfo* b,
	Primitive::Type t) {
	// Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
	int64_t value = -1;
	if (a != nullptr && IsIntAndGet(b, &value)) {
	// Obtain the constant needed for the multiplication. This yields an existing instruction
	// if the constants is already there. Otherwise, this has a side effect on the HIR.
	// The restriction on the shift factor avoids generating a negative constant
	// (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization
	// for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
	if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
	return TransferMul(a, CreateInvariantFetch(graph_->GetIntConstant(1 << value)));
	} else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
	return TransferMul(a, CreateInvariantFetch(graph_->GetLongConstant(1L << value)));
	}
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
	// Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
	// yields a similar but negated induction as result.
	if (a != nullptr) {
	if (a->induction_class == kInvariant) {
	return CreateInvariantOp(kNeg, nullptr, a);
	}
	return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HLoopInformation* loop,
	HInstruction* phi,
	HInstruction* instruction) {
	// Solve within a cycle over a phi: identical inputs are combined into that input as result.
	const size_t count = instruction->InputCount();
	DCHECK_GT(count, 0u);
	auto ita = cycle_.find(instruction->InputAt(0));
	if (ita != cycle_.end()) {
	InductionInfo* a = ita->second;
	for (size_t i = 1; i < count; i++) {
	auto itb = cycle_.find(instruction->InputAt(i));
	if (itb == cycle_.end() \|\| !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
	return nullptr;
	}
	}
	return a;
	}

	// Solve within a cycle over another entry-phi: add invariants into a periodic.
	if (IsEntryPhi(loop, instruction)) {
	InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
	if (a != nullptr && a->induction_class == kInvariant) {
	if (instruction->InputAt(1) == phi) {
	InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
	return CreateInduction(kPeriodic, a, initial);
	}
	auto it = cycle_.find(instruction->InputAt(1));
	if (it != cycle_.end()) {
	InductionInfo* b = it->second;
	if (b->induction_class == kPeriodic) {
	return CreateInduction(kPeriodic, a, b);
	}
	}
	}
	}

	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
	HInstruction* phi,
	HInstruction* instruction,
	HInstruction* x,
	HInstruction* y,
	InductionOp op,
	bool is_first_call) {
	// Solve within a cycle over an addition or subtraction: adding or subtracting an
	// invariant value, seeded from phi, keeps adding to the stride of the induction.
	InductionInfo* b = LookupInfo(loop, y);
	if (b != nullptr && b->induction_class == kInvariant) {
	if (x == phi) {
	return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
	}
	auto it = cycle_.find(x);
	if (it != cycle_.end()) {
	InductionInfo* a = it->second;
	if (a->induction_class == kInvariant) {
	return CreateInvariantOp(op, a, b);
	}
	}
	}

	// Try some alternatives before failing.
	if (op == kAdd) {
	// Try the other way around for an addition if considered for first time.
	if (is_first_call) {
	return SolveAddSub(loop, phi, instruction, y, x, op, false);
	}
	} else if (op == kSub) {
	// Solve within a tight cycle for a periodic idiom k = c - k;
	if (y == phi && instruction == phi->InputAt(1)) {
	InductionInfo* a = LookupInfo(loop, x);
	if (a != nullptr && a->induction_class == kInvariant) {
	InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
	return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial);
	}
	}
	}

	return nullptr;
	}

	void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
	HInstruction* instruction,
	InductionInfo* info) {
	auto it = induction_.find(loop);
	if (it == induction_.end()) {
	it = induction_.Put(loop,
	ArenaSafeMap<HInstruction, InductionInfo>(
	std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
	}
	it->second.Put(instruction, info);
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
	HInstruction* instruction) {
	auto it = induction_.find(loop);
	if (it != induction_.end()) {
	auto loop_it = it->second.find(instruction);
	if (loop_it != it->second.end()) {
	return loop_it->second;
	}
	}
	if (IsLoopInvariant(loop, instruction)) {
	InductionInfo* info = CreateInvariantFetch(instruction);
	AssignInfo(loop, instruction, info);
	return info;
	}
	return nullptr;
	}

	HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
	InductionOp op,
	InductionInfo* a,
	InductionInfo* b) {
	// Perform some light-weight simplifications during construction of a new invariant.
	// This often safes memory and yields a more concise representation of the induction.
	// More exhaustive simplifications are done by later phases once induction nodes are
	// translated back into HIR code (e.g. by loop optimizations or BCE).
	int64_t value = -1;
	if (IsIntAndGet(a, &value)) {
	if (value == 0) {
	// Simplify 0 + b = b, 0 * b = 0.
	if (op == kAdd) {
	return b;
	} else if (op == kMul) {
	return a;
	}
	} else if (value == 1 && op == kMul) {
	// Simplify 1 * b = b.
	return b;
	}
	}
	if (IsIntAndGet(b, &value)) {
	if (value == 0) {
	// Simplify a + 0 = a, a - 0 = a, a * 0 = 0, - 0 = 0.
	if (op == kAdd \|\| op == kSub) {
	return a;
	} else if (op == kMul \|\| op == kNeg) {
	return b;
	}
	} else if (value == 1 && (op == kMul \|\| op == kDiv)) {
	// Simplify a * 1 = a, a / 1 = a.
	return a;
	}
	} else if (b->operation == kNeg) {
	// Simplify a + (-b) = a - b, a - (-b) = a + b, - (-b) = b.
	switch (op) {
	case kAdd: op = kSub; b = b->op_b; break;
	case kSub: op = kAdd; b = b->op_b; break;
	case kNeg: return b->op_b;
	default: break;
	}
	}
	return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
	}

	bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
	InductionInfo* info2) {
	// Test structural equality only, without accounting for simplifications.
	if (info1 != nullptr && info2 != nullptr) {
	return
	info1->induction_class == info2->induction_class &&
	info1->operation == info2->operation &&
	info1->fetch == info2->fetch &&
	InductionEqual(info1->op_a, info2->op_a) &&
	InductionEqual(info1->op_b, info2->op_b);
	}
	// Otherwise only two nullptrs are considered equal.
	return info1 == info2;
	}

	bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) {
	if (info != nullptr && info->induction_class == kInvariant && info->operation == kFetch) {
	DCHECK(info->fetch);
	if (info->fetch->IsIntConstant()) {
	*value = info->fetch->AsIntConstant()->GetValue();
	return true;
	} else if (info->fetch->IsLongConstant()) {
	*value = info->fetch->AsLongConstant()->GetValue();
	return true;
	}
	}
	return false;
	}

	std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
	if (info != nullptr) {
	if (info->induction_class == kInvariant) {
	int64_t value = -1;
	std::string inv = "(";
	inv += InductionToString(info->op_a);
	switch (info->operation) {
	case kNop: inv += " @ "; break;
	case kAdd: inv += " + "; break;
	case kSub:
	case kNeg: inv += " - "; break;
	case kMul: inv += " * "; break;
	case kDiv: inv += " / "; break;
	case kFetch:
	DCHECK(info->fetch);
	if (IsIntAndGet(info, &value)) {
	inv += std::to_string(value);
	} else {
	inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
	}
	break;
	}
	inv += InductionToString(info->op_b);
	return inv + ")";
	} else {
	DCHECK(info->operation == kNop);
	if (info->induction_class == kLinear) {
	return "(" + InductionToString(info->op_a) + " * i + " +
	InductionToString(info->op_b) + ")";
	} else if (info->induction_class == kWrapAround) {
	return "wrap(" + InductionToString(info->op_a) + ", " +
	InductionToString(info->op_b) + ")";
	} else if (info->induction_class == kPeriodic) {
	return "periodic(" + InductionToString(info->op_a) + ", " +
	InductionToString(info->op_b) + ")";
	}
	}
	}
	return "";
	}

	} // namespace art