Home | History | Annotate | Download | only in Sparc 
      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 }
    513