26  * classification, the lexicographically first loop-phi is rotated to the front.
28 static void RotateEntryPhiFirst(HLoopInformation* loop,
31   // Find very first loop-phi.
32   const HInstructionList& phis = loop->GetHeader()->GetPhis();
44   // If found, bring that loop-phi to front.
97  * Returns true if loop is guarded by "a cmp b" on entry.
99 static bool IsGuardedBy(HLoopInformation* loop,
112   HBasicBlock* guard = loop->GetPreHeader();
113   HBasicBlock* entry = loop->GetHeader();
145 /* Finds first loop header phi use. */
146 HInstruction* FindFirstLoopHeaderPhiUse(HLoopInformation* loop, HInstruction* instruction) {
148     if (use.GetUser()->GetBlock() == loop->GetHeader() &&
158  * Relinks the Phi structure after break-loop rewriting.
160 bool FixOutsideUse(HLoopInformation* loop,
170     if (user->GetBlock()->GetLoopInformation() != loop) {
184     if (user->GetHolder()->GetBlock()->GetLoopInformation() != loop) {
198  * Test and rewrite the loop body of a break-loop. Returns true on success.
200 bool RewriteBreakLoopBody(HLoopInformation* loop,
207   for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) {
209     if (!FixOutsideUse(loop, it.Current(), exit_value, rewrite)) {
219     if (!FixOutsideUse(loop, m, FindFirstLoopHeaderPhiUse(loop, m), rewrite)) {
249   // range analysis on outer loop while visiting inner loops.
258 void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
259   // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
265   for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
268     if (loop_block->GetLoopInformation() != loop) {
275         VisitNode(loop, instruction);
281         VisitNode(loop, instruction);
289   // Determine the loop's trip-count.
290   VisitControl(loop);
293 void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
301     low = std::min(low, VisitDescendant(loop, input));
327       ClassifyTrivial(loop, scc_[0]);
329       ClassifyNonTrivial(loop);
337 uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
338   // If the definition is either outside the loop (loop invariant entry value)
339   // or assigned in inner loop (inner exit value), the traversal stops.
341   if (otherLoop != loop) {
347     VisitNode(loop, instruction);
355 void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
358     info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0);
360     info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
361                           LookupInfo(loop, instruction->InputAt(1)), kAdd);
363     info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
364                           LookupInfo(loop, instruction->InputAt(1)), kSub);
366     info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
368     info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
369                        LookupInfo(loop, instruction->InputAt(1)));
371     HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
373       info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
374                          LookupInfo(loop, mulc));
377     info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1);
379     info = TransferConversion(LookupInfo(loop, instruction->InputAt(0)),
383     info = LookupInfo(loop, instruction->InputAt(0));  // Pass-through.
388     AssignInfo(loop, instruction, info);
392 void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
396   // Rotate proper loop-phi to front.
400     RotateEntryPhiFirst(loop, &scc_, &other);
403   // Analyze from loop-phi onwards.
409   // External link should be loop invariant.
410   InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
415   // Store interesting cycle in each loop phi.
424     InductionInfo* update = TransferPhi(loop, phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
426       AssignInfo(loop, phi, CreateInduction(kWrapAround,
442       update = SolvePhiAllInputs(loop, phi, instruction);
445           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
448           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
451           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul);
454           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv);
457           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem);
459       HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
461         update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
464       HInstruction* divc = GetShiftConstant(loop, instruction, initial);
466         update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv);
470           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor);
472       update = SolveTest(loop, phi, instruction, 0);
474       update = SolveTest(loop, phi, instruction, 1);
478       update = SolveConversion(loop, phi, instruction->AsTypeConversion());
499         AssignInfo(loop, phi, induction);
501           ClassifyTrivial(loop, scc_[i]);
509           AssignInfo(loop, scc_[i], induction);
512         AssignInfo(loop, phi, induction);
544 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
551   InductionInfo* a = LookupInfo(loop, inputs[input_index]);
553     InductionInfo* b = LookupInfo(loop, inputs[i]);
695     HLoopInformation* loop,
708     InductionInfo* a = LookupInfo(loop, phi->InputAt(0));
711         InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
723 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
731   InductionInfo* b = LookupInfo(loop, y);
750         InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
763       return SolveAddSub(loop, entry_phi, instruction, y, x, op, false);
769       InductionInfo* a = LookupInfo(loop, x);
771         InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
784 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop,
793     InductionInfo* b = LookupInfo(loop, y);
797       InductionInfo* a = LookupInfo(loop, x);
804       InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
843 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop,
851   if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) {
852     return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor);
853   } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) {
854     return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor);
860     HLoopInformation* loop,
873     InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
891 void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) {
892   HInstruction* control = loop->GetHeader()->GetLastInstruction();
898     // Determine if loop has following structure in header.
899     // loop-header: ....
903       InductionInfo* a = LookupInfo(loop, condition->InputAt(0));
904       InductionInfo* b = LookupInfo(loop, condition->InputAt(1));
906       // Determine if the loop control uses a known sequence on an if-exit (X outside) or on
910       } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) {
911         VisitCondition(loop, if_false, a, b, type, condition->GetOppositeCondition());
912       } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) {
913         VisitCondition(loop, if_true, a, b, type, condition->GetCondition());
919 void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop,
928       case kCondLT: VisitCondition(loop, body, b, a, type, kCondGT); break;
929       case kCondLE: VisitCondition(loop, body, b, a, type, kCondGE); break;
930       case kCondGT: VisitCondition(loop, body, b, a, type, kCondLT); break;
931       case kCondGE: VisitCondition(loop, body, b, a, type, kCondLE); break;
932       case kCondNE: VisitCondition(loop, body, b, a, type, kCondNE); break;
948     // try to rewrite a break-loop with terminating condition i != U into an equivalent loop
950     if (cmp == kCondNE && RewriteBreakLoop(loop, body, stride_value, type)) {
954     // or i > U if this end condition is reached exactly (tested by verifying if the loop has a
966     // Normalize a linear loop control with a nonzero stride:
971       VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp);
976 void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
983   // Any loop of the general form:
997   //     an unsigned entity, for example, as in the following loop that uses the full range:
999   // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in:
1002   //     loop-body proper, not the loop-header unless enforced with an explicit taken-test.
1003   // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in:
1026   // Assign the trip-count expression to the loop control. Clients that use the information
1046   HInstruction* control = loop->GetHeader()->GetLastInstruction();
1049   AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type));
1086   // Some rules under which it is certain at compile-time that the loop is finite.
1128 bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop,
1137   HIf* ifs = loop->GetHeader()->GetLastInstruction()->AsIf();
1142   int c = LookupInfo(loop, cond->InputAt(0))->induction_class == kLinear ? 0 : 1;
1147   if (!index->IsPhi() || !IsFinite(LookupInfo(loop, upper), stride_value, type, cmp)) {
1152       body->GetSingleSuccessor() != loop->GetHeader() ||
1161   if (!IsTaken(LookupInfo(loop, index)->op_b, LookupInfo(loop, upper), cmp) &&
1162       !IsGuardedBy(loop, cmp, index->InputAt(0), upper)) {
1165   // Test if break-loop body can be written, and do so on success.
1166   if (RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ false)) {
1167     RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ true);
1183   loop->GetHeader()->ReplaceAndRemoveInstructionWith(cond, rep);
1191 void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
1194   auto it = induction_.find(loop);
1196     it = induction_.Put(loop,
1204 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
1206   auto it = induction_.find(loop);
1213   if (loop->IsDefinedOutOfTheLoop(instruction)) {
1215     AssignInfo(loop, instruction, info);
1240   // translated back into HIR code (e.g. by loop optimizations or BCE).
1294 HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop,
1311   InductionInfo* b = LookupInfo(loop, instruction->InputAt(1));
1409         case kTripCountInLoop:       inv += " (TC-loop) ";        break;
1411         case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break;

Indexes created Sun Aug 12 02:23:12 CEST 2018