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
23using namespace llvm;
24
25#define DEBUG_TYPE "delay-slot-filler"
26
27STATISTIC(FilledSlots, "Number of delay slots filled");
28
29static 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
34namespace {
35struct 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};
80char Filler::ID = 0;
81} // end of anonymous namespace
82
83// createLanaiDelaySlotFillerPass - Returns a pass that fills in delay
84// slots in Lanai MachineFunctions
85FunctionPass *
86llvm::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.
92bool 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
146bool 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
180bool 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.
227void 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.
257bool 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