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
16#include "AggressiveAntiDepBreaker.h"
17#include "CodeGenOptions.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/CodeGen/LiveRegUnits.h"
22#include "llvm/CodeGen/MachineBasicBlock.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineOperand.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/RegisterClassInfo.h"
28#include "llvm/CodeGen/ScheduleDAG.h"
29#include "llvm/CodeGen/TargetInstrInfo.h"
30#include "llvm/CodeGen/TargetRegisterInfo.h"
31#include "llvm/CodeGenTypes/MachineValueType.h"
32#include "llvm/MC/MCInstrDesc.h"
33#include "llvm/MC/MCRegisterInfo.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36#include <cassert>
37
38using namespace llvm;
39
40#define DEBUG_TYPE "post-RA-sched"
41
42AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
43 MachineBasicBlock *BB)
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
58unsigned AggressiveAntiDepState::GetGroup(MCRegister Reg) {
59 unsigned Node = GroupNodeIndices[Reg.id()];
60 while (GroupNodes[Node] != Node)
61 Node = GroupNodes[Node];
62
63 return Node;
64}
65
66void AggressiveAntiDepState::GetGroupRegs(
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(x: Reg) > 0))
72 Regs.push_back(x: Reg);
73 }
74}
75
76unsigned AggressiveAntiDepState::UnionGroups(MCRegister Reg1, MCRegister Reg2) {
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(Reg: Reg1);
82 unsigned Group2 = GetGroup(Reg: 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(n: Other) = Parent;
88 return Parent;
89}
90
91unsigned AggressiveAntiDepState::LeaveGroup(MCRegister Reg) {
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(x: idx);
97 GroupNodeIndices[Reg.id()] = idx;
98 return idx;
99}
100
101bool AggressiveAntiDepState::IsLive(MCRegister Reg) {
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
107AggressiveAntiDepBreaker::AggressiveAntiDepBreaker(
108 MachineFunction &MFi, const RegisterClassInfo &RCI,
109 TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
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
129AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
130 delete State;
131}
132
133void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
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(MBB: *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(Range: TRI->regunits(Reg), P: [&](MCRegUnit Unit) {
154 return LiveOutUnits.test(Idx: static_cast<unsigned>(Unit));
155 }))
156 continue;
157 State->UnionGroups(Reg1: Reg, Reg2: 0);
158 KillIndices[Reg.id()] = BB->size();
159 DefIndices[Reg.id()] = ~0u;
160 }
161}
162
163void AggressiveAntiDepBreaker::FinishBlock() {
164 delete State;
165 State = nullptr;
166}
167
168void AggressiveAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,
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(Reg1: Reg, Reg2: 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, isKill: 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(DefOpIdx: i)) ||
226 IsImplicitDefUse(MI, MO)) {
227 const Register Reg = MO.getReg();
228 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
229 PassthruRegs.insert(x: 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) {
237 SmallSet<Register, 4> RegSet;
238 for (const SDep &Pred : SU->Preds) {
239 if ((Pred.getKind() == SDep::Anti) || (Pred.getKind() == SDep::Output)) {
240 if (RegSet.insert(V: Pred.getReg()).second)
241 Edges.push_back(x: &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(RegA: Reg, RegB: *AI) && State->IsLive(Reg: *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(x: 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(Reg: SubregReg)) {
305 KillIndices[SubregReg] = KillIdx;
306 DefIndices[SubregReg] = ~0u;
307 RegRefs.erase(x: SubregReg);
308 State->LeaveGroup(Reg: 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: Reg.asMCReg(), KillIdx: Count + 1, tag: "", header: "\tDead Def: ", footer: "\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(Reg1: Reg, Reg2: 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(Reg: AliasReg)) {
369 State->UnionGroups(Reg1: Reg, Reg2: 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(MCID: MI.getDesc(), OpNum: i);
379 AggressiveAntiDepState::RegisterReference RR = { .Operand: &MO, .RC: RC };
380 RegRefs.emplace(args: Reg.asMCReg(), args&: 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(x: 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(RegA: Reg, RegB: *AI) && State->IsLive(Reg: *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: Reg.asMCReg(), KillIdx: Count, tag: "(last-use)");
453
454 if (Special) {
455 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)");
456 State->UnionGroups(Reg1: Reg, Reg2: 0);
457 }
458
459 // Note register reference...
460 const TargetRegisterClass *RC = nullptr;
461 if (i < MI.getDesc().getNumOperands())
462 RC = TII->getRegClass(MCID: MI.getDesc(), OpNum: i);
463 AggressiveAntiDepState::RegisterReference RR = { .Operand: &MO, .RC: RC };
464 RegRefs.emplace(args: Reg.asMCReg(), args&: 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(Reg1: FirstReg, Reg2: 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(p: State->GetRegRefs().equal_range(x: 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(Group: AntiDepGroupIndex, Regs, RegRefs: &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(x: 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(RegA: SuperReg, RegB: 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(Reg: SuperReg);
593
594 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC: 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(x: 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(PhysReg: 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(RegNo: SuperReg, SubRegNo: Reg);
628 if (NewSubRegIdx != 0)
629 NewReg = TRI->getSubReg(Reg: NewSuperReg, Idx: 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(Idx: 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(Reg: 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(Reg: AliasReg) ||
653 (KillIndices[Reg.id()] > DefIndices[AliasReg.id()])) {
654 LLVM_DEBUG(dbgs()
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(p: RegRefs.equal_range(x: Reg))) {
667 MachineInstr *UseMI = Q.second.Operand->getParent();
668 int Idx = UseMI->findRegisterDefOperandIdx(Reg: NewReg, TRI, isDead: false, Overlap: true);
669 if (Idx == -1)
670 continue;
671
672 if (UseMI->getOperand(i: 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(p: RegRefs.equal_range(x: 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(Reg: 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(x: std::make_pair(x&: Reg, y&: 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(x: SuperRC);
699 RenameOrder.insert(x: 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.
715unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
716 const std::vector<SUnit> &SUnits,
717 MachineBasicBlock::iterator Begin,
718 MachineBasicBlock::iterator End,
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(x: std::make_pair(x: SU.getInstr(), y: &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(SU: 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(SU: 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(PhysReg: 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(Idx: 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(x: 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(Reg: 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(Reg: 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(SuperReg: AntiDepReg, AntiDepGroupIndex: 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(p: RegRefs.equal_range(x: 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, ParentMI: Q.second.Operand->getParent(),
915 OldReg: 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(Reg1: NewReg, Reg2: 0);
922 RegRefs.erase(x: NewReg);
923 DefIndices[NewReg.id()] = DefIndices[CurrReg.id()];
924 KillIndices[NewReg.id()] = KillIndices[CurrReg.id()];
925
926 State->UnionGroups(Reg1: CurrReg, Reg2: 0);
927 RegRefs.erase(x: 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
947AntiDepBreaker *llvm::createAggressiveAntiDepBreaker(
948 MachineFunction &MFi, const RegisterClassInfo &RCI,
949 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) {
950 return new AggressiveAntiDepBreaker(MFi, RCI, CriticalPathRCs);
951}
952