134
|
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 ExecutionDomainFix::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
|
|
25 DomainValue *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
|
|
35 void 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
|
|
53 DomainValue *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
|
|
70 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 if (LiveRegs[rx] == dv)
|
|
75 return;
|
|
76 if (LiveRegs[rx])
|
|
77 release(LiveRegs[rx]);
|
|
78 LiveRegs[rx] = retain(dv);
|
|
79 }
|
|
80
|
|
81 void 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
|
|
91 void 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
|
|
112 void 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
|
|
127 bool 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
|
|
152 void 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 DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
|
|
165 return;
|
|
166 }
|
|
167
|
|
168 // Try to coalesce live-out registers from predecessors.
|
|
169 for (MachineBasicBlock *pred : MBB->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 }
|
|
203 DEBUG(dbgs() << printMBBReference(*MBB)
|
|
204 << (!TraversedMBB.IsDone ? ": incomplete\n"
|
|
205 : ": all preds known\n"));
|
|
206 }
|
|
207
|
|
208 void 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
|
|
222 bool 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
|
|
235 void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
|
|
236 assert(!MI->isDebugValue() && "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 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
|
|
257 void 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
|
|
282 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 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.
|
|
320 if (isPowerOf2_32(available)) {
|
|
321 unsigned domain = countTrailingZeros(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.
|
|
329 SmallVector<int, 4> Regs;
|
|
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 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 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 while (!Regs.empty()) {
|
|
352 if (!dv) {
|
|
353 dv = LiveRegs[Regs.pop_back_val()];
|
|
354 // Force the first dv to match the current instruction.
|
|
355 dv->AvailableDomains = dv->getCommonDomains(available);
|
|
356 assert(dv->AvailableDomains && "Domain should have been filtered");
|
|
357 continue;
|
|
358 }
|
|
359
|
|
360 DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
|
|
361 // Skip already merged values.
|
|
362 if (Latest == dv || Latest->Next)
|
|
363 continue;
|
|
364 if (merge(dv, Latest))
|
|
365 continue;
|
|
366
|
|
367 // If latest didn't merge, it is useless now. Kill all registers using it.
|
|
368 for (int i : used) {
|
|
369 assert(!LiveRegs.empty() && "no space allocated for live registers");
|
|
370 if (LiveRegs[i] == Latest)
|
|
371 kill(i);
|
|
372 }
|
|
373 }
|
|
374
|
|
375 // dv is the DomainValue we are going to use for this instruction.
|
|
376 if (!dv) {
|
|
377 dv = alloc();
|
|
378 dv->AvailableDomains = available;
|
|
379 }
|
|
380 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 for (MachineOperand &mo : mi->operands()) {
|
|
385 if (!mo.isReg())
|
|
386 continue;
|
|
387 for (int rx : regIndices(mo.getReg())) {
|
|
388 if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
|
|
389 kill(rx);
|
|
390 setLiveReg(rx, dv);
|
|
391 }
|
|
392 }
|
|
393 }
|
|
394 }
|
|
395
|
|
396 void ExecutionDomainFix::processBasicBlock(
|
|
397 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
|
|
398 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 for (MachineInstr &MI : *TraversedMBB.MBB) {
|
|
404 if (!MI.isDebugValue()) {
|
|
405 bool Kill = false;
|
|
406 if (TraversedMBB.PrimaryPass)
|
|
407 Kill = visitInstr(&MI);
|
|
408 processDefs(&MI, Kill);
|
|
409 }
|
|
410 }
|
|
411 leaveBasicBlock(TraversedMBB);
|
|
412 }
|
|
413
|
|
414 bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
|
|
415 if (skipFunction(mf.getFunction()))
|
|
416 return false;
|
|
417 MF = &mf;
|
|
418 TII = MF->getSubtarget().getInstrInfo();
|
|
419 TRI = MF->getSubtarget().getRegisterInfo();
|
|
420 LiveRegs.clear();
|
|
421 assert(NumRegs == RC->getNumRegs() && "Bad regclass");
|
|
422
|
|
423 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 const MachineRegisterInfo &MRI = mf.getRegInfo();
|
|
430 for (unsigned Reg : *RC) {
|
|
431 if (MRI.isPhysRegUsed(Reg)) {
|
|
432 anyregs = true;
|
|
433 break;
|
|
434 }
|
|
435 }
|
|
436 if (!anyregs)
|
|
437 return false;
|
|
438
|
|
439 RDA = &getAnalysis<ReachingDefAnalysis>();
|
|
440
|
|
441 // Initialize the AliasMap on the first use.
|
|
442 if (AliasMap.empty()) {
|
|
443 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
|
|
444 // therefore the LiveRegs array.
|
|
445 AliasMap.resize(TRI->getNumRegs());
|
|
446 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
|
|
447 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
|
|
448 ++AI)
|
|
449 AliasMap[*AI].push_back(i);
|
|
450 }
|
|
451
|
|
452 // Initialize the MBBOutRegsInfos
|
|
453 MBBOutRegsInfos.resize(mf.getNumBlockIDs());
|
|
454
|
|
455 // Traverse the basic blocks.
|
|
456 LoopTraversal Traversal;
|
|
457 LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
|
|
458 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
|
|
459 processBasicBlock(TraversedMBB);
|
|
460 }
|
|
461
|
|
462 for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
|
|
463 for (DomainValue *OutLiveReg : OutLiveRegs) {
|
|
464 if (OutLiveReg)
|
|
465 release(OutLiveReg);
|
|
466 }
|
|
467 }
|
|
468 MBBOutRegsInfos.clear();
|
|
469 Avail.clear();
|
|
470 Allocator.DestroyAll();
|
|
471
|
|
472 return false;
|
|
473 }
|