StackColoring: better handling of statically unreachable code

[thanm]

Summary

Avoid assert/crash during liveness calculation in situations where the
incoming machine function has statically unreachable BBs.

Fixes PR37130.

[thanm]

I would welcome suggestions on how to write a regression test / lit test for this issue. The tricky part seems to be insuring that a statically unreachable BB survives all the way through the llc pipeline to make it to stack coloring.

[sdardis]

@thanm You can take the reproducer in the bug report, produce LLVM-IR from it (-S -emit-llvm), then run it through llc with "-stop-before stack-slot-coloring" to get MIR output. The test file would then be invoked with the same options as before except you'd add '-start-before stack-slot-coloring'.

test/CodeGen/X86/branch_instruction_and_target_split_perf_nops.mir is an example of such a test.

[thanm]

In D46265#1082768, @sdardis wrote:

@thanm You can take the reproducer in the bug report, produce LLVM-IR from it (-S -emit-llvm), then run it through llc with "-stop-before stack-slot-coloring" to get MIR output. The test file would then be invoked with the same options as before except you'd add '-start-before stack-slot-coloring'.

Thank you! I will look into doing that.

[thanm]

@thanm You can take the reproducer in the bug report, produce LLVM-IR from it (-S -emit-llvm), then run it through llc with "-stop-before stack-slot-coloring" to get MIR output. The test file would then be invoked with the same options as before except you'd add '-start-before stack-slot-coloring'.

Thank you! I will look into doing that.

Well, I am not having much luck creating a runnable MIR test case using this recipe. I tried:

clang -S -emit-llvm ...
llc llvm-pr-37130.opt.ll -stop-before stack-coloring -o abc.mir

then edited the resulting file to introduce the statically unreachable block. When I run it using

llc ../llvm/test/CodeGen/X86/stack-coloring-unreachable-bb.mir -no-stack-coloring=false -start-before stack-coloring

I get a fatal error in the pass manager: "Unable to schedule 'Slot index numbering' required by 'Merge disjoint stack slots'".

I am probably making some sort of rookie mistake here somewhere, but I am not sure what.

[thanm]

Add testcase.

[thanm]

Ready for review at this point.

[thanm]

Friendly ping... let me know if I need to recruit additional reviews.

[• dberlin]

This looks pretty obviously right, i'd commit it.

[sdardis]

Sorry for the delay, but this change looks ok, but the supplied test case is flaky and crashes sometimes on my machine:

Assertion failed: (!isa<Constant>(V) && "Can't get a constant or global slot with this!"), function getLocalSlot, file /Users/sdardis/dev/llvm/llvm/lib/IR/AsmWriter.cpp, line 1038.
Stack dump:
0. Program arguments: /Users/sdardis/dev/llvm/llvmbuild3/bin/llc -mcpu=corei7 -no-stack-coloring=false -stop-after stack-coloring -o /dev/null /Users/sdardis/dev/llvm/llvm/test/CodeGen/X86/stack-coloring-unreachable-bb.mir

1. Running pass 'Function Pass Manager' on module '/Users/sdardis/dev/llvm/llvm/test/CodeGen/X86/stack-coloring-unreachable-bb.mir'.
2. Running pass 'MIR Printing Pass' on function '@foo'

0 llc 0x0000000107cfdeff llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 63
1 llc 0x0000000107cfe3a9 PrintStackTraceSignalHandler(void*) + 25
2 llc 0x0000000107cfaf99 llvm::sys::RunSignalHandlers() + 425
3 llc 0x0000000107cfe629 SignalHandler(int) + 345
4 libsystem_platform.dylib 0x00007fff9ee7b52a _sigtramp + 26
5 libsystem_platform.dylib 0x00007fff63e0f5c8 _sigtramp + 3304669368
6 libsystem_c.dylib 0x00007fff9c3af6df abort + 129
7 libsystem_c.dylib 0x00007fff9c376dd8 basename + 0
8 llc 0x0000000106e07ff1 llvm::SlotTracker::getLocalSlot(llvm::Value const*) + 113
9 llc 0x0000000106e07f6e llvm::ModuleSlotTracker::getLocalSlot(llvm::Value const*) + 126
10 llc 0x0000000106b9bc2f llvm::MIPrinter::print(llvm::MachineBasicBlock const&) + 447
11 llc 0x0000000106b97d30 llvm::MIRPrinter::print(llvm::MachineFunction const&) + 944
12 llc 0x0000000106b9f12d llvm::printMIR(llvm::raw_ostream&, llvm::MachineFunction const&) + 45
13 llc 0x0000000106ba62fa (anonymous namespace)::MIRPrintingPass::runOnMachineFunction(llvm::MachineFunction&) + 298
14 llc 0x0000000106a1b2a6 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) + 454
15 llc 0x000000010708916d llvm::FPPassManager::runOnFunction(llvm::Function&) + 413
16 llc 0x00000001070894a5 llvm::FPPassManager::runOnModule(llvm::Module&) + 117
17 llc 0x000000010708a1fa (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) + 2010
18 llc 0x000000010708978b llvm::legacy::PassManagerImpl::run(llvm::Module&) + 347
19 llc 0x000000010708ae41 llvm::legacy::PassManager::run(llvm::Module&) + 33
20 llc 0x000000010474f991 compileModule(char**, llvm::LLVMContext&) + 19281
21 llc 0x000000010474ab3e main + 4062
22 libdyld.dylib 0x00007fff9b6d85ad start + 1
/Users/sdardis/dev/llvm/llvmbuild3/test/CodeGen/X86/Output/stack-coloring-unreachable-bb.mir.script: line 1: 84647 Abort trap: 6 /Users/sdardis/dev/llvm/llvmbuild3/bin/llc -mcpu=corei7 -no-stack-coloring=false -stop-after stack-coloring -o /dev/null /Users/sdardis/dev/llvm/llvm/test/CodeGen/X86/stack-coloring-unreachable-bb.mir

Digging in with valgrind shows several invalid reads and "Conditional jump or move depends on uninitialised value(s)".

Digging in with LLDB gives differing results (somewhat expected). Can you run valgrind on the run of llc for this test case and report your findings?

test/CodeGen/X86/stack-coloring-unreachable-bb.mir

1 ↗

(On Diff #145056)

Either rename this file to PR37310.mir or cite the PR number as a comment.

1 ↗

(On Diff #145056)

Add -mtriple=x86_64-unknown-linux-gnu to the command line here.

3 ↗

(On Diff #145056)

Explain that this is testing that the stack coloring pass handles statically unreachable blocks.

22–25 ↗

(On Diff #145056)

This can all be removed.

27 ↗

(On Diff #145056)

These "; Function Attrs.." lines can all be removed.

28 ↗

(On Diff #145056)

local_unnamed_addr can be removed.

69–72 ↗

(On Diff #145056)

As far as I can see, these can be removed as well, along with #<num>s in the function declarations.

73–78 ↗

(On Diff #145056)

This can be removed.

[thanm]

In D46265#1095398, @sdardis wrote:

Sorry for the delay, but this change looks ok, but the supplied test case is flaky and crashes sometimes on my machine:

Digging in with LLDB gives differing results (somewhat expected). Can you run valgrind on the run of llc for this test case and report your findings?

You are right, the testcase is indeed flaky. I left out the "-start-before stack-coloring" in the llc run rule -- as a result, what's happening is that the UnreachableBlockElimLegacyPass is running (prior to stack coloring), so it deletes the unreachable BB "unreachable:". The corresponding unreachable machine BB still exists, however, and it includes a reference to the BB, which becomes stale, leading to the crash.

If I add back in "-start-before stack-coloring" to the LLC command line (so as not preserve the BBs), I am back at my original problem of

Unable to schedule 'Slot index numbering' required by 'Merge disjoint stack slots'

for which I have no viable solution. I think what I will do is add a new knob to disable unreachable block elimination, then run llc as usual. Let me work on that.

test/CodeGen/X86/stack-coloring-unreachable-bb.mir

1 ↗

(On Diff #145056)

Will do.

3 ↗

(On Diff #145056)

Will do.

22–25 ↗

(On Diff #145056)

OK, will do. Regarding this and your other suggestions, is there a tool or programmatic way to do this? Or is this just an expected part of creating an MIR testcase? Please bear with me, I haven't written a lot of MIR tests.

28 ↗

(On Diff #145056)

Will do.

69–72 ↗

(On Diff #145056)

Will do.

73–78 ↗

(On Diff #145056)

Will do.

[thanm]

Revised test case. New hidden option to turn off statically
unreachable block elimination.

[sdardis]

I've tried the revised patch, but I am still seeing flakiness when running this on my darwin machine.

It appears CodeGenPrepare::eliminateMostlyEmptyBlock is leaving around stale information that is then read by the MIRPrintingPass.

I have a suggestion inline, and with that, the change to UnreachableBlockElim.cpp seems unnecessary. Can you also test on your side?

test/CodeGen/X86/PR37310.mir

2

Can you add '-start-before isel' here?

test/CodeGen/X86/stack-coloring-unreachable-bb.mir

22–25 ↗

(On Diff #145056)

It's typical to reduce both LLVM IR and MIR to the smallest form that reproduces / tests the bug that a patch fixes. Unfortunately I don't believe we have a clang/llvm output mode which reduces output for test cases.

[thanm]

In D46265#1097769, @sdardis wrote:

I've tried the revised patch, but I am still seeing flakiness when running this on my darwin machine.

OK, got it. Sounds like the test case still needs more work.

I am traveling this week and don't have access to a darwin machine, but I should be able to test that scenario when I get back.

It appears CodeGenPrepare::eliminateMostlyEmptyBlock is leaving around stale information that is then read by the MIRPrintingPass.

I have a suggestion inline, and with that, the change to UnreachableBlockElim.cpp seems unnecessary. Can you also test on your side?

Will do.

[thanm]

Incorporate changes suggested by Simon:

• remove option to disable statically unreachable block elim
• modify MIR test to include "-start-before isel"

[sdardis]

LGTM. Testing this with valgrind on linux and darwin shows no issues now.

[thanm]

Thanks! Review comments and suggestions much appreciated. I will try to submit this later in the week.

[thanm]

Hi Simon,

Your suggested revision to the MIR testcase ("-start-before isel") doesn't seem to agree with some of the buildbots. Do you have any insight into why this might be the case?

I will go ahead and revert the change now, will try to iron out the test case issues later on.

Thanks, Than

[sdardis]

Not immediately, can you forward me the links to some of the failed builds?

[thanm]

In D46265#1104934, @sdardis wrote:

Not immediately, can you forward me the links to some of the failed builds?

Here are a couple:

http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/30255
http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/4445
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/17217

Thanks-

[thakis]

Did you land the revert? I'm seeing the same failure running tests locally as on http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/4445/steps/ninja%20check%201/logs/FAIL%3A%20LLVM%3A%3APR37310.mir

If you haven't reverted yet, please do.

[thakis]

This was reverted by 332742. Sorry, I failed at syncing up my checkout.

[sdardis]

Hi Than,

Sorry I'm not sure what to do in that case. Locally it runs fine on my machine, and I've tested it on another system and it's ok there. You're probably safe enough to re-land the change without the test case.

Thanks,
Simon

[thanm]

Sorry I'm not sure what to do in that case. Locally it runs fine on my machine, and I've tested it on another system and it's ok there. You're probably safe enough to re-land the change without the test case.

I agree, given the nature of the change. I'll prepare another patch.

[thanm]

I agree, given the nature of the change. I'll prepare another patch.

OK, I finally figured out the problem. It turns out that "isel" is not (as I had naively assumed) the instruction selection pass, it's a separate pass specific to AMDGPU (confusing name, IMHO). I changed the test to use "-start-before dwarfehprepare" (a real pass that is not target-specific) and it seems to work now. I will send another patch.

lib/CodeGen/StackColoring.cpp

for (const MachineBasicBlock *BB : BasicBlockNumbering) {
       assert(BI != BlockLiveness.end() && "Block not found");
       BlockLifetimeInfo &BlockInfo = BI->second;
 
       // Compute LiveIn by unioning together the LiveOut sets of all preds.
       BitVector LocalLiveIn;
       for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(),
            PE = BB->pred_end(); PI != PE; ++PI) {
         LivenessMap::const_iterator I = BlockLiveness.find(*PI);
-        assert(I != BlockLiveness.end() && "Predecessor not found");
+        // PR37130: transformations prior to stack coloring can
+        // sometimes leave behind statically unreachable blocks; these
+        // can be safely skipped here.
+        if (I != BlockLiveness.end())
           LocalLiveIn |= I->second.LiveOut;
       }
 
       // Compute LiveOut by subtracting out lifetimes that end in this
       // block, then adding in lifetimes that begin in this block.  If
       // we have both BEGIN and END markers in the same basic block
       // then we know that the BEGIN marker comes after the END,
       // because we already handle the case where the BEGIN comes
       // before the END when collecting the markers (and building the

test/CodeGen/X86/PR37310.mir

+# RUN: llc -mtriple=x86_64-unknown-linux-gnu -mcpu=corei7 -start-before isel -no-stack-coloring=false -stop-after stack-coloring -o - %s
+
+# Test to insure that the liveness analysis in the StackColoring
+# pass gracefully handles statically unreachable blocks. See PR 37310.
+
+# This MIR testcase was created by compiling the following test, first
+# with "clang -emit-llvm -S" and then "llc -stop-before stack-coloring",
+# and finally editing the resulting MIR by hand to introduce a statically
+# unreachable BB (to wit: rename all bb.3 to bb.4, rename bb.2 to bb.3,
+# then add bb.2 with unconditional jump to bb.4).
+
+# Original C code:
+# extern int inita(int *);
+# void foo(int x) {
+#   if (x != 3) {
+#     int q[128];
+#     inita(&q[0]);
+#     return;
+#   }
+#   int r[128];
+#   inita(&r[x]);
+# }
+
+--- |
+  
+  define void @foo(i32 %x) {
+  entry:
+    %q = alloca [128 x i32], align 16
+    %r = alloca [128 x i32], align 16
+    %cmp = icmp eq i32 %x, 3
+    br i1 %cmp, label %if.end, label %if.then
+  
+  if.then:                                          ; preds = %entry
+    %0 = bitcast [128 x i32]* %q to i8*
+    call void @llvm.lifetime.start.p0i8(i64 512, i8* nonnull %0)
+    %arrayidx2 = bitcast [128 x i32]* %q to i32*
+    %call = call i32 @inita(i32* nonnull %arrayidx2)
+    call void @llvm.lifetime.end.p0i8(i64 512, i8* nonnull %0)
+    br label %return
+
+  unreachable:
+    br label %return
+  
+  if.end:                                           ; preds = %entry
+    %1 = bitcast [128 x i32]* %r to i8*
+    call void @llvm.lifetime.start.p0i8(i64 512, i8* nonnull %1)
+    %arrayidx1 = getelementptr inbounds [128 x i32], [128 x i32]* %r, i64 0, i64 3
+    %call2 = call i32 @inita(i32* nonnull %arrayidx1)
+    call void @llvm.lifetime.end.p0i8(i64 512, i8* nonnull %1)
+    br label %return
+  
+  return:                                           ; preds = %if.end, %if.then
+    ret void
+  }
+  
+  declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+  
+  declare i32 @inita(i32*)
+  
+  declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
+  
+  declare void @llvm.stackprotector(i8*, i8**)
+  
+  !llvm.module.flags = !{!0}
+  !llvm.ident = !{!1}
+  
+  !0 = !{i32 1, !"wchar_size", i32 4}
+  !1 = !{!"clang version 7.0.0 (trunk 331069) (llvm/trunk 331070)"}
+
+...
+---
+name:            foo
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: gr32, preferred-register: '' }
+  - { id: 1, class: gr32, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr32, preferred-register: '' }
+  - { id: 4, class: gr64, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+liveins:         
+  - { reg: '$edi', virtual-reg: '%0' }
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    16
+  adjustsStack:    false
+  hasCalls:        true
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      
+stack:           
+  - { id: 0, name: q, type: default, offset: 0, size: 512, alignment: 16, 
+      stack-id: 0, callee-saved-register: '', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: r, type: default, offset: 0, size: 512, alignment: 16, 
+      stack-id: 0, callee-saved-register: '', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+constants:       
+body:             |
+  bb.0.entry:
+    successors: %bb.3(0x40000000), %bb.1(0x40000000)
+    liveins: $edi
+  
+    %0:gr32 = COPY $edi
+    %1:gr32 = SUB32ri8 %0, 3, implicit-def $eflags
+    JE_1 %bb.3, implicit $eflags
+    JMP_1 %bb.1
+  
+  bb.1.if.then:
+    successors: %bb.4(0x80000000)
+  
+    LIFETIME_START %stack.0.q
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %2:gr64 = LEA64r %stack.0.q, 1, $noreg, 0, $noreg
+    $rdi = COPY %2
+    CALL64pcrel32 @inita, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %3:gr32 = COPY $eax
+    LIFETIME_END %stack.0.q
+    JMP_1 %bb.4
+
+  bb.2.unreachable:
+    successors: %bb.4(0x80000000)
+  
+    JMP_1 %bb.4
+  
+  bb.3.if.end:
+    successors: %bb.4(0x80000000)
+  
+    LIFETIME_START %stack.1.r
+    %4:gr64 = LEA64r %stack.1.r, 1, $noreg, 12, $noreg
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $rdi = COPY %4
+    CALL64pcrel32 @inita, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %5:gr32 = COPY $eax
+    LIFETIME_END %stack.1.r
+  
+  bb.4.return:
+    RET 0
+
+...