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