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