search

wsmoses / Tapir-LLVM

Tapir extension to LLVM for optimizing Parallel Programs
Other
132 stars 24 forks source link

Issues with break/return within cilk_for #95

Closed adrieng closed 5 years ago

adrieng commented 5 years ago

Hi! Is exiting a cilk_for via control-flow (break/return) supported? I've run into various issues trying to compile the following function. 

#include "cilk/cilk.h"

int is_sorted(int *tab, int n) {
  cilk_for (int i = 0; i < n - 1; i++) {
    if (tab[i] > tab[i+1]) {
      return i;
    }
  }
  return -1;
}

Trying to compile without optimizations, I get the following error:

$ ~/src/Tapir-Meta/tapir/build/bin/clang -fcilkplus -c test.c
Found return instr that returns non-void in Function of void return type!
  ret i32 %76
 void

The error gets uglier after enabling optimizations:

$ ~/src/Tapir-Meta/tapir/build/bin/clang -O1 -fcilkplus -c test.c
Found return instr that returns non-void in Function of void return type!
  ret i32 %37
 voidtest.c:3:5: warning: Tapir loop not transformed: failed to use divide-and-conquer loop spawning
      [-Wpass-failed=loop-spawning]
int is_sorted(int *tab, int n) {
    ^
#0 0x0000559e79e0301a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a301a)
#1 0x0000559e79e00dde llvm::sys::RunSignalHandlers() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a0dde)
#2 0x0000559e79e00f36 SignalHandler(int) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a0f36)
#3 0x00007f2bb2214d00 __restore_rt (/usr/lib/libpthread.so.0+0x13d00)
#4 0x0000559e79d6514c simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::AssumptionCache*, int, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x120514c)
#5 0x0000559e79965e50 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05e50)
#6 0x0000559e79965ea1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05ea1)
#7 0x0000559e79965576 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05576)
#8 0x0000559e79fe665d (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x148665d)
#9 0x0000559e79fe896b clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x148896b)
#10 0x0000559e7a8a4934 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x1d44934)
#11 0x0000559e7abc40a9 clang::ParseAST(clang::Sema&, bool, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x20640a9)
#12 0x0000559e7a8a37e7 clang::CodeGenAction::ExecuteAction() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x1d437e7)
#13 0x0000559e7a4292a6 clang::FrontendAction::Execute() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x18c92a6)
#14 0x0000559e7a3ef316 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x188f316)
#15 0x0000559e7a4db3c3 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x197b3c3)
#16 0x0000559e791dcaa8 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x67caa8)
#17 0x0000559e79187ded main (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x627ded)
#18 0x00007f2bb1a84ee3 __libc_start_main (/usr/lib/libc.so.6+0x26ee3)
#19 0x0000559e791dad1e _start (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x67ad1e)
Stack dump:
0.  Program arguments: /home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -disable-llvm-verifier -discard-value-names -main-file-name test.c -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -momit-leaf-frame-pointer -dwarf-column-info -debugger-tuning=gdb -coverage-notes-file /home/guatto/tmp/test.gcno -resource-dir /home/guatto/src/Tapir-Meta/tapir/build/lib/clang/5.0.0 -internal-isystem /usr/local/include -internal-isystem /home/guatto/src/Tapir-Meta/tapir/build/lib/clang/5.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O1 -fdebug-compilation-dir /home/guatto/tmp -ferror-limit 19 -fmessage-length 95 -fcilkplus -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -o test.o -x c test.c 
1.  <eof> parser at end of file
2.  Per-module optimization passes
3.  Running pass 'Function Pass Manager' on module 'test.c'.
4.  Running pass 'Simplify the CFG' on function '@is_sorted_.ls'
clang-5.0: error: unable to execute command: Segmentation fault (core dumped)
clang-5.0: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 5.0.0 (https://github.com/wsmoses/Tapir-Clang 94b8db88cc38969262505a8b2942fb69c8fbacde) (https://github.com/wsmoses/Tapir-LLVM ba2f0eda34108ab64e581f2740b4d06eecc50709)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/guatto/src/Tapir-Meta/tapir/build/bin
clang-5.0: note: diagnostic msg: PLEASE submit a bug report to https://github.com/wsmoses/Tapir-LLVM/issues and include the crash backtrace, preprocessed source, and associated run script.
clang-5.0: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-5.0: note: diagnostic msg: /tmp/test-940b5d.c
clang-5.0: note: diagnostic msg: /tmp/test-940b5d.sh
clang-5.0: note: diagnostic msg: 

********************

I've attached the files mentioned above in test-940b5d.zip.

As far as I see, the above crash is deterministic. Replacing return with break leads to non-deterministic, infrequent crashes.

int is_sorted(int *tab, int n) {
  int tmp = -1;
  cilk_for (int i = 0; i < n - 1; i++) {
    if (tab[i] > tab[i+1]) {
      tmp = i;
      break;
    }
  }
  return tmp;
}

The crash I sometimes get is:

$ clang -O1 -fcilkplus -c test.c
#0 0x00005580c3a5101a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a301a)
#1 0x00005580c3a4edde llvm::sys::RunSignalHandlers() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a0dde)
#2 0x00005580c3a4ef36 SignalHandler(int) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12a0f36)
#3 0x00007fd43603cd00 __restore_rt (/usr/lib/libpthread.so.0+0x13d00)
#4 0x00005580c35ed8e6 llvm::Use::getImpliedUser() const (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe3f8e6)
#5 0x00005580c35ed959 llvm::Use::getUser() const (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe3f959)
#6 0x00005580c3218239 llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::advancePastNonTerminators() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xa6a239)
#7 0x00005580c3b4e7e3 llvm::SimplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, unsigned int, llvm::AssumptionCache*, llvm::SmallPtrSetImpl<llvm::BasicBlock*>*, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x13a07e3)
#8 0x00005580c39b28c1 iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::AssumptionCache*, unsigned int, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x12048c1)
#9 0x00005580c39b2c71 simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::AssumptionCache*, int, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x1204c71)
#10 0x00005580c35b3e50 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05e50)
#11 0x00005580c35b3ea1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05ea1)
#12 0x00005580c35b3576 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0xe05576)
#13 0x00005580c3c3465d (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x148665d)
#14 0x00005580c3c3696b clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x148896b)
#15 0x00005580c44f2934 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x1d44934)
#16 0x00005580c48120a9 clang::ParseAST(clang::Sema&, bool, bool) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x20640a9)
#17 0x00005580c44f17e7 clang::CodeGenAction::ExecuteAction() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x1d437e7)
#18 0x00005580c40772a6 clang::FrontendAction::Execute() (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x18c92a6)
#19 0x00005580c403d316 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x188f316)
#20 0x00005580c41293c3 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x197b3c3)
#21 0x00005580c2e2aaa8 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x67caa8)
#22 0x00005580c2dd5ded main (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x627ded)
#23 0x00007fd4358acee3 __libc_start_main (/usr/lib/libc.so.6+0x26ee3)
#24 0x00005580c2e28d1e _start (/home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0+0x67ad1e)
Stack dump:
0.  Program arguments: /home/guatto/src/Tapir-Meta/tapir/build/bin/clang-5.0 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -disable-llvm-verifier -discard-value-names -main-file-name test.c -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -momit-leaf-frame-pointer -dwarf-column-info -debugger-tuning=gdb -coverage-notes-file /home/guatto/tmp/test.gcno -resource-dir /home/guatto/src/Tapir-Meta/tapir/build/lib/clang/5.0.0 -internal-isystem /usr/local/include -internal-isystem /home/guatto/src/Tapir-Meta/tapir/build/lib/clang/5.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O1 -fdebug-compilation-dir /home/guatto/tmp -ferror-limit 19 -fmessage-length 95 -fcilkplus -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -o test.o -x c test.c 
1.  <eof> parser at end of file
2.  Per-module optimization passes
3.  Running pass 'Function Pass Manager' on module 'test.c'.
4.  Running pass 'Simplify the CFG' on function '@is_sorted'
clang-5.0: error: unable to execute command: Segmentation fault (core dumped)
clang-5.0: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 5.0.0 (https://github.com/wsmoses/Tapir-Clang 94b8db88cc38969262505a8b2942fb69c8fbacde) (https://github.com/wsmoses/Tapir-LLVM ba2f0eda34108ab64e581f2740b4d06eecc50709)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/guatto/src/Tapir-Meta/tapir/build/bin
clang-5.0: note: diagnostic msg: PLEASE submit a bug report to https://github.com/wsmoses/Tapir-LLVM/issues and include the crash backtrace, preprocessed source, and associated run script.
clang-5.0: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-5.0: note: diagnostic msg: /tmp/test-f1c94e.c
clang-5.0: note: diagnostic msg: /tmp/test-f1c94e.sh
clang-5.0: note: diagnostic msg: 

********************

Here are the log files for this second crash.

neboat commented 5 years ago

Thanks for the question. Exiting a cilk_for via control flow, such as break or return, is not supported. There are newer versions of Tapir that will catch and report these cases as errors, but we haven't backported those changes to master. (And, unfortunately, we've been remiss in keeping Tapir-Meta up to date.)

adrieng commented 5 years ago

That makes sense. Thanks @neboat!