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