contrib/llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp

   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   StringRef 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::NoVRegs);
  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.getReverse();
 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         MachineBasicBlock::instr_iterator FI = RI.getReverse();
 121         MBB.splice(std::next(I), &MBB, FI, I);
 122         FilledSlots += 2;
 123       } else {
 124         if (!NopDelaySlotFiller && findDelayInstr(MBB, I, J)) {
 125           MBB.splice(std::next(I), &MBB, J);
 126         } else {
 127           BuildMI(MBB, std::next(I), DebugLoc(), TII->get(Lanai::NOP));
 128         }
 129         ++FilledSlots;
 130       }
 131
 132       Changed = true;
 133       // Record the filler instruction that filled the delay slot.
 134       // The instruction after it will be visited in the next iteration.
 135       LastFiller = ++I;
 136
 137       // Bundle the delay slot filler to InstrWithSlot so that the machine
 138       // verifier doesn't expect this instruction to be a terminator.
 139       MIBundleBuilder(MBB, InstrWithSlot, std::next(LastFiller));
 140     }
 141   }
 142   return Changed;
 143 }
 144
 145 bool Filler::findDelayInstr(MachineBasicBlock &MBB,
 146                             MachineBasicBlock::instr_iterator Slot,
 147                             MachineBasicBlock::instr_iterator &Filler) {
 148   SmallSet<unsigned, 32> RegDefs;
 149   SmallSet<unsigned, 32> RegUses;
 150
 151   insertDefsUses(Slot, RegDefs, RegUses);
 152
 153   bool SawLoad = false;
 154   bool SawStore = false;
 155
 156   for (MachineBasicBlock::reverse_instr_iterator I = ++Slot.getReverse();
 157        I != MBB.instr_rend(); ++I) {
 158     // skip debug value
 159     if (I->isDebugValue())
 160       continue;
 161
 162     // Convert to forward iterator.
 163     MachineBasicBlock::instr_iterator FI = I.getReverse();
 164
 165     if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isLabel() ||
 166         FI == LastFiller || I->isPseudo())
 167       break;
 168
 169     if (delayHasHazard(FI, SawLoad, SawStore, RegDefs, RegUses)) {
 170       insertDefsUses(FI, RegDefs, RegUses);
 171       continue;
 172     }
 173     Filler = FI;
 174     return true;
 175   }
 176   return false;
 177 }
 178
 179 bool Filler::delayHasHazard(MachineBasicBlock::instr_iterator MI, bool &SawLoad,
 180                             bool &SawStore, SmallSet<unsigned, 32> &RegDefs,
 181                             SmallSet<unsigned, 32> &RegUses) {
 182   if (MI->isImplicitDef() || MI->isKill())
 183     return true;
 184
 185   // Loads or stores cannot be moved past a store to the delay slot
 186   // and stores cannot be moved past a load.
 187   if (MI->mayLoad()) {
 188     if (SawStore)
 189       return true;
 190     SawLoad = true;
 191   }
 192
 193   if (MI->mayStore()) {
 194     if (SawStore)
 195       return true;
 196     SawStore = true;
 197     if (SawLoad)
 198       return true;
 199   }
 200
 201   assert((!MI->isCall() && !MI->isReturn()) &&
 202          "Cannot put calls or returns in delay slot.");
 203
 204   for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
 205     const MachineOperand &MO = MI->getOperand(I);
 206     unsigned Reg;
 207
 208     if (!MO.isReg() || !(Reg = MO.getReg()))
 209       continue; // skip
 210
 211     if (MO.isDef()) {
 212       // check whether Reg is defined or used before delay slot.
 213       if (isRegInSet(RegDefs, Reg) || isRegInSet(RegUses, Reg))
 214         return true;
 215     }
 216     if (MO.isUse()) {
 217       // check whether Reg is defined before delay slot.
 218       if (isRegInSet(RegDefs, Reg))
 219         return true;
 220     }
 221   }
 222   return false;
 223 }
 224
 225 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
 226 void Filler::insertDefsUses(MachineBasicBlock::instr_iterator MI,
 227                             SmallSet<unsigned, 32> &RegDefs,
 228                             SmallSet<unsigned, 32> &RegUses) {
 229   // If MI is a call or return, just examine the explicit non-variadic operands.
 230   MCInstrDesc MCID = MI->getDesc();
 231   unsigned E = MI->isCall() || MI->isReturn() ? MCID.getNumOperands()
 232                                               : MI->getNumOperands();
 233   for (unsigned I = 0; I != E; ++I) {
 234     const MachineOperand &MO = MI->getOperand(I);
 235     unsigned Reg;
 236
 237     if (!MO.isReg() || !(Reg = MO.getReg()))
 238       continue;
 239
 240     if (MO.isDef())
 241       RegDefs.insert(Reg);
 242     else if (MO.isUse())
 243       RegUses.insert(Reg);
 244   }
 245
 246   // Call & return instructions defines SP implicitly. Implicit defines are not
 247   // included in the RegDefs set of calls but instructions modifying SP cannot
 248   // be inserted in the delay slot of a call/return as these instructions are
 249   // expanded to multiple instructions with SP modified before the branch that
 250   // has the delay slot.
 251   if (MI->isCall() || MI->isReturn())
 252     RegDefs.insert(Lanai::SP);
 253 }
 254
 255 // Returns true if the Reg or its alias is in the RegSet.
 256 bool Filler::isRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) {
 257   // Check Reg and all aliased Registers.
 258   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 259     if (RegSet.count(*AI))
 260       return true;
 261   return false;
 262 }