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 #define DEBUG_TYPE "delay-slot-filler"
  16 #include "Sparc.h"
  17 #include "SparcSubtarget.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineRegisterInfo.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Target/TargetRegisterInfo.h"
  27
  28 using namespace llvm;
  29
  30 STATISTIC(FilledSlots, "Number of delay slots filled");
  31
  32 static cl::opt<bool> DisableDelaySlotFiller(
  33   "disable-sparc-delay-filler",
  34   cl::init(false),
  35   cl::desc("Disable the Sparc delay slot filler."),
  36   cl::Hidden);
  37
  38 namespace {
  39   struct Filler : public MachineFunctionPass {
  40     /// Target machine description which we query for reg. names, data
  41     /// layout, etc.
  42     ///
  43     TargetMachine &TM;
  44     const SparcSubtarget *Subtarget;
  45
  46     static char ID;
  47     Filler(TargetMachine &tm)
  48       : MachineFunctionPass(ID), TM(tm),
  49         Subtarget(&TM.getSubtarget<SparcSubtarget>()) {
  50     }
  51
  52     virtual const char *getPassName() const {
  53       return "SPARC Delay Slot Filler";
  54     }
  55
  56     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
  57     bool runOnMachineFunction(MachineFunction &F) {
  58       bool Changed = false;
  59
  60       // This pass invalidates liveness information when it reorders
  61       // instructions to fill delay slot.
  62       F.getRegInfo().invalidateLiveness();
  63
  64       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
  65            FI != FE; ++FI)
  66         Changed |= runOnMachineBasicBlock(*FI);
  67       return Changed;
  68     }
  69
  70     void insertCallDefsUses(MachineBasicBlock::iterator MI,
  71                             SmallSet<unsigned, 32>& RegDefs,
  72                             SmallSet<unsigned, 32>& RegUses);
  73
  74     void insertDefsUses(MachineBasicBlock::iterator MI,
  75                         SmallSet<unsigned, 32>& RegDefs,
  76                         SmallSet<unsigned, 32>& RegUses);
  77
  78     bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
  79                     unsigned Reg);
  80
  81     bool delayHasHazard(MachineBasicBlock::iterator candidate,
  82                         bool &sawLoad, bool &sawStore,
  83                         SmallSet<unsigned, 32> &RegDefs,
  84                         SmallSet<unsigned, 32> &RegUses);
  85
  86     MachineBasicBlock::iterator
  87     findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
  88
  89     bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
  90
  91     bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
  92                                        MachineBasicBlock::iterator MBBI);
  93
  94   };
  95   char Filler::ID = 0;
  96 } // end of anonymous namespace
  97
  98 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
  99 /// slots in Sparc MachineFunctions
 100 ///
 101 FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) {
 102   return new Filler(tm);
 103 }
 104
 105
 106 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 107 /// We assume there is only one delay slot per delayed instruction.
 108 ///
 109 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 110   bool Changed = false;
 111
 112   const TargetInstrInfo *TII = TM.getInstrInfo();
 113
 114   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
 115     MachineBasicBlock::iterator MI = I;
 116     ++I;
 117
 118     // If MI is restore, try combining it with previous inst.
 119     if (!DisableDelaySlotFiller &&
 120         (MI->getOpcode() == SP::RESTORErr
 121          || MI->getOpcode() == SP::RESTOREri)) {
 122       Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
 123       continue;
 124     }
 125
 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(TM.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 value
 211     if (I->isDebugValue())
 212       continue;
 213
 214
 215     if (I->hasUnmodeledSideEffects()
 216         || I->isInlineAsm()
 217         || I->isLabel()
 218         || I->hasDelaySlot()
 219         || I->isBundledWithSucc())
 220       break;
 221
 222     if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
 223       insertDefsUses(I, RegDefs, RegUses);
 224       continue;
 225     }
 226
 227     return I;
 228   }
 229   return MBB.end();
 230 }
 231
 232 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
 233                             bool &sawLoad,
 234                             bool &sawStore,
 235                             SmallSet<unsigned, 32> &RegDefs,
 236                             SmallSet<unsigned, 32> &RegUses)
 237 {
 238
 239   if (candidate->isImplicitDef() || candidate->isKill())
 240     return true;
 241
 242   if (candidate->mayLoad()) {
 243     sawLoad = true;
 244     if (sawStore)
 245       return true;
 246   }
 247
 248   if (candidate->mayStore()) {
 249     if (sawStore)
 250       return true;
 251     sawStore = true;
 252     if (sawLoad)
 253       return true;
 254   }
 255
 256   for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
 257     const MachineOperand &MO = candidate->getOperand(i);
 258     if (!MO.isReg())
 259       continue; // skip
 260
 261     unsigned Reg = MO.getReg();
 262
 263     if (MO.isDef()) {
 264       // check whether Reg is defined or used before delay slot.
 265       if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
 266         return true;
 267     }
 268     if (MO.isUse()) {
 269       // check whether Reg is defined before delay slot.
 270       if (IsRegInSet(RegDefs, Reg))
 271         return true;
 272     }
 273   }
 274   return false;
 275 }
 276
 277
 278 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
 279                                 SmallSet<unsigned, 32>& RegDefs,
 280                                 SmallSet<unsigned, 32>& RegUses)
 281 {
 282   // Call defines o7, which is visible to the instruction in delay slot.
 283   RegDefs.insert(SP::O7);
 284
 285   switch(MI->getOpcode()) {
 286   default: llvm_unreachable("Unknown opcode.");
 287   case SP::CALL: break;
 288   case SP::CALLrr:
 289   case SP::CALLri:
 290     assert(MI->getNumOperands() >= 2);
 291     const MachineOperand &Reg = MI->getOperand(0);
 292     assert(Reg.isReg() && "CALL first operand is not a register.");
 293     assert(Reg.isUse() && "CALL first operand is not a use.");
 294     RegUses.insert(Reg.getReg());
 295
 296     const MachineOperand &RegOrImm = MI->getOperand(1);
 297     if (RegOrImm.isImm())
 298         break;
 299     assert(RegOrImm.isReg() && "CALLrr second operand is not a register.");
 300     assert(RegOrImm.isUse() && "CALLrr second operand is not a use.");
 301     RegUses.insert(RegOrImm.getReg());
 302     break;
 303   }
 304 }
 305
 306 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
 307 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
 308                             SmallSet<unsigned, 32>& RegDefs,
 309                             SmallSet<unsigned, 32>& RegUses)
 310 {
 311   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 312     const MachineOperand &MO = MI->getOperand(i);
 313     if (!MO.isReg())
 314       continue;
 315
 316     unsigned Reg = MO.getReg();
 317     if (Reg == 0)
 318       continue;
 319     if (MO.isDef())
 320       RegDefs.insert(Reg);
 321     if (MO.isUse()) {
 322       // Implicit register uses of retl are return values and
 323       // retl does not use them.
 324       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
 325         continue;
 326       RegUses.insert(Reg);
 327     }
 328   }
 329 }
 330
 331 // returns true if the Reg or its alias is in the RegSet.
 332 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
 333 {
 334   // Check Reg and all aliased Registers.
 335   for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
 336        AI.isValid(); ++AI)
 337     if (RegSet.count(*AI))
 338       return true;
 339   return false;
 340 }
 341
 342 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
 343 {
 344   if (!I->isCall())
 345     return false;
 346
 347   unsigned structSizeOpNum = 0;
 348   switch (I->getOpcode()) {
 349   default: llvm_unreachable("Unknown call opcode.");
 350   case SP::CALL: structSizeOpNum = 1; break;
 351   case SP::CALLrr:
 352   case SP::CALLri: structSizeOpNum = 2; break;
 353   case SP::TLS_CALL: return false;
 354   }
 355
 356   const MachineOperand &MO = I->getOperand(structSizeOpNum);
 357   if (!MO.isImm())
 358     return false;
 359   StructSize = MO.getImm();
 360   return true;
 361 }
 362
 363 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
 364                               MachineBasicBlock::iterator AddMI,
 365                               const TargetInstrInfo *TII)
 366 {
 367   // Before:  add  <op0>, <op1>, %i[0-7]
 368   //          restore %g0, %g0, %i[0-7]
 369   //
 370   // After :  restore <op0>, <op1>, %o[0-7]
 371
 372   unsigned reg = AddMI->getOperand(0).getReg();
 373   if (reg < SP::I0 || reg > SP::I7)
 374     return false;
 375
 376   // Erase RESTORE.
 377   RestoreMI->eraseFromParent();
 378
 379   // Change ADD to RESTORE.
 380   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
 381                           ? SP::RESTORErr
 382                           : SP::RESTOREri));
 383
 384   // Map the destination register.
 385   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 386
 387   return true;
 388 }
 389
 390 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
 391                              MachineBasicBlock::iterator OrMI,
 392                              const TargetInstrInfo *TII)
 393 {
 394   // Before:  or  <op0>, <op1>, %i[0-7]
 395   //          restore %g0, %g0, %i[0-7]
 396   //    and <op0> or <op1> is zero,
 397   //
 398   // After :  restore <op0>, <op1>, %o[0-7]
 399
 400   unsigned reg = OrMI->getOperand(0).getReg();
 401   if (reg < SP::I0 || reg > SP::I7)
 402     return false;
 403
 404   // check whether it is a copy.
 405   if (OrMI->getOpcode() == SP::ORrr
 406       && OrMI->getOperand(1).getReg() != SP::G0
 407       && OrMI->getOperand(2).getReg() != SP::G0)
 408     return false;
 409
 410   if (OrMI->getOpcode() == SP::ORri
 411       && OrMI->getOperand(1).getReg() != SP::G0
 412       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
 413     return false;
 414
 415   // Erase RESTORE.
 416   RestoreMI->eraseFromParent();
 417
 418   // Change OR to RESTORE.
 419   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
 420                          ? SP::RESTORErr
 421                          : SP::RESTOREri));
 422
 423   // Map the destination register.
 424   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 425
 426   return true;
 427 }
 428
 429 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
 430                                  MachineBasicBlock::iterator SetHiMI,
 431                                  const TargetInstrInfo *TII)
 432 {
 433   // Before:  sethi imm3, %i[0-7]
 434   //          restore %g0, %g0, %g0
 435   //
 436   // After :  restore %g0, (imm3<<10), %o[0-7]
 437
 438   unsigned reg = SetHiMI->getOperand(0).getReg();
 439   if (reg < SP::I0 || reg > SP::I7)
 440     return false;
 441
 442   if (!SetHiMI->getOperand(1).isImm())
 443     return false;
 444
 445   int64_t imm = SetHiMI->getOperand(1).getImm();
 446
 447   // Is it a 3 bit immediate?
 448   if (!isInt<3>(imm))
 449     return false;
 450
 451   // Make it a 13 bit immediate.
 452   imm = (imm << 10) & 0x1FFF;
 453
 454   assert(RestoreMI->getOpcode() == SP::RESTORErr);
 455
 456   RestoreMI->setDesc(TII->get(SP::RESTOREri));
 457
 458   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 459   RestoreMI->getOperand(1).setReg(SP::G0);
 460   RestoreMI->getOperand(2).ChangeToImmediate(imm);
 461
 462
 463   // Erase the original SETHI.
 464   SetHiMI->eraseFromParent();
 465
 466   return true;
 467 }
 468
 469 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
 470                                         MachineBasicBlock::iterator MBBI)
 471 {
 472   // No previous instruction.
 473   if (MBBI == MBB.begin())
 474     return false;
 475
 476   // assert that MBBI is a "restore %g0, %g0, %g0".
 477   assert(MBBI->getOpcode() == SP::RESTORErr
 478          && MBBI->getOperand(0).getReg() == SP::G0
 479          && MBBI->getOperand(1).getReg() == SP::G0
 480          && MBBI->getOperand(2).getReg() == SP::G0);
 481
 482   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
 483
 484   // It cannot be combined with a bundled instruction.
 485   if (PrevInst->isBundledWithSucc())
 486     return false;
 487
 488   const TargetInstrInfo *TII = TM.getInstrInfo();
 489
 490   switch (PrevInst->getOpcode()) {
 491   default: break;
 492   case SP::ADDrr:
 493   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
 494   case SP::ORrr:
 495   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
 496   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
 497   }
 498   // It cannot combine with the previous instruction.
 499   return false;
 500 }