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