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 (ConstMIOperands Mo(MI); Mo.isValid(); ++Mo) {
 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 }
 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
 348 /// Perform most of the PEI work here:
 349 /// - saving/restoring of the callee-saved registers,
 350 /// - stack frame creation and destruction.
 351 /// Normally, this work is distributed among various functions, but doing it
 352 /// in one place allows shrink-wrapping of the stack frame.
 353 void HexagonFrameLowering::emitPrologue(MachineFunction &MF) const {
 354   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 355   auto &HRI = *HST.getRegisterInfo();
 356
 357   MachineFrameInfo *MFI = MF.getFrameInfo();
 358   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 359
 360   MachineBasicBlock *PrologB = &MF.front(), *EpilogB = nullptr;
 361   if (EnableShrinkWrapping)
 362     findShrunkPrologEpilog(MF, PrologB, EpilogB);
 363
 364   insertCSRSpillsInBlock(*PrologB, CSI, HRI);
 365   insertPrologueInBlock(*PrologB);
 366
 367   if (EpilogB) {
 368     insertCSRRestoresInBlock(*EpilogB, CSI, HRI);
 369     insertEpilogueInBlock(*EpilogB);
 370   } else {
 371     for (auto &B : MF)
 372       if (!B.empty() && B.back().isReturn())
 373         insertCSRRestoresInBlock(B, CSI, HRI);
 374
 375     for (auto &B : MF)
 376       if (!B.empty() && B.back().isReturn())
 377         insertEpilogueInBlock(B);
 378   }
 379 }
 380
 381
 382 void HexagonFrameLowering::insertPrologueInBlock(MachineBasicBlock &MBB) const {
 383   MachineFunction &MF = *MBB.getParent();
 384   MachineFrameInfo *MFI = MF.getFrameInfo();
 385   MachineModuleInfo &MMI = MF.getMMI();
 386   MachineBasicBlock::iterator MBBI = MBB.begin();
 387   auto &HTM = static_cast<const HexagonTargetMachine&>(MF.getTarget());
 388   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 389   auto &HII = *HST.getInstrInfo();
 390   auto &HRI = *HST.getRegisterInfo();
 391   DebugLoc dl;
 392
 393   unsigned MaxAlign = std::max(MFI->getMaxAlignment(), getStackAlignment());
 394
 395   // Calculate the total stack frame size.
 396   // Get the number of bytes to allocate from the FrameInfo.
 397   unsigned FrameSize = MFI->getStackSize();
 398   // Round up the max call frame size to the max alignment on the stack.
 399   unsigned MaxCFA = RoundUpToAlignment(MFI->getMaxCallFrameSize(), MaxAlign);
 400   MFI->setMaxCallFrameSize(MaxCFA);
 401
 402   FrameSize = MaxCFA + RoundUpToAlignment(FrameSize, MaxAlign);
 403   MFI->setStackSize(FrameSize);
 404
 405   bool AlignStack = (MaxAlign > getStackAlignment());
 406
 407   // Check if frame moves are needed for EH.
 408   bool needsFrameMoves = MMI.hasDebugInfo() ||
 409     MF.getFunction()->needsUnwindTableEntry();
 410
 411   // Get the number of bytes to allocate from the FrameInfo.
 412   unsigned NumBytes = MFI->getStackSize();
 413   unsigned SP = HRI.getStackRegister();
 414   unsigned MaxCF = MFI->getMaxCallFrameSize();
 415   MachineBasicBlock::iterator InsertPt = MBB.begin();
 416
 417   auto *FuncInfo = MF.getInfo<HexagonMachineFunctionInfo>();
 418   auto &AdjustRegs = FuncInfo->getAllocaAdjustInsts();
 419
 420   for (auto MI : AdjustRegs) {
 421     assert((MI->getOpcode() == Hexagon::ALLOCA) && "Expected alloca");
 422     expandAlloca(MI, HII, SP, MaxCF);
 423     MI->eraseFromParent();
 424   }
 425
 426   //
 427   // Only insert ALLOCFRAME if we need to or at -O0 for the debugger.  Think
 428   // that this shouldn't be required, but doing so now because gcc does and
 429   // gdb can't break at the start of the function without it.  Will remove if
 430   // this turns out to be a gdb bug.
 431   //
 432   bool NoOpt = (HTM.getOptLevel() == CodeGenOpt::None);
 433   if (!NoOpt && !FuncInfo->hasClobberLR() && !hasFP(MF))
 434     return;
 435
 436   // Check for overflow.
 437   // Hexagon_TODO: Ugh! hardcoding. Is there an API that can be used?
 438   const unsigned int ALLOCFRAME_MAX = 16384;
 439
 440   // Create a dummy memory operand to avoid allocframe from being treated as
 441   // a volatile memory reference.
 442   MachineMemOperand *MMO =
 443     MF.getMachineMemOperand(MachinePointerInfo(), MachineMemOperand::MOStore,
 444                             4, 4);
 445
 446   if (NumBytes >= ALLOCFRAME_MAX) {
 447     // Emit allocframe(#0).
 448     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::S2_allocframe))
 449       .addImm(0)
 450       .addMemOperand(MMO);
 451
 452     // Subtract offset from frame pointer.
 453     // We use a caller-saved non-parameter register for that.
 454     unsigned CallerSavedReg = HRI.getFirstCallerSavedNonParamReg();
 455     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::CONST32_Int_Real),
 456             CallerSavedReg).addImm(NumBytes);
 457     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::A2_sub), SP)
 458       .addReg(SP)
 459       .addReg(CallerSavedReg);
 460   } else {
 461     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::S2_allocframe))
 462       .addImm(NumBytes)
 463       .addMemOperand(MMO);
 464   }
 465
 466   if (AlignStack) {
 467     BuildMI(MBB, InsertPt, dl, HII.get(Hexagon::A2_andir), SP)
 468         .addReg(SP)
 469         .addImm(-int64_t(MaxAlign));
 470   }
 471
 472   if (needsFrameMoves) {
 473     std::vector<MCCFIInstruction> Instructions = MMI.getFrameInstructions();
 474     MCSymbol *FrameLabel = MMI.getContext().CreateTempSymbol();
 475
 476     // Advance CFA. DW_CFA_def_cfa
 477     unsigned DwFPReg = HRI.getDwarfRegNum(HRI.getFrameRegister(), true);
 478     unsigned DwRAReg = HRI.getDwarfRegNum(HRI.getRARegister(), true);
 479
 480     // CFA = FP + 8
 481     unsigned CFIIndex = MMI.addFrameInst(MCCFIInstruction::createDefCfa(
 482                                                FrameLabel, DwFPReg, -8));
 483     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 484            .addCFIIndex(CFIIndex);
 485
 486     // R31 (return addr) = CFA - #4
 487     CFIIndex = MMI.addFrameInst(MCCFIInstruction::createOffset(
 488                                                FrameLabel, DwRAReg, -4));
 489     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 490            .addCFIIndex(CFIIndex);
 491
 492     // R30 (frame ptr) = CFA - #8)
 493     CFIIndex = MMI.addFrameInst(MCCFIInstruction::createOffset(
 494                                                FrameLabel, DwFPReg, -8));
 495     BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 496            .addCFIIndex(CFIIndex);
 497
 498     unsigned int regsToMove[] = {
 499       Hexagon::R1,  Hexagon::R0,  Hexagon::R3,  Hexagon::R2,
 500       Hexagon::R17, Hexagon::R16, Hexagon::R19, Hexagon::R18,
 501       Hexagon::R21, Hexagon::R20, Hexagon::R23, Hexagon::R22,
 502       Hexagon::R25, Hexagon::R24, Hexagon::R27, Hexagon::R26,
 503       Hexagon::D0,  Hexagon::D1,  Hexagon::D8,  Hexagon::D9,  Hexagon::D10,
 504       Hexagon::D11, Hexagon::D12, Hexagon::D13, Hexagon::NoRegister
 505     };
 506
 507     const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 508
 509     for (unsigned i = 0; regsToMove[i] != Hexagon::NoRegister; ++i) {
 510       for (unsigned I = 0, E = CSI.size(); I < E; ++I) {
 511         if (CSI[I].getReg() == regsToMove[i]) {
 512           // Subtract 8 to make room for R30 and R31, which are added above.
 513           int64_t Offset = getFrameIndexOffset(MF, CSI[I].getFrameIdx()) - 8;
 514
 515           if (regsToMove[i] < Hexagon::D0 || regsToMove[i] > Hexagon::D15) {
 516             unsigned DwarfReg = HRI.getDwarfRegNum(regsToMove[i], true);
 517             unsigned CFIIndex = MMI.addFrameInst(
 518                                     MCCFIInstruction::createOffset(FrameLabel,
 519                                                         DwarfReg, Offset));
 520             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 521                    .addCFIIndex(CFIIndex);
 522           } else {
 523             // Split the double regs into subregs, and generate appropriate
 524             // cfi_offsets.
 525             // The only reason, we are split double regs is, llvm-mc does not
 526             // understand paired registers for cfi_offset.
 527             // Eg .cfi_offset r1:0, -64
 528             unsigned HiReg = getMax32BitSubRegister(regsToMove[i], HRI);
 529             unsigned LoReg = getMax32BitSubRegister(regsToMove[i], HRI, false);
 530             unsigned HiDwarfReg = HRI.getDwarfRegNum(HiReg, true);
 531             unsigned LoDwarfReg = HRI.getDwarfRegNum(LoReg, true);
 532             unsigned HiCFIIndex = MMI.addFrameInst(
 533                                     MCCFIInstruction::createOffset(FrameLabel,
 534                                                         HiDwarfReg, Offset+4));
 535             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 536                    .addCFIIndex(HiCFIIndex);
 537             unsigned LoCFIIndex = MMI.addFrameInst(
 538                                     MCCFIInstruction::createOffset(FrameLabel,
 539                                                         LoDwarfReg, Offset));
 540             BuildMI(MBB, MBBI, dl, HII.get(TargetOpcode::CFI_INSTRUCTION))
 541                    .addCFIIndex(LoCFIIndex);
 542           }
 543           break;
 544         }
 545       } // for CSI.size()
 546     } // for regsToMove
 547   } // needsFrameMoves
 548 }
 549
 550 void HexagonFrameLowering::insertEpilogueInBlock(MachineBasicBlock &MBB) const {
 551   MachineFunction &MF = *MBB.getParent();
 552   //
 553   // Only insert deallocframe if we need to.  Also at -O0.  See comment
 554   // in insertPrologueInBlock above.
 555   //
 556   if (!hasFP(MF) && MF.getTarget().getOptLevel() != CodeGenOpt::None)
 557     return;
 558
 559   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 560   auto &HII = *HST.getInstrInfo();
 561   auto &HRI = *HST.getRegisterInfo();
 562   unsigned SP = HRI.getStackRegister();
 563
 564   MachineInstr *RetI = nullptr;
 565   for (auto &I : MBB) {
 566     if (!I.isReturn())
 567       continue;
 568     RetI = &I;
 569     break;
 570   }
 571   unsigned RetOpc = RetI ? RetI->getOpcode() : 0;
 572
 573   MachineBasicBlock::iterator InsertPt = MBB.getFirstTerminator();
 574   DebugLoc DL;
 575   if (InsertPt != MBB.end())
 576     DL = InsertPt->getDebugLoc();
 577   else if (!MBB.empty())
 578     DL = std::prev(MBB.end())->getDebugLoc();
 579
 580   // Handle EH_RETURN.
 581   if (RetOpc == Hexagon::EH_RETURN_JMPR) {
 582     MachineOperand &OffsetReg  = RetI->getOperand(0);
 583     (void)OffsetReg; // Silence compiler warning.
 584     assert(OffsetReg.isReg() && "Offset should be in register!");
 585     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 586     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::A2_add), SP)
 587         .addReg(SP)
 588         .addReg(Hexagon::R28);
 589     return;
 590   }
 591
 592   // Check for RESTORE_DEALLOC_RET* tail call. Don't emit an extra dealloc-
 593   // frame instruction if we encounter it.
 594   if (RetOpc == Hexagon::RESTORE_DEALLOC_RET_JMP_V4) {
 595     MachineBasicBlock::iterator It = RetI;
 596     ++It;
 597     // Delete all instructions after the RESTORE (except labels).
 598     while (It != MBB.end()) {
 599       if (!It->isLabel())
 600         It = MBB.erase(It);
 601       else
 602         ++It;
 603     }
 604     return;
 605   }
 606
 607   // It is possible that the restoring code is a call to a library function.
 608   // All of the restore* functions include "deallocframe", so we need to make
 609   // sure that we don't add an extra one.
 610   bool NeedsDeallocframe = true;
 611   if (!MBB.empty() && InsertPt != MBB.begin()) {
 612     MachineBasicBlock::iterator PrevIt = std::prev(InsertPt);
 613     unsigned COpc = PrevIt->getOpcode();
 614     if (COpc == Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4)
 615       NeedsDeallocframe = false;
 616   }
 617
 618   if (!NeedsDeallocframe)
 619     return;
 620   // If the returning instruction is JMPret, replace it with dealloc_return,
 621   // otherwise just add deallocframe. The function could be returning via a
 622   // tail call.
 623   if (RetOpc != Hexagon::JMPret || DisableDeallocRet) {
 624     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 625     return;
 626   }
 627   unsigned NewOpc = Hexagon::L4_return;
 628   MachineInstr *NewI = BuildMI(MBB, RetI, DL, HII.get(NewOpc));
 629   // Transfer the function live-out registers.
 630   NewI->copyImplicitOps(MF, RetI);
 631   MBB.erase(RetI);
 632 }
 633
 634
 635 bool HexagonFrameLowering::hasFP(const MachineFunction &MF) const {
 636   const MachineFrameInfo *MFI = MF.getFrameInfo();
 637   const HexagonMachineFunctionInfo *FuncInfo =
 638     MF.getInfo<HexagonMachineFunctionInfo>();
 639   return MFI->hasCalls() || MFI->getStackSize() > 0 ||
 640          FuncInfo->hasClobberLR();
 641 }
 642
 643
 644 enum SpillKind {
 645   SK_ToMem,
 646   SK_FromMem,
 647   SK_FromMemTailcall
 648 };
 649
 650 static const char *
 651 getSpillFunctionFor(unsigned MaxReg, SpillKind SpillType) {
 652   const char * V4SpillToMemoryFunctions[] = {
 653     "__save_r16_through_r17",
 654     "__save_r16_through_r19",
 655     "__save_r16_through_r21",
 656     "__save_r16_through_r23",
 657     "__save_r16_through_r25",
 658     "__save_r16_through_r27" };
 659
 660   const char * V4SpillFromMemoryFunctions[] = {
 661     "__restore_r16_through_r17_and_deallocframe",
 662     "__restore_r16_through_r19_and_deallocframe",
 663     "__restore_r16_through_r21_and_deallocframe",
 664     "__restore_r16_through_r23_and_deallocframe",
 665     "__restore_r16_through_r25_and_deallocframe",
 666     "__restore_r16_through_r27_and_deallocframe" };
 667
 668   const char * V4SpillFromMemoryTailcallFunctions[] = {
 669     "__restore_r16_through_r17_and_deallocframe_before_tailcall",
 670     "__restore_r16_through_r19_and_deallocframe_before_tailcall",
 671     "__restore_r16_through_r21_and_deallocframe_before_tailcall",
 672     "__restore_r16_through_r23_and_deallocframe_before_tailcall",
 673     "__restore_r16_through_r25_and_deallocframe_before_tailcall",
 674     "__restore_r16_through_r27_and_deallocframe_before_tailcall"
 675   };
 676
 677   const char **SpillFunc = nullptr;
 678
 679   switch(SpillType) {
 680   case SK_ToMem:
 681     SpillFunc = V4SpillToMemoryFunctions;
 682     break;
 683   case SK_FromMem:
 684     SpillFunc = V4SpillFromMemoryFunctions;
 685     break;
 686   case SK_FromMemTailcall:
 687     SpillFunc = V4SpillFromMemoryTailcallFunctions;
 688     break;
 689   }
 690   assert(SpillFunc && "Unknown spill kind");
 691
 692   // Spill all callee-saved registers up to the highest register used.
 693   switch (MaxReg) {
 694   case Hexagon::R17:
 695     return SpillFunc[0];
 696   case Hexagon::R19:
 697     return SpillFunc[1];
 698   case Hexagon::R21:
 699     return SpillFunc[2];
 700   case Hexagon::R23:
 701     return SpillFunc[3];
 702   case Hexagon::R25:
 703     return SpillFunc[4];
 704   case Hexagon::R27:
 705     return SpillFunc[5];
 706   default:
 707     llvm_unreachable("Unhandled maximum callee save register");
 708   }
 709   return 0;
 710 }
 711
 712 /// Adds all callee-saved registers up to MaxReg to the instruction.
 713 static void addCalleeSaveRegistersAsImpOperand(MachineInstr *Inst,
 714                                            unsigned MaxReg, bool IsDef) {
 715   // Add the callee-saved registers as implicit uses.
 716   for (unsigned R = Hexagon::R16; R <= MaxReg; ++R) {
 717     MachineOperand ImpUse = MachineOperand::CreateReg(R, IsDef, true);
 718     Inst->addOperand(ImpUse);
 719   }
 720 }
 721
 722
 723 int HexagonFrameLowering::getFrameIndexOffset(const MachineFunction &MF,
 724       int FI) const {
 725   return MF.getFrameInfo()->getObjectOffset(FI);
 726 }
 727
 728
 729 bool HexagonFrameLowering::insertCSRSpillsInBlock(MachineBasicBlock &MBB,
 730       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 731   if (CSI.empty())
 732     return true;
 733
 734   MachineBasicBlock::iterator MI = MBB.begin();
 735   MachineFunction &MF = *MBB.getParent();
 736   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 737
 738   if (useSpillFunction(MF, CSI)) {
 739     unsigned MaxReg = getMaxCalleeSavedReg(CSI, HRI);
 740     const char *SpillFun = getSpillFunctionFor(MaxReg, SK_ToMem);
 741     // Call spill function.
 742     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc() : DebugLoc();
 743     MachineInstr *SaveRegsCall =
 744         BuildMI(MBB, MI, DL, TII.get(Hexagon::SAVE_REGISTERS_CALL_V4))
 745           .addExternalSymbol(SpillFun);
 746     // Add callee-saved registers as use.
 747     addCalleeSaveRegistersAsImpOperand(SaveRegsCall, MaxReg, false);
 748     // Add live in registers.
 749     for (unsigned I = 0; I < CSI.size(); ++I)
 750       MBB.addLiveIn(CSI[I].getReg());
 751     return true;
 752   }
 753
 754   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
 755     unsigned Reg = CSI[i].getReg();
 756     // Add live in registers. We treat eh_return callee saved register r0 - r3
 757     // specially. They are not really callee saved registers as they are not
 758     // supposed to be killed.
 759     bool IsKill = !HRI.isEHReturnCalleeSaveReg(Reg);
 760     int FI = CSI[i].getFrameIdx();
 761     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 762     TII.storeRegToStackSlot(MBB, MI, Reg, IsKill, FI, RC, &HRI);
 763     if (IsKill)
 764       MBB.addLiveIn(Reg);
 765   }
 766   return true;
 767 }
 768
 769
 770 bool HexagonFrameLowering::insertCSRRestoresInBlock(MachineBasicBlock &MBB,
 771       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 772   if (CSI.empty())
 773     return false;
 774
 775   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 776   MachineFunction &MF = *MBB.getParent();
 777   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 778
 779   if (useRestoreFunction(MF, CSI)) {
 780     bool HasTC = hasTailCall(MBB) || !hasReturn(MBB);
 781     unsigned MaxR = getMaxCalleeSavedReg(CSI, HRI);
 782     SpillKind Kind = HasTC ? SK_FromMemTailcall : SK_FromMem;
 783     const char *RestoreFn = getSpillFunctionFor(MaxR, Kind);
 784
 785     // Call spill function.
 786     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc()
 787                                   : MBB.getLastNonDebugInstr()->getDebugLoc();
 788     MachineInstr *DeallocCall = nullptr;
 789
 790     if (HasTC) {
 791       unsigned ROpc = Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4;
 792       DeallocCall = BuildMI(MBB, MI, DL, TII.get(ROpc))
 793           .addExternalSymbol(RestoreFn);
 794     } else {
 795       // The block has a return.
 796       MachineBasicBlock::iterator It = MBB.getFirstTerminator();
 797       assert(It->isReturn() && std::next(It) == MBB.end());
 798       unsigned ROpc = Hexagon::RESTORE_DEALLOC_RET_JMP_V4;
 799       DeallocCall = BuildMI(MBB, It, DL, TII.get(ROpc))
 800           .addExternalSymbol(RestoreFn);
 801       // Transfer the function live-out registers.
 802       DeallocCall->copyImplicitOps(MF, It);
 803     }
 804     addCalleeSaveRegistersAsImpOperand(DeallocCall, MaxR, true);
 805     return true;
 806   }
 807
 808   for (unsigned i = 0; i < CSI.size(); ++i) {
 809     unsigned Reg = CSI[i].getReg();
 810     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 811     int FI = CSI[i].getFrameIdx();
 812     TII.loadRegFromStackSlot(MBB, MI, Reg, FI, RC, &HRI);
 813   }
 814   return true;
 815 }
 816
 817
 818 void HexagonFrameLowering::eliminateCallFramePseudoInstr(MachineFunction &MF,
 819       MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const {
 820   MachineInstr &MI = *I;
 821   unsigned Opc = MI.getOpcode();
 822   (void)Opc; // Silence compiler warning.
 823   assert((Opc == Hexagon::ADJCALLSTACKDOWN || Opc == Hexagon::ADJCALLSTACKUP) &&
 824          "Cannot handle this call frame pseudo instruction");
 825   MBB.erase(I);
 826 }
 827
 828
 829 void HexagonFrameLowering::processFunctionBeforeFrameFinalized(
 830     MachineFunction &MF, RegScavenger *RS) const {
 831   // If this function has uses aligned stack and also has variable sized stack
 832   // objects, then we need to map all spill slots to fixed positions, so that
 833   // they can be accessed through FP. Otherwise they would have to be accessed
 834   // via AP, which may not be available at the particular place in the program.
 835   MachineFrameInfo *MFI = MF.getFrameInfo();
 836   bool HasAlloca = MFI->hasVarSizedObjects();
 837   bool HasAligna = (MFI->getMaxAlignment() > getStackAlignment());
 838
 839   if (!HasAlloca || !HasAligna)
 840     return;
 841
 842   unsigned LFS = MFI->getLocalFrameSize();
 843   int Offset = -LFS;
 844   for (int i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
 845     if (!MFI->isSpillSlotObjectIndex(i) || MFI->isDeadObjectIndex(i))
 846       continue;
 847     int S = MFI->getObjectSize(i);
 848     LFS += S;
 849     Offset -= S;
 850     MFI->mapLocalFrameObject(i, Offset);
 851   }
 852
 853   MFI->setLocalFrameSize(LFS);
 854   unsigned A = MFI->getLocalFrameMaxAlign();
 855   assert(A <= 8 && "Unexpected local frame alignment");
 856   if (A == 0)
 857     MFI->setLocalFrameMaxAlign(8);
 858   MFI->setUseLocalStackAllocationBlock(true);
 859 }
 860
 861 /// Returns true if there is no caller saved registers available.
 862 static bool needToReserveScavengingSpillSlots(MachineFunction &MF,
 863                                               const HexagonRegisterInfo &HRI) {
 864   MachineRegisterInfo &MRI = MF.getRegInfo();
 865   const MCPhysReg *CallerSavedRegs = HRI.getCallerSavedRegs(&MF);
 866   // Check for an unused caller-saved register.
 867   for ( ; *CallerSavedRegs; ++CallerSavedRegs) {
 868     MCPhysReg FreeReg = *CallerSavedRegs;
 869     if (MRI.isPhysRegUsed(FreeReg))
 870       continue;
 871
 872     // Check aliased register usage.
 873     bool IsCurrentRegUsed = false;
 874     for (MCRegAliasIterator AI(FreeReg, &HRI, false); AI.isValid(); ++AI)
 875       if (MRI.isPhysRegUsed(*AI)) {
 876         IsCurrentRegUsed = true;
 877         break;
 878       }
 879     if (IsCurrentRegUsed)
 880       continue;
 881
 882     // Neither directly used nor used through an aliased register.
 883     return false;
 884   }
 885   // All caller-saved registers are used.
 886   return true;
 887 }
 888
 889
 890 /// Replaces the predicate spill code pseudo instructions by valid instructions.
 891 bool HexagonFrameLowering::replacePredRegPseudoSpillCode(MachineFunction &MF)
 892       const {
 893   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 894   auto &HII = *HST.getInstrInfo();
 895   MachineRegisterInfo &MRI = MF.getRegInfo();
 896   bool HasReplacedPseudoInst = false;
 897   // Replace predicate spill pseudo instructions by real code.
 898   // Loop over all of the basic blocks.
 899   for (MachineFunction::iterator MBBb = MF.begin(), MBBe = MF.end();
 900        MBBb != MBBe; ++MBBb) {
 901     MachineBasicBlock* MBB = MBBb;
 902     // Traverse the basic block.
 903     MachineBasicBlock::iterator NextII;
 904     for (MachineBasicBlock::iterator MII = MBB->begin(); MII != MBB->end();
 905          MII = NextII) {
 906       MachineInstr *MI = MII;
 907       NextII = std::next(MII);
 908       int Opc = MI->getOpcode();
 909       if (Opc == Hexagon::STriw_pred) {
 910         HasReplacedPseudoInst = true;
 911         // STriw_pred FI, 0, SrcReg;
 912         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 913         unsigned SrcReg = MI->getOperand(2).getReg();
 914         bool IsOrigSrcRegKilled = MI->getOperand(2).isKill();
 915
 916         assert(MI->getOperand(0).isFI() && "Expect a frame index");
 917         assert(Hexagon::PredRegsRegClass.contains(SrcReg) &&
 918                "Not a predicate register");
 919
 920         // Insert transfer to general purpose register.
 921         //   VirtReg = C2_tfrpr SrcPredReg
 922         BuildMI(*MBB, MII, MI->getDebugLoc(), HII.get(Hexagon::C2_tfrpr),
 923                 VirtReg).addReg(SrcReg, getKillRegState(IsOrigSrcRegKilled));
 924
 925         // Change instruction to S2_storeri_io.
 926         //   S2_storeri_io FI, 0, VirtReg
 927         MI->setDesc(HII.get(Hexagon::S2_storeri_io));
 928         MI->getOperand(2).setReg(VirtReg);
 929         MI->getOperand(2).setIsKill();
 930
 931       } else if (Opc == Hexagon::LDriw_pred) {
 932         // DstReg = LDriw_pred FI, 0
 933         MachineOperand &M0 = MI->getOperand(0);
 934         if (M0.isDead()) {
 935           MBB->erase(MII);
 936           continue;
 937         }
 938
 939         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 940         unsigned DestReg = MI->getOperand(0).getReg();
 941
 942         assert(MI->getOperand(1).isFI() && "Expect a frame index");
 943         assert(Hexagon::PredRegsRegClass.contains(DestReg) &&
 944                "Not a predicate register");
 945
 946         // Change instruction to L2_loadri_io.
 947         //   VirtReg = L2_loadri_io FI, 0
 948         MI->setDesc(HII.get(Hexagon::L2_loadri_io));
 949         MI->getOperand(0).setReg(VirtReg);
 950
 951         // Insert transfer to general purpose register.
 952         //   DestReg = C2_tfrrp VirtReg
 953         const MCInstrDesc &D = HII.get(Hexagon::C2_tfrrp);
 954         BuildMI(*MBB, std::next(MII), MI->getDebugLoc(), D, DestReg)
 955           .addReg(VirtReg, getKillRegState(true));
 956         HasReplacedPseudoInst = true;
 957       }
 958     }
 959   }
 960   return HasReplacedPseudoInst;
 961 }
 962
 963
 964 void HexagonFrameLowering::processFunctionBeforeCalleeSavedScan(
 965       MachineFunction &MF, RegScavenger* RS) const {
 966   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 967   auto &HRI = *HST.getRegisterInfo();
 968
 969   bool HasEHReturn = MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn();
 970
 971   // If we have a function containing __builtin_eh_return we want to spill and
 972   // restore all callee saved registers. Pretend that they are used.
 973   if (HasEHReturn) {
 974     MachineRegisterInfo &MRI = MF.getRegInfo();
 975     for (const MCPhysReg *CSRegs = HRI.getCalleeSavedRegs(&MF); *CSRegs;
 976          ++CSRegs)
 977       if (!MRI.isPhysRegUsed(*CSRegs))
 978         MRI.setPhysRegUsed(*CSRegs);
 979   }
 980
 981   const TargetRegisterClass &RC = Hexagon::IntRegsRegClass;
 982
 983   // Replace predicate register pseudo spill code.
 984   bool HasReplacedPseudoInst = replacePredRegPseudoSpillCode(MF);
 985
 986   // We need to reserve a a spill slot if scavenging could potentially require
 987   // spilling a scavenged register.
 988   if (HasReplacedPseudoInst && needToReserveScavengingSpillSlots(MF, HRI)) {
 989     MachineFrameInfo *MFI = MF.getFrameInfo();
 990     for (int i=0; i < NumberScavengerSlots; i++)
 991       RS->addScavengingFrameIndex(
 992         MFI->CreateSpillStackObject(RC.getSize(), RC.getAlignment()));
 993   }
 994 }
 995
 996
 997 #ifndef NDEBUG
 998 static void dump_registers(BitVector &Regs, const TargetRegisterInfo &TRI) {
 999   dbgs() << '{';
1000   for (int x = Regs.find_first(); x >= 0; x = Regs.find_next(x)) {
1001     unsigned R = x;
1002     dbgs() << ' ' << PrintReg(R, &TRI);
1003   }
1004   dbgs() << " }";
1005 }
1006 #endif
1007
1008
1009 bool HexagonFrameLowering::assignCalleeSavedSpillSlots(MachineFunction &MF,
1010       const TargetRegisterInfo *TRI, std::vector<CalleeSavedInfo> &CSI) const {
1011   const Function &F = *MF.getFunction();
1012   (void)F; // Silence compiler warning.
1013   DEBUG(dbgs() << LLVM_FUNCTION_NAME << " on " << F.getName() << '\n');
1014   MachineFrameInfo *MFI = MF.getFrameInfo();
1015   BitVector SRegs(Hexagon::NUM_TARGET_REGS);
1016
1017   // Generate a set of unique, callee-saved registers (SRegs), where each
1018   // register in the set is maximal in terms of sub-/super-register relation,
1019   // i.e. for each R in SRegs, no proper super-register of R is also in SRegs.
1020
1021   // (1) For each callee-saved register, add that register and all of its
1022   // sub-registers to SRegs.
1023   DEBUG(dbgs() << "Initial CS registers: {");
1024   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1025     unsigned R = CSI[i].getReg();
1026     DEBUG(dbgs() << ' ' << PrintReg(R, TRI));
1027     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1028       SRegs[*SR] = true;
1029   }
1030   DEBUG(dbgs() << " }\n");
1031   DEBUG(dbgs() << "SRegs.1: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1032
1033   // (2) For each reserved register, remove that register and all of its
1034   // sub- and super-registers from SRegs.
1035   BitVector Reserved = TRI->getReservedRegs(MF);
1036   for (int x = Reserved.find_first(); x >= 0; x = Reserved.find_next(x)) {
1037     unsigned R = x;
1038     for (MCSuperRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1039       SRegs[*SR] = false;
1040   }
1041   DEBUG(dbgs() << "Res:     "; dump_registers(Reserved, *TRI); dbgs() << "\n");
1042   DEBUG(dbgs() << "SRegs.2: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1043
1044   // (3) Collect all registers that have at least one sub-register in SRegs,
1045   // and also have no sub-registers that are reserved. These will be the can-
1046   // didates for saving as a whole instead of their individual sub-registers.
1047   // (Saving R17:16 instead of R16 is fine, but only if R17 was not reserved.)
1048   BitVector TmpSup(Hexagon::NUM_TARGET_REGS);
1049   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1050     unsigned R = x;
1051     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR)
1052       TmpSup[*SR] = true;
1053   }
1054   for (int x = TmpSup.find_first(); x >= 0; x = TmpSup.find_next(x)) {
1055     unsigned R = x;
1056     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR) {
1057       if (!Reserved[*SR])
1058         continue;
1059       TmpSup[R] = false;
1060       break;
1061     }
1062   }
1063   DEBUG(dbgs() << "TmpSup:  "; dump_registers(TmpSup, *TRI); dbgs() << "\n");
1064
1065   // (4) Include all super-registers found in (3) into SRegs.
1066   SRegs |= TmpSup;
1067   DEBUG(dbgs() << "SRegs.4: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1068
1069   // (5) For each register R in SRegs, if any super-register of R is in SRegs,
1070   // remove R from SRegs.
1071   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1072     unsigned R = x;
1073     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR) {
1074       if (!SRegs[*SR])
1075         continue;
1076       SRegs[R] = false;
1077       break;
1078     }
1079   }
1080   DEBUG(dbgs() << "SRegs.5: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1081
1082   // Now, for each register that has a fixed stack slot, create the stack
1083   // object for it.
1084   CSI.clear();
1085
1086   typedef TargetFrameLowering::SpillSlot SpillSlot;
1087   unsigned NumFixed;
1088   int MinOffset = 0;  // CS offsets are negative.
1089   const SpillSlot *FixedSlots = getCalleeSavedSpillSlots(NumFixed);
1090   for (const SpillSlot *S = FixedSlots; S != FixedSlots+NumFixed; ++S) {
1091     if (!SRegs[S->Reg])
1092       continue;
1093     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(S->Reg);
1094     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), S->Offset);
1095     MinOffset = std::min(MinOffset, S->Offset);
1096     CSI.push_back(CalleeSavedInfo(S->Reg, FI));
1097     SRegs[S->Reg] = false;
1098   }
1099
1100   // There can be some registers that don't have fixed slots. For example,
1101   // we need to store R0-R3 in functions with exception handling. For each
1102   // such register, create a non-fixed stack object.
1103   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1104     unsigned R = x;
1105     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(R);
1106     int Off = MinOffset - RC->getSize();
1107     unsigned Align = std::min(RC->getAlignment(), getStackAlignment());
1108     assert(isPowerOf2_32(Align));
1109     Off &= -Align;
1110     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), Off);
1111     MinOffset = std::min(MinOffset, Off);
1112     CSI.push_back(CalleeSavedInfo(R, FI));
1113     SRegs[R] = false;
1114   }
1115
1116   DEBUG({
1117     dbgs() << "CS information: {";
1118     for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1119       int FI = CSI[i].getFrameIdx();
1120       int Off = MFI->getObjectOffset(FI);
1121       dbgs() << ' ' << PrintReg(CSI[i].getReg(), TRI) << ":fi#" << FI << ":sp";
1122       if (Off >= 0)
1123         dbgs() << '+';
1124       dbgs() << Off;
1125     }
1126     dbgs() << " }\n";
1127   });
1128
1129 #ifndef NDEBUG
1130   // Verify that all registers were handled.
1131   bool MissedReg = false;
1132   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1133     unsigned R = x;
1134     dbgs() << PrintReg(R, TRI) << ' ';
1135     MissedReg = true;
1136   }
1137   if (MissedReg)
1138     llvm_unreachable("...there are unhandled callee-saved registers!");
1139 #endif
1140
1141   return true;
1142 }
1143
1144
1145 void HexagonFrameLowering::expandAlloca(MachineInstr *AI,
1146       const HexagonInstrInfo &HII, unsigned SP, unsigned CF) const {
1147   MachineBasicBlock &MB = *AI->getParent();
1148   DebugLoc DL = AI->getDebugLoc();
1149   unsigned A = AI->getOperand(2).getImm();
1150
1151   // Have
1152   //    Rd  = alloca Rs, #A
1153   //
1154   // If Rs and Rd are different registers, use this sequence:
1155   //    Rd  = sub(r29, Rs)
1156   //    r29 = sub(r29, Rs)
1157   //    Rd  = and(Rd, #-A)    ; if necessary
1158   //    r29 = and(r29, #-A)   ; if necessary
1159   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1160   // otherwise, do
1161   //    Rd  = sub(r29, Rs)
1162   //    Rd  = and(Rd, #-A)    ; if necessary
1163   //    r29 = Rd
1164   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1165
1166   MachineOperand &RdOp = AI->getOperand(0);
1167   MachineOperand &RsOp = AI->getOperand(1);
1168   unsigned Rd = RdOp.getReg(), Rs = RsOp.getReg();
1169
1170   // Rd = sub(r29, Rs)
1171   BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), Rd)
1172       .addReg(SP)
1173       .addReg(Rs);
1174   if (Rs != Rd) {
1175     // r29 = sub(r29, Rs)
1176     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), SP)
1177         .addReg(SP)
1178         .addReg(Rs);
1179   }
1180   if (A > 8) {
1181     // Rd  = and(Rd, #-A)
1182     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), Rd)
1183         .addReg(Rd)
1184         .addImm(-int64_t(A));
1185     if (Rs != Rd)
1186       BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), SP)
1187           .addReg(SP)
1188           .addImm(-int64_t(A));
1189   }
1190   if (Rs == Rd) {
1191     // r29 = Rd
1192     BuildMI(MB, AI, DL, HII.get(TargetOpcode::COPY), SP)
1193         .addReg(Rd);
1194   }
1195   if (CF > 0) {
1196     // Rd = add(Rd, #CF)
1197     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_addi), Rd)
1198         .addReg(Rd)
1199         .addImm(CF);
1200   }
1201 }
1202
1203
1204 bool HexagonFrameLowering::needsAligna(const MachineFunction &MF) const {
1205   const MachineFrameInfo *MFI = MF.getFrameInfo();
1206   if (!MFI->hasVarSizedObjects())
1207     return false;
1208   unsigned MaxA = MFI->getMaxAlignment();
1209   if (MaxA <= getStackAlignment())
1210     return false;
1211   return true;
1212 }
1213
1214
1215 MachineInstr *HexagonFrameLowering::getAlignaInstr(MachineFunction &MF) const {
1216   for (auto &B : MF)
1217     for (auto &I : B)
1218       if (I.getOpcode() == Hexagon::ALIGNA)
1219         return &I;
1220   return nullptr;
1221 }
1222
1223
1224 inline static bool isOptSize(const MachineFunction &MF) {
1225   AttributeSet AF = MF.getFunction()->getAttributes();
1226   return AF.hasAttribute(AttributeSet::FunctionIndex,
1227                          Attribute::OptimizeForSize);
1228 }
1229
1230 inline static bool isMinSize(const MachineFunction &MF) {
1231   AttributeSet AF = MF.getFunction()->getAttributes();
1232   return AF.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);
1233 }
1234
1235
1236 /// Determine whether the callee-saved register saves and restores should
1237 /// be generated via inline code. If this function returns "true", inline
1238 /// code will be generated. If this function returns "false", additional
1239 /// checks are performed, which may still lead to the inline code.
1240 bool HexagonFrameLowering::shouldInlineCSR(MachineFunction &MF,
1241       const CSIVect &CSI) const {
1242   if (MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn())
1243     return true;
1244   if (!isOptSize(MF) && !isMinSize(MF))
1245     if (MF.getTarget().getOptLevel() > CodeGenOpt::Default)
1246       return true;
1247
1248   // Check if CSI only has double registers, and if the registers form
1249   // a contiguous block starting from D8.
1250   BitVector Regs(Hexagon::NUM_TARGET_REGS);
1251   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1252     unsigned R = CSI[i].getReg();
1253     if (!Hexagon::DoubleRegsRegClass.contains(R))
1254       return true;
1255     Regs[R] = true;
1256   }
1257   int F = Regs.find_first();
1258   if (F != Hexagon::D8)
1259     return true;
1260   while (F >= 0) {
1261     int N = Regs.find_next(F);
1262     if (N >= 0 && N != F+1)
1263       return true;
1264     F = N;
1265   }
1266
1267   return false;
1268 }
1269
1270
1271 bool HexagonFrameLowering::useSpillFunction(MachineFunction &MF,
1272       const CSIVect &CSI) const {
1273   if (shouldInlineCSR(MF, CSI))
1274     return false;
1275   unsigned NumCSI = CSI.size();
1276   if (NumCSI <= 1)
1277     return false;
1278
1279   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs
1280                                      : SpillFuncThreshold;
1281   return Threshold < NumCSI;
1282 }
1283
1284
1285 bool HexagonFrameLowering::useRestoreFunction(MachineFunction &MF,
1286       const CSIVect &CSI) const {
1287   if (shouldInlineCSR(MF, CSI))
1288     return false;
1289   unsigned NumCSI = CSI.size();
1290   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs-1
1291                                      : SpillFuncThreshold;
1292   return Threshold < NumCSI;
1293 }
1294