diff --git a/llvm/lib/Target/MSP430/CMakeLists.txt b/llvm/lib/Target/MSP430/CMakeLists.txt --- a/llvm/lib/Target/MSP430/CMakeLists.txt +++ b/llvm/lib/Target/MSP430/CMakeLists.txt @@ -24,6 +24,7 @@ MSP430TargetMachine.cpp MSP430AsmPrinter.cpp MSP430MCInstLower.cpp + MSP430CommonEpilogueOptimizer.cpp ) add_subdirectory(MCTargetDesc) diff --git a/llvm/lib/Target/MSP430/MSP430.h b/llvm/lib/Target/MSP430/MSP430.h --- a/llvm/lib/Target/MSP430/MSP430.h +++ b/llvm/lib/Target/MSP430/MSP430.h @@ -42,6 +42,10 @@ FunctionPass *createMSP430BranchSelectionPass(); + FunctionPass *createMSP430CommonEpilogueOptimizerPass(); + + void initializeMSP430CommonEpilogueOptimizerPass(PassRegistry &); + } // end namespace llvm; #endif diff --git a/llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp b/llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp @@ -0,0 +1,172 @@ +//===-- MSP430CommonEpilogueOptimizer.cpp - Rewrite standard epilogues ----===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This is a pass that replaces common epilogue sequences with a single +// 4-byte BR to __mspabi_func_epilog_ when appropriate. +// +// This pass is expected to be run after epilogue generation is done and +// is only applicable to MSP430 (not MSP430X). +// +// Technically, sometimes these branches can be emitted just as a 2-byte +// relative JMP instead of an absolute 4-byte BR. Current implementation always +// uses BRs. +// +// See MSP430 Embedded Application Binary Interface, Section 3.8 +// "__mspabi_func_epilog Helper Functions" for details. +// +//===----------------------------------------------------------------------===// + +#include "MSP430.h" +#include "MSP430TargetMachine.h" + +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" + +using namespace llvm; + +#define DEBUG_TYPE "msp430-epilogue-opt" + +namespace { + +class MSP430CommonEpilogueOptimizer : public MachineFunctionPass { +public: + static char ID; + + MSP430CommonEpilogueOptimizer() : MachineFunctionPass(ID) { + initializeMSP430CommonEpilogueOptimizerPass( + *PassRegistry::getPassRegistry()); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + +private: + const MSP430InstrInfo *TII; + + // Replace instructions in range [EpilogueBegin, EpilogueEnd) with + // a single branch to LibCallName. + void replaceKnownEpilogueSequence(MachineBasicBlock &MBB, + MachineBasicBlock::iterator EpilogueBegin, + MachineBasicBlock::iterator EpilogueEnd, + const char *LibCallName) const; + + // Detect a typical epilogue sequence that can be replaced by a single + // branch to one of __mspabi_func_epilog_. + // On success, returns the name of an appropriate function and sets + // EpilogueBegin to the first instruction of the detected epilogue sequence. + // Returns nullptr when no known epilogue was detected. + const char * + detectKnownEpilogueSequence(MachineBasicBlock &MBB, + MachineBasicBlock::iterator Terminator, + MachineBasicBlock::iterator &EpilogueBegin) const; +}; + +} // end anonymous namespace + +char MSP430CommonEpilogueOptimizer::ID = 0; + +INITIALIZE_PASS(MSP430CommonEpilogueOptimizer, DEBUG_TYPE, + "Optimize known epilogue sequences on MSP430", false, false); + +// LibCall names arranged so that `N`-th element restores N registers +// +// MSP430 EABI defines standard epilogue helper functions like these: +// +// __mspabi_func_epilog_7: POP R4 +// __mspabi_func_epilog_6: POP R5 +// __mspabi_func_epilog_5: POP R6 +// __mspabi_func_epilog_4: POP R7 +// __mspabi_func_epilog_3: POP R8 +// __mspabi_func_epilog_2: POP R9 +// __mspabi_func_epilog_1: POP R10 +// RET +// +// These helper functions do not exist on MSP430X +static const char *EpilogueLibCallNames[] = { + nullptr, + "__mspabi_func_epilog_1", + "__mspabi_func_epilog_2", + "__mspabi_func_epilog_3", + "__mspabi_func_epilog_4", + "__mspabi_func_epilog_5", + "__mspabi_func_epilog_6", + "__mspabi_func_epilog_7", +}; + +// Registers to be restored, from the last `POP` instruction to the first +static const unsigned RestoredRegisters[] = { + MSP430::R10, MSP430::R9, MSP430::R8, MSP430::R7, + MSP430::R6, MSP430::R5, MSP430::R4, +}; + +void MSP430CommonEpilogueOptimizer::replaceKnownEpilogueSequence( + MachineBasicBlock &MBB, MachineBasicBlock::iterator EpilogueBegin, + MachineBasicBlock::iterator EpilogueEnd, const char *LibCallName) const { + + const DebugLoc &DL = EpilogueBegin->getDebugLoc(); + BuildMI(MBB, EpilogueBegin, DL, TII->get(MSP430::Bi)) + .addExternalSymbol(LibCallName); + + MBB.erase(EpilogueBegin, EpilogueEnd); +} + +const char *MSP430CommonEpilogueOptimizer::detectKnownEpilogueSequence( + MachineBasicBlock &MBB, MachineBasicBlock::iterator Terminator, + MachineBasicBlock::iterator &EpilogueBegin) const { + + if (Terminator->getOpcode() != MSP430::RET) + return nullptr; + + const unsigned MaxMatchedRegisters = array_lengthof(RestoredRegisters); + unsigned MatchedRegisters = 0; + + for (auto I = std::next(Terminator.getReverse()), E = MBB.rend(); + I != E && MatchedRegisters < MaxMatchedRegisters; + ++I, ++MatchedRegisters) { + + if (I->isDebugInstr()) + continue; + + if (I->getOpcode() != MSP430::POP16r || + I->getOperand(0).getReg() != RestoredRegisters[MatchedRegisters]) + break; + + // Updated on every successful match + EpilogueBegin = I.getReverse(); + } + + return EpilogueLibCallNames[MatchedRegisters]; +} + +bool MSP430CommonEpilogueOptimizer::runOnMachineFunction(MachineFunction &MF) { + TII = static_cast(MF.getSubtarget().getInstrInfo()); + + bool Modified = false; + for (auto &MBB : MF) { + auto Terminator = MBB.getFirstTerminator(), End = MBB.end(); + while (Terminator != End) { + // Increment before changing the instruction list + auto CurrentTerminator = Terminator++; + + MachineBasicBlock::iterator KnownEpilogueBegin; + const char *LibCallName = detectKnownEpilogueSequence( + MBB, CurrentTerminator, KnownEpilogueBegin); + if (!LibCallName) + continue; + + replaceKnownEpilogueSequence(MBB, KnownEpilogueBegin, + Terminator /* incremented */, LibCallName); + Modified = true; + } + } + + return Modified; +} + +FunctionPass *llvm::createMSP430CommonEpilogueOptimizerPass() { + return new MSP430CommonEpilogueOptimizer(); +} diff --git a/llvm/lib/Target/MSP430/MSP430InstrInfo.cpp b/llvm/lib/Target/MSP430/MSP430InstrInfo.cpp --- a/llvm/lib/Target/MSP430/MSP430InstrInfo.cpp +++ b/llvm/lib/Target/MSP430/MSP430InstrInfo.cpp @@ -114,9 +114,8 @@ --I; if (I->isDebugInstr()) continue; - if (I->getOpcode() != MSP430::JMP && - I->getOpcode() != MSP430::JCC && - I->getOpcode() != MSP430::Br && + if (I->getOpcode() != MSP430::JMP && I->getOpcode() != MSP430::JCC && + I->getOpcode() != MSP430::Bi && I->getOpcode() != MSP430::Br && I->getOpcode() != MSP430::Bm) break; // Remove the branch. @@ -183,12 +182,17 @@ if (!I->isBranch()) return true; - // Cannot handle indirect branches. - if (I->getOpcode() == MSP430::Br || - I->getOpcode() == MSP430::Bm) + // Handle unconditional branches to non-MBBs by removing any instructions + // after the branch instruction and returning true ("cannot understand"). + if (I->getOpcode() == MSP430::Bi || I->getOpcode() == MSP430::Br || + I->getOpcode() == MSP430::Bm) { + if (AllowModify) { + MBB.erase(std::next(I), MBB.end()); + } return true; + } - // Handle unconditional branches. + // Handle unconditional branches to MBB if (I->getOpcode() == MSP430::JMP) { if (!AllowModify) { TBB = I->getOperand(0).getMBB(); @@ -196,8 +200,7 @@ } // If the block has any instructions after a JMP, delete them. - while (std::next(I) != MBB.end()) - std::next(I)->eraseFromParent(); + MBB.erase(std::next(I), MBB.end()); Cond.clear(); FBB = nullptr; diff --git a/llvm/lib/Target/MSP430/MSP430TargetMachine.cpp b/llvm/lib/Target/MSP430/MSP430TargetMachine.cpp --- a/llvm/lib/Target/MSP430/MSP430TargetMachine.cpp +++ b/llvm/lib/Target/MSP430/MSP430TargetMachine.cpp @@ -24,6 +24,9 @@ extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeMSP430Target() { // Register the target. RegisterTargetMachine X(getTheMSP430Target()); + + PassRegistry &PR = *PassRegistry::getPassRegistry(); + initializeMSP430CommonEpilogueOptimizerPass(PR); } static Reloc::Model getEffectiveRelocModel(Optional RM) { @@ -80,6 +83,7 @@ } void MSP430PassConfig::addPreEmitPass() { + addPass(createMSP430CommonEpilogueOptimizerPass()); // Must run branch selection immediately preceding the asm printer. addPass(createMSP430BranchSelectionPass(), false); } diff --git a/llvm/test/CodeGen/MSP430/asm-clobbers.ll b/llvm/test/CodeGen/MSP430/asm-clobbers.ll --- a/llvm/test/CodeGen/MSP430/asm-clobbers.ll +++ b/llvm/test/CodeGen/MSP430/asm-clobbers.ll @@ -13,6 +13,8 @@ ; CHECK: -- End function } +; Arbitrarily split r4, r5, ..., r9 into two disjoint sets + define void @test_1() { entry: ; CHECK-LABEL: test_1: @@ -42,15 +44,15 @@ ; The r10 register is special because the sequence ; pop r10 ; ret -; can be replaced with -; jmp __mspabi_func_epilog_1 -; or other such function (depending on previous instructions). -; Still, it is not replaced *yet*. +; can be replaced with something like +; br __mspabi_func_epilog_1 define void @test_r10() { entry: ; CHECK-LABEL: test_r10: ; CHECK: push r10 call void asm sideeffect "", "~{r10}"() -; CHECK: pop r10 +; CHECK-NEXT: ;APP +; CHECK-NEXT: ;NO_APP +; CHECK-NEXT: br #__mspabi_func_epilog_1 ret void } diff --git a/llvm/test/CodeGen/MSP430/mspabi-func-epilog-multi-terminators.mir b/llvm/test/CodeGen/MSP430/mspabi-func-epilog-multi-terminators.mir new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/MSP430/mspabi-func-epilog-multi-terminators.mir @@ -0,0 +1,46 @@ +# This file tests a (somewhat hypothetical for now) case of multiple terminators, +# one of them being a RET instruction of a known epilogue sequence. + +# RUN: llc --x=mir \ +# RUN: --start-before=msp430-epilogue-opt \ +# RUN: --verify-machineinstrs < %s | FileCheck %s + +--- | + target datalayout = "e-m:e-p:16:16-i32:16-i64:16-f32:16-f64:16-a:8-n8:16-S16" + target triple = "msp430" + + define i16 @pops_1_reg() { + call void asm sideeffect "", "~{r10}"() + ret i16 42 + } +... +--- +name: pops_1_reg +alignment: 2 +tracksRegLiveness: true +frameInfo: + stackSize: 2 + maxAlignment: 2 + maxCallFrameSize: 0 +stack: + - { id: 0, type: spill-slot, offset: -4, size: 2, alignment: 2, callee-saved-register: '$r10' } +machineFunctionInfo: {} +body: | + bb.0 (%ir-block.0): + liveins: $r10 + + PUSH16r killed $r10, implicit-def $sp, implicit $sp + INLINEASM &"", 1 /* sideeffect attdialect */, 12 /* clobber */, implicit-def dead early-clobber $r10 + $r12 = MOV16ri 42 + $r10 = POP16r implicit-def $sp, implicit $sp + RET implicit $r12 /* manually added terminator (to be the last insn of a known epilogue sequence) */ + RET implicit killed $r12 +... + +# CHECK-LABEL: @pops_1_reg +# CHECK-NOT: pop +# CHECK: br #__mspabi_func_epilog_1 +# CHECK-NOT: pop + +# Other terminator instruction remains untouched +# CHECK: ret diff --git a/llvm/test/CodeGen/MSP430/mspabi-func-epilog-special-cases.ll b/llvm/test/CodeGen/MSP430/mspabi-func-epilog-special-cases.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/MSP430/mspabi-func-epilog-special-cases.ll @@ -0,0 +1,26 @@ +; RUN: llc --verify-machineinstrs < %s | FileCheck %s + +target datalayout = "e-m:e-p:16:16-i32:16-i64:16-f32:16-f64:16-a:8-n8:16-S16" +target triple = "msp430" + +define i16 @no_replace() { +; CHECK-LABEL: no_replace + call void asm sideeffect "", "~{r5}"() + ret i16 42 +; CHECK: pop r5 +; CHECK: ret +; CHECK: -- End function +} + +; The fact that non-contiguous range of callee-saved registers is spilled +; should not prevent emitting BR for the last contiguous group + +define i16 @pops_3_last_regs_and_some_other() { +; CHECK-LABEL: pops_3_last_regs_and_some_other + call void asm sideeffect "", "~{r5},~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: pop r5 +; CHECK: br #__mspabi_func_epilog_3 +; CHECK: -- End function +} diff --git a/llvm/test/CodeGen/MSP430/mspabi-func-epilog.ll b/llvm/test/CodeGen/MSP430/mspabi-func-epilog.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/MSP430/mspabi-func-epilog.ll @@ -0,0 +1,77 @@ +; RUN: llc --verify-machineinstrs < %s | \ +; RUN: FileCheck --implicit-check-not "{{(pop|ret) }}" %s + +; Short epilogue should be emitted for both void and non-void functions. +; Emitting __mspabi_func_epilog_N for N=1..7 should be supported. +; BRs to LibCalls should *replace* POP + RET sequences + +target datalayout = "e-m:e-p:16:16-i32:16-i64:16-f32:16-f64:16-a:8-n8:16-S16" +target triple = "msp430" + +; None of the following functions uses any POP or RET instructions, +; so this fact can be tested with --implicit-check-not on the whole output. + +define i16 @pops_1_reg() { +; Replacing 4 bytes with 4 other bytes. Doesn't make code smaller, but doesn't +; make it larger as well... +; CHECK-LABEL: pops_1_reg + call void asm sideeffect "", "~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_1 +; CHECK: -- End function +} + +define i16 @pops_2_regs() { +; CHECK-LABEL: pops_2_regs + call void asm sideeffect "", "~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_2 +; CHECK: -- End function +} + +define i16 @pops_3_regs() { +; CHECK-LABEL: pops_3_regs + call void asm sideeffect "", "~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_3 +; CHECK: -- End function +} + +define i16 @pops_4_regs() { +; CHECK-LABEL: pops_4_regs + call void asm sideeffect "", "~{r7},~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_4 +; CHECK: -- End function +} + +define i16 @pops_5_regs() { +; CHECK-LABEL: pops_5_regs + call void asm sideeffect "", "~{r6},~{r7},~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_5 +; CHECK: -- End function +} + +define i16 @pops_6_regs() { +; CHECK-LABEL: pops_6_regs + call void asm sideeffect "", "~{r5},~{r6},~{r7},~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_6 +; CHECK: -- End function +} + +define i16 @pops_7_regs() { +; CHECK-LABEL: pops_7_regs + call void asm sideeffect "", "~{r4},~{r5},~{r6},~{r7},~{r8},~{r9},~{r10}"() + ret i16 42 +; CHECK: ;NO_APP +; CHECK: br #__mspabi_func_epilog_7 +; CHECK: -- End function +}