lib/Target/Lanai/LanaiDelaySlotFiller.cpp

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