[SCEV][NFC] Verify IR in isLoop[Entry,Backedge]GuardedByCond

[mkazantsev]

Summary

We have a lot of various bugs that are caused by misuse of SCEV (in particular in LV),
all of them can simply be described as "we ask SCEV to prove some fact on invalid IR".
Some of examples of those are PR36311, PR37221, PR39160.

The problem is that these failues manifest differently (what we saw was failure of various
asserts across SCEV, but there can also be miscompiles). This patch adds an assert into two
SCEV methods that strongly rely on correctness of the IR and are involved in known failues.
This will at least allow us to have a clear indication of what was wrong in this case.

This patch also fixes a unit test with incorrect IR that fails this verification.

[fhahn]

verifyFunction is relatively expensive IIRC and isLoopBackedgeGuardedByCond is potentially called multiple times for the same function, so I am slightly worried about increasing the runtime too much. Maybe it would be better under EXPENSIVE_CHECKS?

[sanjoy]

+1 on the general idea, though like Florian I too think this is too expensive for a normal debug build. How about putting it under a flag (putting under EXPENSIVE_CHECKS requires a recompile right?) that can even run on release builds? That flag can even be enabled by default on EXPENSIVE_CHECKS builds.

[hsaito]

I agree with Sanjoy. Making this available under a flag would be good.

[mkazantsev]

Moved under EXPENSIVE_CHECKS.

[mkazantsev]

Changed to option.

[mkazantsev]

Added notion of this option being slow. It can be later be turned on in EXPENSIVE_CHECKS mode along with the other two. I tried turning it on now and currently all three turned on fail 2 tests. Apparently a bug in there.

[mkazantsev]

Ping?

[fhahn]

LGTM.

In D52930#1267561, @mkazantsev wrote:

Added notion of this option being slow. It can be later be turned on in EXPENSIVE_CHECKS mode along with the other two. I tried turning it on now and currently all three turned on fail 2 tests. Apparently a bug in there.

If there are failing tests, could you create a ticket so we can keep track of them?

lib/Analysis/ScalarEvolution.cpp

166

Maybe change the name to something like verify-scev-ir to be more in line with the other verify flags?

lib/Analysis/ScalarEvolution.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/SaveAndRestore.h"

 static cl::opt<bool> VerifySCEV(
     "verify-scev", cl::Hidden,
     cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
 static cl::opt<bool>
     VerifySCEVMap("verify-scev-maps", cl::Hidden,
                   cl::desc("Verify no dangling value in ScalarEvolution's "
                            "ExprValueMap (slow)"));
 
 static cl::opt<unsigned> MulOpsInlineThreshold(
     "scev-mulops-inline-threshold", cl::Hidden,
     cl::desc("Threshold for inlining multiplication operands into a SCEV"),
     cl::init(32));
 
 static cl::opt<unsigned> AddOpsInlineThreshold(
     "scev-addops-inline-threshold", cl::Hidden,
     cl::desc("Threshold for inlining addition operands into a SCEV"),
     cl::init(500));

 bool
 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
                                              ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return true;
 
+#ifdef EXPENSIVE_CHECKS
+  assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) &&
+         "This cannot be done on broken IR!");
+#endif
+
   if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
     return true;
 
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return false;
 
   BranchInst *LoopContinuePredicate =

 bool
 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                           ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return false;
 
+#ifdef EXPENSIVE_CHECKS
+  assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) &&
+         "This cannot be done on broken IR!");
+#endif
+
   // Both LHS and RHS must be available at loop entry.
   assert(isAvailableAtLoopEntry(LHS, L) &&
          "LHS is not available at Loop Entry");
   assert(isAvailableAtLoopEntry(RHS, L) &&
          "RHS is not available at Loop Entry");
 
   if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
     return true;

unittests/Analysis/ScalarEvolutionTest.cpp

for (int i = 0; i < Iters; i++) {
     else
       NextBB = EndBB;
     BranchInst::Create(IncBB, NextBB, Cmp, CondBB);
     auto *Dec = BinaryOperator::CreateNSWAdd(
         PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB);
     PN->addIncoming(Dec, IncBB);
     BranchInst::Create(CondBB, IncBB);
 
-    Accum = GetElementPtrInst::Create(I8Ty, Accum, Dec, "gep", EndBB);
+    Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB);
 
     PrevBB = CondBB;
     CondBB = NextBB;
   }
   ReturnInst::Create(Context, nullptr, EndBB);
   ScalarEvolution SE = buildSE(*F);
   const SCEV *S = SE.getSCEV(Accum);
   Type *I128Ty = Type::getInt128Ty(Context);