lib/Target/Hexagon/HexagonFrameLowering.cpp

   1 //===-- HexagonFrameLowering.cpp - Define frame lowering ------------------===//
   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
  11 #define DEBUG_TYPE "hexagon-pei"
  12
  13 #include "HexagonFrameLowering.h"
  14 #include "Hexagon.h"
  15 #include "HexagonInstrInfo.h"
  16 #include "HexagonMachineFunctionInfo.h"
  17 #include "HexagonRegisterInfo.h"
  18 #include "HexagonSubtarget.h"
  19 #include "HexagonTargetMachine.h"
  20 #include "llvm/ADT/BitVector.h"
  21 #include "llvm/ADT/PostOrderIterator.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/CodeGen/MachineDominators.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/MachineModuleInfo.h"
  29 #include "llvm/CodeGen/MachinePostDominators.h"
  30 #include "llvm/CodeGen/MachineRegisterInfo.h"
  31 #include "llvm/CodeGen/RegisterScavenging.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Target/TargetInstrInfo.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include "llvm/Target/TargetOptions.h"
  40
  41 // Hexagon stack frame layout as defined by the ABI:
  42 //
  43 //                                                       Incoming arguments
  44 //                                                       passed via stack
  45 //                                                                      |
  46 //                                                                      |
  47 //        SP during function's                 FP during function's     |
  48 //    +-- runtime (top of stack)               runtime (bottom) --+     |
  49 //    |                                                           |     |
  50 // --++---------------------+------------------+-----------------++-+-------
  51 //   |  parameter area for  |  variable-size   |   fixed-size    |LR|  arg
  52 //   |   called functions   |  local objects   |  local objects  |FP|
  53 // --+----------------------+------------------+-----------------+--+-------
  54 //    <-    size known    -> <- size unknown -> <- size known  ->
  55 //
  56 // Low address                                                 High address
  57 //
  58 // <--- stack growth
  59 //
  60 //
  61 // - In any circumstances, the outgoing function arguments are always accessi-
  62 //   ble using the SP, and the incoming arguments are accessible using the FP.
  63 // - If the local objects are not aligned, they can always be accessed using
  64 //   the FP.
  65 // - If there are no variable-sized objects, the local objects can always be
  66 //   accessed using the SP, regardless whether they are aligned or not. (The
  67 //   alignment padding will be at the bottom of the stack (highest address),
  68 //   and so the offset with respect to the SP will be known at the compile-
  69 //   -time.)
  70 //
  71 // The only complication occurs if there are both, local aligned objects, and
  72 // dynamically allocated (variable-sized) objects. The alignment pad will be
  73 // placed between the FP and the local objects, thus preventing the use of the
  74 // FP to access the local objects. At the same time, the variable-sized objects
  75 // will be between the SP and the local objects, thus introducing an unknown
  76 // distance from the SP to the locals.
  77 //
  78 // To avoid this problem, a new register is created that holds the aligned
  79 // address of the bottom of the stack, referred in the sources as AP (aligned
  80 // pointer). The AP will be equal to "FP-p", where "p" is the smallest pad
  81 // that aligns AP to the required boundary (a maximum of the alignments of
  82 // all stack objects, fixed- and variable-sized). All local objects[1] will
  83 // then use AP as the base pointer.
  84 // [1] The exception is with "fixed" stack objects. "Fixed" stack objects get
  85 // their name from being allocated at fixed locations on the stack, relative
  86 // to the FP. In the presence of dynamic allocation and local alignment, such
  87 // objects can only be accessed through the FP.
  88 //
  89 // Illustration of the AP:
  90 //                                                                FP --+
  91 //                                                                     |
  92 // ---------------+---------------------+-----+-----------------------++-+--
  93 //   Rest of the  | Local stack objects | Pad |  Fixed stack objects  |LR|
  94 //   stack frame  | (aligned)           |     |  (CSR, spills, etc.)  |FP|
  95 // ---------------+---------------------+-----+-----------------+-----+--+--
  96 //                                      |<-- Multiple of the -->|
  97 //                                           stack alignment    +-- AP
  98 //
  99 // The AP is set up at the beginning of the function. Since it is not a dedi-
 100 // cated (reserved) register, it needs to be kept live throughout the function
 101 // to be available as the base register for local object accesses.
 102 // Normally, an address of a stack objects is obtained by a pseudo-instruction
 103 // TFR_FI. To access local objects with the AP register present, a different
 104 // pseudo-instruction needs to be used: TFR_FIA. The TFR_FIA takes one extra
 105 // argument compared to TFR_FI: the first input register is the AP register.
 106 // This keeps the register live between its definition and its uses.
 107
 108 // The AP register is originally set up using pseudo-instruction ALIGNA:
 109 //   AP = ALIGNA A
 110 // where
 111 //   A  - required stack alignment
 112 // The alignment value must be the maximum of all alignments required by
 113 // any stack object.
 114
 115 // The dynamic allocation uses a pseudo-instruction ALLOCA:
 116 //   Rd = ALLOCA Rs, A
 117 // where
 118 //   Rd - address of the allocated space
 119 //   Rs - minimum size (the actual allocated can be larger to accommodate
 120 //        alignment)
 121 //   A  - required alignment
 122
 123
 124 using namespace llvm;
 125
 126 static cl::opt<bool> DisableDeallocRet("disable-hexagon-dealloc-ret",
 127     cl::Hidden, cl::desc("Disable Dealloc Return for Hexagon target"));
 128
 129
 130 static cl::opt<int> NumberScavengerSlots("number-scavenger-slots",
 131     cl::Hidden, cl::desc("Set the number of scavenger slots"), cl::init(2),
 132     cl::ZeroOrMore);
 133
 134 static cl::opt<int> SpillFuncThreshold("spill-func-threshold",
 135     cl::Hidden, cl::desc("Specify O2(not Os) spill func threshold"),
 136     cl::init(6), cl::ZeroOrMore);
 137
 138 static cl::opt<int> SpillFuncThresholdOs("spill-func-threshold-Os",
 139     cl::Hidden, cl::desc("Specify Os spill func threshold"),
 140     cl::init(1), cl::ZeroOrMore);
 141
 142 static cl::opt<bool> EnableShrinkWrapping("hexagon-shrink-frame",
 143     cl::init(true), cl::Hidden, cl::ZeroOrMore,
 144     cl::desc("Enable stack frame shrink wrapping"));
 145
 146 static cl::opt<unsigned> ShrinkLimit("shrink-frame-limit", cl::init(UINT_MAX),
 147     cl::Hidden, cl::ZeroOrMore, cl::desc("Max count of stack frame "
 148     "shrink-wraps"));
 149
 150 namespace {
 151   /// Map a register pair Reg to the subregister that has the greater "number",
 152   /// i.e. D3 (aka R7:6) will be mapped to R7, etc.
 153   unsigned getMax32BitSubRegister(unsigned Reg, const TargetRegisterInfo &TRI,
 154                                   bool hireg = true) {
 155     if (Reg < Hexagon::D0 || Reg > Hexagon::D15)
 156       return Reg;
 157
 158     unsigned RegNo = 0;
 159     for (MCSubRegIterator SubRegs(Reg, &TRI); SubRegs.isValid(); ++SubRegs) {
 160       if (hireg) {
 161         if (*SubRegs > RegNo)
 162           RegNo = *SubRegs;
 163       } else {
 164         if (!RegNo || *SubRegs < RegNo)
 165           RegNo = *SubRegs;
 166       }
 167     }
 168     return RegNo;
 169   }
 170
 171   /// Returns the callee saved register with the largest id in the vector.
 172   unsigned getMaxCalleeSavedReg(const std::vector<CalleeSavedInfo> &CSI,
 173                                 const TargetRegisterInfo &TRI) {
 174     assert(Hexagon::R1 > 0 &&
 175            "Assume physical registers are encoded as positive integers");
 176     if (CSI.empty())
 177       return 0;
 178
 179     unsigned Max = getMax32BitSubRegister(CSI[0].getReg(), TRI);
 180     for (unsigned I = 1, E = CSI.size(); I < E; ++I) {
 181       unsigned Reg = getMax32BitSubRegister(CSI[I].getReg(), TRI);
 182       if (Reg > Max)
 183         Max = Reg;
 184     }
 185     return Max;
 186   }
 187
 188   /// Checks if the basic block contains any instruction that needs a stack
 189   /// frame to be already in place.
 190   bool needsStackFrame(const MachineBasicBlock &MBB, const BitVector &CSR) {
 191     for (auto &I : MBB) {
 192       const MachineInstr *MI = &I;
 193       if (MI->isCall())
 194         return true;
 195       unsigned Opc = MI->getOpcode();
 196       switch (Opc) {
 197         case Hexagon::ALLOCA:
 198         case Hexagon::ALIGNA:
 199           return true;
 200         default:
 201           break;
 202       }
 203       // Check individual operands.
 204       for (const MachineOperand &MO : MI->operands()) {
 205         // While the presence of a frame index does not prove that a stack
 206         // frame will be required, all frame indexes should be within alloc-
 207         // frame/deallocframe. Otherwise, the code that translates a frame
 208         // index into an offset would have to be aware of the placement of
 209         // the frame creation/destruction instructions.
 210         if (MO.isFI())
 211           return true;
 212         if (!MO.isReg())
 213           continue;
 214         unsigned R = MO.getReg();
 215         // Virtual registers will need scavenging, which then may require
 216         // a stack slot.
 217         if (TargetRegisterInfo::isVirtualRegister(R))
 218           return true;
 219         if (CSR[R])
 220           return true;
 221       }
 222     }
 223     return false;
 224   }
 225
 226   /// Returns true if MBB has a machine instructions that indicates a tail call
 227   /// in the block.
 228   bool hasTailCall(const MachineBasicBlock &MBB) {
 229     MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr();
 230     unsigned RetOpc = I->getOpcode();
 231     return RetOpc == Hexagon::TCRETURNi || RetOpc == Hexagon::TCRETURNr;
 232   }
 233
 234   /// Returns true if MBB contains an instruction that returns.
 235   bool hasReturn(const MachineBasicBlock &MBB) {
 236     for (auto I = MBB.getFirstTerminator(), E = MBB.end(); I != E; ++I)
 237       if (I->isReturn())
 238         return true;
 239     return false;
 240   }
 241 } // namespace
 242
 243
 244 /// Implements shrink-wrapping of the stack frame. By default, stack frame
 245 /// is created in the function entry block, and is cleaned up in every block
 246 /// that returns. This function finds alternate blocks: one for the frame
 247 /// setup (prolog) and one for the cleanup (epilog).
 248 void HexagonFrameLowering::findShrunkPrologEpilog(MachineFunction &MF,
 249       MachineBasicBlock *&PrologB, MachineBasicBlock *&EpilogB) const {
 250   static unsigned ShrinkCounter = 0;
 251
 252   if (ShrinkLimit.getPosition()) {
 253     if (ShrinkCounter >= ShrinkLimit)
 254       return;
 255     ShrinkCounter++;
 256   }
 257
 258   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 259   auto &HRI = *HST.getRegisterInfo();
 260
 261   MachineDominatorTree MDT;
 262   MDT.runOnMachineFunction(MF);
 263   MachinePostDominatorTree MPT;
 264   MPT.runOnMachineFunction(MF);
 265
 266   typedef DenseMap<unsigned,unsigned> UnsignedMap;
 267   UnsignedMap RPO;
 268   typedef ReversePostOrderTraversal<const MachineFunction*> RPOTType;
 269   RPOTType RPOT(&MF);
 270   unsigned RPON = 0;
 271   for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
 272     RPO[(*I)->getNumber()] = RPON++;
 273
 274   // Don't process functions that have loops, at least for now. Placement
 275   // of prolog and epilog must take loop structure into account. For simpli-
 276   // city don't do it right now.
 277   for (auto &I : MF) {
 278     unsigned BN = RPO[I.getNumber()];
 279     for (auto SI = I.succ_begin(), SE = I.succ_end(); SI != SE; ++SI) {
 280       // If found a back-edge, return.
 281       if (RPO[(*SI)->getNumber()] <= BN)
 282         return;
 283     }
 284   }
 285
 286   // Collect the set of blocks that need a stack frame to execute. Scan
 287   // each block for uses/defs of callee-saved registers, calls, etc.
 288   SmallVector<MachineBasicBlock*,16> SFBlocks;
 289   BitVector CSR(Hexagon::NUM_TARGET_REGS);
 290   for (const MCPhysReg *P = HRI.getCalleeSavedRegs(&MF); *P; ++P)
 291     CSR[*P] = true;
 292
 293   for (auto &I : MF)
 294     if (needsStackFrame(I, CSR))
 295       SFBlocks.push_back(&I);
 296
 297   DEBUG({
 298     dbgs() << "Blocks needing SF: {";
 299     for (auto &B : SFBlocks)
 300       dbgs() << " BB#" << B->getNumber();
 301     dbgs() << " }\n";
 302   });
 303   // No frame needed?
 304   if (SFBlocks.empty())
 305     return;
 306
 307   // Pick a common dominator and a common post-dominator.
 308   MachineBasicBlock *DomB = SFBlocks[0];
 309   for (unsigned i = 1, n = SFBlocks.size(); i < n; ++i) {
 310     DomB = MDT.findNearestCommonDominator(DomB, SFBlocks[i]);
 311     if (!DomB)
 312       break;
 313   }
 314   MachineBasicBlock *PDomB = SFBlocks[0];
 315   for (unsigned i = 1, n = SFBlocks.size(); i < n; ++i) {
 316     PDomB = MPT.findNearestCommonDominator(PDomB, SFBlocks[i]);
 317     if (!PDomB)
 318       break;
 319   }
 320   DEBUG({
 321     dbgs() << "Computed dom block: BB#";
 322     if (DomB) dbgs() << DomB->getNumber();
 323     else      dbgs() << "<null>";
 324     dbgs() << ", computed pdom block: BB#";
 325     if (PDomB) dbgs() << PDomB->getNumber();
 326     else       dbgs() << "<null>";
 327     dbgs() << "\n";
 328   });
 329   if (!DomB || !PDomB)
 330     return;
 331
 332   // Make sure that DomB dominates PDomB and PDomB post-dominates DomB.
 333   if (!MDT.dominates(DomB, PDomB)) {
 334     DEBUG(dbgs() << "Dom block does not dominate pdom block\n");
 335     return;
 336   }
 337   if (!MPT.dominates(PDomB, DomB)) {
 338     DEBUG(dbgs() << "PDom block does not post-dominate dom block\n");
 339     return;
 340   }
 341
 342   // Finally, everything seems right.
 343   PrologB = DomB;
 344   EpilogB = PDomB;
 345 }
 346
 347 /// Perform most of the PEI work here:
 348 /// - saving/restoring of the callee-saved registers,
 349 /// - stack frame creation and destruction.
 350 /// Normally, this work is distributed among various functions, but doing it
 351 /// in one place allows shrink-wrapping of the stack frame.
 352 void HexagonFrameLowering::emitPrologue(MachineFunction &MF,
 353                                         MachineBasicBlock &MBB) const {
 354   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 355   auto &HRI = *HST.getRegisterInfo();
 356
 357   assert(&MF.front() == &MBB && "Shrink-wrapping not yet supported");
 358   MachineFrameInfo *MFI = MF.getFrameInfo();
 359   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 360
 361   MachineBasicBlock *PrologB = &MF.front(), *EpilogB = nullptr;
 362   if (EnableShrinkWrapping)
 363     findShrunkPrologEpilog(MF, PrologB, EpilogB);
 364
 365   insertCSRSpillsInBlock(*PrologB, CSI, HRI);
 366   insertPrologueInBlock(*PrologB);
 367
 368   if (EpilogB) {
 369     insertCSRRestoresInBlock(*EpilogB, CSI, HRI);
 370     insertEpilogueInBlock(*EpilogB);
 371   } else {
 372     for (auto &B : MF)
 373       if (!B.empty() && B.back().isReturn())
 374         insertCSRRestoresInBlock(B, CSI, HRI);
 375
 376     for (auto &B : MF)
 377       if (!B.empty() && B.back().isReturn())
 378         insertEpilogueInBlock(B);
 379   }
 380 }
 381
 382
 383 void HexagonFrameLowering::insertPrologueInBlock(MachineBasicBlock &MBB) const {
 384   MachineFunction &MF = *MBB.getParent();
 385   MachineFrameInfo *MFI = MF.getFrameInfo();
 386   MachineModuleInfo &MMI = MF.getMMI();
 387   MachineBasicBlock::iterator MBBI = MBB.begin();
 388   auto &HTM = static_cast<const HexagonTargetMachine&>(MF.getTarget());
 389   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 390   auto &HII = *HST.getInstrInfo();
 391   auto &HRI = *HST.getRegisterInfo();
 392   DebugLoc dl;
 393
 394   unsigned MaxAlign = std::max(MFI->getMaxAlignment(), getStackAlignment());
 395
 396   // Calculate the total stack frame size.
 397   // Get the number of bytes to allocate from the FrameInfo.
 398   unsigned FrameSize = MFI->getStackSize();
 399   // Round up the max call frame size to the max alignment on the stack.
 400   unsigned MaxCFA = RoundUpToAlignment(MFI->getMaxCallFrameSize(), MaxAlign);
 401   MFI->setMaxCallFrameSize(MaxCFA);
 402
 403   FrameSize = MaxCFA + RoundUpToAlignment(FrameSize, MaxAlign);
 404   MFI->setStackSize(FrameSize);
 405
 406   bool AlignStack = (MaxAlign > getStackAlignment());
 407
 408   // Check if frame moves are needed for EH.
 409   bool needsFrameMoves = MMI.hasDebugInfo() ||
 410     MF.getFunction()->needsUnwindTableEntry();
 411
 412   // Get the number of bytes to allocate from the FrameInfo.
 413   unsigned NumBytes = MFI->getStackSize();
 414   unsigned SP = HRI.getStackRegister();
 415   unsigned MaxCF = MFI->getMaxCallFrameSize();
 416   MachineBasicBlock::iterator InsertPt = MBB.begin();
 417
 418   auto *FuncInfo = MF.getInfo<HexagonMachineFunctionInfo>();
 419   auto &AdjustRegs = FuncInfo->getAllocaAdjustInsts();
 420
 421   for (auto MI : AdjustRegs) {
 422     assert((MI->getOpcode() == Hexagon::ALLOCA) && "Expected alloca");
 423     expandAlloca(MI, HII, SP, MaxCF);
 424     MI->eraseFromParent();
 425   }
 426
 427   //
 428   // Only insert ALLOCFRAME if we need to or at -O0 for the debugger.  Think
 429   // that this shouldn't be required, but doing so now because gcc does and
 430   // gdb can't break at the start of the function without it.  Will remove if
 431   // this turns out to be a gdb bug.
 432   //
 433   bool NoOpt = (HTM.getOptLevel() == CodeGenOpt::None);
 434   if (!NoOpt && !FuncInfo->hasClobberLR() && !hasFP(MF))
 435     return;
 436
 437   // Check for overflow.
 438   // Hexagon_TODO: Ugh! hardcoding. Is there an API that can be used?
 439   const unsigned int ALLOCFRAME_MAX = 16384;
 440
 441   // Create a dummy memory operand to avoid allocframe from being treated as
 442   // a volatile memory reference.
 443   MachineMemOperand *MMO =
 444     MF.getMachineMemOperand(MachinePointerInfo(), MachineMemOperand::MOStore,
 445                             4, 4);
 446
 447   if (NumBytes >= ALLOCFRAME_MAX) {
 448     // Emit allocframe(#0).
 449     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::S2_allocframe))
 450       .addImm(0)
 451       .addMemOperand(MMO);
 452
 453     // Subtract offset from frame pointer.
 454     // We use a caller-saved non-parameter register for that.
 455     unsigned CallerSavedReg = HRI.getFirstCallerSavedNonParamReg();
 456     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::CONST32_Int_Real),
 457             CallerSavedReg).addImm(NumBytes);
 458     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::A2_sub), SP)
 459       .addReg(SP)
 460       .addReg(CallerSavedReg);
 461   } else {
 462     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::S2_allocframe))
 463       .addImm(NumBytes)
 464       .addMemOperand(MMO);
 465   }
 466
 467   if (AlignStack) {
 468     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::A2_andir), SP)
 469         .addReg(SP)
 470         .addImm(-int64_t(MaxAlign));
 471   }
 472
 473   if (needsFrameMoves) {
 474     std::vector<MCCFIInstruction> Instructions = MMI.getFrameInstructions();
 475     MCSymbol *FrameLabel = MMI.getContext().createTempSymbol();
 476
 477     // Advance CFA. DW_CFA_def_cfa
 478     unsigned DwFPReg = HRI.getDwarfRegNum(HRI.getFrameRegister(), true);
 479     unsigned DwRAReg = HRI.getDwarfRegNum(HRI.getRARegister(), true);
 480
 481     // CFA = FP + 8
 482     unsigned CFIIndex = MMI.addFrameInst(MCCFIInstruction::createDefCfa(
 483                                                FrameLabel, DwFPReg, -8));
 484     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 485            .addCFIIndex(CFIIndex);
 486
 487     // R31 (return addr) = CFA - #4
 488     CFIIndex = MMI.addFrameInst(MCCFIInstruction::createOffset(
 489                                                FrameLabel, DwRAReg, -4));
 490     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 491            .addCFIIndex(CFIIndex);
 492
 493     // R30 (frame ptr) = CFA - #8)
 494     CFIIndex = MMI.addFrameInst(MCCFIInstruction::createOffset(
 495                                                FrameLabel, DwFPReg, -8));
 496     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 497            .addCFIIndex(CFIIndex);
 498
 499     unsigned int regsToMove[] = {
 500       Hexagon::R1,  Hexagon::R0,  Hexagon::R3,  Hexagon::R2,
 501       Hexagon::R17, Hexagon::R16, Hexagon::R19, Hexagon::R18,
 502       Hexagon::R21, Hexagon::R20, Hexagon::R23, Hexagon::R22,
 503       Hexagon::R25, Hexagon::R24, Hexagon::R27, Hexagon::R26,
 504       Hexagon::D0,  Hexagon::D1,  Hexagon::D8,  Hexagon::D9,  Hexagon::D10,
 505       Hexagon::D11, Hexagon::D12, Hexagon::D13, Hexagon::NoRegister
 506     };
 507
 508     const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 509
 510     for (unsigned i = 0; regsToMove[i] != Hexagon::NoRegister; ++i) {
 511       for (unsigned I = 0, E = CSI.size(); I < E; ++I) {
 512         if (CSI[I].getReg() == regsToMove[i]) {
 513           // Subtract 8 to make room for R30 and R31, which are added above.
 514           int64_t Offset = getFrameIndexOffset(MF, CSI[I].getFrameIdx()) - 8;
 515
 516           if (regsToMove[i] < Hexagon::D0 || regsToMove[i] > Hexagon::D15) {
 517             unsigned DwarfReg = HRI.getDwarfRegNum(regsToMove[i], true);
 518             unsigned CFIIndex = MMI.addFrameInst(
 519                                     MCCFIInstruction::createOffset(FrameLabel,
 520                                                         DwarfReg, Offset));
 521             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 522                    .addCFIIndex(CFIIndex);
 523           } else {
 524             // Split the double regs into subregs, and generate appropriate
 525             // cfi_offsets.
 526             // The only reason, we are split double regs is, llvm-mc does not
 527             // understand paired registers for cfi_offset.
 528             // Eg .cfi_offset r1:0, -64
 529             unsigned HiReg = getMax32BitSubRegister(regsToMove[i], HRI);
 530             unsigned LoReg = getMax32BitSubRegister(regsToMove[i], HRI, false);
 531             unsigned HiDwarfReg = HRI.getDwarfRegNum(HiReg, true);
 532             unsigned LoDwarfReg = HRI.getDwarfRegNum(LoReg, true);
 533             unsigned HiCFIIndex = MMI.addFrameInst(
 534                                     MCCFIInstruction::createOffset(FrameLabel,
 535                                                         HiDwarfReg, Offset+4));
 536             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 537                    .addCFIIndex(HiCFIIndex);
 538             unsigned LoCFIIndex = MMI.addFrameInst(
 539                                     MCCFIInstruction::createOffset(FrameLabel,
 540                                                         LoDwarfReg, Offset));
 541             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 542                    .addCFIIndex(LoCFIIndex);
 543           }
 544           break;
 545         }
 546       } // for CSI.size()
 547     } // for regsToMove
 548   } // needsFrameMoves
 549 }
 550
 551 void HexagonFrameLowering::insertEpilogueInBlock(MachineBasicBlock &MBB) const {
 552   MachineFunction &MF = *MBB.getParent();
 553   //
 554   // Only insert deallocframe if we need to.  Also at -O0.  See comment
 555   // in insertPrologueInBlock above.
 556   //
 557   if (!hasFP(MF) && MF.getTarget().getOptLevel() != CodeGenOpt::None)
 558     return;
 559
 560   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 561   auto &HII = *HST.getInstrInfo();
 562   auto &HRI = *HST.getRegisterInfo();
 563   unsigned SP = HRI.getStackRegister();
 564
 565   MachineInstr *RetI = nullptr;
 566   for (auto &I : MBB) {
 567     if (!I.isReturn())
 568       continue;
 569     RetI = &I;
 570     break;
 571   }
 572   unsigned RetOpc = RetI ? RetI->getOpcode() : 0;
 573
 574   MachineBasicBlock::iterator InsertPt = MBB.getFirstTerminator();
 575   DebugLoc DL;
 576   if (InsertPt != MBB.end())
 577     DL = InsertPt->getDebugLoc();
 578   else if (!MBB.empty())
 579     DL = std::prev(MBB.end())->getDebugLoc();
 580
 581   // Handle EH_RETURN.
 582   if (RetOpc == Hexagon::EH_RETURN_JMPR) {
 583     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 584     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::A2_add), SP)
 585         .addReg(SP)
 586         .addReg(Hexagon::R28);
 587     return;
 588   }
 589
 590   // Check for RESTORE_DEALLOC_RET* tail call. Don't emit an extra dealloc-
 591   // frame instruction if we encounter it.
 592   if (RetOpc == Hexagon::RESTORE_DEALLOC_RET_JMP_V4) {
 593     MachineBasicBlock::iterator It = RetI;
 594     ++It;
 595     // Delete all instructions after the RESTORE (except labels).
 596     while (It != MBB.end()) {
 597       if (!It->isLabel())
 598         It = MBB.erase(It);
 599       else
 600         ++It;
 601     }
 602     return;
 603   }
 604
 605   // It is possible that the restoring code is a call to a library function.
 606   // All of the restore* functions include "deallocframe", so we need to make
 607   // sure that we don't add an extra one.
 608   bool NeedsDeallocframe = true;
 609   if (!MBB.empty() && InsertPt != MBB.begin()) {
 610     MachineBasicBlock::iterator PrevIt = std::prev(InsertPt);
 611     unsigned COpc = PrevIt->getOpcode();
 612     if (COpc == Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4)
 613       NeedsDeallocframe = false;
 614   }
 615
 616   if (!NeedsDeallocframe)
 617     return;
 618   // If the returning instruction is JMPret, replace it with dealloc_return,
 619   // otherwise just add deallocframe. The function could be returning via a
 620   // tail call.
 621   if (RetOpc != Hexagon::JMPret || DisableDeallocRet) {
 622     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 623     return;
 624   }
 625   unsigned NewOpc = Hexagon::L4_return;
 626   MachineInstr *NewI = BuildMI(MBB, RetI, DL, HII.get(NewOpc));
 627   // Transfer the function live-out registers.
 628   NewI->copyImplicitOps(MF, RetI);
 629   MBB.erase(RetI);
 630 }
 631
 632
 633 bool HexagonFrameLowering::hasFP(const MachineFunction &MF) const {
 634   const MachineFrameInfo *MFI = MF.getFrameInfo();
 635   const HexagonMachineFunctionInfo *FuncInfo =
 636     MF.getInfo<HexagonMachineFunctionInfo>();
 637   return MFI->hasCalls() || MFI->getStackSize() > 0 ||
 638          FuncInfo->hasClobberLR();
 639 }
 640
 641
 642 enum SpillKind {
 643   SK_ToMem,
 644   SK_FromMem,
 645   SK_FromMemTailcall
 646 };
 647
 648 static const char *
 649 getSpillFunctionFor(unsigned MaxReg, SpillKind SpillType) {
 650   const char * V4SpillToMemoryFunctions[] = {
 651     "__save_r16_through_r17",
 652     "__save_r16_through_r19",
 653     "__save_r16_through_r21",
 654     "__save_r16_through_r23",
 655     "__save_r16_through_r25",
 656     "__save_r16_through_r27" };
 657
 658   const char * V4SpillFromMemoryFunctions[] = {
 659     "__restore_r16_through_r17_and_deallocframe",
 660     "__restore_r16_through_r19_and_deallocframe",
 661     "__restore_r16_through_r21_and_deallocframe",
 662     "__restore_r16_through_r23_and_deallocframe",
 663     "__restore_r16_through_r25_and_deallocframe",
 664     "__restore_r16_through_r27_and_deallocframe" };
 665
 666   const char * V4SpillFromMemoryTailcallFunctions[] = {
 667     "__restore_r16_through_r17_and_deallocframe_before_tailcall",
 668     "__restore_r16_through_r19_and_deallocframe_before_tailcall",
 669     "__restore_r16_through_r21_and_deallocframe_before_tailcall",
 670     "__restore_r16_through_r23_and_deallocframe_before_tailcall",
 671     "__restore_r16_through_r25_and_deallocframe_before_tailcall",
 672     "__restore_r16_through_r27_and_deallocframe_before_tailcall"
 673   };
 674
 675   const char **SpillFunc = nullptr;
 676
 677   switch(SpillType) {
 678   case SK_ToMem:
 679     SpillFunc = V4SpillToMemoryFunctions;
 680     break;
 681   case SK_FromMem:
 682     SpillFunc = V4SpillFromMemoryFunctions;
 683     break;
 684   case SK_FromMemTailcall:
 685     SpillFunc = V4SpillFromMemoryTailcallFunctions;
 686     break;
 687   }
 688   assert(SpillFunc && "Unknown spill kind");
 689
 690   // Spill all callee-saved registers up to the highest register used.
 691   switch (MaxReg) {
 692   case Hexagon::R17:
 693     return SpillFunc[0];
 694   case Hexagon::R19:
 695     return SpillFunc[1];
 696   case Hexagon::R21:
 697     return SpillFunc[2];
 698   case Hexagon::R23:
 699     return SpillFunc[3];
 700   case Hexagon::R25:
 701     return SpillFunc[4];
 702   case Hexagon::R27:
 703     return SpillFunc[5];
 704   default:
 705     llvm_unreachable("Unhandled maximum callee save register");
 706   }
 707   return 0;
 708 }
 709
 710 /// Adds all callee-saved registers up to MaxReg to the instruction.
 711 static void addCalleeSaveRegistersAsImpOperand(MachineInstr *Inst,
 712                                            unsigned MaxReg, bool IsDef) {
 713   // Add the callee-saved registers as implicit uses.
 714   for (unsigned R = Hexagon::R16; R <= MaxReg; ++R) {
 715     MachineOperand ImpUse = MachineOperand::CreateReg(R, IsDef, true);
 716     Inst->addOperand(ImpUse);
 717   }
 718 }
 719
 720
 721 int HexagonFrameLowering::getFrameIndexOffset(const MachineFunction &MF,
 722       int FI) const {
 723   return MF.getFrameInfo()->getObjectOffset(FI);
 724 }
 725
 726
 727 bool HexagonFrameLowering::insertCSRSpillsInBlock(MachineBasicBlock &MBB,
 728       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 729   if (CSI.empty())
 730     return true;
 731
 732   MachineBasicBlock::iterator MI = MBB.begin();
 733   MachineFunction &MF = *MBB.getParent();
 734   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 735
 736   if (useSpillFunction(MF, CSI)) {
 737     unsigned MaxReg = getMaxCalleeSavedReg(CSI, HRI);
 738     const char *SpillFun = getSpillFunctionFor(MaxReg, SK_ToMem);
 739     // Call spill function.
 740     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc() : DebugLoc();
 741     MachineInstr *SaveRegsCall =
 742         BuildMI(MBB, MI, DL, TII.get(Hexagon::SAVE_REGISTERS_CALL_V4))
 743           .addExternalSymbol(SpillFun);
 744     // Add callee-saved registers as use.
 745     addCalleeSaveRegistersAsImpOperand(SaveRegsCall, MaxReg, false);
 746     // Add live in registers.
 747     for (unsigned I = 0; I < CSI.size(); ++I)
 748       MBB.addLiveIn(CSI[I].getReg());
 749     return true;
 750   }
 751
 752   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
 753     unsigned Reg = CSI[i].getReg();
 754     // Add live in registers. We treat eh_return callee saved register r0 - r3
 755     // specially. They are not really callee saved registers as they are not
 756     // supposed to be killed.
 757     bool IsKill = !HRI.isEHReturnCalleeSaveReg(Reg);
 758     int FI = CSI[i].getFrameIdx();
 759     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 760     TII.storeRegToStackSlot(MBB, MI, Reg, IsKill, FI, RC, &HRI);
 761     if (IsKill)
 762       MBB.addLiveIn(Reg);
 763   }
 764   return true;
 765 }
 766
 767
 768 bool HexagonFrameLowering::insertCSRRestoresInBlock(MachineBasicBlock &MBB,
 769       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 770   if (CSI.empty())
 771     return false;
 772
 773   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 774   MachineFunction &MF = *MBB.getParent();
 775   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 776
 777   if (useRestoreFunction(MF, CSI)) {
 778     bool HasTC = hasTailCall(MBB) || !hasReturn(MBB);
 779     unsigned MaxR = getMaxCalleeSavedReg(CSI, HRI);
 780     SpillKind Kind = HasTC ? SK_FromMemTailcall : SK_FromMem;
 781     const char *RestoreFn = getSpillFunctionFor(MaxR, Kind);
 782
 783     // Call spill function.
 784     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc()
 785                                   : MBB.getLastNonDebugInstr()->getDebugLoc();
 786     MachineInstr *DeallocCall = nullptr;
 787
 788     if (HasTC) {
 789       unsigned ROpc = Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4;
 790       DeallocCall = BuildMI(MBB, MI, DL, TII.get(ROpc))
 791           .addExternalSymbol(RestoreFn);
 792     } else {
 793       // The block has a return.
 794       MachineBasicBlock::iterator It = MBB.getFirstTerminator();
 795       assert(It->isReturn() && std::next(It) == MBB.end());
 796       unsigned ROpc = Hexagon::RESTORE_DEALLOC_RET_JMP_V4;
 797       DeallocCall = BuildMI(MBB, It, DL, TII.get(ROpc))
 798           .addExternalSymbol(RestoreFn);
 799       // Transfer the function live-out registers.
 800       DeallocCall->copyImplicitOps(MF, It);
 801     }
 802     addCalleeSaveRegistersAsImpOperand(DeallocCall, MaxR, true);
 803     return true;
 804   }
 805
 806   for (unsigned i = 0; i < CSI.size(); ++i) {
 807     unsigned Reg = CSI[i].getReg();
 808     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 809     int FI = CSI[i].getFrameIdx();
 810     TII.loadRegFromStackSlot(MBB, MI, Reg, FI, RC, &HRI);
 811   }
 812   return true;
 813 }
 814
 815
 816 void HexagonFrameLowering::eliminateCallFramePseudoInstr(MachineFunction &MF,
 817       MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const {
 818   MachineInstr &MI = *I;
 819   unsigned Opc = MI.getOpcode();
 820   (void)Opc; // Silence compiler warning.
 821   assert((Opc == Hexagon::ADJCALLSTACKDOWN || Opc == Hexagon::ADJCALLSTACKUP) &&
 822          "Cannot handle this call frame pseudo instruction");
 823   MBB.erase(I);
 824 }
 825
 826
 827 void HexagonFrameLowering::processFunctionBeforeFrameFinalized(
 828     MachineFunction &MF, RegScavenger *RS) const {
 829   // If this function has uses aligned stack and also has variable sized stack
 830   // objects, then we need to map all spill slots to fixed positions, so that
 831   // they can be accessed through FP. Otherwise they would have to be accessed
 832   // via AP, which may not be available at the particular place in the program.
 833   MachineFrameInfo *MFI = MF.getFrameInfo();
 834   bool HasAlloca = MFI->hasVarSizedObjects();
 835   bool HasAligna = (MFI->getMaxAlignment() > getStackAlignment());
 836
 837   if (!HasAlloca || !HasAligna)
 838     return;
 839
 840   unsigned LFS = MFI->getLocalFrameSize();
 841   int Offset = -LFS;
 842   for (int i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
 843     if (!MFI->isSpillSlotObjectIndex(i) || MFI->isDeadObjectIndex(i))
 844       continue;
 845     int S = MFI->getObjectSize(i);
 846     LFS += S;
 847     Offset -= S;
 848     MFI->mapLocalFrameObject(i, Offset);
 849   }
 850
 851   MFI->setLocalFrameSize(LFS);
 852   unsigned A = MFI->getLocalFrameMaxAlign();
 853   assert(A <= 8 && "Unexpected local frame alignment");
 854   if (A == 0)
 855     MFI->setLocalFrameMaxAlign(8);
 856   MFI->setUseLocalStackAllocationBlock(true);
 857 }
 858
 859 /// Returns true if there is no caller saved registers available.
 860 static bool needToReserveScavengingSpillSlots(MachineFunction &MF,
 861                                               const HexagonRegisterInfo &HRI) {
 862   MachineRegisterInfo &MRI = MF.getRegInfo();
 863   const MCPhysReg *CallerSavedRegs = HRI.getCallerSavedRegs(&MF);
 864   // Check for an unused caller-saved register.
 865   for ( ; *CallerSavedRegs; ++CallerSavedRegs) {
 866     MCPhysReg FreeReg = *CallerSavedRegs;
 867     if (MRI.isPhysRegUsed(FreeReg))
 868       continue;
 869
 870     // Check aliased register usage.
 871     bool IsCurrentRegUsed = false;
 872     for (MCRegAliasIterator AI(FreeReg, &HRI, false); AI.isValid(); ++AI)
 873       if (MRI.isPhysRegUsed(*AI)) {
 874         IsCurrentRegUsed = true;
 875         break;
 876       }
 877     if (IsCurrentRegUsed)
 878       continue;
 879
 880     // Neither directly used nor used through an aliased register.
 881     return false;
 882   }
 883   // All caller-saved registers are used.
 884   return true;
 885 }
 886
 887
 888 /// Replaces the predicate spill code pseudo instructions by valid instructions.
 889 bool HexagonFrameLowering::replacePredRegPseudoSpillCode(MachineFunction &MF)
 890       const {
 891   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 892   auto &HII = *HST.getInstrInfo();
 893   MachineRegisterInfo &MRI = MF.getRegInfo();
 894   bool HasReplacedPseudoInst = false;
 895   // Replace predicate spill pseudo instructions by real code.
 896   // Loop over all of the basic blocks.
 897   for (MachineFunction::iterator MBBb = MF.begin(), MBBe = MF.end();
 898        MBBb != MBBe; ++MBBb) {
 899     MachineBasicBlock* MBB = MBBb;
 900     // Traverse the basic block.
 901     MachineBasicBlock::iterator NextII;
 902     for (MachineBasicBlock::iterator MII = MBB->begin(); MII != MBB->end();
 903          MII = NextII) {
 904       MachineInstr *MI = MII;
 905       NextII = std::next(MII);
 906       int Opc = MI->getOpcode();
 907       if (Opc == Hexagon::STriw_pred) {
 908         HasReplacedPseudoInst = true;
 909         // STriw_pred FI, 0, SrcReg;
 910         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 911         unsigned SrcReg = MI->getOperand(2).getReg();
 912         bool IsOrigSrcRegKilled = MI->getOperand(2).isKill();
 913
 914         assert(MI->getOperand(0).isFI() && "Expect a frame index");
 915         assert(Hexagon::PredRegsRegClass.contains(SrcReg) &&
 916                "Not a predicate register");
 917
 918         // Insert transfer to general purpose register.
 919         //   VirtReg = C2_tfrpr SrcPredReg
 920         BuildMI(*MBB, MII, MI->getDebugLoc(), HII.get(Hexagon::C2_tfrpr),
 921                 VirtReg).addReg(SrcReg, getKillRegState(IsOrigSrcRegKilled));
 922
 923         // Change instruction to S2_storeri_io.
 924         //   S2_storeri_io FI, 0, VirtReg
 925         MI->setDesc(HII.get(Hexagon::S2_storeri_io));
 926         MI->getOperand(2).setReg(VirtReg);
 927         MI->getOperand(2).setIsKill();
 928
 929       } else if (Opc == Hexagon::LDriw_pred) {
 930         // DstReg = LDriw_pred FI, 0
 931         MachineOperand &M0 = MI->getOperand(0);
 932         if (M0.isDead()) {
 933           MBB->erase(MII);
 934           continue;
 935         }
 936
 937         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 938         unsigned DestReg = MI->getOperand(0).getReg();
 939
 940         assert(MI->getOperand(1).isFI() && "Expect a frame index");
 941         assert(Hexagon::PredRegsRegClass.contains(DestReg) &&
 942                "Not a predicate register");
 943
 944         // Change instruction to L2_loadri_io.
 945         //   VirtReg = L2_loadri_io FI, 0
 946         MI->setDesc(HII.get(Hexagon::L2_loadri_io));
 947         MI->getOperand(0).setReg(VirtReg);
 948
 949         // Insert transfer to general purpose register.
 950         //   DestReg = C2_tfrrp VirtReg
 951         const MCInstrDesc &D = HII.get(Hexagon::C2_tfrrp);
 952         BuildMI(*MBB, std::next(MII), MI->getDebugLoc(), D, DestReg)
 953           .addReg(VirtReg, getKillRegState(true));
 954         HasReplacedPseudoInst = true;
 955       }
 956     }
 957   }
 958   return HasReplacedPseudoInst;
 959 }
 960
 961
 962 void HexagonFrameLowering::processFunctionBeforeCalleeSavedScan(
 963       MachineFunction &MF, RegScavenger* RS) const {
 964   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 965   auto &HRI = *HST.getRegisterInfo();
 966
 967   bool HasEHReturn = MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn();
 968
 969   // If we have a function containing __builtin_eh_return we want to spill and
 970   // restore all callee saved registers. Pretend that they are used.
 971   if (HasEHReturn) {
 972     MachineRegisterInfo &MRI = MF.getRegInfo();
 973     for (const MCPhysReg *CSRegs = HRI.getCalleeSavedRegs(&MF); *CSRegs;
 974          ++CSRegs)
 975       if (!MRI.isPhysRegUsed(*CSRegs))
 976         MRI.setPhysRegUsed(*CSRegs);
 977   }
 978
 979   const TargetRegisterClass &RC = Hexagon::IntRegsRegClass;
 980
 981   // Replace predicate register pseudo spill code.
 982   bool HasReplacedPseudoInst = replacePredRegPseudoSpillCode(MF);
 983
 984   // We need to reserve a a spill slot if scavenging could potentially require
 985   // spilling a scavenged register.
 986   if (HasReplacedPseudoInst && needToReserveScavengingSpillSlots(MF, HRI)) {
 987     MachineFrameInfo *MFI = MF.getFrameInfo();
 988     for (int i=0; i < NumberScavengerSlots; i++)
 989       RS->addScavengingFrameIndex(
 990         MFI->CreateSpillStackObject(RC.getSize(), RC.getAlignment()));
 991   }
 992 }
 993
 994
 995 #ifndef NDEBUG
 996 static void dump_registers(BitVector &Regs, const TargetRegisterInfo &TRI) {
 997   dbgs() << '{';
 998   for (int x = Regs.find_first(); x >= 0; x = Regs.find_next(x)) {
 999     unsigned R = x;
1000     dbgs() << ' ' << PrintReg(R, &TRI);
1001   }
1002   dbgs() << " }";
1003 }
1004 #endif
1005
1006
1007 bool HexagonFrameLowering::assignCalleeSavedSpillSlots(MachineFunction &MF,
1008       const TargetRegisterInfo *TRI, std::vector<CalleeSavedInfo> &CSI) const {
1009   DEBUG(dbgs() << LLVM_FUNCTION_NAME << " on "
1010                << MF.getFunction()->getName() << '\n');
1011   MachineFrameInfo *MFI = MF.getFrameInfo();
1012   BitVector SRegs(Hexagon::NUM_TARGET_REGS);
1013
1014   // Generate a set of unique, callee-saved registers (SRegs), where each
1015   // register in the set is maximal in terms of sub-/super-register relation,
1016   // i.e. for each R in SRegs, no proper super-register of R is also in SRegs.
1017
1018   // (1) For each callee-saved register, add that register and all of its
1019   // sub-registers to SRegs.
1020   DEBUG(dbgs() << "Initial CS registers: {");
1021   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1022     unsigned R = CSI[i].getReg();
1023     DEBUG(dbgs() << ' ' << PrintReg(R, TRI));
1024     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1025       SRegs[*SR] = true;
1026   }
1027   DEBUG(dbgs() << " }\n");
1028   DEBUG(dbgs() << "SRegs.1: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1029
1030   // (2) For each reserved register, remove that register and all of its
1031   // sub- and super-registers from SRegs.
1032   BitVector Reserved = TRI->getReservedRegs(MF);
1033   for (int x = Reserved.find_first(); x >= 0; x = Reserved.find_next(x)) {
1034     unsigned R = x;
1035     for (MCSuperRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1036       SRegs[*SR] = false;
1037   }
1038   DEBUG(dbgs() << "Res:     "; dump_registers(Reserved, *TRI); dbgs() << "\n");
1039   DEBUG(dbgs() << "SRegs.2: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1040
1041   // (3) Collect all registers that have at least one sub-register in SRegs,
1042   // and also have no sub-registers that are reserved. These will be the can-
1043   // didates for saving as a whole instead of their individual sub-registers.
1044   // (Saving R17:16 instead of R16 is fine, but only if R17 was not reserved.)
1045   BitVector TmpSup(Hexagon::NUM_TARGET_REGS);
1046   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1047     unsigned R = x;
1048     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR)
1049       TmpSup[*SR] = true;
1050   }
1051   for (int x = TmpSup.find_first(); x >= 0; x = TmpSup.find_next(x)) {
1052     unsigned R = x;
1053     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR) {
1054       if (!Reserved[*SR])
1055         continue;
1056       TmpSup[R] = false;
1057       break;
1058     }
1059   }
1060   DEBUG(dbgs() << "TmpSup:  "; dump_registers(TmpSup, *TRI); dbgs() << "\n");
1061
1062   // (4) Include all super-registers found in (3) into SRegs.
1063   SRegs |= TmpSup;
1064   DEBUG(dbgs() << "SRegs.4: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1065
1066   // (5) For each register R in SRegs, if any super-register of R is in SRegs,
1067   // remove R from SRegs.
1068   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1069     unsigned R = x;
1070     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR) {
1071       if (!SRegs[*SR])
1072         continue;
1073       SRegs[R] = false;
1074       break;
1075     }
1076   }
1077   DEBUG(dbgs() << "SRegs.5: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1078
1079   // Now, for each register that has a fixed stack slot, create the stack
1080   // object for it.
1081   CSI.clear();
1082
1083   typedef TargetFrameLowering::SpillSlot SpillSlot;
1084   unsigned NumFixed;
1085   int MinOffset = 0;  // CS offsets are negative.
1086   const SpillSlot *FixedSlots = getCalleeSavedSpillSlots(NumFixed);
1087   for (const SpillSlot *S = FixedSlots; S != FixedSlots+NumFixed; ++S) {
1088     if (!SRegs[S->Reg])
1089       continue;
1090     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(S->Reg);
1091     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), S->Offset);
1092     MinOffset = std::min(MinOffset, S->Offset);
1093     CSI.push_back(CalleeSavedInfo(S->Reg, FI));
1094     SRegs[S->Reg] = false;
1095   }
1096
1097   // There can be some registers that don't have fixed slots. For example,
1098   // we need to store R0-R3 in functions with exception handling. For each
1099   // such register, create a non-fixed stack object.
1100   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1101     unsigned R = x;
1102     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(R);
1103     int Off = MinOffset - RC->getSize();
1104     unsigned Align = std::min(RC->getAlignment(), getStackAlignment());
1105     assert(isPowerOf2_32(Align));
1106     Off &= -Align;
1107     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), Off);
1108     MinOffset = std::min(MinOffset, Off);
1109     CSI.push_back(CalleeSavedInfo(R, FI));
1110     SRegs[R] = false;
1111   }
1112
1113   DEBUG({
1114     dbgs() << "CS information: {";
1115     for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1116       int FI = CSI[i].getFrameIdx();
1117       int Off = MFI->getObjectOffset(FI);
1118       dbgs() << ' ' << PrintReg(CSI[i].getReg(), TRI) << ":fi#" << FI << ":sp";
1119       if (Off >= 0)
1120         dbgs() << '+';
1121       dbgs() << Off;
1122     }
1123     dbgs() << " }\n";
1124   });
1125
1126 #ifndef NDEBUG
1127   // Verify that all registers were handled.
1128   bool MissedReg = false;
1129   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1130     unsigned R = x;
1131     dbgs() << PrintReg(R, TRI) << ' ';
1132     MissedReg = true;
1133   }
1134   if (MissedReg)
1135     llvm_unreachable("...there are unhandled callee-saved registers!");
1136 #endif
1137
1138   return true;
1139 }
1140
1141
1142 void HexagonFrameLowering::expandAlloca(MachineInstr *AI,
1143       const HexagonInstrInfo &HII, unsigned SP, unsigned CF) const {
1144   MachineBasicBlock &MB = *AI->getParent();
1145   DebugLoc DL = AI->getDebugLoc();
1146   unsigned A = AI->getOperand(2).getImm();
1147
1148   // Have
1149   //    Rd  = alloca Rs, #A
1150   //
1151   // If Rs and Rd are different registers, use this sequence:
1152   //    Rd  = sub(r29, Rs)
1153   //    r29 = sub(r29, Rs)
1154   //    Rd  = and(Rd, #-A)    ; if necessary
1155   //    r29 = and(r29, #-A)   ; if necessary
1156   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1157   // otherwise, do
1158   //    Rd  = sub(r29, Rs)
1159   //    Rd  = and(Rd, #-A)    ; if necessary
1160   //    r29 = Rd
1161   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1162
1163   MachineOperand &RdOp = AI->getOperand(0);
1164   MachineOperand &RsOp = AI->getOperand(1);
1165   unsigned Rd = RdOp.getReg(), Rs = RsOp.getReg();
1166
1167   // Rd = sub(r29, Rs)
1168   BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), Rd)
1169       .addReg(SP)
1170       .addReg(Rs);
1171   if (Rs != Rd) {
1172     // r29 = sub(r29, Rs)
1173     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), SP)
1174         .addReg(SP)
1175         .addReg(Rs);
1176   }
1177   if (A > 8) {
1178     // Rd  = and(Rd, #-A)
1179     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), Rd)
1180         .addReg(Rd)
1181         .addImm(-int64_t(A));
1182     if (Rs != Rd)
1183       BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), SP)
1184           .addReg(SP)
1185           .addImm(-int64_t(A));
1186   }
1187   if (Rs == Rd) {
1188     // r29 = Rd
1189     BuildMI(MB, AI, DL, HII.get(TargetOpcode::COPY), SP)
1190         .addReg(Rd);
1191   }
1192   if (CF > 0) {
1193     // Rd = add(Rd, #CF)
1194     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_addi), Rd)
1195         .addReg(Rd)
1196         .addImm(CF);
1197   }
1198 }
1199
1200
1201 bool HexagonFrameLowering::needsAligna(const MachineFunction &MF) const {
1202   const MachineFrameInfo *MFI = MF.getFrameInfo();
1203   if (!MFI->hasVarSizedObjects())
1204     return false;
1205   unsigned MaxA = MFI->getMaxAlignment();
1206   if (MaxA <= getStackAlignment())
1207     return false;
1208   return true;
1209 }
1210
1211
1212 MachineInstr *HexagonFrameLowering::getAlignaInstr(MachineFunction &MF) const {
1213   for (auto &B : MF)
1214     for (auto &I : B)
1215       if (I.getOpcode() == Hexagon::ALIGNA)
1216         return &I;
1217   return nullptr;
1218 }
1219
1220
1221 inline static bool isOptSize(const MachineFunction &MF) {
1222   AttributeSet AF = MF.getFunction()->getAttributes();
1223   return AF.hasAttribute(AttributeSet::FunctionIndex,
1224                          Attribute::OptimizeForSize);
1225 }
1226
1227 inline static bool isMinSize(const MachineFunction &MF) {
1228   AttributeSet AF = MF.getFunction()->getAttributes();
1229   return AF.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);
1230 }
1231
1232
1233 /// Determine whether the callee-saved register saves and restores should
1234 /// be generated via inline code. If this function returns "true", inline
1235 /// code will be generated. If this function returns "false", additional
1236 /// checks are performed, which may still lead to the inline code.
1237 bool HexagonFrameLowering::shouldInlineCSR(MachineFunction &MF,
1238       const CSIVect &CSI) const {
1239   if (MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn())
1240     return true;
1241   if (!isOptSize(MF) && !isMinSize(MF))
1242     if (MF.getTarget().getOptLevel() > CodeGenOpt::Default)
1243       return true;
1244
1245   // Check if CSI only has double registers, and if the registers form
1246   // a contiguous block starting from D8.
1247   BitVector Regs(Hexagon::NUM_TARGET_REGS);
1248   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1249     unsigned R = CSI[i].getReg();
1250     if (!Hexagon::DoubleRegsRegClass.contains(R))
1251       return true;
1252     Regs[R] = true;
1253   }
1254   int F = Regs.find_first();
1255   if (F != Hexagon::D8)
1256     return true;
1257   while (F >= 0) {
1258     int N = Regs.find_next(F);
1259     if (N >= 0 && N != F+1)
1260       return true;
1261     F = N;
1262   }
1263
1264   return false;
1265 }
1266
1267
1268 bool HexagonFrameLowering::useSpillFunction(MachineFunction &MF,
1269       const CSIVect &CSI) const {
1270   if (shouldInlineCSR(MF, CSI))
1271     return false;
1272   unsigned NumCSI = CSI.size();
1273   if (NumCSI <= 1)
1274     return false;
1275
1276   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs
1277                                      : SpillFuncThreshold;
1278   return Threshold < NumCSI;
1279 }
1280
1281
1282 bool HexagonFrameLowering::useRestoreFunction(MachineFunction &MF,
1283       const CSIVect &CSI) const {
1284   if (shouldInlineCSR(MF, CSI))
1285     return false;
1286   unsigned NumCSI = CSI.size();
1287   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs-1
1288                                      : SpillFuncThreshold;
1289   return Threshold < NumCSI;
1290 }
1291