lib/Target/ARM/ARMRegisterInfo.cpp

   1 //===- ARMRegisterInfo.cpp - ARM Register Information -----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the "Instituto Nokia de Tecnologia" and
   6 // is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  11 // This file contains the ARM implementation of the MRegisterInfo class.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ARM.h"
  16 #include "ARMAddressingModes.h"
  17 #include "ARMInstrInfo.h"
  18 #include "ARMMachineFunctionInfo.h"
  19 #include "ARMRegisterInfo.h"
  20 #include "ARMSubtarget.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/CodeGen/MachineConstantPool.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/MachineLocation.h"
  28 #include "llvm/CodeGen/RegisterScavenging.h"
  29 #include "llvm/Target/TargetFrameInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Target/TargetOptions.h"
  32 #include "llvm/ADT/BitVector.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include "llvm/Support/CommandLine.h"
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 static cl::opt<bool> EnableScavenging("enable-arm-reg-scavenging", cl::Hidden,
  40                                  cl::desc("Enable register scavenging on ARM"));
  41
  42 unsigned ARMRegisterInfo::getRegisterNumbering(unsigned RegEnum) {
  43   using namespace ARM;
  44   switch (RegEnum) {
  45   case R0:  case S0:  case D0:  return 0;
  46   case R1:  case S1:  case D1:  return 1;
  47   case R2:  case S2:  case D2:  return 2;
  48   case R3:  case S3:  case D3:  return 3;
  49   case R4:  case S4:  case D4:  return 4;
  50   case R5:  case S5:  case D5:  return 5;
  51   case R6:  case S6:  case D6:  return 6;
  52   case R7:  case S7:  case D7:  return 7;
  53   case R8:  case S8:  case D8:  return 8;
  54   case R9:  case S9:  case D9:  return 9;
  55   case R10: case S10: case D10: return 10;
  56   case R11: case S11: case D11: return 11;
  57   case R12: case S12: case D12: return 12;
  58   case SP:  case S13: case D13: return 13;
  59   case LR:  case S14: case D14: return 14;
  60   case PC:  case S15: case D15: return 15;
  61   case S16: return 16;
  62   case S17: return 17;
  63   case S18: return 18;
  64   case S19: return 19;
  65   case S20: return 20;
  66   case S21: return 21;
  67   case S22: return 22;
  68   case S23: return 23;
  69   case S24: return 24;
  70   case S25: return 25;
  71   case S26: return 26;
  72   case S27: return 27;
  73   case S28: return 28;
  74   case S29: return 29;
  75   case S30: return 30;
  76   case S31: return 31;
  77   default:
  78     assert(0 && "Unknown ARM register!");
  79     abort();
  80   }
  81 }
  82
  83 ARMRegisterInfo::ARMRegisterInfo(const TargetInstrInfo &tii,
  84                                  const ARMSubtarget &sti)
  85   : ARMGenRegisterInfo(ARM::ADJCALLSTACKDOWN, ARM::ADJCALLSTACKUP),
  86     TII(tii), STI(sti),
  87     FramePtr(STI.useThumbBacktraces() ? ARM::R7 : ARM::R11) {
  88 }
  89
  90 bool ARMRegisterInfo::spillCalleeSavedRegisters(MachineBasicBlock &MBB,
  91                                                 MachineBasicBlock::iterator MI,
  92                                 const std::vector<CalleeSavedInfo> &CSI) const {
  93   MachineFunction &MF = *MBB.getParent();
  94   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
  95   if (!AFI->isThumbFunction() || CSI.empty())
  96     return false;
  97
  98   MachineInstrBuilder MIB = BuildMI(MBB, MI, TII.get(ARM::tPUSH));
  99   for (unsigned i = CSI.size(); i != 0; --i) {
 100     unsigned Reg = CSI[i-1].getReg();
 101     // Add the callee-saved register as live-in. It's killed at the spill.
 102     MBB.addLiveIn(Reg);
 103     MIB.addReg(Reg, false/*isDef*/,false/*isImp*/,true/*isKill*/);
 104   }
 105   return true;
 106 }
 107
 108 bool ARMRegisterInfo::restoreCalleeSavedRegisters(MachineBasicBlock &MBB,
 109                                                  MachineBasicBlock::iterator MI,
 110                                 const std::vector<CalleeSavedInfo> &CSI) const {
 111   MachineFunction &MF = *MBB.getParent();
 112   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 113   if (!AFI->isThumbFunction() || CSI.empty())
 114     return false;
 115
 116   bool isVarArg = AFI->getVarArgsRegSaveSize() > 0;
 117   MachineInstr *PopMI = new MachineInstr(TII.get(ARM::tPOP));
 118   MBB.insert(MI, PopMI);
 119   for (unsigned i = CSI.size(); i != 0; --i) {
 120     unsigned Reg = CSI[i-1].getReg();
 121     if (Reg == ARM::LR) {
 122       // Special epilogue for vararg functions. See emitEpilogue
 123       if (isVarArg)
 124         continue;
 125       Reg = ARM::PC;
 126       PopMI->setInstrDescriptor(TII.get(ARM::tPOP_RET));
 127       MBB.erase(MI);
 128     }
 129     PopMI->addRegOperand(Reg, true);
 130   }
 131   return true;
 132 }
 133
 134 void ARMRegisterInfo::
 135 storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
 136                     unsigned SrcReg, int FI,
 137                     const TargetRegisterClass *RC) const {
 138   if (RC == ARM::GPRRegisterClass) {
 139     MachineFunction &MF = *MBB.getParent();
 140     ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 141     if (AFI->isThumbFunction())
 142       BuildMI(MBB, I, TII.get(ARM::tSpill)).addReg(SrcReg, false, false, true)
 143         .addFrameIndex(FI).addImm(0);
 144     else
 145       BuildMI(MBB, I, TII.get(ARM::STR)).addReg(SrcReg, false, false, true)
 146           .addFrameIndex(FI).addReg(0).addImm(0);
 147   } else if (RC == ARM::DPRRegisterClass) {
 148     BuildMI(MBB, I, TII.get(ARM::FSTD)).addReg(SrcReg, false, false, true)
 149     .addFrameIndex(FI).addImm(0);
 150   } else {
 151     assert(RC == ARM::SPRRegisterClass && "Unknown regclass!");
 152     BuildMI(MBB, I, TII.get(ARM::FSTS)).addReg(SrcReg, false, false, true)
 153       .addFrameIndex(FI).addImm(0);
 154   }
 155 }
 156
 157 void ARMRegisterInfo::
 158 loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
 159                      unsigned DestReg, int FI,
 160                      const TargetRegisterClass *RC) const {
 161   if (RC == ARM::GPRRegisterClass) {
 162     MachineFunction &MF = *MBB.getParent();
 163     ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 164     if (AFI->isThumbFunction())
 165       BuildMI(MBB, I, TII.get(ARM::tRestore), DestReg)
 166         .addFrameIndex(FI).addImm(0);
 167     else
 168       BuildMI(MBB, I, TII.get(ARM::LDR), DestReg)
 169       .addFrameIndex(FI).addReg(0).addImm(0);
 170   } else if (RC == ARM::DPRRegisterClass) {
 171     BuildMI(MBB, I, TII.get(ARM::FLDD), DestReg)
 172       .addFrameIndex(FI).addImm(0);
 173   } else {
 174     assert(RC == ARM::SPRRegisterClass && "Unknown regclass!");
 175     BuildMI(MBB, I, TII.get(ARM::FLDS), DestReg)
 176       .addFrameIndex(FI).addImm(0);
 177   }
 178 }
 179
 180 void ARMRegisterInfo::copyRegToReg(MachineBasicBlock &MBB,
 181                                    MachineBasicBlock::iterator I,
 182                                    unsigned DestReg, unsigned SrcReg,
 183                                    const TargetRegisterClass *RC) const {
 184   if (RC == ARM::GPRRegisterClass) {
 185     MachineFunction &MF = *MBB.getParent();
 186     ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 187     BuildMI(MBB, I, TII.get(AFI->isThumbFunction() ? ARM::tMOVrr : ARM::MOVrr),
 188             DestReg).addReg(SrcReg);
 189   } else if (RC == ARM::SPRRegisterClass)
 190     BuildMI(MBB, I, TII.get(ARM::FCPYS), DestReg).addReg(SrcReg);
 191   else if (RC == ARM::DPRRegisterClass)
 192     BuildMI(MBB, I, TII.get(ARM::FCPYD), DestReg).addReg(SrcReg);
 193   else
 194     abort();
 195 }
 196
 197 /// isLowRegister - Returns true if the register is low register r0-r7.
 198 ///
 199 static bool isLowRegister(unsigned Reg) {
 200   using namespace ARM;
 201   switch (Reg) {
 202   case R0:  case R1:  case R2:  case R3:
 203   case R4:  case R5:  case R6:  case R7:
 204     return true;
 205   default:
 206     return false;
 207   }
 208 }
 209
 210 MachineInstr *ARMRegisterInfo::foldMemoryOperand(MachineInstr *MI,
 211                                                  unsigned OpNum, int FI) const {
 212   unsigned Opc = MI->getOpcode();
 213   MachineInstr *NewMI = NULL;
 214   switch (Opc) {
 215   default: break;
 216   case ARM::MOVrr: {
 217     if (OpNum == 0) { // move -> store
 218       unsigned SrcReg = MI->getOperand(1).getReg();
 219       NewMI = BuildMI(TII.get(ARM::STR)).addReg(SrcReg).addFrameIndex(FI)
 220         .addReg(0).addImm(0);
 221     } else {          // move -> load
 222       unsigned DstReg = MI->getOperand(0).getReg();
 223       NewMI = BuildMI(TII.get(ARM::LDR), DstReg).addFrameIndex(FI).addReg(0)
 224         .addImm(0);
 225     }
 226     break;
 227   }
 228   case ARM::tMOVrr: {
 229     if (OpNum == 0) { // move -> store
 230       unsigned SrcReg = MI->getOperand(1).getReg();
 231       if (isPhysicalRegister(SrcReg) && !isLowRegister(SrcReg))
 232         // tSpill cannot take a high register operand.
 233         break;
 234       NewMI = BuildMI(TII.get(ARM::tSpill)).addReg(SrcReg).addFrameIndex(FI)
 235         .addImm(0);
 236     } else {          // move -> load
 237       unsigned DstReg = MI->getOperand(0).getReg();
 238       if (isPhysicalRegister(DstReg) && !isLowRegister(DstReg))
 239         // tRestore cannot target a high register operand.
 240         break;
 241       NewMI = BuildMI(TII.get(ARM::tRestore), DstReg).addFrameIndex(FI)
 242         .addImm(0);
 243     }
 244     break;
 245   }
 246   case ARM::FCPYS: {
 247     if (OpNum == 0) { // move -> store
 248       unsigned SrcReg = MI->getOperand(1).getReg();
 249       NewMI = BuildMI(TII.get(ARM::FSTS)).addReg(SrcReg).addFrameIndex(FI)
 250         .addImm(0);
 251     } else {          // move -> load
 252       unsigned DstReg = MI->getOperand(0).getReg();
 253       NewMI = BuildMI(TII.get(ARM::FLDS), DstReg).addFrameIndex(FI).addImm(0);
 254     }
 255     break;
 256   }
 257   case ARM::FCPYD: {
 258     if (OpNum == 0) { // move -> store
 259       unsigned SrcReg = MI->getOperand(1).getReg();
 260       NewMI = BuildMI(TII.get(ARM::FSTD)).addReg(SrcReg).addFrameIndex(FI)
 261         .addImm(0);
 262     } else {          // move -> load
 263       unsigned DstReg = MI->getOperand(0).getReg();
 264       NewMI = BuildMI(TII.get(ARM::FLDD), DstReg).addFrameIndex(FI).addImm(0);
 265     }
 266     break;
 267   }
 268   }
 269
 270   if (NewMI)
 271     NewMI->copyKillDeadInfo(MI);
 272   return NewMI;
 273 }
 274
 275 const unsigned* ARMRegisterInfo::getCalleeSavedRegs() const {
 276   static const unsigned CalleeSavedRegs[] = {
 277     ARM::LR, ARM::R11, ARM::R10, ARM::R9, ARM::R8,
 278     ARM::R7, ARM::R6,  ARM::R5,  ARM::R4,
 279
 280     ARM::D15, ARM::D14, ARM::D13, ARM::D12,
 281     ARM::D11, ARM::D10, ARM::D9,  ARM::D8,
 282     0
 283   };
 284
 285   static const unsigned DarwinCalleeSavedRegs[] = {
 286     ARM::LR,  ARM::R7,  ARM::R6, ARM::R5, ARM::R4,
 287     ARM::R11, ARM::R10, ARM::R9, ARM::R8,
 288
 289     ARM::D15, ARM::D14, ARM::D13, ARM::D12,
 290     ARM::D11, ARM::D10, ARM::D9,  ARM::D8,
 291     0
 292   };
 293   return STI.isTargetDarwin() ? DarwinCalleeSavedRegs : CalleeSavedRegs;
 294 }
 295
 296 const TargetRegisterClass* const *
 297 ARMRegisterInfo::getCalleeSavedRegClasses() const {
 298   static const TargetRegisterClass * const CalleeSavedRegClasses[] = {
 299     &ARM::GPRRegClass, &ARM::GPRRegClass, &ARM::GPRRegClass,
 300     &ARM::GPRRegClass, &ARM::GPRRegClass, &ARM::GPRRegClass,
 301     &ARM::GPRRegClass, &ARM::GPRRegClass, &ARM::GPRRegClass,
 302
 303     &ARM::DPRRegClass, &ARM::DPRRegClass, &ARM::DPRRegClass, &ARM::DPRRegClass,
 304     &ARM::DPRRegClass, &ARM::DPRRegClass, &ARM::DPRRegClass, &ARM::DPRRegClass,
 305     0
 306   };
 307   return CalleeSavedRegClasses;
 308 }
 309
 310 BitVector ARMRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
 311   // FIXME: avoid re-calculating this everytime.
 312   BitVector Reserved(getNumRegs());
 313   Reserved.set(ARM::SP);
 314   Reserved.set(ARM::PC);
 315   if (STI.isTargetDarwin() || hasFP(MF))
 316     Reserved.set(FramePtr);
 317   // Some targets reserve R9.
 318   if (STI.isR9Reserved())
 319     Reserved.set(ARM::R9);
 320   // At PEI time, if LR is used, it will be spilled upon entry.
 321   if (MF.getUsedPhysregs() && !MF.isPhysRegUsed((unsigned)ARM::LR))
 322     Reserved.set(ARM::LR);
 323   return Reserved;
 324 }
 325
 326 bool
 327 ARMRegisterInfo::isReservedReg(const MachineFunction &MF, unsigned Reg) const {
 328   switch (Reg) {
 329   default: break;
 330   case ARM::SP:
 331   case ARM::PC:
 332     return true;
 333   case ARM::R7:
 334   case ARM::R11:
 335     if (FramePtr == Reg && (STI.isTargetDarwin() || hasFP(MF)))
 336       return true;
 337     break;
 338   case ARM::R9:
 339     return STI.isR9Reserved();
 340   }
 341
 342   return false;
 343 }
 344
 345 bool
 346 ARMRegisterInfo::requiresRegisterScavenging(const MachineFunction &MF) const {
 347   const ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 348   return EnableScavenging && !AFI->isThumbFunction();
 349 }
 350
 351 /// hasFP - Return true if the specified function should have a dedicated frame
 352 /// pointer register.  This is true if the function has variable sized allocas
 353 /// or if frame pointer elimination is disabled.
 354 ///
 355 bool ARMRegisterInfo::hasFP(const MachineFunction &MF) const {
 356   return NoFramePointerElim || MF.getFrameInfo()->hasVarSizedObjects();
 357 }
 358
 359 /// emitARMRegPlusImmediate - Emits a series of instructions to materialize
 360 /// a destreg = basereg + immediate in ARM code.
 361 static
 362 void emitARMRegPlusImmediate(MachineBasicBlock &MBB,
 363                              MachineBasicBlock::iterator &MBBI,
 364                              unsigned DestReg, unsigned BaseReg,
 365                              int NumBytes, const TargetInstrInfo &TII) {
 366   bool isSub = NumBytes < 0;
 367   if (isSub) NumBytes = -NumBytes;
 368
 369   while (NumBytes) {
 370     unsigned RotAmt = ARM_AM::getSOImmValRotate(NumBytes);
 371     unsigned ThisVal = NumBytes & ARM_AM::rotr32(0xFF, RotAmt);
 372     assert(ThisVal && "Didn't extract field correctly");
 373
 374     // We will handle these bits from offset, clear them.
 375     NumBytes &= ~ThisVal;
 376
 377     // Get the properly encoded SOImmVal field.
 378     int SOImmVal = ARM_AM::getSOImmVal(ThisVal);
 379     assert(SOImmVal != -1 && "Bit extraction didn't work?");
 380
 381     // Build the new ADD / SUB.
 382     BuildMI(MBB, MBBI, TII.get(isSub ? ARM::SUBri : ARM::ADDri), DestReg)
 383       .addReg(BaseReg, false, false, true).addImm(SOImmVal);
 384     BaseReg = DestReg;
 385   }
 386 }
 387
 388 /// calcNumMI - Returns the number of instructions required to materialize
 389 /// the specific add / sub r, c instruction.
 390 static unsigned calcNumMI(int Opc, int ExtraOpc, unsigned Bytes,
 391                           unsigned NumBits, unsigned Scale) {
 392   unsigned NumMIs = 0;
 393   unsigned Chunk = ((1 << NumBits) - 1) * Scale;
 394
 395   if (Opc == ARM::tADDrSPi) {
 396     unsigned ThisVal = (Bytes > Chunk) ? Chunk : Bytes;
 397     Bytes -= ThisVal;
 398     NumMIs++;
 399     NumBits = 8;
 400     Scale = 1;
 401     Chunk = ((1 << NumBits) - 1) * Scale;
 402   }
 403
 404   NumMIs += Bytes / Chunk;
 405   if ((Bytes % Chunk) != 0)
 406     NumMIs++;
 407   if (ExtraOpc)
 408     NumMIs++;
 409   return NumMIs;
 410 }
 411
 412 /// emitLoadConstPool - Emits a load from constpool to materialize NumBytes
 413 /// immediate.
 414 static void emitLoadConstPool(MachineBasicBlock &MBB,
 415                               MachineBasicBlock::iterator &MBBI,
 416                               unsigned DestReg, int NumBytes,
 417                               const TargetInstrInfo &TII) {
 418   MachineFunction &MF = *MBB.getParent();
 419   MachineConstantPool *ConstantPool = MF.getConstantPool();
 420   Constant *C = ConstantInt::get(Type::Int32Ty, NumBytes);
 421   unsigned Idx = ConstantPool->getConstantPoolIndex(C, 2);
 422   BuildMI(MBB, MBBI, TII.get(ARM::tLDRpci), DestReg).addConstantPoolIndex(Idx);
 423 }
 424
 425 /// emitThumbRegPlusImmInReg - Emits a series of instructions to materialize
 426 /// a destreg = basereg + immediate in Thumb code. Materialize the immediate
 427 /// in a register using mov / mvn sequences or load the immediate from a
 428 /// constpool entry.
 429 static
 430 void emitThumbRegPlusImmInReg(MachineBasicBlock &MBB,
 431                                MachineBasicBlock::iterator &MBBI,
 432                                unsigned DestReg, unsigned BaseReg,
 433                                int NumBytes, bool CanChangeCC,
 434                                const TargetInstrInfo &TII) {
 435     bool isHigh = !isLowRegister(DestReg) ||
 436                   (BaseReg != 0 && !isLowRegister(BaseReg));
 437     bool isSub = false;
 438     // Subtract doesn't have high register version. Load the negative value
 439     // if either base or dest register is a high register. Also, if do not
 440     // issue sub as part of the sequence if condition register is to be
 441     // preserved.
 442     if (NumBytes < 0 && !isHigh && CanChangeCC) {
 443       isSub = true;
 444       NumBytes = -NumBytes;
 445     }
 446     unsigned LdReg = DestReg;
 447     if (DestReg == ARM::SP) {
 448       assert(BaseReg == ARM::SP && "Unexpected!");
 449       LdReg = ARM::R3;
 450       BuildMI(MBB, MBBI, TII.get(ARM::tMOVrr), ARM::R12)
 451         .addReg(ARM::R3, false, false, true);
 452     }
 453
 454     if (NumBytes <= 255 && NumBytes >= 0)
 455       BuildMI(MBB, MBBI, TII.get(ARM::tMOVri8), LdReg).addImm(NumBytes);
 456     else if (NumBytes < 0 && NumBytes >= -255) {
 457       BuildMI(MBB, MBBI, TII.get(ARM::tMOVri8), LdReg).addImm(NumBytes);
 458       BuildMI(MBB, MBBI, TII.get(ARM::tNEG), LdReg)
 459         .addReg(LdReg, false, false, true);
 460     } else
 461       emitLoadConstPool(MBB, MBBI, LdReg, NumBytes, TII);
 462
 463     // Emit add / sub.
 464     int Opc = (isSub) ? ARM::tSUBrr : (isHigh ? ARM::tADDhirr : ARM::tADDrr);
 465     const MachineInstrBuilder MIB = BuildMI(MBB, MBBI, TII.get(Opc), DestReg);
 466     if (DestReg == ARM::SP || isSub)
 467       MIB.addReg(BaseReg).addReg(LdReg, false, false, true);
 468     else
 469       MIB.addReg(LdReg).addReg(BaseReg, false, false, true);
 470     if (DestReg == ARM::SP)
 471       BuildMI(MBB, MBBI, TII.get(ARM::tMOVrr), ARM::R3)
 472         .addReg(ARM::R12, false, false, true);
 473 }
 474
 475 /// emitThumbRegPlusImmediate - Emits a series of instructions to materialize
 476 /// a destreg = basereg + immediate in Thumb code.
 477 static
 478 void emitThumbRegPlusImmediate(MachineBasicBlock &MBB,
 479                                MachineBasicBlock::iterator &MBBI,
 480                                unsigned DestReg, unsigned BaseReg,
 481                                int NumBytes, const TargetInstrInfo &TII) {
 482   bool isSub = NumBytes < 0;
 483   unsigned Bytes = (unsigned)NumBytes;
 484   if (isSub) Bytes = -NumBytes;
 485   bool isMul4 = (Bytes & 3) == 0;
 486   bool isTwoAddr = false;
 487   bool DstNotEqBase = false;
 488   unsigned NumBits = 1;
 489   unsigned Scale = 1;
 490   int Opc = 0;
 491   int ExtraOpc = 0;
 492
 493   if (DestReg == BaseReg && BaseReg == ARM::SP) {
 494     assert(isMul4 && "Thumb sp inc / dec size must be multiple of 4!");
 495     NumBits = 7;
 496     Scale = 4;
 497     Opc = isSub ? ARM::tSUBspi : ARM::tADDspi;
 498     isTwoAddr = true;
 499   } else if (!isSub && BaseReg == ARM::SP) {
 500     // r1 = add sp, 403
 501     // =>
 502     // r1 = add sp, 100 * 4
 503     // r1 = add r1, 3
 504     if (!isMul4) {
 505       Bytes &= ~3;
 506       ExtraOpc = ARM::tADDi3;
 507     }
 508     NumBits = 8;
 509     Scale = 4;
 510     Opc = ARM::tADDrSPi;
 511   } else {
 512     // sp = sub sp, c
 513     // r1 = sub sp, c
 514     // r8 = sub sp, c
 515     if (DestReg != BaseReg)
 516       DstNotEqBase = true;
 517     NumBits = 8;
 518     Opc = isSub ? ARM::tSUBi8 : ARM::tADDi8;
 519     isTwoAddr = true;
 520   }
 521
 522   unsigned NumMIs = calcNumMI(Opc, ExtraOpc, Bytes, NumBits, Scale);
 523   unsigned Threshold = (DestReg == ARM::SP) ? 3 : 2;
 524   if (NumMIs > Threshold) {
 525     // This will expand into too many instructions. Load the immediate from a
 526     // constpool entry.
 527     emitThumbRegPlusImmInReg(MBB, MBBI, DestReg, BaseReg, NumBytes, true, TII);
 528     return;
 529   }
 530
 531   if (DstNotEqBase) {
 532     if (isLowRegister(DestReg) && isLowRegister(BaseReg)) {
 533       // If both are low registers, emit DestReg = add BaseReg, max(Imm, 7)
 534       unsigned Chunk = (1 << 3) - 1;
 535       unsigned ThisVal = (Bytes > Chunk) ? Chunk : Bytes;
 536       Bytes -= ThisVal;
 537       BuildMI(MBB, MBBI, TII.get(isSub ? ARM::tSUBi3 : ARM::tADDi3), DestReg)
 538         .addReg(BaseReg, false, false, true).addImm(ThisVal);
 539     } else {
 540       BuildMI(MBB, MBBI, TII.get(ARM::tMOVrr), DestReg)
 541         .addReg(BaseReg, false, false, true);
 542     }
 543     BaseReg = DestReg;
 544   }
 545
 546   unsigned Chunk = ((1 << NumBits) - 1) * Scale;
 547   while (Bytes) {
 548     unsigned ThisVal = (Bytes > Chunk) ? Chunk : Bytes;
 549     Bytes -= ThisVal;
 550     ThisVal /= Scale;
 551     // Build the new tADD / tSUB.
 552     if (isTwoAddr)
 553       BuildMI(MBB, MBBI, TII.get(Opc), DestReg).addReg(DestReg).addImm(ThisVal);
 554     else {
 555       bool isKill = BaseReg != ARM::SP;
 556       BuildMI(MBB, MBBI, TII.get(Opc), DestReg)
 557         .addReg(BaseReg, false, false, isKill).addImm(ThisVal);
 558       BaseReg = DestReg;
 559
 560       if (Opc == ARM::tADDrSPi) {
 561         // r4 = add sp, imm
 562         // r4 = add r4, imm
 563         // ...
 564         NumBits = 8;
 565         Scale = 1;
 566         Chunk = ((1 << NumBits) - 1) * Scale;
 567         Opc = isSub ? ARM::tSUBi8 : ARM::tADDi8;
 568         isTwoAddr = true;
 569       }
 570     }
 571   }
 572
 573   if (ExtraOpc)
 574     BuildMI(MBB, MBBI, TII.get(ExtraOpc), DestReg)
 575       .addReg(DestReg, false, false, true)
 576       .addImm(((unsigned)NumBytes) & 3);
 577 }
 578
 579 static
 580 void emitSPUpdate(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI,
 581                   int NumBytes, bool isThumb, const TargetInstrInfo &TII) {
 582   if (isThumb)
 583     emitThumbRegPlusImmediate(MBB, MBBI, ARM::SP, ARM::SP, NumBytes, TII);
 584   else
 585     emitARMRegPlusImmediate(MBB, MBBI, ARM::SP, ARM::SP, NumBytes, TII);
 586 }
 587
 588 void ARMRegisterInfo::
 589 eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB,
 590                               MachineBasicBlock::iterator I) const {
 591   if (hasFP(MF)) {
 592     // If we have alloca, convert as follows:
 593     // ADJCALLSTACKDOWN -> sub, sp, sp, amount
 594     // ADJCALLSTACKUP   -> add, sp, sp, amount
 595     MachineInstr *Old = I;
 596     unsigned Amount = Old->getOperand(0).getImmedValue();
 597     if (Amount != 0) {
 598       ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 599       // We need to keep the stack aligned properly.  To do this, we round the
 600       // amount of space needed for the outgoing arguments up to the next
 601       // alignment boundary.
 602       unsigned Align = MF.getTarget().getFrameInfo()->getStackAlignment();
 603       Amount = (Amount+Align-1)/Align*Align;
 604
 605       // Replace the pseudo instruction with a new instruction...
 606       if (Old->getOpcode() == ARM::ADJCALLSTACKDOWN) {
 607         emitSPUpdate(MBB, I, -Amount, AFI->isThumbFunction(), TII);
 608       } else {
 609         assert(Old->getOpcode() == ARM::ADJCALLSTACKUP);
 610         emitSPUpdate(MBB, I, Amount, AFI->isThumbFunction(), TII);
 611       }
 612     }
 613   }
 614   MBB.erase(I);
 615 }
 616
 617 /// emitThumbConstant - Emit a series of instructions to materialize a
 618 /// constant.
 619 static void emitThumbConstant(MachineBasicBlock &MBB,
 620                               MachineBasicBlock::iterator &MBBI,
 621                               unsigned DestReg, int Imm,
 622                               const TargetInstrInfo &TII) {
 623   bool isSub = Imm < 0;
 624   if (isSub) Imm = -Imm;
 625
 626   int Chunk = (1 << 8) - 1;
 627   int ThisVal = (Imm > Chunk) ? Chunk : Imm;
 628   Imm -= ThisVal;
 629   BuildMI(MBB, MBBI, TII.get(ARM::tMOVri8), DestReg).addImm(ThisVal);
 630   if (Imm > 0)
 631     emitThumbRegPlusImmediate(MBB, MBBI, DestReg, DestReg, Imm, TII);
 632   if (isSub)
 633     BuildMI(MBB, MBBI, TII.get(ARM::tNEG), DestReg)
 634       .addReg(DestReg, false, false, true);
 635 }
 636
 637 /// findScratchRegister - Find a 'free' ARM register. If register scavenger
 638 /// is not being used, R12 is available. Otherwise, try for a call-clobbered
 639 /// register first and then a spilled callee-saved register if that fails.
 640 static
 641 unsigned findScratchRegister(RegScavenger *RS, const TargetRegisterClass *RC,
 642                              ARMFunctionInfo *AFI) {
 643   unsigned Reg = RS ? RS->FindUnusedReg(RC, true) : (unsigned) ARM::R12;
 644   if (Reg == 0)
 645     // Try a already spilled CS register.
 646     Reg = RS->FindUnusedReg(RC, AFI->getSpilledCSRegisters());
 647
 648   return Reg;
 649 }
 650
 651 void ARMRegisterInfo::eliminateFrameIndex(MachineBasicBlock::iterator II,
 652                                           RegScavenger *RS) const{
 653   unsigned i = 0;
 654   MachineInstr &MI = *II;
 655   MachineBasicBlock &MBB = *MI.getParent();
 656   MachineFunction &MF = *MBB.getParent();
 657   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 658   bool isThumb = AFI->isThumbFunction();
 659
 660   while (!MI.getOperand(i).isFrameIndex()) {
 661     ++i;
 662     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
 663   }
 664
 665   unsigned FrameReg = ARM::SP;
 666   int FrameIndex = MI.getOperand(i).getFrameIndex();
 667   int Offset = MF.getFrameInfo()->getObjectOffset(FrameIndex) +
 668                MF.getFrameInfo()->getStackSize();
 669
 670   if (AFI->isGPRCalleeSavedArea1Frame(FrameIndex))
 671     Offset -= AFI->getGPRCalleeSavedArea1Offset();
 672   else if (AFI->isGPRCalleeSavedArea2Frame(FrameIndex))
 673     Offset -= AFI->getGPRCalleeSavedArea2Offset();
 674   else if (AFI->isDPRCalleeSavedAreaFrame(FrameIndex))
 675     Offset -= AFI->getDPRCalleeSavedAreaOffset();
 676   else if (hasFP(MF)) {
 677     // There is alloca()'s in this function, must reference off the frame
 678     // pointer instead.
 679     FrameReg = getFrameRegister(MF);
 680     Offset -= AFI->getFramePtrSpillOffset();
 681   }
 682
 683   unsigned Opcode = MI.getOpcode();
 684   const TargetInstrDescriptor &Desc = TII.get(Opcode);
 685   unsigned AddrMode = (Desc.TSFlags & ARMII::AddrModeMask);
 686   bool isSub = false;
 687
 688   if (Opcode == ARM::ADDri) {
 689     Offset += MI.getOperand(i+1).getImm();
 690     if (Offset == 0) {
 691       // Turn it into a move.
 692       MI.setInstrDescriptor(TII.get(ARM::MOVrr));
 693       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 694       MI.RemoveOperand(i+1);
 695       return;
 696     } else if (Offset < 0) {
 697       Offset = -Offset;
 698       isSub = true;
 699       MI.setInstrDescriptor(TII.get(ARM::SUBri));
 700     }
 701
 702     // Common case: small offset, fits into instruction.
 703     int ImmedOffset = ARM_AM::getSOImmVal(Offset);
 704     if (ImmedOffset != -1) {
 705       // Replace the FrameIndex with sp / fp
 706       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 707       MI.getOperand(i+1).ChangeToImmediate(ImmedOffset);
 708       return;
 709     }
 710
 711     // Otherwise, we fallback to common code below to form the imm offset with
 712     // a sequence of ADDri instructions.  First though, pull as much of the imm
 713     // into this ADDri as possible.
 714     unsigned RotAmt = ARM_AM::getSOImmValRotate(Offset);
 715     unsigned ThisImmVal = Offset & ARM_AM::rotr32(0xFF, (32-RotAmt) & 31);
 716
 717     // We will handle these bits from offset, clear them.
 718     Offset &= ~ThisImmVal;
 719
 720     // Get the properly encoded SOImmVal field.
 721     int ThisSOImmVal = ARM_AM::getSOImmVal(ThisImmVal);
 722     assert(ThisSOImmVal != -1 && "Bit extraction didn't work?");
 723     MI.getOperand(i+1).ChangeToImmediate(ThisSOImmVal);
 724   } else if (Opcode == ARM::tADDrSPi) {
 725     Offset += MI.getOperand(i+1).getImm();
 726     assert((Offset & 3) == 0 &&
 727            "Thumb add/sub sp, #imm immediate must be multiple of 4!");
 728     if (Offset == 0) {
 729       // Turn it into a move.
 730       MI.setInstrDescriptor(TII.get(ARM::tMOVrr));
 731       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 732       MI.RemoveOperand(i+1);
 733       return;
 734     }
 735
 736     // Common case: small offset, fits into instruction.
 737     if (((Offset >> 2) & ~255U) == 0) {
 738       // Replace the FrameIndex with sp / fp
 739       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 740       MI.getOperand(i+1).ChangeToImmediate(Offset >> 2);
 741       return;
 742     }
 743
 744     unsigned DestReg = MI.getOperand(0).getReg();
 745     unsigned Bytes = (Offset > 0) ? Offset : -Offset;
 746     unsigned NumMIs = calcNumMI(Opcode, 0, Bytes, 8, 1);
 747     // MI would expand into a large number of instructions. Don't try to
 748     // simplify the immediate.
 749     if (NumMIs > 2) {
 750       emitThumbRegPlusImmediate(MBB, II, DestReg, FrameReg, Offset, TII);
 751       MBB.erase(II);
 752       return;
 753     }
 754
 755     if (Offset > 0) {
 756       // Translate r0 = add sp, imm to
 757       // r0 = add sp, 255*4
 758       // r0 = add r0, (imm - 255*4)
 759       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 760       MI.getOperand(i+1).ChangeToImmediate(255);
 761       Offset = (Offset - 255 * 4);
 762       MachineBasicBlock::iterator NII = next(II);
 763       emitThumbRegPlusImmediate(MBB, NII, DestReg, DestReg, Offset, TII);
 764     } else {
 765       // Translate r0 = add sp, -imm to
 766       // r0 = -imm (this is then translated into a series of instructons)
 767       // r0 = add r0, sp
 768       emitThumbConstant(MBB, II, DestReg, Offset, TII);
 769       MI.setInstrDescriptor(TII.get(ARM::tADDhirr));
 770       MI.getOperand(i).ChangeToRegister(DestReg, false, false, true);
 771       MI.getOperand(i+1).ChangeToRegister(FrameReg, false);
 772     }
 773     return;
 774   } else {
 775     unsigned ImmIdx = 0;
 776     int InstrOffs = 0;
 777     unsigned NumBits = 0;
 778     unsigned Scale = 1;
 779     switch (AddrMode) {
 780     case ARMII::AddrMode2: {
 781       ImmIdx = i+2;
 782       InstrOffs = ARM_AM::getAM2Offset(MI.getOperand(ImmIdx).getImm());
 783       if (ARM_AM::getAM2Op(MI.getOperand(ImmIdx).getImm()) == ARM_AM::sub)
 784         InstrOffs *= -1;
 785       NumBits = 12;
 786       break;
 787     }
 788     case ARMII::AddrMode3: {
 789       ImmIdx = i+2;
 790       InstrOffs = ARM_AM::getAM3Offset(MI.getOperand(ImmIdx).getImm());
 791       if (ARM_AM::getAM3Op(MI.getOperand(ImmIdx).getImm()) == ARM_AM::sub)
 792         InstrOffs *= -1;
 793       NumBits = 8;
 794       break;
 795     }
 796     case ARMII::AddrMode5: {
 797       ImmIdx = i+1;
 798       InstrOffs = ARM_AM::getAM5Offset(MI.getOperand(ImmIdx).getImm());
 799       if (ARM_AM::getAM5Op(MI.getOperand(ImmIdx).getImm()) == ARM_AM::sub)
 800         InstrOffs *= -1;
 801       NumBits = 8;
 802       Scale = 4;
 803       break;
 804     }
 805     case ARMII::AddrModeTs: {
 806       ImmIdx = i+1;
 807       InstrOffs = MI.getOperand(ImmIdx).getImm();
 808       NumBits = (FrameReg == ARM::SP) ? 8 : 5;
 809       Scale = 4;
 810       break;
 811     }
 812     default:
 813       assert(0 && "Unsupported addressing mode!");
 814       abort();
 815       break;
 816     }
 817
 818     Offset += InstrOffs * Scale;
 819     assert((Offset & (Scale-1)) == 0 && "Can't encode this offset!");
 820     if (Offset < 0 && !isThumb) {
 821       Offset = -Offset;
 822       isSub = true;
 823     }
 824
 825     // Common case: small offset, fits into instruction.
 826     MachineOperand &ImmOp = MI.getOperand(ImmIdx);
 827     int ImmedOffset = Offset / Scale;
 828     unsigned Mask = (1 << NumBits) - 1;
 829     if ((unsigned)Offset <= Mask * Scale) {
 830       // Replace the FrameIndex with sp
 831       MI.getOperand(i).ChangeToRegister(FrameReg, false);
 832       if (isSub)
 833         ImmedOffset |= 1 << NumBits;
 834       ImmOp.ChangeToImmediate(ImmedOffset);
 835       return;
 836     }
 837
 838     bool isThumSpillRestore = Opcode == ARM::tRestore || Opcode == ARM::tSpill;
 839     if (AddrMode == ARMII::AddrModeTs) {
 840       // Thumb tLDRspi, tSTRspi. These will change to instructions that use
 841       // a different base register.
 842       NumBits = 5;
 843       Mask = (1 << NumBits) - 1;
 844     }
 845     // If this is a thumb spill / restore, we will be using a constpool load to
 846     // materialize the offset.
 847     if (AddrMode == ARMII::AddrModeTs && isThumSpillRestore)
 848       ImmOp.ChangeToImmediate(0);
 849     else {
 850       // Otherwise, it didn't fit. Pull in what we can to simplify the immed.
 851       ImmedOffset = ImmedOffset & Mask;
 852       if (isSub)
 853         ImmedOffset |= 1 << NumBits;
 854       ImmOp.ChangeToImmediate(ImmedOffset);
 855       Offset &= ~(Mask*Scale);
 856     }
 857   }
 858
 859   // If we get here, the immediate doesn't fit into the instruction.  We folded
 860   // as much as possible above, handle the rest, providing a register that is
 861   // SP+LargeImm.
 862   assert(Offset && "This code isn't needed if offset already handled!");
 863
 864   if (isThumb) {
 865     if (TII.isLoad(Opcode)) {
 866       // Use the destination register to materialize sp + offset.
 867       unsigned TmpReg = MI.getOperand(0).getReg();
 868       bool UseRR = false;
 869       if (Opcode == ARM::tRestore) {
 870         if (FrameReg == ARM::SP)
 871           emitThumbRegPlusImmInReg(MBB, II, TmpReg, FrameReg,Offset,false,TII);
 872         else {
 873           emitLoadConstPool(MBB, II, TmpReg, Offset, TII);
 874           UseRR = true;
 875         }
 876       } else
 877         emitThumbRegPlusImmediate(MBB, II, TmpReg, FrameReg, Offset, TII);
 878       MI.setInstrDescriptor(TII.get(ARM::tLDR));
 879       MI.getOperand(i).ChangeToRegister(TmpReg, false, false, true);
 880       if (UseRR)
 881         MI.addRegOperand(FrameReg, false);  // Use [reg, reg] addrmode.
 882       else
 883         MI.addRegOperand(0, false); // tLDR has an extra register operand.
 884     } else if (TII.isStore(Opcode)) {
 885       // FIXME! This is horrific!!! We need register scavenging.
 886       // Our temporary workaround has marked r3 unavailable. Of course, r3 is
 887       // also a ABI register so it's possible that is is the register that is
 888       // being storing here. If that's the case, we do the following:
 889       // r12 = r2
 890       // Use r2 to materialize sp + offset
 891       // str r3, r2
 892       // r2 = r12
 893       unsigned ValReg = MI.getOperand(0).getReg();
 894       unsigned TmpReg = ARM::R3;
 895       bool UseRR = false;
 896       if (ValReg == ARM::R3) {
 897         BuildMI(MBB, II, TII.get(ARM::tMOVrr), ARM::R12)
 898           .addReg(ARM::R2, false, false, true);
 899         TmpReg = ARM::R2;
 900       }
 901       if (TmpReg == ARM::R3 && AFI->isR3LiveIn())
 902         BuildMI(MBB, II, TII.get(ARM::tMOVrr), ARM::R12)
 903           .addReg(ARM::R3, false, false, true);
 904       if (Opcode == ARM::tSpill) {
 905         if (FrameReg == ARM::SP)
 906           emitThumbRegPlusImmInReg(MBB, II, TmpReg, FrameReg,Offset,false,TII);
 907         else {
 908           emitLoadConstPool(MBB, II, TmpReg, Offset, TII);
 909           UseRR = true;
 910         }
 911       } else
 912         emitThumbRegPlusImmediate(MBB, II, TmpReg, FrameReg, Offset, TII);
 913       MI.setInstrDescriptor(TII.get(ARM::tSTR));
 914       MI.getOperand(i).ChangeToRegister(TmpReg, false, false, true);
 915       if (UseRR)
 916         MI.addRegOperand(FrameReg, false);  // Use [reg, reg] addrmode.
 917       else
 918         MI.addRegOperand(0, false); // tSTR has an extra register operand.
 919
 920       MachineBasicBlock::iterator NII = next(II);
 921       if (ValReg == ARM::R3)
 922         BuildMI(MBB, NII, TII.get(ARM::tMOVrr), ARM::R2)
 923           .addReg(ARM::R12, false, false, true);
 924       if (TmpReg == ARM::R3 && AFI->isR3LiveIn())
 925         BuildMI(MBB, NII, TII.get(ARM::tMOVrr), ARM::R3)
 926           .addReg(ARM::R12, false, false, true);
 927     } else
 928       assert(false && "Unexpected opcode!");
 929   } else {
 930     // Insert a set of r12 with the full address: r12 = sp + offset
 931     // If the offset we have is too large to fit into the instruction, we need
 932     // to form it with a series of ADDri's.  Do this by taking 8-bit chunks
 933     // out of 'Offset'.
 934     unsigned ScratchReg = findScratchRegister(RS, &ARM::GPRRegClass, AFI);
 935     if (ScratchReg == 0)
 936       // No register is "free". Scavenge a register.
 937       ScratchReg = RS->scavengeRegister(&ARM::GPRRegClass, II);
 938     emitARMRegPlusImmediate(MBB, II, ScratchReg, FrameReg,
 939                             isSub ? -Offset : Offset, TII);
 940     MI.getOperand(i).ChangeToRegister(ScratchReg, false, false, true);
 941   }
 942 }
 943
 944 static unsigned estimateStackSize(MachineFunction &MF, MachineFrameInfo *MFI) {
 945   const MachineFrameInfo *FFI = MF.getFrameInfo();
 946   int Offset = 0;
 947   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
 948     int FixedOff = -FFI->getObjectOffset(i);
 949     if (FixedOff > Offset) Offset = FixedOff;
 950   }
 951   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
 952     Offset += FFI->getObjectSize(i);
 953     unsigned Align = FFI->getObjectAlignment(i);
 954     // Adjust to alignment boundary
 955     Offset = (Offset+Align-1)/Align*Align;
 956   }
 957   return (unsigned)Offset;
 958 }
 959
 960 void
 961 ARMRegisterInfo::processFunctionBeforeCalleeSavedScan(MachineFunction &MF,
 962                                                       RegScavenger *RS) const {
 963   // This tells PEI to spill the FP as if it is any other callee-save register
 964   // to take advantage the eliminateFrameIndex machinery. This also ensures it
 965   // is spilled in the order specified by getCalleeSavedRegs() to make it easier
 966   // to combine multiple loads / stores.
 967   bool CanEliminateFrame = true;
 968   bool CS1Spilled = false;
 969   bool LRSpilled = false;
 970   unsigned NumGPRSpills = 0;
 971   SmallVector<unsigned, 4> UnspilledCS1GPRs;
 972   SmallVector<unsigned, 4> UnspilledCS2GPRs;
 973   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
 974
 975   // Don't spill FP if the frame can be eliminated. This is determined
 976   // by scanning the callee-save registers to see if any is used.
 977   const unsigned *CSRegs = getCalleeSavedRegs();
 978   const TargetRegisterClass* const *CSRegClasses = getCalleeSavedRegClasses();
 979   for (unsigned i = 0; CSRegs[i]; ++i) {
 980     unsigned Reg = CSRegs[i];
 981     bool Spilled = false;
 982     if (MF.isPhysRegUsed(Reg)) {
 983       AFI->setCSRegisterIsSpilled(Reg);
 984       Spilled = true;
 985       CanEliminateFrame = false;
 986     } else {
 987       // Check alias registers too.
 988       for (const unsigned *Aliases = getAliasSet(Reg); *Aliases; ++Aliases) {
 989         if (MF.isPhysRegUsed(*Aliases)) {
 990           Spilled = true;
 991           CanEliminateFrame = false;
 992         }
 993       }
 994     }
 995
 996     if (CSRegClasses[i] == &ARM::GPRRegClass) {
 997       if (Spilled) {
 998         NumGPRSpills++;
 999
1000         if (!STI.isTargetDarwin()) {
1001           if (Reg == ARM::LR)
1002             LRSpilled = true;
1003           else
1004             CS1Spilled = true;
1005           continue;
1006         }
1007
1008         // Keep track if LR and any of R4, R5, R6, and R7 is spilled.
1009         switch (Reg) {
1010         case ARM::LR:
1011           LRSpilled = true;
1012           // Fallthrough
1013         case ARM::R4:
1014         case ARM::R5:
1015         case ARM::R6:
1016         case ARM::R7:
1017           CS1Spilled = true;
1018           break;
1019         default:
1020           break;
1021         }
1022       } else {
1023         if (!STI.isTargetDarwin()) {
1024           UnspilledCS1GPRs.push_back(Reg);
1025           continue;
1026         }
1027
1028         switch (Reg) {
1029         case ARM::R4:
1030         case ARM::R5:
1031         case ARM::R6:
1032         case ARM::R7:
1033         case ARM::LR:
1034           UnspilledCS1GPRs.push_back(Reg);
1035           break;
1036         default:
1037           UnspilledCS2GPRs.push_back(Reg);
1038           break;
1039         }
1040       }
1041     }
1042   }
1043
1044   bool ForceLRSpill = false;
1045   if (!LRSpilled && AFI->isThumbFunction()) {
1046     unsigned FnSize = ARM::GetFunctionSize(MF);
1047     // Force LR to be spilled if the Thumb function size is > 2048. This enables
1048     // use of BL to implement far jump. If it turns out that it's not needed
1049     // then the branch fix up path will undo it.
1050     if (FnSize >= (1 << 11)) {
1051       CanEliminateFrame = false;
1052       ForceLRSpill = true;
1053     }
1054   }
1055
1056   bool ExtraCSSpill = false;
1057   if (!CanEliminateFrame || hasFP(MF)) {
1058     AFI->setHasStackFrame(true);
1059
1060     // If LR is not spilled, but at least one of R4, R5, R6, and R7 is spilled.
1061     // Spill LR as well so we can fold BX_RET to the registers restore (LDM).
1062     if (!LRSpilled && CS1Spilled) {
1063       MF.changePhyRegUsed(ARM::LR, true);
1064       AFI->setCSRegisterIsSpilled(ARM::LR);
1065       NumGPRSpills++;
1066       UnspilledCS1GPRs.erase(std::find(UnspilledCS1GPRs.begin(),
1067                                     UnspilledCS1GPRs.end(), (unsigned)ARM::LR));
1068       ForceLRSpill = false;
1069       ExtraCSSpill = true;
1070     }
1071
1072     // Darwin ABI requires FP to point to the stack slot that contains the
1073     // previous FP.
1074     if (STI.isTargetDarwin() || hasFP(MF)) {
1075       MF.changePhyRegUsed(FramePtr, true);
1076       NumGPRSpills++;
1077     }
1078
1079     // If stack and double are 8-byte aligned and we are spilling an odd number
1080     // of GPRs. Spill one extra callee save GPR so we won't have to pad between
1081     // the integer and double callee save areas.
1082     unsigned TargetAlign = MF.getTarget().getFrameInfo()->getStackAlignment();
1083     if (TargetAlign == 8 && (NumGPRSpills & 1)) {
1084       if (CS1Spilled && !UnspilledCS1GPRs.empty()) {
1085         unsigned Reg = UnspilledCS1GPRs.front();
1086         MF.changePhyRegUsed(Reg, true);
1087         AFI->setCSRegisterIsSpilled(Reg);
1088         if (!isReservedReg(MF, Reg))
1089           ExtraCSSpill = true;
1090       } else if (!UnspilledCS2GPRs.empty()) {
1091         unsigned Reg = UnspilledCS2GPRs.front();
1092         MF.changePhyRegUsed(Reg, true);
1093         AFI->setCSRegisterIsSpilled(Reg);
1094         if (!isReservedReg(MF, Reg))
1095           ExtraCSSpill = true;
1096       }
1097     }
1098
1099     // Estimate if we might need to scavenge a register at some point in order
1100     // to materialize a stack offset. If so, either spill one additiona
1101     // callee-saved register or reserve a special spill slot to facilitate
1102     // register scavenging.
1103     if (RS && !ExtraCSSpill && !AFI->isThumbFunction()) {
1104       MachineFrameInfo  *MFI = MF.getFrameInfo();
1105       unsigned Size = estimateStackSize(MF, MFI);
1106       unsigned Limit = (1 << 12) - 1;
1107       for (MachineFunction::iterator BB = MF.begin(),E = MF.end();BB != E; ++BB)
1108         for (MachineBasicBlock::iterator I= BB->begin(); I != BB->end(); ++I) {
1109           for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1110             if (I->getOperand(i).isFrameIndex()) {
1111               unsigned Opcode = I->getOpcode();
1112               const TargetInstrDescriptor &Desc = TII.get(Opcode);
1113               unsigned AddrMode = (Desc.TSFlags & ARMII::AddrModeMask);
1114               if (AddrMode == ARMII::AddrMode3) {
1115                 Limit = (1 << 8) - 1;
1116                 goto DoneEstimating;
1117               } else if (AddrMode == ARMII::AddrMode5) {
1118                 Limit = ((1 << 8) - 1) * 4;
1119                 goto DoneEstimating;
1120               }
1121             }
1122         }
1123     DoneEstimating:
1124       if (Size >= Limit) {
1125         // If any non-reserved CS register isn't spilled, just spill one or two
1126         // extra. That should take care of it!
1127         unsigned NumExtras = TargetAlign / 4;
1128         SmallVector<unsigned, 2> Extras;
1129         while (NumExtras && !UnspilledCS1GPRs.empty()) {
1130           unsigned Reg = UnspilledCS1GPRs.back();
1131           UnspilledCS1GPRs.pop_back();
1132           if (!isReservedReg(MF, Reg)) {
1133             Extras.push_back(Reg);
1134             NumExtras--;
1135           }
1136         }
1137         while (NumExtras && !UnspilledCS2GPRs.empty()) {
1138           unsigned Reg = UnspilledCS2GPRs.back();
1139           UnspilledCS2GPRs.pop_back();
1140           if (!isReservedReg(MF, Reg)) {
1141             Extras.push_back(Reg);
1142             NumExtras--;
1143           }
1144         }
1145         if (Extras.size() && NumExtras == 0) {
1146           for (unsigned i = 0, e = Extras.size(); i != e; ++i) {
1147             MF.changePhyRegUsed(Extras[i], true);
1148             AFI->setCSRegisterIsSpilled(Extras[i]);
1149           }
1150         } else {
1151           // Reserve a slot closest to SP or frame pointer.
1152           const TargetRegisterClass *RC = &ARM::GPRRegClass;
1153           RS->setScavengingFrameIndex(MFI->CreateStackObject(RC->getSize(),
1154                                                            RC->getAlignment()));
1155         }
1156       }
1157     }
1158   }
1159
1160   if (ForceLRSpill) {
1161     MF.changePhyRegUsed(ARM::LR, true);
1162     AFI->setCSRegisterIsSpilled(ARM::LR);
1163     AFI->setLRIsSpilledForFarJump(true);
1164   }
1165 }
1166
1167 /// Move iterator pass the next bunch of callee save load / store ops for
1168 /// the particular spill area (1: integer area 1, 2: integer area 2,
1169 /// 3: fp area, 0: don't care).
1170 static void movePastCSLoadStoreOps(MachineBasicBlock &MBB,
1171                                    MachineBasicBlock::iterator &MBBI,
1172                                    int Opc, unsigned Area,
1173                                    const ARMSubtarget &STI) {
1174   while (MBBI != MBB.end() &&
1175          MBBI->getOpcode() == Opc && MBBI->getOperand(1).isFrameIndex()) {
1176     if (Area != 0) {
1177       bool Done = false;
1178       unsigned Category = 0;
1179       switch (MBBI->getOperand(0).getReg()) {
1180       case ARM::R4:  case ARM::R5:  case ARM::R6: case ARM::R7:
1181       case ARM::LR:
1182         Category = 1;
1183         break;
1184       case ARM::R8:  case ARM::R9:  case ARM::R10: case ARM::R11:
1185         Category = STI.isTargetDarwin() ? 2 : 1;
1186         break;
1187       case ARM::D8:  case ARM::D9:  case ARM::D10: case ARM::D11:
1188       case ARM::D12: case ARM::D13: case ARM::D14: case ARM::D15:
1189         Category = 3;
1190         break;
1191       default:
1192         Done = true;
1193         break;
1194       }
1195       if (Done || Category != Area)
1196         break;
1197     }
1198
1199     ++MBBI;
1200   }
1201 }
1202
1203 void ARMRegisterInfo::emitPrologue(MachineFunction &MF) const {
1204   MachineBasicBlock &MBB = MF.front();
1205   MachineBasicBlock::iterator MBBI = MBB.begin();
1206   MachineFrameInfo  *MFI = MF.getFrameInfo();
1207   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
1208   bool isThumb = AFI->isThumbFunction();
1209   unsigned VARegSaveSize = AFI->getVarArgsRegSaveSize();
1210   unsigned Align = MF.getTarget().getFrameInfo()->getStackAlignment();
1211   unsigned NumBytes = MFI->getStackSize();
1212   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
1213
1214   if (isThumb) {
1215     // Check if R3 is live in. It might have to be used as a scratch register.
1216     for (MachineFunction::livein_iterator I=MF.livein_begin(),E=MF.livein_end();
1217          I != E; ++I) {
1218       if ((*I).first == ARM::R3) {
1219         AFI->setR3IsLiveIn(true);
1220         break;
1221       }
1222     }
1223
1224     // Thumb add/sub sp, imm8 instructions implicitly multiply the offset by 4.
1225     NumBytes = (NumBytes + 3) & ~3;
1226     MFI->setStackSize(NumBytes);
1227   }
1228
1229   // Determine the sizes of each callee-save spill areas and record which frame
1230   // belongs to which callee-save spill areas.
1231   unsigned GPRCS1Size = 0, GPRCS2Size = 0, DPRCSSize = 0;
1232   int FramePtrSpillFI = 0;
1233
1234   if (VARegSaveSize)
1235     emitSPUpdate(MBB, MBBI, -VARegSaveSize, isThumb, TII);
1236
1237   if (!AFI->hasStackFrame()) {
1238     if (NumBytes != 0)
1239       emitSPUpdate(MBB, MBBI, -NumBytes, isThumb, TII);
1240     return;
1241   }
1242
1243   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
1244     unsigned Reg = CSI[i].getReg();
1245     int FI = CSI[i].getFrameIdx();
1246     switch (Reg) {
1247     case ARM::R4:
1248     case ARM::R5:
1249     case ARM::R6:
1250     case ARM::R7:
1251     case ARM::LR:
1252       if (Reg == FramePtr)
1253         FramePtrSpillFI = FI;
1254       AFI->addGPRCalleeSavedArea1Frame(FI);
1255       GPRCS1Size += 4;
1256       break;
1257     case ARM::R8:
1258     case ARM::R9:
1259     case ARM::R10:
1260     case ARM::R11:
1261       if (Reg == FramePtr)
1262         FramePtrSpillFI = FI;
1263       if (STI.isTargetDarwin()) {
1264         AFI->addGPRCalleeSavedArea2Frame(FI);
1265         GPRCS2Size += 4;
1266       } else {
1267         AFI->addGPRCalleeSavedArea1Frame(FI);
1268         GPRCS1Size += 4;
1269       }
1270       break;
1271     default:
1272       AFI->addDPRCalleeSavedAreaFrame(FI);
1273       DPRCSSize += 8;
1274     }
1275   }
1276
1277   if (Align == 8 && (GPRCS1Size & 7) != 0)
1278     // Pad CS1 to ensure proper alignment.
1279     GPRCS1Size += 4;
1280
1281   if (!isThumb) {
1282     // Build the new SUBri to adjust SP for integer callee-save spill area 1.
1283     emitSPUpdate(MBB, MBBI, -GPRCS1Size, isThumb, TII);
1284     movePastCSLoadStoreOps(MBB, MBBI, ARM::STR, 1, STI);
1285   } else if (MBBI != MBB.end() && MBBI->getOpcode() == ARM::tPUSH)
1286     ++MBBI;
1287
1288   // Darwin ABI requires FP to point to the stack slot that contains the
1289   // previous FP.
1290   if (STI.isTargetDarwin() || hasFP(MF))
1291     BuildMI(MBB, MBBI, TII.get(isThumb ? ARM::tADDrSPi : ARM::ADDri), FramePtr)
1292       .addFrameIndex(FramePtrSpillFI).addImm(0);
1293
1294   if (!isThumb) {
1295     // Build the new SUBri to adjust SP for integer callee-save spill area 2.
1296     emitSPUpdate(MBB, MBBI, -GPRCS2Size, false, TII);
1297
1298     // Build the new SUBri to adjust SP for FP callee-save spill area.
1299     movePastCSLoadStoreOps(MBB, MBBI, ARM::STR, 2, STI);
1300     emitSPUpdate(MBB, MBBI, -DPRCSSize, false, TII);
1301   }
1302
1303   // Determine starting offsets of spill areas.
1304   unsigned DPRCSOffset  = NumBytes - (GPRCS1Size + GPRCS2Size + DPRCSSize);
1305   unsigned GPRCS2Offset = DPRCSOffset + DPRCSSize;
1306   unsigned GPRCS1Offset = GPRCS2Offset + GPRCS2Size;
1307   AFI->setFramePtrSpillOffset(MFI->getObjectOffset(FramePtrSpillFI) + NumBytes);
1308   AFI->setGPRCalleeSavedArea1Offset(GPRCS1Offset);
1309   AFI->setGPRCalleeSavedArea2Offset(GPRCS2Offset);
1310   AFI->setDPRCalleeSavedAreaOffset(DPRCSOffset);
1311
1312   NumBytes = DPRCSOffset;
1313   if (NumBytes) {
1314     // Insert it after all the callee-save spills.
1315     if (!isThumb)
1316       movePastCSLoadStoreOps(MBB, MBBI, ARM::FSTD, 3, STI);
1317     emitSPUpdate(MBB, MBBI, -NumBytes, isThumb, TII);
1318   }
1319
1320   AFI->setGPRCalleeSavedArea1Size(GPRCS1Size);
1321   AFI->setGPRCalleeSavedArea2Size(GPRCS2Size);
1322   AFI->setDPRCalleeSavedAreaSize(DPRCSSize);
1323 }
1324
1325 static bool isCalleeSavedRegister(unsigned Reg, const unsigned *CSRegs) {
1326   for (unsigned i = 0; CSRegs[i]; ++i)
1327     if (Reg == CSRegs[i])
1328       return true;
1329   return false;
1330 }
1331
1332 static bool isCSRestore(MachineInstr *MI, const unsigned *CSRegs) {
1333   return ((MI->getOpcode() == ARM::FLDD ||
1334            MI->getOpcode() == ARM::LDR  ||
1335            MI->getOpcode() == ARM::tRestore) &&
1336           MI->getOperand(1).isFrameIndex() &&
1337           isCalleeSavedRegister(MI->getOperand(0).getReg(), CSRegs));
1338 }
1339
1340 void ARMRegisterInfo::emitEpilogue(MachineFunction &MF,
1341                                    MachineBasicBlock &MBB) const {
1342   MachineBasicBlock::iterator MBBI = prior(MBB.end());
1343   assert((MBBI->getOpcode() == ARM::BX_RET ||
1344           MBBI->getOpcode() == ARM::tBX_RET ||
1345           MBBI->getOpcode() == ARM::tPOP_RET) &&
1346          "Can only insert epilog into returning blocks");
1347
1348   MachineFrameInfo *MFI = MF.getFrameInfo();
1349   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
1350   bool isThumb = AFI->isThumbFunction();
1351   unsigned VARegSaveSize = AFI->getVarArgsRegSaveSize();
1352   int NumBytes = (int)MFI->getStackSize();
1353   if (!AFI->hasStackFrame()) {
1354     if (NumBytes != 0)
1355       emitSPUpdate(MBB, MBBI, NumBytes, isThumb, TII);
1356   } else {
1357     // Unwind MBBI to point to first LDR / FLDD.
1358     const unsigned *CSRegs = getCalleeSavedRegs();
1359     if (MBBI != MBB.begin()) {
1360       do
1361         --MBBI;
1362       while (MBBI != MBB.begin() && isCSRestore(MBBI, CSRegs));
1363       if (!isCSRestore(MBBI, CSRegs))
1364         ++MBBI;
1365     }
1366
1367     // Move SP to start of FP callee save spill area.
1368     NumBytes -= (AFI->getGPRCalleeSavedArea1Size() +
1369                  AFI->getGPRCalleeSavedArea2Size() +
1370                  AFI->getDPRCalleeSavedAreaSize());
1371     if (isThumb) {
1372       if (hasFP(MF)) {
1373         NumBytes = AFI->getFramePtrSpillOffset() - NumBytes;
1374         // Reset SP based on frame pointer only if the stack frame extends beyond
1375         // frame pointer stack slot or target is ELF and the function has FP.
1376         if (NumBytes)
1377           emitThumbRegPlusImmediate(MBB, MBBI, ARM::SP, FramePtr, -NumBytes, TII);
1378         else
1379           BuildMI(MBB, MBBI, TII.get(ARM::tMOVrr), ARM::SP).addReg(FramePtr);
1380       } else {
1381         if (MBBI->getOpcode() == ARM::tBX_RET &&
1382             &MBB.front() != MBBI &&
1383             prior(MBBI)->getOpcode() == ARM::tPOP) {
1384           MachineBasicBlock::iterator PMBBI = prior(MBBI);
1385           emitSPUpdate(MBB, PMBBI, NumBytes, isThumb, TII);
1386         } else
1387           emitSPUpdate(MBB, MBBI, NumBytes, isThumb, TII);
1388       }
1389     } else {
1390       // Darwin ABI requires FP to point to the stack slot that contains the
1391       // previous FP.
1392       if ((STI.isTargetDarwin() && NumBytes) || hasFP(MF)) {
1393         NumBytes = AFI->getFramePtrSpillOffset() - NumBytes;
1394         // Reset SP based on frame pointer only if the stack frame extends beyond
1395         // frame pointer stack slot or target is ELF and the function has FP.
1396         if (AFI->getGPRCalleeSavedArea2Size() ||
1397             AFI->getDPRCalleeSavedAreaSize()  ||
1398             AFI->getDPRCalleeSavedAreaOffset()||
1399             hasFP(MF))
1400           if (NumBytes)
1401             BuildMI(MBB, MBBI, TII.get(ARM::SUBri), ARM::SP).addReg(FramePtr)
1402               .addImm(NumBytes);
1403           else
1404             BuildMI(MBB, MBBI, TII.get(ARM::MOVrr), ARM::SP).addReg(FramePtr);
1405       } else if (NumBytes) {
1406         emitSPUpdate(MBB, MBBI, NumBytes, false, TII);
1407       }
1408
1409       // Move SP to start of integer callee save spill area 2.
1410       movePastCSLoadStoreOps(MBB, MBBI, ARM::FLDD, 3, STI);
1411       emitSPUpdate(MBB, MBBI, AFI->getDPRCalleeSavedAreaSize(), false, TII);
1412
1413       // Move SP to start of integer callee save spill area 1.
1414       movePastCSLoadStoreOps(MBB, MBBI, ARM::LDR, 2, STI);
1415       emitSPUpdate(MBB, MBBI, AFI->getGPRCalleeSavedArea2Size(), false, TII);
1416
1417       // Move SP to SP upon entry to the function.
1418       movePastCSLoadStoreOps(MBB, MBBI, ARM::LDR, 1, STI);
1419       emitSPUpdate(MBB, MBBI, AFI->getGPRCalleeSavedArea1Size(), false, TII);
1420     }
1421   }
1422
1423   if (VARegSaveSize) {
1424     if (isThumb)
1425       // Epilogue for vararg functions: pop LR to R3 and branch off it.
1426       // FIXME: Verify this is still ok when R3 is no longer being reserved.
1427       BuildMI(MBB, MBBI, TII.get(ARM::tPOP)).addReg(ARM::R3);
1428
1429     emitSPUpdate(MBB, MBBI, VARegSaveSize, isThumb, TII);
1430
1431     if (isThumb) {
1432       BuildMI(MBB, MBBI, TII.get(ARM::tBX_RET_vararg)).addReg(ARM::R3);
1433       MBB.erase(MBBI);
1434     }
1435   }
1436 }
1437
1438 unsigned ARMRegisterInfo::getRARegister() const {
1439   return ARM::LR;
1440 }
1441
1442 unsigned ARMRegisterInfo::getFrameRegister(MachineFunction &MF) const {
1443   return STI.useThumbBacktraces() ? ARM::R7 : ARM::R11;
1444 }
1445
1446 unsigned ARMRegisterInfo::getEHExceptionRegister() const {
1447   assert(0 && "What is the exception register");
1448   return 0;
1449 }
1450
1451 unsigned ARMRegisterInfo::getEHHandlerRegister() const {
1452   assert(0 && "What is the exception handler register");
1453   return 0;
1454 }
1455
1456 #include "ARMGenRegisterInfo.inc"
1457