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