LLVM 19.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 = 1, 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 = 1; 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 (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
217 KeepRegs.set(SubReg);
218 }
219 }
220 }
221
222 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
223 const MachineOperand &MO = MI.getOperand(I);
224 if (!MO.isReg()) continue;
225 Register Reg = MO.getReg();
226 if (!Reg.isValid())
227 continue;
228 // If this reg is tied and live (Classes[Reg] is set to -1), we can't change
229 // it or any of its sub or super regs. We need to use KeepRegs to mark the
230 // reg because not all uses of the same reg within an instruction are
231 // necessarily tagged as tied.
232 // Example: an x86 "xor %eax, %eax" will have one source operand tied to the
233 // def register but not the second (see PR20020 for details).
234 // FIXME: can this check be relaxed to account for undef uses
235 // of a register? In the above 'xor' example, the uses of %eax are undef, so
236 // earlier instructions could still replace %eax even though the 'xor'
237 // itself can't be changed.
238 if (MI.isRegTiedToUseOperand(I) &&
239 Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) {
240 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
241 KeepRegs.set(SubReg);
242 }
243 for (MCPhysReg SuperReg : TRI->superregs(Reg)) {
244 KeepRegs.set(SuperReg);
245 }
246 }
247 }
248}
249
250void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) {
251 // Update liveness.
252 // Proceeding upwards, registers that are defed but not used in this
253 // instruction are now dead.
254 assert(!MI.isKill() && "Attempting to scan a kill instruction");
255
256 if (!TII->isPredicated(MI)) {
257 // Predicated defs are modeled as read + write, i.e. similar to two
258 // address updates.
259 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
260 MachineOperand &MO = MI.getOperand(i);
261
262 if (MO.isRegMask()) {
263 auto ClobbersPhysRegAndSubRegs = [&](unsigned PhysReg) {
264 return all_of(TRI->subregs_inclusive(PhysReg),
265 [&](MCPhysReg SR) { return MO.clobbersPhysReg(SR); });
266 };
267
268 for (unsigned i = 1, 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 (MCPhysReg SubregReg : TRI->subregs_inclusive(Reg)) {
295 DefIndices[SubregReg] = Count;
296 KillIndices[SubregReg] = ~0u;
297 Classes[SubregReg] = nullptr;
298 RegRefs.erase(SubregReg);
299 if (!Keep)
300 KeepRegs.reset(SubregReg);
301 }
302 // Conservatively mark super-registers as unusable.
303 for (MCPhysReg SR : TRI->superregs(Reg))
304 Classes[SR] = reinterpret_cast<TargetRegisterClass *>(-1);
305 }
306 }
307 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
308 MachineOperand &MO = MI.getOperand(i);
309 if (!MO.isReg()) continue;
310 Register Reg = MO.getReg();
311 if (Reg == 0) continue;
312 if (!MO.isUse()) continue;
313
314 const TargetRegisterClass *NewRC = nullptr;
315 if (i < MI.getDesc().getNumOperands())
316 NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
317
318 // For now, only allow the register to be changed if its register
319 // class is consistent across all uses.
320 if (!Classes[Reg] && NewRC)
321 Classes[Reg] = NewRC;
322 else if (!NewRC || Classes[Reg] != NewRC)
323 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
324
325 RegRefs.insert(std::make_pair(Reg, &MO));
326
327 // It wasn't previously live but now it is, this is a kill.
328 // Repeat for all aliases.
329 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
330 unsigned AliasReg = *AI;
331 if (KillIndices[AliasReg] == ~0u) {
332 KillIndices[AliasReg] = Count;
333 DefIndices[AliasReg] = ~0u;
334 }
335 }
336 }
337}
338
339// Check all machine operands that reference the antidependent register and must
340// be replaced by NewReg. Return true if any of their parent instructions may
341// clobber the new register.
342//
343// Note: AntiDepReg may be referenced by a two-address instruction such that
344// it's use operand is tied to a def operand. We guard against the case in which
345// the two-address instruction also defines NewReg, as may happen with
346// pre/postincrement loads. In this case, both the use and def operands are in
347// RegRefs because the def is inserted by PrescanInstruction and not erased
348// during ScanInstruction. So checking for an instruction with definitions of
349// both NewReg and AntiDepReg covers it.
350bool
351CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,
352 RegRefIter RegRefEnd,
353 unsigned NewReg) {
354 for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) {
355 MachineOperand *RefOper = I->second;
356
357 // Don't allow the instruction defining AntiDepReg to earlyclobber its
358 // operands, in case they may be assigned to NewReg. In this case antidep
359 // breaking must fail, but it's too rare to bother optimizing.
360 if (RefOper->isDef() && RefOper->isEarlyClobber())
361 return true;
362
363 // Handle cases in which this instruction defines NewReg.
364 MachineInstr *MI = RefOper->getParent();
365 for (const MachineOperand &CheckOper : MI->operands()) {
366 if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))
367 return true;
368
369 if (!CheckOper.isReg() || !CheckOper.isDef() ||
370 CheckOper.getReg() != NewReg)
371 continue;
372
373 // Don't allow the instruction to define NewReg and AntiDepReg.
374 // When AntiDepReg is renamed it will be an illegal op.
375 if (RefOper->isDef())
376 return true;
377
378 // Don't allow an instruction using AntiDepReg to be earlyclobbered by
379 // NewReg.
380 if (CheckOper.isEarlyClobber())
381 return true;
382
383 // Don't allow inline asm to define NewReg at all. Who knows what it's
384 // doing with it.
385 if (MI->isInlineAsm())
386 return true;
387 }
388 }
389 return false;
390}
391
392unsigned CriticalAntiDepBreaker::
393findSuitableFreeRegister(RegRefIter RegRefBegin,
394 RegRefIter RegRefEnd,
395 unsigned AntiDepReg,
396 unsigned LastNewReg,
397 const TargetRegisterClass *RC,
399 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC);
400 for (unsigned NewReg : Order) {
401 // Don't replace a register with itself.
402 if (NewReg == AntiDepReg) continue;
403 // Don't replace a register with one that was recently used to repair
404 // an anti-dependence with this AntiDepReg, because that would
405 // re-introduce that anti-dependence.
406 if (NewReg == LastNewReg) continue;
407 // If any instructions that define AntiDepReg also define the NewReg, it's
408 // not suitable. For example, Instruction with multiple definitions can
409 // result in this condition.
410 if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue;
411 // If NewReg is dead and NewReg's most recent def is not before
412 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg.
413 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
414 && "Kill and Def maps aren't consistent for AntiDepReg!");
415 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
416 && "Kill and Def maps aren't consistent for NewReg!");
417 if (KillIndices[NewReg] != ~0u ||
418 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) ||
419 KillIndices[AntiDepReg] > DefIndices[NewReg])
420 continue;
421 // If NewReg overlaps any of the forbidden registers, we can't use it.
422 bool Forbidden = false;
423 for (unsigned R : Forbid)
424 if (TRI->regsOverlap(NewReg, R)) {
425 Forbidden = true;
426 break;
427 }
428 if (Forbidden) continue;
429 return NewReg;
430 }
431
432 // No registers are free and available!
433 return 0;
434}
435
437BreakAntiDependencies(const std::vector<SUnit> &SUnits,
440 unsigned InsertPosIndex,
441 DbgValueVector &DbgValues) {
442 // The code below assumes that there is at least one instruction,
443 // so just duck out immediately if the block is empty.
444 if (SUnits.empty()) return 0;
445
446 // Keep a map of the MachineInstr*'s back to the SUnit representing them.
447 // This is used for updating debug information.
448 //
449 // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap
451
452 // Find the node at the bottom of the critical path.
453 const SUnit *Max = nullptr;
454 for (const SUnit &SU : SUnits) {
455 MISUnitMap[SU.getInstr()] = &SU;
456 if (!Max || SU.getDepth() + SU.Latency > Max->getDepth() + Max->Latency)
457 Max = &SU;
458 }
459 assert(Max && "Failed to find bottom of the critical path");
460
461#ifndef NDEBUG
462 {
463 LLVM_DEBUG(dbgs() << "Critical path has total latency "
464 << (Max->getDepth() + Max->Latency) << "\n");
465 LLVM_DEBUG(dbgs() << "Available regs:");
466 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) {
467 if (KillIndices[Reg] == ~0u)
468 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));
469 }
470 LLVM_DEBUG(dbgs() << '\n');
471 }
472#endif
473
474 // Track progress along the critical path through the SUnit graph as we walk
475 // the instructions.
476 const SUnit *CriticalPathSU = Max;
477 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
478
479 // Consider this pattern:
480 // A = ...
481 // ... = A
482 // A = ...
483 // ... = A
484 // A = ...
485 // ... = A
486 // A = ...
487 // ... = A
488 // There are three anti-dependencies here, and without special care,
489 // we'd break all of them using the same register:
490 // A = ...
491 // ... = A
492 // B = ...
493 // ... = B
494 // B = ...
495 // ... = B
496 // B = ...
497 // ... = B
498 // because at each anti-dependence, B is the first register that
499 // isn't A which is free. This re-introduces anti-dependencies
500 // at all but one of the original anti-dependencies that we were
501 // trying to break. To avoid this, keep track of the most recent
502 // register that each register was replaced with, avoid
503 // using it to repair an anti-dependence on the same register.
504 // This lets us produce this:
505 // A = ...
506 // ... = A
507 // B = ...
508 // ... = B
509 // C = ...
510 // ... = C
511 // B = ...
512 // ... = B
513 // This still has an anti-dependence on B, but at least it isn't on the
514 // original critical path.
515 //
516 // TODO: If we tracked more than one register here, we could potentially
517 // fix that remaining critical edge too. This is a little more involved,
518 // because unlike the most recent register, less recent registers should
519 // still be considered, though only if no other registers are available.
520 std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0);
521
522 // Attempt to break anti-dependence edges on the critical path. Walk the
523 // instructions from the bottom up, tracking information about liveness
524 // as we go to help determine which registers are available.
525 unsigned Broken = 0;
526 unsigned Count = InsertPosIndex - 1;
527 for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) {
528 MachineInstr &MI = *--I;
529 // Kill instructions can define registers but are really nops, and there
530 // might be a real definition earlier that needs to be paired with uses
531 // dominated by this kill.
532
533 // FIXME: It may be possible to remove the isKill() restriction once PR18663
534 // has been properly fixed. There can be value in processing kills as seen
535 // in the AggressiveAntiDepBreaker class.
536 if (MI.isDebugInstr() || MI.isKill())
537 continue;
538
539 // Check if this instruction has a dependence on the critical path that
540 // is an anti-dependence that we may be able to break. If it is, set
541 // AntiDepReg to the non-zero register associated with the anti-dependence.
542 //
543 // We limit our attention to the critical path as a heuristic to avoid
544 // breaking anti-dependence edges that aren't going to significantly
545 // impact the overall schedule. There are a limited number of registers
546 // and we want to save them for the important edges.
547 //
548 // TODO: Instructions with multiple defs could have multiple
549 // anti-dependencies. The current code here only knows how to break one
550 // edge per instruction. Note that we'd have to be able to break all of
551 // the anti-dependencies in an instruction in order to be effective.
552 unsigned AntiDepReg = 0;
553 if (&MI == CriticalPathMI) {
554 if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) {
555 const SUnit *NextSU = Edge->getSUnit();
556
557 // Only consider anti-dependence edges.
558 if (Edge->getKind() == SDep::Anti) {
559 AntiDepReg = Edge->getReg();
560 assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
561 if (!MRI.isAllocatable(AntiDepReg))
562 // Don't break anti-dependencies on non-allocatable registers.
563 AntiDepReg = 0;
564 else if (KeepRegs.test(AntiDepReg))
565 // Don't break anti-dependencies if a use down below requires
566 // this exact register.
567 AntiDepReg = 0;
568 else {
569 // If the SUnit has other dependencies on the SUnit that it
570 // anti-depends on, don't bother breaking the anti-dependency
571 // since those edges would prevent such units from being
572 // scheduled past each other regardless.
573 //
574 // Also, if there are dependencies on other SUnits with the
575 // same register as the anti-dependency, don't attempt to
576 // break it.
577 for (const SDep &P : CriticalPathSU->Preds)
578 if (P.getSUnit() == NextSU
579 ? (P.getKind() != SDep::Anti || P.getReg() != AntiDepReg)
580 : (P.getKind() == SDep::Data &&
581 P.getReg() == AntiDepReg)) {
582 AntiDepReg = 0;
583 break;
584 }
585 }
586 }
587 CriticalPathSU = NextSU;
588 CriticalPathMI = CriticalPathSU->getInstr();
589 } else {
590 // We've reached the end of the critical path.
591 CriticalPathSU = nullptr;
592 CriticalPathMI = nullptr;
593 }
594 }
595
596 PrescanInstruction(MI);
597
598 SmallVector<unsigned, 2> ForbidRegs;
599
600 // If MI's defs have a special allocation requirement, don't allow
601 // any def registers to be changed. Also assume all registers
602 // defined in a call must not be changed (ABI).
603 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI))
604 // If this instruction's defs have special allocation requirement, don't
605 // break this anti-dependency.
606 AntiDepReg = 0;
607 else if (AntiDepReg) {
608 // If this instruction has a use of AntiDepReg, breaking it
609 // is invalid. If the instruction defines other registers,
610 // save a list of them so that we don't pick a new register
611 // that overlaps any of them.
612 for (const MachineOperand &MO : MI.operands()) {
613 if (!MO.isReg()) continue;
614 Register Reg = MO.getReg();
615 if (Reg == 0) continue;
616 if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) {
617 AntiDepReg = 0;
618 break;
619 }
620 if (MO.isDef() && Reg != AntiDepReg)
621 ForbidRegs.push_back(Reg);
622 }
623 }
624
625 // Determine AntiDepReg's register class, if it is live and is
626 // consistently used within a single class.
627 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg]
628 : nullptr;
629 assert((AntiDepReg == 0 || RC != nullptr) &&
630 "Register should be live if it's causing an anti-dependence!");
631 if (RC == reinterpret_cast<TargetRegisterClass *>(-1))
632 AntiDepReg = 0;
633
634 // Look for a suitable register to use to break the anti-dependence.
635 //
636 // TODO: Instead of picking the first free register, consider which might
637 // be the best.
638 if (AntiDepReg != 0) {
639 std::pair<std::multimap<unsigned, MachineOperand *>::iterator,
640 std::multimap<unsigned, MachineOperand *>::iterator>
641 Range = RegRefs.equal_range(AntiDepReg);
642 if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second,
643 AntiDepReg,
644 LastNewReg[AntiDepReg],
645 RC, ForbidRegs)) {
646 LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on "
647 << printReg(AntiDepReg, TRI) << " with "
648 << RegRefs.count(AntiDepReg) << " references"
649 << " using " << printReg(NewReg, TRI) << "!\n");
650
651 // Update the references to the old register to refer to the new
652 // register.
653 for (std::multimap<unsigned, MachineOperand *>::iterator
654 Q = Range.first, QE = Range.second; Q != QE; ++Q) {
655 Q->second->setReg(NewReg);
656 // If the SU for the instruction being updated has debug information
657 // related to the anti-dependency register, make sure to update that
658 // as well.
659 const SUnit *SU = MISUnitMap[Q->second->getParent()];
660 if (!SU) continue;
661 UpdateDbgValues(DbgValues, Q->second->getParent(),
662 AntiDepReg, NewReg);
663 }
664
665 // We just went back in time and modified history; the
666 // liveness information for the anti-dependence reg is now
667 // inconsistent. Set the state as if it were dead.
668 Classes[NewReg] = Classes[AntiDepReg];
669 DefIndices[NewReg] = DefIndices[AntiDepReg];
670 KillIndices[NewReg] = KillIndices[AntiDepReg];
671 assert(((KillIndices[NewReg] == ~0u) !=
672 (DefIndices[NewReg] == ~0u)) &&
673 "Kill and Def maps aren't consistent for NewReg!");
674
675 Classes[AntiDepReg] = nullptr;
676 DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
677 KillIndices[AntiDepReg] = ~0u;
678 assert(((KillIndices[AntiDepReg] == ~0u) !=
679 (DefIndices[AntiDepReg] == ~0u)) &&
680 "Kill and Def maps aren't consistent for AntiDepReg!");
681
682 RegRefs.erase(AntiDepReg);
683 LastNewReg[AntiDepReg] = NewReg;
684 ++Broken;
685 }
686 }
687
688 ScanInstruction(MI, Count);
689 }
690
691 return Broken;
692}
693
696 const RegisterClassInfo &RCI) {
697 return new CriticalAntiDepBreaker(MFi, RCI);
698}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#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.
iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
iterator_range< MCSubRegIterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
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:69
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.
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:416
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:262
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:390
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
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.