LLVM 24.0.0git
AggressiveAntiDepBreaker.cpp
Go to the documentation of this file.
1//===- AggressiveAntiDepBreaker.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 AggressiveAntiDepBreaker class, which
10// implements register anti-dependence breaking during post-RA
11// scheduling. It attempts to break all anti-dependencies within a
12// block.
13//
14//===----------------------------------------------------------------------===//
15
17#include "CodeGenOptions.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/SmallSet.h"
32#include "llvm/MC/MCInstrDesc.h"
34#include "llvm/Support/Debug.h"
36#include <cassert>
37
38using namespace llvm;
39
40#define DEBUG_TYPE "post-RA-sched"
41
44 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
45 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
46 DefIndices(TargetRegs, 0) {
47 const unsigned BBSize = BB->size();
48 for (unsigned i = 0; i < NumTargetRegs; ++i) {
49 // Initialize all registers to be in their own group. Initially we
50 // assign the register to the same-indexed GroupNode.
51 GroupNodeIndices[i] = i;
52 // Initialize the indices to indicate that no registers are live.
53 KillIndices[i] = ~0u;
54 DefIndices[i] = BBSize;
55 }
56}
57
59 unsigned Node = GroupNodeIndices[Reg.id()];
60 while (GroupNodes[Node] != Node)
61 Node = GroupNodes[Node];
62
63 return Node;
64}
65
67 unsigned Group, std::vector<MCRegister> &Regs,
68 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
69 *RegRefs) {
70 for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
71 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
72 Regs.push_back(Reg);
73 }
74}
75
77 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");
78 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");
79
80 // find group for each register
81 unsigned Group1 = GetGroup(Reg1);
82 unsigned Group2 = GetGroup(Reg2);
83
84 // if either group is 0, then that must become the parent
85 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
86 unsigned Other = (Parent == Group1) ? Group2 : Group1;
87 GroupNodes.at(Other) = Parent;
88 return Parent;
89}
90
92 // Create a new GroupNode for Reg. Reg's existing GroupNode must
93 // stay as is because there could be other GroupNodes referring to
94 // it.
95 unsigned idx = GroupNodes.size();
96 GroupNodes.push_back(idx);
97 GroupNodeIndices[Reg.id()] = idx;
98 return idx;
99}
100
102 // KillIndex must be defined and DefIndex not defined for a register
103 // to be live.
104 return ((KillIndices[Reg.id()] != ~0u) && (DefIndices[Reg.id()] == ~0u));
105}
106
108 MachineFunction &MFi, const RegisterClassInfo &RCI,
110 : MF(MFi), MRI(MF.getRegInfo()), TII(MF.getSubtarget().getInstrInfo()),
111 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
112 /* Collect a bitset of all registers that are only broken if they
113 are on the critical path. */
114 for (const TargetRegisterClass *RC : CriticalPathRCs) {
115 BitVector CPSet = TRI->getAllocatableSet(MF, RC);
116 if (CriticalPathSet.none())
117 CriticalPathSet = CPSet;
118 else
119 CriticalPathSet |= CPSet;
120 }
121
122 LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
123 LLVM_DEBUG(for (unsigned r
124 : CriticalPathSet.set_bits()) dbgs()
125 << " " << printReg(r, TRI));
126 LLVM_DEBUG(dbgs() << '\n');
127}
128
132
134 assert(!State);
135 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
136
137 std::vector<unsigned> &KillIndices = State->GetKillIndices();
138 std::vector<unsigned> &DefIndices = State->GetDefIndices();
139
140 // Compute the register units live out of the block: the live-ins of all
141 // successors, the pristine registers and, in a return block, the
142 // callee-saved registers.
143 LiveRegUnits LiveOuts(*TRI);
144 LiveOuts.addLiveOuts(*BB);
145 const BitVector &LiveOutUnits = LiveOuts.getBitVector();
146
147 // Mark the registers fully covered by live-out units as live, and don't
148 // allow renaming them. A super-register that merely overlaps a live-out
149 // register (e.g. a register tuple) is not live, and treating it as such would
150 // wrongly prevent its other sub-registers from being renamed.
151 for (unsigned R = 1, E = TRI->getNumRegs(); R != E; ++R) {
152 MCRegister Reg(R);
153 if (!all_of(TRI->regunits(Reg), [&](MCRegUnit Unit) {
154 return LiveOutUnits.test(static_cast<unsigned>(Unit));
155 }))
156 continue;
157 State->UnionGroups(Reg, 0);
158 KillIndices[Reg.id()] = BB->size();
159 DefIndices[Reg.id()] = ~0u;
160 }
161}
162
164 delete State;
165 State = nullptr;
166}
167
169 unsigned InsertPosIndex) {
170 assert(Count < InsertPosIndex && "Instruction index out of expected range!");
171
172 std::set<MCRegister> PassthruRegs;
173 GetPassthruRegs(MI, PassthruRegs);
174 PrescanInstruction(MI, Count, PassthruRegs);
175 ScanInstruction(MI, Count);
176
177 LLVM_DEBUG(dbgs() << "Observe: ");
178 LLVM_DEBUG(MI.dump());
179 LLVM_DEBUG(dbgs() << "\tRegs:");
180
181 std::vector<unsigned> &DefIndices = State->GetDefIndices();
182 for (unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) {
183 // If Reg is current live, then mark that it can't be renamed as
184 // we don't know the extent of its live-range anymore (now that it
185 // has been scheduled). If it is not live but was defined in the
186 // previous schedule region, then set its def index to the most
187 // conservative location (i.e. the beginning of the previous
188 // schedule region).
189 if (State->IsLive(Reg)) {
190 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs()
191 << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg)
192 << "->g0(region live-out)");
193 State->UnionGroups(Reg, 0);
194 } else if ((DefIndices[Reg] < InsertPosIndex)
195 && (DefIndices[Reg] >= Count)) {
196 DefIndices[Reg] = Count;
197 }
198 }
199 LLVM_DEBUG(dbgs() << '\n');
200}
201
202bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI,
203 MachineOperand &MO) {
204 if (!MO.isReg() || !MO.isImplicit())
205 return false;
206
207 Register Reg = MO.getReg();
208 if (Reg == 0)
209 return false;
210
211 MachineOperand *Op = nullptr;
212 if (MO.isDef())
213 Op = MI.findRegisterUseOperand(Reg, /*TRI=*/nullptr, true);
214 else
215 Op = MI.findRegisterDefOperand(Reg, /*TRI=*/nullptr);
216
217 return(Op && Op->isImplicit());
218}
219
220void AggressiveAntiDepBreaker::GetPassthruRegs(
221 MachineInstr &MI, std::set<MCRegister> &PassthruRegs) {
222 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
223 MachineOperand &MO = MI.getOperand(i);
224 if (!MO.isReg()) continue;
225 if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) ||
226 IsImplicitDefUse(MI, MO)) {
227 const Register Reg = MO.getReg();
228 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
229 PassthruRegs.insert(SubReg);
230 }
231 }
232}
233
234/// AntiDepEdges - Return in Edges the anti- and output- dependencies
235/// in SU that we want to consider for breaking.
236static void AntiDepEdges(const SUnit *SU, std::vector<const SDep *> &Edges) {
238 for (const SDep &Pred : SU->Preds) {
239 if ((Pred.getKind() == SDep::Anti) || (Pred.getKind() == SDep::Output)) {
240 if (RegSet.insert(Pred.getReg()).second)
241 Edges.push_back(&Pred);
242 }
243 }
244}
245
246/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
247/// critical path.
248static const SUnit *CriticalPathStep(const SUnit *SU) {
249 const SDep *Next = nullptr;
250 unsigned NextDepth = 0;
251 // Find the predecessor edge with the greatest depth.
252 if (SU) {
253 for (const SDep &Pred : SU->Preds) {
254 const SUnit *PredSU = Pred.getSUnit();
255 unsigned PredLatency = Pred.getLatency();
256 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
257 // In the case of a latency tie, prefer an anti-dependency edge over
258 // other types of edges.
259 if (NextDepth < PredTotalLatency ||
260 (NextDepth == PredTotalLatency && Pred.getKind() == SDep::Anti)) {
261 NextDepth = PredTotalLatency;
262 Next = &Pred;
263 }
264 }
265 }
266
267 return (Next) ? Next->getSUnit() : nullptr;
268}
269
270void AggressiveAntiDepBreaker::HandleLastUse(MCRegister Reg, unsigned KillIdx,
271 const char *tag,
272 const char *header,
273 const char *footer) {
274 std::vector<unsigned> &KillIndices = State->GetKillIndices();
275 std::vector<unsigned> &DefIndices = State->GetDefIndices();
276 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
277 &RegRefs = State->GetRegRefs();
278
279 // FIXME: We must leave subregisters of live super registers as live, so that
280 // we don't clear out the register tracking information for subregisters of
281 // super registers we're still tracking (and with which we're unioning
282 // subregister definitions).
283 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
284 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) {
285 LLVM_DEBUG(if (!header && footer) dbgs() << footer);
286 return;
287 }
288
289 if (!State->IsLive(Reg)) {
290 KillIndices[Reg.id()] = KillIdx;
291 DefIndices[Reg.id()] = ~0u;
292 RegRefs.erase(Reg);
293 State->LeaveGroup(Reg);
294 LLVM_DEBUG(if (header) {
295 dbgs() << header << printReg(Reg, TRI);
296 header = nullptr;
297 });
298 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag);
299 // Repeat for subregisters. Note that we only do this if the superregister
300 // was not live because otherwise, regardless whether we have an explicit
301 // use of the subregister, the subregister's contents are needed for the
302 // uses of the superregister.
303 for (MCPhysReg SubregReg : TRI->subregs(Reg)) {
304 if (!State->IsLive(SubregReg)) {
305 KillIndices[SubregReg] = KillIdx;
306 DefIndices[SubregReg] = ~0u;
307 RegRefs.erase(SubregReg);
308 State->LeaveGroup(SubregReg);
309 LLVM_DEBUG(if (header) {
310 dbgs() << header << printReg(Reg, TRI);
311 header = nullptr;
312 });
313 LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g"
314 << State->GetGroup(SubregReg) << tag);
315 }
316 }
317 }
318
319 LLVM_DEBUG(if (!header && footer) dbgs() << footer);
320}
321
322void AggressiveAntiDepBreaker::PrescanInstruction(
323 MachineInstr &MI, unsigned Count,
324 const std::set<MCRegister> &PassthruRegs) {
325 std::vector<unsigned> &DefIndices = State->GetDefIndices();
326 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
327 &RegRefs = State->GetRegRefs();
328
329 // Handle dead defs by simulating a last-use of the register just
330 // after the def. A dead def can occur because the def is truly
331 // dead, or because only a subregister is live at the def. If we
332 // don't do this the dead def will be incorrectly merged into the
333 // previous def.
334 for (const MachineOperand &MO : MI.all_defs()) {
335 Register Reg = MO.getReg();
336 if (!Reg)
337 continue;
338
339 HandleLastUse(Reg.asMCReg(), Count + 1, "", "\tDead Def: ", "\n");
340 }
341
342 LLVM_DEBUG(dbgs() << "\tDef Groups:");
343 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
344 MachineOperand &MO = MI.getOperand(i);
345 if (!MO.isReg() || !MO.isDef()) continue;
346 Register Reg = MO.getReg();
347 if (!Reg)
348 continue;
349
350 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"
351 << State->GetGroup(Reg));
352
353 // If MI's defs have a special allocation requirement, don't allow
354 // any def registers to be changed. Also assume all registers
355 // defined in a call must not be changed (ABI). Inline assembly may
356 // reference either system calls or the register directly. Skip it until we
357 // can tell user specified registers from compiler-specified.
358 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) ||
359 MI.isInlineAsm()) {
360 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
361 State->UnionGroups(Reg, 0);
362 }
363
364 // Any aliased that are live at this point are completely or
365 // partially defined here, so group those aliases with Reg.
366 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
367 MCRegister AliasReg = *AI;
368 if (State->IsLive(AliasReg)) {
369 State->UnionGroups(Reg, AliasReg);
370 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via "
371 << printReg(AliasReg, TRI) << ")");
372 }
373 }
374
375 // Note register reference...
376 const TargetRegisterClass *RC = nullptr;
377 if (i < MI.getDesc().getNumOperands())
378 RC = TII->getRegClass(MI.getDesc(), i);
379 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
380 RegRefs.emplace(Reg.asMCReg(), RR);
381 }
382
383 LLVM_DEBUG(dbgs() << '\n');
384
385 // Scan the register defs for this instruction and update
386 // live-ranges.
387 for (const MachineOperand &MO : MI.all_defs()) {
388 Register Reg = MO.getReg();
389 if (!Reg)
390 continue;
391 // Ignore KILLs and passthru registers for liveness...
392 if (MI.isKill() || (PassthruRegs.count(Reg) != 0))
393 continue;
394
395 // Update def for Reg and aliases.
396 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
397 // We need to be careful here not to define already-live super registers.
398 // If the super register is already live, then this definition is not
399 // a definition of the whole super register (just a partial insertion
400 // into it). Earlier subregister definitions (which we've not yet visited
401 // because we're iterating bottom-up) need to be linked to the same group
402 // as this definition.
403 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI))
404 continue;
405
406 DefIndices[(*AI).id()] = Count;
407 }
408 }
409}
410
411void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI,
412 unsigned Count) {
413 LLVM_DEBUG(dbgs() << "\tUse Groups:");
414 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
415 &RegRefs = State->GetRegRefs();
416
417 // If MI's uses have special allocation requirement, don't allow
418 // any use registers to be changed. Also assume all registers
419 // used in a call must not be changed (ABI).
420 // Inline Assembly register uses also cannot be safely changed.
421 // FIXME: The issue with predicated instruction is more complex. We are being
422 // conservatively here because the kill markers cannot be trusted after
423 // if-conversion:
424 // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14]
425 // ...
426 // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395]
427 // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12]
428 // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8)
429 //
430 // The first R6 kill is not really a kill since it's killed by a predicated
431 // instruction which may not be executed. The second R6 def may or may not
432 // re-define R6 so it's not safe to change it since the last R6 use cannot be
433 // changed.
434 bool Special = MI.isCall() || MI.hasExtraSrcRegAllocReq() ||
435 TII->isPredicated(MI) || MI.isInlineAsm();
436
437 // Scan the register uses for this instruction and update
438 // live-ranges, groups and RegRefs.
439 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
440 MachineOperand &MO = MI.getOperand(i);
441 if (!MO.isReg() || !MO.isUse()) continue;
442 Register Reg = MO.getReg();
443 if (!Reg)
444 continue;
445
446 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"
447 << State->GetGroup(Reg));
448
449 // It wasn't previously live but now it is, this is a kill. Forget
450 // the previous live-range information and start a new live-range
451 // for the register.
452 HandleLastUse(Reg.asMCReg(), Count, "(last-use)");
453
454 if (Special) {
455 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
456 State->UnionGroups(Reg, 0);
457 }
458
459 // Note register reference...
460 const TargetRegisterClass *RC = nullptr;
461 if (i < MI.getDesc().getNumOperands())
462 RC = TII->getRegClass(MI.getDesc(), i);
463 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
464 RegRefs.emplace(Reg.asMCReg(), RR);
465 }
466
467 LLVM_DEBUG(dbgs() << '\n');
468
469 // Form a group of all defs and uses of a KILL instruction to ensure
470 // that all registers are renamed as a group.
471 if (MI.isKill()) {
472 LLVM_DEBUG(dbgs() << "\tKill Group:");
473
474 Register FirstReg;
475 for (const MachineOperand &MO : MI.operands()) {
476 if (!MO.isReg()) continue;
477 Register Reg = MO.getReg();
478 if (!Reg)
479 continue;
480
481 if (FirstReg) {
482 LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI));
483 State->UnionGroups(FirstReg, Reg);
484 } else {
485 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));
486 FirstReg = Reg;
487 }
488 }
489
490 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n');
491 }
492}
493
494BitVector AggressiveAntiDepBreaker::GetRenameRegisters(MCRegister Reg) {
495 BitVector BV(TRI->getNumRegs(), false);
496 bool first = true;
497
498 // Check all references that need rewriting for Reg. For each, use
499 // the corresponding register class to narrow the set of registers
500 // that are appropriate for renaming.
501 for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) {
502 const TargetRegisterClass *RC = Q.second.RC;
503 if (!RC) continue;
504
505 BitVector RCBV = TRI->getAllocatableSet(MF, RC);
506 if (first) {
507 BV |= RCBV;
508 first = false;
509 } else {
510 BV &= RCBV;
511 }
512
513 LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC));
514 }
515
516 return BV;
517}
518
519bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
520 MCRegister SuperReg, unsigned AntiDepGroupIndex,
521 RenameOrderType &RenameOrder, std::map<MCRegister, MCRegister> &RenameMap) {
522 std::vector<unsigned> &KillIndices = State->GetKillIndices();
523 std::vector<unsigned> &DefIndices = State->GetDefIndices();
524 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
525 &RegRefs = State->GetRegRefs();
526
527 // Collect all referenced registers in the same group as
528 // AntiDepReg. These all need to be renamed together if we are to
529 // break the anti-dependence.
530 std::vector<MCRegister> Regs;
531 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
532 assert(!Regs.empty() && "Empty register group!");
533 if (Regs.empty())
534 return false;
535
536 // Collect the BitVector of registers that can be used to rename
537 // each register.
538 LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
539 << ":\n");
540 std::map<MCRegister, BitVector> RenameRegisterMap;
541 for (MCRegister Reg : Regs) {
542 // If Reg has any references, then collect possible rename regs
543 if (RegRefs.count(Reg) > 0) {
544 LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":");
545
546 BitVector &BV = RenameRegisterMap[Reg];
547 assert(BV.empty());
548 BV = GetRenameRegisters(Reg);
549
550 LLVM_DEBUG({
551 dbgs() << " ::";
552 for (unsigned r : BV.set_bits())
553 dbgs() << " " << printReg(r, TRI);
554 dbgs() << "\n";
555 });
556 }
557 }
558
559 // All group registers should be a subreg of SuperReg.
560 for (MCRegister Reg : Regs) {
561 if (Reg == SuperReg) continue;
562 bool IsSub = TRI->isSubRegister(SuperReg, Reg);
563 // FIXME: remove this once PR18663 has been properly fixed. For now,
564 // return a conservative answer:
565 // assert(IsSub && "Expecting group subregister");
566 if (!IsSub)
567 return false;
568 }
569
570#ifndef NDEBUG
571 // If -agg-antidep-debugdiv=D is positive, only rename when
572 // renamecnt % D == -agg-antidep-debugmod.
573 const CodeGenOptions &Opts = getCodeGenOptions(MF);
574 if (Opts.agg_antidep_debugdiv > 0) {
575 static int renamecnt = 0;
576 if (renamecnt++ % Opts.agg_antidep_debugdiv != Opts.agg_antidep_debugmod)
577 return false;
578
579 dbgs() << "*** Performing rename " << printReg(SuperReg, TRI)
580 << " for debug ***\n";
581 }
582#endif
583
584 // Check each possible rename register for SuperReg in round-robin
585 // order. If that register is available, and the corresponding
586 // registers are available for the other group subregisters, then we
587 // can use those registers to rename.
588
589 // FIXME: Using getMinimalPhysRegClass is very conservative. We should
590 // check every use of the register and find the largest register class
591 // that can be used in all of them.
592 const TargetRegisterClass *SuperRC = TRI->getMinimalPhysRegClass(SuperReg);
593
594 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC);
595 if (Order.empty()) {
596 LLVM_DEBUG(dbgs() << "\tEmpty Super Regclass!!\n");
597 return false;
598 }
599
600 LLVM_DEBUG(dbgs() << "\tFind Registers:");
601
602 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
603
604 unsigned OrigR = RenameOrder[SuperRC];
605 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
606 unsigned R = OrigR;
607 do {
608 if (R == 0) R = Order.size();
609 --R;
610 const MCRegister NewSuperReg = Order[R];
611 // Don't consider non-allocatable registers
612 if (!MRI.isAllocatable(NewSuperReg)) continue;
613 // Don't replace a register with itself.
614 if (NewSuperReg == SuperReg) continue;
615
616 LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':');
617 RenameMap.clear();
618
619 // For each referenced group register (which must be a SuperReg or
620 // a subregister of SuperReg), find the corresponding subregister
621 // of NewSuperReg and make sure it is free to be renamed.
622 for (MCRegister Reg : Regs) {
623 MCRegister NewReg;
624 if (Reg == SuperReg) {
625 NewReg = NewSuperReg;
626 } else {
627 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg);
628 if (NewSubRegIdx != 0)
629 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);
630 }
631
632 LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI));
633
634 // Check if Reg can be renamed to NewReg.
635 if (!RenameRegisterMap[Reg].test(NewReg.id())) {
636 LLVM_DEBUG(dbgs() << "(no rename)");
637 goto next_super_reg;
638 }
639
640 // If NewReg is dead and NewReg's most recent def is not before
641 // Regs's kill, it's safe to replace Reg with NewReg. We
642 // must also check all aliases of NewReg, because we can't define a
643 // register when any sub or super is already live.
644 if (State->IsLive(NewReg) ||
645 (KillIndices[Reg.id()] > DefIndices[NewReg.id()])) {
646 LLVM_DEBUG(dbgs() << "(live)");
647 goto next_super_reg;
648 } else {
649 bool found = false;
650 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {
651 MCRegister AliasReg = *AI;
652 if (State->IsLive(AliasReg) ||
653 (KillIndices[Reg.id()] > DefIndices[AliasReg.id()])) {
655 << "(alias " << printReg(AliasReg, TRI) << " live)");
656 found = true;
657 break;
658 }
659 }
660 if (found)
661 goto next_super_reg;
662 }
663
664 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also
665 // defines 'NewReg' via an early-clobber operand.
666 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
667 MachineInstr *UseMI = Q.second.Operand->getParent();
668 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, TRI, false, true);
669 if (Idx == -1)
670 continue;
671
672 if (UseMI->getOperand(Idx).isEarlyClobber()) {
673 LLVM_DEBUG(dbgs() << "(ec)");
674 goto next_super_reg;
675 }
676 }
677
678 // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining
679 // 'Reg' is an early-clobber define and that instruction also uses
680 // 'NewReg'.
681 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
682 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
683 continue;
684
685 MachineInstr *DefMI = Q.second.Operand->getParent();
686 if (DefMI->readsRegister(NewReg, TRI)) {
687 LLVM_DEBUG(dbgs() << "(ec)");
688 goto next_super_reg;
689 }
690 }
691
692 // Record that 'Reg' can be renamed to 'NewReg'.
693 RenameMap.insert(std::make_pair(Reg, NewReg));
694 }
695
696 // If we fall-out here, then every register in the group can be
697 // renamed, as recorded in RenameMap.
698 RenameOrder.erase(SuperRC);
699 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
700 LLVM_DEBUG(dbgs() << "]\n");
701 return true;
702
703 next_super_reg:
704 LLVM_DEBUG(dbgs() << ']');
705 } while (R != EndR);
706
707 LLVM_DEBUG(dbgs() << '\n');
708
709 // No registers are free and available!
710 return false;
711}
712
713/// BreakAntiDependencies - Identifiy anti-dependencies within the
714/// ScheduleDAG and break them by renaming registers.
716 const std::vector<SUnit> &SUnits,
719 unsigned InsertPosIndex,
720 DbgValueVector &DbgValues) {
721 std::vector<unsigned> &KillIndices = State->GetKillIndices();
722 std::vector<unsigned> &DefIndices = State->GetDefIndices();
723 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
724 &RegRefs = State->GetRegRefs();
725
726 // The code below assumes that there is at least one instruction,
727 // so just duck out immediately if the block is empty.
728 if (SUnits.empty()) return 0;
729
730 // For each regclass the next register to use for renaming.
731 RenameOrderType RenameOrder;
732
733 // ...need a map from MI to SUnit.
734 std::map<MachineInstr *, const SUnit *> MISUnitMap;
735 for (const SUnit &SU : SUnits)
736 MISUnitMap.insert(std::make_pair(SU.getInstr(), &SU));
737
738 // Track progress along the critical path through the SUnit graph as
739 // we walk the instructions. This is needed for regclasses that only
740 // break critical-path anti-dependencies.
741 const SUnit *CriticalPathSU = nullptr;
742 MachineInstr *CriticalPathMI = nullptr;
743 if (CriticalPathSet.any()) {
744 for (const SUnit &SU : SUnits) {
745 if (!CriticalPathSU ||
746 ((SU.getDepth() + SU.Latency) >
747 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {
748 CriticalPathSU = &SU;
749 }
750 }
751 assert(CriticalPathSU && "Failed to find SUnit critical path");
752 CriticalPathMI = CriticalPathSU->getInstr();
753 }
754
755#ifndef NDEBUG
756 LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n");
757 LLVM_DEBUG(dbgs() << "Available regs:");
758 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) {
759 if (!State->IsLive(Reg))
760 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));
761 }
762 LLVM_DEBUG(dbgs() << '\n');
763#endif
764
765 // Attempt to break anti-dependence edges. Walk the instructions
766 // from the bottom up, tracking information about liveness as we go
767 // to help determine which registers are available.
768 unsigned Broken = 0;
769 unsigned Count = InsertPosIndex - 1;
770 for (MachineBasicBlock::iterator I = End, E = Begin;
771 I != E; --Count) {
772 MachineInstr &MI = *--I;
773
774 if (MI.isDebugOrPseudoInstr())
775 continue;
776
777 LLVM_DEBUG(dbgs() << "Anti: ");
778 LLVM_DEBUG(MI.dump());
779
780 std::set<MCRegister> PassthruRegs;
781 GetPassthruRegs(MI, PassthruRegs);
782
783 // Process the defs in MI...
784 PrescanInstruction(MI, Count, PassthruRegs);
785
786 // The dependence edges that represent anti- and output-
787 // dependencies that are candidates for breaking.
788 std::vector<const SDep *> Edges;
789 const SUnit *PathSU = MISUnitMap[&MI];
790 AntiDepEdges(PathSU, Edges);
791
792 // If MI is not on the critical path, then we don't rename
793 // registers in the CriticalPathSet.
794 BitVector *ExcludeRegs = nullptr;
795 if (&MI == CriticalPathMI) {
796 CriticalPathSU = CriticalPathStep(CriticalPathSU);
797 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr;
798 } else if (CriticalPathSet.any()) {
799 ExcludeRegs = &CriticalPathSet;
800 }
801
802 // Ignore KILL instructions (they form a group in ScanInstruction
803 // but don't cause any anti-dependence breaking themselves)
804 if (!MI.isKill()) {
805 // Attempt to break each anti-dependency...
806 for (const SDep *Edge : Edges) {
807 SUnit *NextSU = Edge->getSUnit();
808
809 if ((Edge->getKind() != SDep::Anti) &&
810 (Edge->getKind() != SDep::Output)) continue;
811
812 MCRegister AntiDepReg = Edge->getReg().asMCReg();
813 LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI));
814 assert(AntiDepReg && "Anti-dependence on reg0?");
815
816 if (!MRI.isAllocatable(AntiDepReg)) {
817 // Don't break anti-dependencies on non-allocatable registers.
818 LLVM_DEBUG(dbgs() << " (non-allocatable)\n");
819 continue;
820 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg.id())) {
821 // Don't break anti-dependencies for critical path registers
822 // if not on the critical path
823 LLVM_DEBUG(dbgs() << " (not critical-path)\n");
824 continue;
825 } else if (PassthruRegs.count(AntiDepReg) != 0) {
826 // If the anti-dep register liveness "passes-thru", then
827 // don't try to change it. It will be changed along with
828 // the use if required to break an earlier antidep.
829 LLVM_DEBUG(dbgs() << " (passthru)\n");
830 continue;
831 } else {
832 // No anti-dep breaking for implicit deps
833 MachineOperand *AntiDepOp =
834 MI.findRegisterDefOperand(AntiDepReg, /*TRI=*/nullptr);
835 assert(AntiDepOp && "Can't find index for defined register operand");
836 if (!AntiDepOp || AntiDepOp->isImplicit()) {
837 LLVM_DEBUG(dbgs() << " (implicit)\n");
838 continue;
839 }
840
841 // If the SUnit has other dependencies on the SUnit that
842 // it anti-depends on, don't bother breaking the
843 // anti-dependency since those edges would prevent such
844 // units from being scheduled past each other
845 // regardless.
846 //
847 // Also, if there are dependencies on other SUnits with the
848 // same register as the anti-dependency, don't attempt to
849 // break it.
850 for (const SDep &Pred : PathSU->Preds) {
851 if (Pred.getSUnit() == NextSU ? (Pred.getKind() != SDep::Anti ||
852 Pred.getReg() != AntiDepReg)
853 : (Pred.getKind() == SDep::Data &&
854 Pred.getReg() == AntiDepReg)) {
855 AntiDepReg = MCRegister();
856 break;
857 }
858 }
859 for (const SDep &Pred : PathSU->Preds) {
860 if ((Pred.getSUnit() == NextSU) && (Pred.getKind() != SDep::Anti) &&
861 (Pred.getKind() != SDep::Output)) {
862 LLVM_DEBUG(dbgs() << " (real dependency)\n");
863 AntiDepReg = MCRegister();
864 break;
865 } else if ((Pred.getSUnit() != NextSU) &&
866 (Pred.getKind() == SDep::Data) &&
867 (Pred.getReg() == AntiDepReg)) {
868 LLVM_DEBUG(dbgs() << " (other dependency)\n");
869 AntiDepReg = MCRegister();
870 break;
871 }
872 }
873
874 if (!AntiDepReg)
875 continue;
876 }
877
878 assert(AntiDepReg);
879
880 // Determine AntiDepReg's register group.
881 const unsigned GroupIndex = State->GetGroup(AntiDepReg);
882 if (GroupIndex == 0) {
883 LLVM_DEBUG(dbgs() << " (zero group)\n");
884 continue;
885 }
886
887 LLVM_DEBUG(dbgs() << '\n');
888
889 // Look for a suitable register to use to break the anti-dependence.
890 std::map<MCRegister, MCRegister> RenameMap;
891 if (FindSuitableFreeRegisters(AntiDepReg, GroupIndex, RenameOrder,
892 RenameMap)) {
893 LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
894 << printReg(AntiDepReg, TRI) << ":");
895
896 // Handle each group register...
897 for (const auto &P : RenameMap) {
898 MCRegister CurrReg = P.first;
899 MCRegister NewReg = P.second;
900
901 LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->"
902 << printReg(NewReg, TRI) << "("
903 << RegRefs.count(CurrReg) << " refs)");
904
905 // Update the references to the old register CurrReg to
906 // refer to the new register NewReg.
907 for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) {
908 Q.second.Operand->setReg(NewReg);
909 // If the SU for the instruction being updated has debug
910 // information related to the anti-dependency register, make
911 // sure to update that as well.
912 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
913 if (!SU) continue;
914 UpdateDbgValues(DbgValues, Q.second.Operand->getParent(),
915 AntiDepReg, NewReg);
916 }
917
918 // We just went back in time and modified history; the
919 // liveness information for CurrReg is now inconsistent. Set
920 // the state as if it were dead.
921 State->UnionGroups(NewReg, 0);
922 RegRefs.erase(NewReg);
923 DefIndices[NewReg.id()] = DefIndices[CurrReg.id()];
924 KillIndices[NewReg.id()] = KillIndices[CurrReg.id()];
925
926 State->UnionGroups(CurrReg, 0);
927 RegRefs.erase(CurrReg);
928 DefIndices[CurrReg.id()] = KillIndices[CurrReg.id()];
929 KillIndices[CurrReg.id()] = ~0u;
930 assert(((KillIndices[CurrReg.id()] == ~0u) !=
931 (DefIndices[CurrReg.id()] == ~0u)) &&
932 "Kill and Def maps aren't consistent for AntiDepReg!");
933 }
934
935 ++Broken;
936 LLVM_DEBUG(dbgs() << '\n');
937 }
938 }
939 }
940
941 ScanInstruction(MI, Count);
942 }
943
944 return Broken;
945}
946
948 MachineFunction &MFi, const RegisterClassInfo &RCI,
949 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) {
950 return new AggressiveAntiDepBreaker(MFi, RCI, CriticalPathRCs);
951}
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static void AntiDepEdges(const SUnit *SU, std::vector< const SDep * > &Edges)
AntiDepEdges - Return in Edges the anti- and output- dependencies in SU that we want to consider for ...
static const SUnit * CriticalPathStep(const SUnit *SU)
CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.
IRTranslator LLVM IR MI
A set of register units.
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
modulo schedule test
#define P(N)
This file defines the SmallSet class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override
Update liveness information to account for the current instruction, which will not be scheduled.
void FinishBlock() override
Finish anti-dep breaking for a basic block.
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 StartBlock(MachineBasicBlock *BB) override
Initialize anti-dep breaking for a new basic block.
AggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
Contains all the state necessary for anti-dep breaking.
AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB)
void GetGroupRegs(unsigned Group, std::vector< MCRegister > &Regs, std::multimap< MCRegister, AggressiveAntiDepState::RegisterReference > *RegRefs)
bool IsLive(MCRegister Reg)
Return true if Reg is live.
unsigned UnionGroups(MCRegister Reg1, MCRegister Reg2)
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
void UpdateDbgValues(const DbgValueVector &DbgValues, MachineInstr *ParentMI, MCRegister OldReg, MCRegister 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
size_t size() const
Get the array size.
Definition ArrayRef.h:141
bool empty() const
Check if the array is empty.
Definition ArrayRef.h:136
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Definition BitVector.h:483
iterator_range< const_set_bits_iterator > set_bits() const
Definition BitVector.h:160
bool empty() const
Returns whether there are no bits in this bitvector.
Definition BitVector.h:176
A set of register units used to track register liveness.
const BitVector & getBitVector() const
Return the internal bitvector representation of the set.
LLVM_ABI void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
Wrapper class representing physical registers. Should be passed by value.
Definition MCRegister.h:41
constexpr unsigned id() const
Definition MCRegister.h:82
MachineInstrBundleIterator< MachineInstr > iterator
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI) const
Return true if the MachineInstr reads the specified register.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
Wrapper class representing virtual and physical registers.
Definition Register.h:20
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition Register.h:107
constexpr unsigned id() const
Definition Register.h:100
Scheduling dependency.
Definition ScheduleDAG.h:54
@ Output
A register output-dependence (aka WAW).
Definition ScheduleDAG.h:60
@ Anti
A register anti-dependence (aka WAR).
Definition ScheduleDAG.h:59
@ Data
Regular data dependence (aka true-dependence).
Definition ScheduleDAG.h:58
Scheduling unit. This is a node in the scheduling DAG.
unsigned short Latency
Node latency.
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...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:134
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:184
SmallVectorImpl< const TargetRegisterClass * > RegClassVector
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
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:1755
LLVM_ABI AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
@ Other
Any other memory.
Definition ModRef.h:68
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition MCRegister.h:21
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
Definition InstrProf.h:147
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
LLVM_ABI 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.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
Definition FastISel.h:58