opt -passes='loop-interchange' crashes with "bad subscript classification UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!" #51512

mikaelholmen · 2021-10-14T05:36:43Z


Bugzilla Link	52170
Version	trunk
OS	Linux
Attachments	bbi-61519.ll reproducer

Extended Description

llvm commit: 0fbd3aa

Reproduce with:
opt -passes='loop-interchange' -o /dev/null bbi-61519.ll

Result:
bad subscript classification
UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0. Program arguments: ../../master-github/llvm/build-all/bin/opt -passes=loop-interchange -o /dev/null bbi-61519.ll
#0 0x0000000002b5b8c3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../master-github/llvm/build-all/bin/opt+0x2b5b8c3)
#1 0x0000000002b5953e llvm::sys::RunSignalHandlers() (../../master-github/llvm/build-all/bin/opt+0x2b5953e)
#2 0x0000000002b5bc46 SignalHandler(int) Signals.cpp:0:0
#3 0x00007efe70534630 __restore_rt sigaction.c:0:0
#4 0x00007efe6dc67387 raise (/lib64/libc.so.6+0x36387)
#5 0x00007efe6dc68a78 abort (/lib64/libc.so.6+0x37a78)
#6 0x0000000002ad8d5f (../../master-github/llvm/build-all/bin/opt+0x2ad8d5f)
#7 0x0000000001a4e606 llvm::DependenceInfo::depends(llvm::Instruction*, llvm::Instruction*, bool) (../../master-github/llvm/build-all/bin/opt+0x1a4e606)
#8 0x00000000028ec1db (anonymous namespace)::LoopInterchange::processLoopList(llvm::ArrayRefllvm::Loop*) LoopInterchange.cpp:0:0
#9 0x00000000028eb21a llvm::LoopInterchangePass::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x28eb21a)
#10 0x0000000002e606dd llvm::detail::PassModel<llvm::LoopNest, llvm::LoopInterchangePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0
#11 0x0000000003375b6c llvm::Optionalllvm::PreservedAnalyses llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::LoopNest, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::LoopNest&, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (../../master-github/llvm/build-all/bin/opt+0x3375b6c)
#12 0x0000000003374fb3 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&) (../../master-github/llvm/build-all/bin/opt+0x3374fb3)
#13 0x0000000003374b91 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&) (../../master-github/llvm/build-all/bin/opt+0x3374b91)
#14 0x0000000002e3256d 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&) crtstuff.c:0:0
#15 0x0000000003376a6b llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (../../master-github/llvm/build-all/bin/opt+0x3376a6b)
#16 0x0000000002e4dc8d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) crtstuff.c:0:0
#17 0x0000000002308fd5 llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (../../master-github/llvm/build-all/bin/opt+0x2308fd5)
#18 0x0000000000ad615d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) crtstuff.c:0:0
#19 0x000000000230d356 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (../../master-github/llvm/build-all/bin/opt+0x230d356)
#20 0x000000000078f47d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) crtstuff.c:0:0
#21 0x0000000002308118 llvm::PassManager<llvm::Module, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (../../master-github/llvm/build-all/bin/opt+0x2308118)
#22 0x00000000007872a2 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRefllvm::StringRef, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool) (../../master-github/llvm/build-all/bin/opt+0x7872a2)
#23 0x0000000000799e86 main (../../master-github/llvm/build-all/bin/opt+0x799e86)
#24 0x00007efe6dc53555 __libc_start_main (/lib64/libc.so.6+0x22555)
#25 0x00000000007826fc _start (../../master-github/llvm/build-all/bin/opt+0x7826fc)
Abort

Starts crashing with commit 7086025:
[Dependence Analysis] Enable delinearization of fixed sized arrays

Patch by Artem Radzikhovskyy!

Allow delinearization of fixed sized arrays if we can prove that the GEP indices do not overflow the array dimensions. The checks applied are similar to the ones that are used for delinearization of parametric size arrays. Make sure that the GEP indices are non-negative and that they are smaller than the range of that dimension.

Changes Summary:

- Updated the LIT tests with more exact values, as we are able to delinearize and apply more exact tests
- profitability.ll - now able to delinearize in all cases, no need to use -da-disable-delinearization-checks flag and run the test twice
- loop-interchange-optimization-remarks.ll - in one of the cases we are able to delinearize without using -da-disable-delinearization-checks
- SimpleSIVNoValidityCheckFixedSize.ll - removed unnecessary "-da-disable-delinearization-checks" flag. Now can get the exact answer without it.
- SimpleSIVNoValidityCheckFixedSize.ll and PreliminaryNoValidityCheckFixedSize.ll - made negative tests more explicit, in order to demonstrate the need for "-da-disable-delinearization-checks" flag

Differential Revision: https://reviews.llvm.org/D101486

The text was updated successfully, but these errors were encountered:

llvmbot · 2022-01-16T05:59:22Z

@llvm/issue-subscribers-bug

fhahn · 2022-01-17T18:44:17Z

cc @andykaylor

artemrad · 2022-02-04T15:31:10Z

The following commit 7086025 enabled delinearization of fixed sized arrays. It is now possible to propagate SIV constraints to other coupled subscripts in more cases, resulting in more accurate dependence analysis. When a SIV constraint is propagated we re-classify the other non-SIV subscripts. It is possible that the re-classified subscript is now marked as non-linear, in cases where we cannot prove that the taken backedge of the loop may not overflow. In such cases DependenceAnalysis should conservatively report that a dependence may be present instead of crashing the compiler with llvm_unreachable.

Actively working on a fix.

artemrad · 2022-02-08T17:53:59Z

Posted a review https://reviews.llvm.org/D119261

dfszabo · 2024-09-17T13:19:44Z

Shouldn't this issue be closed already?

bjope · 2024-09-17T13:58:40Z

Afaict it still hits UNREACHABLE: https://godbolt.org/z/MY5seqoPc

mikaelholmen · 2024-09-18T05:03:06Z

Shouldn't this issue be closed already?

As @bjope said the reproducer in the description still hits the descibed UNREACHABLE.
The review https://reviews.llvm.org/D119261 never got accepted or submitted.

madhur13490 · 2024-10-21T23:33:06Z

@artemrad Are you planning to resurrect the patch and proceed? https://reviews.llvm.org/D119261

sebpop · 2024-11-15T01:28:21Z

Patch in https://reviews.llvm.org/D119261 makes no sense to me: it weakens sanity checks for subscripts upper bounds.

DA generates SCEVs to represent constraints for coupled subscripts.
DA wrongly uses wrap-around arithmetic SCEV::FlagAnyWrap and the semantics of such evolutions lead to "non-linear" effects which are unexpected this late in the dependence test.
The fix is to use NSW arithmetic.

I will post a patch for review, like this:

--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -3166,7 +3166,7 @@ const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
     return SE->getAddRecExpr(Expr,
                              Value,
                              TargetLoop,
-                             SCEV::FlagAnyWrap); // Worst case, with no info.
+                             SCEV::FlagNSW); // Worst case, with no info.
   if (AddRec->getLoop() == TargetLoop) {
     const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);
     if (Sum->isZero())
@@ -3177,7 +3177,7 @@ const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
                              AddRec->getNoWrapFlags());
   }
   if (SE->isLoopInvariant(AddRec, TargetLoop))
-    return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
+    return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagNSW);
   return SE->getAddRecExpr(
       addToCoefficient(AddRec->getStart(), TargetLoop, Value),
       AddRec->getStepRecurrence(*SE), AddRec->getLoop(),

nikic · 2024-11-15T11:49:45Z

@sebpop I haven't looked at the context here, but you generally have to be very careful with passing nowrap flags to getAddRecExpr. Passing a flag here doesn't mean "analyze this under the assumption of no overflow", it means "it is UB for this addrec to overflow" as a global, context-independent promise.

sebpop · 2024-11-15T15:05:45Z

Thanks @nikic for the heads'up comment. I believe the intended meaning is undefined behavior on overflow.

The AddRec SCEVs generated here are "left-over" constraints produced by intersection of two systems of linear constraints. Using NSW allows DA to continue solving the constraints with linear equations instead of modulo arithmetic, i.e., wrap arounds, which is non-linear.

DA uses SCEV to solve linear constraints. When it generates SCEVs with negative strides, i.e., {0,+,-1}, make sure the SCEVs are marked as non wrap arithmetic. This patch fixes llvm#51512

This patch fixes llvm#51512 DA uses SCEVs to represent linear constraints on memory accesses. addToCoefficient is only called from the "Constraint Propagation engine": https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/DependenceAnalysis.cpp#L3877 The propagation engine works on MIV subscripts. MIV subscripts are pairs of *linear* memory accesses that vary in multiple loops. At this point all memory accesses are linear, non-linear have been filtered out. When addToCoefficient creates an AddRec with flags SCEV::FlagAnyWrap, classifyPair returns llvm::DependenceInfo::Subscript::NonLinear. https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/DependenceAnalysis.cpp#L3882 Having a non-linear effect this late in the dependence test is surprising, and the test fails with llvm_unreachable("bad subscript classification"). Instead of building non-linear functions, this patch modifies the flags to SCEV::FlagNSW that has the meaning of linear functions that do not wrap around.

Revert part of llvm@c0661ae that modified the definition of what an affine subscript is. This patch fixes llvm#51512

Fix llvm#51512 by reverting a part of commit llvm@c0661ae that modified the definition affine subscripts.

…632) Fix llvm/llvm-project#51512 by reverting a part of commit llvm/llvm-project@c0661ae that modified the definition affine subscripts.

llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021

EugeneZelenko added bug Indicates an unexpected problem or unintended behavior tools:opt labels Jan 16, 2022

fhahn added the llvm:crash label Jan 17, 2022

EugeneZelenko added crash Prefer [crash-on-valid] or [crash-on-invalid] llvm:analysis and removed tools:opt llvm:crash labels Sep 17, 2024

sebpop mentioned this issue Nov 15, 2024

Bug fixes for Array Dependence Analysis #116389

Closed

sebpop mentioned this issue Nov 18, 2024

[DA] remove wrap-around check from affine definition #116632

Merged

sebpop added a commit to sebpop/llvm-project that referenced this issue Feb 6, 2025

[DA] use NSW arithmetic

11aaf58

Revert part of llvm@c0661ae that modified the definition of what an affine subscript is. This patch fixes llvm#51512

sebpop added a commit to sebpop/llvm-project that referenced this issue Feb 11, 2025

[DA] remove wrap-around check from affine definition

baf23e1

Revert part of llvm@c0661ae that modified the definition of what an affine subscript is. This patch fixes llvm#51512

sebpop added a commit to sebpop/llvm-project that referenced this issue Feb 21, 2025

[DA] remove wrap-around check from affine definition

e20a742

Fix llvm#51512 by reverting a part of commit llvm@c0661ae that modified the definition affine subscripts.

sebpop closed this as completed in #116632 Feb 22, 2025

sebpop closed this as completed in 5f8da7e Feb 22, 2025

EugeneZelenko removed the bug Indicates an unexpected problem or unintended behavior label Feb 22, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

opt -passes='loop-interchange' crashes with "bad subscript classification UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!" #51512

opt -passes='loop-interchange' crashes with "bad subscript classification UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!" #51512

mikaelholmen commented Oct 14, 2021

llvmbot commented Jan 16, 2022

Uh oh!

fhahn commented Jan 17, 2022

Uh oh!

artemrad commented Feb 4, 2022

Uh oh!

artemrad commented Feb 8, 2022

Uh oh!

dfszabo commented Sep 17, 2024

Uh oh!

bjope commented Sep 17, 2024

Uh oh!

mikaelholmen commented Sep 18, 2024

Uh oh!

madhur13490 commented Oct 21, 2024

Uh oh!

sebpop commented Nov 15, 2024

Uh oh!

nikic commented Nov 15, 2024

Uh oh!

sebpop commented Nov 15, 2024

Uh oh!

opt -passes='loop-interchange' crashes with "bad subscript classification UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!" #51512

opt -passes='loop-interchange' crashes with "bad subscript classification UNREACHABLE executed at ../lib/Analysis/DependenceAnalysis.cpp:3833!" #51512

Comments

mikaelholmen commented Oct 14, 2021

Extended Description

llvmbot commented Jan 16, 2022

Uh oh!

fhahn commented Jan 17, 2022

Uh oh!

artemrad commented Feb 4, 2022

Uh oh!

artemrad commented Feb 8, 2022

Uh oh!

dfszabo commented Sep 17, 2024

Uh oh!

bjope commented Sep 17, 2024

Uh oh!

mikaelholmen commented Sep 18, 2024

Uh oh!

madhur13490 commented Oct 21, 2024

Uh oh!

sebpop commented Nov 15, 2024

Uh oh!

nikic commented Nov 15, 2024

Uh oh!

sebpop commented Nov 15, 2024

Uh oh!