LLVM  6.0.0svn
CriticalAntiDepBreaker.cpp
Go to the documentation of this file.
1 //===- CriticalAntiDepBreaker.cpp - Anti-dep breaker ----------------------===//
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 // This file implements the CriticalAntiDepBreaker class, which
11 // implements register anti-dependence breaking along a blocks
12 // critical path during post-RA scheduler.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "CriticalAntiDepBreaker.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/MC/MCInstrDesc.h"
33 #include "llvm/MC/MCRegisterInfo.h"
34 #include "llvm/Support/Debug.h"
36 #include <cassert>
37 #include <map>
38 #include <utility>
39 #include <vector>
40 
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "post-RA-sched"
44 
46  const RegisterClassInfo &RCI)
47  : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()),
48  TII(MF.getSubtarget().getInstrInfo()),
49  TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),
50  Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0),
51  DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {}
52 
54 
56  const unsigned BBSize = BB->size();
57  for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) {
58  // Clear out the register class data.
59  Classes[i] = nullptr;
60 
61  // Initialize the indices to indicate that no registers are live.
62  KillIndices[i] = ~0u;
63  DefIndices[i] = BBSize;
64  }
65 
66  // Clear "do not change" set.
67  KeepRegs.reset();
68 
69  bool IsReturnBlock = BB->isReturnBlock();
70 
71  // Examine the live-in regs of all successors.
73  SE = BB->succ_end(); SI != SE; ++SI)
74  for (const auto &LI : (*SI)->liveins()) {
75  for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
76  unsigned Reg = *AI;
77  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
78  KillIndices[Reg] = BBSize;
79  DefIndices[Reg] = ~0u;
80  }
81  }
82 
83  // Mark live-out callee-saved registers. In a return block this is
84  // all callee-saved registers. In non-return this is any
85  // callee-saved register that is not saved in the prolog.
86  const MachineFrameInfo &MFI = MF.getFrameInfo();
87  BitVector Pristine = MFI.getPristineRegs(MF);
88  for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;
89  ++I) {
90  unsigned Reg = *I;
91  if (!IsReturnBlock && !Pristine.test(Reg))
92  continue;
93  for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
94  unsigned Reg = *AI;
95  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
96  KillIndices[Reg] = BBSize;
97  DefIndices[Reg] = ~0u;
98  }
99  }
100 }
101 
103  RegRefs.clear();
104  KeepRegs.reset();
105 }
106 
108  unsigned InsertPosIndex) {
109  // Kill instructions can define registers but are really nops, and there might
110  // be a real definition earlier that needs to be paired with uses dominated by
111  // this kill.
112 
113  // FIXME: It may be possible to remove the isKill() restriction once PR18663
114  // has been properly fixed. There can be value in processing kills as seen in
115  // the AggressiveAntiDepBreaker class.
116  if (MI.isDebugValue() || MI.isKill())
117  return;
118  assert(Count < InsertPosIndex && "Instruction index out of expected range!");
119 
120  for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
121  if (KillIndices[Reg] != ~0u) {
122  // If Reg is currently live, then mark that it can't be renamed as
123  // we don't know the extent of its live-range anymore (now that it
124  // has been scheduled).
125  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
126  KillIndices[Reg] = Count;
127  } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {
128  // Any register which was defined within the previous scheduling region
129  // may have been rescheduled and its lifetime may overlap with registers
130  // in ways not reflected in our current liveness state. For each such
131  // register, adjust the liveness state to be conservatively correct.
132  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
133 
134  // Move the def index to the end of the previous region, to reflect
135  // that the def could theoretically have been scheduled at the end.
136  DefIndices[Reg] = InsertPosIndex;
137  }
138  }
139 
140  PrescanInstruction(MI);
141  ScanInstruction(MI, Count);
142 }
143 
144 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
145 /// critical path.
146 static const SDep *CriticalPathStep(const SUnit *SU) {
147  const SDep *Next = nullptr;
148  unsigned NextDepth = 0;
149  // Find the predecessor edge with the greatest depth.
150  for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
151  P != PE; ++P) {
152  const SUnit *PredSU = P->getSUnit();
153  unsigned PredLatency = P->getLatency();
154  unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
155  // In the case of a latency tie, prefer an anti-dependency edge over
156  // other types of edges.
157  if (NextDepth < PredTotalLatency ||
158  (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
159  NextDepth = PredTotalLatency;
160  Next = &*P;
161  }
162  }
163  return Next;
164 }
165 
166 void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) {
167  // It's not safe to change register allocation for source operands of
168  // instructions that have special allocation requirements. Also assume all
169  // registers used in a call must not be changed (ABI).
170  // FIXME: The issue with predicated instruction is more complex. We are being
171  // conservative here because the kill markers cannot be trusted after
172  // if-conversion:
173  // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14]
174  // ...
175  // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395]
176  // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12]
177  // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8)
178  //
179  // The first R6 kill is not really a kill since it's killed by a predicated
180  // instruction which may not be executed. The second R6 def may or may not
181  // re-define R6 so it's not safe to change it since the last R6 use cannot be
182  // changed.
183  bool Special =
184  MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI);
185 
186  // Scan the register operands for this instruction and update
187  // Classes and RegRefs.
188  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
189  MachineOperand &MO = MI.getOperand(i);
190  if (!MO.isReg()) continue;
191  unsigned Reg = MO.getReg();
192  if (Reg == 0) continue;
193  const TargetRegisterClass *NewRC = nullptr;
194 
195  if (i < MI.getDesc().getNumOperands())
196  NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
197 
198  // For now, only allow the register to be changed if its register
199  // class is consistent across all uses.
200  if (!Classes[Reg] && NewRC)
201  Classes[Reg] = NewRC;
202  else if (!NewRC || Classes[Reg] != NewRC)
203  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
204 
205  // Now check for aliases.
206  for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
207  // If an alias of the reg is used during the live range, give up.
208  // Note that this allows us to skip checking if AntiDepReg
209  // overlaps with any of the aliases, among other things.
210  unsigned AliasReg = *AI;
211  if (Classes[AliasReg]) {
212  Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);
213  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
214  }
215  }
216 
217  // If we're still willing to consider this register, note the reference.
218  if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1))
219  RegRefs.insert(std::make_pair(Reg, &MO));
220 
221  // If this reg is tied and live (Classes[Reg] is set to -1), we can't change
222  // it or any of its sub or super regs. We need to use KeepRegs to mark the
223  // reg because not all uses of the same reg within an instruction are
224  // necessarily tagged as tied.
225  // Example: an x86 "xor %eax, %eax" will have one source operand tied to the
226  // def register but not the second (see PR20020 for details).
227  // FIXME: can this check be relaxed to account for undef uses
228  // of a register? In the above 'xor' example, the uses of %eax are undef, so
229  // earlier instructions could still replace %eax even though the 'xor'
230  // itself can't be changed.
231  if (MI.isRegTiedToUseOperand(i) &&
232  Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) {
233  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
234  SubRegs.isValid(); ++SubRegs) {
235  KeepRegs.set(*SubRegs);
236  }
237  for (MCSuperRegIterator SuperRegs(Reg, TRI);
238  SuperRegs.isValid(); ++SuperRegs) {
239  KeepRegs.set(*SuperRegs);
240  }
241  }
242 
243  if (MO.isUse() && Special) {
244  if (!KeepRegs.test(Reg)) {
245  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
246  SubRegs.isValid(); ++SubRegs)
247  KeepRegs.set(*SubRegs);
248  }
249  }
250  }
251 }
252 
253 void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) {
254  // Update liveness.
255  // Proceeding upwards, registers that are defed but not used in this
256  // instruction are now dead.
257  assert(!MI.isKill() && "Attempting to scan a kill instruction");
258 
259  if (!TII->isPredicated(MI)) {
260  // Predicated defs are modeled as read + write, i.e. similar to two
261  // address updates.
262  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
263  MachineOperand &MO = MI.getOperand(i);
264 
265  if (MO.isRegMask())
266  for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i)
267  if (MO.clobbersPhysReg(i)) {
268  DefIndices[i] = Count;
269  KillIndices[i] = ~0u;
270  KeepRegs.reset(i);
271  Classes[i] = nullptr;
272  RegRefs.erase(i);
273  }
274 
275  if (!MO.isReg()) continue;
276  unsigned Reg = MO.getReg();
277  if (Reg == 0) continue;
278  if (!MO.isDef()) continue;
279 
280  // Ignore two-addr defs.
281  if (MI.isRegTiedToUseOperand(i))
282  continue;
283 
284  // If we've already marked this reg as unchangeable, don't remove
285  // it or any of its subregs from KeepRegs.
286  bool Keep = KeepRegs.test(Reg);
287 
288  // For the reg itself and all subregs: update the def to current;
289  // reset the kill state, any restrictions, and references.
290  for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) {
291  unsigned SubregReg = *SRI;
292  DefIndices[SubregReg] = Count;
293  KillIndices[SubregReg] = ~0u;
294  Classes[SubregReg] = nullptr;
295  RegRefs.erase(SubregReg);
296  if (!Keep)
297  KeepRegs.reset(SubregReg);
298  }
299  // Conservatively mark super-registers as unusable.
300  for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
301  Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1);
302  }
303  }
304  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
305  MachineOperand &MO = MI.getOperand(i);
306  if (!MO.isReg()) continue;
307  unsigned Reg = MO.getReg();
308  if (Reg == 0) continue;
309  if (!MO.isUse()) continue;
310 
311  const TargetRegisterClass *NewRC = nullptr;
312  if (i < MI.getDesc().getNumOperands())
313  NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
314 
315  // For now, only allow the register to be changed if its register
316  // class is consistent across all uses.
317  if (!Classes[Reg] && NewRC)
318  Classes[Reg] = NewRC;
319  else if (!NewRC || Classes[Reg] != NewRC)
320  Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
321 
322  RegRefs.insert(std::make_pair(Reg, &MO));
323 
324  // It wasn't previously live but now it is, this is a kill.
325  // Repeat for all aliases.
326  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
327  unsigned AliasReg = *AI;
328  if (KillIndices[AliasReg] == ~0u) {
329  KillIndices[AliasReg] = Count;
330  DefIndices[AliasReg] = ~0u;
331  }
332  }
333  }
334 }
335 
336 // Check all machine operands that reference the antidependent register and must
337 // be replaced by NewReg. Return true if any of their parent instructions may
338 // clobber the new register.
339 //
340 // Note: AntiDepReg may be referenced by a two-address instruction such that
341 // it's use operand is tied to a def operand. We guard against the case in which
342 // the two-address instruction also defines NewReg, as may happen with
343 // pre/postincrement loads. In this case, both the use and def operands are in
344 // RegRefs because the def is inserted by PrescanInstruction and not erased
345 // during ScanInstruction. So checking for an instruction with definitions of
346 // both NewReg and AntiDepReg covers it.
347 bool
348 CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,
349  RegRefIter RegRefEnd,
350  unsigned NewReg) {
351  for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) {
352  MachineOperand *RefOper = I->second;
353 
354  // Don't allow the instruction defining AntiDepReg to earlyclobber its
355  // operands, in case they may be assigned to NewReg. In this case antidep
356  // breaking must fail, but it's too rare to bother optimizing.
357  if (RefOper->isDef() && RefOper->isEarlyClobber())
358  return true;
359 
360  // Handle cases in which this instruction defines NewReg.
361  MachineInstr *MI = RefOper->getParent();
362  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
363  const MachineOperand &CheckOper = MI->getOperand(i);
364 
365  if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))
366  return true;
367 
368  if (!CheckOper.isReg() || !CheckOper.isDef() ||
369  CheckOper.getReg() != NewReg)
370  continue;
371 
372  // Don't allow the instruction to define NewReg and AntiDepReg.
373  // When AntiDepReg is renamed it will be an illegal op.
374  if (RefOper->isDef())
375  return true;
376 
377  // Don't allow an instruction using AntiDepReg to be earlyclobbered by
378  // NewReg.
379  if (CheckOper.isEarlyClobber())
380  return true;
381 
382  // Don't allow inline asm to define NewReg at all. Who knows what it's
383  // doing with it.
384  if (MI->isInlineAsm())
385  return true;
386  }
387  }
388  return false;
389 }
390 
391 unsigned CriticalAntiDepBreaker::
392 findSuitableFreeRegister(RegRefIter RegRefBegin,
393  RegRefIter RegRefEnd,
394  unsigned AntiDepReg,
395  unsigned LastNewReg,
396  const TargetRegisterClass *RC,
397  SmallVectorImpl<unsigned> &Forbid) {
398  ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC);
399  for (unsigned i = 0; i != Order.size(); ++i) {
400  unsigned NewReg = Order[i];
401  // Don't replace a register with itself.
402  if (NewReg == AntiDepReg) continue;
403  // Don't replace a register with one that was recently used to repair
404  // an anti-dependence with this AntiDepReg, because that would
405  // re-introduce that anti-dependence.
406  if (NewReg == LastNewReg) continue;
407  // If any instructions that define AntiDepReg also define the NewReg, it's
408  // not suitable. For example, Instruction with multiple definitions can
409  // result in this condition.
410  if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue;
411  // If NewReg is dead and NewReg's most recent def is not before
412  // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg.
413  assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
414  && "Kill and Def maps aren't consistent for AntiDepReg!");
415  assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
416  && "Kill and Def maps aren't consistent for NewReg!");
417  if (KillIndices[NewReg] != ~0u ||
418  Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) ||
419  KillIndices[AntiDepReg] > DefIndices[NewReg])
420  continue;
421  // If NewReg overlaps any of the forbidden registers, we can't use it.
422  bool Forbidden = false;
423  for (SmallVectorImpl<unsigned>::iterator it = Forbid.begin(),
424  ite = Forbid.end(); it != ite; ++it)
425  if (TRI->regsOverlap(NewReg, *it)) {
426  Forbidden = true;
427  break;
428  }
429  if (Forbidden) continue;
430  return NewReg;
431  }
432 
433  // No registers are free and available!
434  return 0;
435 }
436 
438 BreakAntiDependencies(const std::vector<SUnit> &SUnits,
441  unsigned InsertPosIndex,
442  DbgValueVector &DbgValues) {
443  // The code below assumes that there is at least one instruction,
444  // so just duck out immediately if the block is empty.
445  if (SUnits.empty()) return 0;
446 
447  // Keep a map of the MachineInstr*'s back to the SUnit representing them.
448  // This is used for updating debug information.
449  //
450  // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap
452 
453  // Find the node at the bottom of the critical path.
454  const SUnit *Max = nullptr;
455  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
456  const SUnit *SU = &SUnits[i];
457  MISUnitMap[SU->getInstr()] = SU;
458  if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency)
459  Max = SU;
460  }
461 
462 #ifndef NDEBUG
463  {
464  DEBUG(dbgs() << "Critical path has total latency "
465  << (Max->getDepth() + Max->Latency) << "\n");
466  DEBUG(dbgs() << "Available regs:");
467  for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
468  if (KillIndices[Reg] == ~0u)
469  DEBUG(dbgs() << " " << TRI->getName(Reg));
470  }
471  DEBUG(dbgs() << '\n');
472  }
473 #endif
474 
475  // Track progress along the critical path through the SUnit graph as we walk
476  // the instructions.
477  const SUnit *CriticalPathSU = Max;
478  MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
479 
480  // Consider this pattern:
481  // A = ...
482  // ... = A
483  // A = ...
484  // ... = A
485  // A = ...
486  // ... = A
487  // A = ...
488  // ... = A
489  // There are three anti-dependencies here, and without special care,
490  // we'd break all of them using the same register:
491  // A = ...
492  // ... = A
493  // B = ...
494  // ... = B
495  // B = ...
496  // ... = B
497  // B = ...
498  // ... = B
499  // because at each anti-dependence, B is the first register that
500  // isn't A which is free. This re-introduces anti-dependencies
501  // at all but one of the original anti-dependencies that we were
502  // trying to break. To avoid this, keep track of the most recent
503  // register that each register was replaced with, avoid
504  // using it to repair an anti-dependence on the same register.
505  // This lets us produce this:
506  // A = ...
507  // ... = A
508  // B = ...
509  // ... = B
510  // C = ...
511  // ... = C
512  // B = ...
513  // ... = B
514  // This still has an anti-dependence on B, but at least it isn't on the
515  // original critical path.
516  //
517  // TODO: If we tracked more than one register here, we could potentially
518  // fix that remaining critical edge too. This is a little more involved,
519  // because unlike the most recent register, less recent registers should
520  // still be considered, though only if no other registers are available.
521  std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0);
522 
523  // Attempt to break anti-dependence edges on the critical path. Walk the
524  // instructions from the bottom up, tracking information about liveness
525  // as we go to help determine which registers are available.
526  unsigned Broken = 0;
527  unsigned Count = InsertPosIndex - 1;
528  for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) {
529  MachineInstr &MI = *--I;
530  // Kill instructions can define registers but are really nops, and there
531  // might be a real definition earlier that needs to be paired with uses
532  // dominated by this kill.
533 
534  // FIXME: It may be possible to remove the isKill() restriction once PR18663
535  // has been properly fixed. There can be value in processing kills as seen
536  // in the AggressiveAntiDepBreaker class.
537  if (MI.isDebugValue() || MI.isKill())
538  continue;
539 
540  // Check if this instruction has a dependence on the critical path that
541  // is an anti-dependence that we may be able to break. If it is, set
542  // AntiDepReg to the non-zero register associated with the anti-dependence.
543  //
544  // We limit our attention to the critical path as a heuristic to avoid
545  // breaking anti-dependence edges that aren't going to significantly
546  // impact the overall schedule. There are a limited number of registers
547  // and we want to save them for the important edges.
548  //
549  // TODO: Instructions with multiple defs could have multiple
550  // anti-dependencies. The current code here only knows how to break one
551  // edge per instruction. Note that we'd have to be able to break all of
552  // the anti-dependencies in an instruction in order to be effective.
553  unsigned AntiDepReg = 0;
554  if (&MI == CriticalPathMI) {
555  if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) {
556  const SUnit *NextSU = Edge->getSUnit();
557 
558  // Only consider anti-dependence edges.
559  if (Edge->getKind() == SDep::Anti) {
560  AntiDepReg = Edge->getReg();
561  assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
562  if (!MRI.isAllocatable(AntiDepReg))
563  // Don't break anti-dependencies on non-allocatable registers.
564  AntiDepReg = 0;
565  else if (KeepRegs.test(AntiDepReg))
566  // Don't break anti-dependencies if a use down below requires
567  // this exact register.
568  AntiDepReg = 0;
569  else {
570  // If the SUnit has other dependencies on the SUnit that it
571  // anti-depends on, don't bother breaking the anti-dependency
572  // since those edges would prevent such units from being
573  // scheduled past each other regardless.
574  //
575  // Also, if there are dependencies on other SUnits with the
576  // same register as the anti-dependency, don't attempt to
577  // break it.
578  for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(),
579  PE = CriticalPathSU->Preds.end(); P != PE; ++P)
580  if (P->getSUnit() == NextSU ?
581  (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
582  (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
583  AntiDepReg = 0;
584  break;
585  }
586  }
587  }
588  CriticalPathSU = NextSU;
589  CriticalPathMI = CriticalPathSU->getInstr();
590  } else {
591  // We've reached the end of the critical path.
592  CriticalPathSU = nullptr;
593  CriticalPathMI = nullptr;
594  }
595  }
596 
597  PrescanInstruction(MI);
598 
599  SmallVector<unsigned, 2> ForbidRegs;
600 
601  // If MI's defs have a special allocation requirement, don't allow
602  // any def registers to be changed. Also assume all registers
603  // defined in a call must not be changed (ABI).
604  if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI))
605  // If this instruction's defs have special allocation requirement, don't
606  // break this anti-dependency.
607  AntiDepReg = 0;
608  else if (AntiDepReg) {
609  // If this instruction has a use of AntiDepReg, breaking it
610  // is invalid. If the instruction defines other registers,
611  // save a list of them so that we don't pick a new register
612  // that overlaps any of them.
613  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
614  MachineOperand &MO = MI.getOperand(i);
615  if (!MO.isReg()) continue;
616  unsigned Reg = MO.getReg();
617  if (Reg == 0) continue;
618  if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) {
619  AntiDepReg = 0;
620  break;
621  }
622  if (MO.isDef() && Reg != AntiDepReg)
623  ForbidRegs.push_back(Reg);
624  }
625  }
626 
627  // Determine AntiDepReg's register class, if it is live and is
628  // consistently used within a single class.
629  const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg]
630  : nullptr;
631  assert((AntiDepReg == 0 || RC != nullptr) &&
632  "Register should be live if it's causing an anti-dependence!");
633  if (RC == reinterpret_cast<TargetRegisterClass *>(-1))
634  AntiDepReg = 0;
635 
636  // Look for a suitable register to use to break the anti-dependence.
637  //
638  // TODO: Instead of picking the first free register, consider which might
639  // be the best.
640  if (AntiDepReg != 0) {
641  std::pair<std::multimap<unsigned, MachineOperand *>::iterator,
642  std::multimap<unsigned, MachineOperand *>::iterator>
643  Range = RegRefs.equal_range(AntiDepReg);
644  if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second,
645  AntiDepReg,
646  LastNewReg[AntiDepReg],
647  RC, ForbidRegs)) {
648  DEBUG(dbgs() << "Breaking anti-dependence edge on "
649  << TRI->getName(AntiDepReg)
650  << " with " << RegRefs.count(AntiDepReg) << " references"
651  << " using " << TRI->getName(NewReg) << "!\n");
652 
653  // Update the references to the old register to refer to the new
654  // register.
655  for (std::multimap<unsigned, MachineOperand *>::iterator
656  Q = Range.first, QE = Range.second; Q != QE; ++Q) {
657  Q->second->setReg(NewReg);
658  // If the SU for the instruction being updated has debug information
659  // related to the anti-dependency register, make sure to update that
660  // as well.
661  const SUnit *SU = MISUnitMap[Q->second->getParent()];
662  if (!SU) continue;
663  UpdateDbgValues(DbgValues, Q->second->getParent(),
664  AntiDepReg, NewReg);
665  }
666 
667  // We just went back in time and modified history; the
668  // liveness information for the anti-dependence reg is now
669  // inconsistent. Set the state as if it were dead.
670  Classes[NewReg] = Classes[AntiDepReg];
671  DefIndices[NewReg] = DefIndices[AntiDepReg];
672  KillIndices[NewReg] = KillIndices[AntiDepReg];
673  assert(((KillIndices[NewReg] == ~0u) !=
674  (DefIndices[NewReg] == ~0u)) &&
675  "Kill and Def maps aren't consistent for NewReg!");
676 
677  Classes[AntiDepReg] = nullptr;
678  DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
679  KillIndices[AntiDepReg] = ~0u;
680  assert(((KillIndices[AntiDepReg] == ~0u) !=
681  (DefIndices[AntiDepReg] == ~0u)) &&
682  "Kill and Def maps aren't consistent for AntiDepReg!");
683 
684  RegRefs.erase(AntiDepReg);
685  LastNewReg[AntiDepReg] = NewReg;
686  ++Broken;
687  }
688  }
689 
690  ScanInstruction(MI, Count);
691  }
692 
693  return Broken;
694 }
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
void push_back(const T &Elt)
Definition: SmallVector.h:212
BitVector & set()
Definition: BitVector.h:398
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn&#39;t been...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool hasExtraDefRegAllocReq(QueryType Type=AnyInBundle) const
Returns true if this instruction def operands have special register allocation requirements that are ...
Definition: MachineInstr.h:746
void FinishBlock() override
Finish anti-dep breaking for a basic block.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:403
unsigned getReg() const
getReg - Returns the register number.
bool isInlineAsm() const
Definition: MachineInstr.h:832
bool test(unsigned Idx) const
Definition: BitVector.h:502
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:261
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:55
bool isEarlyClobber() const
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
MCSuperRegIterator enumerates all super-registers of Reg.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
const HexagonInstrInfo * TII
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:266
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:54
Reg
All possible values of the reg field in the ModR/M byte.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:287
const TargetRegisterClass * getRegClass(const MCInstrDesc &TID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
const char * getName(unsigned RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
Scheduling dependency.
Definition: ScheduleDAG.h:50
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:378
unsigned const MachineRegisterInfo * MRI
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:278
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
MCRegAliasIterator enumerates all registers aliasing Reg.
BitVector & reset()
Definition: BitVector.h:439
static const unsigned End
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
CriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
unsigned BreakAntiDependencies(const std::vector< SUnit > &SUnits, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned InsertPosIndex, DbgValueVector &DbgValues) override
Identifiy anti-dependencies along the critical path of the ScheduleDAG and break them by renaming reg...
MCSubRegIterator enumerates all sub-registers of Reg.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled...
Representation of each machine instruction.
Definition: MachineInstr.h:59
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasExtraSrcRegAllocReq(QueryType Type=AnyInBundle) const
Returns true if this instruction source operands have special register allocation requirements that a...
Definition: MachineInstr.h:736
static const SDep * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path. ...
bool isKill() const
Definition: MachineInstr.h:830
bool isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx=nullptr) const
Given the index of a register def operand, check if the register def is tied to a source operand...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void UpdateDbgValues(const DbgValueVector &DbgValues, MachineInstr *ParentMI, unsigned OldReg, unsigned NewReg)
Update all DBG_VALUE instructions that may be affected by the dependency breaker&#39;s update of ParentMI...
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
std::vector< MachineBasicBlock * >::iterator succ_iterator
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:247