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