xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/CriticalAntiDepBreaker.cpp (revision 3e8eb5c7f4909209c042403ddee340b2ee7003a5)
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"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineOperand.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/RegisterClassInfo.h"
26 #include "llvm/CodeGen/ScheduleDAG.h"
27 #include "llvm/CodeGen/TargetInstrInfo.h"
28 #include "llvm/CodeGen/TargetRegisterInfo.h"
29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
30 #include "llvm/MC/MCInstrDesc.h"
31 #include "llvm/MC/MCRegisterInfo.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include <cassert>
35 #include <utility>
36 
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "post-RA-sched"
40 
41 CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi,
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 
48 CriticalAntiDepBreaker::~CriticalAntiDepBreaker() = default;
49 
50 void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
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 
96 void CriticalAntiDepBreaker::FinishBlock() {
97   RegRefs.clear();
98   KeepRegs.reset();
99 }
100 
101 void CriticalAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,
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 
443 unsigned CriticalAntiDepBreaker::
444 BreakAntiDependencies(const std::vector<SUnit> &SUnits,
445                       MachineBasicBlock::iterator Begin,
446                       MachineBasicBlock::iterator End,
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
457   DenseMap<MachineInstr *, const SUnit *> 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 
701 AntiDepBreaker *
702 llvm::createCriticalAntiDepBreaker(MachineFunction &MFi,
703                                    const RegisterClassInfo &RCI) {
704   return new CriticalAntiDepBreaker(MFi, RCI);
705 }
706