[MSP430] Replace known epilogues with branches to __mspabi_func_epilog_N

[atrosinenko]

Summary

Optimize the size of epilogue sequences by replacing common cases with a single branch to __mspabi_func_epilog_<N> function described in MSP430 EABI document, part 3.8.

As part of that, the patch adjust handling of MSP430::Bi instruction.

[asl]

Will you please switch to iterators here?

Thanks!

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

113

I would not use low-level list-manipulating stuff here. Can we just use iterators here?

So we would have iterator to Begin, to End. In the for loop do something like this:

while (EpilogueBegin != EpilogueEnd) {
      MachineInstr *InstrToRemove = EpilogueBegin;
      EpilogueBegin = std::next(EpilogueBegin);
      // Do crazy removal
}

127

See above. Please use iterators.

[atrosinenko]

Address the comment + misc fixes.

Thanks!

[atrosinenko]

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

156

Not sure this is not against the code style, still should work.

[asl]

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

152

You don't need this. Just do std::next / std::prev prior to changing the iterators.

[atrosinenko]

Address the review comment

[arsenm]

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

146

getSubtarget<MSP430Subtarget>().getInstrInfo(() should work and is cleaner

llvm/lib/Target/MSP430/MSP430InstrInfo.cpp

187–193

This seems like a different patch. Also does AllowModify actually happen?

[arsenm]

analyzeBranch should probably be a separate patch

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

151

can you use make_early_inc_range?

llvm/test/CodeGen/MSP430/mspabi-func-epilog-multi-terminators.mir

8–16

Can drop IR section

llvm/test/CodeGen/MSP430/mspabi-func-epilog-special-cases.ll

4

Move to -mtriple and drop datalayout

llvm/test/CodeGen/MSP430/mspabi-func-epilog.ll

8–9

Ditto

llvm/lib/Target/MSP430/CMakeLists.txt

add_llvm_target(MSP430CodeGen
   MSP430InstrInfo.cpp
   MSP430FrameLowering.cpp
   MSP430MachineFunctionInfo.cpp
   MSP430RegisterInfo.cpp
   MSP430Subtarget.cpp
   MSP430TargetMachine.cpp
   MSP430AsmPrinter.cpp
   MSP430MCInstLower.cpp
+  MSP430CommonEpilogueOptimizer.cpp
   )
 
 add_subdirectory(MCTargetDesc)
 add_subdirectory(TargetInfo)
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)

llvm/lib/Target/MSP430/MSP430.h

namespace llvm {
   class MSP430TargetMachine;
   class FunctionPass;
 
   FunctionPass *createMSP430ISelDag(MSP430TargetMachine &TM,
                                     CodeGenOpt::Level OptLevel);
 
   FunctionPass *createMSP430BranchSelectionPass();
 
+  FunctionPass *createMSP430CommonEpilogueOptimizerPass();
+
+  void initializeMSP430CommonEpilogueOptimizerPass(PassRegistry &);
+
 } // end namespace llvm;
 
 #endif

llvm/lib/Target/MSP430/MSP430CommonEpilogueOptimizer.cpp

+//===-- 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_<N> 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_<N>.
+  // 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<const MSP430InstrInfo *>(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();
+}

llvm/lib/Target/MSP430/MSP430InstrInfo.cpp

unsigned MSP430InstrInfo::removeBranch(MachineBasicBlock &MBB,
 
   MachineBasicBlock::iterator I = MBB.end();
   unsigned Count = 0;
 
   while (I != MBB.begin()) {
     --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.
     I->eraseFromParent();
     I = MBB.end();
     ++Count;
   }
 
while (I != MBB.begin()) {
     if (!isUnpredicatedTerminator(*I))
       break;
 
     // A terminator that isn't a branch can't easily be handled
     // by this analysis.
     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();
         continue;
       }
 
       // 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;
 
       // Delete the JMP if it's equivalent to a fall-through.
       if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) {
         TBB = nullptr;
         I->eraseFromParent();
         I = MBB.end();

llvm/lib/Target/MSP430/MSP430TargetMachine.cpp

 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Support/TargetRegistry.h"
 using namespace llvm;
 
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeMSP430Target() {
   // Register the target.
   RegisterTargetMachine<MSP430TargetMachine> X(getTheMSP430Target());
+
+  PassRegistry &PR = *PassRegistry::getPassRegistry();
+  initializeMSP430CommonEpilogueOptimizerPass(PR);
 }
 
 static Reloc::Model getEffectiveRelocModel(Optional<Reloc::Model> RM) {
   if (!RM.hasValue())
     return Reloc::Static;
   return *RM;
 }
 

 
 bool MSP430PassConfig::addInstSelector() {
   // Install an instruction selector.
   addPass(createMSP430ISelDag(getMSP430TargetMachine(), getOptLevel()));
   return false;
 }
 
 void MSP430PassConfig::addPreEmitPass() {
+  addPass(createMSP430CommonEpilogueOptimizerPass());
   // Must run branch selection immediately preceding the asm printer.
   addPass(createMSP430BranchSelectionPass(), false);
 }

llvm/test/CodeGen/MSP430/asm-clobbers.ll

 ; RUN: llc < %s | FileCheck %s
 
 target datalayout = "e-m:e-p:16:16-i32:16:32-a:16-n8:16"
 target triple = "msp430---elf"
 
 define void @test_no_clobber() {
 entry:
 ; CHECK-LABEL: test_no_clobber
 ; CHECK-NOT: push
   call void asm sideeffect "", ""()
 ; CHECK-NOT: pop
   ret void
 ; CHECK: -- End function
 }
 
+; Arbitrarily split r4, r5, ..., r9 into two disjoint sets
+
 define void @test_1() {
 entry:
 ; CHECK-LABEL: test_1:
 ; CHECK: push r8
 ; CHECK: push r6
 ; CHECK: push r4
   call void asm sideeffect "", "~{r4},~{r6},~{r8}"()
 ; CHECK: pop r4

 ; CHECK: pop r7
 ; CHECK: pop r9
   ret void
 }
 
 ; 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
 }

llvm/test/CodeGen/MSP430/mspabi-func-epilog-multi-terminators.mir

+# 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

llvm/test/CodeGen/MSP430/mspabi-func-epilog-special-cases.ll

+; 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
+}

llvm/test/CodeGen/MSP430/mspabi-func-epilog.ll

+; 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
+}