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     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   return false;
 271 }
 272
 273
 274 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
 275                                 SmallSet<unsigned, 32>& RegDefs,
 276                                 SmallSet<unsigned, 32>& RegUses)
 277 {
 278   // Call defines o7, which is visible to the instruction in delay slot.
 279   RegDefs.insert(SP::O7);
 280
 281   switch(MI->getOpcode()) {
 282   default: llvm_unreachable("Unknown opcode.");
 283   case SP::CALL: break;
 284   case SP::CALLrr:
 285   case SP::CALLri:
 286     assert(MI->getNumOperands() >= 2);
 287     const MachineOperand &Reg = MI->getOperand(0);
 288     assert(Reg.isReg() && "CALL first operand is not a register.");
 289     assert(Reg.isUse() && "CALL first operand is not a use.");
 290     RegUses.insert(Reg.getReg());
 291
 292     const MachineOperand &RegOrImm = MI->getOperand(1);
 293     if (RegOrImm.isImm())
 294         break;
 295     assert(RegOrImm.isReg() && "CALLrr second operand is not a register.");
 296     assert(RegOrImm.isUse() && "CALLrr second operand is not a use.");
 297     RegUses.insert(RegOrImm.getReg());
 298     break;
 299   }
 300 }
 301
 302 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
 303 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
 304                             SmallSet<unsigned, 32>& RegDefs,
 305                             SmallSet<unsigned, 32>& RegUses)
 306 {
 307   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 308     const MachineOperand &MO = MI->getOperand(i);
 309     if (!MO.isReg())
 310       continue;
 311
 312     unsigned Reg = MO.getReg();
 313     if (Reg == 0)
 314       continue;
 315     if (MO.isDef())
 316       RegDefs.insert(Reg);
 317     if (MO.isUse()) {
 318       // Implicit register uses of retl are return values and
 319       // retl does not use them.
 320       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
 321         continue;
 322       RegUses.insert(Reg);
 323     }
 324   }
 325 }
 326
 327 // returns true if the Reg or its alias is in the RegSet.
 328 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
 329 {
 330   // Check Reg and all aliased Registers.
 331   for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
 332        AI.isValid(); ++AI)
 333     if (RegSet.count(*AI))
 334       return true;
 335   return false;
 336 }
 337
 338 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
 339 {
 340   if (!I->isCall())
 341     return false;
 342
 343   unsigned structSizeOpNum = 0;
 344   switch (I->getOpcode()) {
 345   default: llvm_unreachable("Unknown call opcode.");
 346   case SP::CALL: structSizeOpNum = 1; break;
 347   case SP::CALLrr:
 348   case SP::CALLri: structSizeOpNum = 2; break;
 349   case SP::TLS_CALL: return false;
 350   }
 351
 352   const MachineOperand &MO = I->getOperand(structSizeOpNum);
 353   if (!MO.isImm())
 354     return false;
 355   StructSize = MO.getImm();
 356   return true;
 357 }
 358
 359 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
 360                               MachineBasicBlock::iterator AddMI,
 361                               const TargetInstrInfo *TII)
 362 {
 363   // Before:  add  <op0>, <op1>, %i[0-7]
 364   //          restore %g0, %g0, %i[0-7]
 365   //
 366   // After :  restore <op0>, <op1>, %o[0-7]
 367
 368   unsigned reg = AddMI->getOperand(0).getReg();
 369   if (reg < SP::I0 || reg > SP::I7)
 370     return false;
 371
 372   // Erase RESTORE.
 373   RestoreMI->eraseFromParent();
 374
 375   // Change ADD to RESTORE.
 376   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
 377                           ? SP::RESTORErr
 378                           : SP::RESTOREri));
 379
 380   // Map the destination register.
 381   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 382
 383   return true;
 384 }
 385
 386 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
 387                              MachineBasicBlock::iterator OrMI,
 388                              const TargetInstrInfo *TII)
 389 {
 390   // Before:  or  <op0>, <op1>, %i[0-7]
 391   //          restore %g0, %g0, %i[0-7]
 392   //    and <op0> or <op1> is zero,
 393   //
 394   // After :  restore <op0>, <op1>, %o[0-7]
 395
 396   unsigned reg = OrMI->getOperand(0).getReg();
 397   if (reg < SP::I0 || reg > SP::I7)
 398     return false;
 399
 400   // check whether it is a copy.
 401   if (OrMI->getOpcode() == SP::ORrr
 402       && OrMI->getOperand(1).getReg() != SP::G0
 403       && OrMI->getOperand(2).getReg() != SP::G0)
 404     return false;
 405
 406   if (OrMI->getOpcode() == SP::ORri
 407       && OrMI->getOperand(1).getReg() != SP::G0
 408       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
 409     return false;
 410
 411   // Erase RESTORE.
 412   RestoreMI->eraseFromParent();
 413
 414   // Change OR to RESTORE.
 415   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
 416                          ? SP::RESTORErr
 417                          : SP::RESTOREri));
 418
 419   // Map the destination register.
 420   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 421
 422   return true;
 423 }
 424
 425 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
 426                                  MachineBasicBlock::iterator SetHiMI,
 427                                  const TargetInstrInfo *TII)
 428 {
 429   // Before:  sethi imm3, %i[0-7]
 430   //          restore %g0, %g0, %g0
 431   //
 432   // After :  restore %g0, (imm3<<10), %o[0-7]
 433
 434   unsigned reg = SetHiMI->getOperand(0).getReg();
 435   if (reg < SP::I0 || reg > SP::I7)
 436     return false;
 437
 438   if (!SetHiMI->getOperand(1).isImm())
 439     return false;
 440
 441   int64_t imm = SetHiMI->getOperand(1).getImm();
 442
 443   // Is it a 3 bit immediate?
 444   if (!isInt<3>(imm))
 445     return false;
 446
 447   // Make it a 13 bit immediate.
 448   imm = (imm << 10) & 0x1FFF;
 449
 450   assert(RestoreMI->getOpcode() == SP::RESTORErr);
 451
 452   RestoreMI->setDesc(TII->get(SP::RESTOREri));
 453
 454   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 455   RestoreMI->getOperand(1).setReg(SP::G0);
 456   RestoreMI->getOperand(2).ChangeToImmediate(imm);
 457
 458
 459   // Erase the original SETHI.
 460   SetHiMI->eraseFromParent();
 461
 462   return true;
 463 }
 464
 465 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
 466                                         MachineBasicBlock::iterator MBBI)
 467 {
 468   // No previous instruction.
 469   if (MBBI == MBB.begin())
 470     return false;
 471
 472   // assert that MBBI is a "restore %g0, %g0, %g0".
 473   assert(MBBI->getOpcode() == SP::RESTORErr
 474          && MBBI->getOperand(0).getReg() == SP::G0
 475          && MBBI->getOperand(1).getReg() == SP::G0
 476          && MBBI->getOperand(2).getReg() == SP::G0);
 477
 478   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
 479
 480   // It cannot be combined with a bundled instruction.
 481   if (PrevInst->isBundledWithSucc())
 482     return false;
 483
 484   const TargetInstrInfo *TII = TM.getInstrInfo();
 485
 486   switch (PrevInst->getOpcode()) {
 487   default: break;
 488   case SP::ADDrr:
 489   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
 490   case SP::ORrr:
 491   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
 492   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
 493   }
 494   // It cannot combine with the previous instruction.
 495   return false;
 496 }