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