LLVM  9.0.0svn
ExecutionDomainFix.cpp
Go to the documentation of this file.
1 //===- ExecutionDomainFix.cpp - Fix execution domain issues ----*- C++ -*--===//
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 
12 
13 using namespace llvm;
14 
15 #define DEBUG_TYPE "execution-deps-fix"
16 
18 ExecutionDomainFix::regIndices(unsigned Reg) const {
19  assert(Reg < AliasMap.size() && "Invalid register");
20  const auto &Entry = AliasMap[Reg];
21  return make_range(Entry.begin(), Entry.end());
22 }
23 
24 DomainValue *ExecutionDomainFix::alloc(int domain) {
25  DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
26  : Avail.pop_back_val();
27  if (domain >= 0)
28  dv->addDomain(domain);
29  assert(dv->Refs == 0 && "Reference count wasn't cleared");
30  assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
31  return dv;
32 }
33 
34 void ExecutionDomainFix::release(DomainValue *DV) {
35  while (DV) {
36  assert(DV->Refs && "Bad DomainValue");
37  if (--DV->Refs)
38  return;
39 
40  // There are no more DV references. Collapse any contained instructions.
41  if (DV->AvailableDomains && !DV->isCollapsed())
42  collapse(DV, DV->getFirstDomain());
43 
44  DomainValue *Next = DV->Next;
45  DV->clear();
46  Avail.push_back(DV);
47  // Also release the next DomainValue in the chain.
48  DV = Next;
49  }
50 }
51 
52 DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
53  DomainValue *DV = DVRef;
54  if (!DV || !DV->Next)
55  return DV;
56 
57  // DV has a chain. Find the end.
58  do
59  DV = DV->Next;
60  while (DV->Next);
61 
62  // Update DVRef to point to DV.
63  retain(DV);
64  release(DVRef);
65  DVRef = DV;
66  return DV;
67 }
68 
69 void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
70  assert(unsigned(rx) < NumRegs && "Invalid index");
71  assert(!LiveRegs.empty() && "Must enter basic block first.");
72 
73  if (LiveRegs[rx] == dv)
74  return;
75  if (LiveRegs[rx])
76  release(LiveRegs[rx]);
77  LiveRegs[rx] = retain(dv);
78 }
79 
80 void ExecutionDomainFix::kill(int rx) {
81  assert(unsigned(rx) < NumRegs && "Invalid index");
82  assert(!LiveRegs.empty() && "Must enter basic block first.");
83  if (!LiveRegs[rx])
84  return;
85 
86  release(LiveRegs[rx]);
87  LiveRegs[rx] = nullptr;
88 }
89 
90 void ExecutionDomainFix::force(int rx, unsigned domain) {
91  assert(unsigned(rx) < NumRegs && "Invalid index");
92  assert(!LiveRegs.empty() && "Must enter basic block first.");
93  if (DomainValue *dv = LiveRegs[rx]) {
94  if (dv->isCollapsed())
95  dv->addDomain(domain);
96  else if (dv->hasDomain(domain))
97  collapse(dv, domain);
98  else {
99  // This is an incompatible open DomainValue. Collapse it to whatever and
100  // force the new value into domain. This costs a domain crossing.
101  collapse(dv, dv->getFirstDomain());
102  assert(LiveRegs[rx] && "Not live after collapse?");
103  LiveRegs[rx]->addDomain(domain);
104  }
105  } else {
106  // Set up basic collapsed DomainValue.
107  setLiveReg(rx, alloc(domain));
108  }
109 }
110 
111 void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
112  assert(dv->hasDomain(domain) && "Cannot collapse");
113 
114  // Collapse all the instructions.
115  while (!dv->Instrs.empty())
116  TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
117  dv->setSingleDomain(domain);
118 
119  // If there are multiple users, give them new, unique DomainValues.
120  if (!LiveRegs.empty() && dv->Refs > 1)
121  for (unsigned rx = 0; rx != NumRegs; ++rx)
122  if (LiveRegs[rx] == dv)
123  setLiveReg(rx, alloc(domain));
124 }
125 
126 bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
127  assert(!A->isCollapsed() && "Cannot merge into collapsed");
128  assert(!B->isCollapsed() && "Cannot merge from collapsed");
129  if (A == B)
130  return true;
131  // Restrict to the domains that A and B have in common.
132  unsigned common = A->getCommonDomains(B->AvailableDomains);
133  if (!common)
134  return false;
135  A->AvailableDomains = common;
136  A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
137 
138  // Clear the old DomainValue so we won't try to swizzle instructions twice.
139  B->clear();
140  // All uses of B are referred to A.
141  B->Next = retain(A);
142 
143  for (unsigned rx = 0; rx != NumRegs; ++rx) {
144  assert(!LiveRegs.empty() && "no space allocated for live registers");
145  if (LiveRegs[rx] == B)
146  setLiveReg(rx, A);
147  }
148  return true;
149 }
150 
151 void ExecutionDomainFix::enterBasicBlock(
152  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
153 
154  MachineBasicBlock *MBB = TraversedMBB.MBB;
155 
156  // Set up LiveRegs to represent registers entering MBB.
157  // Set default domain values to 'no domain' (nullptr)
158  if (LiveRegs.empty())
159  LiveRegs.assign(NumRegs, nullptr);
160 
161  // This is the entry block.
162  if (MBB->pred_empty()) {
163  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
164  return;
165  }
166 
167  // Try to coalesce live-out registers from predecessors.
168  for (MachineBasicBlock *pred : MBB->predecessors()) {
169  assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
170  "Should have pre-allocated MBBInfos for all MBBs");
171  LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
172  // Incoming is null if this is a backedge from a BB
173  // we haven't processed yet
174  if (Incoming.empty())
175  continue;
176 
177  for (unsigned rx = 0; rx != NumRegs; ++rx) {
178  DomainValue *pdv = resolve(Incoming[rx]);
179  if (!pdv)
180  continue;
181  if (!LiveRegs[rx]) {
182  setLiveReg(rx, pdv);
183  continue;
184  }
185 
186  // We have a live DomainValue from more than one predecessor.
187  if (LiveRegs[rx]->isCollapsed()) {
188  // We are already collapsed, but predecessor is not. Force it.
189  unsigned Domain = LiveRegs[rx]->getFirstDomain();
190  if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
191  collapse(pdv, Domain);
192  continue;
193  }
194 
195  // Currently open, merge in predecessor.
196  if (!pdv->isCollapsed())
197  merge(LiveRegs[rx], pdv);
198  else
199  force(rx, pdv->getFirstDomain());
200  }
201  }
203  << (!TraversedMBB.IsDone ? ": incomplete\n"
204  : ": all preds known\n"));
205 }
206 
207 void ExecutionDomainFix::leaveBasicBlock(
208  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
209  assert(!LiveRegs.empty() && "Must enter basic block first.");
210  unsigned MBBNumber = TraversedMBB.MBB->getNumber();
211  assert(MBBNumber < MBBOutRegsInfos.size() &&
212  "Unexpected basic block number.");
213  // Save register clearances at end of MBB - used by enterBasicBlock().
214  for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
215  release(OldLiveReg);
216  }
217  MBBOutRegsInfos[MBBNumber] = LiveRegs;
218  LiveRegs.clear();
219 }
220 
221 bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
222  // Update instructions with explicit execution domains.
223  std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
224  if (DomP.first) {
225  if (DomP.second)
226  visitSoftInstr(MI, DomP.second);
227  else
228  visitHardInstr(MI, DomP.first);
229  }
230 
231  return !DomP.first;
232 }
233 
234 void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
235  assert(!MI->isDebugInstr() && "Won't process debug values");
236  const MCInstrDesc &MCID = MI->getDesc();
237  for (unsigned i = 0,
238  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
239  i != e; ++i) {
240  MachineOperand &MO = MI->getOperand(i);
241  if (!MO.isReg())
242  continue;
243  if (MO.isUse())
244  continue;
245  for (int rx : regIndices(MO.getReg())) {
246  // This instruction explicitly defines rx.
247  LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
248 
249  // Kill off domains redefined by generic instructions.
250  if (Kill)
251  kill(rx);
252  }
253  }
254 }
255 
256 void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
257  // Collapse all uses.
258  for (unsigned i = mi->getDesc().getNumDefs(),
259  e = mi->getDesc().getNumOperands();
260  i != e; ++i) {
261  MachineOperand &mo = mi->getOperand(i);
262  if (!mo.isReg())
263  continue;
264  for (int rx : regIndices(mo.getReg())) {
265  force(rx, domain);
266  }
267  }
268 
269  // Kill all defs and force them.
270  for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
271  MachineOperand &mo = mi->getOperand(i);
272  if (!mo.isReg())
273  continue;
274  for (int rx : regIndices(mo.getReg())) {
275  kill(rx);
276  force(rx, domain);
277  }
278  }
279 }
280 
281 void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
282  // Bitmask of available domains for this instruction after taking collapsed
283  // operands into account.
284  unsigned available = mask;
285 
286  // Scan the explicit use operands for incoming domains.
287  SmallVector<int, 4> used;
288  if (!LiveRegs.empty())
289  for (unsigned i = mi->getDesc().getNumDefs(),
290  e = mi->getDesc().getNumOperands();
291  i != e; ++i) {
292  MachineOperand &mo = mi->getOperand(i);
293  if (!mo.isReg())
294  continue;
295  for (int rx : regIndices(mo.getReg())) {
296  DomainValue *dv = LiveRegs[rx];
297  if (dv == nullptr)
298  continue;
299  // Bitmask of domains that dv and available have in common.
300  unsigned common = dv->getCommonDomains(available);
301  // Is it possible to use this collapsed register for free?
302  if (dv->isCollapsed()) {
303  // Restrict available domains to the ones in common with the operand.
304  // If there are no common domains, we must pay the cross-domain
305  // penalty for this operand.
306  if (common)
307  available = common;
308  } else if (common)
309  // Open DomainValue is compatible, save it for merging.
310  used.push_back(rx);
311  else
312  // Open DomainValue is not compatible with instruction. It is useless
313  // now.
314  kill(rx);
315  }
316  }
317 
318  // If the collapsed operands force a single domain, propagate the collapse.
319  if (isPowerOf2_32(available)) {
320  unsigned domain = countTrailingZeros(available);
321  TII->setExecutionDomain(*mi, domain);
322  visitHardInstr(mi, domain);
323  return;
324  }
325 
326  // Kill off any remaining uses that don't match available, and build a list of
327  // incoming DomainValues that we want to merge.
328  SmallVector<int, 4> Regs;
329  for (int rx : used) {
330  assert(!LiveRegs.empty() && "no space allocated for live registers");
331  DomainValue *&LR = LiveRegs[rx];
332  // This useless DomainValue could have been missed above.
333  if (!LR->getCommonDomains(available)) {
334  kill(rx);
335  continue;
336  }
337  // Sorted insertion.
338  // Enables giving priority to the latest domains during merging.
339  auto I = std::upper_bound(
340  Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
341  return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
342  RDA->getReachingDef(mi, RC->getRegister(RHS));
343  });
344  Regs.insert(I, rx);
345  }
346 
347  // doms are now sorted in order of appearance. Try to merge them all, giving
348  // priority to the latest ones.
349  DomainValue *dv = nullptr;
350  while (!Regs.empty()) {
351  if (!dv) {
352  dv = LiveRegs[Regs.pop_back_val()];
353  // Force the first dv to match the current instruction.
354  dv->AvailableDomains = dv->getCommonDomains(available);
355  assert(dv->AvailableDomains && "Domain should have been filtered");
356  continue;
357  }
358 
359  DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
360  // Skip already merged values.
361  if (Latest == dv || Latest->Next)
362  continue;
363  if (merge(dv, Latest))
364  continue;
365 
366  // If latest didn't merge, it is useless now. Kill all registers using it.
367  for (int i : used) {
368  assert(!LiveRegs.empty() && "no space allocated for live registers");
369  if (LiveRegs[i] == Latest)
370  kill(i);
371  }
372  }
373 
374  // dv is the DomainValue we are going to use for this instruction.
375  if (!dv) {
376  dv = alloc();
378  }
379  dv->Instrs.push_back(mi);
380 
381  // Finally set all defs and non-collapsed uses to dv. We must iterate through
382  // all the operators, including imp-def ones.
383  for (MachineOperand &mo : mi->operands()) {
384  if (!mo.isReg())
385  continue;
386  for (int rx : regIndices(mo.getReg())) {
387  if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
388  kill(rx);
389  setLiveReg(rx, dv);
390  }
391  }
392  }
393 }
394 
395 void ExecutionDomainFix::processBasicBlock(
396  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
397  enterBasicBlock(TraversedMBB);
398  // If this block is not done, it makes little sense to make any decisions
399  // based on clearance information. We need to make a second pass anyway,
400  // and by then we'll have better information, so we can avoid doing the work
401  // to try and break dependencies now.
402  for (MachineInstr &MI : *TraversedMBB.MBB) {
403  if (!MI.isDebugInstr()) {
404  bool Kill = false;
405  if (TraversedMBB.PrimaryPass)
406  Kill = visitInstr(&MI);
407  processDefs(&MI, Kill);
408  }
409  }
410  leaveBasicBlock(TraversedMBB);
411 }
412 
414  if (skipFunction(mf.getFunction()))
415  return false;
416  MF = &mf;
417  TII = MF->getSubtarget().getInstrInfo();
418  TRI = MF->getSubtarget().getRegisterInfo();
419  LiveRegs.clear();
420  assert(NumRegs == RC->getNumRegs() && "Bad regclass");
421 
422  LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
423  << TRI->getRegClassName(RC) << " **********\n");
424 
425  // If no relevant registers are used in the function, we can skip it
426  // completely.
427  bool anyregs = false;
428  const MachineRegisterInfo &MRI = mf.getRegInfo();
429  for (unsigned Reg : *RC) {
430  if (MRI.isPhysRegUsed(Reg)) {
431  anyregs = true;
432  break;
433  }
434  }
435  if (!anyregs)
436  return false;
437 
438  RDA = &getAnalysis<ReachingDefAnalysis>();
439 
440  // Initialize the AliasMap on the first use.
441  if (AliasMap.empty()) {
442  // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
443  // therefore the LiveRegs array.
444  AliasMap.resize(TRI->getNumRegs());
445  for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
446  for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
447  ++AI)
448  AliasMap[*AI].push_back(i);
449  }
450 
451  // Initialize the MBBOutRegsInfos
452  MBBOutRegsInfos.resize(mf.getNumBlockIDs());
453 
454  // Traverse the basic blocks.
455  LoopTraversal Traversal;
456  LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
457  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
458  processBasicBlock(TraversedMBB);
459  }
460 
461  for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
462  for (DomainValue *OutLiveReg : OutLiveRegs) {
463  if (OutLiveReg)
464  release(OutLiveReg);
465  }
466  }
467  MBBOutRegsInfos.clear();
468  Avail.clear();
469  Allocator.DestroyAll();
470 
471  return false;
472 }
unsigned getCommonDomains(unsigned mask) const
Return bitmask of domains that are available and in mask.
void addDomain(unsigned domain)
Mark domain as available.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getNumRegs() const
Return the number of registers in this class.
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.
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
unsigned getRegister(unsigned i) const
Return the specified register in the class.
void push_back(const T &Elt)
Definition: SmallVector.h:211
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getFirstDomain() const
First domain available.
unsigned getReg() const
getReg - Returns the register number.
unsigned Reg
unsigned AvailableDomains
Bitmask of available domains.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:458
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
void clear()
Clear this DomainValue and point to next which has all its data.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:405
DomainValue * Next
Pointer to the next DomainValue in a chain.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
return !LiveInRegUnits available(Reg)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
bool hasDomain(unsigned domain) const
Is domain available?
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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:119
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MCRegAliasIterator enumerates all registers aliasing Reg.
iterator_range< pred_iterator > predecessors()
size_t size() const
Definition: SmallVector.h:52
bool isDebugInstr() const
Definition: MachineInstr.h:998
hexagon gen pred
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MachineOperand class - Representation of each machine instruction operand.
void setSingleDomain(unsigned domain)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:373
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:606
const Function & getFunction() const
Return the LLVM function that this machine code represents.
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:470
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:63
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
SmallVector< MachineInstr *, 8 > Instrs
Twiddleable instructions using or defining these registers.
#define I(x, y, z)
Definition: MD5.cpp:58
TraversalOrder traverse(MachineFunction &MF)
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.
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
bool isReg() const
isReg - Tests if this is a MO_Register operand.
auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1294
int getReachingDef(MachineInstr *MI, int PhysReg)
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
unsigned Refs
Basic reference counting.
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 IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
bool isCollapsed() const
A collapsed DomainValue has no instructions to twiddle - it simply keeps track of the domains where t...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
void resize(size_type N)
Definition: SmallVector.h:343