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
9#include "llvm/CodeGen/ExecutionDomainFix.h"
10#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
11#include "llvm/CodeGen/MachinePassManager.h"
12#include "llvm/CodeGen/MachineRegisterInfo.h"
13#include "llvm/CodeGen/Passes.h"
14#include "llvm/CodeGen/ReachingDefAnalysis.h"
15#include "llvm/CodeGen/TargetInstrInfo.h"
16#include "llvm/IR/Analysis.h"
17#include "llvm/Support/Debug.h"
18
19using namespace llvm;
20
21#define DEBUG_TYPE "execution-deps-fix"
22
23namespace {
24
25class ExecutionDomainFixImpl {
26 SpecificBumpPtrAllocator<DomainValue> Allocator;
27 SmallVector<DomainValue *, 16> Avail;
28
29 const TargetRegisterClass *RC;
30 MachineFunction *MF = nullptr;
31 const TargetInstrInfo *TII = nullptr;
32 const TargetRegisterInfo *TRI = nullptr;
33 std::vector<SmallVector<int, 1>> AliasMap;
34 /// Value currently in each register, or NULL when no value is being tracked.
35 /// This counts as a DomainValue reference.
36 using LiveRegsDVInfo = std::vector<DomainValue *>;
37 LiveRegsDVInfo LiveRegs;
38 /// Keeps domain information for all registers. Note that this
39 /// is different from the usual definition notion of liveness. The CPU
40 /// doesn't care whether or not we consider a register killed.
41 using OutRegsInfoMap = SmallVector<LiveRegsDVInfo, 4>;
42 OutRegsInfoMap MBBOutRegsInfos;
43
44 ReachingDefInfo *RDI = nullptr;
45
46public:
47 bool runOnMachineFunction(MachineFunction &MF,
48 function_ref<ReachingDefInfo *()> GetRDI);
49
50private:
51 /// Translate TRI register number to a list of indices into our smaller tables
52 /// of interesting registers.
53 iterator_range<SmallVectorImpl<int>::const_iterator>
54 regIndices(MCRegister Reg) const;
55
56 /// DomainValue allocation.
57 DomainValue *alloc(int domain = -1);
58
59 /// Add reference to DV.
60 DomainValue *retain(DomainValue *DV) {
61 if (DV)
62 ++DV->Refs;
63 return DV;
64 }
65
66 /// Release a reference to DV. When the last reference is released,
67 /// collapse if needed.
68 void release(DomainValue *);
69
70 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
71 /// Update the referenced pointer when necessary.
72 DomainValue *resolve(DomainValue *&);
73
74 /// Set LiveRegs[rx] = dv, updating reference counts.
75 void setLiveReg(int rx, DomainValue *DV);
76
77 /// Kill register rx, recycle or collapse any DomainValue.
78 void kill(int rx);
79
80 /// Force register rx into domain.
81 void force(int rx, unsigned domain);
82
83 /// Collapse open DomainValue into given domain. If there are multiple
84 /// registers using dv, they each get a unique collapsed DomainValue.
85 void collapse(DomainValue *dv, unsigned domain);
86
87 /// All instructions and registers in B are moved to A, and B is released.
88 bool merge(DomainValue *A, DomainValue *B);
89
90 /// Set up LiveRegs by merging predecessor live-out values.
91 void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
92
93 /// Update live-out values.
94 void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
95
96 /// Process he given basic block.
97 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
98
99 /// Visit given insturcion.
100 bool visitInstr(MachineInstr *);
101
102 /// Update def-ages for registers defined by MI.
103 /// If Kill is set, also kill off DomainValues clobbered by the defs.
104 void processDefs(MachineInstr *, bool Kill);
105
106 /// A soft instruction can be changed to work in other domains given by mask.
107 void visitSoftInstr(MachineInstr *, unsigned mask);
108
109 /// A hard instruction only works in one domain. All input registers will be
110 /// forced into that domain.
111 void visitHardInstr(MachineInstr *, unsigned domain);
112};
113
114} // namespace
115
116iterator_range<SmallVectorImpl<int>::const_iterator>
117ExecutionDomainFixImpl::regIndices(MCRegister Reg) const {
118 assert(Reg < AliasMap.size() && "Invalid register");
119 const auto &Entry = AliasMap[Reg.id()];
120 return make_range(x: Entry.begin(), y: Entry.end());
121}
122
123DomainValue *ExecutionDomainFixImpl::alloc(int domain) {
124 DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
125 : Avail.pop_back_val();
126 if (domain >= 0)
127 dv->addDomain(domain);
128 assert(dv->Refs == 0 && "Reference count wasn't cleared");
129 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
130 return dv;
131}
132
133void ExecutionDomainFixImpl::release(DomainValue *DV) {
134 while (DV) {
135 assert(DV->Refs && "Bad DomainValue");
136 if (--DV->Refs)
137 return;
138
139 // There are no more DV references. Collapse any contained instructions.
140 if (DV->AvailableDomains && !DV->isCollapsed())
141 collapse(dv: DV, domain: DV->getFirstDomain());
142
143 DomainValue *Next = DV->Next;
144 DV->clear();
145 Avail.push_back(Elt: DV);
146 // Also release the next DomainValue in the chain.
147 DV = Next;
148 }
149}
150
151DomainValue *ExecutionDomainFixImpl::resolve(DomainValue *&DVRef) {
152 DomainValue *DV = DVRef;
153 if (!DV || !DV->Next)
154 return DV;
155
156 // DV has a chain. Find the end.
157 do
158 DV = DV->Next;
159 while (DV->Next);
160
161 // Update DVRef to point to DV.
162 retain(DV);
163 release(DV: DVRef);
164 DVRef = DV;
165 return DV;
166}
167
168void ExecutionDomainFixImpl::setLiveReg(int rx, DomainValue *dv) {
169 assert(unsigned(rx) < RC->getNumRegs() && "Invalid index");
170 assert(!LiveRegs.empty() && "Must enter basic block first.");
171
172 if (LiveRegs[rx] == dv)
173 return;
174 if (LiveRegs[rx])
175 release(DV: LiveRegs[rx]);
176 LiveRegs[rx] = retain(DV: dv);
177}
178
179void ExecutionDomainFixImpl::kill(int rx) {
180 assert(unsigned(rx) < RC->getNumRegs() && "Invalid index");
181 assert(!LiveRegs.empty() && "Must enter basic block first.");
182 if (!LiveRegs[rx])
183 return;
184
185 release(DV: LiveRegs[rx]);
186 LiveRegs[rx] = nullptr;
187}
188
189void ExecutionDomainFixImpl::force(int rx, unsigned domain) {
190 assert(unsigned(rx) < RC->getNumRegs() && "Invalid index");
191 assert(!LiveRegs.empty() && "Must enter basic block first.");
192 if (DomainValue *dv = LiveRegs[rx]) {
193 if (dv->isCollapsed())
194 dv->addDomain(domain);
195 else if (dv->hasDomain(domain))
196 collapse(dv, domain);
197 else {
198 // This is an incompatible open DomainValue. Collapse it to whatever and
199 // force the new value into domain. This costs a domain crossing.
200 collapse(dv, domain: dv->getFirstDomain());
201 assert(LiveRegs[rx] && "Not live after collapse?");
202 LiveRegs[rx]->addDomain(domain);
203 }
204 } else {
205 // Set up basic collapsed DomainValue.
206 setLiveReg(rx, dv: alloc(domain));
207 }
208}
209
210void ExecutionDomainFixImpl::collapse(DomainValue *dv, unsigned domain) {
211 assert(dv->hasDomain(domain) && "Cannot collapse");
212
213 // Collapse all the instructions.
214 while (!dv->Instrs.empty())
215 TII->setExecutionDomain(MI&: *dv->Instrs.pop_back_val(), Domain: domain);
216 dv->setSingleDomain(domain);
217
218 // If there are multiple users, give them new, unique DomainValues.
219 if (!LiveRegs.empty() && dv->Refs > 1)
220 for (unsigned rx = 0; rx != RC->getNumRegs(); ++rx)
221 if (LiveRegs[rx] == dv)
222 setLiveReg(rx, dv: alloc(domain));
223}
224
225bool ExecutionDomainFixImpl::merge(DomainValue *A, DomainValue *B) {
226 assert(!A->isCollapsed() && "Cannot merge into collapsed");
227 assert(!B->isCollapsed() && "Cannot merge from collapsed");
228 if (A == B)
229 return true;
230 // Restrict to the domains that A and B have in common.
231 unsigned common = A->getCommonDomains(mask: B->AvailableDomains);
232 if (!common)
233 return false;
234 A->AvailableDomains = common;
235 A->Instrs.append(in_start: B->Instrs.begin(), in_end: B->Instrs.end());
236
237 // Clear the old DomainValue so we won't try to swizzle instructions twice.
238 B->clear();
239 // All uses of B are referred to A.
240 B->Next = retain(DV: A);
241
242 for (unsigned rx = 0; rx != RC->getNumRegs(); ++rx) {
243 assert(!LiveRegs.empty() && "no space allocated for live registers");
244 if (LiveRegs[rx] == B)
245 setLiveReg(rx, dv: A);
246 }
247 return true;
248}
249
250void ExecutionDomainFixImpl::enterBasicBlock(
251 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
252
253 MachineBasicBlock *MBB = TraversedMBB.MBB;
254
255 // Set up LiveRegs to represent registers entering MBB.
256 // Set default domain values to 'no domain' (nullptr)
257 if (LiveRegs.empty())
258 LiveRegs.assign(n: RC->getNumRegs(), val: nullptr);
259
260 // This is the entry block.
261 if (MBB->pred_empty()) {
262 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
263 return;
264 }
265
266 // Try to coalesce live-out registers from predecessors.
267 for (MachineBasicBlock *pred : MBB->predecessors()) {
268 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
269 "Should have pre-allocated MBBInfos for all MBBs");
270 LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
271 // Incoming is null if this is a backedge from a BB
272 // we haven't processed yet
273 if (Incoming.empty())
274 continue;
275
276 for (unsigned rx = 0; rx != RC->getNumRegs(); ++rx) {
277 DomainValue *pdv = resolve(DVRef&: Incoming[rx]);
278 if (!pdv)
279 continue;
280 if (!LiveRegs[rx]) {
281 setLiveReg(rx, dv: pdv);
282 continue;
283 }
284
285 // We have a live DomainValue from more than one predecessor.
286 if (LiveRegs[rx]->isCollapsed()) {
287 // We are already collapsed, but predecessor is not. Force it.
288 unsigned Domain = LiveRegs[rx]->getFirstDomain();
289 if (!pdv->isCollapsed() && pdv->hasDomain(domain: Domain))
290 collapse(dv: pdv, domain: Domain);
291 continue;
292 }
293
294 // Currently open, merge in predecessor.
295 if (!pdv->isCollapsed())
296 merge(A: LiveRegs[rx], B: pdv);
297 else
298 force(rx, domain: pdv->getFirstDomain());
299 }
300 }
301 LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
302 << (!TraversedMBB.IsDone ? ": incomplete\n"
303 : ": all preds known\n"));
304}
305
306void ExecutionDomainFixImpl::leaveBasicBlock(
307 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
308 assert(!LiveRegs.empty() && "Must enter basic block first.");
309 unsigned MBBNumber = TraversedMBB.MBB->getNumber();
310 assert(MBBNumber < MBBOutRegsInfos.size() &&
311 "Unexpected basic block number.");
312 // Save register clearances at end of MBB - used by enterBasicBlock().
313 for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
314 release(DV: OldLiveReg);
315 }
316 MBBOutRegsInfos[MBBNumber] = LiveRegs;
317 LiveRegs.clear();
318}
319
320bool ExecutionDomainFixImpl::visitInstr(MachineInstr *MI) {
321 // Update instructions with explicit execution domains.
322 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(MI: *MI);
323 if (DomP.first) {
324 if (DomP.second)
325 visitSoftInstr(MI, mask: DomP.second);
326 else
327 visitHardInstr(MI, domain: DomP.first);
328 }
329
330 return !DomP.first;
331}
332
333void ExecutionDomainFixImpl::processDefs(MachineInstr *MI, bool Kill) {
334 assert(!MI->isDebugInstr() && "Won't process debug values");
335 const MCInstrDesc &MCID = MI->getDesc();
336 for (unsigned i = 0,
337 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
338 i != e; ++i) {
339 MachineOperand &MO = MI->getOperand(i);
340 if (!MO.isReg())
341 continue;
342 if (MO.isUse())
343 continue;
344 for (int rx : regIndices(Reg: MO.getReg())) {
345 // This instruction explicitly defines rx.
346 LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
347
348 // Kill off domains redefined by generic instructions.
349 if (Kill)
350 kill(rx);
351 }
352 }
353}
354
355void ExecutionDomainFixImpl::visitHardInstr(MachineInstr *mi, unsigned domain) {
356 // Collapse all uses.
357 for (unsigned i = mi->getDesc().getNumDefs(),
358 e = mi->getDesc().getNumOperands();
359 i != e; ++i) {
360 MachineOperand &mo = mi->getOperand(i);
361 if (!mo.isReg())
362 continue;
363 for (int rx : regIndices(Reg: mo.getReg())) {
364 force(rx, domain);
365 }
366 }
367
368 // Kill all defs and force them.
369 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
370 MachineOperand &mo = mi->getOperand(i);
371 if (!mo.isReg())
372 continue;
373 for (int rx : regIndices(Reg: mo.getReg())) {
374 kill(rx);
375 force(rx, domain);
376 }
377 }
378}
379
380void ExecutionDomainFixImpl::visitSoftInstr(MachineInstr *mi, unsigned mask) {
381 // Bitmask of available domains for this instruction after taking collapsed
382 // operands into account.
383 unsigned available = mask;
384
385 // Scan the explicit use operands for incoming domains.
386 SmallVector<int, 4> used;
387 if (!LiveRegs.empty())
388 for (unsigned i = mi->getDesc().getNumDefs(),
389 e = mi->getDesc().getNumOperands();
390 i != e; ++i) {
391 MachineOperand &mo = mi->getOperand(i);
392 if (!mo.isReg())
393 continue;
394 for (int rx : regIndices(Reg: mo.getReg())) {
395 DomainValue *dv = LiveRegs[rx];
396 if (dv == nullptr)
397 continue;
398 // Bitmask of domains that dv and available have in common.
399 unsigned common = dv->getCommonDomains(mask: available);
400 // Is it possible to use this collapsed register for free?
401 if (dv->isCollapsed()) {
402 // Restrict available domains to the ones in common with the operand.
403 // If there are no common domains, we must pay the cross-domain
404 // penalty for this operand.
405 if (common)
406 available = common;
407 } else if (common)
408 // Open DomainValue is compatible, save it for merging.
409 used.push_back(Elt: rx);
410 else
411 // Open DomainValue is not compatible with instruction. It is useless
412 // now.
413 kill(rx);
414 }
415 }
416
417 // If the collapsed operands force a single domain, propagate the collapse.
418 if (isPowerOf2_32(Value: available)) {
419 unsigned domain = llvm::countr_zero(Val: available);
420 TII->setExecutionDomain(MI&: *mi, Domain: domain);
421 visitHardInstr(mi, domain);
422 return;
423 }
424
425 // Kill off any remaining uses that don't match available, and build a list of
426 // incoming DomainValues that we want to merge.
427 SmallVector<int, 4> Regs;
428 for (int rx : used) {
429 assert(!LiveRegs.empty() && "no space allocated for live registers");
430 DomainValue *&LR = LiveRegs[rx];
431 // This useless DomainValue could have been missed above.
432 if (!LR->getCommonDomains(mask: available)) {
433 kill(rx);
434 continue;
435 }
436 // Sorted insertion.
437 // Enables giving priority to the latest domains during merging.
438 const int Def = RDI->getReachingDef(MI: mi, Reg: RC->getRegister(i: rx));
439 auto I = partition_point(Range&: Regs, P: [&](int I) {
440 return RDI->getReachingDef(MI: mi, Reg: RC->getRegister(i: I)) <= Def;
441 });
442 Regs.insert(I, Elt: rx);
443 }
444
445 // doms are now sorted in order of appearance. Try to merge them all, giving
446 // priority to the latest ones.
447 DomainValue *dv = nullptr;
448 while (!Regs.empty()) {
449 if (!dv) {
450 dv = LiveRegs[Regs.pop_back_val()];
451 // Force the first dv to match the current instruction.
452 dv->AvailableDomains = dv->getCommonDomains(mask: available);
453 assert(dv->AvailableDomains && "Domain should have been filtered");
454 continue;
455 }
456
457 DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
458 // Skip already merged values.
459 if (Latest == dv || Latest->Next)
460 continue;
461 if (merge(A: dv, B: Latest))
462 continue;
463
464 // If latest didn't merge, it is useless now. Kill all registers using it.
465 for (int i : used) {
466 assert(!LiveRegs.empty() && "no space allocated for live registers");
467 if (LiveRegs[i] == Latest)
468 kill(rx: i);
469 }
470 }
471
472 // dv is the DomainValue we are going to use for this instruction.
473 if (!dv) {
474 dv = alloc();
475 dv->AvailableDomains = available;
476 }
477 dv->Instrs.push_back(Elt: mi);
478
479 // Finally set all defs and non-collapsed uses to dv. We must iterate through
480 // all the operators, including imp-def ones.
481 for (const MachineOperand &mo : mi->operands()) {
482 if (!mo.isReg())
483 continue;
484 for (int rx : regIndices(Reg: mo.getReg())) {
485 if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
486 kill(rx);
487 setLiveReg(rx, dv);
488 }
489 }
490 }
491}
492
493void ExecutionDomainFixImpl::processBasicBlock(
494 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
495 enterBasicBlock(TraversedMBB);
496 // If this block is not done, it makes little sense to make any decisions
497 // based on clearance information. We need to make a second pass anyway,
498 // and by then we'll have better information, so we can avoid doing the work
499 // to try and break dependencies now.
500 for (MachineInstr &MI : *TraversedMBB.MBB) {
501 if (!MI.isDebugInstr()) {
502 bool Kill = false;
503 if (TraversedMBB.PrimaryPass)
504 Kill = visitInstr(MI: &MI);
505 processDefs(MI: &MI, Kill);
506 }
507 }
508 leaveBasicBlock(TraversedMBB);
509}
510
511bool ExecutionDomainFixImpl::runOnMachineFunction(
512 MachineFunction &mf, function_ref<ReachingDefInfo *()> GetRDI) {
513 MF = &mf;
514 TII = MF->getSubtarget().getInstrInfo();
515 TRI = MF->getSubtarget().getRegisterInfo();
516 RC = TRI->getRegClassToMinimizeDomainCrossings();
517 assert(RC &&
518 "getRegClassToMinimizeDomainCrossings in TRI must be implemented for "
519 "targets using ExecutionDomainFix");
520 LiveRegs.clear();
521
522 LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
523 << TRI->getRegClassName(RC) << " **********\n");
524
525 // If no relevant registers are used in the function, we can skip it
526 // completely.
527 bool anyregs = false;
528 const MachineRegisterInfo &MRI = mf.getRegInfo();
529 for (unsigned Reg : *RC) {
530 if (MRI.isPhysRegUsed(PhysReg: Reg, /*SkipRegMaskTest=*/true)) {
531 anyregs = true;
532 break;
533 }
534 }
535 if (!anyregs)
536 return false;
537
538 RDI = GetRDI();
539
540 // Initialize the AliasMap on the first use.
541 if (AliasMap.empty()) {
542 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
543 // therefore the LiveRegs array.
544 AliasMap.resize(new_size: TRI->getNumRegs());
545 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
546 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
547 ++AI)
548 AliasMap[(*AI).id()].push_back(Elt: i);
549 }
550
551 // Initialize the MBBOutRegsInfos
552 MBBOutRegsInfos.resize(N: mf.getNumBlockIDs());
553
554 // Traverse the basic blocks.
555 LoopTraversal Traversal;
556 LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(MF&: mf);
557 for (const LoopTraversal::TraversedMBBInfo &TraversedMBB : TraversedMBBOrder)
558 processBasicBlock(TraversedMBB);
559
560 for (const LiveRegsDVInfo &OutLiveRegs : MBBOutRegsInfos)
561 for (DomainValue *OutLiveReg : OutLiveRegs)
562 if (OutLiveReg)
563 release(DV: OutLiveReg);
564
565 MBBOutRegsInfos.clear();
566 Avail.clear();
567 Allocator.DestroyAll();
568
569 return false;
570}
571
572char ExecutionDomainFixLegacy::ID = 0;
573INITIALIZE_PASS_BEGIN(ExecutionDomainFixLegacy, DEBUG_TYPE,
574 "execution-domain-fix", false, false)
575INITIALIZE_PASS_DEPENDENCY(ReachingDefInfoWrapperPass)
576INITIALIZE_PASS_END(ExecutionDomainFixLegacy, DEBUG_TYPE,
577 "execution-domain-fix", false, false)
578
579FunctionPass *llvm::createExecutionDomainFixLegacyPass() {
580 return new ExecutionDomainFixLegacy();
581}
582
583bool ExecutionDomainFixLegacy::runOnMachineFunction(MachineFunction &MF) {
584 if (skipFunction(F: MF.getFunction()))
585 return false;
586 ExecutionDomainFixImpl Impl;
587 return Impl.runOnMachineFunction(mf&: MF, GetRDI: [&]() {
588 return &getAnalysis<ReachingDefInfoWrapperPass>().getRDI();
589 });
590}
591
592PreservedAnalyses
593ExecutionDomainFixPass::run(MachineFunction &MF,
594 MachineFunctionAnalysisManager &MFAM) {
595 MFPropsModifier _(*this, MF);
596 ExecutionDomainFixImpl Impl;
597 bool Changed = Impl.runOnMachineFunction(
598 mf&: MF, GetRDI: [&]() { return &MFAM.getResult<ReachingDefAnalysis>(IR&: MF); });
599 if (!Changed)
600 return PreservedAnalyses::all();
601 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
602}
603