lib/Target/X86/SSEDomainFix.cpp

   1 //===- SSEDomainFix.cpp - Use proper int/float domain for SSE ---*- 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 // This file contains the SSEDomainFix pass.
  11 //
  12 // Some 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.
  16 //
  17 // This pass changes the variant instructions to minimize domain crossings.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "sse-domain-fix"
  22 #include "X86InstrInfo.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/ADT/DepthFirstIterator.h"
  26 #include "llvm/Support/Allocator.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 using namespace llvm;
  30
  31 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
  32 /// of execution domains.
  33 ///
  34 /// An open DomainValue represents a set of instructions that can still switch
  35 /// execution domain. Multiple registers may refer to the same open
  36 /// DomainValue - they will eventually be collapsed to the same execution
  37 /// domain.
  38 ///
  39 /// A collapsed DomainValue represents a single register that has been forced
  40 /// into one of more execution domains. There is a separate collapsed
  41 /// DomainValue for each register, but it may contain multiple execution
  42 /// domains. A register value is initially created in a single execution
  43 /// domain, but if we were forced to pay the penalty of a domain crossing, we
  44 /// keep track of the fact the the register is now available in multiple
  45 /// domains.
  46 namespace {
  47 struct DomainValue {
  48   // Basic reference counting.
  49   unsigned Refs;
  50
  51   // Available domains. For an open DomainValue, it is the still possible
  52   // domains for collapsing. For a collapsed DomainValue it is the domains where
  53   // the register is available for free.
  54   unsigned Mask;
  55
  56   // Position of the last defining instruction.
  57   unsigned Dist;
  58
  59   // Twiddleable instructions using or defining these registers.
  60   SmallVector<MachineInstr*, 8> Instrs;
  61
  62   // Collapsed DomainValue have no instructions to twiddle - it simply keeps
  63   // track of the domains where the registers are already available.
  64   bool collapsed() const { return Instrs.empty(); }
  65
  66   // Is any domain in mask available?
  67   bool compat(unsigned mask) const {
  68     return Mask & mask;
  69   }
  70
  71   // Mark domain as available.
  72   void add(unsigned domain) {
  73     Mask |= 1u << domain;
  74   }
  75
  76   // First domain available in mask.
  77   unsigned firstDomain() const {
  78     return CountTrailingZeros_32(Mask);
  79   }
  80
  81   DomainValue() { clear(); }
  82
  83   void clear() {
  84     Refs = Mask = Dist = 0;
  85     Instrs.clear();
  86   }
  87 };
  88 }
  89
  90 static const unsigned NumRegs = 16;
  91
  92 namespace {
  93 class SSEDomainFixPass : public MachineFunctionPass {
  94   static char ID;
  95   SpecificBumpPtrAllocator<DomainValue> Allocator;
  96   SmallVector<DomainValue*,16> Avail;
  97
  98   MachineFunction *MF;
  99   const X86InstrInfo *TII;
 100   const TargetRegisterInfo *TRI;
 101   MachineBasicBlock *MBB;
 102   DomainValue **LiveRegs;
 103   typedef DenseMap<MachineBasicBlock*,DomainValue**> LiveOutMap;
 104   LiveOutMap LiveOuts;
 105   unsigned Distance;
 106
 107 public:
 108   SSEDomainFixPass() : MachineFunctionPass(&ID) {}
 109
 110   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 111     AU.setPreservesAll();
 112     MachineFunctionPass::getAnalysisUsage(AU);
 113   }
 114
 115   virtual bool runOnMachineFunction(MachineFunction &MF);
 116
 117   virtual const char *getPassName() const {
 118     return "SSE execution domain fixup";
 119   }
 120
 121 private:
 122   // Register mapping.
 123   int RegIndex(unsigned Reg);
 124
 125   // DomainValue allocation.
 126   DomainValue *Alloc(int domain = -1);
 127   void Recycle(DomainValue*);
 128
 129   // LiveRegs manipulations.
 130   void SetLiveReg(int rx, DomainValue *DV);
 131   void Kill(int rx);
 132   void Force(int rx, unsigned domain);
 133   void Collapse(DomainValue *dv, unsigned domain);
 134   bool Merge(DomainValue *A, DomainValue *B);
 135
 136   void enterBasicBlock();
 137   void visitGenericInstr(MachineInstr*);
 138   void visitSoftInstr(MachineInstr*, unsigned mask);
 139   void visitHardInstr(MachineInstr*, unsigned domain);
 140 };
 141 }
 142
 143 char SSEDomainFixPass::ID = 0;
 144
 145 /// Translate TRI register number to an index into our smaller tables of
 146 /// interesting registers. Return -1 for boring registers.
 147 int SSEDomainFixPass::RegIndex(unsigned reg) {
 148   // Registers are sorted lexicographically.
 149   // We just need them to be consecutive, ordering doesn't matter.
 150   assert(X86::XMM9 == X86::XMM0+NumRegs-1 && "Unexpected sort");
 151   reg -= X86::XMM0;
 152   return reg < NumRegs ? reg : -1;
 153 }
 154
 155 DomainValue *SSEDomainFixPass::Alloc(int domain) {
 156   DomainValue *dv = Avail.empty() ?
 157                       new(Allocator.Allocate()) DomainValue :
 158                       Avail.pop_back_val();
 159   dv->Dist = Distance;
 160   if (domain >= 0)
 161     dv->Mask = 1u << domain;
 162   return dv;
 163 }
 164
 165 void SSEDomainFixPass::Recycle(DomainValue *dv) {
 166   assert(dv && "Cannot recycle NULL");
 167   dv->clear();
 168   Avail.push_back(dv);
 169 }
 170
 171 /// Set LiveRegs[rx] = dv, updating reference counts.
 172 void SSEDomainFixPass::SetLiveReg(int rx, DomainValue *dv) {
 173   assert(unsigned(rx) < NumRegs && "Invalid index");
 174   if (!LiveRegs)
 175     LiveRegs = (DomainValue**)calloc(sizeof(DomainValue*), NumRegs);
 176
 177   if (LiveRegs[rx] == dv)
 178     return;
 179   if (LiveRegs[rx]) {
 180     assert(LiveRegs[rx]->Refs && "Bad refcount");
 181     if (--LiveRegs[rx]->Refs == 0) Recycle(LiveRegs[rx]);
 182   }
 183   LiveRegs[rx] = dv;
 184   if (dv) ++dv->Refs;
 185 }
 186
 187 // Kill register rx, recycle or collapse any DomainValue.
 188 void SSEDomainFixPass::Kill(int rx) {
 189   assert(unsigned(rx) < NumRegs && "Invalid index");
 190   if (!LiveRegs || !LiveRegs[rx]) return;
 191
 192   // Before killing the last reference to an open DomainValue, collapse it to
 193   // the first available domain.
 194   if (LiveRegs[rx]->Refs == 1 && !LiveRegs[rx]->collapsed())
 195     Collapse(LiveRegs[rx], LiveRegs[rx]->firstDomain());
 196   else
 197     SetLiveReg(rx, 0);
 198 }
 199
 200 /// Force register rx into domain.
 201 void SSEDomainFixPass::Force(int rx, unsigned domain) {
 202   assert(unsigned(rx) < NumRegs && "Invalid index");
 203   DomainValue *dv;
 204   if (LiveRegs && (dv = LiveRegs[rx])) {
 205     if (dv->collapsed())
 206       dv->add(domain);
 207     else
 208       Collapse(dv, domain);
 209   } else {
 210     // Set up basic collapsed DomainValue.
 211     SetLiveReg(rx, Alloc(domain));
 212   }
 213 }
 214
 215 /// Collapse open DomainValue into given domain. If there are multiple
 216 /// registers using dv, they each get a unique collapsed DomainValue.
 217 void SSEDomainFixPass::Collapse(DomainValue *dv, unsigned domain) {
 218   assert(dv->compat(1u << domain) && "Cannot collapse");
 219
 220   // Collapse all the instructions.
 221   while (!dv->Instrs.empty()) {
 222     MachineInstr *mi = dv->Instrs.back();
 223     TII->SetSSEDomain(mi, domain);
 224     dv->Instrs.pop_back();
 225   }
 226   dv->Mask = 1u << domain;
 227
 228   // If there are multiple users, give them new, unique DomainValues.
 229   if (LiveRegs && dv->Refs > 1)
 230     for (unsigned rx = 0; rx != NumRegs; ++rx)
 231       if (LiveRegs[rx] == dv)
 232         SetLiveReg(rx, Alloc(domain));
 233 }
 234
 235 /// Merge - All instructions and registers in B are moved to A, and B is
 236 /// released.
 237 bool SSEDomainFixPass::Merge(DomainValue *A, DomainValue *B) {
 238   assert(!A->collapsed() && "Cannot merge into collapsed");
 239   assert(!B->collapsed() && "Cannot merge from collapsed");
 240   if (A == B)
 241     return true;
 242   if (!A->compat(B->Mask))
 243     return false;
 244   A->Mask &= B->Mask;
 245   A->Dist = std::max(A->Dist, B->Dist);
 246   A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
 247   for (unsigned rx = 0; rx != NumRegs; ++rx)
 248     if (LiveRegs[rx] == B)
 249       SetLiveReg(rx, A);
 250   return true;
 251 }
 252
 253 void SSEDomainFixPass::enterBasicBlock() {
 254   // Try to coalesce live-out registers from predecessors.
 255   for (MachineBasicBlock::const_livein_iterator i = MBB->livein_begin(),
 256          e = MBB->livein_end(); i != e; ++i) {
 257     int rx = RegIndex(*i);
 258     if (rx < 0) continue;
 259     for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
 260            pe = MBB->pred_end(); pi != pe; ++pi) {
 261       LiveOutMap::const_iterator fi = LiveOuts.find(*pi);
 262       if (fi == LiveOuts.end()) continue;
 263       DomainValue *pdv = fi->second[rx];
 264       if (!pdv) continue;
 265       if (!LiveRegs || !LiveRegs[rx]) {
 266         SetLiveReg(rx, pdv);
 267         continue;
 268       }
 269
 270       // We have a live DomainValue from more than one predecessor.
 271       if (LiveRegs[rx]->collapsed()) {
 272         // We are already collapsed, but predecessor is not. Force him.
 273         if (!pdv->collapsed())
 274           Collapse(pdv, LiveRegs[rx]->firstDomain());
 275         continue;
 276       }
 277
 278       // Currently open, merge in predecessor.
 279       if (!pdv->collapsed())
 280         Merge(LiveRegs[rx], pdv);
 281       else
 282         Collapse(LiveRegs[rx], pdv->firstDomain());
 283     }
 284   }
 285 }
 286
 287 // A hard instruction only works in one domain. All input registers will be
 288 // forced into that domain.
 289 void SSEDomainFixPass::visitHardInstr(MachineInstr *mi, unsigned domain) {
 290   // Collapse all uses.
 291   for (unsigned i = mi->getDesc().getNumDefs(),
 292                 e = mi->getDesc().getNumOperands(); i != e; ++i) {
 293     MachineOperand &mo = mi->getOperand(i);
 294     if (!mo.isReg()) continue;
 295     int rx = RegIndex(mo.getReg());
 296     if (rx < 0) continue;
 297     Force(rx, domain);
 298   }
 299
 300   // Kill all defs and force them.
 301   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
 302     MachineOperand &mo = mi->getOperand(i);
 303     if (!mo.isReg()) continue;
 304     int rx = RegIndex(mo.getReg());
 305     if (rx < 0) continue;
 306     Kill(rx);
 307     Force(rx, domain);
 308   }
 309 }
 310
 311 // A soft instruction can be changed to work in other domains given by mask.
 312 void SSEDomainFixPass::visitSoftInstr(MachineInstr *mi, unsigned mask) {
 313   // Scan the explicit use operands for incoming domains.
 314   unsigned collmask = mask;
 315   SmallVector<int, 4> used;
 316   if (LiveRegs)
 317     for (unsigned i = mi->getDesc().getNumDefs(),
 318                   e = mi->getDesc().getNumOperands(); i != e; ++i) {
 319       MachineOperand &mo = mi->getOperand(i);
 320       if (!mo.isReg()) continue;
 321       int rx = RegIndex(mo.getReg());
 322       if (rx < 0) continue;
 323       if (DomainValue *dv = LiveRegs[rx]) {
 324         // Is it possible to use this collapsed register for free?
 325         if (dv->collapsed()) {
 326           if (unsigned m = collmask & dv->Mask)
 327             collmask = m;
 328         } else if (dv->compat(collmask))
 329           used.push_back(rx);
 330         else
 331           Kill(rx);
 332       }
 333     }
 334
 335   // If the collapsed operands force a single domain, propagate the collapse.
 336   if (isPowerOf2_32(collmask)) {
 337     unsigned domain = CountTrailingZeros_32(collmask);
 338     TII->SetSSEDomain(mi, domain);
 339     visitHardInstr(mi, domain);
 340     return;
 341   }
 342
 343   // Kill off any remaining uses that don't match collmask, and build a list of
 344   // incoming DomainValue that we want to merge.
 345   SmallVector<DomainValue*,4> doms;
 346   for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
 347     int rx = *i;
 348     DomainValue *dv = LiveRegs[rx];
 349     // This useless DomainValue could have been missed above.
 350     if (!dv->compat(collmask)) {
 351       Kill(*i);
 352       continue;
 353     }
 354     // sorted, uniqued insert.
 355     bool inserted = false;
 356     for (SmallVector<DomainValue*,4>::iterator i = doms.begin(), e = doms.end();
 357            i != e && !inserted; ++i) {
 358       if (dv == *i)
 359         inserted = true;
 360       else if (dv->Dist < (*i)->Dist) {
 361         inserted = true;
 362         doms.insert(i, dv);
 363       }
 364     }
 365     if (!inserted)
 366       doms.push_back(dv);
 367   }
 368
 369   //  doms are now sorted in order of appearance. Try to merge them all, giving
 370   //  priority to the latest ones.
 371   DomainValue *dv = 0;
 372   while (!doms.empty()) {
 373     if (!dv) {
 374       dv = doms.pop_back_val();
 375       continue;
 376     }
 377
 378     DomainValue *ThisDV = doms.pop_back_val();
 379     if (Merge(dv, ThisDV)) continue;
 380
 381     for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i)
 382       if (LiveRegs[*i] == ThisDV)
 383         Kill(*i);
 384   }
 385
 386   // dv is the DomainValue we are going to use for this instruction.
 387   if (!dv)
 388     dv = Alloc();
 389   dv->Dist = Distance;
 390   dv->Mask = collmask;
 391   dv->Instrs.push_back(mi);
 392
 393   // Finally set all defs and non-collapsed uses to dv.
 394   for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) {
 395     MachineOperand &mo = mi->getOperand(i);
 396     if (!mo.isReg()) continue;
 397     int rx = RegIndex(mo.getReg());
 398     if (rx < 0) continue;
 399     if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) {
 400       Kill(rx);
 401       SetLiveReg(rx, dv);
 402     }
 403   }
 404 }
 405
 406 void SSEDomainFixPass::visitGenericInstr(MachineInstr *mi) {
 407   // Process explicit defs, kill any XMM registers redefined.
 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;
 413     Kill(rx);
 414   }
 415 }
 416
 417 bool SSEDomainFixPass::runOnMachineFunction(MachineFunction &mf) {
 418   MF = &mf;
 419   TII = static_cast<const X86InstrInfo*>(MF->getTarget().getInstrInfo());
 420   TRI = MF->getTarget().getRegisterInfo();
 421   MBB = 0;
 422   LiveRegs = 0;
 423   Distance = 0;
 424   assert(NumRegs == X86::VR128RegClass.getNumRegs() && "Bad regclass");
 425
 426   // If no XMM registers are used in the function, we can skip it completely.
 427   bool anyregs = false;
 428   for (TargetRegisterClass::const_iterator I = X86::VR128RegClass.begin(),
 429          E = X86::VR128RegClass.end(); I != E; ++I)
 430     if (MF->getRegInfo().isPhysRegUsed(*I)) {
 431       anyregs = true;
 432       break;
 433     }
 434   if (!anyregs) return false;
 435
 436   MachineBasicBlock *Entry = MF->begin();
 437   SmallPtrSet<MachineBasicBlock*, 16> Visited;
 438   for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*, 16> >
 439          DFI = df_ext_begin(Entry, Visited), DFE = df_ext_end(Entry, Visited);
 440          DFI != DFE; ++DFI) {
 441     MBB = *DFI;
 442     enterBasicBlock();
 443     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
 444         ++I) {
 445       MachineInstr *mi = I;
 446       if (mi->isDebugValue()) continue;
 447       ++Distance;
 448       std::pair<uint16_t, uint16_t> domp = TII->GetSSEDomain(mi);
 449       if (domp.first)
 450         if (domp.second)
 451           visitSoftInstr(mi, domp.second);
 452         else
 453           visitHardInstr(mi, domp.first);
 454       else if (LiveRegs)
 455         visitGenericInstr(mi);
 456     }
 457
 458     // Save live registers at end of MBB - used by enterBasicBlock().
 459     if (LiveRegs)
 460       LiveOuts.insert(std::make_pair(MBB, LiveRegs));
 461     LiveRegs = 0;
 462   }
 463
 464   // Clear the LiveOuts vectors. Should we also collapse any remaining
 465   // DomainValues?
 466   for (LiveOutMap::const_iterator i = LiveOuts.begin(), e = LiveOuts.end();
 467          i != e; ++i)
 468     free(i->second);
 469   LiveOuts.clear();
 470   Avail.clear();
 471   Allocator.DestroyAll();
 472
 473   return false;
 474 }
 475
 476 FunctionPass *llvm::createSSEDomainFixPass() {
 477   return new SSEDomainFixPass();
 478 }