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

   1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This is a simple local pass that attempts to fill delay slots with useful
  10 // instructions. If no instructions can be moved into the delay slot, then a
  11 // NOP is placed.
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "Sparc.h"
  15 #include "SparcSubtarget.h"
  16 #include "llvm/ADT/SmallSet.h"
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstrBuilder.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/CodeGen/TargetInstrInfo.h"
  22 #include "llvm/CodeGen/TargetRegisterInfo.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Target/TargetMachine.h"
  25
  26 using namespace llvm;
  27
  28 #define DEBUG_TYPE "delay-slot-filler"
  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     const SparcSubtarget *Subtarget;
  41
  42     static char ID;
  43     Filler() : MachineFunctionPass(ID) {}
  44
  45     StringRef getPassName() const override { return "SPARC Delay Slot Filler"; }
  46
  47     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
  48     bool runOnMachineFunction(MachineFunction &F) override {
  49       bool Changed = false;
  50       Subtarget = &F.getSubtarget<SparcSubtarget>();
  51
  52       // This pass invalidates liveness information when it reorders
  53       // instructions to fill delay slot.
  54       F.getRegInfo().invalidateLiveness();
  55
  56       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
  57            FI != FE; ++FI)
  58         Changed |= runOnMachineBasicBlock(*FI);
  59       return Changed;
  60     }
  61
  62     MachineFunctionProperties getRequiredProperties() const override {
  63       return MachineFunctionProperties().set(
  64           MachineFunctionProperties::Property::NoVRegs);
  65     }
  66
  67     void insertCallDefsUses(MachineBasicBlock::iterator MI,
  68                             SmallSet<unsigned, 32>& RegDefs,
  69                             SmallSet<unsigned, 32>& RegUses);
  70
  71     void insertDefsUses(MachineBasicBlock::iterator MI,
  72                         SmallSet<unsigned, 32>& RegDefs,
  73                         SmallSet<unsigned, 32>& RegUses);
  74
  75     bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
  76                     unsigned Reg);
  77
  78     bool delayHasHazard(MachineBasicBlock::iterator candidate,
  79                         bool &sawLoad, bool &sawStore,
  80                         SmallSet<unsigned, 32> &RegDefs,
  81                         SmallSet<unsigned, 32> &RegUses);
  82
  83     MachineBasicBlock::iterator
  84     findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
  85
  86     bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
  87
  88     bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
  89                                        MachineBasicBlock::iterator MBBI);
  90
  91   };
  92   char Filler::ID = 0;
  93 } // end of anonymous namespace
  94
  95 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
  96 /// slots in Sparc MachineFunctions
  97 ///
  98 FunctionPass *llvm::createSparcDelaySlotFillerPass() {
  99   return new Filler;
 100 }
 101
 102
 103 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 104 /// We assume there is only one delay slot per delayed instruction.
 105 ///
 106 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 107   bool Changed = false;
 108   Subtarget = &MBB.getParent()->getSubtarget<SparcSubtarget>();
 109   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
 110
 111   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
 112     MachineBasicBlock::iterator MI = I;
 113     ++I;
 114
 115     // If MI is restore, try combining it with previous inst.
 116     if (!DisableDelaySlotFiller &&
 117         (MI->getOpcode() == SP::RESTORErr
 118          || MI->getOpcode() == SP::RESTOREri)) {
 119       Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
 120       continue;
 121     }
 122
 123     // TODO: If we ever want to support v7, this needs to be extended
 124     // to cover all floating point operations.
 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 instruction
 210     if (I->isDebugInstr())
 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
 270   unsigned Opcode = candidate->getOpcode();
 271   // LD and LDD may have NOPs inserted afterwards in the case of some LEON
 272   // processors, so we can't use the delay slot if this feature is switched-on.
 273   if (Subtarget->insertNOPLoad()
 274       &&
 275       Opcode >=  SP::LDDArr && Opcode <= SP::LDrr)
 276     return true;
 277
 278   // Same as above for FDIV and FSQRT on some LEON processors.
 279   if (Subtarget->fixAllFDIVSQRT()
 280       &&
 281       Opcode >=  SP::FDIVD && Opcode <= SP::FSQRTD)
 282     return true;
 283
 284
 285   return false;
 286 }
 287
 288
 289 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
 290                                 SmallSet<unsigned, 32>& RegDefs,
 291                                 SmallSet<unsigned, 32>& RegUses)
 292 {
 293   // Call defines o7, which is visible to the instruction in delay slot.
 294   RegDefs.insert(SP::O7);
 295
 296   switch(MI->getOpcode()) {
 297   default: llvm_unreachable("Unknown opcode.");
 298   case SP::CALL: break;
 299   case SP::CALLrr:
 300   case SP::CALLri:
 301     assert(MI->getNumOperands() >= 2);
 302     const MachineOperand &Reg = MI->getOperand(0);
 303     assert(Reg.isReg() && "CALL first operand is not a register.");
 304     assert(Reg.isUse() && "CALL first operand is not a use.");
 305     RegUses.insert(Reg.getReg());
 306
 307     const MachineOperand &Operand1 = MI->getOperand(1);
 308     if (Operand1.isImm() || Operand1.isGlobal())
 309         break;
 310     assert(Operand1.isReg() && "CALLrr second operand is not a register.");
 311     assert(Operand1.isUse() && "CALLrr second operand is not a use.");
 312     RegUses.insert(Operand1.getReg());
 313     break;
 314   }
 315 }
 316
 317 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
 318 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
 319                             SmallSet<unsigned, 32>& RegDefs,
 320                             SmallSet<unsigned, 32>& RegUses)
 321 {
 322   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 323     const MachineOperand &MO = MI->getOperand(i);
 324     if (!MO.isReg())
 325       continue;
 326
 327     unsigned Reg = MO.getReg();
 328     if (Reg == 0)
 329       continue;
 330     if (MO.isDef())
 331       RegDefs.insert(Reg);
 332     if (MO.isUse()) {
 333       // Implicit register uses of retl are return values and
 334       // retl does not use them.
 335       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
 336         continue;
 337       RegUses.insert(Reg);
 338     }
 339   }
 340 }
 341
 342 // returns true if the Reg or its alias is in the RegSet.
 343 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
 344 {
 345   // Check Reg and all aliased Registers.
 346   for (MCRegAliasIterator AI(Reg, Subtarget->getRegisterInfo(), true);
 347        AI.isValid(); ++AI)
 348     if (RegSet.count(*AI))
 349       return true;
 350   return false;
 351 }
 352
 353 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
 354 {
 355   if (!I->isCall())
 356     return false;
 357
 358   unsigned structSizeOpNum = 0;
 359   switch (I->getOpcode()) {
 360   default: llvm_unreachable("Unknown call opcode.");
 361   case SP::CALL: structSizeOpNum = 1; break;
 362   case SP::CALLrr:
 363   case SP::CALLri: structSizeOpNum = 2; break;
 364   case SP::TLS_CALL: return false;
 365   }
 366
 367   const MachineOperand &MO = I->getOperand(structSizeOpNum);
 368   if (!MO.isImm())
 369     return false;
 370   StructSize = MO.getImm();
 371   return true;
 372 }
 373
 374 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
 375                               MachineBasicBlock::iterator AddMI,
 376                               const TargetInstrInfo *TII)
 377 {
 378   // Before:  add  <op0>, <op1>, %i[0-7]
 379   //          restore %g0, %g0, %i[0-7]
 380   //
 381   // After :  restore <op0>, <op1>, %o[0-7]
 382
 383   unsigned reg = AddMI->getOperand(0).getReg();
 384   if (reg < SP::I0 || reg > SP::I7)
 385     return false;
 386
 387   // Erase RESTORE.
 388   RestoreMI->eraseFromParent();
 389
 390   // Change ADD to RESTORE.
 391   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
 392                           ? SP::RESTORErr
 393                           : SP::RESTOREri));
 394
 395   // Map the destination register.
 396   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 397
 398   return true;
 399 }
 400
 401 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
 402                              MachineBasicBlock::iterator OrMI,
 403                              const TargetInstrInfo *TII)
 404 {
 405   // Before:  or  <op0>, <op1>, %i[0-7]
 406   //          restore %g0, %g0, %i[0-7]
 407   //    and <op0> or <op1> is zero,
 408   //
 409   // After :  restore <op0>, <op1>, %o[0-7]
 410
 411   unsigned reg = OrMI->getOperand(0).getReg();
 412   if (reg < SP::I0 || reg > SP::I7)
 413     return false;
 414
 415   // check whether it is a copy.
 416   if (OrMI->getOpcode() == SP::ORrr
 417       && OrMI->getOperand(1).getReg() != SP::G0
 418       && OrMI->getOperand(2).getReg() != SP::G0)
 419     return false;
 420
 421   if (OrMI->getOpcode() == SP::ORri
 422       && OrMI->getOperand(1).getReg() != SP::G0
 423       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
 424     return false;
 425
 426   // Erase RESTORE.
 427   RestoreMI->eraseFromParent();
 428
 429   // Change OR to RESTORE.
 430   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
 431                          ? SP::RESTORErr
 432                          : SP::RESTOREri));
 433
 434   // Map the destination register.
 435   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 436
 437   return true;
 438 }
 439
 440 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
 441                                  MachineBasicBlock::iterator SetHiMI,
 442                                  const TargetInstrInfo *TII)
 443 {
 444   // Before:  sethi imm3, %i[0-7]
 445   //          restore %g0, %g0, %g0
 446   //
 447   // After :  restore %g0, (imm3<<10), %o[0-7]
 448
 449   unsigned reg = SetHiMI->getOperand(0).getReg();
 450   if (reg < SP::I0 || reg > SP::I7)
 451     return false;
 452
 453   if (!SetHiMI->getOperand(1).isImm())
 454     return false;
 455
 456   int64_t imm = SetHiMI->getOperand(1).getImm();
 457
 458   // Is it a 3 bit immediate?
 459   if (!isInt<3>(imm))
 460     return false;
 461
 462   // Make it a 13 bit immediate.
 463   imm = (imm << 10) & 0x1FFF;
 464
 465   assert(RestoreMI->getOpcode() == SP::RESTORErr);
 466
 467   RestoreMI->setDesc(TII->get(SP::RESTOREri));
 468
 469   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
 470   RestoreMI->getOperand(1).setReg(SP::G0);
 471   RestoreMI->getOperand(2).ChangeToImmediate(imm);
 472
 473
 474   // Erase the original SETHI.
 475   SetHiMI->eraseFromParent();
 476
 477   return true;
 478 }
 479
 480 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
 481                                         MachineBasicBlock::iterator MBBI)
 482 {
 483   // No previous instruction.
 484   if (MBBI == MBB.begin())
 485     return false;
 486
 487   // assert that MBBI is a "restore %g0, %g0, %g0".
 488   assert(MBBI->getOpcode() == SP::RESTORErr
 489          && MBBI->getOperand(0).getReg() == SP::G0
 490          && MBBI->getOperand(1).getReg() == SP::G0
 491          && MBBI->getOperand(2).getReg() == SP::G0);
 492
 493   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
 494
 495   // It cannot be combined with a bundled instruction.
 496   if (PrevInst->isBundledWithSucc())
 497     return false;
 498
 499   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
 500
 501   switch (PrevInst->getOpcode()) {
 502   default: break;
 503   case SP::ADDrr:
 504   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
 505   case SP::ORrr:
 506   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
 507   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
 508   }
 509   // It cannot combine with the previous instruction.
 510   return false;
 511 }