lib/CodeGen/ExecutionDepsFix.cpp

   1 //===- ExecutionDepsFix.cpp - Fix execution dependecy 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 // This file contains the execution dependency fix pass.
  11 //
  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
  17 // pipelines.
  18 //
  19 // This pass changes the variant instructions to minimize domain crossings.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #define DEBUG_TYPE "execution-fix"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/ADT/PostOrderIterator.h"
  26 #include "llvm/CodeGen/LiveRegUnits.h"
  27 #include "llvm/CodeGen/MachineFunctionPass.h"
  28 #include "llvm/CodeGen/MachineRegisterInfo.h"
  29 #include "llvm/Support/Allocator.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include "llvm/Target/TargetInstrInfo.h"
  33 #include "llvm/Target/TargetMachine.h"
  34 using namespace llvm;
  35
  36 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
  37 /// of execution domains.
  38 ///
  39 /// An open DomainValue represents a set of instructions that can still switch
  40 /// execution domain. Multiple registers may refer to the same open
  41 /// DomainValue - they will eventually be collapsed to the same execution
  42 /// domain.
  43 ///
  44 /// A collapsed DomainValue represents a single register that has been forced
  45 /// into one of more execution domains. There is a separate collapsed
  46 /// DomainValue for each register, but it may contain multiple execution
  47 /// domains. A register value is initially created in a single execution
  48 /// domain, but if we were forced to pay the penalty of a domain crossing, we
  49 /// keep track of the fact that the register is now available in multiple
  50 /// domains.
  51 namespace {
  52 struct DomainValue {
  53   // Basic reference counting.
  54   unsigned Refs;
  55
  56   // Bitmask of available domains. For an open DomainValue, it is the still
  57   // possible domains for collapsing. For a collapsed DomainValue it is the
  58   // domains where the register is available for free.
  59   unsigned AvailableDomains;
  60
  61   // Pointer to the next DomainValue in a chain.  When two DomainValues are
  62   // merged, Victim.Next is set to point to Victor, so old DomainValue
  63   // references can be updated by following the chain.
  64   DomainValue *Next;
  65
  66   // Twiddleable instructions using or defining these registers.
  67   SmallVector<MachineInstr*, 8> Instrs;
  68
  69   // A collapsed DomainValue has no instructions to twiddle - it simply keeps
  70   // track of the domains where the registers are already available.
  71   bool isCollapsed() const { return Instrs.empty(); }
  72
  73   // Is domain available?
  74   bool hasDomain(unsigned domain) const {
  75     return AvailableDomains & (1u << domain);
  76   }
  77
  78   // Mark domain as available.
  79   void addDomain(unsigned domain) {
  80     AvailableDomains |= 1u << domain;
  81   }
  82
  83   // Restrict to a single domain available.
  84   void setSingleDomain(unsigned domain) {
  85     AvailableDomains = 1u << domain;
  86   }
  87
  88   // Return bitmask of domains that are available and in mask.
  89   unsigned getCommonDomains(unsigned mask) const {
  90     return AvailableDomains & mask;
  91   }
  92
  93   // First domain available.
  94   unsigned getFirstDomain() const {
  95     return countTrailingZeros(AvailableDomains);
  96   }
  97
  98   DomainValue() : Refs(0) { clear(); }
  99
 100   // Clear this DomainValue and point to next which has all its data.
 101   void clear() {
 102     AvailableDomains = 0;
 103     Next = 0;
 104     Instrs.clear();
 105   }
 106 };
 107 }
 108
 109 namespace {
 110 /// LiveReg - Information about a live register.
 111 struct LiveReg {
 112   /// Value currently in this register, or NULL when no value is being tracked.
 113   /// This counts as a DomainValue reference.
 114   DomainValue *Value;
 115
 116   /// Instruction that defined this register, relative to the beginning of the
 117   /// current basic block.  When a LiveReg is used to represent a live-out
 118   /// register, this value is relative to the end of the basic block, so it
 119   /// will be a negative number.
 120   int Def;
 121 };
 122 } // anonynous namespace
 123
 124 namespace {
 125 class ExeDepsFix : public MachineFunctionPass {
 126   static char ID;
 127   SpecificBumpPtrAllocator<DomainValue> Allocator;
 128   SmallVector<DomainValue*,16> Avail;
 129
 130   const TargetRegisterClass *const RC;
 131   MachineFunction *MF;
 132   const TargetInstrInfo *TII;
 133   const TargetRegisterInfo *TRI;
 134   std::vector<int> AliasMap;
 135   const unsigned NumRegs;
 136   LiveReg *LiveRegs;
 137   typedef DenseMap<MachineBasicBlock*, LiveReg*> LiveOutMap;
 138   LiveOutMap LiveOuts;
 139
 140   /// List of undefined register reads in this block in forward order.
 141   std::vector<std::pair<MachineInstr*, unsigned> > UndefReads;
 142
 143   /// Storage for register unit liveness.
 144   LiveRegUnits LiveUnits;
 145
 146   /// Current instruction number.
 147   /// The first instruction in each basic block is 0.
 148   int CurInstr;
 149
 150   /// True when the current block has a predecessor that hasn't been visited
 151   /// yet.
 152   bool SeenUnknownBackEdge;
 153
 154 public:
 155   ExeDepsFix(const TargetRegisterClass *rc)
 156     : MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {}
 157
 158   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 159     AU.setPreservesAll();
 160     MachineFunctionPass::getAnalysisUsage(AU);
 161   }
 162
 163   virtual bool runOnMachineFunction(MachineFunction &MF);
 164
 165   virtual const char *getPassName() const {
 166     return "Execution dependency fix";
 167   }
 168
 169 private:
 170   // Register mapping.
 171   int regIndex(unsigned Reg);
 172
 173   // DomainValue allocation.
 174   DomainValue *alloc(int domain = -1);
 175   DomainValue *retain(DomainValue *DV) {
 176     if (DV) ++DV->Refs;
 177     return DV;
 178   }
 179   void release(DomainValue*);
 180   DomainValue *resolve(DomainValue*&);
 181
 182   // LiveRegs manipulations.
 183   void setLiveReg(int rx, DomainValue *DV);
 184   void kill(int rx);
 185   void force(int rx, unsigned domain);
 186   void collapse(DomainValue *dv, unsigned domain);
 187   bool merge(DomainValue *A, DomainValue *B);
 188
 189   void enterBasicBlock(MachineBasicBlock*);
 190   void leaveBasicBlock(MachineBasicBlock*);
 191   void visitInstr(MachineInstr*);
 192   void processDefs(MachineInstr*, bool Kill);
 193   void visitSoftInstr(MachineInstr*, unsigned mask);
 194   void visitHardInstr(MachineInstr*, unsigned domain);
 195   bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref);
 196   void processUndefReads(MachineBasicBlock*);
 197 };
 198 }
 199
 200 char ExeDepsFix::ID = 0;
 201
 202 /// Translate TRI register number to an index into our smaller tables of
 203 /// interesting registers. Return -1 for boring registers.
 204 int ExeDepsFix::regIndex(unsigned Reg) {
 205   assert(Reg < AliasMap.size() && "Invalid register");
 206   return AliasMap[Reg];
 207 }
 208
 209 DomainValue *ExeDepsFix::alloc(int domain) {
 210   DomainValue *dv = Avail.empty() ?
 211                       new(Allocator.Allocate()) DomainValue :
 212                       Avail.pop_back_val();
 213   if (domain >= 0)
 214     dv->addDomain(domain);
 215   assert(dv->Refs == 0 && "Reference count wasn't cleared");
 216   assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
 217   return dv;
 218 }
 219
 220 /// release - Release a reference to DV.  When the last reference is released,
 221 /// collapse if needed.
 222 void ExeDepsFix::release(DomainValue *DV) {
 223   while (DV) {
 224     assert(DV->Refs && "Bad DomainValue");
 225     if (--DV->Refs)
 226       return;
 227
 228     // There are no more DV references. Collapse any contained instructions.
 229     if (DV->AvailableDomains && !DV->isCollapsed())
 230       collapse(DV, DV->getFirstDomain());
 231
 232     DomainValue *Next = DV->Next;
 233     DV->clear();
 234     Avail.push_back(DV);
 235     // Also release the next DomainValue in the chain.
 236     DV = Next;
 237   }
 238 }
 239
 240 /// resolve - Follow the chain of dead DomainValues until a live DomainValue is
 241 /// reached.  Update the referenced pointer when necessary.
 242 DomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) {
 243   DomainValue *DV = DVRef;
 244   if (!DV || !DV->Next)
 245     return DV;
 246
 247   // DV has a chain. Find the end.
 248   do DV = DV->Next;
 249   while (DV->Next);
 250
 251   // Update DVRef to point to DV.
 252   retain(DV);
 253   release(DVRef);
 254   DVRef = DV;
 255   return DV;
 256 }
 257
 258 /// Set LiveRegs[rx] = dv, updating reference counts.
 259 void ExeDepsFix::setLiveReg(int rx, DomainValue *dv) {
 260   assert(unsigned(rx) < NumRegs && "Invalid index");
 261   assert(LiveRegs && "Must enter basic block first.");
 262
 263   if (LiveRegs[rx].Value == dv)
 264     return;
 265   if (LiveRegs[rx].Value)
 266     release(LiveRegs[rx].Value);
 267   LiveRegs[rx].Value = retain(dv);
 268 }
 269
 270 // Kill register rx, recycle or collapse any DomainValue.
 271 void ExeDepsFix::kill(int rx) {
 272   assert(unsigned(rx) < NumRegs && "Invalid index");
 273   assert(LiveRegs && "Must enter basic block first.");
 274   if (!LiveRegs[rx].Value)
 275     return;
 276
 277   release(LiveRegs[rx].Value);
 278   LiveRegs[rx].Value = 0;
 279 }
 280
 281 /// Force register rx into domain.
 282 void ExeDepsFix::force(int rx, unsigned domain) {
 283   assert(unsigned(rx) < NumRegs && "Invalid index");
 284   assert(LiveRegs && "Must enter basic block first.");
 285   if (DomainValue *dv = LiveRegs[rx].Value) {
 286     if (dv->isCollapsed())
 287       dv->addDomain(domain);
 288     else if (dv->hasDomain(domain))
 289       collapse(dv, domain);
 290     else {
 291       // This is an incompatible open DomainValue. Collapse it to whatever and
 292       // force the new value into domain. This costs a domain crossing.
 293       collapse(dv, dv->getFirstDomain());
 294       assert(LiveRegs[rx].Value && "Not live after collapse?");
 295       LiveRegs[rx].Value->addDomain(domain);
 296     }
 297   } else {
 298     // Set up basic collapsed DomainValue.
 299     setLiveReg(rx, alloc(domain));
 300   }
 301 }
 302
 303 /// Collapse open DomainValue into given domain. If there are multiple
 304 /// registers using dv, they each get a unique collapsed DomainValue.
 305 void ExeDepsFix::collapse(DomainValue *dv, unsigned domain) {
 306   assert(dv->hasDomain(domain) && "Cannot collapse");
 307
 308   // Collapse all the instructions.
 309   while (!dv->Instrs.empty())
 310     TII->setExecutionDomain(dv->Instrs.pop_back_val(), domain);
 311   dv->setSingleDomain(domain);
 312
 313   // If there are multiple users, give them new, unique DomainValues.
 314   if (LiveRegs && dv->Refs > 1)
 315     for (unsigned rx = 0; rx != NumRegs; ++rx)
 316       if (LiveRegs[rx].Value == dv)
 317         setLiveReg(rx, alloc(domain));
 318 }
 319
 320 /// Merge - All instructions and registers in B are moved to A, and B is
 321 /// released.
 322 bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) {
 323   assert(!A->isCollapsed() && "Cannot merge into collapsed");
 324   assert(!B->isCollapsed() && "Cannot merge from collapsed");
 325   if (A == B)
 326     return true;
 327   // Restrict to the domains that A and B have in common.
 328   unsigned common = A->getCommonDomains(B->AvailableDomains);
 329   if (!common)
 330     return false;
 331   A->AvailableDomains = common;
 332   A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
 333
 334   // Clear the old DomainValue so we won't try to swizzle instructions twice.
 335   B->clear();
 336   // All uses of B are referred to A.
 337   B->Next = retain(A);
 338
 339   for (unsigned rx = 0; rx != NumRegs; ++rx)
 340     if (LiveRegs[rx].Value == B)
 341       setLiveReg(rx, A);
 342   return true;
 343 }
 344
 345 // enterBasicBlock - Set up LiveRegs by merging predecessor live-out values.
 346 void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
 347   // Detect back-edges from predecessors we haven't processed yet.
 348   SeenUnknownBackEdge = false;
 349
 350   // Reset instruction counter in each basic block.
 351   CurInstr = 0;
 352
 353   // Set up UndefReads to track undefined register reads.
 354   UndefReads.clear();
 355   LiveUnits.clear();
 356
 357   // Set up LiveRegs to represent registers entering MBB.
 358   if (!LiveRegs)
 359     LiveRegs = new LiveReg[NumRegs];
 360
 361   // Default values are 'nothing happened a long time ago'.
 362   for (unsigned rx = 0; rx != NumRegs; ++rx) {
 363     LiveRegs[rx].Value = 0;
 364     LiveRegs[rx].Def = -(1 << 20);
 365   }
 366
 367   // This is the entry block.
 368   if (MBB->pred_empty()) {
 369     for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(),
 370          e = MBB->livein_end(); i != e; ++i) {
 371       int rx = regIndex(*i);
 372       if (rx < 0)
 373         continue;
 374       // Treat function live-ins as if they were defined just before the first
 375       // instruction.  Usually, function arguments are set up immediately
 376       // before the call.
 377       LiveRegs[rx].Def = -1;
 378     }
 379     DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n");
 380     return;
 381   }
 382
 383   // Try to coalesce live-out registers from predecessors.
 384   for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
 385        pe = MBB->pred_end(); pi != pe; ++pi) {
 386     LiveOutMap::const_iterator fi = LiveOuts.find(*pi);
 387     if (fi == LiveOuts.end()) {
 388       SeenUnknownBackEdge = true;
 389       continue;
 390     }
 391     assert(fi->second && "Can't have NULL entries");
 392
 393     for (unsigned rx = 0; rx != NumRegs; ++rx) {
 394       // Use the most recent predecessor def for each register.
 395       LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, fi->second[rx].Def);
 396
 397       DomainValue *pdv = resolve(fi->second[rx].Value);
 398       if (!pdv)
 399         continue;
 400       if (!LiveRegs[rx].Value) {
 401         setLiveReg(rx, pdv);
 402         continue;
 403       }
 404
 405       // We have a live DomainValue from more than one predecessor.
 406       if (LiveRegs[rx].Value->isCollapsed()) {
 407         // We are already collapsed, but predecessor is not. Force him.
 408         unsigned Domain = LiveRegs[rx].Value->getFirstDomain();
 409         if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
 410           collapse(pdv, Domain);
 411         continue;
 412       }
 413
 414       // Currently open, merge in predecessor.
 415       if (!pdv->isCollapsed())
 416         merge(LiveRegs[rx].Value, pdv);
 417       else
 418         force(rx, pdv->getFirstDomain());
 419     }
 420   }
 421   DEBUG(dbgs() << "BB#" << MBB->getNumber()
 422         << (SeenUnknownBackEdge ? ": incomplete\n" : ": all preds known\n"));
 423 }
 424
 425 void ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
 426   assert(LiveRegs && "Must enter basic block first.");
 427   // Save live registers at end of MBB - used by enterBasicBlock().
 428   // Also use LiveOuts as a visited set to detect back-edges.
 429   bool First = LiveOuts.insert(std::make_pair(MBB, LiveRegs)).second;
 430
 431   if (First) {
 432     // LiveRegs was inserted in LiveOuts.  Adjust all defs to be relative to
 433     // the end of this block instead of the beginning.
 434     for (unsigned i = 0, e = NumRegs; i != e; ++i)
 435       LiveRegs[i].Def -= CurInstr;
 436   } else {
 437     // Insertion failed, this must be the second pass.
 438     // Release all the DomainValues instead of keeping them.
 439     for (unsigned i = 0, e = NumRegs; i != e; ++i)
 440       release(LiveRegs[i].Value);
 441     delete[] LiveRegs;
 442   }
 443   LiveRegs = 0;
 444 }
 445
 446 void ExeDepsFix::visitInstr(MachineInstr *MI) {
 447   if (MI->isDebugValue())
 448     return;
 449
 450   // Update instructions with explicit execution domains.
 451   std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(MI);
 452   if (DomP.first) {
 453     if (DomP.second)
 454       visitSoftInstr(MI, DomP.second);
 455     else
 456       visitHardInstr(MI, DomP.first);
 457   }
 458
 459   // Process defs to track register ages, and kill values clobbered by generic
 460   // instructions.
 461   processDefs(MI, !DomP.first);
 462 }
 463
 464 /// \brief Return true to if it makes sense to break dependence on a partial def
 465 /// or undef use.
 466 bool ExeDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
 467                                        unsigned Pref) {
 468   int rx = regIndex(MI->getOperand(OpIdx).getReg());
 469   if (rx < 0)
 470     return false;
 471
 472   unsigned Clearance = CurInstr - LiveRegs[rx].Def;
 473   DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
 474
 475   if (Pref > Clearance) {
 476     DEBUG(dbgs() << ": Break dependency.\n");
 477     return true;
 478   }
 479   // The current clearance seems OK, but we may be ignoring a def from a
 480   // back-edge.
 481   if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) {
 482     DEBUG(dbgs() << ": OK .\n");
 483     return false;
 484   }
 485   // A def from an unprocessed back-edge may make us break this dependency.
 486   DEBUG(dbgs() << ": Wait for back-edge to resolve.\n");
 487   return false;
 488 }
 489
 490 // Update def-ages for registers defined by MI.
 491 // If Kill is set, also kill off DomainValues clobbered by the defs.
 492 //
 493 // Also break dependencies on partial defs and undef uses.
 494 void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) {
 495   assert(!MI->isDebugValue() && "Won't process debug values");
 496
 497   // Break dependence on undef uses. Do this before updating LiveRegs below.
 498   unsigned OpNum;
 499   unsigned Pref = TII->getUndefRegClearance(MI, OpNum, TRI);
 500   if (Pref) {
 501     if (shouldBreakDependence(MI, OpNum, Pref))
 502       UndefReads.push_back(std::make_pair(MI, OpNum));
 503   }
 504   const MCInstrDesc &MCID = MI->getDesc();
 505   for (unsigned i = 0,
 506          e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
 507          i != e; ++i) {
 508     MachineOperand &MO = MI->getOperand(i);
 509     if (!MO.isReg())
 510       continue;
 511     if (MO.isImplicit())
 512       break;
 513     if (MO.isUse())
 514       continue;
 515     int rx = regIndex(MO.getReg());
 516     if (rx < 0)
 517       continue;
 518
 519     // This instruction explicitly defines rx.
 520     DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr
 521                  << '\t' << *MI);
 522
 523     // Check clearance before partial register updates.
 524     // Call breakDependence before setting LiveRegs[rx].Def.
 525     unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI);
 526     if (Pref && shouldBreakDependence(MI, i, Pref))
 527       TII->breakPartialRegDependency(MI, i, TRI);
 528
 529     // How many instructions since rx was last written?
 530     LiveRegs[rx].Def = CurInstr;
 531
 532     // Kill off domains redefined by generic instructions.
 533     if (Kill)
 534       kill(rx);
 535   }
 536   ++CurInstr;
 537 }
 538
 539 /// \break Break false dependencies on undefined register reads.
 540 ///
 541 /// Walk the block backward computing precise liveness. This is expensive, so we
 542 /// only do it on demand. Note that the occurrence of undefined register reads
 543 /// that should be broken is very rare, but when they occur we may have many in
 544 /// a single block.
 545 void ExeDepsFix::processUndefReads(MachineBasicBlock *MBB) {
 546   if (UndefReads.empty())
 547     return;
 548
 549   // Collect this block's live out register units.
 550   LiveUnits.init(TRI);
 551   for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
 552          SE = MBB->succ_end(); SI != SE; ++SI) {
 553     LiveUnits.addLiveIns(*SI, *TRI);
 554   }
 555   MachineInstr *UndefMI = UndefReads.back().first;
 556   unsigned OpIdx = UndefReads.back().second;
 557
 558   for (MachineBasicBlock::reverse_iterator I = MBB->rbegin(), E = MBB->rend();
 559        I != E; ++I) {
 560     // Update liveness, including the current instruction's defs.
 561     LiveUnits.stepBackward(*I, *TRI);
 562
 563     if (UndefMI == &*I) {
 564       if (!LiveUnits.contains(UndefMI->getOperand(OpIdx).getReg(), *TRI))
 565         TII->breakPartialRegDependency(UndefMI, OpIdx, TRI);
 566
 567       UndefReads.pop_back();
 568       if (UndefReads.empty())
 569         return;
 570
 571       UndefMI = UndefReads.back().first;
 572       OpIdx = UndefReads.back().second;
 573     }
 574   }
 575 }
 576
 577 // A hard instruction only works in one domain. All input registers will be
 578 // forced into that domain.
 579 void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
 580   // Collapse all uses.
 581   for (unsigned i = mi->getDesc().getNumDefs(),
 582                 e = mi->getDesc().getNumOperands(); i != e; ++i) {
 583     MachineOperand &mo = mi->getOperand(i);
 584     if (!mo.isReg()) continue;
 585     int rx = regIndex(mo.getReg());
 586     if (rx < 0) continue;
 587     force(rx, domain);
 588   }
 589
 590   // Kill all defs and force them.
 591   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
 592     MachineOperand &mo = mi->getOperand(i);
 593     if (!mo.isReg()) continue;
 594     int rx = regIndex(mo.getReg());
 595     if (rx < 0) continue;
 596     kill(rx);
 597     force(rx, domain);
 598   }
 599 }
 600
 601 // A soft instruction can be changed to work in other domains given by mask.
 602 void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
 603   // Bitmask of available domains for this instruction after taking collapsed
 604   // operands into account.
 605   unsigned available = mask;
 606
 607   // Scan the explicit use operands for incoming domains.
 608   SmallVector<int, 4> used;
 609   if (LiveRegs)
 610     for (unsigned i = mi->getDesc().getNumDefs(),
 611                   e = mi->getDesc().getNumOperands(); i != e; ++i) {
 612       MachineOperand &mo = mi->getOperand(i);
 613       if (!mo.isReg()) continue;
 614       int rx = regIndex(mo.getReg());
 615       if (rx < 0) continue;
 616       if (DomainValue *dv = LiveRegs[rx].Value) {
 617         // Bitmask of domains that dv and available have in common.
 618         unsigned common = dv->getCommonDomains(available);
 619         // Is it possible to use this collapsed register for free?
 620         if (dv->isCollapsed()) {
 621           // Restrict available domains to the ones in common with the operand.
 622           // If there are no common domains, we must pay the cross-domain
 623           // penalty for this operand.
 624           if (common) available = common;
 625         } else if (common)
 626           // Open DomainValue is compatible, save it for merging.
 627           used.push_back(rx);
 628         else
 629           // Open DomainValue is not compatible with instruction. It is useless
 630           // now.
 631           kill(rx);
 632       }
 633     }
 634
 635   // If the collapsed operands force a single domain, propagate the collapse.
 636   if (isPowerOf2_32(available)) {
 637     unsigned domain = countTrailingZeros(available);
 638     TII->setExecutionDomain(mi, domain);
 639     visitHardInstr(mi, domain);
 640     return;
 641   }
 642
 643   // Kill off any remaining uses that don't match available, and build a list of
 644   // incoming DomainValues that we want to merge.
 645   SmallVector<LiveReg, 4> Regs;
 646   for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
 647     int rx = *i;
 648     const LiveReg &LR = LiveRegs[rx];
 649     // This useless DomainValue could have been missed above.
 650     if (!LR.Value->getCommonDomains(available)) {
 651       kill(rx);
 652       continue;
 653     }
 654     // Sorted insertion.
 655     bool Inserted = false;
 656     for (SmallVectorImpl<LiveReg>::iterator i = Regs.begin(), e = Regs.end();
 657            i != e && !Inserted; ++i) {
 658       if (LR.Def < i->Def) {
 659         Inserted = true;
 660         Regs.insert(i, LR);
 661       }
 662     }
 663     if (!Inserted)
 664       Regs.push_back(LR);
 665   }
 666
 667   // doms are now sorted in order of appearance. Try to merge them all, giving
 668   // priority to the latest ones.
 669   DomainValue *dv = 0;
 670   while (!Regs.empty()) {
 671     if (!dv) {
 672       dv = Regs.pop_back_val().Value;
 673       // Force the first dv to match the current instruction.
 674       dv->AvailableDomains = dv->getCommonDomains(available);
 675       assert(dv->AvailableDomains && "Domain should have been filtered");
 676       continue;
 677     }
 678
 679     DomainValue *Latest = Regs.pop_back_val().Value;
 680     // Skip already merged values.
 681     if (Latest == dv || Latest->Next)
 682       continue;
 683     if (merge(dv, Latest))
 684       continue;
 685
 686     // If latest didn't merge, it is useless now. Kill all registers using it.
 687     for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i)
 688       if (LiveRegs[*i].Value == Latest)
 689         kill(*i);
 690   }
 691
 692   // dv is the DomainValue we are going to use for this instruction.
 693   if (!dv) {
 694     dv = alloc();
 695     dv->AvailableDomains = available;
 696   }
 697   dv->Instrs.push_back(mi);
 698
 699   // Finally set all defs and non-collapsed uses to dv. We must iterate through
 700   // all the operators, including imp-def ones.
 701   for (MachineInstr::mop_iterator ii = mi->operands_begin(),
 702                                   ee = mi->operands_end();
 703                                   ii != ee; ++ii) {
 704     MachineOperand &mo = *ii;
 705     if (!mo.isReg()) continue;
 706     int rx = regIndex(mo.getReg());
 707     if (rx < 0) continue;
 708     if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
 709       kill(rx);
 710       setLiveReg(rx, dv);
 711     }
 712   }
 713 }
 714
 715 bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) {
 716   MF = &mf;
 717   TII = MF->getTarget().getInstrInfo();
 718   TRI = MF->getTarget().getRegisterInfo();
 719   LiveRegs = 0;
 720   assert(NumRegs == RC->getNumRegs() && "Bad regclass");
 721
 722   DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
 723                << RC->getName() << " **********\n");
 724
 725   // If no relevant registers are used in the function, we can skip it
 726   // completely.
 727   bool anyregs = false;
 728   for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end();
 729        I != E; ++I)
 730     if (MF->getRegInfo().isPhysRegUsed(*I)) {
 731       anyregs = true;
 732       break;
 733     }
 734   if (!anyregs) return false;
 735
 736   // Initialize the AliasMap on the first use.
 737   if (AliasMap.empty()) {
 738     // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC,
 739     // or -1.
 740     AliasMap.resize(TRI->getNumRegs(), -1);
 741     for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
 742       for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
 743            AI.isValid(); ++AI)
 744         AliasMap[*AI] = i;
 745   }
 746
 747   MachineBasicBlock *Entry = MF->begin();
 748   ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
 749   SmallVector<MachineBasicBlock*, 16> Loops;
 750   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
 751          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
 752     MachineBasicBlock *MBB = *MBBI;
 753     enterBasicBlock(MBB);
 754     if (SeenUnknownBackEdge)
 755       Loops.push_back(MBB);
 756     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
 757         ++I)
 758       visitInstr(I);
 759     processUndefReads(MBB);
 760     leaveBasicBlock(MBB);
 761   }
 762
 763   // Visit all the loop blocks again in order to merge DomainValues from
 764   // back-edges.
 765   for (unsigned i = 0, e = Loops.size(); i != e; ++i) {
 766     MachineBasicBlock *MBB = Loops[i];
 767     enterBasicBlock(MBB);
 768     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
 769         ++I)
 770       if (!I->isDebugValue())
 771         processDefs(I, false);
 772     processUndefReads(MBB);
 773     leaveBasicBlock(MBB);
 774   }
 775
 776   // Clear the LiveOuts vectors and collapse any remaining DomainValues.
 777   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
 778          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
 779     LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI);
 780     if (FI == LiveOuts.end() || !FI->second)
 781       continue;
 782     for (unsigned i = 0, e = NumRegs; i != e; ++i)
 783       if (FI->second[i].Value)
 784         release(FI->second[i].Value);
 785     delete[] FI->second;
 786   }
 787   LiveOuts.clear();
 788   UndefReads.clear();
 789   Avail.clear();
 790   Allocator.DestroyAll();
 791
 792   return false;
 793 }
 794
 795 FunctionPass *
 796 llvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) {
 797   return new ExeDepsFix(RC);
 798 }