[SR-9291] SIGSEGV with large array in SILGen

[swift-ci]

Previous ID	SR-9291
Radar	rdar://problem/46279391
Original Reporter	andreasw (JIRA User)
Type	Bug

Attachment: Download

Environment

Linux with release no-assertions build of swift with the above mentioned patches applied.Makefile

Additional Detail from JIRA

Votes	1
Component/s	Compiler
Labels	Bug, CompilerCrash
Assignee	None
Priority	Medium

md5: f3b2ee52855e03d9f071a263a4b97f47

Issue Description:

I am trying to compile a large array (70.000 elements) with a release no-assertions build.

Swift stops with:

<unknown>:0: error: unable to execute command: Segmentation fault  
<unknown>:0: error: compile command failed due to signal 11 (use -v to see invocation)

The stack trace is:

-   thread #1, name = 'swift', stop reason = signal SIGSEGV: invalid address (fault address: 0xffffffffffffff22)

-   frame #0: 0x0000000000d0c321 swift`(anonymous namespace)::ArgEmitter::emit(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 2017
    frame #1: 0x0000000000d0d1b0 swift`(anonymous namespace)::ArgEmitter::emitExpanded(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 816
    frame #2: 0x0000000000d0bce0 swift`(anonymous namespace)::ArgEmitter::emit(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 416
    frame #3: 0x0000000000d075a0 swift`(anonymous namespace)::ArgEmitter::emitTopLevel(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 4656
    frame #4: 0x0000000000d156c6 swift`(anonymous namespace)::CallSite::emit(swift::Lowering::SILGenFunction&, swift::Lowering::AbstractionPattern, swift::CanTypeWrapper<swift::SILFunctionType>, (anonymous namespace)::ParamLowering&, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::SmallVectorImpl<(anonymous namespace)::DelayedArgument>&, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus) && + 710
    frame #5: 0x0000000000d15130 swift`(anonymous namespace)::CallEmission::emitArgumentsForNormalApply(swift::CanTypeWrapper<swift::FunctionType>&, swift::Lowering::AbstractionPattern&, swift::CanTypeWrapper<swift::SILFunctionType>, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::Optional<swift::SILLocation>&, swift::CanTypeWrapper<swift::FunctionType>&) + 1200
    frame #6: 0x0000000000d00a42 swift`(anonymous namespace)::CallEmission::apply(swift::Lowering::SGFContext) + 3202
    frame #7: 0x0000000000cffd1a swift`swift::Lowering::SILGenFunction::emitApplyExpr(swift::Expr*, swift::Lowering::SGFContext) + 2218
    frame #8: 0x0000000000ca8a83 swift`swift::ASTVisitor<(anonymous namespace)::RValueEmitter, swift::Lowering::RValue, void, void, void, void, void, swift::Lowering::SGFContext>::visit(swift::Expr*, swift::Lowering::SGFContext) + 83
    frame #9: 0x0000000000caae08 swift`swift::ASTVisitor<(anonymous namespace)::RValueEmitter, swift::Lowering::RValue, void, void, void, void, void, swift::Lowering::SGFContext>::visit(swift::Expr*, swift::Lowering::SGFContext) + 9176
    frame #10: 0x0000000000c9eba1 swift`swift::Lowering::SILGenFunction::emitExprInto(swift::Expr*, swift::Lowering::Initialization*, llvm::Optional<swift::SILLocation>) + 289
    frame #11: 0x0000000000c93288 swift`swift::Lowering::SILGenFunction::emitPatternBinding(swift::PatternBindingDecl*, unsigned int) + 280
    frame #12: 0x0000000000c9333d swift`swift::Lowering::SILGenFunction::visitPatternBindingDecl(swift::PatternBindingDecl*) + 45
    frame #13: 0x0000000000c724af swift`swift::Lowering::SILGenModule::visitTopLevelCodeDecl(swift::TopLevelCodeDecl*) + 255
    frame #14: 0x0000000000c72b3b swift`swift::Lowering::SILGenModule::emitSourceFile(swift::SourceFile*) + 811
    frame #15: 0x0000000000c736d1 swift`swift::SILModule::constructSIL(swift::ModuleDecl*, swift::SILOptions&, swift::FileUnit*) + 273
    frame #16: 0x0000000000c73b77 swift`swift::performSILGeneration(swift::FileUnit&, swift::SILOptions&) + 23
    frame #17: 0x00000000004ca182 swift`performCompile(swift::CompilerInstance&, swift::CompilerInvocation&, llvm::ArrayRef<char const*>, int&, swift::FrontendObserver*, swift::UnifiedStatsReporter*) + 7410
    frame #18: 0x00000000004c77be swift`swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 3454
    frame #19: 0x000000000047f01e swift`main + 670
    frame #20: 0x00007ffff73f009b libc.so.6`__libc_start_main(main=(swift`main), argc=13, argv=0x00007fffffffdd88, init=<unavailable>, fini=<unavailable>, rtld_fini=<unavailable>, stack_end=0x00007fffffffdd78) at libc-start.c:308:16
    frame #21: 0x000000000047d5aa swift`_start + 42

I applied the two patches from @atrick fixing quadratic behaviour in the inliner:

https://github.com/apple/swift/pull/20630/commits

His comment was:

This is the SILGen assert for the initialization of 70k array elements:
Assertion failed: (params.size() == labels.size()), function relabelParams, file /s/sown/swift/lib/AST/ASTContext.cpp, line 3784.
This should be filed as a separate bug against SILGen. Someone may have thought it was ok to use 16 bits for a param index.

@slavapestov might be interested since he added this assertion.

I used the attached Makefile to generate the source.

[atrick]

I don't know if it's reasonable to allow this use case yet. I'd have to dig in further. But even if we don't allow it, that should be diagnosed properly in release builds.

[atrick]

andreasw (JIRA User) it's great that you're filing these bugs, and we're fixing quadratic behavior in the compiler. But as an implementation technique, statically initializing a giant Swift array doesn't make much sense, since it's going to generate a giant sequence of instructions to initialize each element. Writing a loop that appends elements probably makes more sense. You could statically initialize a C array and import it into Swift as UnsafeBufferPointer<Int>. That can be used in as a collection of Int in generic Swift code or even copied into a Swift array much more efficiently than initializing a Swift array from scratch. If you ask on the dev forums you might get better suggestions.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

@atrick

> But as an implementation technique, statically initializing a giant Swift array doesn't make much sense, since it's going to generate a giant sequence of instructions to initialize each element.

In the graphics community (pbrt.org) for example static arrays with ~50.000 elements are used to generate Sobol sequences to distribute samples:

https://raw.githubusercontent.com/mmp/pbrt-v3/master/src/core/sobolmatrices.cpp

So I think it makes much sense. Do you have an alternative? I would be happy to consider it. I like the static approach because a) I don't have to ship an extra file because everything is in the binary and b) it has virtually zero startup cost and c) simple things should be simple.

> Writing a loop that appends elements probably makes more sense

See point b) above, that has to be done every time at startup right? Maybe it is possible with template metaprogramming but why make it unnecessarily complicated?

> You could statically initialize a C array and import it into Swift as `UnsafeBufferPointer<Int>`

When a compiler engineer tells me to use another language I have the feeling that something is wrong.

FWIW, I did a little survey on the most used languages according to the TIOBE index (excluding SQL). Here are my results with a 50.000 element array.

"No problem" means compilation time is less than a second and execution time for printing one random element is less than a second.

Java: Doesn't work: "code too large". With workaround*: No problem.
C: No problem
C++: No problem
Python: No problem
Visual Basic .NET: Compilation slow but works
C#: No problem
Javascript: No problem
PHP: No problem
Go: No problem
Objective-C: No problem

*The Java workaround is to split the array into smaller arrays of 8000 elements into different classes.

So Swift would be the only language that crashes/asserts/is very slow.

Finally, this one thing (large arrays) exposed quadratic complexity in the SILVerifier, found dead code in debug locations, still shows quadratic complexity in RedundantLoadElimination, fixed quadratic behaviour in the inliner and now crashes the compiler in non-assert builds (which I have to use because of the quadratic complexity in the SILVerifier). I think that alone makes it a valuable testcase. That and the fact, that it might trigger in the future each time quadratic or worse complexity is unintentionally added.

[atrick]

andreasw (JIRA User) I never questioned your use case. I'm explaining that Swift arrays aren't intrinsically a good fit for that use case and that there's an easy workaround when you run into compiler problems. I personally think these are extremely valuable bugs and want them all to be fixed.

Note that Swift does have an optimization specifically for static array intialization that eliminates initiailization at startup time. In that respect, Swift will be much better than other high level languages. You may want to look at your app's disassembly when compiling with -O to make sure that's actually happening.

Swift arrays are fundamentally different from the C-based languages that you listed. I think it would be nice if the language allowed us to explicitly declare an immutable fixed size array that is guaranteed to be initialized statically, even at -Onone. It's not a very high priority because Swift Arrays are optimized well enough for almost all use cases, and it's very easy to import a C array for any use cases that aren't handled perfectly yet.

My comment about using a loop vs. a literal expression really had more to do with code size. At -Onone, the compiler is going to generate roughly 10 bytes of code per array element. A loop obviously generates an insignificant amount of code and probably has faster startup time as the array size increases due to the cost of loading the code. Now, none of this probably matters to you as long as that initialization is all optimized away at -O.

If you want Swift language/compiler developers to be more aware of your use case, I would bring it up on the dev forum.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

@atrick Thanks for the insight. I will write something up on the dev forum.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

You can find my article here: https://forums.swift.org/t/compile-performance-with-large-constant-arrays/18143

[atrick]

@swift-ci create.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Nearly 300 views and no reply. It seems nobody is interested in fixing a crashing/slow compiler. 🙁

[atrick]

The right fix isn't obvious. The parameter limit is in place because the underlying design doesn't support 60k+ parameters in a reasonable way. Hopefully someone will have time to work on the underlying design. If you don't see any activity on the bug in the next month please comment again so it isn't forgotten.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

This still happens with Xcode 10.2 and Swift 5.0.

[atrick]

andreasw (JIRA User) thanks for keeping on top of this.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Xcode 10.2.1 still crashes (immediately), the latest snapshot (2019-04-16) doesn't crash anymore but takes 12 minutes to compile.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.0.1 on Linux crashes immediately:

swift: /home/buildnode/jenkins/workspace/oss-swift-5.0-package-linux-ubuntu-18_04/swift/lib/AST/ASTContext.cpp:3814: static void swift::AnyFunctionType::relabelParams(MutableArrayRef<swift::AnyFunctionType::Param>, ArrayRef<swift::Identifier>): Assertion `params.size() == labels.size()' failed.
Stack dump:
0. Program arguments: /home/xxxxxx/opt/swift-5.0.1-RELEASE-ubuntu18.04/usr/bin/swift -frontend -c -primary-file bug.swift -target x86_64-unknown-linux-gnu -disable-objc-interop -color-diagnostics -module-name bug -o /tmp/bug-c283e7.o
1. While type-checking statement at [bug.swift:1:1 - line:2:560101] RangeText="let x: [UInt] = [
0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, 0x24, [...]

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1 macOS still crashes.

Stack dump:

0. Program arguments: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swift -frontend -c -primary-file bug.swift -target x86_64-apple-darwin18.7.0 -enable-objc-interop -sdk /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.15.sdk -color-diagnostics -module-name bug -o /var/folders/sl/6p8kkn497tq_fq836sftp9000000gn/T/bug-d10bd5.o
0 swift 0x0000000106c42eb3 PrintStackTraceSignalHandler(void*) + 51
1 swift 0x0000000106c42686 SignalHandler(int) + 358
2 libsystem_platform.dylib 0x00007fff5c748b5d _sigtramp + 29
3 swift 0x00000001036c67eb swift::TupleType::Profile(llvm::FoldingSetNodeID&) + 331
4 swift 0x0000000102c98ff3 (anonymous namespace)::ArgEmitter::emit(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 2403
5 swift 0x0000000102c9d352 (anonymous namespace)::ArgEmitter::emitExpanded(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 306
6 swift 0x0000000102cabb0f (anonymous namespace)::ArgEmitter::emitTopLevel(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 5887
7 swift 0x0000000102caa1bd (anonymous namespace)::CallSite::emit(swift::Lowering::SILGenFunction&, swift::Lowering::AbstractionPattern, swift::CanTypeWrapper<swift::SILFunctionType>, (anonymous namespace)::ParamLowering&, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::SmallVectorImpl<(anonymous namespace)::DelayedArgument>&, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus) && + 701
8 swift 0x0000000102ca733b (anonymous namespace)::CallEmission::emitArgumentsForNormalApply(swift::CanTypeWrapper<swift::FunctionType>&, swift::Lowering::AbstractionPattern&, swift::CanTypeWrapper<swift::SILFunctionType>, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::Optional<swift::SILLocation>&, swift::CanTypeWrapper<swift::FunctionType>&) + 1451
9 swift 0x0000000102ca4df3 (anonymous namespace)::CallEmission::apply(swift::Lowering::SGFContext) + 3059
10 swift 0x0000000102ca10ab swift::Lowering::SILGenFunction::emitApplyExpr(swift::Expr*, swift::Lowering::SGFContext) + 2331
11 swift 0x0000000102cf75b3 swift::Lowering::SILGenFunction::emitExprInto(swift::Expr*, swift::Lowering::Initialization*, llvm::Optional<swift::SILLocation>) + 131
12 swift 0x0000000102cea9ac swift::Lowering::SILGenFunction::emitPatternBinding(swift::PatternBindingDecl*, unsigned int) + 268
13 swift 0x0000000102c918ad swift::ASTVisitor<swift::Lowering::SILGenFunction, void, void, void, void, void, void>::visit(swift::Decl*) + 93
14 swift 0x0000000102c9403f swift::ASTVisitor<swift::Lowering::SILGenModule, void, void, void, void, void, void>::visit(swift::Decl*) + 1087
15 swift 0x0000000102c92e96 swift::Lowering::SILGenModule::emitSourceFile(swift::SourceFile*) + 1238
16 swift 0x0000000102c948f6 swift::SILModule::constructSIL(swift::ModuleDecl*, swift::SILOptions&, swift::FileUnit*) + 1238
17 swift 0x00000001028986f9 performCompile(swift::CompilerInstance&, swift::CompilerInvocation&, llvm::ArrayRef<char const*>, int&, swift::FrontendObserver*, swift::UnifiedStatsReporter*) + 28345
18 swift 0x000000010288e034 swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 6820
19 swift 0x000000010281b5a3 main + 1219
20 libdyld.dylib 0x00007fff5c55d3d5 start + 1
<unknown>:0: error: unable to execute command: Segmentation fault: 11
<unknown>:0: error: compile command failed due to signal 11 (use -v to see invocation)

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1.1 on Linux crashes.

This bug crashes Swift for nearly one year now.