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