1 //===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the execution dependency fix pass.
12 // Some X86 SSE instructions like mov, and, or, xor are available in different
13 // variants for different operand types. These variant instructions are
14 // equivalent, but on Nehalem and newer cpus there is extra latency
15 // transferring data between integer and floating point domains. ARM cores
16 // have similar issues when they are configured with both VFP and NEON
19 // This pass changes the variant instructions to minimize domain crossings.
21 //===----------------------------------------------------------------------===//
23 #define DEBUG_TYPE "execution-fix"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/Target/TargetMachine.h"
29 #include "llvm/ADT/PostOrderIterator.h"
30 #include "llvm/Support/Allocator.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
35 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
36 /// of execution domains.
38 /// An open DomainValue represents a set of instructions that can still switch
39 /// execution domain. Multiple registers may refer to the same open
40 /// DomainValue - they will eventually be collapsed to the same execution
43 /// A collapsed DomainValue represents a single register that has been forced
44 /// into one of more execution domains. There is a separate collapsed
45 /// DomainValue for each register, but it may contain multiple execution
46 /// domains. A register value is initially created in a single execution
47 /// domain, but if we were forced to pay the penalty of a domain crossing, we
48 /// keep track of the fact the the register is now available in multiple
52 // Basic reference counting.
55 // Bitmask of available domains. For an open DomainValue, it is the still
56 // possible domains for collapsing. For a collapsed DomainValue it is the
57 // domains where the register is available for free.
58 unsigned AvailableDomains;
60 // Position of the last defining instruction.
63 // Pointer to the next DomainValue in a chain. When two DomainValues are
64 // merged, Victim.Next is set to point to Victor, so old DomainValue
65 // references can be updated by folowing the chain.
68 // Twiddleable instructions using or defining these registers.
69 SmallVector<MachineInstr*, 8> Instrs;
71 // A collapsed DomainValue has no instructions to twiddle - it simply keeps
72 // track of the domains where the registers are already available.
73 bool isCollapsed() const { return Instrs.empty(); }
75 // Is domain available?
76 bool hasDomain(unsigned domain) const {
77 return AvailableDomains & (1u << domain);
80 // Mark domain as available.
81 void addDomain(unsigned domain) {
82 AvailableDomains |= 1u << domain;
85 // Restrict to a single domain available.
86 void setSingleDomain(unsigned domain) {
87 AvailableDomains = 1u << domain;
90 // Return bitmask of domains that are available and in mask.
91 unsigned getCommonDomains(unsigned mask) const {
92 return AvailableDomains & mask;
95 // First domain available.
96 unsigned getFirstDomain() const {
97 return CountTrailingZeros_32(AvailableDomains);
100 DomainValue() : Refs(0) { clear(); }
102 // Clear this DomainValue and point to next which has all its data.
104 AvailableDomains = Dist = 0;
112 class ExeDepsFix : public MachineFunctionPass {
114 SpecificBumpPtrAllocator<DomainValue> Allocator;
115 SmallVector<DomainValue*,16> Avail;
117 const TargetRegisterClass *const RC;
119 const TargetInstrInfo *TII;
120 const TargetRegisterInfo *TRI;
121 std::vector<int> AliasMap;
122 const unsigned NumRegs;
123 DomainValue **LiveRegs;
124 typedef DenseMap<MachineBasicBlock*,DomainValue**> LiveOutMap;
129 ExeDepsFix(const TargetRegisterClass *rc)
130 : MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {}
132 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
133 AU.setPreservesAll();
134 MachineFunctionPass::getAnalysisUsage(AU);
137 virtual bool runOnMachineFunction(MachineFunction &MF);
139 virtual const char *getPassName() const {
140 return "Execution dependency fix";
145 int regIndex(unsigned Reg);
147 // DomainValue allocation.
148 DomainValue *alloc(int domain = -1);
149 DomainValue *retain(DomainValue *DV) {
153 void release(DomainValue*);
154 DomainValue *resolve(DomainValue*&);
156 // LiveRegs manipulations.
157 void setLiveReg(int rx, DomainValue *DV);
159 void force(int rx, unsigned domain);
160 void collapse(DomainValue *dv, unsigned domain);
161 bool merge(DomainValue *A, DomainValue *B);
163 void enterBasicBlock(MachineBasicBlock*);
164 void leaveBasicBlock(MachineBasicBlock*);
165 void visitInstr(MachineInstr*);
166 void visitGenericInstr(MachineInstr*);
167 void visitSoftInstr(MachineInstr*, unsigned mask);
168 void visitHardInstr(MachineInstr*, unsigned domain);
172 char ExeDepsFix::ID = 0;
174 /// Translate TRI register number to an index into our smaller tables of
175 /// interesting registers. Return -1 for boring registers.
176 int ExeDepsFix::regIndex(unsigned Reg) {
177 assert(Reg < AliasMap.size() && "Invalid register");
178 return AliasMap[Reg];
181 DomainValue *ExeDepsFix::alloc(int domain) {
182 DomainValue *dv = Avail.empty() ?
183 new(Allocator.Allocate()) DomainValue :
184 Avail.pop_back_val();
187 dv->addDomain(domain);
188 assert(dv->Refs == 0 && "Reference count wasn't cleared");
189 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
193 /// release - Release a reference to DV. When the last reference is released,
194 /// collapse if needed.
195 void ExeDepsFix::release(DomainValue *DV) {
197 assert(DV->Refs && "Bad DomainValue");
201 // There are no more DV references. Collapse any contained instructions.
202 if (DV->AvailableDomains && !DV->isCollapsed())
203 collapse(DV, DV->getFirstDomain());
205 DomainValue *Next = DV->Next;
208 // Also release the next DomainValue in the chain.
213 /// resolve - Follow the chain of dead DomainValues until a live DomainValue is
214 /// reached. Update the referenced pointer when necessary.
215 DomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) {
216 DomainValue *DV = DVRef;
217 if (!DV || !DV->Next)
220 // DV has a chain. Find the end.
224 // Update DVRef to point to DV.
231 /// Set LiveRegs[rx] = dv, updating reference counts.
232 void ExeDepsFix::setLiveReg(int rx, DomainValue *dv) {
233 assert(unsigned(rx) < NumRegs && "Invalid index");
235 LiveRegs = new DomainValue*[NumRegs];
236 std::fill(LiveRegs, LiveRegs+NumRegs, (DomainValue*)0);
239 if (LiveRegs[rx] == dv)
242 release(LiveRegs[rx]);
243 LiveRegs[rx] = retain(dv);
246 // Kill register rx, recycle or collapse any DomainValue.
247 void ExeDepsFix::kill(int rx) {
248 assert(unsigned(rx) < NumRegs && "Invalid index");
249 if (!LiveRegs || !LiveRegs[rx]) return;
251 release(LiveRegs[rx]);
255 /// Force register rx into domain.
256 void ExeDepsFix::force(int rx, unsigned domain) {
257 assert(unsigned(rx) < NumRegs && "Invalid index");
259 if (LiveRegs && (dv = LiveRegs[rx])) {
260 if (dv->isCollapsed())
261 dv->addDomain(domain);
262 else if (dv->hasDomain(domain))
263 collapse(dv, domain);
265 // This is an incompatible open DomainValue. Collapse it to whatever and
266 // force the new value into domain. This costs a domain crossing.
267 collapse(dv, dv->getFirstDomain());
268 assert(LiveRegs[rx] && "Not live after collapse?");
269 LiveRegs[rx]->addDomain(domain);
272 // Set up basic collapsed DomainValue.
273 setLiveReg(rx, alloc(domain));
277 /// Collapse open DomainValue into given domain. If there are multiple
278 /// registers using dv, they each get a unique collapsed DomainValue.
279 void ExeDepsFix::collapse(DomainValue *dv, unsigned domain) {
280 assert(dv->hasDomain(domain) && "Cannot collapse");
282 // Collapse all the instructions.
283 while (!dv->Instrs.empty())
284 TII->setExecutionDomain(dv->Instrs.pop_back_val(), domain);
285 dv->setSingleDomain(domain);
287 // If there are multiple users, give them new, unique DomainValues.
288 if (LiveRegs && dv->Refs > 1)
289 for (unsigned rx = 0; rx != NumRegs; ++rx)
290 if (LiveRegs[rx] == dv)
291 setLiveReg(rx, alloc(domain));
294 /// Merge - All instructions and registers in B are moved to A, and B is
296 bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) {
297 assert(!A->isCollapsed() && "Cannot merge into collapsed");
298 assert(!B->isCollapsed() && "Cannot merge from collapsed");
301 // Restrict to the domains that A and B have in common.
302 unsigned common = A->getCommonDomains(B->AvailableDomains);
305 A->AvailableDomains = common;
306 A->Dist = std::max(A->Dist, B->Dist);
307 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
309 // Clear the old DomainValue so we won't try to swizzle instructions twice.
311 // All uses of B are referred to A.
314 for (unsigned rx = 0; rx != NumRegs; ++rx)
315 if (LiveRegs[rx] == B)
320 void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
321 // Try to coalesce live-out registers from predecessors.
322 for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(),
323 e = MBB->livein_end(); i != e; ++i) {
324 int rx = regIndex(*i);
325 if (rx < 0) continue;
326 for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
327 pe = MBB->pred_end(); pi != pe; ++pi) {
328 LiveOutMap::const_iterator fi = LiveOuts.find(*pi);
329 if (fi == LiveOuts.end()) continue;
330 DomainValue *pdv = resolve(fi->second[rx]);
332 if (!LiveRegs || !LiveRegs[rx]) {
337 // We have a live DomainValue from more than one predecessor.
338 if (LiveRegs[rx]->isCollapsed()) {
339 // We are already collapsed, but predecessor is not. Force him.
340 unsigned domain = LiveRegs[rx]->getFirstDomain();
341 if (!pdv->isCollapsed() && pdv->hasDomain(domain))
342 collapse(pdv, domain);
346 // Currently open, merge in predecessor.
347 if (!pdv->isCollapsed())
348 merge(LiveRegs[rx], pdv);
350 force(rx, pdv->getFirstDomain());
355 void ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
356 // Save live registers at end of MBB - used by enterBasicBlock().
358 LiveOuts.insert(std::make_pair(MBB, LiveRegs));
362 void ExeDepsFix::visitInstr(MachineInstr *MI) {
363 if (MI->isDebugValue())
366 std::pair<uint16_t, uint16_t> domp = TII->getExecutionDomain(MI);
369 visitSoftInstr(MI, domp.second);
371 visitHardInstr(MI, domp.first);
373 visitGenericInstr(MI);
376 // A hard instruction only works in one domain. All input registers will be
377 // forced into that domain.
378 void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
379 // Collapse all uses.
380 for (unsigned i = mi->getDesc().getNumDefs(),
381 e = mi->getDesc().getNumOperands(); i != e; ++i) {
382 MachineOperand &mo = mi->getOperand(i);
383 if (!mo.isReg()) continue;
384 int rx = regIndex(mo.getReg());
385 if (rx < 0) continue;
389 // Kill all defs and force them.
390 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
391 MachineOperand &mo = mi->getOperand(i);
392 if (!mo.isReg()) continue;
393 int rx = regIndex(mo.getReg());
394 if (rx < 0) continue;
400 // A soft instruction can be changed to work in other domains given by mask.
401 void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
402 // Bitmask of available domains for this instruction after taking collapsed
403 // operands into account.
404 unsigned available = mask;
406 // Scan the explicit use operands for incoming domains.
407 SmallVector<int, 4> used;
409 for (unsigned i = mi->getDesc().getNumDefs(),
410 e = mi->getDesc().getNumOperands(); i != e; ++i) {
411 MachineOperand &mo = mi->getOperand(i);
412 if (!mo.isReg()) continue;
413 int rx = regIndex(mo.getReg());
414 if (rx < 0) continue;
415 if (DomainValue *dv = LiveRegs[rx]) {
416 // Bitmask of domains that dv and available have in common.
417 unsigned common = dv->getCommonDomains(available);
418 // Is it possible to use this collapsed register for free?
419 if (dv->isCollapsed()) {
420 // Restrict available domains to the ones in common with the operand.
421 // If there are no common domains, we must pay the cross-domain
422 // penalty for this operand.
423 if (common) available = common;
425 // Open DomainValue is compatible, save it for merging.
428 // Open DomainValue is not compatible with instruction. It is useless
434 // If the collapsed operands force a single domain, propagate the collapse.
435 if (isPowerOf2_32(available)) {
436 unsigned domain = CountTrailingZeros_32(available);
437 TII->setExecutionDomain(mi, domain);
438 visitHardInstr(mi, domain);
442 // Kill off any remaining uses that don't match available, and build a list of
443 // incoming DomainValues that we want to merge.
444 SmallVector<DomainValue*,4> doms;
445 for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
447 DomainValue *dv = LiveRegs[rx];
448 // This useless DomainValue could have been missed above.
449 if (!dv->getCommonDomains(available)) {
453 // sorted, uniqued insert.
454 bool inserted = false;
455 for (SmallVector<DomainValue*,4>::iterator i = doms.begin(), e = doms.end();
456 i != e && !inserted; ++i) {
459 else if (dv->Dist < (*i)->Dist) {
468 // doms are now sorted in order of appearance. Try to merge them all, giving
469 // priority to the latest ones.
471 while (!doms.empty()) {
473 dv = doms.pop_back_val();
477 DomainValue *latest = doms.pop_back_val();
478 if (merge(dv, latest)) continue;
480 // If latest didn't merge, it is useless now. Kill all registers using it.
481 for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i)
482 if (LiveRegs[*i] == latest)
486 // dv is the DomainValue we are going to use for this instruction.
490 dv->AvailableDomains = available;
491 dv->Instrs.push_back(mi);
493 // Finally set all defs and non-collapsed uses to dv.
494 for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) {
495 MachineOperand &mo = mi->getOperand(i);
496 if (!mo.isReg()) continue;
497 int rx = regIndex(mo.getReg());
498 if (rx < 0) continue;
499 if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) {
506 void ExeDepsFix::visitGenericInstr(MachineInstr *mi) {
507 // Process explicit defs, kill any relevant registers redefined.
508 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
509 MachineOperand &mo = mi->getOperand(i);
510 if (!mo.isReg()) continue;
511 int rx = regIndex(mo.getReg());
512 if (rx < 0) continue;
517 bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) {
519 TII = MF->getTarget().getInstrInfo();
520 TRI = MF->getTarget().getRegisterInfo();
523 assert(NumRegs == RC->getNumRegs() && "Bad regclass");
525 // If no relevant registers are used in the function, we can skip it
527 bool anyregs = false;
528 for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end();
530 if (MF->getRegInfo().isPhysRegUsed(*I)) {
534 if (!anyregs) return false;
536 // Initialize the AliasMap on the first use.
537 if (AliasMap.empty()) {
538 // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC,
540 AliasMap.resize(TRI->getNumRegs(), -1);
541 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
542 for (const unsigned *AI = TRI->getOverlaps(RC->getRegister(i)); *AI; ++AI)
546 MachineBasicBlock *Entry = MF->begin();
547 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
548 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
549 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
550 MachineBasicBlock *MBB = *MBBI;
551 enterBasicBlock(MBB);
552 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
555 leaveBasicBlock(MBB);
558 // Clear the LiveOuts vectors and collapse any remaining DomainValues.
559 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
560 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
561 LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI);
562 if (FI == LiveOuts.end())
564 assert(FI->second && "Null entry");
565 for (unsigned i = 0, e = NumRegs; i != e; ++i)
567 release(FI->second[i]);
572 Allocator.DestroyAll();
578 llvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) {
579 return new ExeDepsFix(RC);