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 #include "llvm/CodeGen/ExecutionDepsFix.h"
  11
  12 #include "llvm/ADT/PostOrderIterator.h"
  13 #include "llvm/ADT/iterator_range.h"
  14 #include "llvm/CodeGen/LivePhysRegs.h"
  15 #include "llvm/CodeGen/MachineFunctionPass.h"
  16 #include "llvm/CodeGen/MachineRegisterInfo.h"
  17 #include "llvm/CodeGen/RegisterClassInfo.h"
  18 #include "llvm/CodeGen/TargetInstrInfo.h"
  19 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  20 #include "llvm/Support/Allocator.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "execution-deps-fix"
  27
  28 /// Translate TRI register number to a list of indices into our smaller tables
  29 /// of interesting registers.
  30 iterator_range<SmallVectorImpl<int>::const_iterator>
  31 ExecutionDepsFix::regIndices(unsigned Reg) const {
  32   assert(Reg < AliasMap.size() && "Invalid register");
  33   const auto &Entry = AliasMap[Reg];
  34   return make_range(Entry.begin(), Entry.end());
  35 }
  36
  37 DomainValue *ExecutionDepsFix::alloc(int domain) {
  38   DomainValue *dv = Avail.empty() ?
  39                       new(Allocator.Allocate()) DomainValue :
  40                       Avail.pop_back_val();
  41   if (domain >= 0)
  42     dv->addDomain(domain);
  43   assert(dv->Refs == 0 && "Reference count wasn't cleared");
  44   assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
  45   return dv;
  46 }
  47
  48 /// Release a reference to DV.  When the last reference is released,
  49 /// collapse if needed.
  50 void ExecutionDepsFix::release(DomainValue *DV) {
  51   while (DV) {
  52     assert(DV->Refs && "Bad DomainValue");
  53     if (--DV->Refs)
  54       return;
  55
  56     // There are no more DV references. Collapse any contained instructions.
  57     if (DV->AvailableDomains && !DV->isCollapsed())
  58       collapse(DV, DV->getFirstDomain());
  59
  60     DomainValue *Next = DV->Next;
  61     DV->clear();
  62     Avail.push_back(DV);
  63     // Also release the next DomainValue in the chain.
  64     DV = Next;
  65   }
  66 }
  67
  68 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
  69 /// Update the referenced pointer when necessary.
  70 DomainValue *ExecutionDepsFix::resolve(DomainValue *&DVRef) {
  71   DomainValue *DV = DVRef;
  72   if (!DV || !DV->Next)
  73     return DV;
  74
  75   // DV has a chain. Find the end.
  76   do DV = DV->Next;
  77   while (DV->Next);
  78
  79   // Update DVRef to point to DV.
  80   retain(DV);
  81   release(DVRef);
  82   DVRef = DV;
  83   return DV;
  84 }
  85
  86 /// Set LiveRegs[rx] = dv, updating reference counts.
  87 void ExecutionDepsFix::setLiveReg(int rx, DomainValue *dv) {
  88   assert(unsigned(rx) < NumRegs && "Invalid index");
  89   assert(LiveRegs && "Must enter basic block first.");
  90
  91   if (LiveRegs[rx].Value == dv)
  92     return;
  93   if (LiveRegs[rx].Value)
  94     release(LiveRegs[rx].Value);
  95   LiveRegs[rx].Value = retain(dv);
  96 }
  97
  98 // Kill register rx, recycle or collapse any DomainValue.
  99 void ExecutionDepsFix::kill(int rx) {
 100   assert(unsigned(rx) < NumRegs && "Invalid index");
 101   assert(LiveRegs && "Must enter basic block first.");
 102   if (!LiveRegs[rx].Value)
 103     return;
 104
 105   release(LiveRegs[rx].Value);
 106   LiveRegs[rx].Value = nullptr;
 107 }
 108
 109 /// Force register rx into domain.
 110 void ExecutionDepsFix::force(int rx, unsigned domain) {
 111   assert(unsigned(rx) < NumRegs && "Invalid index");
 112   assert(LiveRegs && "Must enter basic block first.");
 113   if (DomainValue *dv = LiveRegs[rx].Value) {
 114     if (dv->isCollapsed())
 115       dv->addDomain(domain);
 116     else if (dv->hasDomain(domain))
 117       collapse(dv, domain);
 118     else {
 119       // This is an incompatible open DomainValue. Collapse it to whatever and
 120       // force the new value into domain. This costs a domain crossing.
 121       collapse(dv, dv->getFirstDomain());
 122       assert(LiveRegs[rx].Value && "Not live after collapse?");
 123       LiveRegs[rx].Value->addDomain(domain);
 124     }
 125   } else {
 126     // Set up basic collapsed DomainValue.
 127     setLiveReg(rx, alloc(domain));
 128   }
 129 }
 130
 131 /// Collapse open DomainValue into given domain. If there are multiple
 132 /// registers using dv, they each get a unique collapsed DomainValue.
 133 void ExecutionDepsFix::collapse(DomainValue *dv, unsigned domain) {
 134   assert(dv->hasDomain(domain) && "Cannot collapse");
 135
 136   // Collapse all the instructions.
 137   while (!dv->Instrs.empty())
 138     TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
 139   dv->setSingleDomain(domain);
 140
 141   // If there are multiple users, give them new, unique DomainValues.
 142   if (LiveRegs && dv->Refs > 1)
 143     for (unsigned rx = 0; rx != NumRegs; ++rx)
 144       if (LiveRegs[rx].Value == dv)
 145         setLiveReg(rx, alloc(domain));
 146 }
 147
 148 /// All instructions and registers in B are moved to A, and B is released.
 149 bool ExecutionDepsFix::merge(DomainValue *A, DomainValue *B) {
 150   assert(!A->isCollapsed() && "Cannot merge into collapsed");
 151   assert(!B->isCollapsed() && "Cannot merge from collapsed");
 152   if (A == B)
 153     return true;
 154   // Restrict to the domains that A and B have in common.
 155   unsigned common = A->getCommonDomains(B->AvailableDomains);
 156   if (!common)
 157     return false;
 158   A->AvailableDomains = common;
 159   A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
 160
 161   // Clear the old DomainValue so we won't try to swizzle instructions twice.
 162   B->clear();
 163   // All uses of B are referred to A.
 164   B->Next = retain(A);
 165
 166   for (unsigned rx = 0; rx != NumRegs; ++rx) {
 167     assert(LiveRegs && "no space allocated for live registers");
 168     if (LiveRegs[rx].Value == B)
 169       setLiveReg(rx, A);
 170   }
 171   return true;
 172 }
 173
 174 /// Set up LiveRegs by merging predecessor live-out values.
 175 void ExecutionDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
 176   // Reset instruction counter in each basic block.
 177   CurInstr = 0;
 178
 179   // Set up UndefReads to track undefined register reads.
 180   UndefReads.clear();
 181   LiveRegSet.clear();
 182
 183   // Set up LiveRegs to represent registers entering MBB.
 184   if (!LiveRegs)
 185     LiveRegs = new LiveReg[NumRegs];
 186
 187   // Default values are 'nothing happened a long time ago'.
 188   for (unsigned rx = 0; rx != NumRegs; ++rx) {
 189     LiveRegs[rx].Value = nullptr;
 190     LiveRegs[rx].Def = -(1 << 20);
 191   }
 192
 193   // This is the entry block.
 194   if (MBB->pred_empty()) {
 195     for (const auto &LI : MBB->liveins()) {
 196       for (int rx : regIndices(LI.PhysReg)) {
 197         // Treat function live-ins as if they were defined just before the first
 198         // instruction.  Usually, function arguments are set up immediately
 199         // before the call.
 200         LiveRegs[rx].Def = -1;
 201       }
 202     }
 203     DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
 204     return;
 205   }
 206
 207   // Try to coalesce live-out registers from predecessors.
 208   for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
 209        pe = MBB->pred_end(); pi != pe; ++pi) {
 210     auto fi = MBBInfos.find(*pi);
 211     assert(fi != MBBInfos.end() &&
 212            "Should have pre-allocated MBBInfos for all MBBs");
 213     LiveReg *Incoming = fi->second.OutRegs;
 214     // Incoming is null if this is a backedge from a BB
 215     // we haven't processed yet
 216     if (Incoming == nullptr) {
 217       continue;
 218     }
 219
 220     for (unsigned rx = 0; rx != NumRegs; ++rx) {
 221       // Use the most recent predecessor def for each register.
 222       LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, Incoming[rx].Def);
 223
 224       DomainValue *pdv = resolve(Incoming[rx].Value);
 225       if (!pdv)
 226         continue;
 227       if (!LiveRegs[rx].Value) {
 228         setLiveReg(rx, pdv);
 229         continue;
 230       }
 231
 232       // We have a live DomainValue from more than one predecessor.
 233       if (LiveRegs[rx].Value->isCollapsed()) {
 234         // We are already collapsed, but predecessor is not. Force it.
 235         unsigned Domain = LiveRegs[rx].Value->getFirstDomain();
 236         if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
 237           collapse(pdv, Domain);
 238         continue;
 239       }
 240
 241       // Currently open, merge in predecessor.
 242       if (!pdv->isCollapsed())
 243         merge(LiveRegs[rx].Value, pdv);
 244       else
 245         force(rx, pdv->getFirstDomain());
 246     }
 247   }
 248   DEBUG(
 249       dbgs() << printMBBReference(*MBB)
 250              << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"));
 251 }
 252
 253 void ExecutionDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
 254   assert(LiveRegs && "Must enter basic block first.");
 255   LiveReg *OldOutRegs = MBBInfos[MBB].OutRegs;
 256   // Save register clearances at end of MBB - used by enterBasicBlock().
 257   MBBInfos[MBB].OutRegs = LiveRegs;
 258
 259   // While processing the basic block, we kept `Def` relative to the start
 260   // of the basic block for convenience. However, future use of this information
 261   // only cares about the clearance from the end of the block, so adjust
 262   // everything to be relative to the end of the basic block.
 263   for (unsigned i = 0, e = NumRegs; i != e; ++i)
 264     LiveRegs[i].Def -= CurInstr;
 265   if (OldOutRegs) {
 266     // This must be the second pass.
 267     // Release all the DomainValues instead of keeping them.
 268     for (unsigned i = 0, e = NumRegs; i != e; ++i)
 269       release(OldOutRegs[i].Value);
 270     delete[] OldOutRegs;
 271   }
 272   LiveRegs = nullptr;
 273 }
 274
 275 bool ExecutionDepsFix::visitInstr(MachineInstr *MI) {
 276   // Update instructions with explicit execution domains.
 277   std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
 278   if (DomP.first) {
 279     if (DomP.second)
 280       visitSoftInstr(MI, DomP.second);
 281     else
 282       visitHardInstr(MI, DomP.first);
 283   }
 284
 285   return !DomP.first;
 286 }
 287
 288 /// \brief Helps avoid false dependencies on undef registers by updating the
 289 /// machine instructions' undef operand to use a register that the instruction
 290 /// is truly dependent on, or use a register with clearance higher than Pref.
 291 /// Returns true if it was able to find a true dependency, thus not requiring
 292 /// a dependency breaking instruction regardless of clearance.
 293 bool ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
 294                                                 unsigned OpIdx, unsigned Pref) {
 295   MachineOperand &MO = MI->getOperand(OpIdx);
 296   assert(MO.isUndef() && "Expected undef machine operand");
 297
 298   unsigned OriginalReg = MO.getReg();
 299
 300   // Update only undef operands that are mapped to one register.
 301   if (AliasMap[OriginalReg].size() != 1)
 302     return false;
 303
 304   // Get the undef operand's register class
 305   const TargetRegisterClass *OpRC =
 306       TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
 307
 308   // If the instruction has a true dependency, we can hide the false depdency
 309   // behind it.
 310   for (MachineOperand &CurrMO : MI->operands()) {
 311     if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
 312         !OpRC->contains(CurrMO.getReg()))
 313       continue;
 314     // We found a true dependency - replace the undef register with the true
 315     // dependency.
 316     MO.setReg(CurrMO.getReg());
 317     return true;
 318   }
 319
 320   // Go over all registers in the register class and find the register with
 321   // max clearance or clearance higher than Pref.
 322   unsigned MaxClearance = 0;
 323   unsigned MaxClearanceReg = OriginalReg;
 324   ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
 325   for (auto Reg : Order) {
 326     assert(AliasMap[Reg].size() == 1 &&
 327            "Reg is expected to be mapped to a single index");
 328     int RCrx = *regIndices(Reg).begin();
 329     unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
 330     if (Clearance <= MaxClearance)
 331       continue;
 332     MaxClearance = Clearance;
 333     MaxClearanceReg = Reg;
 334
 335     if (MaxClearance > Pref)
 336       break;
 337   }
 338
 339   // Update the operand if we found a register with better clearance.
 340   if (MaxClearanceReg != OriginalReg)
 341     MO.setReg(MaxClearanceReg);
 342
 343   return false;
 344 }
 345
 346 /// \brief Return true to if it makes sense to break dependence on a partial def
 347 /// or undef use.
 348 bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
 349                                              unsigned Pref) {
 350   unsigned reg = MI->getOperand(OpIdx).getReg();
 351   for (int rx : regIndices(reg)) {
 352     unsigned Clearance = CurInstr - LiveRegs[rx].Def;
 353     DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
 354
 355     if (Pref > Clearance) {
 356       DEBUG(dbgs() << ": Break dependency.\n");
 357       continue;
 358     }
 359     DEBUG(dbgs() << ": OK .\n");
 360     return false;
 361   }
 362   return true;
 363 }
 364
 365 // Update def-ages for registers defined by MI.
 366 // If Kill is set, also kill off DomainValues clobbered by the defs.
 367 //
 368 // Also break dependencies on partial defs and undef uses.
 369 void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
 370                                    bool Kill) {
 371   assert(!MI->isDebugValue() && "Won't process debug values");
 372
 373   // Break dependence on undef uses. Do this before updating LiveRegs below.
 374   unsigned OpNum;
 375   if (breakDependency) {
 376     unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
 377     if (Pref) {
 378       bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
 379       // We don't need to bother trying to break a dependency if this
 380       // instruction has a true dependency on that register through another
 381       // operand - we'll have to wait for it to be available regardless.
 382       if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
 383         UndefReads.push_back(std::make_pair(MI, OpNum));
 384     }
 385   }
 386   const MCInstrDesc &MCID = MI->getDesc();
 387   for (unsigned i = 0,
 388          e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
 389          i != e; ++i) {
 390     MachineOperand &MO = MI->getOperand(i);
 391     if (!MO.isReg())
 392       continue;
 393     if (MO.isUse())
 394       continue;
 395     for (int rx : regIndices(MO.getReg())) {
 396       // This instruction explicitly defines rx.
 397       DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << CurInstr
 398                    << '\t' << *MI);
 399
 400       if (breakDependency) {
 401         // Check clearance before partial register updates.
 402         // Call breakDependence before setting LiveRegs[rx].Def.
 403         unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
 404         if (Pref && shouldBreakDependence(MI, i, Pref))
 405           TII->breakPartialRegDependency(*MI, i, TRI);
 406       }
 407
 408       // How many instructions since rx was last written?
 409       LiveRegs[rx].Def = CurInstr;
 410
 411       // Kill off domains redefined by generic instructions.
 412       if (Kill)
 413         kill(rx);
 414     }
 415   }
 416   ++CurInstr;
 417 }
 418
 419 /// \break Break false dependencies on undefined register reads.
 420 ///
 421 /// Walk the block backward computing precise liveness. This is expensive, so we
 422 /// only do it on demand. Note that the occurrence of undefined register reads
 423 /// that should be broken is very rare, but when they occur we may have many in
 424 /// a single block.
 425 void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
 426   if (UndefReads.empty())
 427     return;
 428
 429   // Collect this block's live out register units.
 430   LiveRegSet.init(*TRI);
 431   // We do not need to care about pristine registers as they are just preserved
 432   // but not actually used in the function.
 433   LiveRegSet.addLiveOutsNoPristines(*MBB);
 434
 435   MachineInstr *UndefMI = UndefReads.back().first;
 436   unsigned OpIdx = UndefReads.back().second;
 437
 438   for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
 439     // Update liveness, including the current instruction's defs.
 440     LiveRegSet.stepBackward(I);
 441
 442     if (UndefMI == &I) {
 443       if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
 444         TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
 445
 446       UndefReads.pop_back();
 447       if (UndefReads.empty())
 448         return;
 449
 450       UndefMI = UndefReads.back().first;
 451       OpIdx = UndefReads.back().second;
 452     }
 453   }
 454 }
 455
 456 // A hard instruction only works in one domain. All input registers will be
 457 // forced into that domain.
 458 void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
 459   // Collapse all uses.
 460   for (unsigned i = mi->getDesc().getNumDefs(),
 461                 e = mi->getDesc().getNumOperands(); i != e; ++i) {
 462     MachineOperand &mo = mi->getOperand(i);
 463     if (!mo.isReg()) continue;
 464     for (int rx : regIndices(mo.getReg())) {
 465       force(rx, domain);
 466     }
 467   }
 468
 469   // Kill all defs and force them.
 470   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
 471     MachineOperand &mo = mi->getOperand(i);
 472     if (!mo.isReg()) continue;
 473     for (int rx : regIndices(mo.getReg())) {
 474       kill(rx);
 475       force(rx, domain);
 476     }
 477   }
 478 }
 479
 480 // A soft instruction can be changed to work in other domains given by mask.
 481 void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
 482   // Bitmask of available domains for this instruction after taking collapsed
 483   // operands into account.
 484   unsigned available = mask;
 485
 486   // Scan the explicit use operands for incoming domains.
 487   SmallVector<int, 4> used;
 488   if (LiveRegs)
 489     for (unsigned i = mi->getDesc().getNumDefs(),
 490                   e = mi->getDesc().getNumOperands(); i != e; ++i) {
 491       MachineOperand &mo = mi->getOperand(i);
 492       if (!mo.isReg()) continue;
 493       for (int rx : regIndices(mo.getReg())) {
 494         DomainValue *dv = LiveRegs[rx].Value;
 495         if (dv == nullptr)
 496           continue;
 497         // Bitmask of domains that dv and available have in common.
 498         unsigned common = dv->getCommonDomains(available);
 499         // Is it possible to use this collapsed register for free?
 500         if (dv->isCollapsed()) {
 501           // Restrict available domains to the ones in common with the operand.
 502           // If there are no common domains, we must pay the cross-domain
 503           // penalty for this operand.
 504           if (common) available = common;
 505         } else if (common)
 506           // Open DomainValue is compatible, save it for merging.
 507           used.push_back(rx);
 508         else
 509           // Open DomainValue is not compatible with instruction. It is useless
 510           // now.
 511           kill(rx);
 512       }
 513     }
 514
 515   // If the collapsed operands force a single domain, propagate the collapse.
 516   if (isPowerOf2_32(available)) {
 517     unsigned domain = countTrailingZeros(available);
 518     TII->setExecutionDomain(*mi, domain);
 519     visitHardInstr(mi, domain);
 520     return;
 521   }
 522
 523   // Kill off any remaining uses that don't match available, and build a list of
 524   // incoming DomainValues that we want to merge.
 525   SmallVector<const LiveReg *, 4> Regs;
 526   for (int rx : used) {
 527     assert(LiveRegs && "no space allocated for live registers");
 528     const LiveReg &LR = LiveRegs[rx];
 529     // This useless DomainValue could have been missed above.
 530     if (!LR.Value->getCommonDomains(available)) {
 531       kill(rx);
 532       continue;
 533     }
 534     // Sorted insertion.
 535     auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
 536                               [](const LiveReg *LHS, const LiveReg *RHS) {
 537                                 return LHS->Def < RHS->Def;
 538                               });
 539     Regs.insert(I, &LR);
 540   }
 541
 542   // doms are now sorted in order of appearance. Try to merge them all, giving
 543   // priority to the latest ones.
 544   DomainValue *dv = nullptr;
 545   while (!Regs.empty()) {
 546     if (!dv) {
 547       dv = Regs.pop_back_val()->Value;
 548       // Force the first dv to match the current instruction.
 549       dv->AvailableDomains = dv->getCommonDomains(available);
 550       assert(dv->AvailableDomains && "Domain should have been filtered");
 551       continue;
 552     }
 553
 554     DomainValue *Latest = Regs.pop_back_val()->Value;
 555     // Skip already merged values.
 556     if (Latest == dv || Latest->Next)
 557       continue;
 558     if (merge(dv, Latest))
 559       continue;
 560
 561     // If latest didn't merge, it is useless now. Kill all registers using it.
 562     for (int i : used) {
 563       assert(LiveRegs && "no space allocated for live registers");
 564       if (LiveRegs[i].Value == Latest)
 565         kill(i);
 566     }
 567   }
 568
 569   // dv is the DomainValue we are going to use for this instruction.
 570   if (!dv) {
 571     dv = alloc();
 572     dv->AvailableDomains = available;
 573   }
 574   dv->Instrs.push_back(mi);
 575
 576   // Finally set all defs and non-collapsed uses to dv. We must iterate through
 577   // all the operators, including imp-def ones.
 578   for (MachineInstr::mop_iterator ii = mi->operands_begin(),
 579                                   ee = mi->operands_end();
 580                                   ii != ee; ++ii) {
 581     MachineOperand &mo = *ii;
 582     if (!mo.isReg()) continue;
 583     for (int rx : regIndices(mo.getReg())) {
 584       if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
 585         kill(rx);
 586         setLiveReg(rx, dv);
 587       }
 588     }
 589   }
 590 }
 591
 592 void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
 593                                          bool PrimaryPass) {
 594   enterBasicBlock(MBB);
 595   // If this block is not done, it makes little sense to make any decisions
 596   // based on clearance information. We need to make a second pass anyway,
 597   // and by then we'll have better information, so we can avoid doing the work
 598   // to try and break dependencies now.
 599   bool breakDependency = isBlockDone(MBB);
 600   for (MachineInstr &MI : *MBB) {
 601     if (!MI.isDebugValue()) {
 602       bool Kill = false;
 603       if (PrimaryPass)
 604         Kill = visitInstr(&MI);
 605       processDefs(&MI, breakDependency, Kill);
 606     }
 607   }
 608   if (breakDependency)
 609     processUndefReads(MBB);
 610   leaveBasicBlock(MBB);
 611 }
 612
 613 bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
 614   return MBBInfos[MBB].PrimaryCompleted &&
 615          MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
 616          MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
 617 }
 618
 619 bool ExecutionDepsFix::runOnMachineFunction(MachineFunction &mf) {
 620   if (skipFunction(mf.getFunction()))
 621     return false;
 622   MF = &mf;
 623   TII = MF->getSubtarget().getInstrInfo();
 624   TRI = MF->getSubtarget().getRegisterInfo();
 625   RegClassInfo.runOnMachineFunction(mf);
 626   LiveRegs = nullptr;
 627   assert(NumRegs == RC->getNumRegs() && "Bad regclass");
 628
 629   DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
 630                << TRI->getRegClassName(RC) << " **********\n");
 631
 632   // If no relevant registers are used in the function, we can skip it
 633   // completely.
 634   bool anyregs = false;
 635   const MachineRegisterInfo &MRI = mf.getRegInfo();
 636   for (unsigned Reg : *RC) {
 637     if (MRI.isPhysRegUsed(Reg)) {
 638       anyregs = true;
 639       break;
 640     }
 641   }
 642   if (!anyregs) return false;
 643
 644   // Initialize the AliasMap on the first use.
 645   if (AliasMap.empty()) {
 646     // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
 647     // therefore the LiveRegs array.
 648     AliasMap.resize(TRI->getNumRegs());
 649     for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
 650       for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
 651            AI.isValid(); ++AI)
 652         AliasMap[*AI].push_back(i);
 653   }
 654
 655   // Initialize the MMBInfos
 656   for (auto &MBB : mf) {
 657     MBBInfo InitialInfo;
 658     MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
 659   }
 660
 661   /*
 662    *  We want to visit every instruction in every basic block in order to update
 663    *  it's execution domain or break any false dependencies. However, for the
 664    *  dependency breaking, we need to know clearances from all predecessors
 665    *  (including any backedges). One way to do so would be to do two complete
 666    *  passes over all basic blocks/instructions, the first for recording
 667    *  clearances, the second to break the dependencies. However, for functions
 668    *  without backedges, or functions with a lot of straight-line code, and
 669    *  a small loop, that would be a lot of unnecessary work (since only the
 670    *  BBs that are part of the loop require two passes). As an example,
 671    *  consider the following loop.
 672    *
 673    *
 674    *     PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
 675    *           ^                                  |
 676    *           +----------------------------------+
 677    *
 678    *  The iteration order is as follows:
 679    *  Naive: PH A B C D A' B' C' D'
 680    *  Optimized: PH A B C A' B' C' D
 681    *
 682    *  Note that we avoid processing D twice, because we can entirely process
 683    *  the predecessors before getting to D. We call a block that is ready
 684    *  for its second round of processing `done` (isBlockDone). Once we finish
 685    *  processing some block, we update the counters in MBBInfos and re-process
 686    *  any successors that are now done.
 687    */
 688
 689   MachineBasicBlock *Entry = &*MF->begin();
 690   ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
 691   SmallVector<MachineBasicBlock *, 4> Workqueue;
 692   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
 693          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
 694     MachineBasicBlock *MBB = *MBBI;
 695     // N.B: IncomingProcessed and IncomingCompleted were already updated while
 696     // processing this block's predecessors.
 697     MBBInfos[MBB].PrimaryCompleted = true;
 698     MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
 699     bool Primary = true;
 700     Workqueue.push_back(MBB);
 701     while (!Workqueue.empty()) {
 702       MachineBasicBlock *ActiveMBB = &*Workqueue.back();
 703       Workqueue.pop_back();
 704       processBasicBlock(ActiveMBB, Primary);
 705       bool Done = isBlockDone(ActiveMBB);
 706       for (auto *Succ : ActiveMBB->successors()) {
 707         if (!isBlockDone(Succ)) {
 708           if (Primary) {
 709             MBBInfos[Succ].IncomingProcessed++;
 710           }
 711           if (Done) {
 712             MBBInfos[Succ].IncomingCompleted++;
 713           }
 714           if (isBlockDone(Succ)) {
 715             Workqueue.push_back(Succ);
 716           }
 717         }
 718       }
 719       Primary = false;
 720     }
 721   }
 722
 723   // We need to go through again and finalize any blocks that are not done yet.
 724   // This is possible if blocks have dead predecessors, so we didn't visit them
 725   // above.
 726   for (ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
 727            MBBI = RPOT.begin(),
 728            MBBE = RPOT.end();
 729        MBBI != MBBE; ++MBBI) {
 730     MachineBasicBlock *MBB = *MBBI;
 731     if (!isBlockDone(MBB)) {
 732       processBasicBlock(MBB, false);
 733       // Don't update successors here. We'll get to them anyway through this
 734       // loop.
 735     }
 736   }
 737
 738   // Clear the LiveOuts vectors and collapse any remaining DomainValues.
 739   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
 740          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
 741     auto FI = MBBInfos.find(*MBBI);
 742     if (FI == MBBInfos.end() || !FI->second.OutRegs)
 743       continue;
 744     for (unsigned i = 0, e = NumRegs; i != e; ++i)
 745       if (FI->second.OutRegs[i].Value)
 746         release(FI->second.OutRegs[i].Value);
 747     delete[] FI->second.OutRegs;
 748   }
 749   MBBInfos.clear();
 750   UndefReads.clear();
 751   Avail.clear();
 752   Allocator.DestroyAll();
 753
 754   return false;
 755 }