Line data Source code
1 : //===- ExecutionDomainFix.cpp - Fix execution domain 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 :
10 : #include "llvm/CodeGen/ExecutionDomainFix.h"
11 : #include "llvm/CodeGen/MachineRegisterInfo.h"
12 : #include "llvm/CodeGen/TargetInstrInfo.h"
13 :
14 : using namespace llvm;
15 :
16 : #define DEBUG_TYPE "execution-deps-fix"
17 :
18 : iterator_range<SmallVectorImpl<int>::const_iterator>
19 4593657 : ExecutionDomainFix::regIndices(unsigned Reg) const {
20 : assert(Reg < AliasMap.size() && "Invalid register");
21 4593657 : const auto &Entry = AliasMap[Reg];
22 4593657 : return make_range(Entry.begin(), Entry.end());
23 : }
24 :
25 603712 : DomainValue *ExecutionDomainFix::alloc(int domain) {
26 603712 : DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
27 : : Avail.pop_back_val();
28 603712 : if (domain >= 0)
29 463335 : 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 603712 : return dv;
33 : }
34 :
35 3463324 : void ExecutionDomainFix::release(DomainValue *DV) {
36 4067000 : while (DV) {
37 : assert(DV->Refs && "Bad DomainValue");
38 1491054 : if (--DV->Refs)
39 : return;
40 :
41 : // There are no more DV references. Collapse any contained instructions.
42 603676 : if (DV->AvailableDomains && !DV->isCollapsed())
43 20865 : collapse(DV, DV->getFirstDomain());
44 :
45 603676 : DomainValue *Next = DV->Next;
46 : DV->clear();
47 603676 : Avail.push_back(DV);
48 : // Also release the next DomainValue in the chain.
49 603676 : DV = Next;
50 : }
51 : }
52 :
53 13401280 : DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
54 13401280 : DomainValue *DV = DVRef;
55 13401280 : if (!DV || !DV->Next)
56 : return DV;
57 :
58 : // DV has a chain. Find the end.
59 : do
60 821 : DV = DV->Next;
61 821 : while (DV->Next);
62 :
63 : // Update DVRef to point to DV.
64 : retain(DV);
65 666 : release(DVRef);
66 666 : DVRef = DV;
67 666 : return DV;
68 : }
69 :
70 1487739 : void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
71 : assert(unsigned(rx) < NumRegs && "Invalid index");
72 : assert(!LiveRegs.empty() && "Must enter basic block first.");
73 :
74 2975478 : if (LiveRegs[rx] == dv)
75 : return;
76 1487739 : if (LiveRegs[rx])
77 23626 : release(LiveRegs[rx]);
78 2975478 : LiveRegs[rx] = retain(dv);
79 : }
80 :
81 540008 : void ExecutionDomainFix::kill(int rx) {
82 : assert(unsigned(rx) < NumRegs && "Invalid index");
83 : assert(!LiveRegs.empty() && "Must enter basic block first.");
84 1080016 : if (!LiveRegs[rx])
85 : return;
86 :
87 412768 : release(LiveRegs[rx]);
88 825536 : LiveRegs[rx] = nullptr;
89 : }
90 :
91 1026337 : void ExecutionDomainFix::force(int rx, unsigned domain) {
92 : assert(unsigned(rx) < NumRegs && "Invalid index");
93 : assert(!LiveRegs.empty() && "Must enter basic block first.");
94 2052674 : if (DomainValue *dv = LiveRegs[rx]) {
95 584358 : if (dv->isCollapsed())
96 : dv->addDomain(domain);
97 232336 : else if (dv->hasDomain(domain))
98 116017 : 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 151 : collapse(dv, dv->getFirstDomain());
103 : assert(LiveRegs[rx] && "Not live after collapse?");
104 302 : LiveRegs[rx]->addDomain(domain);
105 : }
106 : } else {
107 : // Set up basic collapsed DomainValue.
108 441979 : setLiveReg(rx, alloc(domain));
109 : }
110 1026337 : }
111 :
112 137692 : void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
113 : assert(dv->hasDomain(domain) && "Cannot collapse");
114 :
115 : // Collapse all the instructions.
116 337783 : while (!dv->Instrs.empty())
117 400182 : 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 137692 : if (!LiveRegs.empty() && dv->Refs > 1)
122 348744 : for (unsigned rx = 0; rx != NumRegs; ++rx)
123 676352 : if (LiveRegs[rx] == dv)
124 21356 : setLiveReg(rx, alloc(domain));
125 137692 : }
126 :
127 15837 : bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
128 : assert(!A->isCollapsed() && "Cannot merge into collapsed");
129 : assert(!B->isCollapsed() && "Cannot merge from collapsed");
130 15837 : if (A == B)
131 : return true;
132 : // Restrict to the domains that A and B have in common.
133 2649 : unsigned common = A->getCommonDomains(B->AvailableDomains);
134 2649 : if (!common)
135 : return false;
136 2649 : A->AvailableDomains = common;
137 5298 : 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 2649 : B->Next = retain(A);
143 :
144 87417 : for (unsigned rx = 0; rx != NumRegs; ++rx) {
145 : assert(!LiveRegs.empty() && "no space allocated for live registers");
146 169536 : if (LiveRegs[rx] == B)
147 2270 : setLiveReg(rx, A);
148 : }
149 : return true;
150 : }
151 :
152 397162 : void ExecutionDomainFix::enterBasicBlock(
153 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
154 :
155 397162 : MachineBasicBlock *MBB = TraversedMBB.MBB;
156 :
157 : // Set up LiveRegs to represent registers entering MBB.
158 : // Set default domain values to 'no domain' (nullptr)
159 397162 : if (LiveRegs.empty())
160 397162 : LiveRegs.assign(NumRegs, nullptr);
161 :
162 : // This is the entry block.
163 397162 : 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.
169 723016 : for (MachineBasicBlock *pred : MBB->predecessors()) {
170 : assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
171 : "Should have pre-allocated MBBInfos for all MBBs");
172 423418 : LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
173 : // Incoming is null if this is a backedge from a BB
174 : // we haven't processed yet
175 423418 : if (Incoming.empty())
176 : continue;
177 :
178 13820070 : for (unsigned rx = 0; rx != NumRegs; ++rx) {
179 26802560 : DomainValue *pdv = resolve(Incoming[rx]);
180 13401280 : if (!pdv)
181 : continue;
182 2401946 : if (!LiveRegs[rx]) {
183 866692 : setLiveReg(rx, pdv);
184 866692 : continue;
185 : }
186 :
187 : // We have a live DomainValue from more than one predecessor.
188 334281 : if (LiveRegs[rx]->isCollapsed()) {
189 : // We are already collapsed, but predecessor is not. Force it.
190 319127 : unsigned Domain = LiveRegs[rx]->getFirstDomain();
191 319127 : if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
192 659 : collapse(pdv, Domain);
193 319127 : continue;
194 : }
195 :
196 : // Currently open, merge in predecessor.
197 15154 : if (!pdv->isCollapsed())
198 14314 : merge(LiveRegs[rx], pdv);
199 : else
200 1680 : force(rx, pdv->getFirstDomain());
201 : }
202 : }
203 : LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
204 : << (!TraversedMBB.IsDone ? ": incomplete\n"
205 : : ": all preds known\n"));
206 : }
207 :
208 397162 : void ExecutionDomainFix::leaveBasicBlock(
209 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
210 : assert(!LiveRegs.empty() && "Must enter basic block first.");
211 397162 : 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 2616618 : for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
216 2219456 : release(OldLiveReg);
217 : }
218 794324 : MBBOutRegsInfos[MBBNumber] = LiveRegs;
219 : LiveRegs.clear();
220 397162 : }
221 :
222 2327566 : bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
223 : // Update instructions with explicit execution domains.
224 2327566 : std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
225 2327566 : if (DomP.first) {
226 649661 : if (DomP.second)
227 335553 : visitSoftInstr(MI, DomP.second);
228 : else
229 314108 : visitHardInstr(MI, DomP.first);
230 : }
231 :
232 2327566 : return !DomP.first;
233 : }
234 :
235 2781404 : void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
236 : assert(!MI->isDebugInstr() && "Won't process debug values");
237 2781404 : const MCInstrDesc &MCID = MI->getDesc();
238 1469631 : for (unsigned i = 0,
239 2781404 : e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
240 4251035 : i != e; ++i) {
241 1469631 : MachineOperand &MO = MI->getOperand(i);
242 1469631 : if (!MO.isReg())
243 : continue;
244 1408056 : if (MO.isUse())
245 : continue;
246 1877560 : 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 596080 : if (Kill)
252 51309 : kill(rx);
253 : }
254 : }
255 2781404 : }
256 :
257 449534 : void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
258 : // Collapse all uses.
259 1909209 : for (unsigned i = mi->getDesc().getNumDefs(),
260 449534 : e = mi->getDesc().getNumOperands();
261 1909209 : i != e; ++i) {
262 1459675 : MachineOperand &mo = mi->getOperand(i);
263 1459675 : if (!mo.isReg())
264 : continue;
265 1813027 : for (int rx : regIndices(mo.getReg())) {
266 692257 : force(rx, domain);
267 : }
268 : }
269 :
270 : // Kill all defs and force them.
271 801120 : for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
272 351586 : MachineOperand &mo = mi->getOperand(i);
273 351586 : if (!mo.isReg())
274 : continue;
275 684826 : for (int rx : regIndices(mo.getReg())) {
276 333240 : kill(rx);
277 333240 : force(rx, domain);
278 : }
279 : }
280 449534 : }
281 :
282 335553 : void 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.
288 : SmallVector<int, 4> used;
289 335553 : if (!LiveRegs.empty())
290 1966119 : for (unsigned i = mi->getDesc().getNumDefs(),
291 335553 : e = mi->getDesc().getNumOperands();
292 1966119 : i != e; ++i) {
293 1630566 : MachineOperand &mo = mi->getOperand(i);
294 1630566 : if (!mo.isReg())
295 : continue;
296 1324733 : for (int rx : regIndices(mo.getReg())) {
297 254124 : DomainValue *dv = LiveRegs[rx];
298 254124 : if (dv == nullptr)
299 : continue;
300 : // Bitmask of domains that dv and available have in common.
301 219766 : unsigned common = dv->getCommonDomains(available);
302 : // Is it possible to use this collapsed register for free?
303 219766 : 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 153841 : if (common)
308 : available = common;
309 65925 : } else if (common)
310 : // Open DomainValue is compatible, save it for merging.
311 65908 : used.push_back(rx);
312 : else
313 : // Open DomainValue is not compatible with instruction. It is useless
314 : // now.
315 17 : kill(rx);
316 : }
317 : }
318 :
319 : // If the collapsed operands force a single domain, propagate the collapse.
320 : if (isPowerOf2_32(available)) {
321 135426 : unsigned domain = countTrailingZeros(available);
322 135426 : TII->setExecutionDomain(*mi, domain);
323 135426 : 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.
329 : SmallVector<int, 4> Regs;
330 263525 : for (int rx : used) {
331 : assert(!LiveRegs.empty() && "no space allocated for live registers");
332 63398 : DomainValue *&LR = LiveRegs[rx];
333 : // This useless DomainValue could have been missed above.
334 126796 : if (!LR->getCommonDomains(available)) {
335 0 : kill(rx);
336 0 : continue;
337 : }
338 : // Sorted insertion.
339 : // Enables giving priority to the latest domains during merging.
340 : auto I = std::upper_bound(
341 : Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
342 : return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
343 : RDA->getReachingDef(mi, RC->getRegister(RHS));
344 : });
345 63398 : Regs.insert(I, rx);
346 : }
347 :
348 : // doms are now sorted in order of appearance. Try to merge them all, giving
349 : // priority to the latest ones.
350 : DomainValue *dv = nullptr;
351 263525 : while (!Regs.empty()) {
352 63398 : if (!dv) {
353 59750 : dv = LiveRegs[Regs.pop_back_val()];
354 : // Force the first dv to match the current instruction.
355 59750 : dv->AvailableDomains = dv->getCommonDomains(available);
356 : assert(dv->AvailableDomains && "Domain should have been filtered");
357 59750 : continue;
358 : }
359 :
360 3648 : DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
361 : // Skip already merged values.
362 3648 : if (Latest == dv || Latest->Next)
363 : continue;
364 1523 : if (merge(dv, Latest))
365 : continue;
366 :
367 : // If latest didn't merge, it is useless now. Kill all registers using it.
368 0 : for (int i : used) {
369 : assert(!LiveRegs.empty() && "no space allocated for live registers");
370 0 : if (LiveRegs[i] == Latest)
371 0 : kill(i);
372 : }
373 : }
374 :
375 : // dv is the DomainValue we are going to use for this instruction.
376 200127 : if (!dv) {
377 140377 : dv = alloc();
378 140377 : dv->AvailableDomains = available;
379 : }
380 200127 : dv->Instrs.push_back(mi);
381 :
382 : // Finally set all defs and non-collapsed uses to dv. We must iterate through
383 : // all the operators, including imp-def ones.
384 1323976 : for (MachineOperand &mo : mi->operands()) {
385 1123849 : if (!mo.isReg())
386 : continue;
387 1017737 : for (int rx : regIndices(mo.getReg())) {
388 497050 : if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
389 155442 : kill(rx);
390 155442 : setLiveReg(rx, dv);
391 : }
392 : }
393 : }
394 : }
395 :
396 397162 : void ExecutionDomainFix::processBasicBlock(
397 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
398 397162 : enterBasicBlock(TraversedMBB);
399 : // If this block is not done, it makes little sense to make any decisions
400 : // based on clearance information. We need to make a second pass anyway,
401 : // and by then we'll have better information, so we can avoid doing the work
402 : // to try and break dependencies now.
403 3313804 : for (MachineInstr &MI : *TraversedMBB.MBB) {
404 : if (!MI.isDebugInstr()) {
405 : bool Kill = false;
406 2781404 : if (TraversedMBB.PrimaryPass)
407 2327566 : Kill = visitInstr(&MI);
408 2781404 : processDefs(&MI, Kill);
409 : }
410 : }
411 397162 : leaveBasicBlock(TraversedMBB);
412 397162 : }
413 :
414 125006 : bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
415 125006 : if (skipFunction(mf.getFunction()))
416 : return false;
417 124864 : MF = &mf;
418 124864 : TII = MF->getSubtarget().getInstrInfo();
419 124864 : TRI = MF->getSubtarget().getRegisterInfo();
420 : LiveRegs.clear();
421 : assert(NumRegs == RC->getNumRegs() && "Bad regclass");
422 :
423 : LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
424 : << TRI->getRegClassName(RC) << " **********\n");
425 :
426 : // If no relevant registers are used in the function, we can skip it
427 : // completely.
428 : bool anyregs = false;
429 124864 : const MachineRegisterInfo &MRI = mf.getRegInfo();
430 1032152 : for (unsigned Reg : *RC) {
431 1004852 : if (MRI.isPhysRegUsed(Reg)) {
432 : anyregs = true;
433 : break;
434 : }
435 : }
436 124864 : if (!anyregs)
437 : return false;
438 :
439 97564 : RDA = &getAnalysis<ReachingDefAnalysis>();
440 :
441 : // Initialize the AliasMap on the first use.
442 97564 : if (AliasMap.empty()) {
443 : // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
444 : // therefore the LiveRegs array.
445 6504 : AliasMap.resize(TRI->getNumRegs());
446 214632 : for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
447 2014314 : for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
448 1806186 : ++AI)
449 3612372 : AliasMap[*AI].push_back(i);
450 : }
451 :
452 : // Initialize the MBBOutRegsInfos
453 195128 : MBBOutRegsInfos.resize(mf.getNumBlockIDs());
454 :
455 : // Traverse the basic blocks.
456 : LoopTraversal Traversal;
457 97564 : LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
458 494726 : for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
459 397162 : processBasicBlock(TraversedMBB);
460 : }
461 :
462 426890 : for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
463 10819054 : for (DomainValue *OutLiveReg : OutLiveRegs) {
464 10489728 : if (OutLiveReg)
465 806808 : release(OutLiveReg);
466 : }
467 : }
468 97564 : MBBOutRegsInfos.clear();
469 : Avail.clear();
470 97564 : Allocator.DestroyAll();
471 :
472 : return false;
473 : }
|
