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