[SCEV] Use isKnownPredicateAt in isLoopBackedgeGuardedByCond

[mkazantsev]

Summary

A piece of code in isLoopBackedgeGuardedByCond basically duplicates
the dominators traversal from isBlockEntryGuardedByCond called from
isKnownPredicateAt, but it's less powerful because it does not give context
to isImpliedCond. This patch reuses the isKnownPredicateAt function there,
reducing the amount of code duplication and making it more powerful.

[nikic]

Looks like this change has a large negative compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=2254e014a9019bf17c3f5cb27c1dc40ca0f2ffce&to=14f2ad0e3cc54d5eb254b545a469e8ffdb62b119&stat=instructions 2% on average, 6% on mafft.

[mkazantsev]

Strange. I'll revert it for now and investigate.

[mkazantsev]

Maybe it's because isKnownPredicateAt makes an extra call to isKnownPredicate which we don't really need. Let's try more lightweight version with isBasicBlockEntryGuardedByCond. This should not introduce extra overhead.

[mkazantsev]

Previous version was better, but still not good enough. Tried another version that removes two instances of isKnownViaNonRecuriveReasoning from the path.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
   // infinite loop as we walk up into the dom tree.  These loops do not matter
   // anyway, so we just return a conservative answer when we see them.
   if (!DT.isReachableFromEntry(L->getHeader()))
     return false;
 
   if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
     return true;
 
-  for (DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
-       DTN != HeaderDTN; DTN = DTN->getIDom()) {
-    assert(DTN && "should reach the loop header before reaching the root!");
-
-    BasicBlock *BB = DTN->getBlock();
-    if (isImpliedViaGuard(BB, Pred, LHS, RHS))
-      return true;
-
-    BasicBlock *PBB = BB->getSinglePredecessor();
-    if (!PBB)
-      continue;
-
-    BranchInst *ContinuePredicate = dyn_cast<BranchInst>(PBB->getTerminator());
-    if (!ContinuePredicate || !ContinuePredicate->isConditional())
-      continue;
-
-    Value *Condition = ContinuePredicate->getCondition();
-
-    // If we have an edge `E` within the loop body that dominates the only
-    // latch, the condition guarding `E` also guards the backedge.  This
-    // reasoning works only for loops with a single latch.
-
-    BasicBlockEdge DominatingEdge(PBB, BB);
-    if (DominatingEdge.isSingleEdge()) {
-      // We're constructively (and conservatively) enumerating edges within the
-      // loop body that dominate the latch.  The dominator tree better agree
-      // with us on this:
-      assert(DT.dominates(DominatingEdge, Latch) && "should be!");
-
-      if (isImpliedCond(Pred, LHS, RHS, Condition,
-                        BB != ContinuePredicate->getSuccessor(0)))
-        return true;
-    }
-  }
-
-  return false;
+  return isKnownPredicateAt(Pred, LHS, RHS, Latch->getTerminator());
 }
 
 bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
                                                      ICmpInst::Predicate Pred,
                                                      const SCEV *LHS,
                                                      const SCEV *RHS) {
   if (VerifyIR)
     assert(!verifyFunction(*BB->getParent(), &dbgs()) &&

llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll

 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[LSR_IV8:%.*]] = phi [33 x i16]* [ [[TMP3:%.*]], [[FOR_BODY]] ], [ [[TMP2]], [[FOR_BODY_LR_PH]] ]
 ; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_LR_PH]] ]
 ; CHECK-NEXT:    [[LSR_IV810:%.*]] = bitcast [33 x i16]* [[LSR_IV8]] to i16*
 ; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[SCEVGEP1]], i64 [[LSR_IV]]
 ; CHECK-NEXT:    [[UGLYGEP2:%.*]] = bitcast i8* [[UGLYGEP]] to i16*
 ; CHECK-NEXT:    [[TMP29:%.*]] = load i16, i16* [[LSR_IV810]], align 2
 ; CHECK-NEXT:    store i16 [[TMP29]], i16* [[UGLYGEP2]], align 2
-; CHECK-NEXT:    [[LSR_IV_NEXT]] = add i64 [[LSR_IV]], 2
+; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nuw nsw i64 [[LSR_IV]], 2
 ; CHECK-NEXT:    [[LSR_IV_NEXT3:%.*]] = inttoptr i64 [[LSR_IV_NEXT]] to i16*
 ; CHECK-NEXT:    [[SCEVGEP9:%.*]] = getelementptr [33 x i16], [33 x i16]* [[LSR_IV8]], i64 0, i64 1
 ; CHECK-NEXT:    [[TMP3]] = bitcast i16* [[SCEVGEP9]] to [33 x i16]*
 ; CHECK-NEXT:    [[CMP27:%.*]] = icmp eq i16* [[LSR_IV_NEXT3]], null
 ; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end: