LLVM 18.0.0git
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#include "llvm/Support/Debug.h"
13
14using namespace llvm;
15
16#define DEBUG_TYPE "execution-deps-fix"
17
19ExecutionDomainFix::regIndices(unsigned Reg) const {
20 assert(Reg < AliasMap.size() && "Invalid register");
21 const auto &Entry = AliasMap[Reg];
22 return make_range(Entry.begin(), Entry.end());
23}
24
25DomainValue *ExecutionDomainFix::alloc(int domain) {
26 DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
27 : Avail.pop_back_val();
28 if (domain >= 0)
29 dv->addDomain(domain);
30 assert(dv->Refs == 0 && "Reference count wasn't cleared");
31 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
32 return dv;
33}
34
35void ExecutionDomainFix::release(DomainValue *DV) {
36 while (DV) {
37 assert(DV->Refs && "Bad DomainValue");
38 if (--DV->Refs)
39 return;
40
41 // There are no more DV references. Collapse any contained instructions.
42 if (DV->AvailableDomains && !DV->isCollapsed())
43 collapse(DV, DV->getFirstDomain());
44
45 DomainValue *Next = DV->Next;
46 DV->clear();
47 Avail.push_back(DV);
48 // Also release the next DomainValue in the chain.
49 DV = Next;
50 }
51}
52
53DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
54 DomainValue *DV = DVRef;
55 if (!DV || !DV->Next)
56 return DV;
57
58 // DV has a chain. Find the end.
59 do
60 DV = DV->Next;
61 while (DV->Next);
62
63 // Update DVRef to point to DV.
64 retain(DV);
65 release(DVRef);
66 DVRef = DV;
67 return DV;
68}
69
70void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
71 assert(unsigned(rx) < NumRegs && "Invalid index");
72 assert(!LiveRegs.empty() && "Must enter basic block first.");
73
74 if (LiveRegs[rx] == dv)
75 return;
76 if (LiveRegs[rx])
77 release(LiveRegs[rx]);
78 LiveRegs[rx] = retain(dv);
79}
80
81void ExecutionDomainFix::kill(int rx) {
82 assert(unsigned(rx) < NumRegs && "Invalid index");
83 assert(!LiveRegs.empty() && "Must enter basic block first.");
84 if (!LiveRegs[rx])
85 return;
86
87 release(LiveRegs[rx]);
88 LiveRegs[rx] = nullptr;
89}
90
91void ExecutionDomainFix::force(int rx, unsigned domain) {
92 assert(unsigned(rx) < NumRegs && "Invalid index");
93 assert(!LiveRegs.empty() && "Must enter basic block first.");
94 if (DomainValue *dv = LiveRegs[rx]) {
95 if (dv->isCollapsed())
96 dv->addDomain(domain);
97 else if (dv->hasDomain(domain))
98 collapse(dv, domain);
99 else {
100 // This is an incompatible open DomainValue. Collapse it to whatever and
101 // force the new value into domain. This costs a domain crossing.
102 collapse(dv, dv->getFirstDomain());
103 assert(LiveRegs[rx] && "Not live after collapse?");
104 LiveRegs[rx]->addDomain(domain);
105 }
106 } else {
107 // Set up basic collapsed DomainValue.
108 setLiveReg(rx, alloc(domain));
109 }
110}
111
112void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
113 assert(dv->hasDomain(domain) && "Cannot collapse");
114
115 // Collapse all the instructions.
116 while (!dv->Instrs.empty())
117 TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
118 dv->setSingleDomain(domain);
119
120 // If there are multiple users, give them new, unique DomainValues.
121 if (!LiveRegs.empty() && dv->Refs > 1)
122 for (unsigned rx = 0; rx != NumRegs; ++rx)
123 if (LiveRegs[rx] == dv)
124 setLiveReg(rx, alloc(domain));
125}
126
127bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
128 assert(!A->isCollapsed() && "Cannot merge into collapsed");
129 assert(!B->isCollapsed() && "Cannot merge from collapsed");
130 if (A == B)
131 return true;
132 // Restrict to the domains that A and B have in common.
133 unsigned common = A->getCommonDomains(B->AvailableDomains);
134 if (!common)
135 return false;
136 A->AvailableDomains = common;
137 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
138
139 // Clear the old DomainValue so we won't try to swizzle instructions twice.
140 B->clear();
141 // All uses of B are referred to A.
142 B->Next = retain(A);
143
144 for (unsigned rx = 0; rx != NumRegs; ++rx) {
145 assert(!LiveRegs.empty() && "no space allocated for live registers");
146 if (LiveRegs[rx] == B)
147 setLiveReg(rx, A);
148 }
149 return true;
150}
151
152void ExecutionDomainFix::enterBasicBlock(
153 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
154
155 MachineBasicBlock *MBB = TraversedMBB.MBB;
156
157 // Set up LiveRegs to represent registers entering MBB.
158 // Set default domain values to 'no domain' (nullptr)
159 if (LiveRegs.empty())
160 LiveRegs.assign(NumRegs, nullptr);
161
162 // This is the entry block.
163 if (MBB->pred_empty()) {
164 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
165 return;
166 }
167
168 // Try to coalesce live-out registers from predecessors.
170 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
171 "Should have pre-allocated MBBInfos for all MBBs");
172 LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
173 // Incoming is null if this is a backedge from a BB
174 // we haven't processed yet
175 if (Incoming.empty())
176 continue;
177
178 for (unsigned rx = 0; rx != NumRegs; ++rx) {
179 DomainValue *pdv = resolve(Incoming[rx]);
180 if (!pdv)
181 continue;
182 if (!LiveRegs[rx]) {
183 setLiveReg(rx, pdv);
184 continue;
185 }
186
187 // We have a live DomainValue from more than one predecessor.
188 if (LiveRegs[rx]->isCollapsed()) {
189 // We are already collapsed, but predecessor is not. Force it.
190 unsigned Domain = LiveRegs[rx]->getFirstDomain();
191 if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
192 collapse(pdv, Domain);
193 continue;
194 }
195
196 // Currently open, merge in predecessor.
197 if (!pdv->isCollapsed())
198 merge(LiveRegs[rx], pdv);
199 else
200 force(rx, pdv->getFirstDomain());
201 }
202 }
204 << (!TraversedMBB.IsDone ? ": incomplete\n"
205 : ": all preds known\n"));
206}
207
208void ExecutionDomainFix::leaveBasicBlock(
209 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
210 assert(!LiveRegs.empty() && "Must enter basic block first.");
211 unsigned MBBNumber = TraversedMBB.MBB->getNumber();
212 assert(MBBNumber < MBBOutRegsInfos.size() &&
213 "Unexpected basic block number.");
214 // Save register clearances at end of MBB - used by enterBasicBlock().
215 for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
216 release(OldLiveReg);
217 }
218 MBBOutRegsInfos[MBBNumber] = LiveRegs;
219 LiveRegs.clear();
220}
221
222bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
223 // Update instructions with explicit execution domains.
224 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
225 if (DomP.first) {
226 if (DomP.second)
227 visitSoftInstr(MI, DomP.second);
228 else
229 visitHardInstr(MI, DomP.first);
230 }
231
232 return !DomP.first;
233}
234
235void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
236 assert(!MI->isDebugInstr() && "Won't process debug values");
237 const MCInstrDesc &MCID = MI->getDesc();
238 for (unsigned i = 0,
239 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
240 i != e; ++i) {
241 MachineOperand &MO = MI->getOperand(i);
242 if (!MO.isReg())
243 continue;
244 if (MO.isUse())
245 continue;
246 for (int rx : regIndices(MO.getReg())) {
247 // This instruction explicitly defines rx.
248 LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
249
250 // Kill off domains redefined by generic instructions.
251 if (Kill)
252 kill(rx);
253 }
254 }
255}
256
257void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
258 // Collapse all uses.
259 for (unsigned i = mi->getDesc().getNumDefs(),
260 e = mi->getDesc().getNumOperands();
261 i != e; ++i) {
262 MachineOperand &mo = mi->getOperand(i);
263 if (!mo.isReg())
264 continue;
265 for (int rx : regIndices(mo.getReg())) {
266 force(rx, domain);
267 }
268 }
269
270 // Kill all defs and force them.
271 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
272 MachineOperand &mo = mi->getOperand(i);
273 if (!mo.isReg())
274 continue;
275 for (int rx : regIndices(mo.getReg())) {
276 kill(rx);
277 force(rx, domain);
278 }
279 }
280}
281
282void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
283 // Bitmask of available domains for this instruction after taking collapsed
284 // operands into account.
285 unsigned available = mask;
286
287 // Scan the explicit use operands for incoming domains.
289 if (!LiveRegs.empty())
290 for (unsigned i = mi->getDesc().getNumDefs(),
291 e = mi->getDesc().getNumOperands();
292 i != e; ++i) {
293 MachineOperand &mo = mi->getOperand(i);
294 if (!mo.isReg())
295 continue;
296 for (int rx : regIndices(mo.getReg())) {
297 DomainValue *dv = LiveRegs[rx];
298 if (dv == nullptr)
299 continue;
300 // Bitmask of domains that dv and available have in common.
301 unsigned common = dv->getCommonDomains(available);
302 // Is it possible to use this collapsed register for free?
303 if (dv->isCollapsed()) {
304 // Restrict available domains to the ones in common with the operand.
305 // If there are no common domains, we must pay the cross-domain
306 // penalty for this operand.
307 if (common)
308 available = common;
309 } else if (common)
310 // Open DomainValue is compatible, save it for merging.
311 used.push_back(rx);
312 else
313 // Open DomainValue is not compatible with instruction. It is useless
314 // now.
315 kill(rx);
316 }
317 }
318
319 // If the collapsed operands force a single domain, propagate the collapse.
321 unsigned domain = llvm::countr_zero(available);
322 TII->setExecutionDomain(*mi, domain);
323 visitHardInstr(mi, domain);
324 return;
325 }
326
327 // Kill off any remaining uses that don't match available, and build a list of
328 // incoming DomainValues that we want to merge.
330 for (int rx : used) {
331 assert(!LiveRegs.empty() && "no space allocated for live registers");
332 DomainValue *&LR = LiveRegs[rx];
333 // This useless DomainValue could have been missed above.
334 if (!LR->getCommonDomains(available)) {
335 kill(rx);
336 continue;
337 }
338 // Sorted insertion.
339 // Enables giving priority to the latest domains during merging.
340 const int Def = RDA->getReachingDef(mi, RC->getRegister(rx));
341 auto I = partition_point(Regs, [&](int I) {
342 return RDA->getReachingDef(mi, RC->getRegister(I)) <= Def;
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.
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 (const 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
395void 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 (const LoopTraversal::TraversedMBBInfo &TraversedMBB : TraversedMBBOrder)
458 processBasicBlock(TraversedMBB);
459
460 for (const LiveRegsDVInfo &OutLiveRegs : MBBOutRegsInfos)
461 for (DomainValue *OutLiveReg : OutLiveRegs)
462 if (OutLiveReg)
463 release(OutLiveReg);
464
465 MBBOutRegsInfos.clear();
466 Avail.clear();
467 Allocator.DestroyAll();
468
469 return false;
470}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
hexagon gen pred
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
return !LiveInRegUnits available(Reg)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
TraversalOrder traverse(MachineFunction &MF)
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:237
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:248
MCRegAliasIterator enumerates all registers aliasing Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator_range< pred_iterator > predecessors()
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:540
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:659
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI,...
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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.
virtual void setExecutionDomain(MachineInstr &MI, unsigned Domain) const
Change the opcode of MI to execute in Domain.
unsigned getNumRegs() const
Return the number of registers in this class.
MCRegister getRegister(unsigned i) const
Return the specified register in the class.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
A range adaptor for a pair of iterators.
@ Kill
The last use of a register.
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1983
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: bit.h:214
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:264
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
auto mask(ShuffFunc S, unsigned Length, OptArgs... args) -> MaskT
A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track of execution domains.
unsigned getCommonDomains(unsigned mask) const
Return bitmask of domains that are available and in mask.
void clear()
Clear this DomainValue and point to next which has all its data.
SmallVector< MachineInstr *, 8 > Instrs
Twiddleable instructions using or defining these registers.
void setSingleDomain(unsigned domain)
bool isCollapsed() const
A collapsed DomainValue has no instructions to twiddle - it simply keeps track of the domains where t...
DomainValue * Next
Pointer to the next DomainValue in a chain.
void addDomain(unsigned domain)
Mark domain as available.
unsigned AvailableDomains
Bitmask of available domains.
unsigned Refs
Basic reference counting.
unsigned getFirstDomain() const
First domain available.
bool hasDomain(unsigned domain) const
Is domain available?
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
bool IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92