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     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 583     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::A2_add), SP)
 584         .addReg(SP)
 585         .addReg(Hexagon::R28);
 586     return;
 587   }
 588
 589   // Check for RESTORE_DEALLOC_RET* tail call. Don't emit an extra dealloc-
 590   // frame instruction if we encounter it.
 591   if (RetOpc == Hexagon::RESTORE_DEALLOC_RET_JMP_V4) {
 592     MachineBasicBlock::iterator It = RetI;
 593     ++It;
 594     // Delete all instructions after the RESTORE (except labels).
 595     while (It != MBB.end()) {
 596       if (!It->isLabel())
 597         It = MBB.erase(It);
 598       else
 599         ++It;
 600     }
 601     return;
 602   }
 603
 604   // It is possible that the restoring code is a call to a library function.
 605   // All of the restore* functions include "deallocframe", so we need to make
 606   // sure that we don't add an extra one.
 607   bool NeedsDeallocframe = true;
 608   if (!MBB.empty() && InsertPt != MBB.begin()) {
 609     MachineBasicBlock::iterator PrevIt = std::prev(InsertPt);
 610     unsigned COpc = PrevIt->getOpcode();
 611     if (COpc == Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4)
 612       NeedsDeallocframe = false;
 613   }
 614
 615   if (!NeedsDeallocframe)
 616     return;
 617   // If the returning instruction is JMPret, replace it with dealloc_return,
 618   // otherwise just add deallocframe. The function could be returning via a
 619   // tail call.
 620   if (RetOpc != Hexagon::JMPret || DisableDeallocRet) {
 621     BuildMI(MBB, InsertPt, DL, HII.get(Hexagon::L2_deallocframe));
 622     return;
 623   }
 624   unsigned NewOpc = Hexagon::L4_return;
 625   MachineInstr *NewI = BuildMI(MBB, RetI, DL, HII.get(NewOpc));
 626   // Transfer the function live-out registers.
 627   NewI->copyImplicitOps(MF, RetI);
 628   MBB.erase(RetI);
 629 }
 630
 631
 632 bool HexagonFrameLowering::hasFP(const MachineFunction &MF) const {
 633   const MachineFrameInfo *MFI = MF.getFrameInfo();
 634   const HexagonMachineFunctionInfo *FuncInfo =
 635     MF.getInfo<HexagonMachineFunctionInfo>();
 636   return MFI->hasCalls() || MFI->getStackSize() > 0 ||
 637          FuncInfo->hasClobberLR();
 638 }
 639
 640
 641 enum SpillKind {
 642   SK_ToMem,
 643   SK_FromMem,
 644   SK_FromMemTailcall
 645 };
 646
 647 static const char *
 648 getSpillFunctionFor(unsigned MaxReg, SpillKind SpillType) {
 649   const char * V4SpillToMemoryFunctions[] = {
 650     "__save_r16_through_r17",
 651     "__save_r16_through_r19",
 652     "__save_r16_through_r21",
 653     "__save_r16_through_r23",
 654     "__save_r16_through_r25",
 655     "__save_r16_through_r27" };
 656
 657   const char * V4SpillFromMemoryFunctions[] = {
 658     "__restore_r16_through_r17_and_deallocframe",
 659     "__restore_r16_through_r19_and_deallocframe",
 660     "__restore_r16_through_r21_and_deallocframe",
 661     "__restore_r16_through_r23_and_deallocframe",
 662     "__restore_r16_through_r25_and_deallocframe",
 663     "__restore_r16_through_r27_and_deallocframe" };
 664
 665   const char * V4SpillFromMemoryTailcallFunctions[] = {
 666     "__restore_r16_through_r17_and_deallocframe_before_tailcall",
 667     "__restore_r16_through_r19_and_deallocframe_before_tailcall",
 668     "__restore_r16_through_r21_and_deallocframe_before_tailcall",
 669     "__restore_r16_through_r23_and_deallocframe_before_tailcall",
 670     "__restore_r16_through_r25_and_deallocframe_before_tailcall",
 671     "__restore_r16_through_r27_and_deallocframe_before_tailcall"
 672   };
 673
 674   const char **SpillFunc = nullptr;
 675
 676   switch(SpillType) {
 677   case SK_ToMem:
 678     SpillFunc = V4SpillToMemoryFunctions;
 679     break;
 680   case SK_FromMem:
 681     SpillFunc = V4SpillFromMemoryFunctions;
 682     break;
 683   case SK_FromMemTailcall:
 684     SpillFunc = V4SpillFromMemoryTailcallFunctions;
 685     break;
 686   }
 687   assert(SpillFunc && "Unknown spill kind");
 688
 689   // Spill all callee-saved registers up to the highest register used.
 690   switch (MaxReg) {
 691   case Hexagon::R17:
 692     return SpillFunc[0];
 693   case Hexagon::R19:
 694     return SpillFunc[1];
 695   case Hexagon::R21:
 696     return SpillFunc[2];
 697   case Hexagon::R23:
 698     return SpillFunc[3];
 699   case Hexagon::R25:
 700     return SpillFunc[4];
 701   case Hexagon::R27:
 702     return SpillFunc[5];
 703   default:
 704     llvm_unreachable("Unhandled maximum callee save register");
 705   }
 706   return 0;
 707 }
 708
 709 /// Adds all callee-saved registers up to MaxReg to the instruction.
 710 static void addCalleeSaveRegistersAsImpOperand(MachineInstr *Inst,
 711                                            unsigned MaxReg, bool IsDef) {
 712   // Add the callee-saved registers as implicit uses.
 713   for (unsigned R = Hexagon::R16; R <= MaxReg; ++R) {
 714     MachineOperand ImpUse = MachineOperand::CreateReg(R, IsDef, true);
 715     Inst->addOperand(ImpUse);
 716   }
 717 }
 718
 719
 720 int HexagonFrameLowering::getFrameIndexOffset(const MachineFunction &MF,
 721       int FI) const {
 722   return MF.getFrameInfo()->getObjectOffset(FI);
 723 }
 724
 725
 726 bool HexagonFrameLowering::insertCSRSpillsInBlock(MachineBasicBlock &MBB,
 727       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 728   if (CSI.empty())
 729     return true;
 730
 731   MachineBasicBlock::iterator MI = MBB.begin();
 732   MachineFunction &MF = *MBB.getParent();
 733   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 734
 735   if (useSpillFunction(MF, CSI)) {
 736     unsigned MaxReg = getMaxCalleeSavedReg(CSI, HRI);
 737     const char *SpillFun = getSpillFunctionFor(MaxReg, SK_ToMem);
 738     // Call spill function.
 739     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc() : DebugLoc();
 740     MachineInstr *SaveRegsCall =
 741         BuildMI(MBB, MI, DL, TII.get(Hexagon::SAVE_REGISTERS_CALL_V4))
 742           .addExternalSymbol(SpillFun);
 743     // Add callee-saved registers as use.
 744     addCalleeSaveRegistersAsImpOperand(SaveRegsCall, MaxReg, false);
 745     // Add live in registers.
 746     for (unsigned I = 0; I < CSI.size(); ++I)
 747       MBB.addLiveIn(CSI[I].getReg());
 748     return true;
 749   }
 750
 751   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
 752     unsigned Reg = CSI[i].getReg();
 753     // Add live in registers. We treat eh_return callee saved register r0 - r3
 754     // specially. They are not really callee saved registers as they are not
 755     // supposed to be killed.
 756     bool IsKill = !HRI.isEHReturnCalleeSaveReg(Reg);
 757     int FI = CSI[i].getFrameIdx();
 758     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 759     TII.storeRegToStackSlot(MBB, MI, Reg, IsKill, FI, RC, &HRI);
 760     if (IsKill)
 761       MBB.addLiveIn(Reg);
 762   }
 763   return true;
 764 }
 765
 766
 767 bool HexagonFrameLowering::insertCSRRestoresInBlock(MachineBasicBlock &MBB,
 768       const CSIVect &CSI, const HexagonRegisterInfo &HRI) const {
 769   if (CSI.empty())
 770     return false;
 771
 772   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 773   MachineFunction &MF = *MBB.getParent();
 774   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 775
 776   if (useRestoreFunction(MF, CSI)) {
 777     bool HasTC = hasTailCall(MBB) || !hasReturn(MBB);
 778     unsigned MaxR = getMaxCalleeSavedReg(CSI, HRI);
 779     SpillKind Kind = HasTC ? SK_FromMemTailcall : SK_FromMem;
 780     const char *RestoreFn = getSpillFunctionFor(MaxR, Kind);
 781
 782     // Call spill function.
 783     DebugLoc DL = MI != MBB.end() ? MI->getDebugLoc()
 784                                   : MBB.getLastNonDebugInstr()->getDebugLoc();
 785     MachineInstr *DeallocCall = nullptr;
 786
 787     if (HasTC) {
 788       unsigned ROpc = Hexagon::RESTORE_DEALLOC_BEFORE_TAILCALL_V4;
 789       DeallocCall = BuildMI(MBB, MI, DL, TII.get(ROpc))
 790           .addExternalSymbol(RestoreFn);
 791     } else {
 792       // The block has a return.
 793       MachineBasicBlock::iterator It = MBB.getFirstTerminator();
 794       assert(It->isReturn() && std::next(It) == MBB.end());
 795       unsigned ROpc = Hexagon::RESTORE_DEALLOC_RET_JMP_V4;
 796       DeallocCall = BuildMI(MBB, It, DL, TII.get(ROpc))
 797           .addExternalSymbol(RestoreFn);
 798       // Transfer the function live-out registers.
 799       DeallocCall->copyImplicitOps(MF, It);
 800     }
 801     addCalleeSaveRegistersAsImpOperand(DeallocCall, MaxR, true);
 802     return true;
 803   }
 804
 805   for (unsigned i = 0; i < CSI.size(); ++i) {
 806     unsigned Reg = CSI[i].getReg();
 807     const TargetRegisterClass *RC = HRI.getMinimalPhysRegClass(Reg);
 808     int FI = CSI[i].getFrameIdx();
 809     TII.loadRegFromStackSlot(MBB, MI, Reg, FI, RC, &HRI);
 810   }
 811   return true;
 812 }
 813
 814
 815 void HexagonFrameLowering::eliminateCallFramePseudoInstr(MachineFunction &MF,
 816       MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const {
 817   MachineInstr &MI = *I;
 818   unsigned Opc = MI.getOpcode();
 819   (void)Opc; // Silence compiler warning.
 820   assert((Opc == Hexagon::ADJCALLSTACKDOWN || Opc == Hexagon::ADJCALLSTACKUP) &&
 821          "Cannot handle this call frame pseudo instruction");
 822   MBB.erase(I);
 823 }
 824
 825
 826 void HexagonFrameLowering::processFunctionBeforeFrameFinalized(
 827     MachineFunction &MF, RegScavenger *RS) const {
 828   // If this function has uses aligned stack and also has variable sized stack
 829   // objects, then we need to map all spill slots to fixed positions, so that
 830   // they can be accessed through FP. Otherwise they would have to be accessed
 831   // via AP, which may not be available at the particular place in the program.
 832   MachineFrameInfo *MFI = MF.getFrameInfo();
 833   bool HasAlloca = MFI->hasVarSizedObjects();
 834   bool HasAligna = (MFI->getMaxAlignment() > getStackAlignment());
 835
 836   if (!HasAlloca || !HasAligna)
 837     return;
 838
 839   unsigned LFS = MFI->getLocalFrameSize();
 840   int Offset = -LFS;
 841   for (int i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
 842     if (!MFI->isSpillSlotObjectIndex(i) || MFI->isDeadObjectIndex(i))
 843       continue;
 844     int S = MFI->getObjectSize(i);
 845     LFS += S;
 846     Offset -= S;
 847     MFI->mapLocalFrameObject(i, Offset);
 848   }
 849
 850   MFI->setLocalFrameSize(LFS);
 851   unsigned A = MFI->getLocalFrameMaxAlign();
 852   assert(A <= 8 && "Unexpected local frame alignment");
 853   if (A == 0)
 854     MFI->setLocalFrameMaxAlign(8);
 855   MFI->setUseLocalStackAllocationBlock(true);
 856 }
 857
 858 /// Returns true if there is no caller saved registers available.
 859 static bool needToReserveScavengingSpillSlots(MachineFunction &MF,
 860                                               const HexagonRegisterInfo &HRI) {
 861   MachineRegisterInfo &MRI = MF.getRegInfo();
 862   const MCPhysReg *CallerSavedRegs = HRI.getCallerSavedRegs(&MF);
 863   // Check for an unused caller-saved register.
 864   for ( ; *CallerSavedRegs; ++CallerSavedRegs) {
 865     MCPhysReg FreeReg = *CallerSavedRegs;
 866     if (MRI.isPhysRegUsed(FreeReg))
 867       continue;
 868
 869     // Check aliased register usage.
 870     bool IsCurrentRegUsed = false;
 871     for (MCRegAliasIterator AI(FreeReg, &HRI, false); AI.isValid(); ++AI)
 872       if (MRI.isPhysRegUsed(*AI)) {
 873         IsCurrentRegUsed = true;
 874         break;
 875       }
 876     if (IsCurrentRegUsed)
 877       continue;
 878
 879     // Neither directly used nor used through an aliased register.
 880     return false;
 881   }
 882   // All caller-saved registers are used.
 883   return true;
 884 }
 885
 886
 887 /// Replaces the predicate spill code pseudo instructions by valid instructions.
 888 bool HexagonFrameLowering::replacePredRegPseudoSpillCode(MachineFunction &MF)
 889       const {
 890   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 891   auto &HII = *HST.getInstrInfo();
 892   MachineRegisterInfo &MRI = MF.getRegInfo();
 893   bool HasReplacedPseudoInst = false;
 894   // Replace predicate spill pseudo instructions by real code.
 895   // Loop over all of the basic blocks.
 896   for (MachineFunction::iterator MBBb = MF.begin(), MBBe = MF.end();
 897        MBBb != MBBe; ++MBBb) {
 898     MachineBasicBlock* MBB = MBBb;
 899     // Traverse the basic block.
 900     MachineBasicBlock::iterator NextII;
 901     for (MachineBasicBlock::iterator MII = MBB->begin(); MII != MBB->end();
 902          MII = NextII) {
 903       MachineInstr *MI = MII;
 904       NextII = std::next(MII);
 905       int Opc = MI->getOpcode();
 906       if (Opc == Hexagon::STriw_pred) {
 907         HasReplacedPseudoInst = true;
 908         // STriw_pred FI, 0, SrcReg;
 909         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 910         unsigned SrcReg = MI->getOperand(2).getReg();
 911         bool IsOrigSrcRegKilled = MI->getOperand(2).isKill();
 912
 913         assert(MI->getOperand(0).isFI() && "Expect a frame index");
 914         assert(Hexagon::PredRegsRegClass.contains(SrcReg) &&
 915                "Not a predicate register");
 916
 917         // Insert transfer to general purpose register.
 918         //   VirtReg = C2_tfrpr SrcPredReg
 919         BuildMI(*MBB, MII, MI->getDebugLoc(), HII.get(Hexagon::C2_tfrpr),
 920                 VirtReg).addReg(SrcReg, getKillRegState(IsOrigSrcRegKilled));
 921
 922         // Change instruction to S2_storeri_io.
 923         //   S2_storeri_io FI, 0, VirtReg
 924         MI->setDesc(HII.get(Hexagon::S2_storeri_io));
 925         MI->getOperand(2).setReg(VirtReg);
 926         MI->getOperand(2).setIsKill();
 927
 928       } else if (Opc == Hexagon::LDriw_pred) {
 929         // DstReg = LDriw_pred FI, 0
 930         MachineOperand &M0 = MI->getOperand(0);
 931         if (M0.isDead()) {
 932           MBB->erase(MII);
 933           continue;
 934         }
 935
 936         unsigned VirtReg = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
 937         unsigned DestReg = MI->getOperand(0).getReg();
 938
 939         assert(MI->getOperand(1).isFI() && "Expect a frame index");
 940         assert(Hexagon::PredRegsRegClass.contains(DestReg) &&
 941                "Not a predicate register");
 942
 943         // Change instruction to L2_loadri_io.
 944         //   VirtReg = L2_loadri_io FI, 0
 945         MI->setDesc(HII.get(Hexagon::L2_loadri_io));
 946         MI->getOperand(0).setReg(VirtReg);
 947
 948         // Insert transfer to general purpose register.
 949         //   DestReg = C2_tfrrp VirtReg
 950         const MCInstrDesc &D = HII.get(Hexagon::C2_tfrrp);
 951         BuildMI(*MBB, std::next(MII), MI->getDebugLoc(), D, DestReg)
 952           .addReg(VirtReg, getKillRegState(true));
 953         HasReplacedPseudoInst = true;
 954       }
 955     }
 956   }
 957   return HasReplacedPseudoInst;
 958 }
 959
 960
 961 void HexagonFrameLowering::processFunctionBeforeCalleeSavedScan(
 962       MachineFunction &MF, RegScavenger* RS) const {
 963   auto &HST = static_cast<const HexagonSubtarget&>(MF.getSubtarget());
 964   auto &HRI = *HST.getRegisterInfo();
 965
 966   bool HasEHReturn = MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn();
 967
 968   // If we have a function containing __builtin_eh_return we want to spill and
 969   // restore all callee saved registers. Pretend that they are used.
 970   if (HasEHReturn) {
 971     MachineRegisterInfo &MRI = MF.getRegInfo();
 972     for (const MCPhysReg *CSRegs = HRI.getCalleeSavedRegs(&MF); *CSRegs;
 973          ++CSRegs)
 974       if (!MRI.isPhysRegUsed(*CSRegs))
 975         MRI.setPhysRegUsed(*CSRegs);
 976   }
 977
 978   const TargetRegisterClass &RC = Hexagon::IntRegsRegClass;
 979
 980   // Replace predicate register pseudo spill code.
 981   bool HasReplacedPseudoInst = replacePredRegPseudoSpillCode(MF);
 982
 983   // We need to reserve a a spill slot if scavenging could potentially require
 984   // spilling a scavenged register.
 985   if (HasReplacedPseudoInst && needToReserveScavengingSpillSlots(MF, HRI)) {
 986     MachineFrameInfo *MFI = MF.getFrameInfo();
 987     for (int i=0; i < NumberScavengerSlots; i++)
 988       RS->addScavengingFrameIndex(
 989         MFI->CreateSpillStackObject(RC.getSize(), RC.getAlignment()));
 990   }
 991 }
 992
 993
 994 #ifndef NDEBUG
 995 static void dump_registers(BitVector &Regs, const TargetRegisterInfo &TRI) {
 996   dbgs() << '{';
 997   for (int x = Regs.find_first(); x >= 0; x = Regs.find_next(x)) {
 998     unsigned R = x;
 999     dbgs() << ' ' << PrintReg(R, &TRI);
1000   }
1001   dbgs() << " }";
1002 }
1003 #endif
1004
1005
1006 bool HexagonFrameLowering::assignCalleeSavedSpillSlots(MachineFunction &MF,
1007       const TargetRegisterInfo *TRI, std::vector<CalleeSavedInfo> &CSI) const {
1008   DEBUG(dbgs() << LLVM_FUNCTION_NAME << " on "
1009                << MF.getFunction()->getName() << '\n');
1010   MachineFrameInfo *MFI = MF.getFrameInfo();
1011   BitVector SRegs(Hexagon::NUM_TARGET_REGS);
1012
1013   // Generate a set of unique, callee-saved registers (SRegs), where each
1014   // register in the set is maximal in terms of sub-/super-register relation,
1015   // i.e. for each R in SRegs, no proper super-register of R is also in SRegs.
1016
1017   // (1) For each callee-saved register, add that register and all of its
1018   // sub-registers to SRegs.
1019   DEBUG(dbgs() << "Initial CS registers: {");
1020   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1021     unsigned R = CSI[i].getReg();
1022     DEBUG(dbgs() << ' ' << PrintReg(R, TRI));
1023     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1024       SRegs[*SR] = true;
1025   }
1026   DEBUG(dbgs() << " }\n");
1027   DEBUG(dbgs() << "SRegs.1: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1028
1029   // (2) For each reserved register, remove that register and all of its
1030   // sub- and super-registers from SRegs.
1031   BitVector Reserved = TRI->getReservedRegs(MF);
1032   for (int x = Reserved.find_first(); x >= 0; x = Reserved.find_next(x)) {
1033     unsigned R = x;
1034     for (MCSuperRegIterator SR(R, TRI, true); SR.isValid(); ++SR)
1035       SRegs[*SR] = false;
1036   }
1037   DEBUG(dbgs() << "Res:     "; dump_registers(Reserved, *TRI); dbgs() << "\n");
1038   DEBUG(dbgs() << "SRegs.2: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1039
1040   // (3) Collect all registers that have at least one sub-register in SRegs,
1041   // and also have no sub-registers that are reserved. These will be the can-
1042   // didates for saving as a whole instead of their individual sub-registers.
1043   // (Saving R17:16 instead of R16 is fine, but only if R17 was not reserved.)
1044   BitVector TmpSup(Hexagon::NUM_TARGET_REGS);
1045   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1046     unsigned R = x;
1047     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR)
1048       TmpSup[*SR] = true;
1049   }
1050   for (int x = TmpSup.find_first(); x >= 0; x = TmpSup.find_next(x)) {
1051     unsigned R = x;
1052     for (MCSubRegIterator SR(R, TRI, true); SR.isValid(); ++SR) {
1053       if (!Reserved[*SR])
1054         continue;
1055       TmpSup[R] = false;
1056       break;
1057     }
1058   }
1059   DEBUG(dbgs() << "TmpSup:  "; dump_registers(TmpSup, *TRI); dbgs() << "\n");
1060
1061   // (4) Include all super-registers found in (3) into SRegs.
1062   SRegs |= TmpSup;
1063   DEBUG(dbgs() << "SRegs.4: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1064
1065   // (5) For each register R in SRegs, if any super-register of R is in SRegs,
1066   // remove R from SRegs.
1067   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1068     unsigned R = x;
1069     for (MCSuperRegIterator SR(R, TRI); SR.isValid(); ++SR) {
1070       if (!SRegs[*SR])
1071         continue;
1072       SRegs[R] = false;
1073       break;
1074     }
1075   }
1076   DEBUG(dbgs() << "SRegs.5: "; dump_registers(SRegs, *TRI); dbgs() << "\n");
1077
1078   // Now, for each register that has a fixed stack slot, create the stack
1079   // object for it.
1080   CSI.clear();
1081
1082   typedef TargetFrameLowering::SpillSlot SpillSlot;
1083   unsigned NumFixed;
1084   int MinOffset = 0;  // CS offsets are negative.
1085   const SpillSlot *FixedSlots = getCalleeSavedSpillSlots(NumFixed);
1086   for (const SpillSlot *S = FixedSlots; S != FixedSlots+NumFixed; ++S) {
1087     if (!SRegs[S->Reg])
1088       continue;
1089     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(S->Reg);
1090     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), S->Offset);
1091     MinOffset = std::min(MinOffset, S->Offset);
1092     CSI.push_back(CalleeSavedInfo(S->Reg, FI));
1093     SRegs[S->Reg] = false;
1094   }
1095
1096   // There can be some registers that don't have fixed slots. For example,
1097   // we need to store R0-R3 in functions with exception handling. For each
1098   // such register, create a non-fixed stack object.
1099   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1100     unsigned R = x;
1101     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(R);
1102     int Off = MinOffset - RC->getSize();
1103     unsigned Align = std::min(RC->getAlignment(), getStackAlignment());
1104     assert(isPowerOf2_32(Align));
1105     Off &= -Align;
1106     int FI = MFI->CreateFixedSpillStackObject(RC->getSize(), Off);
1107     MinOffset = std::min(MinOffset, Off);
1108     CSI.push_back(CalleeSavedInfo(R, FI));
1109     SRegs[R] = false;
1110   }
1111
1112   DEBUG({
1113     dbgs() << "CS information: {";
1114     for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1115       int FI = CSI[i].getFrameIdx();
1116       int Off = MFI->getObjectOffset(FI);
1117       dbgs() << ' ' << PrintReg(CSI[i].getReg(), TRI) << ":fi#" << FI << ":sp";
1118       if (Off >= 0)
1119         dbgs() << '+';
1120       dbgs() << Off;
1121     }
1122     dbgs() << " }\n";
1123   });
1124
1125 #ifndef NDEBUG
1126   // Verify that all registers were handled.
1127   bool MissedReg = false;
1128   for (int x = SRegs.find_first(); x >= 0; x = SRegs.find_next(x)) {
1129     unsigned R = x;
1130     dbgs() << PrintReg(R, TRI) << ' ';
1131     MissedReg = true;
1132   }
1133   if (MissedReg)
1134     llvm_unreachable("...there are unhandled callee-saved registers!");
1135 #endif
1136
1137   return true;
1138 }
1139
1140
1141 void HexagonFrameLowering::expandAlloca(MachineInstr *AI,
1142       const HexagonInstrInfo &HII, unsigned SP, unsigned CF) const {
1143   MachineBasicBlock &MB = *AI->getParent();
1144   DebugLoc DL = AI->getDebugLoc();
1145   unsigned A = AI->getOperand(2).getImm();
1146
1147   // Have
1148   //    Rd  = alloca Rs, #A
1149   //
1150   // If Rs and Rd are different registers, use this sequence:
1151   //    Rd  = sub(r29, Rs)
1152   //    r29 = sub(r29, Rs)
1153   //    Rd  = and(Rd, #-A)    ; if necessary
1154   //    r29 = and(r29, #-A)   ; if necessary
1155   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1156   // otherwise, do
1157   //    Rd  = sub(r29, Rs)
1158   //    Rd  = and(Rd, #-A)    ; if necessary
1159   //    r29 = Rd
1160   //    Rd  = add(Rd, #CF)    ; CF size aligned to at most A
1161
1162   MachineOperand &RdOp = AI->getOperand(0);
1163   MachineOperand &RsOp = AI->getOperand(1);
1164   unsigned Rd = RdOp.getReg(), Rs = RsOp.getReg();
1165
1166   // Rd = sub(r29, Rs)
1167   BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), Rd)
1168       .addReg(SP)
1169       .addReg(Rs);
1170   if (Rs != Rd) {
1171     // r29 = sub(r29, Rs)
1172     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_sub), SP)
1173         .addReg(SP)
1174         .addReg(Rs);
1175   }
1176   if (A > 8) {
1177     // Rd  = and(Rd, #-A)
1178     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), Rd)
1179         .addReg(Rd)
1180         .addImm(-int64_t(A));
1181     if (Rs != Rd)
1182       BuildMI(MB, AI, DL, HII.get(Hexagon::A2_andir), SP)
1183           .addReg(SP)
1184           .addImm(-int64_t(A));
1185   }
1186   if (Rs == Rd) {
1187     // r29 = Rd
1188     BuildMI(MB, AI, DL, HII.get(TargetOpcode::COPY), SP)
1189         .addReg(Rd);
1190   }
1191   if (CF > 0) {
1192     // Rd = add(Rd, #CF)
1193     BuildMI(MB, AI, DL, HII.get(Hexagon::A2_addi), Rd)
1194         .addReg(Rd)
1195         .addImm(CF);
1196   }
1197 }
1198
1199
1200 bool HexagonFrameLowering::needsAligna(const MachineFunction &MF) const {
1201   const MachineFrameInfo *MFI = MF.getFrameInfo();
1202   if (!MFI->hasVarSizedObjects())
1203     return false;
1204   unsigned MaxA = MFI->getMaxAlignment();
1205   if (MaxA <= getStackAlignment())
1206     return false;
1207   return true;
1208 }
1209
1210
1211 MachineInstr *HexagonFrameLowering::getAlignaInstr(MachineFunction &MF) const {
1212   for (auto &B : MF)
1213     for (auto &I : B)
1214       if (I.getOpcode() == Hexagon::ALIGNA)
1215         return &I;
1216   return nullptr;
1217 }
1218
1219
1220 inline static bool isOptSize(const MachineFunction &MF) {
1221   AttributeSet AF = MF.getFunction()->getAttributes();
1222   return AF.hasAttribute(AttributeSet::FunctionIndex,
1223                          Attribute::OptimizeForSize);
1224 }
1225
1226 inline static bool isMinSize(const MachineFunction &MF) {
1227   AttributeSet AF = MF.getFunction()->getAttributes();
1228   return AF.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);
1229 }
1230
1231
1232 /// Determine whether the callee-saved register saves and restores should
1233 /// be generated via inline code. If this function returns "true", inline
1234 /// code will be generated. If this function returns "false", additional
1235 /// checks are performed, which may still lead to the inline code.
1236 bool HexagonFrameLowering::shouldInlineCSR(MachineFunction &MF,
1237       const CSIVect &CSI) const {
1238   if (MF.getInfo<HexagonMachineFunctionInfo>()->hasEHReturn())
1239     return true;
1240   if (!isOptSize(MF) && !isMinSize(MF))
1241     if (MF.getTarget().getOptLevel() > CodeGenOpt::Default)
1242       return true;
1243
1244   // Check if CSI only has double registers, and if the registers form
1245   // a contiguous block starting from D8.
1246   BitVector Regs(Hexagon::NUM_TARGET_REGS);
1247   for (unsigned i = 0, n = CSI.size(); i < n; ++i) {
1248     unsigned R = CSI[i].getReg();
1249     if (!Hexagon::DoubleRegsRegClass.contains(R))
1250       return true;
1251     Regs[R] = true;
1252   }
1253   int F = Regs.find_first();
1254   if (F != Hexagon::D8)
1255     return true;
1256   while (F >= 0) {
1257     int N = Regs.find_next(F);
1258     if (N >= 0 && N != F+1)
1259       return true;
1260     F = N;
1261   }
1262
1263   return false;
1264 }
1265
1266
1267 bool HexagonFrameLowering::useSpillFunction(MachineFunction &MF,
1268       const CSIVect &CSI) const {
1269   if (shouldInlineCSR(MF, CSI))
1270     return false;
1271   unsigned NumCSI = CSI.size();
1272   if (NumCSI <= 1)
1273     return false;
1274
1275   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs
1276                                      : SpillFuncThreshold;
1277   return Threshold < NumCSI;
1278 }
1279
1280
1281 bool HexagonFrameLowering::useRestoreFunction(MachineFunction &MF,
1282       const CSIVect &CSI) const {
1283   if (shouldInlineCSR(MF, CSI))
1284     return false;
1285   unsigned NumCSI = CSI.size();
1286   unsigned Threshold = isOptSize(MF) ? SpillFuncThresholdOs-1
1287                                      : SpillFuncThreshold;
1288   return Threshold < NumCSI;
1289 }
1290