Home | History | Annotate | Download | only in CodeGen
      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/MachineFunctionPass.h"
     27 #include "llvm/CodeGen/MachineRegisterInfo.h"
     28 #include "llvm/Support/Allocator.h"
     29 #include "llvm/Support/Debug.h"
     30 #include "llvm/Support/raw_ostream.h"
     31 #include "llvm/Target/TargetInstrInfo.h"
     32 #include "llvm/Target/TargetMachine.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(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(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 (SmallVectorImpl<int>::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 (SmallVectorImpl<LiveReg>::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 (SmallVectorImpl<int>::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. We must iterate through
    630   // all the operators, including imp-def ones.
    631   for (MachineInstr::mop_iterator ii = mi->operands_begin(),
    632                                   ee = mi->operands_end();
    633                                   ii != ee; ++ii) {
    634     MachineOperand &mo = *ii;
    635     if (!mo.isReg()) continue;
    636     int rx = regIndex(mo.getReg());
    637     if (rx < 0) continue;
    638     if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
    639       kill(rx);
    640       setLiveReg(rx, dv);
    641     }
    642   }
    643 }
    644 
    645 bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) {
    646   MF = &mf;
    647   TII = MF->getTarget().getInstrInfo();
    648   TRI = MF->getTarget().getRegisterInfo();
    649   LiveRegs = 0;
    650   assert(NumRegs == RC->getNumRegs() && "Bad regclass");
    651 
    652   DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
    653                << RC->getName() << " **********\n");
    654 
    655   // If no relevant registers are used in the function, we can skip it
    656   // completely.
    657   bool anyregs = false;
    658   for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end();
    659        I != E; ++I)
    660     if (MF->getRegInfo().isPhysRegUsed(*I)) {
    661       anyregs = true;
    662       break;
    663     }
    664   if (!anyregs) return false;
    665 
    666   // Initialize the AliasMap on the first use.
    667   if (AliasMap.empty()) {
    668     // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC,
    669     // or -1.
    670     AliasMap.resize(TRI->getNumRegs(), -1);
    671     for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
    672       for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
    673            AI.isValid(); ++AI)
    674         AliasMap[*AI] = i;
    675   }
    676 
    677   MachineBasicBlock *Entry = MF->begin();
    678   ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
    679   SmallVector<MachineBasicBlock*, 16> Loops;
    680   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
    681          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
    682     MachineBasicBlock *MBB = *MBBI;
    683     enterBasicBlock(MBB);
    684     if (SeenUnknownBackEdge)
    685       Loops.push_back(MBB);
    686     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
    687         ++I)
    688       visitInstr(I);
    689     leaveBasicBlock(MBB);
    690   }
    691 
    692   // Visit all the loop blocks again in order to merge DomainValues from
    693   // back-edges.
    694   for (unsigned i = 0, e = Loops.size(); i != e; ++i) {
    695     MachineBasicBlock *MBB = Loops[i];
    696     enterBasicBlock(MBB);
    697     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
    698         ++I)
    699       if (!I->isDebugValue())
    700         processDefs(I, false);
    701     leaveBasicBlock(MBB);
    702   }
    703 
    704   // Clear the LiveOuts vectors and collapse any remaining DomainValues.
    705   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
    706          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
    707     LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI);
    708     if (FI == LiveOuts.end() || !FI->second)
    709       continue;
    710     for (unsigned i = 0, e = NumRegs; i != e; ++i)
    711       if (FI->second[i].Value)
    712         release(FI->second[i].Value);
    713     delete[] FI->second;
    714   }
    715   LiveOuts.clear();
    716   Avail.clear();
    717   Allocator.DestroyAll();
    718 
    719   return false;
    720 }
    721 
    722 FunctionPass *
    723 llvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) {
    724   return new ExeDepsFix(RC);
    725 }
    726