[LCSSA] Don't invalidate SCEV

[nikic]

Summary

LCSSA currently invalidates SCEV for all instructions for which LCSSA phi nodes are created. This used to be necessary, because SCEV has historically tried to maintain LCSSA form as well. As such, some SCEV uses of the value would have to become uses of the phi node instead.

However, nowadays SCEV itself no longer maintains LCSSA form. The SCEV of on LCSSA phi node will be the same as the SCEV of its argument. LCSSA is instead maintained in the SCEVExpander.

As such, I believe it is no longer necessary to perform any SCEV invalidation during LCSSA construction.

After this patch the ScalarEvolution argument to the LCSSA utilities is no longer necessary -- I'll remove it in a followup NFC patch to keep this patch more concise.

[fhahn]

However, nowadays SCEV itself no longer maintains LCSSA form. The SCEV of on LCSSA phi node will be the same as the SCEV of its argumen

Agreed, the phis we insert here should all be looked-through by SCEV. LGTM, thanks!

[uabelho]

I noticed that after the revert, the following

opt -passes="indvars" bbi-83751.ll -o /dev/null

crashes with

Attempt to use a SCEVCouldNotCompute object!
UNREACHABLE executed at ../include/llvm/Analysis/ScalarEvolutionExpressions.h:705!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -passes=indvars bbi-83751.ll -o /dev/null
 #0 0x000056064f0f9267 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2dcb267)
 #1 0x000056064f0f6f8e llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2dc8f8e)
 #2 0x000056064f0f98ff SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f3f0f708630 __restore_rt sigaction.c:0:0
 #4 0x00007f3f0ce4f387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f3f0ce50a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x000056064f07737f (../../main-github/llvm/build-all/bin/opt+0x2d4937f)
 #7 0x000056064f202a44 llvm::SCEVExpander::expand(llvm::SCEV const*) (../../main-github/llvm/build-all/bin/opt+0x2ed4a44)
 #8 0x000056064f202539 llvm::SCEVExpander::expandCodeForImpl(llvm::SCEV const*, llvm::Type*) (../../main-github/llvm/build-all/bin/opt+0x2ed4539)
 #9 0x000056064fbd317d (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) IndVarSimplify.cpp:0:0
#10 0x000056064fbcd858 llvm::IndVarSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x389f858)
#11 0x000056064f31504d llvm::detail::PassModel<llvm::Loop, llvm::IndVarSimplifyPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x2fe704d)
#12 0x000056064fc2ba03 std::optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>>(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (../../main-github/llvm/build-all/bin/opt+0x38fda03)
#13 0x000056064fc2b657 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x38fd657)
#14 0x000056064fc2abf8 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x38fcbf8)
#15 0x000056064f2f4c1d llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x2fc6c1d)
#16 0x000056064fc2ca61 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x38fea61)
#17 0x000056064f3145ad llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x2fe65ad)
#18 0x000056064eb087f4 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x27da7f4)
#19 0x000056064cfb9a0d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0xc8ba0d)
#20 0x000056064eb0cbde llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27debde)
#21 0x000056064cfb97ad llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0xc8b7ad)
#22 0x000056064eb07984 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27d9984)
#23 0x000056064cbf35ee llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x8c55ee)
#24 0x000056064cc01cbe main (../../main-github/llvm/build-all/bin/opt+0x8d3cbe)
#25 0x00007f3f0ce3b555 __libc_start_main (/lib64/libc.so.6+0x22555)
#26 0x000056064cbedd40 _start (../../main-github/llvm/build-all/bin/opt+0x8bfd40)
Abort (core dumped)

bbi-83751.ll1 KBDownload

[nikic]

@uabelho Thanks for the report! Always nice when reverts also regress things... I've submitted a possible solution at https://reviews.llvm.org/D153145.

llvm/lib/Transforms/Utils/LCSSA.cpp

while (!Worklist.empty()) {
 
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
     SmallVector<PHINode *, 4> InsertedPHIs;
     SSAUpdater SSAUpdate(&InsertedPHIs);
     SSAUpdate.Initialize(I->getType(), I->getName());
 
-    // Force re-computation of I, as some users now need to use the new PHI
-    // node.
-    if (SE)
-      SE->forgetValue(I);
-
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
       if (SSAUpdate.HasValueForBlock(ExitBB))