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.

[TatyanaDoubts]

To reproduce run opt with the test below (-passes=loop-vectorize ):

; ModuleID = './reduced.ll'
source_filename = "./reduced.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

define ptr addrspace(1) @wombat(i32 %arg) gc "statepoint-example" {
bb:
  %select = select i1 false, i32 0, i32 8
  br label %bb3

bb1:                                              ; preds = %bb3
  br i1 false, label %bb4, label %bb9

bb2:                                              ; No predecessors!
  %zext = zext i32 %select to i64
  br label %bb3

bb3:                                              ; preds = %bb3, %bb2, %bb
  %phi = phi i64 [ %zext, %bb2 ], [ 0, %bb3 ], [ 0, %bb ]
  br i1 false, label %bb1, label %bb3

bb4:                                              ; preds = %bb4, %bb1
  %phi5 = phi i64 [ %add7, %bb4 ], [ 0, %bb1 ]
  %phi6 = phi i32 [ %add, %bb4 ], [ %arg, %bb1 ]
  %add = add i32 %phi6, 1
  %add7 = add i64 %phi5, 1
  %shl = shl i32 %phi6, 1
  %zext8 = zext i32 %shl to i64
  %getelementptr = getelementptr i8, ptr addrspace(1) null, i64 %zext8
  store i16 0, ptr addrspace(1) %getelementptr, align 2
  %icmp = icmp ult i64 %phi5, %phi
  br i1 %icmp, label %bb4, label %bb15

bb9:                                              ; preds = %bb9, %bb1
  %phi10 = phi i64 [ %add12, %bb9 ], [ 0, %bb1 ]
  %getelementptr11 = getelementptr i8, ptr addrspace(1) null, i64 %phi10
  store i8 0, ptr addrspace(1) %getelementptr11, align 1
  %add12 = add i64 %phi10, 1
  %icmp13 = icmp ult i64 %add12, %phi
  br i1 %icmp13, label %bb9, label %bb14

bb14:                                             ; preds = %bb9
  ret ptr addrspace(1) null

bb15:                                             ; preds = %bb4
  ret ptr addrspace(1) null
}

Reproducer: https://godbolt.org/z/67vadzMbr
Stack dump:

0.	Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=loop-vectorize <source>
1.	Running pass "function(loop-vectorize<no-interleave-forced-only;no-vectorize-forced-only;>)" on module "<source>"
2.	Running pass "loop-vectorize<no-interleave-forced-only;no-vectorize-forced-only;>" on function "wombat"
 #0 0x000000000525d5d8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x525d5d8)
 #1 0x000000000525afdc SignalHandler(int) Signals.cpp:0:0
 #2 0x00007cf6f6042520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007cf6f60969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x00007cf6f6042476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007cf6f60287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x00007cf6f602871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x00007cf6f6039e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x00000000045a6237 llvm::SCEVExpanderCleaner::cleanup() (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x45a6237)
 #9 0x00000000041cf7df (anonymous namespace)::GeneratedRTChecks::~GeneratedRTChecks() LoopVectorize.cpp:0:0
#10 0x0000000004227f36 llvm::LoopVectorizePass::processLoop(llvm::Loop*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4227f36)
#11 0x0000000004229cc9 llvm::LoopVectorizePass::runImpl(llvm::Function&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4229cc9)
#12 0x000000000422a303 llvm::LoopVectorizePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x422a303)
#13 0x0000000003029e0e llvm::detail::PassModel<llvm::Function, llvm::LoopVectorizePass, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3029e0e)
#14 0x000000000505b4d0 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x505b4d0)
#15 0x0000000000e6bc0e llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xe6bc0e)
#16 0x0000000005059deb llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x5059deb)
#17 0x0000000000e6b29e llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xe6b29e)
#18 0x00000000050597f0 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x50597f0)
#19 0x0000000000941fba llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::ArrayRef<std::function<void (llvm::PassBuilder&)>>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x941fba)
#20 0x0000000000934559 optMain (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x934559)
#21 0x00007cf6f6029d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#22 0x00007cf6f6029e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#23 0x000000000092be35 _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x92be35)
Program terminated with signal: SIGSEGV

[TatyanaDoubts]

Triage on our side found the fault commit

commit 6dc23b7

Author: Nikita Popov <npopov@redhat.com>

Date: Mon Nov 11 12:36:29 2024 +0100

[SCEVExpander] Don't try to reuse SCEVUnknown values (#115141)



The expansion of a SCEVUnknown is trivial (it's just the wrapped value).

If we try to reuse an existing value it might be a more complex

expression that simplifies to the SCEVUnknown.



This is inspired by [WRONG code: GVN? Loop opts? · Issue #114879 · llvm/llvm-project](https://github.com/llvm/llvm-project/issues/114879) ,

because SCEVExpander replacing a constant with a phi node is just silly.

(I don't consider this a fix for that issue though.)

@nikic , could you please have a look? Thank you!

[danilaml]

Looks like when FindValueInExprValueMap returns a nullptr (like it does for a phi in reproducer after SCEVUnknown changes) the code runs fixupLCSSAFormFor. This function runs llvm::formLCSSAForInstructions that can insert a new LCSSA phi and more importantly can rewrite the uses of instructions in the worklist. So what happens is this function is run, new phi is added, some old phi uses are replaced with this new phi, then the changes are "rolled back", i.e. the cleanup is called on SCEVExpander, it tries to remove the inserted lcssa phi but it doesn't know how to rewrite the uses back so it just asserts (since those users were not inserted by the expander itself, they were already there - they just had their arguments replaced to use instruction from expander).

@nikic this looks like an old issue, although I wasn't yet able to figure out how to trigger it before SCEVUnknown changes (and if it even practically possible or just theoretically).

[danilaml]

fixupLCSSAFormFor was introduced by @fhahn so perhaps they have a better understanding where the issue lies.

[nikic]

I think there are two issues here:

1. It looks like LV is generating references to the TC that break LCSSA form.
2. SCEVExpander cleanup can't handle the case where LCSSA formation modified existing uses.

[nikic]

This is a possible fix for the SCEVExpander issue: nikic@3217b04

But after thinking about this, I'm not convinced that SCEVExpander really needs fixing. It is being invoked in PreserveLCSSA mode, so it should be able to rely on the original IR being in LCSSA form.

Note that the [[N_RND_UP:%.*]] = add i64 [[PHI]], 15 in nikic@3217b04#diff-9e3a00a1cffe1764ee50ab6c79bdea53cd1847cf7b77810a4cdc6835bfc79a52R44 doesn't satisfy LCSSA form, it should be using PHI_LCSSA.

Maybe @fhahn could take a look at the LoopVectorize issue?

I could also be convinced to land the SCEVExpander change, as it seems harmless even if LV is fixed...

[fhahn]

Yep, I'll take a look in the next few days

[fhahn]

#125235 should fix the place where LCSSA is broken