[WIP] Emit tail calls to __mspabi_func_epilog_X

[atrosinenko]

Here is a draft PR for internal discussion of a fix for #1. For now, it is expected to be squashed/rebased periodically, when appropriate for discussion.

To Do

• [x] create a stub patch that just compiles and tests itself somehow
• [ ] ensure the resulting code can be linked correctly (all symbols can be resolved, etc.)
• [x] find out why R4 seems to not being spilled just like R5 - R10 (or why this is correct). For now, this looks contradicting MSP EABI
• [x] get rid of the dangling ret at the very end of a function
• [x] rewrite string handling idiomatically (symbol names: use literal constant strings, dynamic formatting on stack / on heap, etc.; speed / allocation / maintainability trade-off)
• [ ] ultimately improve it to upstreamable quality

[atrosinenko]

On linkability, I expect no need to implement an automatic integration test, since any large enough code compiled as part of the nightly tests should catch this.

[cr1901]

ultimately improve it to upstreamable quality

I would like to test this against Rust ASAP. Do you suggest I wait until its upstreamable quality or start running smoke tests as soon as the feature seems to be working?

[atrosinenko]

@cr1901

I would like to test this against Rust ASAP. Do you suggest I wait until its upstreamable quality or start running smoke tests as soon as the feature seems to be working?

I expect this feature to be testable already. I'm not sure it would not have unresolved symbols during linking, but this depends on the sysroot being used for cross-compilation anyway. Current implementation is not expected to break something silently - just link-time errors :)

On the other hand, I'm not absolutely sure this patch will not be rewritten from scratch once again.

[atrosinenko]

• Squashed commits and updated for #12 (renaming FP -> R4).
• Made tests slightly stricter

[atrosinenko]

When compiling newlib with this patch applied, code generator crashes several times. The crash can be reproduced with

target datalayout = "e-m:e-p:16:16-i32:16-i64:16-f32:16-f64:16-a:8-n8:16-S16"
target triple = "msp430"

@x = external dso_local global i16

define dso_local void @_dtoa_r(i16*, i64) {
; First, make the function not fit into about 1024 bytes
  store volatile i16 1, i16* @x
  store volatile i16 1, i16* @x
; ... 200-300 lines here ...
  store volatile i16 1, i16* @x
  store volatile i16 1, i16* @x
; Then force emitting jump to LibCall
  call void asm sideeffect "", "~{r4},~{r5},~{r6},~{r7},~{r8},~{r9},~{r10}"()
  ret void
}

$ /path/to/bin/llc < test.ll 
        .text
        .file   "<stdin>"
llc: /old_ssd/ast/msp430-projects/llvm-project/llvm/include/llvm/CodeGen/MachineOperand.h:551: llvm::MachineBasicBlock* llvm::MachineOperand::getMBB() const: Assertion `isMBB() && "Wrong MachineOperand accessor"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /old_ssd/ast/msp430-projects/llvm-project/build-rel-assert/bin/llc 
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'MSP430 Branch Selector' on function '@_dtoa_r'
 #0 0x00005614194ca9ce llvm::sys::PrintStackTrace(llvm::raw_ostream&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Support/Unix/Signals.inc:568:3
 #1 0x00005614194c8744 llvm::sys::RunSignalHandlers() /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Support/Signals.cpp:68:20
 #2 0x00005614194c8e85 SignalHandler(int) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Support/Unix/Signals.inc:396:31
 #3 0x00007f1966743540 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x15540)
 #4 0x00007f19661d83eb raise /build/glibc-t7JzpG/glibc-2.30/signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #5 0x00007f19661b7899 abort /build/glibc-t7JzpG/glibc-2.30/stdlib/abort.c:81:7
 #6 0x00007f19661b7769 get_sysdep_segment_value /build/glibc-t7JzpG/glibc-2.30/intl/loadmsgcat.c:509:8
 #7 0x00007f19661b7769 _nl_load_domain /build/glibc-t7JzpG/glibc-2.30/intl/loadmsgcat.c:970:34
 #8 0x00007f19661c9006 (/lib/x86_64-linux-gnu/libc.so.6+0x37006)
 #9 0x000056141824981a llvm::MCInstrInfo::get(unsigned int) const /old_ssd/ast/msp430-projects/llvm-project/llvm/include/llvm/MC/MCInstrInfo.h:61:5
#10 0x000056141824981a llvm::MCInstrInfo::get(unsigned int) const /old_ssd/ast/msp430-projects/llvm-project/llvm/include/llvm/MC/MCInstrInfo.h:60:22
#11 0x000056141824981a expandBranches /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Target/MSP430/MSP430BranchSelector.cpp:196:57
#12 0x000056141824981a runOnMachineFunction /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Target/MSP430/MSP430BranchSelector.cpp:248:24
#13 0x000056141824981a (anonymous namespace)::MSP430BSel::runOnMachineFunction(llvm::MachineFunction&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/Target/MSP430/MSP430BranchSelector.cpp:224:6
#14 0x00005614189509f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:73:33
#15 0x00005614189509f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:38:6
#16 0x0000561418d63d43 llvm::FPPassManager::runOnFunction(llvm::Function&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1483:7
#17 0x0000561418d647b9 llvm::ilist_node_impl<llvm::ilist_detail::node_options<llvm::Function, true, false, void> >::getNext() /old_ssd/ast/msp430-projects/llvm-project/llvm/include/llvm/ADT/ilist_node.h:66:66
#18 0x0000561418d647b9 llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Function, true, false, void>, false, false>::operator++() /old_ssd/ast/msp430-projects/llvm-project/llvm/include/llvm/ADT/ilist_iterator.h:157:25
#19 0x0000561418d647b9 llvm::FPPassManager::runOnModule(llvm::Module&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:22
#20 0x0000561418d64b73 runOnModule /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1584:7
#21 0x0000561418d64b73 llvm::legacy::PassManagerImpl::run(llvm::Module&) /old_ssd/ast/msp430-projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1695:55
#22 0x00005614181cc50b compileModule /old_ssd/ast/msp430-projects/llvm-project/llvm/tools/llc/llc.cpp:627:66
#23 0x00005614181cc50b main /old_ssd/ast/msp430-projects/llvm-project/llvm/tools/llc/llc.cpp:360:35
#24 0x00007f19661b91e3 __libc_start_main /build/glibc-t7JzpG/glibc-2.30/csu/../csu/libc-start.c:342:3
#25 0x0000561418219e8e _start (/old_ssd/ast/msp430-projects/llvm-project/build-rel-assert/bin/llc+0x41be8e)
Aborted

MSP430BSel::expandBranches tries to extract JMP target as a MachineBasicBlock when it is LibCall:

  MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();

The issues itself seems not too hard to fix. But it would be useful to add a test on this. The problem is due to condition inside the MSP430BSel::runOnMachineFunction function:

  unsigned FunctionSize = measureFunction(BlockOffsets);
  // If the entire function is smaller than the displacement of a branch field,
  // we know we don't need to expand any branches in this
  // function. This is a common case.
  if (isInRage(FunctionSize)) {
    return false;
  }

My reproducer triggers this issue well now, but my general concern is "how to handle such simple and generally useful heuristics that can make some testcase no-op" (such as if the test would be implemented just as a couple of instructions before this optimization was added)?

[atrosinenko]

Hmm... Can we emit these epilogues via jmp external_symbol at all? Looks like we have no information on its displacement before actual linking.

[asl]

The issue here is that JMP instruction expects basic block. We just need another variant with different opcode that expects external symbol as an argument, so the code in branch expansion will not touch it.

[atrosinenko]

The issue here is that JMP instruction expects basic block.

Is it because its input list is described as (ins jmptarget:$dst) in .td?

If I get it right, MSP430::Bi does exactly what is required.

[asl]

Is it because its input list is described as (ins jmptarget:$dst) in .td?

Right

If I get it right, MSP430::Bi does exactly what is required.

I'm not 100% sure. We'd need long jump, not PC-relative branch, please double check.

[atrosinenko]

Replaced JMP with Bi. Now epilogues are generated like the following:

      76: 30 40 00 00                   br      #0
                        00000078:  R_MSP430_16_BYTE     __mspabi_func_epilog_7

The fact that epilogue is emitted via br #__mspabi_func_epilog_N is checked by regression tests. Hope this ensures jumps are always "long-enough". I'm not familiar with precise MSP430 assembler mnemonics, though.

On the other hand, now epilogues are always 4-byte long. Still, this never makes code larger - just not as small as it could be.

UPD: now newlib can be built with this patch successfully.

[atrosinenko]

Sent for public discussion: https://reviews.llvm.org/D84397