[SCEV] Use defining scope to bound backwards predicate search [mostly-nfc]

[reames]

Summary

The basic idea here is that if we have an expression, we can't find a predicate which proves facts about that expression outside the region in which that expression is defined. We can find facts about sub-expressions, but the current logic doesn't let us leverage those. (Note that applyLoopGuards does build facts about sub-expressions and then lazily apply them, so we can't do the same there. In theory at least.)

The one exception is that a trivially unreachable block currently implies all conditions and we loose that. I'm honestly not sure how interesting that is given simplify-cfg and friends will rip the code away wholesale.

The motivation here is to improve compile time. @nikic Do you see any positive impact from this? If not, I'll abandon as the complexity is not worth it on it's own.

[nikic]

This does have an effect: https://llvm-compile-time-tracker.com/compare.php?from=69853f992048efa7fd1b2700b7b71def72300682&to=dce310f616a16f29a8eed239de9d31559de238d9&stat=instructions

Worth noting that there are some minor code size differences: https://llvm-compile-time-tracker.com/compare.php?from=69853f992048efa7fd1b2700b7b71def72300682&to=dce310f616a16f29a8eed239de9d31559de238d9&stat=size-text It seems unlikely that they're due to unreachable code (or not?), so maybe there's something more going on.

[mkazantsev]

CT boost is cool, but the regressions are concerning. Any plans to fix them?

llvm/lib/Analysis/ScalarEvolution.cpp

13715

nit

[reames]

Abandoning as there was unexpected code size regressions from this patch. In abstract, it would be worth understanding why as the CT wins are interesting, but I'm not going to have time to get to that in the nearish future. Will reopen the review if that changes at any time.

llvm/lib/Analysis/ScalarEvolution.cpp

if (ProvingStrictComparison) {
         return isImpliedCond(P, LHS, RHS, Condition, Inverse, CtxI);
       };
       if (SplitAndProve(ProofFn))
         return true;
     }
     return false;
   };
 
+  // The defining scope is the first point at which our operands are both
+  // defined.
+  auto *DefI = getDefiningScopeBound({LHS, RHS});
+
   // Starting at the block's predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
   // leading to the original block.
   const Loop *ContainingLoop = LI.getLoopFor(BB);
   const BasicBlock *PredBB;
   if (ContainingLoop && ContainingLoop->getHeader() == BB)
     PredBB = ContainingLoop->getLoopPredecessor();
   else
     PredBB = BB->getSinglePredecessor();
   for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
     if (ProveViaGuard(Pair.first))
       return true;
 
+    // There's no need to scan above the defining scope for Expr, by definition
+    // there's nothing to find in terms of further relevant conditions.
+    if (!DT.dominates(DefI, Pair.first->getTerminator()))
+      break;
+
     const BranchInst *LoopEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate ||
         LoopEntryPredicate->isUnconditional())
       continue;
 
     if (ProveViaCond(LoopEntryPredicate->getCondition(),
                      LoopEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, BB))
       continue;
+    // There's no need to scan above the defining scope for Expr, by definition
+    // there's nothing to find in terms of further relevant conditions.
+    if (!DT.dominates(DefI, CI))
+      continue;
 
     if (ProveViaCond(CI->getArgOperand(0), false))
       return true;
   }
 
   return false;
 }
 
case CmpInst::ICMP_NE:
       break;
     default:
       break;
     }
 
     if (RewrittenRHS)
       RewriteMap[LHSUnknown->getValue()] = RewrittenRHS;
   };
+
   // Starting at the loop predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
   // leading to the original header.
   // TODO: share this logic with isLoopEntryGuardedByCond.
   ValueToSCEVMapTy RewriteMap;
   for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
            L->getLoopPredecessor(), L->getHeader());
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {

llvm/test/Transforms/IndVarSimplify/trivial-guard.ll

 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[IV_NEXT_1:%.*]], [[GUARDED_1:%.*]] ], [ 0, [[LOOP_1_PREHEADER]] ]
 ; CHECK-NEXT:    [[CHECK_1:%.*]] = icmp slt i32 [[IV_1]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CHECK_1]], label [[GUARDED_1]], label [[FAIL_LOOPEXIT:%.*]]
 ; CHECK:       guarded.1:
 ; CHECK-NEXT:    [[IV_NEXT_1]] = add nuw i32 [[IV_1]], 1
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       loop.2:
-; CHECK-NEXT:    br i1 true, label [[GUARDED_2:%.*]], label [[FAIL_LOOPEXIT1:%.*]]
+; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[IV_NEXT_2:%.*]], [[GUARDED_2:%.*]] ], [ 0, [[LOOP_2_PREHEADER]] ]
+; CHECK-NEXT:    [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X]]
+; CHECK-NEXT:    br i1 [[CHECK_2]], label [[GUARDED_2]], label [[FAIL_LOOPEXIT1:%.*]]
 ; CHECK:       guarded.2:
+; CHECK-NEXT:    [[IV_NEXT_2]] = add nuw i32 [[IV_2]], 1
 ; CHECK-NEXT:    [[LOOP_COND_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_2]], label [[LOOP_2]], label [[EXIT_LOOPEXIT2:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit.loopexit2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void

 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 false, label [[LOOP_1_PREHEADER:%.*]], label [[LOOP_2_PREHEADER:%.*]]
 ; CHECK:       loop.2.preheader:
 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop.1.preheader:
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop.1:
-; CHECK-NEXT:    br i1 true, label [[GUARDED_1:%.*]], label [[FAIL_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[IV_NEXT_1:%.*]], [[GUARDED_1:%.*]] ], [ 0, [[LOOP_1_PREHEADER]] ]
+; CHECK-NEXT:    [[CHECK_1:%.*]] = icmp slt i32 [[IV_1]], [[X:%.*]]
+; CHECK-NEXT:    br i1 [[CHECK_1]], label [[GUARDED_1]], label [[FAIL_LOOPEXIT:%.*]]
 ; CHECK:       guarded.1:
+; CHECK-NEXT:    [[IV_NEXT_1]] = add nuw i32 [[IV_1]], 1
 ; CHECK-NEXT:    [[LOOP_COND_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       loop.2:
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[IV_NEXT_2:%.*]], [[GUARDED_2:%.*]] ], [ 0, [[LOOP_2_PREHEADER]] ]
-; CHECK-NEXT:    [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X:%.*]]
+; CHECK-NEXT:    [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X]]
 ; CHECK-NEXT:    br i1 [[CHECK_2]], label [[GUARDED_2]], label [[FAIL_LOOPEXIT1:%.*]]
 ; CHECK:       guarded.2:
 ; CHECK-NEXT:    [[IV_NEXT_2]] = add nuw i32 [[IV_2]], 1
 ; CHECK-NEXT:    [[LOOP_COND_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND_2]], label [[LOOP_2]], label [[EXIT_LOOPEXIT2:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit.loopexit2: