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