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 bool 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 // enterBasicBlock - Set up LiveRegs by merging predecessor live-out values.
321 // Return true if some predecessor hasn't been processed yet (like on a loop
323 bool ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
324 // Detect back-edges from predecessors we haven't processed yet.
325 bool seenBackEdge = false;
327 // Try to coalesce live-out registers from predecessors.
328 for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(),
329 e = MBB->livein_end(); i != e; ++i) {
330 int rx = regIndex(*i);
331 if (rx < 0) continue;
332 for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
333 pe = MBB->pred_end(); pi != pe; ++pi) {
334 LiveOutMap::const_iterator fi = LiveOuts.find(*pi);
335 if (fi == LiveOuts.end()) {
341 DomainValue *pdv = resolve(fi->second[rx]);
343 if (!LiveRegs || !LiveRegs[rx]) {
348 // We have a live DomainValue from more than one predecessor.
349 if (LiveRegs[rx]->isCollapsed()) {
350 // We are already collapsed, but predecessor is not. Force him.
351 unsigned domain = LiveRegs[rx]->getFirstDomain();
352 if (!pdv->isCollapsed() && pdv->hasDomain(domain))
353 collapse(pdv, domain);
357 // Currently open, merge in predecessor.
358 if (!pdv->isCollapsed())
359 merge(LiveRegs[rx], pdv);
361 force(rx, pdv->getFirstDomain());
367 void ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
368 // Save live registers at end of MBB - used by enterBasicBlock().
369 // Also use LiveOuts as a visited set to detect back-edges.
370 if (!LiveOuts.insert(std::make_pair(MBB, LiveRegs)).second && LiveRegs) {
371 // Insertion failed, this must be the second pass.
372 // Release all the DomainValues instead of keeping them.
373 for (unsigned i = 0, e = NumRegs; i != e; ++i)
374 release(LiveRegs[i]);
380 void ExeDepsFix::visitInstr(MachineInstr *MI) {
381 if (MI->isDebugValue())
384 std::pair<uint16_t, uint16_t> domp = TII->getExecutionDomain(MI);
387 visitSoftInstr(MI, domp.second);
389 visitHardInstr(MI, domp.first);
391 visitGenericInstr(MI);
394 // A hard instruction only works in one domain. All input registers will be
395 // forced into that domain.
396 void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
397 // Collapse all uses.
398 for (unsigned i = mi->getDesc().getNumDefs(),
399 e = mi->getDesc().getNumOperands(); i != e; ++i) {
400 MachineOperand &mo = mi->getOperand(i);
401 if (!mo.isReg()) continue;
402 int rx = regIndex(mo.getReg());
403 if (rx < 0) continue;
407 // Kill all defs and force them.
408 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
409 MachineOperand &mo = mi->getOperand(i);
410 if (!mo.isReg()) continue;
411 int rx = regIndex(mo.getReg());
412 if (rx < 0) continue;
418 // A soft instruction can be changed to work in other domains given by mask.
419 void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
420 // Bitmask of available domains for this instruction after taking collapsed
421 // operands into account.
422 unsigned available = mask;
424 // Scan the explicit use operands for incoming domains.
425 SmallVector<int, 4> used;
427 for (unsigned i = mi->getDesc().getNumDefs(),
428 e = mi->getDesc().getNumOperands(); i != e; ++i) {
429 MachineOperand &mo = mi->getOperand(i);
430 if (!mo.isReg()) continue;
431 int rx = regIndex(mo.getReg());
432 if (rx < 0) continue;
433 if (DomainValue *dv = LiveRegs[rx]) {
434 // Bitmask of domains that dv and available have in common.
435 unsigned common = dv->getCommonDomains(available);
436 // Is it possible to use this collapsed register for free?
437 if (dv->isCollapsed()) {
438 // Restrict available domains to the ones in common with the operand.
439 // If there are no common domains, we must pay the cross-domain
440 // penalty for this operand.
441 if (common) available = common;
443 // Open DomainValue is compatible, save it for merging.
446 // Open DomainValue is not compatible with instruction. It is useless
452 // If the collapsed operands force a single domain, propagate the collapse.
453 if (isPowerOf2_32(available)) {
454 unsigned domain = CountTrailingZeros_32(available);
455 TII->setExecutionDomain(mi, domain);
456 visitHardInstr(mi, domain);
460 // Kill off any remaining uses that don't match available, and build a list of
461 // incoming DomainValues that we want to merge.
462 SmallVector<DomainValue*,4> doms;
463 for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
465 DomainValue *dv = LiveRegs[rx];
466 // This useless DomainValue could have been missed above.
467 if (!dv->getCommonDomains(available)) {
471 // sorted, uniqued insert.
472 bool inserted = false;
473 for (SmallVector<DomainValue*,4>::iterator i = doms.begin(), e = doms.end();
474 i != e && !inserted; ++i) {
477 else if (dv->Dist < (*i)->Dist) {
486 // doms are now sorted in order of appearance. Try to merge them all, giving
487 // priority to the latest ones.
489 while (!doms.empty()) {
491 dv = doms.pop_back_val();
495 DomainValue *latest = doms.pop_back_val();
496 if (merge(dv, latest)) continue;
498 // If latest didn't merge, it is useless now. Kill all registers using it.
499 for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i)
500 if (LiveRegs[*i] == latest)
504 // dv is the DomainValue we are going to use for this instruction.
508 dv->AvailableDomains = available;
509 dv->Instrs.push_back(mi);
511 // Finally set all defs and non-collapsed uses to dv.
512 for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) {
513 MachineOperand &mo = mi->getOperand(i);
514 if (!mo.isReg()) continue;
515 int rx = regIndex(mo.getReg());
516 if (rx < 0) continue;
517 if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) {
524 void ExeDepsFix::visitGenericInstr(MachineInstr *mi) {
525 // Process explicit defs, kill any relevant registers redefined.
526 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
527 MachineOperand &mo = mi->getOperand(i);
528 if (!mo.isReg()) continue;
529 int rx = regIndex(mo.getReg());
530 if (rx < 0) continue;
535 bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) {
537 TII = MF->getTarget().getInstrInfo();
538 TRI = MF->getTarget().getRegisterInfo();
541 assert(NumRegs == RC->getNumRegs() && "Bad regclass");
543 // If no relevant registers are used in the function, we can skip it
545 bool anyregs = false;
546 for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end();
548 if (MF->getRegInfo().isPhysRegUsed(*I)) {
552 if (!anyregs) return false;
554 // Initialize the AliasMap on the first use.
555 if (AliasMap.empty()) {
556 // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC,
558 AliasMap.resize(TRI->getNumRegs(), -1);
559 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
560 for (const unsigned *AI = TRI->getOverlaps(RC->getRegister(i)); *AI; ++AI)
564 MachineBasicBlock *Entry = MF->begin();
565 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
566 SmallVector<MachineBasicBlock*, 16> Loops;
567 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
568 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
569 MachineBasicBlock *MBB = *MBBI;
570 if (enterBasicBlock(MBB))
571 Loops.push_back(MBB);
572 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
575 leaveBasicBlock(MBB);
578 // Visit all the loop blocks again in order to merge DomainValues from
580 for (unsigned i = 0, e = Loops.size(); i != e; ++i) {
581 MachineBasicBlock *MBB = Loops[i];
582 enterBasicBlock(MBB);
583 leaveBasicBlock(MBB);
586 // Clear the LiveOuts vectors and collapse any remaining DomainValues.
587 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
588 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
589 LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI);
590 if (FI == LiveOuts.end() || !FI->second)
592 for (unsigned i = 0, e = NumRegs; i != e; ++i)
594 release(FI->second[i]);
599 Allocator.DestroyAll();
605 llvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) {
606 return new ExeDepsFix(RC);