search

llvm / circt

Circuit IR Compilers and Tools
https://circt.org
Other
1.63k stars 283 forks source link

Memref access dependence fails on checkMemrefAccessDependence in --convert-affine-to-pipeline #4814

Open j2kun opened 1 year ago

j2kun commented 1 year ago

I'd like to convert some scf/affine MLIR to verilog, and while I am sure there are multiple problems with my input MLIR (I'm figuring out which additional passes I need to run to get it into a suitable form), I'm running into some mlir-opt crashes and thought it might be worthwhile to submit them as bug reports.

I'm struggling a bit to minimize the example to a small reproduction, in part because I don't understand what section of the input mlir-opt is unable to handle. I would appreciate some advice on what part to extract to make this bug simpler to triage.

repro.mlir.txt

Command (named txt so GitHub would let me attach it to this issue):

bin/circt-opt --convert-affine-to-pipeline /usr/home/jkun/repro.mlir.txt

Error logs:

circt-opt: /usr/home/jkun/circt/llvm/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp:643: mlir::DependenceResult mlir::checkMemrefAccessDependence(const mlir::MemRefAccess &, const mlir::MemRefAccess &, unsigned int, mlir::FlatAffineValueConstraints *, SmallVector<mlir::DependenceComponent, 2> *, bool): Assertion `loopDepth <= numCommonLoops + 1' failed.
PLEASE submit a bug report to https://github.com/llvm/circt and include the crash backtrace.
Stack dump:
0.  Program arguments: bin/circt-opt --convert-affine-to-pipeline /usr/home/jkun/repro.mlir
 #0 0x000055a086e1d467 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (bin/circt-opt+0x1305467)
 #1 0x000055a086e1b31e llvm::sys::RunSignalHandlers() (bin/circt-opt+0x130331e)
 #2 0x000055a086e1ddaa SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f27a8c3af90 (/lib/x86_64-linux-gnu/libc.so.6+0x3bf90)
 #4 0x00007f27a8c89ccc __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #5 0x00007f27a8c3aef2 raise ./signal/../sysdeps/posix/raise.c:27:6
 #6 0x00007f27a8c25472 abort ./stdlib/abort.c:81:7
 #7 0x00007f27a8c25395 _nl_load_domain ./intl/loadmsgcat.c:1177:9
 #8 0x00007f27a8c33df2 (/lib/x86_64-linux-gnu/libc.so.6+0x34df2)
 #9 0x000055a0887fbe8c mlir::checkMemrefAccessDependence(mlir::MemRefAccess const&, mlir::MemRefAccess const&, unsigned int, mlir::FlatAffineValueConstraints*, llvm::SmallVector<mlir::DependenceComponent, 2u>*, bool) (bin/circt-opt+0x2ce3e8c)
#10 0x000055a0886bb1be checkMemrefDependence(llvm::SmallVectorImpl<mlir::Operation*>&, unsigned int, llvm::DenseMap<mlir::Operation*, llvm::SmallVector<circt::analysis::MemoryDependence, 1u>, llvm::DenseMapInfo<mlir::Operation*, void>, llvm::detail::DenseMapPair<mlir::Operation*, llvm::SmallVector<circt::analysis::MemoryDependence, 1u>>>&) /usr/home/jkun/circt/lib/Analysis/DependenceAnalysis.cpp:46:33
#11 0x000055a0886bafcf circt::analysis::MemoryDependenceAnalysis::MemoryDependenceAnalysis(mlir::Operation*) /usr/home/jkun/circt/lib/Analysis/DependenceAnalysis.cpp:142:65
#12 0x000055a086e2a7a4 mlir::detail::AnalysisModel<circt::analysis::MemoryDependenceAnalysis>::AnalysisModel<mlir::func::FuncOp&>(mlir::func::FuncOp&) /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/AnalysisManager.h:120:48
#13 0x000055a086e2a71e std::__detail::_MakeUniq<mlir::detail::AnalysisModel<circt::analysis::MemoryDependenceAnalysis>>::__single_object std::make_unique<mlir::detail::AnalysisModel<circt::analysis::MemoryDependenceAnalysis>, mlir::func::FuncOp&>(mlir::func::FuncOp&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/unique_ptr.h:1065:34
#14 0x000055a086e272d7 auto mlir::detail::AnalysisMap::constructAnalysis<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp, (void*)0>(mlir::AnalysisManager&, mlir::func::FuncOp) /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/AnalysisManager.h:233:12
#15 0x000055a086e26dc6 circt::analysis::MemoryDependenceAnalysis& mlir::detail::AnalysisMap::getAnalysisImpl<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp>(mlir::PassInstrumentor*, mlir::func::FuncOp, mlir::AnalysisManager&) /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/AnalysisManager.h:211:27
#16 0x000055a086e26ca5 std::enable_if<std::is_constructible<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp>::value || std::is_constructible<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp, mlir::AnalysisManager&>::value, circt::analysis::MemoryDependenceAnalysis&>::type mlir::detail::AnalysisMap::getAnalysis<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp>(mlir::PassInstrumentor*, mlir::AnalysisManager&) /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/AnalysisManager.h:167:5
#17 0x000055a086e26af4 circt::analysis::MemoryDependenceAnalysis& mlir::AnalysisManager::getAnalysis<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp>() /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/AnalysisManager.h:326:5
#18 0x000055a086e26a82 circt::analysis::MemoryDependenceAnalysis& mlir::Pass::getAnalysis<circt::analysis::MemoryDependenceAnalysis, mlir::func::FuncOp>() /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/Pass.h:225:5
#19 0x000055a086e26535 circt::analysis::MemoryDependenceAnalysis& mlir::OperationPass<mlir::func::FuncOp>::getAnalysis<circt::analysis::MemoryDependenceAnalysis>() /usr/home/jkun/circt/llvm/mlir/include/mlir/Pass/Pass.h:373:5
#20 0x000055a086e1f5bf (anonymous namespace)::AffineToPipeline::runOnOperation() /usr/home/jkun/circt/lib/Conversion/AffineToPipeline/AffineToPipeline.cpp:103:29
#21 0x000055a088e2c764 mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) (bin/circt-opt+0x3314764)
#22 0x000055a088e2ce81 mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) (bin/circt-opt+0x3314e81)
#23 0x000055a088e2e708 mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool) (bin/circt-opt+0x3316708)
#24 0x000055a088e2c87e mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) (bin/circt-opt+0x331487e)
#25 0x000055a088e2ce81 mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) (bin/circt-opt+0x3314e81)
#26 0x000055a088e2f65c mlir::PassManager::run(mlir::Operation*) (bin/circt-opt+0x331765c)
#27 0x000055a08862a9a4 performActions(llvm::raw_ostream&, std::shared_ptr<llvm::SourceMgr> const&, mlir::MLIRContext*, mlir::MlirOptMainConfig const&) MlirOptMain.cpp:0:0
#28 0x000055a08862a6a6 mlir::LogicalResult llvm::function_ref<mlir::LogicalResult (std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&)>::callback_fn<mlir::MlirOptMain(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::DialectRegistry&, mlir::MlirOptMainConfig const&)::$_1>(long, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&) MlirOptMain.cpp:0:0
#29 0x000055a08864bae8 mlir::splitAndProcessBuffer(std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::function_ref<mlir::LogicalResult (std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&)>, llvm::raw_ostream&, bool, bool) (bin/circt-opt+0x2b33ae8)
#30 0x000055a0886287d3 mlir::MlirOptMain(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::DialectRegistry&, mlir::MlirOptMainConfig const&) (bin/circt-opt+0x2b107d3)
#31 0x000055a088628e70 mlir::MlirOptMain(int, char**, llvm::StringRef, mlir::DialectRegistry&, bool) (bin/circt-opt+0x2b10e70)
#32 0x000055a086d3bc5f main /usr/home/jkun/circt/tools/circt-opt/circt-opt.cpp:70:23
#33 0x00007f27a8c2618a __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:74:3
#34 0x00007f27a8c26245 call_init ./csu/../csu/libc-start.c:128:20
#35 0x00007f27a8c26245 __libc_start_main ./csu/../csu/libc-start.c:368:5
#36 0x000055a086d3ba81 _start (bin/circt-opt+0x1223a81)
mikeurbach commented 1 year ago

Thanks for opening this. After taking a quick look, I'm not sure exactly what part of the input MLIR causes this issue, but it seems we are trying to check a memory dependence between a pair of memory operations that the upstream MLIR memory dependence utility asserts we should not be checking. We can probably adjust which memory dependences we check to avoid this issue.

Another point to bring up: this example is hitting this issue because it contains nested Affine loops. While the memory dependence analysis should support nested loops (and we should do something like what I mentioned above), the -convert-affine-to-pipeline pass does not. We have open issues on this topic for some time, and there is some interest in figuring out a way to make it work. This may or may not be the point in the design space you are interested in, but if you want to get something to work today, you can unroll the inner loops in each nest until there is just one Affine loop for each original loop nest.