This is an archive of the discontinued LLVM Phabricator instance.

[SCEVExpander] Add helper to clean up instrs inserted while expanding.
ClosedPublic

Authored by fhahn on Jul 22 2020, 7:30 AM.

Details

Summary

SCEVExpander already tracks which instructions have been inserted n
InsertedValues/InsertedPostIncValues. This patch adds an additional
vector to collect the instructions in insertion order. This can then be
used to remove exactly the instructions inserted by the expander.

This replaces ExpandedValuesCleaner, which in some cases might remove
values not inserted by the expander (e.g. if a value was dead before
insertion and is then used during expansion).

Diff Detail

Event Timeline

fhahn created this revision.Jul 22 2020, 7:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 22 2020, 7:30 AM

This looks about right to me. Some thoughts.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
64

Should this also be AssertingVH, just to be extra safe?

457

This doesn't read as a setter to me i'm afraid.
Maybe either keep commit(), or at least markResultAsUsed(), or something.

Good call. This is definitely a better place for that to live.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1119

I think the interface between SCEVExpanderCleaner and SCEVExpander should be a subscriber/consumer model, and the cleaner should own the tracking of what gets added, rather than the expander. Then SCEVExpanderCleaner can hook into IRBuilderCallbackInserter to track these too.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1242

Where does InsertedValues differ from InsertedInstructions? Should the former be re-used with an appropriate isa<Instruction>() filter, rather than keeping two separate lists?

fhahn marked 2 inline comments as done.Jul 22 2020, 10:03 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1119

I am not sure. What would the benefit be? SCEVExpander already needs to track which values it inserted for some internal optimizations, so hooking up 2 different callbacks seems to make things more complex than they need to be. But as mentioned inline earlier, we don't really need the extra vector, we can combine the sets and sort them.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1242

The main purpose of a separate list is to keep track of the insertion order, while InsertedValues/InsertedPostIncValues are sets. We could trade the extra memory cost for extra compile-time cost, by combing the sets and sort them by. dominance when it comes to deleting.

jroelofs added inline comments.Jul 22 2020, 10:32 AM
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1119

Oh, never mind. I misread the early return on line 1127 as post-dominating this insertion, and thought it needed to be cleaned up if that happened.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
1242

Ah, ok. Sounds not worth it.

fhahn updated this revision to Diff 280095.Jul 23 2020, 6:44 AM

I explored getting rid of the InsertedInstructions vector and instead combine & sort the existing sets.

I think this is probably beneficial, as long as cleaning up remains more uncommon. The removal logic is also updated, to also work for inserted PHIs. The patch now replaces all uses of a rewritten value with undef before removing. This works fine, if all uses are part of instructions inserted by the expander (which will be removed).

I added an assertion to ensure that, which uncovered a case where the expander actually modifies uses outside of the instructions it creates. This needs to be addressed first, I put up D84399.

lebedev.ri accepted this revision.Jul 24 2020, 2:10 PM

LG to me, but probably wait a bit for @jroelofs.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
181

I think it's not unreasonable to reserve the worst-case final size?

450

bool ResultUsed = false;

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2543–2544

You need to wrap this into #ifndef NDEBUG, we won't manage to optimize this out
https://godbolt.org/z/Mhq5P1

This revision is now accepted and ready to land.Jul 24 2020, 2:10 PM
lebedev.ri added inline comments.Jul 24 2020, 2:14 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2543–2544

Correction: it looks slightly less ugly -RTTI -EH, but still: https://godbolt.org/z/sjr1dd

LG to me, but probably wait a bit for @jroelofs.

LGTM also

fhahn updated this revision to Diff 284605.Aug 11 2020, 1:30 AM

Rebase, guard InsertedSet by ifndef NDEBUG, add messages to asserts, increase size of getAllInsertedInstrs result vector.

This revision was landed with ongoing or failed builds.Aug 11 2020, 1:38 AM
This revision was automatically updated to reflect the committed changes.

FYI, I reverted this in 38884641f28e373ce291dc5ea93416756216e536 due to the assertion failure being triggered. The reduction is taking longer than usual, so I wasn't able to finish it today. I should be able to have something on Monday.

It's down to a couple hundred lines of C++, but when I try to get an IR reduction (e.g. using -Xclang -disable-O0-optnone -S -emit-llvm), the crash does not reproduce. And creduce doesn't seem to know how to reduce a bunch of the stuff (heavy on the templates), so I'm paring it down manually.

The assertion failure is only with the new pass manager, btw.

Here's as far as I could get with a repro. Sorry it's weird:

$ cat /tmp/repro.cc 
template <typename bm>
class b {
 public:
  b(bm d) : bn(d) {}
  template <typename bo>
  void operator=(bo d) {
    bh(bn, d);
  }
  bm bn;
};

template <typename>
class c;

template <typename a>
class e {
 public:
  b<a> ai() { return *static_cast<a *>(this); }
  c<a> ag(long d) { return c<a>(a(), d); }
};

template <typename ax, typename bg>
void bh(ax d, bg g) {
  float *h = d.al(), *k = g.al();
  for (long f; f; ++f) h[f] = k[f];
}

class n : public e<n> {
 public:
  float *al();
};

class o : public e<c<int> > {
 public:
  float *al() { return ak; }
  o(float *d) : ak(d) {}
  float *ak;
};

template <typename aj>
class c : public o {
 public:
  c(aj d, long g) : o(d.al() + g) {}
};

n l, m;
void by() {
  for (int j = 0, i = 0;; ++j, i += j) m.ag(i).ai() = l;
}
$ clang -O1 -fexperimental-new-pass-manager -c /tmp/repro.cc -o /tmp/repro.o                                                                                                                                                                                                         
clang: /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2663: llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner(): Assertion `all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: bin/clang -O1 -fexperimental-new-pass-manager -c /tmp/repro.cc -o /tmp/repro.o
1.      <eof> parser at end of file
2.      Optimizer
 ....
#12 0x0000000008d6eac0 llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner() /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2665:5
#13 0x00000000088ebc6e (anonymous namespace)::LoopIdiomRecognize::processLoopStoreOfLoopLoad(llvm::StoreInst*, llvm::SCEV const*) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:1174:1
#14 0x00000000088e9e0d (anonymous namespace)::LoopIdiomRecognize::runOnLoopBlock(llvm::BasicBlock*, llvm::SCEV const*, llvm::SmallVectorImpl<llvm::BasicBlock*>&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:589:19
#15 0x00000000088e99f1 (anonymous namespace)::LoopIdiomRecognize::runOnCountableLoop() /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:366:19
#16 0x00000000088e91ce (anonymous namespace)::LoopIdiomRecognize::runOnLoop(llvm::Loop*) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:326:7
#17 0x00000000088e8e26 llvm::LoopIdiomRecognizePass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:274:7
#18 0x000000000a70b885 llvm::detail::PassModel<llvm::Loop, llvm::LoopIdiomRecognizePass, 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&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#19 0x000000000a892f8c 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&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopPassManager.cpp:45:14
#20 0x000000000a70d83a llvm::FunctionToLoopPassAdaptor<llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h:335:16
#21 0x000000000a70d445 llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor<llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#22 0x000000000814afc0 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#23 0x000000000a719ff8 llvm::CGSCCToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:508:16
#24 0x000000000a719d05 llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#25 0x0000000008209465 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:84:14
#26 0x0000000008364046 llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:641:11
#27 0x0000000008363787 llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:902:20
#28 0x0000000008362ed5 llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#29 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#30 0x0000000008350706 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/IPO/Inliner.cpp:1072:3
#31 0x000000000a71a835 llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#32 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#33 0x000000000a7340f5 llvm::detail::PassModel<llvm::Module, llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#34 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#35 0x0000000009015591 (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1460:5
#36 0x00000000090122e5 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1685:5
#37 0x0000000009cb0155 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:335:7
#38 0x000000000c2b1658 clang::ParseAST(clang::Sema&, bool, bool) /home/rupprecht/src/llvm-project/clang/lib/Parse/ParseAST.cpp:178:12
#39 0x0000000009add31d clang::ASTFrontendAction::ExecuteAction() /home/rupprecht/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1059:1
#40 0x0000000009cac47f clang::CodeGenAction::ExecuteAction() /home/rupprecht/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1183:1
#41 0x0000000009adcce8 clang::FrontendAction::Execute() /home/rupprecht/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:954:7
#42 0x0000000009a0b5fc clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/rupprecht/src/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:984:23
#43 0x0000000009c981ed clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/rupprecht/src/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278:8
#44 0x0000000005ae603c cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /home/rupprecht/src/llvm-project/clang/tools/driver/cc1_main.cpp:240:13
...

Thanks for the reproducer! Looking into what is going wrong now.

fhahn added a comment.Aug 21 2020, 7:08 AM

I recommitted the change in 8eded24bf46c05ffd110d521f58320cdee93866e with a fix for the issue reported by @rupprecht, which was caused due to the expander also adding existing, re-used values to InsertedValues, which we should not try to remove.

I recommitted the change in 8eded24bf46c05ffd110d521f58320cdee93866e with a fix for the issue reported by @rupprecht, which was caused due to the expander also adding existing, re-used values to InsertedValues, which we should not try to remove.

I can confirm the recommit looks good, thanks!

I forgot to mention we actually saw this as a miscompile when building w/ a release build of clang; the assertion caught the underlying issue. Both the miscompile (with the release build) and the assertion (with the debug build) are gone now.