contrib/llvm/lib/Target/ARM/Thumb1FrameLowering.cpp

   1 //===-- Thumb1FrameLowering.cpp - Thumb1 Frame Information ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the Thumb1 implementation of TargetFrameLowering class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "ARMBaseInstrInfo.h"
  15 #include "ARMBaseRegisterInfo.h"
  16 #include "ARMMachineFunctionInfo.h"
  17 #include "ARMSubtarget.h"
  18 #include "MCTargetDesc/ARMBaseInfo.h"
  19 #include "Thumb1FrameLowering.h"
  20 #include "Thumb1InstrInfo.h"
  21 #include "ThumbRegisterInfo.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/SmallSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/CodeGen/LivePhysRegs.h"
  27 #include "llvm/CodeGen/MachineBasicBlock.h"
  28 #include "llvm/CodeGen/MachineFrameInfo.h"
  29 #include "llvm/CodeGen/MachineFunction.h"
  30 #include "llvm/CodeGen/MachineInstr.h"
  31 #include "llvm/CodeGen/MachineInstrBuilder.h"
  32 #include "llvm/CodeGen/MachineOperand.h"
  33 #include "llvm/CodeGen/MachineModuleInfo.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/IR/DebugLoc.h"
  36 #include "llvm/MC/MCDwarf.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include "llvm/Support/ErrorHandling.h"
  39 #include "llvm/Target/TargetInstrInfo.h"
  40 #include "llvm/Target/TargetSubtargetInfo.h"
  41 #include <cassert>
  42 #include <iterator>
  43 #include <vector>
  44
  45 using namespace llvm;
  46
  47 Thumb1FrameLowering::Thumb1FrameLowering(const ARMSubtarget &sti)
  48     : ARMFrameLowering(sti) {}
  49
  50 bool Thumb1FrameLowering::hasReservedCallFrame(const MachineFunction &MF) const{
  51   const MachineFrameInfo &MFI = MF.getFrameInfo();
  52   unsigned CFSize = MFI.getMaxCallFrameSize();
  53   // It's not always a good idea to include the call frame as part of the
  54   // stack frame. ARM (especially Thumb) has small immediate offset to
  55   // address the stack frame. So a large call frame can cause poor codegen
  56   // and may even makes it impossible to scavenge a register.
  57   if (CFSize >= ((1 << 8) - 1) * 4 / 2) // Half of imm8 * 4
  58     return false;
  59
  60   return !MFI.hasVarSizedObjects();
  61 }
  62
  63 static void emitSPUpdate(MachineBasicBlock &MBB,
  64                          MachineBasicBlock::iterator &MBBI,
  65                          const TargetInstrInfo &TII, const DebugLoc &dl,
  66                          const ThumbRegisterInfo &MRI, int NumBytes,
  67                          unsigned MIFlags = MachineInstr::NoFlags) {
  68   emitThumbRegPlusImmediate(MBB, MBBI, dl, ARM::SP, ARM::SP, NumBytes, TII,
  69                             MRI, MIFlags);
  70 }
  71
  72
  73 MachineBasicBlock::iterator Thumb1FrameLowering::
  74 eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB,
  75                               MachineBasicBlock::iterator I) const {
  76   const Thumb1InstrInfo &TII =
  77       *static_cast<const Thumb1InstrInfo *>(STI.getInstrInfo());
  78   const ThumbRegisterInfo *RegInfo =
  79       static_cast<const ThumbRegisterInfo *>(STI.getRegisterInfo());
  80   if (!hasReservedCallFrame(MF)) {
  81     // If we have alloca, convert as follows:
  82     // ADJCALLSTACKDOWN -> sub, sp, sp, amount
  83     // ADJCALLSTACKUP   -> add, sp, sp, amount
  84     MachineInstr &Old = *I;
  85     DebugLoc dl = Old.getDebugLoc();
  86     unsigned Amount = TII.getFrameSize(Old);
  87     if (Amount != 0) {
  88       // We need to keep the stack aligned properly.  To do this, we round the
  89       // amount of space needed for the outgoing arguments up to the next
  90       // alignment boundary.
  91       Amount = alignTo(Amount, getStackAlignment());
  92
  93       // Replace the pseudo instruction with a new instruction...
  94       unsigned Opc = Old.getOpcode();
  95       if (Opc == ARM::ADJCALLSTACKDOWN || Opc == ARM::tADJCALLSTACKDOWN) {
  96         emitSPUpdate(MBB, I, TII, dl, *RegInfo, -Amount);
  97       } else {
  98         assert(Opc == ARM::ADJCALLSTACKUP || Opc == ARM::tADJCALLSTACKUP);
  99         emitSPUpdate(MBB, I, TII, dl, *RegInfo, Amount);
 100       }
 101     }
 102   }
 103   return MBB.erase(I);
 104 }
 105
 106 void Thumb1FrameLowering::emitPrologue(MachineFunction &MF,
 107                                        MachineBasicBlock &MBB) const {
 108   MachineBasicBlock::iterator MBBI = MBB.begin();
 109   MachineFrameInfo &MFI = MF.getFrameInfo();
 110   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 111   MachineModuleInfo &MMI = MF.getMMI();
 112   const MCRegisterInfo *MRI = MMI.getContext().getRegisterInfo();
 113   const ThumbRegisterInfo *RegInfo =
 114       static_cast<const ThumbRegisterInfo *>(STI.getRegisterInfo());
 115   const Thumb1InstrInfo &TII =
 116       *static_cast<const Thumb1InstrInfo *>(STI.getInstrInfo());
 117
 118   unsigned ArgRegsSaveSize = AFI->getArgRegsSaveSize();
 119   unsigned NumBytes = MFI.getStackSize();
 120   assert(NumBytes >= ArgRegsSaveSize &&
 121          "ArgRegsSaveSize is included in NumBytes");
 122   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
 123
 124   // Debug location must be unknown since the first debug location is used
 125   // to determine the end of the prologue.
 126   DebugLoc dl;
 127
 128   unsigned FramePtr = RegInfo->getFrameRegister(MF);
 129   unsigned BasePtr = RegInfo->getBaseRegister();
 130   int CFAOffset = 0;
 131
 132   // Thumb add/sub sp, imm8 instructions implicitly multiply the offset by 4.
 133   NumBytes = (NumBytes + 3) & ~3;
 134   MFI.setStackSize(NumBytes);
 135
 136   // Determine the sizes of each callee-save spill areas and record which frame
 137   // belongs to which callee-save spill areas.
 138   unsigned GPRCS1Size = 0, GPRCS2Size = 0, DPRCSSize = 0;
 139   int FramePtrSpillFI = 0;
 140
 141   if (ArgRegsSaveSize) {
 142     emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, -ArgRegsSaveSize,
 143                  MachineInstr::FrameSetup);
 144     CFAOffset -= ArgRegsSaveSize;
 145     unsigned CFIIndex = MF.addFrameInst(
 146         MCCFIInstruction::createDefCfaOffset(nullptr, CFAOffset));
 147     BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 148         .addCFIIndex(CFIIndex)
 149         .setMIFlags(MachineInstr::FrameSetup);
 150   }
 151
 152   if (!AFI->hasStackFrame()) {
 153     if (NumBytes - ArgRegsSaveSize != 0) {
 154       emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, -(NumBytes - ArgRegsSaveSize),
 155                    MachineInstr::FrameSetup);
 156       CFAOffset -= NumBytes - ArgRegsSaveSize;
 157       unsigned CFIIndex = MF.addFrameInst(
 158           MCCFIInstruction::createDefCfaOffset(nullptr, CFAOffset));
 159       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 160           .addCFIIndex(CFIIndex)
 161           .setMIFlags(MachineInstr::FrameSetup);
 162     }
 163     return;
 164   }
 165
 166   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 167     unsigned Reg = CSI[i].getReg();
 168     int FI = CSI[i].getFrameIdx();
 169     switch (Reg) {
 170     case ARM::R8:
 171     case ARM::R9:
 172     case ARM::R10:
 173     case ARM::R11:
 174       if (STI.splitFramePushPop(MF)) {
 175         GPRCS2Size += 4;
 176         break;
 177       }
 178       LLVM_FALLTHROUGH;
 179     case ARM::R4:
 180     case ARM::R5:
 181     case ARM::R6:
 182     case ARM::R7:
 183     case ARM::LR:
 184       if (Reg == FramePtr)
 185         FramePtrSpillFI = FI;
 186       GPRCS1Size += 4;
 187       break;
 188     default:
 189       DPRCSSize += 8;
 190     }
 191   }
 192
 193   if (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tPUSH) {
 194     ++MBBI;
 195   }
 196
 197   // Determine starting offsets of spill areas.
 198   unsigned DPRCSOffset  = NumBytes - ArgRegsSaveSize - (GPRCS1Size + GPRCS2Size + DPRCSSize);
 199   unsigned GPRCS2Offset = DPRCSOffset + DPRCSSize;
 200   unsigned GPRCS1Offset = GPRCS2Offset + GPRCS2Size;
 201   bool HasFP = hasFP(MF);
 202   if (HasFP)
 203     AFI->setFramePtrSpillOffset(MFI.getObjectOffset(FramePtrSpillFI) +
 204                                 NumBytes);
 205   AFI->setGPRCalleeSavedArea1Offset(GPRCS1Offset);
 206   AFI->setGPRCalleeSavedArea2Offset(GPRCS2Offset);
 207   AFI->setDPRCalleeSavedAreaOffset(DPRCSOffset);
 208   NumBytes = DPRCSOffset;
 209
 210   int FramePtrOffsetInBlock = 0;
 211   unsigned adjustedGPRCS1Size = GPRCS1Size;
 212   if (GPRCS1Size > 0 && GPRCS2Size == 0 &&
 213       tryFoldSPUpdateIntoPushPop(STI, MF, &*std::prev(MBBI), NumBytes)) {
 214     FramePtrOffsetInBlock = NumBytes;
 215     adjustedGPRCS1Size += NumBytes;
 216     NumBytes = 0;
 217   }
 218
 219   if (adjustedGPRCS1Size) {
 220     CFAOffset -= adjustedGPRCS1Size;
 221     unsigned CFIIndex = MF.addFrameInst(
 222         MCCFIInstruction::createDefCfaOffset(nullptr, CFAOffset));
 223     BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 224         .addCFIIndex(CFIIndex)
 225         .setMIFlags(MachineInstr::FrameSetup);
 226   }
 227   for (std::vector<CalleeSavedInfo>::const_iterator I = CSI.begin(),
 228          E = CSI.end(); I != E; ++I) {
 229     unsigned Reg = I->getReg();
 230     int FI = I->getFrameIdx();
 231     switch (Reg) {
 232     case ARM::R8:
 233     case ARM::R9:
 234     case ARM::R10:
 235     case ARM::R11:
 236     case ARM::R12:
 237       if (STI.splitFramePushPop(MF))
 238         break;
 239       // fallthough
 240     case ARM::R0:
 241     case ARM::R1:
 242     case ARM::R2:
 243     case ARM::R3:
 244     case ARM::R4:
 245     case ARM::R5:
 246     case ARM::R6:
 247     case ARM::R7:
 248     case ARM::LR:
 249       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createOffset(
 250           nullptr, MRI->getDwarfRegNum(Reg, true), MFI.getObjectOffset(FI)));
 251       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 252           .addCFIIndex(CFIIndex)
 253           .setMIFlags(MachineInstr::FrameSetup);
 254       break;
 255     }
 256   }
 257
 258   // Adjust FP so it point to the stack slot that contains the previous FP.
 259   if (HasFP) {
 260     FramePtrOffsetInBlock +=
 261         MFI.getObjectOffset(FramePtrSpillFI) + GPRCS1Size + ArgRegsSaveSize;
 262     BuildMI(MBB, MBBI, dl, TII.get(ARM::tADDrSPi), FramePtr)
 263         .addReg(ARM::SP)
 264         .addImm(FramePtrOffsetInBlock / 4)
 265         .setMIFlags(MachineInstr::FrameSetup)
 266         .add(predOps(ARMCC::AL));
 267     if(FramePtrOffsetInBlock) {
 268       CFAOffset += FramePtrOffsetInBlock;
 269       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createDefCfa(
 270           nullptr, MRI->getDwarfRegNum(FramePtr, true), CFAOffset));
 271       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 272           .addCFIIndex(CFIIndex)
 273           .setMIFlags(MachineInstr::FrameSetup);
 274     } else {
 275       unsigned CFIIndex =
 276           MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
 277               nullptr, MRI->getDwarfRegNum(FramePtr, true)));
 278       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 279           .addCFIIndex(CFIIndex)
 280           .setMIFlags(MachineInstr::FrameSetup);
 281     }
 282     if (NumBytes > 508)
 283       // If offset is > 508 then sp cannot be adjusted in a single instruction,
 284       // try restoring from fp instead.
 285       AFI->setShouldRestoreSPFromFP(true);
 286   }
 287
 288   // Skip past the spilling of r8-r11, which could consist of multiple tPUSH
 289   // and tMOVr instructions. We don't need to add any call frame information
 290   // in-between these instructions, because they do not modify the high
 291   // registers.
 292   while (true) {
 293     MachineBasicBlock::iterator OldMBBI = MBBI;
 294     // Skip a run of tMOVr instructions
 295     while (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tMOVr)
 296       MBBI++;
 297     if (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tPUSH) {
 298       MBBI++;
 299     } else {
 300       // We have reached an instruction which is not a push, so the previous
 301       // run of tMOVr instructions (which may have been empty) was not part of
 302       // the prologue. Reset MBBI back to the last PUSH of the prologue.
 303       MBBI = OldMBBI;
 304       break;
 305     }
 306   }
 307
 308   // Emit call frame information for the callee-saved high registers.
 309   for (auto &I : CSI) {
 310     unsigned Reg = I.getReg();
 311     int FI = I.getFrameIdx();
 312     switch (Reg) {
 313     case ARM::R8:
 314     case ARM::R9:
 315     case ARM::R10:
 316     case ARM::R11:
 317     case ARM::R12: {
 318       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createOffset(
 319           nullptr, MRI->getDwarfRegNum(Reg, true), MFI.getObjectOffset(FI)));
 320       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 321           .addCFIIndex(CFIIndex)
 322           .setMIFlags(MachineInstr::FrameSetup);
 323       break;
 324     }
 325     default:
 326       break;
 327     }
 328   }
 329
 330   if (NumBytes) {
 331     // Insert it after all the callee-save spills.
 332     emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, -NumBytes,
 333                  MachineInstr::FrameSetup);
 334     if (!HasFP) {
 335       CFAOffset -= NumBytes;
 336       unsigned CFIIndex = MF.addFrameInst(
 337           MCCFIInstruction::createDefCfaOffset(nullptr, CFAOffset));
 338       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
 339           .addCFIIndex(CFIIndex)
 340           .setMIFlags(MachineInstr::FrameSetup);
 341     }
 342   }
 343
 344   if (STI.isTargetELF() && HasFP)
 345     MFI.setOffsetAdjustment(MFI.getOffsetAdjustment() -
 346                             AFI->getFramePtrSpillOffset());
 347
 348   AFI->setGPRCalleeSavedArea1Size(GPRCS1Size);
 349   AFI->setGPRCalleeSavedArea2Size(GPRCS2Size);
 350   AFI->setDPRCalleeSavedAreaSize(DPRCSSize);
 351
 352   // Thumb1 does not currently support dynamic stack realignment.  Report a
 353   // fatal error rather then silently generate bad code.
 354   if (RegInfo->needsStackRealignment(MF))
 355       report_fatal_error("Dynamic stack realignment not supported for thumb1.");
 356
 357   // If we need a base pointer, set it up here. It's whatever the value
 358   // of the stack pointer is at this point. Any variable size objects
 359   // will be allocated after this, so we can still use the base pointer
 360   // to reference locals.
 361   if (RegInfo->hasBasePointer(MF))
 362     BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr), BasePtr)
 363         .addReg(ARM::SP)
 364         .add(predOps(ARMCC::AL));
 365
 366   // If the frame has variable sized objects then the epilogue must restore
 367   // the sp from fp. We can assume there's an FP here since hasFP already
 368   // checks for hasVarSizedObjects.
 369   if (MFI.hasVarSizedObjects())
 370     AFI->setShouldRestoreSPFromFP(true);
 371
 372   // In some cases, virtual registers have been introduced, e.g. by uses of
 373   // emitThumbRegPlusImmInReg.
 374   MF.getProperties().reset(MachineFunctionProperties::Property::NoVRegs);
 375 }
 376
 377 static bool isCSRestore(MachineInstr &MI, const MCPhysReg *CSRegs) {
 378   if (MI.getOpcode() == ARM::tLDRspi && MI.getOperand(1).isFI() &&
 379       isCalleeSavedRegister(MI.getOperand(0).getReg(), CSRegs))
 380     return true;
 381   else if (MI.getOpcode() == ARM::tPOP) {
 382     return true;
 383   } else if (MI.getOpcode() == ARM::tMOVr) {
 384     unsigned Dst = MI.getOperand(0).getReg();
 385     unsigned Src = MI.getOperand(1).getReg();
 386     return ((ARM::tGPRRegClass.contains(Src) || Src == ARM::LR) &&
 387             ARM::hGPRRegClass.contains(Dst));
 388   }
 389   return false;
 390 }
 391
 392 void Thumb1FrameLowering::emitEpilogue(MachineFunction &MF,
 393                                    MachineBasicBlock &MBB) const {
 394   MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
 395   DebugLoc dl = MBBI != MBB.end() ? MBBI->getDebugLoc() : DebugLoc();
 396   MachineFrameInfo &MFI = MF.getFrameInfo();
 397   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 398   const ThumbRegisterInfo *RegInfo =
 399       static_cast<const ThumbRegisterInfo *>(STI.getRegisterInfo());
 400   const Thumb1InstrInfo &TII =
 401       *static_cast<const Thumb1InstrInfo *>(STI.getInstrInfo());
 402
 403   unsigned ArgRegsSaveSize = AFI->getArgRegsSaveSize();
 404   int NumBytes = (int)MFI.getStackSize();
 405   assert((unsigned)NumBytes >= ArgRegsSaveSize &&
 406          "ArgRegsSaveSize is included in NumBytes");
 407   const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(&MF);
 408   unsigned FramePtr = RegInfo->getFrameRegister(MF);
 409
 410   if (!AFI->hasStackFrame()) {
 411     if (NumBytes - ArgRegsSaveSize != 0)
 412       emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, NumBytes - ArgRegsSaveSize);
 413   } else {
 414     // Unwind MBBI to point to first LDR / VLDRD.
 415     if (MBBI != MBB.begin()) {
 416       do
 417         --MBBI;
 418       while (MBBI != MBB.begin() && isCSRestore(*MBBI, CSRegs));
 419       if (!isCSRestore(*MBBI, CSRegs))
 420         ++MBBI;
 421     }
 422
 423     // Move SP to start of FP callee save spill area.
 424     NumBytes -= (AFI->getGPRCalleeSavedArea1Size() +
 425                  AFI->getGPRCalleeSavedArea2Size() +
 426                  AFI->getDPRCalleeSavedAreaSize() +
 427                  ArgRegsSaveSize);
 428
 429     if (AFI->shouldRestoreSPFromFP()) {
 430       NumBytes = AFI->getFramePtrSpillOffset() - NumBytes;
 431       // Reset SP based on frame pointer only if the stack frame extends beyond
 432       // frame pointer stack slot, the target is ELF and the function has FP, or
 433       // the target uses var sized objects.
 434       if (NumBytes) {
 435         assert(!MFI.getPristineRegs(MF).test(ARM::R4) &&
 436                "No scratch register to restore SP from FP!");
 437         emitThumbRegPlusImmediate(MBB, MBBI, dl, ARM::R4, FramePtr, -NumBytes,
 438                                   TII, *RegInfo);
 439         BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr), ARM::SP)
 440             .addReg(ARM::R4)
 441             .add(predOps(ARMCC::AL));
 442       } else
 443         BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr), ARM::SP)
 444             .addReg(FramePtr)
 445             .add(predOps(ARMCC::AL));
 446     } else {
 447       if (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tBX_RET &&
 448           &MBB.front() != &*MBBI && std::prev(MBBI)->getOpcode() == ARM::tPOP) {
 449         MachineBasicBlock::iterator PMBBI = std::prev(MBBI);
 450         if (!tryFoldSPUpdateIntoPushPop(STI, MF, &*PMBBI, NumBytes))
 451           emitSPUpdate(MBB, PMBBI, TII, dl, *RegInfo, NumBytes);
 452       } else if (!tryFoldSPUpdateIntoPushPop(STI, MF, &*MBBI, NumBytes))
 453         emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, NumBytes);
 454     }
 455   }
 456
 457   if (needPopSpecialFixUp(MF)) {
 458     bool Done = emitPopSpecialFixUp(MBB, /* DoIt */ true);
 459     (void)Done;
 460     assert(Done && "Emission of the special fixup failed!?");
 461   }
 462 }
 463
 464 bool Thumb1FrameLowering::canUseAsEpilogue(const MachineBasicBlock &MBB) const {
 465   if (!needPopSpecialFixUp(*MBB.getParent()))
 466     return true;
 467
 468   MachineBasicBlock *TmpMBB = const_cast<MachineBasicBlock *>(&MBB);
 469   return emitPopSpecialFixUp(*TmpMBB, /* DoIt */ false);
 470 }
 471
 472 bool Thumb1FrameLowering::needPopSpecialFixUp(const MachineFunction &MF) const {
 473   ARMFunctionInfo *AFI =
 474       const_cast<MachineFunction *>(&MF)->getInfo<ARMFunctionInfo>();
 475   if (AFI->getArgRegsSaveSize())
 476     return true;
 477
 478   // LR cannot be encoded with Thumb1, i.e., it requires a special fix-up.
 479   for (const CalleeSavedInfo &CSI : MF.getFrameInfo().getCalleeSavedInfo())
 480     if (CSI.getReg() == ARM::LR)
 481       return true;
 482
 483   return false;
 484 }
 485
 486 bool Thumb1FrameLowering::emitPopSpecialFixUp(MachineBasicBlock &MBB,
 487                                               bool DoIt) const {
 488   MachineFunction &MF = *MBB.getParent();
 489   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 490   unsigned ArgRegsSaveSize = AFI->getArgRegsSaveSize();
 491   const TargetInstrInfo &TII = *STI.getInstrInfo();
 492   const ThumbRegisterInfo *RegInfo =
 493       static_cast<const ThumbRegisterInfo *>(STI.getRegisterInfo());
 494
 495   // If MBBI is a return instruction, or is a tPOP followed by a return
 496   // instruction in the successor BB, we may be able to directly restore
 497   // LR in the PC.
 498   // This is only possible with v5T ops (v4T can't change the Thumb bit via
 499   // a POP PC instruction), and only if we do not need to emit any SP update.
 500   // Otherwise, we need a temporary register to pop the value
 501   // and copy that value into LR.
 502   auto MBBI = MBB.getFirstTerminator();
 503   bool CanRestoreDirectly = STI.hasV5TOps() && !ArgRegsSaveSize;
 504   if (CanRestoreDirectly) {
 505     if (MBBI != MBB.end() && MBBI->getOpcode() != ARM::tB)
 506       CanRestoreDirectly = (MBBI->getOpcode() == ARM::tBX_RET ||
 507                             MBBI->getOpcode() == ARM::tPOP_RET);
 508     else {
 509       auto MBBI_prev = MBBI;
 510       MBBI_prev--;
 511       assert(MBBI_prev->getOpcode() == ARM::tPOP);
 512       assert(MBB.succ_size() == 1);
 513       if ((*MBB.succ_begin())->begin()->getOpcode() == ARM::tBX_RET)
 514         MBBI = MBBI_prev; // Replace the final tPOP with a tPOP_RET.
 515       else
 516         CanRestoreDirectly = false;
 517     }
 518   }
 519
 520   if (CanRestoreDirectly) {
 521     if (!DoIt || MBBI->getOpcode() == ARM::tPOP_RET)
 522       return true;
 523     MachineInstrBuilder MIB =
 524         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII.get(ARM::tPOP_RET))
 525             .add(predOps(ARMCC::AL));
 526     // Copy implicit ops and popped registers, if any.
 527     for (auto MO: MBBI->operands())
 528       if (MO.isReg() && (MO.isImplicit() || MO.isDef()))
 529         MIB.add(MO);
 530     MIB.addReg(ARM::PC, RegState::Define);
 531     // Erase the old instruction (tBX_RET or tPOP).
 532     MBB.erase(MBBI);
 533     return true;
 534   }
 535
 536   // Look for a temporary register to use.
 537   // First, compute the liveness information.
 538   const TargetRegisterInfo &TRI = *STI.getRegisterInfo();
 539   LivePhysRegs UsedRegs(TRI);
 540   UsedRegs.addLiveOuts(MBB);
 541   // The semantic of pristines changed recently and now,
 542   // the callee-saved registers that are touched in the function
 543   // are not part of the pristines set anymore.
 544   // Add those callee-saved now.
 545   const MCPhysReg *CSRegs = TRI.getCalleeSavedRegs(&MF);
 546   for (unsigned i = 0; CSRegs[i]; ++i)
 547     UsedRegs.addReg(CSRegs[i]);
 548
 549   DebugLoc dl = DebugLoc();
 550   if (MBBI != MBB.end()) {
 551     dl = MBBI->getDebugLoc();
 552     auto InstUpToMBBI = MBB.end();
 553     while (InstUpToMBBI != MBBI)
 554       // The pre-decrement is on purpose here.
 555       // We want to have the liveness right before MBBI.
 556       UsedRegs.stepBackward(*--InstUpToMBBI);
 557   }
 558
 559   // Look for a register that can be directly use in the POP.
 560   unsigned PopReg = 0;
 561   // And some temporary register, just in case.
 562   unsigned TemporaryReg = 0;
 563   BitVector PopFriendly =
 564       TRI.getAllocatableSet(MF, TRI.getRegClass(ARM::tGPRRegClassID));
 565   assert(PopFriendly.any() && "No allocatable pop-friendly register?!");
 566   // Rebuild the GPRs from the high registers because they are removed
 567   // form the GPR reg class for thumb1.
 568   BitVector GPRsNoLRSP =
 569       TRI.getAllocatableSet(MF, TRI.getRegClass(ARM::hGPRRegClassID));
 570   GPRsNoLRSP |= PopFriendly;
 571   GPRsNoLRSP.reset(ARM::LR);
 572   GPRsNoLRSP.reset(ARM::SP);
 573   GPRsNoLRSP.reset(ARM::PC);
 574   for (unsigned Register : GPRsNoLRSP.set_bits()) {
 575     if (!UsedRegs.contains(Register)) {
 576       // Remember the first pop-friendly register and exit.
 577       if (PopFriendly.test(Register)) {
 578         PopReg = Register;
 579         TemporaryReg = 0;
 580         break;
 581       }
 582       // Otherwise, remember that the register will be available to
 583       // save a pop-friendly register.
 584       TemporaryReg = Register;
 585     }
 586   }
 587
 588   if (!DoIt && !PopReg && !TemporaryReg)
 589     return false;
 590
 591   assert((PopReg || TemporaryReg) && "Cannot get LR");
 592
 593   if (TemporaryReg) {
 594     assert(!PopReg && "Unnecessary MOV is about to be inserted");
 595     PopReg = PopFriendly.find_first();
 596     BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr))
 597         .addReg(TemporaryReg, RegState::Define)
 598         .addReg(PopReg, RegState::Kill)
 599         .add(predOps(ARMCC::AL));
 600   }
 601
 602   if (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tPOP_RET) {
 603     // We couldn't use the direct restoration above, so
 604     // perform the opposite conversion: tPOP_RET to tPOP.
 605     MachineInstrBuilder MIB =
 606         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII.get(ARM::tPOP))
 607             .add(predOps(ARMCC::AL));
 608     bool Popped = false;
 609     for (auto MO: MBBI->operands())
 610       if (MO.isReg() && (MO.isImplicit() || MO.isDef()) &&
 611           MO.getReg() != ARM::PC) {
 612         MIB.add(MO);
 613         if (!MO.isImplicit())
 614           Popped = true;
 615       }
 616     // Is there anything left to pop?
 617     if (!Popped)
 618       MBB.erase(MIB.getInstr());
 619     // Erase the old instruction.
 620     MBB.erase(MBBI);
 621     MBBI = BuildMI(MBB, MBB.end(), dl, TII.get(ARM::tBX_RET))
 622                .add(predOps(ARMCC::AL));
 623   }
 624
 625   assert(PopReg && "Do not know how to get LR");
 626   BuildMI(MBB, MBBI, dl, TII.get(ARM::tPOP))
 627       .add(predOps(ARMCC::AL))
 628       .addReg(PopReg, RegState::Define);
 629
 630   emitSPUpdate(MBB, MBBI, TII, dl, *RegInfo, ArgRegsSaveSize);
 631
 632   BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr))
 633       .addReg(ARM::LR, RegState::Define)
 634       .addReg(PopReg, RegState::Kill)
 635       .add(predOps(ARMCC::AL));
 636
 637   if (TemporaryReg)
 638     BuildMI(MBB, MBBI, dl, TII.get(ARM::tMOVr))
 639         .addReg(PopReg, RegState::Define)
 640         .addReg(TemporaryReg, RegState::Kill)
 641         .add(predOps(ARMCC::AL));
 642
 643   return true;
 644 }
 645
 646 // Return the first iteraror after CurrentReg which is present in EnabledRegs,
 647 // or OrderEnd if no further registers are in that set. This does not advance
 648 // the iterator fiorst, so returns CurrentReg if it is in EnabledRegs.
 649 template <unsigned SetSize>
 650 static const unsigned *
 651 findNextOrderedReg(const unsigned *CurrentReg,
 652                    SmallSet<unsigned, SetSize> &EnabledRegs,
 653                    const unsigned *OrderEnd) {
 654   while (CurrentReg != OrderEnd && !EnabledRegs.count(*CurrentReg))
 655     ++CurrentReg;
 656   return CurrentReg;
 657 }
 658
 659 bool Thumb1FrameLowering::
 660 spillCalleeSavedRegisters(MachineBasicBlock &MBB,
 661                           MachineBasicBlock::iterator MI,
 662                           const std::vector<CalleeSavedInfo> &CSI,
 663                           const TargetRegisterInfo *TRI) const {
 664   if (CSI.empty())
 665     return false;
 666
 667   DebugLoc DL;
 668   const TargetInstrInfo &TII = *STI.getInstrInfo();
 669   MachineFunction &MF = *MBB.getParent();
 670   const ARMBaseRegisterInfo *RegInfo = static_cast<const ARMBaseRegisterInfo *>(
 671       MF.getSubtarget().getRegisterInfo());
 672
 673   SmallSet<unsigned, 9> LoRegsToSave; // r0-r7, lr
 674   SmallSet<unsigned, 4> HiRegsToSave; // r8-r11
 675   SmallSet<unsigned, 9> CopyRegs; // Registers which can be used after pushing
 676                            // LoRegs for saving HiRegs.
 677
 678   for (unsigned i = CSI.size(); i != 0; --i) {
 679     unsigned Reg = CSI[i-1].getReg();
 680
 681     if (ARM::tGPRRegClass.contains(Reg) || Reg == ARM::LR) {
 682       LoRegsToSave.insert(Reg);
 683     } else if (ARM::hGPRRegClass.contains(Reg) && Reg != ARM::LR) {
 684       HiRegsToSave.insert(Reg);
 685     } else {
 686       llvm_unreachable("callee-saved register of unexpected class");
 687     }
 688
 689     if ((ARM::tGPRRegClass.contains(Reg) || Reg == ARM::LR) &&
 690         !MF.getRegInfo().isLiveIn(Reg) &&
 691         !(hasFP(MF) && Reg == RegInfo->getFrameRegister(MF)))
 692       CopyRegs.insert(Reg);
 693   }
 694
 695   // Unused argument registers can be used for the high register saving.
 696   for (unsigned ArgReg : {ARM::R0, ARM::R1, ARM::R2, ARM::R3})
 697     if (!MF.getRegInfo().isLiveIn(ArgReg))
 698       CopyRegs.insert(ArgReg);
 699
 700   // Push the low registers and lr
 701   if (!LoRegsToSave.empty()) {
 702     MachineInstrBuilder MIB =
 703         BuildMI(MBB, MI, DL, TII.get(ARM::tPUSH)).add(predOps(ARMCC::AL));
 704     for (unsigned Reg : {ARM::R4, ARM::R5, ARM::R6, ARM::R7, ARM::LR}) {
 705       if (LoRegsToSave.count(Reg)) {
 706         bool isKill = !MF.getRegInfo().isLiveIn(Reg);
 707         if (isKill)
 708           MBB.addLiveIn(Reg);
 709
 710         MIB.addReg(Reg, getKillRegState(isKill));
 711       }
 712     }
 713     MIB.setMIFlags(MachineInstr::FrameSetup);
 714   }
 715
 716   // Push the high registers. There are no store instructions that can access
 717   // these registers directly, so we have to move them to low registers, and
 718   // push them. This might take multiple pushes, as it is possible for there to
 719   // be fewer low registers available than high registers which need saving.
 720
 721   // These are in reverse order so that in the case where we need to use
 722   // multiple PUSH instructions, the order of the registers on the stack still
 723   // matches the unwind info. They need to be swicthed back to ascending order
 724   // before adding to the PUSH instruction.
 725   static const unsigned AllCopyRegs[] = {ARM::LR, ARM::R7, ARM::R6,
 726                                          ARM::R5, ARM::R4, ARM::R3,
 727                                          ARM::R2, ARM::R1, ARM::R0};
 728   static const unsigned AllHighRegs[] = {ARM::R11, ARM::R10, ARM::R9, ARM::R8};
 729
 730   const unsigned *AllCopyRegsEnd = std::end(AllCopyRegs);
 731   const unsigned *AllHighRegsEnd = std::end(AllHighRegs);
 732
 733   // Find the first register to save.
 734   const unsigned *HiRegToSave = findNextOrderedReg(
 735       std::begin(AllHighRegs), HiRegsToSave, AllHighRegsEnd);
 736
 737   while (HiRegToSave != AllHighRegsEnd) {
 738     // Find the first low register to use.
 739     const unsigned *CopyReg =
 740         findNextOrderedReg(std::begin(AllCopyRegs), CopyRegs, AllCopyRegsEnd);
 741
 742     // Create the PUSH, but don't insert it yet (the MOVs need to come first).
 743     MachineInstrBuilder PushMIB =
 744         BuildMI(MF, DL, TII.get(ARM::tPUSH)).add(predOps(ARMCC::AL));
 745
 746     SmallVector<unsigned, 4> RegsToPush;
 747     while (HiRegToSave != AllHighRegsEnd && CopyReg != AllCopyRegsEnd) {
 748       if (HiRegsToSave.count(*HiRegToSave)) {
 749         bool isKill = !MF.getRegInfo().isLiveIn(*HiRegToSave);
 750         if (isKill)
 751           MBB.addLiveIn(*HiRegToSave);
 752
 753         // Emit a MOV from the high reg to the low reg.
 754         BuildMI(MBB, MI, DL, TII.get(ARM::tMOVr))
 755             .addReg(*CopyReg, RegState::Define)
 756             .addReg(*HiRegToSave, getKillRegState(isKill))
 757             .add(predOps(ARMCC::AL));
 758
 759         // Record the register that must be added to the PUSH.
 760         RegsToPush.push_back(*CopyReg);
 761
 762         CopyReg = findNextOrderedReg(++CopyReg, CopyRegs, AllCopyRegsEnd);
 763         HiRegToSave =
 764             findNextOrderedReg(++HiRegToSave, HiRegsToSave, AllHighRegsEnd);
 765       }
 766     }
 767
 768     // Add the low registers to the PUSH, in ascending order.
 769     for (unsigned Reg : llvm::reverse(RegsToPush))
 770       PushMIB.addReg(Reg, RegState::Kill);
 771
 772     // Insert the PUSH instruction after the MOVs.
 773     MBB.insert(MI, PushMIB);
 774   }
 775
 776   return true;
 777 }
 778
 779 bool Thumb1FrameLowering::
 780 restoreCalleeSavedRegisters(MachineBasicBlock &MBB,
 781                             MachineBasicBlock::iterator MI,
 782                             const std::vector<CalleeSavedInfo> &CSI,
 783                             const TargetRegisterInfo *TRI) const {
 784   if (CSI.empty())
 785     return false;
 786
 787   MachineFunction &MF = *MBB.getParent();
 788   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 789   const TargetInstrInfo &TII = *STI.getInstrInfo();
 790   const ARMBaseRegisterInfo *RegInfo = static_cast<const ARMBaseRegisterInfo *>(
 791       MF.getSubtarget().getRegisterInfo());
 792
 793   bool isVarArg = AFI->getArgRegsSaveSize() > 0;
 794   DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc() : DebugLoc();
 795
 796   SmallSet<unsigned, 9> LoRegsToRestore;
 797   SmallSet<unsigned, 4> HiRegsToRestore;
 798   // Low registers (r0-r7) which can be used to restore the high registers.
 799   SmallSet<unsigned, 9> CopyRegs;
 800
 801   for (CalleeSavedInfo I : CSI) {
 802     unsigned Reg = I.getReg();
 803
 804     if (ARM::tGPRRegClass.contains(Reg) || Reg == ARM::LR) {
 805       LoRegsToRestore.insert(Reg);
 806     } else if (ARM::hGPRRegClass.contains(Reg) && Reg != ARM::LR) {
 807       HiRegsToRestore.insert(Reg);
 808     } else {
 809       llvm_unreachable("callee-saved register of unexpected class");
 810     }
 811
 812     // If this is a low register not used as the frame pointer, we may want to
 813     // use it for restoring the high registers.
 814     if ((ARM::tGPRRegClass.contains(Reg)) &&
 815         !(hasFP(MF) && Reg == RegInfo->getFrameRegister(MF)))
 816       CopyRegs.insert(Reg);
 817   }
 818
 819   // If this is a return block, we may be able to use some unused return value
 820   // registers for restoring the high regs.
 821   auto Terminator = MBB.getFirstTerminator();
 822   if (Terminator != MBB.end() && Terminator->getOpcode() == ARM::tBX_RET) {
 823     CopyRegs.insert(ARM::R0);
 824     CopyRegs.insert(ARM::R1);
 825     CopyRegs.insert(ARM::R2);
 826     CopyRegs.insert(ARM::R3);
 827     for (auto Op : Terminator->implicit_operands()) {
 828       if (Op.isReg())
 829         CopyRegs.erase(Op.getReg());
 830     }
 831   }
 832
 833   static const unsigned AllCopyRegs[] = {ARM::R0, ARM::R1, ARM::R2, ARM::R3,
 834                                          ARM::R4, ARM::R5, ARM::R6, ARM::R7};
 835   static const unsigned AllHighRegs[] = {ARM::R8, ARM::R9, ARM::R10, ARM::R11};
 836
 837   const unsigned *AllCopyRegsEnd = std::end(AllCopyRegs);
 838   const unsigned *AllHighRegsEnd = std::end(AllHighRegs);
 839
 840   // Find the first register to restore.
 841   auto HiRegToRestore = findNextOrderedReg(std::begin(AllHighRegs),
 842                                            HiRegsToRestore, AllHighRegsEnd);
 843
 844   while (HiRegToRestore != AllHighRegsEnd) {
 845     assert(!CopyRegs.empty());
 846     // Find the first low register to use.
 847     auto CopyReg =
 848         findNextOrderedReg(std::begin(AllCopyRegs), CopyRegs, AllCopyRegsEnd);
 849
 850     // Create the POP instruction.
 851     MachineInstrBuilder PopMIB =
 852         BuildMI(MBB, MI, DL, TII.get(ARM::tPOP)).add(predOps(ARMCC::AL));
 853
 854     while (HiRegToRestore != AllHighRegsEnd && CopyReg != AllCopyRegsEnd) {
 855       // Add the low register to the POP.
 856       PopMIB.addReg(*CopyReg, RegState::Define);
 857
 858       // Create the MOV from low to high register.
 859       BuildMI(MBB, MI, DL, TII.get(ARM::tMOVr))
 860           .addReg(*HiRegToRestore, RegState::Define)
 861           .addReg(*CopyReg, RegState::Kill)
 862           .add(predOps(ARMCC::AL));
 863
 864       CopyReg = findNextOrderedReg(++CopyReg, CopyRegs, AllCopyRegsEnd);
 865       HiRegToRestore =
 866           findNextOrderedReg(++HiRegToRestore, HiRegsToRestore, AllHighRegsEnd);
 867     }
 868   }
 869
 870   MachineInstrBuilder MIB =
 871       BuildMI(MF, DL, TII.get(ARM::tPOP)).add(predOps(ARMCC::AL));
 872
 873   bool NeedsPop = false;
 874   for (unsigned i = CSI.size(); i != 0; --i) {
 875     unsigned Reg = CSI[i-1].getReg();
 876
 877     // High registers (excluding lr) have already been dealt with
 878     if (!(ARM::tGPRRegClass.contains(Reg) || Reg == ARM::LR))
 879       continue;
 880
 881     if (Reg == ARM::LR) {
 882       if (MBB.succ_empty()) {
 883         // Special epilogue for vararg functions. See emitEpilogue
 884         if (isVarArg)
 885           continue;
 886         // ARMv4T requires BX, see emitEpilogue
 887         if (!STI.hasV5TOps())
 888           continue;
 889         // Tailcall optimization failed; change TCRETURN to a tBL
 890         if (MI->getOpcode() == ARM::TCRETURNdi ||
 891             MI->getOpcode() == ARM::TCRETURNri) {
 892           unsigned Opcode = MI->getOpcode() == ARM::TCRETURNdi
 893                             ? ARM::tBL : ARM::tBLXr;
 894           MachineInstrBuilder BL = BuildMI(MF, DL, TII.get(Opcode));
 895           BL.add(predOps(ARMCC::AL));
 896           BL.add(MI->getOperand(0));
 897           MBB.insert(MI, &*BL);
 898         }
 899         Reg = ARM::PC;
 900         (*MIB).setDesc(TII.get(ARM::tPOP_RET));
 901         if (MI != MBB.end())
 902           MIB.copyImplicitOps(*MI);
 903         MI = MBB.erase(MI);
 904       } else
 905         // LR may only be popped into PC, as part of return sequence.
 906         // If this isn't the return sequence, we'll need emitPopSpecialFixUp
 907         // to restore LR the hard way.
 908         continue;
 909     }
 910     MIB.addReg(Reg, getDefRegState(true));
 911     NeedsPop = true;
 912   }
 913
 914   // It's illegal to emit pop instruction without operands.
 915   if (NeedsPop)
 916     MBB.insert(MI, &*MIB);
 917   else
 918     MF.DeleteMachineInstr(MIB);
 919
 920   return true;
 921 }