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