Assert on isForInductionVar in SuperVectorizer

[c-rhodes]

The following IR (taken from mlir/test/Integration/Dialect/Linalg/CPU/matmul-vs-matvec.mlir):

func @matvec(%A: memref<?x?xf32>, %B: memref<?x?xf32>) -> (memref<?x?xf32>) {
  %c0 = arith.constant 0 : index
  %c1 = arith.constant 1 : index
  %f0 = arith.constant 0.0 : f32
  %m = memref.dim %A, %c0 : memref<?x?xf32>
  %x = memref.dim %A, %c1 : memref<?x?xf32>
  %n = memref.dim %B, %c1 : memref<?x?xf32>
  %C = memref.alloc(%m, %n) : memref<?x?xf32>
  linalg.fill(%f0, %C) : f32, memref<?x?xf32>
  scf.for %i = %c0 to %n step %c1 {
    %b = memref.subview %B[0, %i][%x, 1][1, 1] : memref<?x?xf32> to memref<?xf32, offset: ?, strides: [?]>
    %c = memref.subview %C[0, %i][%m, 1][1, 1] : memref<?x?xf32> to memref<?xf32, offset: ?, strides: [?]>
    linalg.matvec ins(%A, %b: memref<?x?xf32>, memref<?xf32, offset: ?, strides: [?]>)
                  outs(%c: memref<?xf32, offset: ?, strides: [?]>)
  }
  return %C : memref<?x?xf32>
}

crashes in the SuperVectorizer:

./bin/mlir-opt ../mlir/test/Integration/Dialect/Linalg/CPU/matmul-vs-matvec.mlir -convert-linalg-to-affine-loops -affine-super-vectorize="virtual-vector-size=128"
mlir-opt: /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp:567: void mlir::FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(mlir::Value): Assertion `(isTopLevelValue(val) || isForInductionVar(val)) && "non-terminal symbol / loop
 IV expected"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ./bin/mlir-opt ../mlir/test/Integration/Dialect/Linalg/CPU/matmul-vs-matvec.mlir -convert-linalg-to-affine-loops -affine-super-vectorize=virtual-vector-size=128
1.      #0 0x0000ffff9d237c5c llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/culrho01/llvm-project/llvm/lib/Support/Unix/Signals.inc:565:11
[1]    21947 abort (core dumped)  ./bin/mlir-opt  -convert-linalg-to-affine-loops

The issue appears to be the upper bound of an AffineForOp is owned by an scf::ForOp, so isForInductionVar(val) triggers the assert. The IR after -convert-linalg-to-affine-loops is:

  func @matvec(%arg0: memref<?x?xf32>, %arg1: memref<?x?xf32>) -> memref<?x?xf32> {
    %c0 = arith.constant 0 : index
    %c1 = arith.constant 1 : index
    %cst = arith.constant 0.000000e+00 : f32
    %0 = memref.dim %arg0, %c0 : memref<?x?xf32>
    %1 = memref.dim %arg0, %c1 : memref<?x?xf32>
    %2 = memref.dim %arg1, %c1 : memref<?x?xf32>
    %3 = memref.alloc(%0, %2) : memref<?x?xf32>
    affine.for %arg2 = 0 to %0 {
      affine.for %arg3 = 0 to %2 {
        affine.store %cst, %3[%arg2, %arg3] : memref<?x?xf32>
      }
    }
    scf.for %arg2 = %c0 to %2 step %c1 {
      %4 = memref.subview %arg1[0, %arg2] [%1, 1] [1, 1] : memref<?x?xf32> to memref<?xf32, #map>
      %5 = memref.subview %3[0, %arg2] [%0, 1] [1, 1] : memref<?x?xf32> to memref<?xf32, #map>
      %6 = memref.dim %arg0, %c0 : memref<?x?xf32>
      %7 = memref.dim %arg0, %c1 : memref<?x?xf32>
      affine.for %arg3 = 0 to %6 {
        affine.for %arg4 = 0 to %7 {
          %8 = affine.load %arg0[%arg3, %arg4] : memref<?x?xf32>
          %9 = affine.load %4[%arg4] : memref<?xf32, #map>
          %10 = affine.load %5[%arg3] : memref<?xf32, #map>
          %11 = arith.mulf %8, %9 : f32
          %12 = arith.addf %10, %11 : f32
          affine.store %12, %5[%arg3] : memref<?xf32, #map>
        }
      }
    }
    return %3 : memref<?x?xf32>
  }

and the val that triggers the assert is: %6 = memref.dim %arg0, %c0 : memref<?x?xf32>.

Full backtrace:

#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x0000ffffeecc5d54 in __GI_abort () at abort.c:79
#2  0x0000ffffeecd261c in __assert_fail_base (fmt=0xffffeedcbc48 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=assertion@entry=0xfffff2456f86 "(isTopLevelValue(val) || isForInductionVar(val)) && \"non-terminal symbol / loop IV expected\"",
    file=file@entry=0xfffff244e7d6 "/home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp", line=line@entry=567, function=function@entry=0xfffff2448c46 "void mlir::FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(mlir::Value)")
    at assert.c:92
#3  0x0000ffffeecd2684 in __GI___assert_fail (assertion=0xfffff2456f86 "(isTopLevelValue(val) || isForInductionVar(val)) && \"non-terminal symbol / loop IV expected\"",
    file=0xfffff244e7d6 "/home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp", line=567, function=0xfffff2448c46 "void mlir::FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(mlir::Value)") at assert.c:101
#4  0x0000fffff2480c84 in mlir::FlatAffineValueConstraints::addInductionVarOrTerminalSymbol (this=0xffffeb6637c0, val=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp:566
#5  0x0000fffff2481390 in mlir::FlatAffineValueConstraints::addBound (this=0xffffeb6637c0, type=mlir::IntegerPolyhedron::UB, pos=0, boundMap=..., boundOperands=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp:1246
#6  0x0000fffff24811e4 in mlir::FlatAffineValueConstraints::addAffineForOpDomain (this=0xffffeb6637c0, forOp=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp:631
#7  0x0000fffff246ab4c in mlir::getIndexSet (ops=..., domain=0xffffeb6637c0) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:229
#8  0x0000fffff246aee4 in getOpIndexSet (op=0xffffe0006450, indexSet=0xffffeb6637c0) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:247
#9  0x0000fffff246ac78 in mlir::MemRefAccess::getAccessRelation (this=0xffffeb665728, rel=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:431
#10 0x0000fffff246a3c0 in mlir::checkMemrefAccessDependence (srcAccess=..., dstAccess=..., loopDepth=2, dependenceConstraints=0xffffeb6651e0, dependenceComponents=0x0, allowRAR=false) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:589
#11 0x0000fffff246a0c4 in mlir::isLoopMemoryParallel (forOp=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:147
#12 0x0000fffff2469ef0 in mlir::isLoopParallel (forOp=..., parallelReductions=0x0) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:115
#13 0x0000fffff5a8e734 in (anonymous namespace)::Vectorize::runOnOperation()::$_5::operator()(mlir::AffineForOp) const (this=0xffffeb665ed8, loop=...) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Transforms/SuperVectorize.cpp:1751
#14 0x0000fffff5a8e6f4 in _ZZN4mlir6detail4walkILNS_9WalkOrderE1EZN12_GLOBAL__N_19Vectorize14runOnOperationEvE3$_5NS_11AffineForOpEvEENSt9enable_ifIXaantsr4llvm9is_one_ofIT1_PNS_9OperationEPNS_6RegionEPNS_5BlockEEE5valuesr3std7is_sameIT2_vEE5valueESF_E4typeESA_OT0_ENKUlSA_E_clESA_ (this=0xffffeb665d58, op=0xffffe0006c10) at /home/culrho01/llvm-project/mlir/include/mlir/IR/Visitors.h:195
#15 0x0000fffff5a8e690 in _ZN4llvm12function_refIFvPN4mlir9OperationEEE11callback_fnIZNS1_6detail4walkILNS1_9WalkOrderE1EZN12_GLOBAL__N_19Vectorize14runOnOperationEvE3$_5NS1_11AffineForOpEvEENSt9enable_ifIXaantsr4llvm9is_one_ofIT1_S3_PNS1_6RegionEPNS1_5BlockEEE5valuesr3std7is_sameIT2_vEE5valueESK_E4typeES3_OT0_EUlS3_E_EEvlS3_ (callable=281474631097688, params=0xffffe0006c10) at /home/culrho01/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45
#16 0x0000ffffef8c8b30 in llvm::function_ref<void (mlir::Operation*)>::operator()(mlir::Operation*) const (this=0xffffeb665a40, params=0xffffe0006c10) at /home/culrho01/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68
#17 0x0000ffffef8c7ee8 in mlir::detail::walk(mlir::Operation*, llvm::function_ref<void (mlir::Operation*)>, mlir::WalkOrder) (op=0xffffe0006c10, callback=..., order=mlir::WalkOrder::PostOrder) at /home/culrho01/llvm-project/mlir/lib/IR/Visitors.cpp:70
#18 0x0000ffffef8c7ea8 in mlir::detail::walk(mlir::Operation*, llvm::function_ref<void (mlir::Operation*)>, mlir::WalkOrder) (op=0xffffe0004430, callback=..., order=mlir::WalkOrder::PostOrder) at /home/culrho01/llvm-project/mlir/lib/IR/Visitors.cpp:65
#19 0x0000ffffef8c7ea8 in mlir::detail::walk(mlir::Operation*, llvm::function_ref<void (mlir::Operation*)>, mlir::WalkOrder) (op=0x382450, callback=..., order=mlir::WalkOrder::PostOrder) at /home/culrho01/llvm-project/mlir/lib/IR/Visitors.cpp:65
#20 0x0000ffffef8c7ea8 in mlir::detail::walk(mlir::Operation*, llvm::function_ref<void (mlir::Operation*)>, mlir::WalkOrder) (op=0x37de90, callback=..., order=mlir::WalkOrder::PostOrder) at /home/culrho01/llvm-project/mlir/lib/IR/Visitors.cpp:65
#21 0x0000fffff5a8e61c in mlir::detail::walk<(mlir::WalkOrder)1, (anonymous namespace)::Vectorize::runOnOperation()::$_5, mlir::AffineForOp, void> (op=0x37de90, callback=...) at /home/culrho01/llvm-project/mlir/include/mlir/IR/Visitors.h:197
#22 0x0000fffff5a8e59c in mlir::Operation::walk<(mlir::WalkOrder)1, (anonymous namespace)::Vectorize::runOnOperation()::$_5, void> (this=0x37de90, callback=...) at /home/culrho01/llvm-project/mlir/include/mlir/IR/Operation.h:516
#23 0x0000fffff5a8e2f0 in mlir::OpState::walk<(mlir::WalkOrder)1, (anonymous namespace)::Vectorize::runOnOperation()::$_5, void> (this=0xffffeb666100, callback=...) at /home/culrho01/llvm-project/mlir/include/mlir/IR/OpDefinition.h:163
#24 0x0000fffff5a8e08c in (anonymous namespace)::Vectorize::runOnOperation (this=0x3c3ec0) at /home/culrho01/llvm-project/mlir/lib/Dialect/Affine/Transforms/SuperVectorize.cpp:1750
#25 0x0000ffffefbd8a70 in mlir::detail::OpToOpPassAdaptor::run (pass=0x3c3ec0, op=0x37de90, am=..., verifyPasses=true, parentInitGeneration=1) at /home/culrho01/llvm-project/mlir/lib/Pass/Pass.cpp:392
#26 0x0000ffffefbd906c in mlir::detail::OpToOpPassAdaptor::runPipeline (passes=..., op=0x37de90, am=..., verifyPasses=true, parentInitGeneration=1, instrumentor=0x0, parentInfo=0xffffffffc678) at /home/culrho01/llvm-project/mlir/lib/Pass/Pass.cpp:452
#27 0x0000ffffefbdcba4 in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_8::operator()<std::pair<mlir::Operation*, mlir::AnalysisManager> >(std::pair<mlir::Operation*, mlir::AnalysisManager>&) const (this=0xffffffffc608, opPMPair=...)
    at /home/culrho01/llvm-project/mlir/lib/Pass/Pass.cpp:614
#28 0x0000ffffefbdcd40 in mlir::failableParallelForEach<__gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_8&>(mlir::MLIRContext*, __gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, __gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_8&)::{lambda()#1}::operator()() const (this=0x3d5600) at /home/culrho01/llvm-project/mlir/include/mlir/IR/Threading.h:65
#29 0x0000ffffefbdd550 in std::_Function_handler<void (), mlir::failableParallelForEach<__gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_8&>(mlir::MLIRContext*, __gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, __gnu_cxx::__normal_iterator<std::pair<mlir::Operation*, mlir::AnalysisManager>*, std::vector<std::pair<mlir::Operation*, mlir::AnalysisManager>, std::allocator<std::pair<mlir::Operation*, mlir::AnalysisManager> > > >, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_8&)::{lambda()#1}>::_M_invoke(std::_Any_data const&) (__functor=...) at /usr/bin/../lib/gcc/aarch64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:300
#30 0x0000fffff037dee8 in std::function<void ()>::operator()() const (this=0x3d5650) at /usr/bin/../lib/gcc/aarch64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:688
#31 0x0000ffffefbf4e38 in llvm::ThreadPool::createTaskAndFuture(std::function<void ()>)::{lambda()#1}::operator()() const (this=0x3d5640) at /home/culrho01/llvm-project/llvm/include/llvm/Support/ThreadPool.h:95
#32 0x0000ffffefbf4ca4 in std::_Function_handler<void (), llvm::ThreadPool::createTaskAndFuture(std::function<void ()>)::{lambda()#1}>::_M_invoke(std::_Any_data const&) (__functor=...)
    at /usr/bin/../lib/gcc/aarch64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:300
#33 0x0000fffff037dee8 in std::function<void ()>::operator()() const (this=0xffffeb6666d8) at /usr/bin/../lib/gcc/aarch64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:688
#34 0x0000ffffef3804b0 in llvm::ThreadPool::grow(int)::$_0::operator()() const (this=0x3d56b0) at /home/culrho01/llvm-project/llvm/lib/Support/ThreadPool.cpp:59
#35 0x0000ffffef380374 in llvm::thread::Apply<llvm::ThreadPool::grow(int)::$_0>(std::tuple<llvm::ThreadPool::grow(int)::$_0>&, std::integer_sequence<unsigned long>) (Callee=...) at /home/culrho01/llvm-project/llvm/include/llvm/Support/thread.h:42
#36 0x0000ffffef38033c in llvm::thread::GenericThreadProxy<std::tuple<llvm::ThreadPool::grow(int)::$_0> >(void*) (Ptr=0x3d56b0) at /home/culrho01/llvm-project/llvm/include/llvm/Support/thread.h:50
#37 0x0000ffffef37ffec in llvm::thread::ThreadProxy<std::tuple<llvm::ThreadPool::grow(int)::$_0> >(void*) (Ptr=0x3d56b0) at /home/culrho01/llvm-project/llvm/include/llvm/Support/thread.h:60
#38 0x0000fffff7fa53d0 in start_thread (arg=0xffffffffbeaf) at pthread_create.c:477
#39 0x0000ffffeed754ec in thread_start () at ../sysdeps/unix/sysv/linux/aarch64/clone.S:78

I'm based on commit f72d8897.

[llvmbot]

@llvm/issue-subscribers-mlir-affine

[kaitingwang]

The crash happens when building dependence polyhedron and attempting to add the domain constraint. The code in AffineStructures.cpp:FlatAffineValueConstraints' assert statement checks that the loop bound (i.e. val) isTopLevelValue or isForInductionVar. In this case, %6 = memref.dim %arg0, %c0 : memref<?x?xf32> is neither. Thus, the assert is triggered.

However, %6 = memref.dim %arg0, %c0 : memref<?x?xf32> is loop invariant in the scope of the scf.for loop (i.e. dim of %arg0 is not changed anywhere in the scf.for loop) A invariant code motion could have hoisted it to be outside (above) the scf.for loop which would then satisfy the isTopLevelValue condition of the assert.

I propose to add an extra allowance in the assert checking. That is, isTopLevelValue(val) || isForInductionVar(val) || isLoopInvariant(val, loop). What do you think? (the isLoopInvariant API is currently made up to demonstrate the concept of the fix only)

[kaitingwang]

First, -convert-linalg-to-affine-loops should have created a affine.for loop instead of the scf.for loop. Agree?

Instead of : scf.for %arg2 = %c0 to %2 step %c1
Should generate: affine.for %arg2 = %c0 to %2 step 1

Then, running -affine-loop-invariant-code-motion will hoist the %6 = memref.dim %arg0, %c0 : memref<?x?xf32> stmt to be outside of the affine.for (which is currently an scf.for loop).

[jsetoain]

Indeed, that seems to solve the crash. It's still generating an error:

matmul-vs-matvec.mlir:33:5: error: NYI: non-trivial layoutMap linalg.matvec ins(%A, %b: memref<?x?xf32>, memref<?xf32, offset: ?, strides: [?]>) ^ matmul-vs-matvec.mlir:33:5: note: see current operation: %12 = "affine.load"(%9, %arg4) {map = affine_map<(d0) -> (d0)>} : (memref<?xf32, affine_map<(d0)[s0, s1] -> (d0 * s1 + s0)>>, index) -> f32

And fails to vectorize. Oddly enough, instead of bailing after the error, it just keeps going and generates scalar code for that loop. Not sure if that's the intended behavior, but looks like an entirely different problem.

Another question is whether those memref.dim shouldn't be hoisted out of the scf.for anyway, I don't really see the reason why that loop should be affine for the supervectorizer to do its job 🤔

[bondhugula]

This should be fixed by #129476 since the assertion is now removed with proper status check and failure return status.