Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1098,8 +1098,12 @@ bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); /// Return the "disposition" of the given SCEV with respect to the given - /// block. - BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); + /// block. NOTE: If UseCache is true (default), this method is not truly + /// const. It's going to modify its internal (mutable) cache structure. + /// If UseCache is false, it is truly const, but is potentially *very* + /// expensive. This should only used for validation of cached values. + BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB, + bool UseCache = true) const; /// Return true if elements that makes up the given SCEV dominate the /// specified basic block. @@ -1490,13 +1494,14 @@ LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// Memoized computeBlockDisposition results. - DenseMap< + mutable DenseMap< const SCEV *, - SmallVector, 2>> - BlockDispositions; + SmallVector, 2> > + BlockDispositions; /// Compute a BlockDisposition value. - BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); + BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB, + bool UseCache = true) const; /// Memoized results from getRange DenseMap UnsignedRanges; @@ -1890,6 +1895,10 @@ /// pointer. bool checkValidity(const SCEV *S) const; + /// Return false iff given SCEV is, or contains, a SCEV that has been erased + /// from ExprValueMap. + bool containsDanglingPointers(const SCEV *S) const; + /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is /// equivalent to proving no signed (resp. unsigned) wrap in Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -3998,6 +3998,11 @@ return !ContainsNulls; } +bool ScalarEvolution::containsDanglingPointers(const SCEV *S) const { + return SCEVExprContains( + S, [this](const SCEV *S) { return !ExprValueMap.count(S); }); +} + bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { HasRecMapType::iterator I = HasRecMap.find(S); if (I != HasRecMap.end()) @@ -12505,6 +12510,18 @@ llvm_unreachable("Unknown ScalarEvolution::LoopDisposition kind!"); } +static StringRef blockDispositionToStr(ScalarEvolution::BlockDisposition BD) { + switch (BD) { + case ScalarEvolution::DoesNotDominateBlock: + return "Does not dominate block"; + case ScalarEvolution::DominatesBlock: + return "Dominates block"; + case ScalarEvolution::ProperlyDominatesBlock: + return "Properly dominates block"; + } + llvm_unreachable("Unknown ScalarEvolution::BlockDisposition kind!"); +} + void ScalarEvolution::print(raw_ostream &OS) const { // ScalarEvolution's implementation of the print method is to print // out SCEV values of all instructions that are interesting. Doing @@ -12704,26 +12721,32 @@ } ScalarEvolution::BlockDisposition -ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { +ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB, + bool UseCache) const { auto &Values = BlockDispositions[S]; - for (auto &V : Values) { - if (V.getPointer() == BB) - return V.getInt(); - } - Values.emplace_back(BB, DoesNotDominateBlock); - BlockDisposition D = computeBlockDisposition(S, BB); - auto &Values2 = BlockDispositions[S]; - for (auto &V : make_range(Values2.rbegin(), Values2.rend())) { - if (V.getPointer() == BB) { - V.setInt(D); - break; + if (UseCache) { + for (auto &V : Values) { + if (V.getPointer() == BB) + return V.getInt(); + } + Values.emplace_back(BB, DoesNotDominateBlock); + } + BlockDisposition D = computeBlockDisposition(S, BB, UseCache); + if (UseCache) { + auto &Values2 = BlockDispositions[S]; + for (auto &V : make_range(Values2.rbegin(), Values2.rend())) { + if (V.getPointer() == BB) { + V.setInt(D); + break; + } } } return D; } ScalarEvolution::BlockDisposition -ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { +ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB, + bool UseCache) const { switch (S->getSCEVType()) { case scConstant: return ProperlyDominatesBlock; @@ -12731,7 +12754,8 @@ case scTruncate: case scZeroExtend: case scSignExtend: - return getBlockDisposition(cast(S)->getOperand(), BB); + return getBlockDisposition(cast(S)->getOperand(), BB, + UseCache); case scAddRecExpr: { // This uses a "dominates" query instead of "properly dominates" query // to test for proper dominance too, because the instruction which @@ -12753,7 +12777,7 @@ const SCEVNAryExpr *NAry = cast(S); bool Proper = true; for (const SCEV *NAryOp : NAry->operands()) { - BlockDisposition D = getBlockDisposition(NAryOp, BB); + BlockDisposition D = getBlockDisposition(NAryOp, BB, UseCache); if (D == DoesNotDominateBlock) return DoesNotDominateBlock; if (D == DominatesBlock) @@ -12764,10 +12788,10 @@ case scUDivExpr: { const SCEVUDivExpr *UDiv = cast(S); const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS(); - BlockDisposition LD = getBlockDisposition(LHS, BB); + BlockDisposition LD = getBlockDisposition(LHS, BB, UseCache); if (LD == DoesNotDominateBlock) return DoesNotDominateBlock; - BlockDisposition RD = getBlockDisposition(RHS, BB); + BlockDisposition RD = getBlockDisposition(RHS, BB, UseCache); if (RD == DoesNotDominateBlock) return DoesNotDominateBlock; return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ? @@ -12953,6 +12977,29 @@ assert(ValidLoops.contains(AR->getLoop()) && "AddRec references invalid loop"); } + + // Verify cached block dispositions. + for (auto &It : BlockDispositions) { + const SCEV *S = It.first; + if (containsDanglingPointers(S)) + // FIXME: Remove this when we wipe out dangling pointers from all maps. + continue; + auto &Values = It.second; + for (auto &V : Values) { + auto *BB = V.getPointer(); + auto CachedDisposition = V.getInt(); + auto ActualDisposition = getBlockDisposition(S, BB, /*UseCache*/ false); + if (CachedDisposition != ActualDisposition) { + dbgs() << "Cached block disposition of SCEV " << *S + << " for basic block: " << BB->getName() + << " has changed!\nCached: " + << blockDispositionToStr(CachedDisposition) + << "\nActual: " << blockDispositionToStr(ActualDisposition) + << "\n"; + std::abort(); + } + } + } } bool ScalarEvolution::invalidate( Index: llvm/test/Transforms/LoopRotate/pr51981-scev-problem-verification.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopRotate/pr51981-scev-problem-verification.ll @@ -0,0 +1,41 @@ +; RUN: opt < %s -passes='verify,loop(loop-rotate),verify' -disable-output 2>&1 | FileCheck %s +; FIXME: BlockDisposition cache is in invalid state after this transform. +; +; Cached block disposition of SCEV %wide for basic block: loop.inner has changed! +; Cached: Properly dominates block +; Actual: Does not dominate block +; +; XFAIL: * +; REQUIRES: asserts + +@offset = external dso_local global i32, align 1 +@array = internal global [11263 x i32] zeroinitializer, align 1 + +define void @test_function(i1 %cond) { +; CHECK-LABEL: test_function +entry: + br label %loop.outer.header + +loop.outer.header: ; preds = %loop.outer.latch, %entry + %wide = load i32, i32* @offset, align 1 + br i1 %cond, label %exit, label %loop.inner.ph + +loop.inner.ph: ; preds = %loop.outer.header + %narrow = trunc i32 %wide to i16 + br label %loop.inner + +loop.inner: ; preds = %loop.inner, %loop.inner.ph + %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ] + %iv.promoted = zext i16 %iv to i32 + %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted + store i32 7, i32* %gep, align 1 + %iv.plus = add i16 %iv, 1 + %cmp = icmp ult i16 %iv.plus, 700 + br i1 %cmp, label %loop.inner, label %loop.outer.latch + +loop.outer.latch: ; preds = %loop.inner + br label %loop.outer.header + +exit: ; preds = %loop.outer.header + ret void +}