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