[LoopInterchange] Assertion `getActiveBits() <= 64 && "Too many bits for uint64_t"

[sjoerdmeijer]

With options "-O3 --target=aarch64 func.cpp -mllvm -enable-loopinterchange" and this input:

unsigned int A[11][11][11] __attribute__((aligned(16)));
void a(int b) {
  for (int c;; c += b)
    for (long d = 0; d < -3ULL; d += 2ULL)
      A[c][d][d] = 0;
}

Loop-interchange runs in an assert:

llvm-project/llvm/include/llvm/ADT/APInt.h:1501: uint64_t llvm::APInt::getZExtValue() const: Assertion `getActiveBits() <= 64 && "Too many bits for uint64_t"' failed.

IR reproducer, compile this with "opt -passes=loop-interchange -S":

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-Fn32"
target triple = "aarch64-unknown-linux-gnu"

@A = local_unnamed_addr global [11 x [11 x [11 x i32]]] zeroinitializer, align 16

define void @_Z1ai(i32 noundef %b) local_unnamed_addr #0 {
entry:
  %0 = sext i32 %b to i64
  br label %for.cond

; Loop:
for.cond:                                         ; preds = %for.cond.cleanup, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.cond.cleanup ], [ 0, %entry ]
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body
  %indvars.iv.next = add nsw i64 %indvars.iv, %0
  br label %for.cond

for.body:                                         ; preds = %for.cond, %for.body
  %d.010 = phi i64 [ 0, %for.cond ], [ %add, %for.body ]
  %arrayidx3 = getelementptr inbounds [11 x [11 x [11 x i32]]], ptr @A, i64 0, i64 %indvars.iv, i64 %d.010, i64 %d.010
  store i32 0, ptr %arrayidx3, align 4
  %add = add nuw i64 %d.010, 2
  %cmp = icmp ult i64 %d.010, -5
  br i1 %cmp, label %for.body, label %for.cond.cleanup
}

[RKSimon]

opt: /root/llvm-project/llvm/include/llvm/ADT/APInt.h:1501: uint64_t llvm::APInt::getZExtValue() const: Assertion `getActiveBits() <= 64 && "Too many bits for uint64_t"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.  Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=loop-interchange -debug <source>
1.  Running pass "function(loop(loop-interchange))" on module "<source>"
2.  Running pass "loop(loop-interchange)" on function "_Z1ai"
 #0 0x0000000004f7f528 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4f7f528)
 #1 0x0000000004f7cc9c SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f497b842520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007f497b8969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x00007f497b842476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007f497b8287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x00007f497b82871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x00007f497b839e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x00000000045677cc llvm::IndexedReference::computeRefCost(llvm::Loop const&, unsigned int) const (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x45677cc)
 #9 0x000000000456995f llvm::CacheCost::computeLoopCacheCost(llvm::Loop const&, llvm::SmallVector<llvm::SmallVector<std::unique_ptr<llvm::IndexedReference, std::default_delete<llvm::IndexedReference>>, 8u>, 8u> const&) const (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x456995f)
#10 0x000000000456c137 llvm::CacheCost::calculateCacheFootprint() (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x456c137)
#11 0x0000000004573d5c llvm::CacheCost::getCacheCost(llvm::Loop&, llvm::LoopStandardAnalysisResults&, llvm::DependenceInfo&, std::optional<unsigned int>) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4573d5c)
#12 0x0000000003c71d66 llvm::LoopInterchangePass::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3c71d66)
#13 0x0000000002eb0a6e llvm::detail::PassModel<llvm::LoopNest, llvm::LoopInterchangePass, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2eb0a6e)
#14 0x0000000003c85255 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3c85255)
#15 0x0000000003c85ce3 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&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3c85ce3)
#16 0x0000000003c868b8 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3c868b8)
#17 0x0000000000df128e llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xdf128e)
#18 0x0000000004d7c368 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4d7c368)
#19 0x0000000000df14be 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+0xdf14be)
#20 0x0000000004d7ad5e llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4d7ad5e)
#21 0x0000000000df0f8e 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+0xdf0f8e)
#22 0x0000000004d78ec0 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4d78ec0)
#23 0x00000000008e7582 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+0x8e7582)
#24 0x00000000008da45c optMain (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x8da45c)
#25 0x00007f497b829d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#26 0x00007f497b829e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#27 0x00000000008d1eee _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x8d1eee)

Which seems to be due to the getZExtValue() call inside IndexedReference::computeRefCost https://github.com/llvm/llvm-project/blob/b05c55472bf7cadcd0e4cb1a669b3474695b0524/llvm/lib/Analysis/LoopCacheAnalysis.cpp#L340:L343

[svs-quic]

cc: @caojoshua

[sjoerdmeijer]

I have a fix, will put it up for review tomorrow.