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