Home | History | Annotate | Download | only in Lanai 
      1 //===-- LanaiDelaySlotFiller.cpp - Lanai 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 // Simple pass to fills delay slots with useful instructions.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "Lanai.h"
     15 #include "LanaiTargetMachine.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/Support/CommandLine.h"
     21 #include "llvm/Target/TargetInstrInfo.h"
     22 
     23 using namespace llvm;
     24 
     25 #define DEBUG_TYPE "delay-slot-filler"
     26 
     27 STATISTIC(FilledSlots, "Number of delay slots filled");
     28 
     29 static cl::opt<bool>
     30     NopDelaySlotFiller("lanai-nop-delay-filler", cl::init(false),
     31                        cl::desc("Fill Lanai delay slots with NOPs."),
     32                        cl::Hidden);
     33 
     34 namespace {
     35 struct Filler : public MachineFunctionPass {
     36   // Target machine description which we query for reg. names, data
     37   // layout, etc.
     38   const TargetInstrInfo *TII;
     39   const TargetRegisterInfo *TRI;
     40   MachineBasicBlock::instr_iterator LastFiller;
     41 
     42   static char ID;
     43   explicit Filler() : MachineFunctionPass(ID) {}
     44 
     45   const char *getPassName() const override { return "Lanai Delay Slot Filler"; }
     46 
     47   bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
     48 
     49   bool runOnMachineFunction(MachineFunction &MF) override {
     50     const LanaiSubtarget &Subtarget = MF.getSubtarget<LanaiSubtarget>();
     51     TII = Subtarget.getInstrInfo();
     52     TRI = Subtarget.getRegisterInfo();
     53 
     54     bool Changed = false;
     55     for (MachineFunction::iterator FI = MF.begin(), FE = MF.end(); FI != FE;
     56          ++FI)
     57       Changed |= runOnMachineBasicBlock(*FI);
     58     return Changed;
     59   }
     60 
     61   MachineFunctionProperties getRequiredProperties() const override {
     62     return MachineFunctionProperties().set(
     63         MachineFunctionProperties::Property::AllVRegsAllocated);
     64   }
     65 
     66   void insertDefsUses(MachineBasicBlock::instr_iterator MI,
     67                       SmallSet<unsigned, 32> &RegDefs,
     68                       SmallSet<unsigned, 32> &RegUses);
     69 
     70   bool isRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg);
     71 
     72   bool delayHasHazard(MachineBasicBlock::instr_iterator MI, bool &SawLoad,
     73                       bool &SawStore, SmallSet<unsigned, 32> &RegDefs,
     74                       SmallSet<unsigned, 32> &RegUses);
     75 
     76   bool findDelayInstr(MachineBasicBlock &MBB,
     77                       MachineBasicBlock::instr_iterator Slot,
     78                       MachineBasicBlock::instr_iterator &Filler);
     79 };
     80 char Filler::ID = 0;
     81 } // end of anonymous namespace
     82 
     83 // createLanaiDelaySlotFillerPass - Returns a pass that fills in delay
     84 // slots in Lanai MachineFunctions
     85 FunctionPass *
     86 llvm::createLanaiDelaySlotFillerPass(const LanaiTargetMachine &tm) {
     87   return new Filler();
     88 }
     89 
     90 // runOnMachineBasicBlock - Fill in delay slots for the given basic block.
     91 // There is one or two delay slot per delayed instruction.
     92 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
     93   bool Changed = false;
     94   LastFiller = MBB.instr_end();
     95 
     96   for (MachineBasicBlock::instr_iterator I = MBB.instr_begin();
     97        I != MBB.instr_end(); ++I) {
     98     if (I->getDesc().hasDelaySlot()) {
     99       MachineBasicBlock::instr_iterator InstrWithSlot = I;
    100       MachineBasicBlock::instr_iterator J = I;
    101 
    102       // Treat RET specially as it is only instruction with 2 delay slots
    103       // generated while all others generated have 1 delay slot.
    104       if (I->getOpcode() == Lanai::RET) {
    105         // RET is generated as part of epilogue generation and hence we know
    106         // what the two instructions preceding it are and that it is safe to
    107         // insert RET above them.
    108         MachineBasicBlock::reverse_instr_iterator RI(I);
    109         assert(RI->getOpcode() == Lanai::LDW_RI && RI->getOperand(0).isReg() &&
    110                RI->getOperand(0).getReg() == Lanai::FP &&
    111                RI->getOperand(1).isReg() &&
    112                RI->getOperand(1).getReg() == Lanai::FP &&
    113                RI->getOperand(2).isImm() && RI->getOperand(2).getImm() == -8);
    114         ++RI;
    115         assert(RI->getOpcode() == Lanai::ADD_I_LO &&
    116                RI->getOperand(0).isReg() &&
    117                RI->getOperand(0).getReg() == Lanai::SP &&
    118                RI->getOperand(1).isReg() &&
    119                RI->getOperand(1).getReg() == Lanai::FP);
    120         ++RI;
    121         MachineBasicBlock::instr_iterator FI(RI.base());
    122         MBB.splice(std::next(I), &MBB, FI, I);
    123         FilledSlots += 2;
    124       } else {
    125         if (!NopDelaySlotFiller && findDelayInstr(MBB, I, J)) {
    126           MBB.splice(std::next(I), &MBB, J);
    127         } else {
    128           BuildMI(MBB, std::next(I), DebugLoc(), TII->get(Lanai::NOP));
    129         }
    130         ++FilledSlots;
    131       }
    132 
    133       Changed = true;
    134       // Record the filler instruction that filled the delay slot.
    135       // The instruction after it will be visited in the next iteration.
    136       LastFiller = ++I;
    137 
    138       // Bundle the delay slot filler to InstrWithSlot so that the machine
    139       // verifier doesn't expect this instruction to be a terminator.
    140       MIBundleBuilder(MBB, InstrWithSlot, std::next(LastFiller));
    141     }
    142   }
    143   return Changed;
    144 }
    145 
    146 bool Filler::findDelayInstr(MachineBasicBlock &MBB,
    147                             MachineBasicBlock::instr_iterator Slot,
    148                             MachineBasicBlock::instr_iterator &Filler) {
    149   SmallSet<unsigned, 32> RegDefs;
    150   SmallSet<unsigned, 32> RegUses;
    151 
    152   insertDefsUses(Slot, RegDefs, RegUses);
    153 
    154   bool SawLoad = false;
    155   bool SawStore = false;
    156 
    157   for (MachineBasicBlock::reverse_instr_iterator I(Slot); I != MBB.instr_rend();
    158        ++I) {
    159     // skip debug value
    160     if (I->isDebugValue())
    161       continue;
    162 
    163     // Convert to forward iterator.
    164     MachineBasicBlock::instr_iterator FI(std::next(I).base());
    165 
    166     if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isLabel() ||
    167         FI == LastFiller || I->isPseudo())
    168       break;
    169 
    170     if (delayHasHazard(FI, SawLoad, SawStore, RegDefs, RegUses)) {
    171       insertDefsUses(FI, RegDefs, RegUses);
    172       continue;
    173     }
    174     Filler = FI;
    175     return true;
    176   }
    177   return false;
    178 }
    179 
    180 bool Filler::delayHasHazard(MachineBasicBlock::instr_iterator MI, bool &SawLoad,
    181                             bool &SawStore, SmallSet<unsigned, 32> &RegDefs,
    182                             SmallSet<unsigned, 32> &RegUses) {
    183   if (MI->isImplicitDef() || MI->isKill())
    184     return true;
    185 
    186   // Loads or stores cannot be moved past a store to the delay slot
    187   // and stores cannot be moved past a load.
    188   if (MI->mayLoad()) {
    189     if (SawStore)
    190       return true;
    191     SawLoad = true;
    192   }
    193 
    194   if (MI->mayStore()) {
    195     if (SawStore)
    196       return true;
    197     SawStore = true;
    198     if (SawLoad)
    199       return true;
    200   }
    201 
    202   assert((!MI->isCall() && !MI->isReturn()) &&
    203          "Cannot put calls or returns in delay slot.");
    204 
    205   for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
    206     const MachineOperand &MO = MI->getOperand(I);
    207     unsigned Reg;
    208 
    209     if (!MO.isReg() || !(Reg = MO.getReg()))
    210       continue; // skip
    211 
    212     if (MO.isDef()) {
    213       // check whether Reg is defined or used before delay slot.
    214       if (isRegInSet(RegDefs, Reg) || isRegInSet(RegUses, Reg))
    215         return true;
    216     }
    217     if (MO.isUse()) {
    218       // check whether Reg is defined before delay slot.
    219       if (isRegInSet(RegDefs, Reg))
    220         return true;
    221     }
    222   }
    223   return false;
    224 }
    225 
    226 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
    227 void Filler::insertDefsUses(MachineBasicBlock::instr_iterator MI,
    228                             SmallSet<unsigned, 32> &RegDefs,
    229                             SmallSet<unsigned, 32> &RegUses) {
    230   // If MI is a call or return, just examine the explicit non-variadic operands.
    231   MCInstrDesc MCID = MI->getDesc();
    232   unsigned E = MI->isCall() || MI->isReturn() ? MCID.getNumOperands()
    233                                               : MI->getNumOperands();
    234   for (unsigned I = 0; I != E; ++I) {
    235     const MachineOperand &MO = MI->getOperand(I);
    236     unsigned Reg;
    237 
    238     if (!MO.isReg() || !(Reg = MO.getReg()))
    239       continue;
    240 
    241     if (MO.isDef())
    242       RegDefs.insert(Reg);
    243     else if (MO.isUse())
    244       RegUses.insert(Reg);
    245   }
    246 
    247   // Call & return instructions defines SP implicitly. Implicit defines are not
    248   // included in the RegDefs set of calls but instructions modifying SP cannot
    249   // be inserted in the delay slot of a call/return as these instructions are
    250   // expanded to multiple instructions with SP modified before the branch that
    251   // has the delay slot.
    252   if (MI->isCall() || MI->isReturn())
    253     RegDefs.insert(Lanai::SP);
    254 }
    255 
    256 // Returns true if the Reg or its alias is in the RegSet.
    257 bool Filler::isRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) {
    258   // Check Reg and all aliased Registers.
    259   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
    260     if (RegSet.count(*AI))
    261       return true;
    262   return false;
    263 }
    264