LLVM ERROR: Instruction Combining did not reach a fixpoint after 1 iterations

[TatyanaDoubts]

FuzzGen generated test failed with the error above.

run opt with -passes=instcombine
https://godbolt.org/z/9n5djc1Mh
There is an entry #65107, but it seems below is more interesting testcase.

Test.ll

; ModuleID = 'gen_00017'
source_filename = "gen_00017"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(inaccessiblemem: write)
declare void @llvm.assume(i1 noundef) #1

define i1 @function_0(i64 %val_i64_10, i16 %val_i16_17) {
entry_1:
  %val_i1_47 = trunc i64 %val_i64_10 to i1
  %val_i64_64 = zext i1 %val_i1_47 to i64
  br label %prhdr_loop_5

bb_3:                                             ; preds = %loop_6, %bb_3
  %struct_val_i64_71 = cmpxchg ptr null, i64 0, i64 %val_i64_64 syncscope("singlethread") monotonic monotonic, align 8
  br i1 false, label %bb_3, label %prhdr_loop_5

prhdr_loop_5:                                     ; preds = %bb_3, %entry_1
  %val_i32_74 = trunc i64 %val_i64_64 to i32
  %val_i1_76 = trunc i32 %val_i32_74 to i1
  call void @llvm.assume(i1 %val_i1_47)
  br label %loop_6

loop_6:                                           ; preds = %be_8, %prhdr_loop_5
  br i1 %val_i1_47, label %be_8, label %bb_3

be_8:                                             ; preds = %loop_6
  call void @llvm.assume(i1 %val_i1_76)
  br label %loop_6
}

Stack dump:

0.	Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes instcombine <source>
 #0 0x00000000035a87a8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x35a87a8)
 #1 0x00000000035a5efc SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f93f4042520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007f93f40969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x00007f93f4042476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007f93f40287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x0000000000790ecd llvm::json::operator==(llvm::json::Value const&, llvm::json::Value const&) (.cold) JSON.cpp:0:0
 #7 0x000000000315b551 combineInstructionsOverFunction(llvm::Function&, llvm::InstructionWorklist&, llvm::AAResults*, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::OptimizationRemarkEmitter&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*, llvm::LoopInfo*, llvm::InstCombineOptions const&) (.isra.0) InstructionCombining.cpp:0:0
 #8 0x000000000315bbcb llvm::InstCombinePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x315bbcb)
 #9 0x00000000037afbfe llvm::detail::PassModel<llvm::Function, llvm::InstCombinePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x37afbfe)
#10 0x0000000000d8763d 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>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xd8763d)
#11 0x0000000002f456fe llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f456fe)
#12 0x0000000000d6b97e llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xd6b97e)
#13 0x0000000002f436ac llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f436ac)
#14 0x000000000089673a 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, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x89673a)
#15 0x000000000079cd53 main (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x79cd53)
#16 0x00007f93f4029d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#17 0x00007f93f4029e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#18 0x000000000088b98e _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x88b98e)
Program terminated with signal: SIGSEGV
Compiler returned: 139

[gargaroff]

I just ran into the same error on the following simple reproducer: https://godbolt.org/z/8hfeP58z6
I think the issue on my reproducer stems from InstCombine canonicalizing the icmp slt 0, %val to icmp sgt %val, 0, which seems to impact the KnownBits analysis. As %val is never re-added to the worklist, it's not revisited and the 2nd iteration will add a nuw flag to the shl.

Edit: I tried to confirm my theory and fix it by adding the users of non-constant Cmp operands, but for some reason it's still not fixing the issue. I don't understand why KnownBits is only able to compute the min number of leading zeros only in the 2nd iteration

[gargaroff]

Ok this has nothing to do with the ICMP. Something is really weird: https://godbolt.org/z/ebsYKKPKG
Looking at this reproducer, even though the first iteration only sinks the shl, the 2nd iteration then adds the nuw flag.

Sinking the shl manually makes InstCombine pass...

[gargaroff]

I managed to find a one-line fix for the issue. I also saw that this is a known issue in sink_instructions.ll. With that one-line fix applied, that test now passes. I'll try to prepare a patch for it tomorrow.