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