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