[IndVars] Sharpen context in eliminateIVComparison

[mkazantsev]

Summary

When eliminating comparisons, we can use common dominator of
all its users as context. This gives better results when ICMP is not
computed right before the branch that uses it.

[mkazantsev]

clang-format

[lebedev.ri]

LGTM, thanks.

Also, this appears to be a win overall
https://llvm-compile-time-tracker.com/compare.php?from=19d2c65ddd757997785163709800f837857f686d&to=68b16450c5394e36bafd8d21ad236e7d1e5d92ab&stat=instructions

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   // Get the SCEVs for the ICmp operands (in the specific context of the
   // current loop)
   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
   const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
   const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
 
   // If the condition is always true or always false in the given context,
   // replace it with a constant value.
-  // TODO: We can sharpen the context to common dominator of all ICmp's users.
-  if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, ICmp)) {
+  SmallVector<Instruction *, 4> Users;
+  for (auto *U : ICmp->users())
+    Users.push_back(cast<Instruction>(U));
+  const Instruction *CtxI = findCommonDominator(Users, *DT);
+  if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
     ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
     DeadInsts.emplace_back(ICmp);
     LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
   } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
     // fallthrough to end of function
   } else if (ICmpInst::isSigned(OriginalPred) &&
              SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
     // If we were unable to make anything above, all we can is to canonicalize

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

 
 define i32 @func_28(i32 %start) {
 ; CHECK-LABEL: @func_28(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
-; CHECK-NEXT:    [[C2:%.*]] = icmp ne i32 [[IV]], 0
-; CHECK-NEXT:    [[C3:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 ; CHECK:       checked.1:
-; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
 ; CHECK:       checked.2:
-; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]