LLVM  9.0.0svn
DelaySlotFiller.cpp
Go to the documentation of this file.
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"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "delay-slot-filler"
29 
30 STATISTIC(FilledSlots, "Number of delay slots filled");
31 
33  "disable-sparc-delay-filler",
34  cl::init(false),
35  cl::desc("Disable the Sparc delay slot filler."),
36  cl::Hidden);
37 
38 namespace {
39  struct Filler : public MachineFunctionPass {
40  const SparcSubtarget *Subtarget;
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.
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 {
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 
84  findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
85 
86  bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
87 
88  bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
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 ///
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 ///
106 bool 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(); ) {
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 
138 
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)) {
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.
159  } else {
161  }
162  }
163  return Changed;
164 }
165 
167 Filler::findDelayInstr(MachineBasicBlock &MBB,
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) {
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 
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 
227 bool 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  unsigned 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 
289 void 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.
318 void 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  unsigned 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.
343 bool 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 
353 bool 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 
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  unsigned 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 
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  unsigned 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 
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  unsigned 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 
480 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
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 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
FunctionPass * createSparcDelaySlotFillerPass()
createSparcDelaySlotFillerPass - Returns a pass that fills in delay slots in Sparc MachineFunctions ...
unsigned getReg() const
getReg - Returns the register number.
unsigned Reg
STATISTIC(NumFunctions, "Total number of functions")
F(f)
const SparcInstrInfo * getInstrInfo() const override
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI, MachineBasicBlock::iterator OrMI, const TargetInstrInfo *TII)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
bool insertNOPLoad() const
bool fixAllFDIVSQRT() const
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI, MachineBasicBlock::iterator SetHiMI, const TargetInstrInfo *TII)
MCRegAliasIterator enumerates all registers aliasing Reg.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const SparcRegisterInfo * getRegisterInfo() const override
static cl::opt< bool > DisableDelaySlotFiller("disable-sparc-delay-filler", cl::init(false), cl::desc("Disable the Sparc delay slot filler."), cl::Hidden)
Iterator for intrusive lists based on ilist_node.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
MachineOperand class - Representation of each machine instruction operand.
static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI, MachineBasicBlock::iterator AddMI, const TargetInstrInfo *TII)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
int64_t getImm() const
MachineFunctionProperties & set(Property P)
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
#define I(x, y, z)
Definition: MD5.cpp:58
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Properties which a MachineFunction may have at a given point in time.
Helper class for constructing bundles of MachineInstrs.
bool isImplicit() const
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164