lib/Target/Hexagon/HexagonFrameLowering.cpp

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