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