LLVM  6.0.0svn
ExecutionDepsFix.cpp
Go to the documentation of this file.
1 //===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 
20 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/Debug.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "execution-deps-fix"
27 
28 /// Translate TRI register number to a list of indices into our smaller tables
29 /// of interesting registers.
31 ExecutionDepsFix::regIndices(unsigned Reg) const {
32  assert(Reg < AliasMap.size() && "Invalid register");
33  const auto &Entry = AliasMap[Reg];
34  return make_range(Entry.begin(), Entry.end());
35 }
36 
37 DomainValue *ExecutionDepsFix::alloc(int domain) {
38  DomainValue *dv = Avail.empty() ?
39  new(Allocator.Allocate()) DomainValue :
40  Avail.pop_back_val();
41  if (domain >= 0)
42  dv->addDomain(domain);
43  assert(dv->Refs == 0 && "Reference count wasn't cleared");
44  assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
45  return dv;
46 }
47 
48 /// Release a reference to DV. When the last reference is released,
49 /// collapse if needed.
50 void ExecutionDepsFix::release(DomainValue *DV) {
51  while (DV) {
52  assert(DV->Refs && "Bad DomainValue");
53  if (--DV->Refs)
54  return;
55 
56  // There are no more DV references. Collapse any contained instructions.
57  if (DV->AvailableDomains && !DV->isCollapsed())
58  collapse(DV, DV->getFirstDomain());
59 
60  DomainValue *Next = DV->Next;
61  DV->clear();
62  Avail.push_back(DV);
63  // Also release the next DomainValue in the chain.
64  DV = Next;
65  }
66 }
67 
68 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
69 /// Update the referenced pointer when necessary.
70 DomainValue *ExecutionDepsFix::resolve(DomainValue *&DVRef) {
71  DomainValue *DV = DVRef;
72  if (!DV || !DV->Next)
73  return DV;
74 
75  // DV has a chain. Find the end.
76  do DV = DV->Next;
77  while (DV->Next);
78 
79  // Update DVRef to point to DV.
80  retain(DV);
81  release(DVRef);
82  DVRef = DV;
83  return DV;
84 }
85 
86 /// Set LiveRegs[rx] = dv, updating reference counts.
87 void ExecutionDepsFix::setLiveReg(int rx, DomainValue *dv) {
88  assert(unsigned(rx) < NumRegs && "Invalid index");
89  assert(LiveRegs && "Must enter basic block first.");
90 
91  if (LiveRegs[rx].Value == dv)
92  return;
93  if (LiveRegs[rx].Value)
94  release(LiveRegs[rx].Value);
95  LiveRegs[rx].Value = retain(dv);
96 }
97 
98 // Kill register rx, recycle or collapse any DomainValue.
99 void ExecutionDepsFix::kill(int rx) {
100  assert(unsigned(rx) < NumRegs && "Invalid index");
101  assert(LiveRegs && "Must enter basic block first.");
102  if (!LiveRegs[rx].Value)
103  return;
104 
105  release(LiveRegs[rx].Value);
106  LiveRegs[rx].Value = nullptr;
107 }
108 
109 /// Force register rx into domain.
110 void ExecutionDepsFix::force(int rx, unsigned domain) {
111  assert(unsigned(rx) < NumRegs && "Invalid index");
112  assert(LiveRegs && "Must enter basic block first.");
113  if (DomainValue *dv = LiveRegs[rx].Value) {
114  if (dv->isCollapsed())
115  dv->addDomain(domain);
116  else if (dv->hasDomain(domain))
117  collapse(dv, domain);
118  else {
119  // This is an incompatible open DomainValue. Collapse it to whatever and
120  // force the new value into domain. This costs a domain crossing.
121  collapse(dv, dv->getFirstDomain());
122  assert(LiveRegs[rx].Value && "Not live after collapse?");
123  LiveRegs[rx].Value->addDomain(domain);
124  }
125  } else {
126  // Set up basic collapsed DomainValue.
127  setLiveReg(rx, alloc(domain));
128  }
129 }
130 
131 /// Collapse open DomainValue into given domain. If there are multiple
132 /// registers using dv, they each get a unique collapsed DomainValue.
133 void ExecutionDepsFix::collapse(DomainValue *dv, unsigned domain) {
134  assert(dv->hasDomain(domain) && "Cannot collapse");
135 
136  // Collapse all the instructions.
137  while (!dv->Instrs.empty())
138  TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
139  dv->setSingleDomain(domain);
140 
141  // If there are multiple users, give them new, unique DomainValues.
142  if (LiveRegs && dv->Refs > 1)
143  for (unsigned rx = 0; rx != NumRegs; ++rx)
144  if (LiveRegs[rx].Value == dv)
145  setLiveReg(rx, alloc(domain));
146 }
147 
148 /// All instructions and registers in B are moved to A, and B is released.
149 bool ExecutionDepsFix::merge(DomainValue *A, DomainValue *B) {
150  assert(!A->isCollapsed() && "Cannot merge into collapsed");
151  assert(!B->isCollapsed() && "Cannot merge from collapsed");
152  if (A == B)
153  return true;
154  // Restrict to the domains that A and B have in common.
155  unsigned common = A->getCommonDomains(B->AvailableDomains);
156  if (!common)
157  return false;
158  A->AvailableDomains = common;
159  A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
160 
161  // Clear the old DomainValue so we won't try to swizzle instructions twice.
162  B->clear();
163  // All uses of B are referred to A.
164  B->Next = retain(A);
165 
166  for (unsigned rx = 0; rx != NumRegs; ++rx) {
167  assert(LiveRegs && "no space allocated for live registers");
168  if (LiveRegs[rx].Value == B)
169  setLiveReg(rx, A);
170  }
171  return true;
172 }
173 
174 /// Set up LiveRegs by merging predecessor live-out values.
175 void ExecutionDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
176  // Reset instruction counter in each basic block.
177  CurInstr = 0;
178 
179  // Set up UndefReads to track undefined register reads.
180  UndefReads.clear();
181  LiveRegSet.clear();
182 
183  // Set up LiveRegs to represent registers entering MBB.
184  if (!LiveRegs)
185  LiveRegs = new LiveReg[NumRegs];
186 
187  // Default values are 'nothing happened a long time ago'.
188  for (unsigned rx = 0; rx != NumRegs; ++rx) {
189  LiveRegs[rx].Value = nullptr;
190  LiveRegs[rx].Def = -(1 << 20);
191  }
192 
193  // This is the entry block.
194  if (MBB->pred_empty()) {
195  for (const auto &LI : MBB->liveins()) {
196  for (int rx : regIndices(LI.PhysReg)) {
197  // Treat function live-ins as if they were defined just before the first
198  // instruction. Usually, function arguments are set up immediately
199  // before the call.
200  LiveRegs[rx].Def = -1;
201  }
202  }
203  DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n");
204  return;
205  }
206 
207  // Try to coalesce live-out registers from predecessors.
209  pe = MBB->pred_end(); pi != pe; ++pi) {
210  auto fi = MBBInfos.find(*pi);
211  assert(fi != MBBInfos.end() &&
212  "Should have pre-allocated MBBInfos for all MBBs");
213  LiveReg *Incoming = fi->second.OutRegs;
214  // Incoming is null if this is a backedge from a BB
215  // we haven't processed yet
216  if (Incoming == nullptr) {
217  continue;
218  }
219 
220  for (unsigned rx = 0; rx != NumRegs; ++rx) {
221  // Use the most recent predecessor def for each register.
222  LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, Incoming[rx].Def);
223 
224  DomainValue *pdv = resolve(Incoming[rx].Value);
225  if (!pdv)
226  continue;
227  if (!LiveRegs[rx].Value) {
228  setLiveReg(rx, pdv);
229  continue;
230  }
231 
232  // We have a live DomainValue from more than one predecessor.
233  if (LiveRegs[rx].Value->isCollapsed()) {
234  // We are already collapsed, but predecessor is not. Force it.
235  unsigned Domain = LiveRegs[rx].Value->getFirstDomain();
236  if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
237  collapse(pdv, Domain);
238  continue;
239  }
240 
241  // Currently open, merge in predecessor.
242  if (!pdv->isCollapsed())
243  merge(LiveRegs[rx].Value, pdv);
244  else
245  force(rx, pdv->getFirstDomain());
246  }
247  }
248  DEBUG(
249  dbgs() << "BB#" << MBB->getNumber()
250  << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"));
251 }
252 
253 void ExecutionDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
254  assert(LiveRegs && "Must enter basic block first.");
255  LiveReg *OldOutRegs = MBBInfos[MBB].OutRegs;
256  // Save register clearances at end of MBB - used by enterBasicBlock().
257  MBBInfos[MBB].OutRegs = LiveRegs;
258 
259  // While processing the basic block, we kept `Def` relative to the start
260  // of the basic block for convenience. However, future use of this information
261  // only cares about the clearance from the end of the block, so adjust
262  // everything to be relative to the end of the basic block.
263  for (unsigned i = 0, e = NumRegs; i != e; ++i)
264  LiveRegs[i].Def -= CurInstr;
265  if (OldOutRegs) {
266  // This must be the second pass.
267  // Release all the DomainValues instead of keeping them.
268  for (unsigned i = 0, e = NumRegs; i != e; ++i)
269  release(OldOutRegs[i].Value);
270  delete[] OldOutRegs;
271  }
272  LiveRegs = nullptr;
273 }
274 
275 bool ExecutionDepsFix::visitInstr(MachineInstr *MI) {
276  // Update instructions with explicit execution domains.
277  std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
278  if (DomP.first) {
279  if (DomP.second)
280  visitSoftInstr(MI, DomP.second);
281  else
282  visitHardInstr(MI, DomP.first);
283  }
284 
285  return !DomP.first;
286 }
287 
288 /// \brief Helps avoid false dependencies on undef registers by updating the
289 /// machine instructions' undef operand to use a register that the instruction
290 /// is truly dependent on, or use a register with clearance higher than Pref.
291 /// Returns true if it was able to find a true dependency, thus not requiring
292 /// a dependency breaking instruction regardless of clearance.
293 bool ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
294  unsigned OpIdx, unsigned Pref) {
295  MachineOperand &MO = MI->getOperand(OpIdx);
296  assert(MO.isUndef() && "Expected undef machine operand");
297 
298  unsigned OriginalReg = MO.getReg();
299 
300  // Update only undef operands that are mapped to one register.
301  if (AliasMap[OriginalReg].size() != 1)
302  return false;
303 
304  // Get the undef operand's register class
305  const TargetRegisterClass *OpRC =
306  TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
307 
308  // If the instruction has a true dependency, we can hide the false depdency
309  // behind it.
310  for (MachineOperand &CurrMO : MI->operands()) {
311  if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
312  !OpRC->contains(CurrMO.getReg()))
313  continue;
314  // We found a true dependency - replace the undef register with the true
315  // dependency.
316  MO.setReg(CurrMO.getReg());
317  return true;
318  }
319 
320  // Go over all registers in the register class and find the register with
321  // max clearance or clearance higher than Pref.
322  unsigned MaxClearance = 0;
323  unsigned MaxClearanceReg = OriginalReg;
324  ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
325  for (auto Reg : Order) {
326  assert(AliasMap[Reg].size() == 1 &&
327  "Reg is expected to be mapped to a single index");
328  int RCrx = *regIndices(Reg).begin();
329  unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
330  if (Clearance <= MaxClearance)
331  continue;
332  MaxClearance = Clearance;
333  MaxClearanceReg = Reg;
334 
335  if (MaxClearance > Pref)
336  break;
337  }
338 
339  // Update the operand if we found a register with better clearance.
340  if (MaxClearanceReg != OriginalReg)
341  MO.setReg(MaxClearanceReg);
342 
343  return false;
344 }
345 
346 /// \brief Return true to if it makes sense to break dependence on a partial def
347 /// or undef use.
348 bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
349  unsigned Pref) {
350  unsigned reg = MI->getOperand(OpIdx).getReg();
351  for (int rx : regIndices(reg)) {
352  unsigned Clearance = CurInstr - LiveRegs[rx].Def;
353  DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
354 
355  if (Pref > Clearance) {
356  DEBUG(dbgs() << ": Break dependency.\n");
357  continue;
358  }
359  DEBUG(dbgs() << ": OK .\n");
360  return false;
361  }
362  return true;
363 }
364 
365 // Update def-ages for registers defined by MI.
366 // If Kill is set, also kill off DomainValues clobbered by the defs.
367 //
368 // Also break dependencies on partial defs and undef uses.
369 void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
370  bool Kill) {
371  assert(!MI->isDebugValue() && "Won't process debug values");
372 
373  // Break dependence on undef uses. Do this before updating LiveRegs below.
374  unsigned OpNum;
375  if (breakDependency) {
376  unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
377  if (Pref) {
378  bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
379  // We don't need to bother trying to break a dependency if this
380  // instruction has a true dependency on that register through another
381  // operand - we'll have to wait for it to be available regardless.
382  if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
383  UndefReads.push_back(std::make_pair(MI, OpNum));
384  }
385  }
386  const MCInstrDesc &MCID = MI->getDesc();
387  for (unsigned i = 0,
388  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
389  i != e; ++i) {
390  MachineOperand &MO = MI->getOperand(i);
391  if (!MO.isReg())
392  continue;
393  if (MO.isUse())
394  continue;
395  for (int rx : regIndices(MO.getReg())) {
396  // This instruction explicitly defines rx.
397  DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr
398  << '\t' << *MI);
399 
400  if (breakDependency) {
401  // Check clearance before partial register updates.
402  // Call breakDependence before setting LiveRegs[rx].Def.
403  unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
404  if (Pref && shouldBreakDependence(MI, i, Pref))
405  TII->breakPartialRegDependency(*MI, i, TRI);
406  }
407 
408  // How many instructions since rx was last written?
409  LiveRegs[rx].Def = CurInstr;
410 
411  // Kill off domains redefined by generic instructions.
412  if (Kill)
413  kill(rx);
414  }
415  }
416  ++CurInstr;
417 }
418 
419 /// \break Break false dependencies on undefined register reads.
420 ///
421 /// Walk the block backward computing precise liveness. This is expensive, so we
422 /// only do it on demand. Note that the occurrence of undefined register reads
423 /// that should be broken is very rare, but when they occur we may have many in
424 /// a single block.
425 void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
426  if (UndefReads.empty())
427  return;
428 
429  // Collect this block's live out register units.
430  LiveRegSet.init(*TRI);
431  // We do not need to care about pristine registers as they are just preserved
432  // but not actually used in the function.
433  LiveRegSet.addLiveOutsNoPristines(*MBB);
434 
435  MachineInstr *UndefMI = UndefReads.back().first;
436  unsigned OpIdx = UndefReads.back().second;
437 
438  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
439  // Update liveness, including the current instruction's defs.
440  LiveRegSet.stepBackward(I);
441 
442  if (UndefMI == &I) {
443  if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
444  TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
445 
446  UndefReads.pop_back();
447  if (UndefReads.empty())
448  return;
449 
450  UndefMI = UndefReads.back().first;
451  OpIdx = UndefReads.back().second;
452  }
453  }
454 }
455 
456 // A hard instruction only works in one domain. All input registers will be
457 // forced into that domain.
458 void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
459  // Collapse all uses.
460  for (unsigned i = mi->getDesc().getNumDefs(),
461  e = mi->getDesc().getNumOperands(); i != e; ++i) {
462  MachineOperand &mo = mi->getOperand(i);
463  if (!mo.isReg()) continue;
464  for (int rx : regIndices(mo.getReg())) {
465  force(rx, domain);
466  }
467  }
468 
469  // Kill all defs and force them.
470  for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
471  MachineOperand &mo = mi->getOperand(i);
472  if (!mo.isReg()) continue;
473  for (int rx : regIndices(mo.getReg())) {
474  kill(rx);
475  force(rx, domain);
476  }
477  }
478 }
479 
480 // A soft instruction can be changed to work in other domains given by mask.
481 void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
482  // Bitmask of available domains for this instruction after taking collapsed
483  // operands into account.
484  unsigned available = mask;
485 
486  // Scan the explicit use operands for incoming domains.
487  SmallVector<int, 4> used;
488  if (LiveRegs)
489  for (unsigned i = mi->getDesc().getNumDefs(),
490  e = mi->getDesc().getNumOperands(); i != e; ++i) {
491  MachineOperand &mo = mi->getOperand(i);
492  if (!mo.isReg()) continue;
493  for (int rx : regIndices(mo.getReg())) {
494  DomainValue *dv = LiveRegs[rx].Value;
495  if (dv == nullptr)
496  continue;
497  // Bitmask of domains that dv and available have in common.
498  unsigned common = dv->getCommonDomains(available);
499  // Is it possible to use this collapsed register for free?
500  if (dv->isCollapsed()) {
501  // Restrict available domains to the ones in common with the operand.
502  // If there are no common domains, we must pay the cross-domain
503  // penalty for this operand.
504  if (common) available = common;
505  } else if (common)
506  // Open DomainValue is compatible, save it for merging.
507  used.push_back(rx);
508  else
509  // Open DomainValue is not compatible with instruction. It is useless
510  // now.
511  kill(rx);
512  }
513  }
514 
515  // If the collapsed operands force a single domain, propagate the collapse.
516  if (isPowerOf2_32(available)) {
517  unsigned domain = countTrailingZeros(available);
518  TII->setExecutionDomain(*mi, domain);
519  visitHardInstr(mi, domain);
520  return;
521  }
522 
523  // Kill off any remaining uses that don't match available, and build a list of
524  // incoming DomainValues that we want to merge.
526  for (int rx : used) {
527  assert(LiveRegs && "no space allocated for live registers");
528  const LiveReg &LR = LiveRegs[rx];
529  // This useless DomainValue could have been missed above.
530  if (!LR.Value->getCommonDomains(available)) {
531  kill(rx);
532  continue;
533  }
534  // Sorted insertion.
535  auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
536  [](const LiveReg *LHS, const LiveReg *RHS) {
537  return LHS->Def < RHS->Def;
538  });
539  Regs.insert(I, &LR);
540  }
541 
542  // doms are now sorted in order of appearance. Try to merge them all, giving
543  // priority to the latest ones.
544  DomainValue *dv = nullptr;
545  while (!Regs.empty()) {
546  if (!dv) {
547  dv = Regs.pop_back_val()->Value;
548  // Force the first dv to match the current instruction.
549  dv->AvailableDomains = dv->getCommonDomains(available);
550  assert(dv->AvailableDomains && "Domain should have been filtered");
551  continue;
552  }
553 
554  DomainValue *Latest = Regs.pop_back_val()->Value;
555  // Skip already merged values.
556  if (Latest == dv || Latest->Next)
557  continue;
558  if (merge(dv, Latest))
559  continue;
560 
561  // If latest didn't merge, it is useless now. Kill all registers using it.
562  for (int i : used) {
563  assert(LiveRegs && "no space allocated for live registers");
564  if (LiveRegs[i].Value == Latest)
565  kill(i);
566  }
567  }
568 
569  // dv is the DomainValue we are going to use for this instruction.
570  if (!dv) {
571  dv = alloc();
572  dv->AvailableDomains = available;
573  }
574  dv->Instrs.push_back(mi);
575 
576  // Finally set all defs and non-collapsed uses to dv. We must iterate through
577  // all the operators, including imp-def ones.
579  ee = mi->operands_end();
580  ii != ee; ++ii) {
581  MachineOperand &mo = *ii;
582  if (!mo.isReg()) continue;
583  for (int rx : regIndices(mo.getReg())) {
584  if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
585  kill(rx);
586  setLiveReg(rx, dv);
587  }
588  }
589  }
590 }
591 
592 void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
593  bool PrimaryPass) {
594  enterBasicBlock(MBB);
595  // If this block is not done, it makes little sense to make any decisions
596  // based on clearance information. We need to make a second pass anyway,
597  // and by then we'll have better information, so we can avoid doing the work
598  // to try and break dependencies now.
599  bool breakDependency = isBlockDone(MBB);
600  for (MachineInstr &MI : *MBB) {
601  if (!MI.isDebugValue()) {
602  bool Kill = false;
603  if (PrimaryPass)
604  Kill = visitInstr(&MI);
605  processDefs(&MI, breakDependency, Kill);
606  }
607  }
608  if (breakDependency)
609  processUndefReads(MBB);
610  leaveBasicBlock(MBB);
611 }
612 
613 bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
614  return MBBInfos[MBB].PrimaryCompleted &&
615  MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
616  MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
617 }
618 
620  if (skipFunction(*mf.getFunction()))
621  return false;
622  MF = &mf;
623  TII = MF->getSubtarget().getInstrInfo();
624  TRI = MF->getSubtarget().getRegisterInfo();
625  RegClassInfo.runOnMachineFunction(mf);
626  LiveRegs = nullptr;
627  assert(NumRegs == RC->getNumRegs() && "Bad regclass");
628 
629  DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
630  << TRI->getRegClassName(RC) << " **********\n");
631 
632  // If no relevant registers are used in the function, we can skip it
633  // completely.
634  bool anyregs = false;
635  const MachineRegisterInfo &MRI = mf.getRegInfo();
636  for (unsigned Reg : *RC) {
637  if (MRI.isPhysRegUsed(Reg)) {
638  anyregs = true;
639  break;
640  }
641  }
642  if (!anyregs) return false;
643 
644  // Initialize the AliasMap on the first use.
645  if (AliasMap.empty()) {
646  // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
647  // therefore the LiveRegs array.
648  AliasMap.resize(TRI->getNumRegs());
649  for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
650  for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
651  AI.isValid(); ++AI)
652  AliasMap[*AI].push_back(i);
653  }
654 
655  // Initialize the MMBInfos
656  for (auto &MBB : mf) {
657  MBBInfo InitialInfo;
658  MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
659  }
660 
661  /*
662  * We want to visit every instruction in every basic block in order to update
663  * it's execution domain or break any false dependencies. However, for the
664  * dependency breaking, we need to know clearances from all predecessors
665  * (including any backedges). One way to do so would be to do two complete
666  * passes over all basic blocks/instructions, the first for recording
667  * clearances, the second to break the dependencies. However, for functions
668  * without backedges, or functions with a lot of straight-line code, and
669  * a small loop, that would be a lot of unnecessary work (since only the
670  * BBs that are part of the loop require two passes). As an example,
671  * consider the following loop.
672  *
673  *
674  * PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
675  * ^ |
676  * +----------------------------------+
677  *
678  * The iteration order is as follows:
679  * Naive: PH A B C D A' B' C' D'
680  * Optimized: PH A B C A' B' C' D
681  *
682  * Note that we avoid processing D twice, because we can entirely process
683  * the predecessors before getting to D. We call a block that is ready
684  * for its second round of processing `done` (isBlockDone). Once we finish
685  * processing some block, we update the counters in MBBInfos and re-process
686  * any successors that are now done.
687  */
688 
689  MachineBasicBlock *Entry = &*MF->begin();
693  MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
694  MachineBasicBlock *MBB = *MBBI;
695  // N.B: IncomingProcessed and IncomingCompleted were already updated while
696  // processing this block's predecessors.
697  MBBInfos[MBB].PrimaryCompleted = true;
698  MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
699  bool Primary = true;
700  Workqueue.push_back(MBB);
701  while (!Workqueue.empty()) {
702  MachineBasicBlock *ActiveMBB = &*Workqueue.back();
703  Workqueue.pop_back();
704  processBasicBlock(ActiveMBB, Primary);
705  bool Done = isBlockDone(ActiveMBB);
706  for (auto *Succ : ActiveMBB->successors()) {
707  if (!isBlockDone(Succ)) {
708  if (Primary) {
709  MBBInfos[Succ].IncomingProcessed++;
710  }
711  if (Done) {
712  MBBInfos[Succ].IncomingCompleted++;
713  }
714  if (isBlockDone(Succ)) {
715  Workqueue.push_back(Succ);
716  }
717  }
718  }
719  Primary = false;
720  }
721  }
722 
723  // We need to go through again and finalize any blocks that are not done yet.
724  // This is possible if blocks have dead predecessors, so we didn't visit them
725  // above.
727  MBBI = RPOT.begin(),
728  MBBE = RPOT.end();
729  MBBI != MBBE; ++MBBI) {
730  MachineBasicBlock *MBB = *MBBI;
731  if (!isBlockDone(MBB)) {
732  processBasicBlock(MBB, false);
733  // Don't update successors here. We'll get to them anyway through this
734  // loop.
735  }
736  }
737 
738  // Clear the LiveOuts vectors and collapse any remaining DomainValues.
740  MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
741  auto FI = MBBInfos.find(*MBBI);
742  if (FI == MBBInfos.end() || !FI->second.OutRegs)
743  continue;
744  for (unsigned i = 0, e = NumRegs; i != e; ++i)
745  if (FI->second.OutRegs[i].Value)
746  release(FI->second.OutRegs[i].Value);
747  delete[] FI->second.OutRegs;
748  }
749  MBBInfos.clear();
750  UndefReads.clear();
751  Avail.clear();
752  Allocator.DestroyAll();
753 
754  return false;
755 }
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
void push_back(const T &Elt)
Definition: SmallVector.h:212
mop_iterator operands_end()
Definition: MachineInstr.h:327
unsigned getCommonDomains(unsigned mask) const
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
void addDomain(unsigned domain)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getNumRegs() const
Return the number of registers in this class.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual void setExecutionDomain(MachineInstr &MI, unsigned Domain) const
Change the opcode of MI to execute in Domain.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getRegister(unsigned i) const
Return the specified register in the class.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getFirstDomain() const
unsigned getReg() const
getReg - Returns the register number.
std::vector< MachineBasicBlock * >::const_iterator const_pred_iterator
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
iterator_range< succ_iterator > successors()
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
virtual unsigned getPartialRegUpdateClearance(const MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Returns the preferred minimum clearance before an instruction with an unwanted partial register updat...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
Reg
All possible values of the reg field in the ModR/M byte.
DomainValue * Value
Value currently in this register, or NULL when no value is being tracked.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:287
const RegList & Regs
const TargetRegisterClass * getRegClass(const MCInstrDesc &TID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
LaneBitmask contains(unsigned Reg) const
DomainValue * Next
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
reverse_iterator rend()
reverse_iterator rbegin()
const char * getName(unsigned RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
void init(const MachineRegisterInfo &MRI)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
bool hasDomain(unsigned domain) const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
int Def
Instruction that defined this register, relative to the beginning of the current basic block...
unsigned const MachineRegisterInfo * MRI
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:112
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:421
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
MCRegAliasIterator enumerates all registers aliasing Reg.
SmallVector< MachineInstr *, 8 > Instrs
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
A set of live virtual registers and physical register units.
Information about a live register.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
void setSingleDomain(unsigned domain)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
bool isVariadic(QueryType Type=IgnoreBundle) const
Return true if this instruction can have a variable number of operands.
Definition: MachineInstr.h:438
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isPhysRegUsed(unsigned PhysReg) const
Return true if the specified register is modified or read in this function.
A range adaptor for a pair of iterators.
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
A DomainValue is a bit like LiveIntervals&#39; ValNo, but it also keeps track of execution domains...
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:59
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
virtual void breakPartialRegDependency(MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Insert a dependency-breaking instruction before MI to eliminate an unwanted dependency on OpNum...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:79
typename std::vector< NodeRef >::reverse_iterator rpo_iterator
virtual std::pair< uint16_t, uint16_t > getExecutionDomain(const MachineInstr &MI) const
Return the current execution domain and bit mask of possible domains for instruction.
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
mop_iterator operands_begin()
Definition: MachineInstr.h:326
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:157
bool isCollapsed() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned &OpNum, const TargetRegisterInfo *TRI) const
Return the minimum clearance before an instruction that reads an unused register. ...