contrib/llvm/lib/Target/Sparc/DelaySlotFiller.cpp

   1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===//
   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 // This is a simple local pass that attempts to fill delay slots with useful
  11 // instructions. If no instructions can be moved into the delay slot, then a
  12 // NOP is placed.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "Sparc.h"
  16 #include "SparcSubtarget.h"
  17 #include "llvm/ADT/SmallSet.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineInstrBuilder.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/TargetInstrInfo.h"
  23 #include "llvm/CodeGen/TargetRegisterInfo.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Target/TargetMachine.h"
  26
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "delay-slot-filler"
  30
  31 STATISTIC(FilledSlots, "Number of delay slots filled");
  32
  33 static cl::opt<bool> DisableDelaySlotFiller(
  34   "disable-sparc-delay-filler",
  35   cl::init(false),
  36   cl::desc("Disable the Sparc delay slot filler."),
  37   cl::Hidden);
  38
  39 namespace {
  40   struct Filler : public MachineFunctionPass {
  41     const SparcSubtarget *Subtarget;
  42
  43     static char ID;
  44     Filler() : MachineFunctionPass(ID) {}
  45
  46     StringRef getPassName() const override { return "SPARC Delay Slot Filler"; }
  47
  48     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
  49     bool runOnMachineFunction(MachineFunction &F) override {
  50       bool Changed = false;
  51       Subtarget = &F.getSubtarget<SparcSubtarget>();
  52
  53       // This pass invalidates liveness information when it reorders
  54       // instructions to fill delay slot.
  55       F.getRegInfo().invalidateLiveness();
  56
  57       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
  58            FI != FE; ++FI)
  59         Changed |= runOnMachineBasicBlock(*FI);
  60       return Changed;
  61     }
  62
  63     MachineFunctionProperties getRequiredProperties() const override {
  64       return MachineFunctionProperties().set(
  65           MachineFunctionProperties::Property::NoVRegs);
  66     }
  67
  68     void insertCallDefsUses(MachineBasicBlock::iterator MI,
  69                             SmallSet<unsigned, 32>& RegDefs,
  70                             SmallSet<unsigned, 32>& RegUses);
  71
  72     void insertDefsUses(MachineBasicBlock::iterator MI,
  73                         SmallSet<unsigned, 32>& RegDefs,
  74                         SmallSet<unsigned, 32>& RegUses);
  75
  76     bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
  77                     unsigned Reg);
  78
  79     bool delayHasHazard(MachineBasicBlock::iterator candidate,
  80                         bool &sawLoad, bool &sawStore,
  81                         SmallSet<unsigned, 32> &RegDefs,
  82                         SmallSet<unsigned, 32> &RegUses);
  83
  84     MachineBasicBlock::iterator
  85     findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
  86
  87     bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
  88
  89     bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
  90                                        MachineBasicBlock::iterator MBBI);
  91
  92   };
  93   char Filler::ID = 0;
  94 } // end of anonymous namespace
  95
  96 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
  97 /// slots in Sparc MachineFunctions
  98 ///
  99 FunctionPass *llvm::createSparcDelaySlotFillerPass() {
 100   return new Filler;
 101 }
 102
 103
 104 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 105 /// We assume there is only one delay slot per delayed instruction.
 106 ///
 107 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 108   bool Changed = false;
 109   Subtarget = &MBB.getParent()->getSubtarget<SparcSubtarget>();
 110   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
 111
 112   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
 113     MachineBasicBlock::iterator MI = I;
 114     ++I;
 115
 116     // If MI is restore, try combining it with previous inst.
 117     if (!DisableDelaySlotFiller &&
 118         (MI->getOpcode() == SP::RESTORErr
 119          || MI->getOpcode() == SP::RESTOREri)) {
 120       Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
 121       continue;
 122     }
 123
 124     // TODO: If we ever want to support v7, this needs to be extended
 125     // to cover all floating point operations.
 126     if (!Subtarget->isV9() &&
 127         (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD
 128          || MI->getOpcode() == SP::FCMPQ)) {
 129       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
 130       Changed = true;
 131       continue;
 132     }
 133
 134     // If MI has no delay slot, skip.
 135     if (!MI->hasDelaySlot())
 136       continue;
 137
 138     MachineBasicBlock::iterator D = MBB.end();
 139
 140     if (!DisableDelaySlotFiller)
 141       D = findDelayInstr(MBB, MI);
 142
 143     ++FilledSlots;
 144     Changed = true;
 145
 146     if (D == MBB.end())
 147       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
 148     else
 149       MBB.splice(I, &MBB, D);
 150
 151     unsigned structSize = 0;
 152     if (needsUnimp(MI, structSize)) {
 153       MachineBasicBlock::iterator J = MI;
 154       ++J; // skip the delay filler.
 155       assert (J != MBB.end() && "MI needs a delay instruction.");
 156       BuildMI(MBB, ++J, MI->getDebugLoc(),
 157               TII->get(SP::UNIMP)).addImm(structSize);
 158       // Bundle the delay filler and unimp with the instruction.
 159       MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J);
 160     } else {
 161       MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I);
 162     }
 163   }
 164   return Changed;
 165 }
 166
 167 MachineBasicBlock::iterator
 168 Filler::findDelayInstr(MachineBasicBlock &MBB,
 169                        MachineBasicBlock::iterator slot)
 170 {
 171   SmallSet<unsigned, 32> RegDefs;
 172   SmallSet<unsigned, 32> RegUses;
 173   bool sawLoad = false;
 174   bool sawStore = false;
 175
 176   if (slot == MBB.begin())
 177     return MBB.end();
 178
 179   if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL)
 180     return MBB.end();
 181
 182   if (slot->getOpcode() == SP::RETL) {
 183     MachineBasicBlock::iterator J = slot;
 184     --J;
 185
 186     if (J->getOpcode() == SP::RESTORErr
 187         || J->getOpcode() == SP::RESTOREri) {
 188       // change retl to ret.
 189       slot->setDesc(Subtarget->getInstrInfo()->get(SP::RET));
 190       return J;
 191     }
 192   }
 193
 194   // Call's delay filler can def some of call's uses.
 195   if (slot->isCall())
 196     insertCallDefsUses(slot, RegDefs, RegUses);
 197   else
 198     insertDefsUses(slot, RegDefs, RegUses);
 199
 200   bool done = false;
 201
 202   MachineBasicBlock::iterator I = slot;
 203
 204   while (!done) {
 205     done = (I == MBB.begin());
 206
 207     if (!done)
 208       --I;
 209
 210     // skip debug instruction
 211     if (I->isDebugInstr())
 212       continue;
 213
 214     if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isPosition() ||
 215         I->hasDelaySlot() || I->isBundledWithSucc())
 216       break;
 217
 218     if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
 219       insertDefsUses(I, RegDefs, RegUses);
 220       continue;
 221     }
 222
 223     return I;
 224   }
 225   return MBB.end();
 226 }
 227
 228 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
 229                             bool &sawLoad,
 230                             bool &sawStore,
 231                             SmallSet<unsigned, 32> &RegDefs,
 232                             SmallSet<unsigned, 32> &RegUses)
 233 {
 234
 235   if (candidate->isImplicitDef() || candidate->isKill())
 236     return true;
 237
 238   if (candidate->mayLoad()) {
 239     sawLoad = true;
 240     if (sawStore)
 241       return true;
 242   }
 243
 244   if (candidate->mayStore()) {
 245     if (sawStore)
 246       return true;
 247     sawStore = true;
 248     if (sawLoad)
 249       return true;
 250   }
 251
 252   for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
 253     const MachineOperand &MO = candidate->getOperand(i);
 254     if (!MO.isReg())
 255       continue; // skip
 256
 257     unsigned Reg = MO.getReg();
 258
 259     if (MO.isDef()) {
 260       // check whether Reg is defined or used before delay slot.
 261       if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
 262         return true;
 263     }
 264     if (MO.isUse()) {
 265       // check whether Reg is defined before delay slot.
 266       if (IsRegInSet(RegDefs, Reg))
 267         return true;
 268     }
 269   }
 270
 271   unsigned Opcode = candidate->getOpcode();
 272   // LD and LDD may have NOPs inserted afterwards in the case of some LEON
 273   // processors, so we can't use the delay slot if this feature is switched-on.
 274   if (Subtarget->insertNOPLoad()
 275       &&
 276       Opcode >=  SP::LDDArr && Opcode <= SP::LDrr)
 277     return true;
 278
 279   // Same as above for FDIV and FSQRT on some LEON processors.
 280   if (Subtarget->fixAllFDIVSQRT()
 281       &&
 282       Opcode >=  SP::FDIVD && Opcode <= SP::FSQRTD)
 283     return true;
 284
 285
 286   return false;
 287 }
 288
 289
 290 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
 291                                 SmallSet<unsigned, 32>& RegDefs,
 292                                 SmallSet<unsigned, 32>& RegUses)
 293 {
 294   // Call defines o7, which is visible to the instruction in delay slot.
 295   RegDefs.insert(SP::O7);
 296
 297   switch(MI->getOpcode()) {
 298   default: llvm_unreachable("Unknown opcode.");
 299   case SP::CALL: break;
 300   case SP::CALLrr:
 301   case SP::CALLri:
 302     assert(MI->getNumOperands() >= 2);
 303     const MachineOperand &Reg = MI->getOperand(0);
 304     assert(Reg.isReg() && "CALL first operand is not a register.");
 305     assert(Reg.isUse() && "CALL first operand is not a use.");
 306     RegUses.insert(Reg.getReg());
 307
 308     const MachineOperand &Operand1 = MI->getOperand(1);
 309     if (Operand1.isImm() || Operand1.isGlobal())
 310         break;
 311     assert(Operand1.isReg() && "CALLrr second operand is not a register.");
 312     assert(Operand1.isUse() && "CALLrr second operand is not a use.");
 313     RegUses.insert(Operand1.getReg());
 314     break;
 315   }
 316 }
 317
 318 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
 319 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
 320                             SmallSet<unsigned, 32>& RegDefs,
 321                             SmallSet<unsigned, 32>& RegUses)
 322 {
 323   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 324     const MachineOperand &MO = MI->getOperand(i);
 325     if (!MO.isReg())
 326       continue;
 327
 328     unsigned Reg = MO.getReg();
 329     if (Reg == 0)
 330       continue;
 331     if (MO.isDef())
 332       RegDefs.insert(Reg);
 333     if (MO.isUse()) {
 334       // Implicit register uses of retl are return values and
 335       // retl does not use them.
 336       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
 337         continue;
 338       RegUses.insert(Reg);
 339     }
 340   }
 341 }
 342
 343 // returns true if the Reg or its alias is in the RegSet.
 344 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
 345 {
 346   // Check Reg and all aliased Registers.
 347   for (MCRegAliasIterator AI(Reg, Subtarget->getRegisterInfo(), true);
 348        AI.isValid(); ++AI)
 349     if (RegSet.count(*AI))
 350       return true;
 351   return false;
 352 }
 353
 354 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
 355 {
 356   if (!I->isCall())
 357     return false;
 358
 359   unsigned structSizeOpNum = 0;
 360   switch (I->getOpcode()) {
 361   default: llvm_unreachable("Unknown call opcode.");
 362   case SP::CALL: structSizeOpNum = 1; break;
 363   case SP::CALLrr:
 364   case SP::CALLri: structSizeOpNum = 2; break;
 365   case SP::TLS_CALL: return false;
 366   }
 367
 368   const MachineOperand &MO = I->getOperand(structSizeOpNum);
 369   if (!MO.isImm())
 370     return false;
 371   StructSize = MO.getImm();
 372   return true;
 373 }
 374
 375 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
 376                               MachineBasicBlock::iterator AddMI,
 377                               const TargetInstrInfo *TII)
 378 {
 379   // Before:  add  <op0>, <op1>, %i[0-7]
 380   //          restore %g0, %g0, %i[0-7]
 381   //
 382   // After :  restore <op0>, <op1>, %o[0-7]
 383
 384   unsigned reg = AddMI->getOperand(0).getReg();
 385   if (reg < SP::I0 || reg > SP::I7)
 386     return false;
 387
 388   // Erase RESTORE.
 389   RestoreMI->eraseFromParent();
 390
 391   // Change ADD to RESTORE.
 392   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
 393                           ? SP::RESTORErr
 394                           : SP::RESTOREri));
 395
 396   // Map the destination register.
 397   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 398
 399   return true;
 400 }
 401
 402 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
 403                              MachineBasicBlock::iterator OrMI,
 404                              const TargetInstrInfo *TII)
 405 {
 406   // Before:  or  <op0>, <op1>, %i[0-7]
 407   //          restore %g0, %g0, %i[0-7]
 408   //    and <op0> or <op1> is zero,
 409   //
 410   // After :  restore <op0>, <op1>, %o[0-7]
 411
 412   unsigned reg = OrMI->getOperand(0).getReg();
 413   if (reg < SP::I0 || reg > SP::I7)
 414     return false;
 415
 416   // check whether it is a copy.
 417   if (OrMI->getOpcode() == SP::ORrr
 418       && OrMI->getOperand(1).getReg() != SP::G0
 419       && OrMI->getOperand(2).getReg() != SP::G0)
 420     return false;
 421
 422   if (OrMI->getOpcode() == SP::ORri
 423       && OrMI->getOperand(1).getReg() != SP::G0
 424       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
 425     return false;
 426
 427   // Erase RESTORE.
 428   RestoreMI->eraseFromParent();
 429
 430   // Change OR to RESTORE.
 431   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
 432                          ? SP::RESTORErr
 433                          : SP::RESTOREri));
 434
 435   // Map the destination register.
 436   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 437
 438   return true;
 439 }
 440
 441 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
 442                                  MachineBasicBlock::iterator SetHiMI,
 443                                  const TargetInstrInfo *TII)
 444 {
 445   // Before:  sethi imm3, %i[0-7]
 446   //          restore %g0, %g0, %g0
 447   //
 448   // After :  restore %g0, (imm3<<10), %o[0-7]
 449
 450   unsigned reg = SetHiMI->getOperand(0).getReg();
 451   if (reg < SP::I0 || reg > SP::I7)
 452     return false;
 453
 454   if (!SetHiMI->getOperand(1).isImm())
 455     return false;
 456
 457   int64_t imm = SetHiMI->getOperand(1).getImm();
 458
 459   // Is it a 3 bit immediate?
 460   if (!isInt<3>(imm))
 461     return false;
 462
 463   // Make it a 13 bit immediate.
 464   imm = (imm << 10) & 0x1FFF;
 465
 466   assert(RestoreMI->getOpcode() == SP::RESTORErr);
 467
 468   RestoreMI->setDesc(TII->get(SP::RESTOREri));
 469
 470   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 471   RestoreMI->getOperand(1).setReg(SP::G0);
 472   RestoreMI->getOperand(2).ChangeToImmediate(imm);
 473
 474
 475   // Erase the original SETHI.
 476   SetHiMI->eraseFromParent();
 477
 478   return true;
 479 }
 480
 481 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
 482                                         MachineBasicBlock::iterator MBBI)
 483 {
 484   // No previous instruction.
 485   if (MBBI == MBB.begin())
 486     return false;
 487
 488   // assert that MBBI is a "restore %g0, %g0, %g0".
 489   assert(MBBI->getOpcode() == SP::RESTORErr
 490          && MBBI->getOperand(0).getReg() == SP::G0
 491          && MBBI->getOperand(1).getReg() == SP::G0
 492          && MBBI->getOperand(2).getReg() == SP::G0);
 493
 494   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
 495
 496   // It cannot be combined with a bundled instruction.
 497   if (PrevInst->isBundledWithSucc())
 498     return false;
 499
 500   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
 501
 502   switch (PrevInst->getOpcode()) {
 503   default: break;
 504   case SP::ADDrr:
 505   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
 506   case SP::ORrr:
 507   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
 508   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
 509   }
 510   // It cannot combine with the previous instruction.
 511   return false;
 512 }