LLVM 17.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
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
30#include "llvm/MC/MCInstrDesc.h"
32#include "llvm/Support/Debug.h"
34#include <cassert>
35#include <utility>
36
37using 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.
140static 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
159void 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
253void 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.
357bool
358CriticalAntiDepBreaker::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
399unsigned CriticalAntiDepBreaker::
400findSuitableFreeRegister(RegRefIter RegRefBegin,
401 RegRefIter RegRefEnd,
402 unsigned AntiDepReg,
403 unsigned LastNewReg,
404 const TargetRegisterClass *RC,
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
444BreakAntiDependencies(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}
unsigned const MachineRegisterInfo * MRI
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
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...
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & reset()
Definition: BitVector.h:392
BitVector & set()
Definition: BitVector.h:351
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...
void FinishBlock() override
Finish anti-dep breaking for a basic block.
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
void StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
CriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
MCRegAliasIterator enumerates all registers aliasing Reg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MCSubRegIterator enumerates all sub-registers of Reg.
MCSuperRegIterator enumerates all super-registers of Reg.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction.
iterator_range< succ_iterator > successors()
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
BitVector getPristineRegs(const MachineFunction &MF) const
Return a set of physical registers that are pristine.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
Scheduling dependency.
Definition: ScheduleDAG.h:49
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
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
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
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,...
Reg
All possible values of the reg field in the ModR/M byte.
constexpr double e
Definition: MathExtras.h:31
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
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.
@ Keep
No function return thunk.