lib/CodeGen/ExecutionDomainFix.cpp

   1 //===- ExecutionDomainFix.cpp - Fix execution domain 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/ExecutionDomainFix.h"
  11 #include "llvm/CodeGen/MachineRegisterInfo.h"
  12 #include "llvm/CodeGen/TargetInstrInfo.h"
  13
  14 using namespace llvm;
  15
  16 #define DEBUG_TYPE "execution-deps-fix"
  17
  18 iterator_range<SmallVectorImpl<int>::const_iterator>
  19 ExecutionDomainFix::regIndices(unsigned Reg) const {
  20   assert(Reg < AliasMap.size() && "Invalid register");
  21   const auto &Entry = AliasMap[Reg];
  22   return make_range(Entry.begin(), Entry.end());
  23 }
  24
  25 DomainValue *ExecutionDomainFix::alloc(int domain) {
  26   DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
  27                                   : Avail.pop_back_val();
  28   if (domain >= 0)
  29     dv->addDomain(domain);
  30   assert(dv->Refs == 0 && "Reference count wasn't cleared");
  31   assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
  32   return dv;
  33 }
  34
  35 void ExecutionDomainFix::release(DomainValue *DV) {
  36   while (DV) {
  37     assert(DV->Refs && "Bad DomainValue");
  38     if (--DV->Refs)
  39       return;
  40
  41     // There are no more DV references. Collapse any contained instructions.
  42     if (DV->AvailableDomains && !DV->isCollapsed())
  43       collapse(DV, DV->getFirstDomain());
  44
  45     DomainValue *Next = DV->Next;
  46     DV->clear();
  47     Avail.push_back(DV);
  48     // Also release the next DomainValue in the chain.
  49     DV = Next;
  50   }
  51 }
  52
  53 DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
  54   DomainValue *DV = DVRef;
  55   if (!DV || !DV->Next)
  56     return DV;
  57
  58   // DV has a chain. Find the end.
  59   do
  60     DV = DV->Next;
  61   while (DV->Next);
  62
  63   // Update DVRef to point to DV.
  64   retain(DV);
  65   release(DVRef);
  66   DVRef = DV;
  67   return DV;
  68 }
  69
  70 void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
  71   assert(unsigned(rx) < NumRegs && "Invalid index");
  72   assert(!LiveRegs.empty() && "Must enter basic block first.");
  73
  74   if (LiveRegs[rx] == dv)
  75     return;
  76   if (LiveRegs[rx])
  77     release(LiveRegs[rx]);
  78   LiveRegs[rx] = retain(dv);
  79 }
  80
  81 void ExecutionDomainFix::kill(int rx) {
  82   assert(unsigned(rx) < NumRegs && "Invalid index");
  83   assert(!LiveRegs.empty() && "Must enter basic block first.");
  84   if (!LiveRegs[rx])
  85     return;
  86
  87   release(LiveRegs[rx]);
  88   LiveRegs[rx] = nullptr;
  89 }
  90
  91 void ExecutionDomainFix::force(int rx, unsigned domain) {
  92   assert(unsigned(rx) < NumRegs && "Invalid index");
  93   assert(!LiveRegs.empty() && "Must enter basic block first.");
  94   if (DomainValue *dv = LiveRegs[rx]) {
  95     if (dv->isCollapsed())
  96       dv->addDomain(domain);
  97     else if (dv->hasDomain(domain))
  98       collapse(dv, domain);
  99     else {
 100       // This is an incompatible open DomainValue. Collapse it to whatever and
 101       // force the new value into domain. This costs a domain crossing.
 102       collapse(dv, dv->getFirstDomain());
 103       assert(LiveRegs[rx] && "Not live after collapse?");
 104       LiveRegs[rx]->addDomain(domain);
 105     }
 106   } else {
 107     // Set up basic collapsed DomainValue.
 108     setLiveReg(rx, alloc(domain));
 109   }
 110 }
 111
 112 void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
 113   assert(dv->hasDomain(domain) && "Cannot collapse");
 114
 115   // Collapse all the instructions.
 116   while (!dv->Instrs.empty())
 117     TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
 118   dv->setSingleDomain(domain);
 119
 120   // If there are multiple users, give them new, unique DomainValues.
 121   if (!LiveRegs.empty() && dv->Refs > 1)
 122     for (unsigned rx = 0; rx != NumRegs; ++rx)
 123       if (LiveRegs[rx] == dv)
 124         setLiveReg(rx, alloc(domain));
 125 }
 126
 127 bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
 128   assert(!A->isCollapsed() && "Cannot merge into collapsed");
 129   assert(!B->isCollapsed() && "Cannot merge from collapsed");
 130   if (A == B)
 131     return true;
 132   // Restrict to the domains that A and B have in common.
 133   unsigned common = A->getCommonDomains(B->AvailableDomains);
 134   if (!common)
 135     return false;
 136   A->AvailableDomains = common;
 137   A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
 138
 139   // Clear the old DomainValue so we won't try to swizzle instructions twice.
 140   B->clear();
 141   // All uses of B are referred to A.
 142   B->Next = retain(A);
 143
 144   for (unsigned rx = 0; rx != NumRegs; ++rx) {
 145     assert(!LiveRegs.empty() && "no space allocated for live registers");
 146     if (LiveRegs[rx] == B)
 147       setLiveReg(rx, A);
 148   }
 149   return true;
 150 }
 151
 152 void ExecutionDomainFix::enterBasicBlock(
 153     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 154
 155   MachineBasicBlock *MBB = TraversedMBB.MBB;
 156
 157   // Set up LiveRegs to represent registers entering MBB.
 158   // Set default domain values to 'no domain' (nullptr)
 159   if (LiveRegs.empty())
 160     LiveRegs.assign(NumRegs, nullptr);
 161
 162   // This is the entry block.
 163   if (MBB->pred_empty()) {
 164     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
 165     return;
 166   }
 167
 168   // Try to coalesce live-out registers from predecessors.
 169   for (MachineBasicBlock *pred : MBB->predecessors()) {
 170     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
 171            "Should have pre-allocated MBBInfos for all MBBs");
 172     LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
 173     // Incoming is null if this is a backedge from a BB
 174     // we haven't processed yet
 175     if (Incoming.empty())
 176       continue;
 177
 178     for (unsigned rx = 0; rx != NumRegs; ++rx) {
 179       DomainValue *pdv = resolve(Incoming[rx]);
 180       if (!pdv)
 181         continue;
 182       if (!LiveRegs[rx]) {
 183         setLiveReg(rx, pdv);
 184         continue;
 185       }
 186
 187       // We have a live DomainValue from more than one predecessor.
 188       if (LiveRegs[rx]->isCollapsed()) {
 189         // We are already collapsed, but predecessor is not. Force it.
 190         unsigned Domain = LiveRegs[rx]->getFirstDomain();
 191         if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
 192           collapse(pdv, Domain);
 193         continue;
 194       }
 195
 196       // Currently open, merge in predecessor.
 197       if (!pdv->isCollapsed())
 198         merge(LiveRegs[rx], pdv);
 199       else
 200         force(rx, pdv->getFirstDomain());
 201     }
 202   }
 203   LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
 204                     << (!TraversedMBB.IsDone ? ": incomplete\n"
 205                                              : ": all preds known\n"));
 206 }
 207
 208 void ExecutionDomainFix::leaveBasicBlock(
 209     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 210   assert(!LiveRegs.empty() && "Must enter basic block first.");
 211   unsigned MBBNumber = TraversedMBB.MBB->getNumber();
 212   assert(MBBNumber < MBBOutRegsInfos.size() &&
 213          "Unexpected basic block number.");
 214   // Save register clearances at end of MBB - used by enterBasicBlock().
 215   for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
 216     release(OldLiveReg);
 217   }
 218   MBBOutRegsInfos[MBBNumber] = LiveRegs;
 219   LiveRegs.clear();
 220 }
 221
 222 bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
 223   // Update instructions with explicit execution domains.
 224   std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
 225   if (DomP.first) {
 226     if (DomP.second)
 227       visitSoftInstr(MI, DomP.second);
 228     else
 229       visitHardInstr(MI, DomP.first);
 230   }
 231
 232   return !DomP.first;
 233 }
 234
 235 void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
 236   assert(!MI->isDebugInstr() && "Won't process debug values");
 237   const MCInstrDesc &MCID = MI->getDesc();
 238   for (unsigned i = 0,
 239                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
 240        i != e; ++i) {
 241     MachineOperand &MO = MI->getOperand(i);
 242     if (!MO.isReg())
 243       continue;
 244     if (MO.isUse())
 245       continue;
 246     for (int rx : regIndices(MO.getReg())) {
 247       // This instruction explicitly defines rx.
 248       LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
 249
 250       // Kill off domains redefined by generic instructions.
 251       if (Kill)
 252         kill(rx);
 253     }
 254   }
 255 }
 256
 257 void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
 258   // Collapse all uses.
 259   for (unsigned i = mi->getDesc().getNumDefs(),
 260                 e = mi->getDesc().getNumOperands();
 261        i != e; ++i) {
 262     MachineOperand &mo = mi->getOperand(i);
 263     if (!mo.isReg())
 264       continue;
 265     for (int rx : regIndices(mo.getReg())) {
 266       force(rx, domain);
 267     }
 268   }
 269
 270   // Kill all defs and force them.
 271   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
 272     MachineOperand &mo = mi->getOperand(i);
 273     if (!mo.isReg())
 274       continue;
 275     for (int rx : regIndices(mo.getReg())) {
 276       kill(rx);
 277       force(rx, domain);
 278     }
 279   }
 280 }
 281
 282 void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
 283   // Bitmask of available domains for this instruction after taking collapsed
 284   // operands into account.
 285   unsigned available = mask;
 286
 287   // Scan the explicit use operands for incoming domains.
 288   SmallVector<int, 4> used;
 289   if (!LiveRegs.empty())
 290     for (unsigned i = mi->getDesc().getNumDefs(),
 291                   e = mi->getDesc().getNumOperands();
 292          i != e; ++i) {
 293       MachineOperand &mo = mi->getOperand(i);
 294       if (!mo.isReg())
 295         continue;
 296       for (int rx : regIndices(mo.getReg())) {
 297         DomainValue *dv = LiveRegs[rx];
 298         if (dv == nullptr)
 299           continue;
 300         // Bitmask of domains that dv and available have in common.
 301         unsigned common = dv->getCommonDomains(available);
 302         // Is it possible to use this collapsed register for free?
 303         if (dv->isCollapsed()) {
 304           // Restrict available domains to the ones in common with the operand.
 305           // If there are no common domains, we must pay the cross-domain
 306           // penalty for this operand.
 307           if (common)
 308             available = common;
 309         } else if (common)
 310           // Open DomainValue is compatible, save it for merging.
 311           used.push_back(rx);
 312         else
 313           // Open DomainValue is not compatible with instruction. It is useless
 314           // now.
 315           kill(rx);
 316       }
 317     }
 318
 319   // If the collapsed operands force a single domain, propagate the collapse.
 320   if (isPowerOf2_32(available)) {
 321     unsigned domain = countTrailingZeros(available);
 322     TII->setExecutionDomain(*mi, domain);
 323     visitHardInstr(mi, domain);
 324     return;
 325   }
 326
 327   // Kill off any remaining uses that don't match available, and build a list of
 328   // incoming DomainValues that we want to merge.
 329   SmallVector<int, 4> Regs;
 330   for (int rx : used) {
 331     assert(!LiveRegs.empty() && "no space allocated for live registers");
 332     DomainValue *&LR = LiveRegs[rx];
 333     // This useless DomainValue could have been missed above.
 334     if (!LR->getCommonDomains(available)) {
 335       kill(rx);
 336       continue;
 337     }
 338     // Sorted insertion.
 339     // Enables giving priority to the latest domains during merging.
 340     auto I = std::upper_bound(
 341         Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
 342           return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
 343                  RDA->getReachingDef(mi, RC->getRegister(RHS));
 344         });
 345     Regs.insert(I, rx);
 346   }
 347
 348   // doms are now sorted in order of appearance. Try to merge them all, giving
 349   // priority to the latest ones.
 350   DomainValue *dv = nullptr;
 351   while (!Regs.empty()) {
 352     if (!dv) {
 353       dv = LiveRegs[Regs.pop_back_val()];
 354       // Force the first dv to match the current instruction.
 355       dv->AvailableDomains = dv->getCommonDomains(available);
 356       assert(dv->AvailableDomains && "Domain should have been filtered");
 357       continue;
 358     }
 359
 360     DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
 361     // Skip already merged values.
 362     if (Latest == dv || Latest->Next)
 363       continue;
 364     if (merge(dv, Latest))
 365       continue;
 366
 367     // If latest didn't merge, it is useless now. Kill all registers using it.
 368     for (int i : used) {
 369       assert(!LiveRegs.empty() && "no space allocated for live registers");
 370       if (LiveRegs[i] == Latest)
 371         kill(i);
 372     }
 373   }
 374
 375   // dv is the DomainValue we are going to use for this instruction.
 376   if (!dv) {
 377     dv = alloc();
 378     dv->AvailableDomains = available;
 379   }
 380   dv->Instrs.push_back(mi);
 381
 382   // Finally set all defs and non-collapsed uses to dv. We must iterate through
 383   // all the operators, including imp-def ones.
 384   for (MachineOperand &mo : mi->operands()) {
 385     if (!mo.isReg())
 386       continue;
 387     for (int rx : regIndices(mo.getReg())) {
 388       if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
 389         kill(rx);
 390         setLiveReg(rx, dv);
 391       }
 392     }
 393   }
 394 }
 395
 396 void ExecutionDomainFix::processBasicBlock(
 397     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 398   enterBasicBlock(TraversedMBB);
 399   // If this block is not done, it makes little sense to make any decisions
 400   // based on clearance information. We need to make a second pass anyway,
 401   // and by then we'll have better information, so we can avoid doing the work
 402   // to try and break dependencies now.
 403   for (MachineInstr &MI : *TraversedMBB.MBB) {
 404     if (!MI.isDebugInstr()) {
 405       bool Kill = false;
 406       if (TraversedMBB.PrimaryPass)
 407         Kill = visitInstr(&MI);
 408       processDefs(&MI, Kill);
 409     }
 410   }
 411   leaveBasicBlock(TraversedMBB);
 412 }
 413
 414 bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
 415   if (skipFunction(mf.getFunction()))
 416     return false;
 417   MF = &mf;
 418   TII = MF->getSubtarget().getInstrInfo();
 419   TRI = MF->getSubtarget().getRegisterInfo();
 420   LiveRegs.clear();
 421   assert(NumRegs == RC->getNumRegs() && "Bad regclass");
 422
 423   LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
 424                     << TRI->getRegClassName(RC) << " **********\n");
 425
 426   // If no relevant registers are used in the function, we can skip it
 427   // completely.
 428   bool anyregs = false;
 429   const MachineRegisterInfo &MRI = mf.getRegInfo();
 430   for (unsigned Reg : *RC) {
 431     if (MRI.isPhysRegUsed(Reg)) {
 432       anyregs = true;
 433       break;
 434     }
 435   }
 436   if (!anyregs)
 437     return false;
 438
 439   RDA = &getAnalysis<ReachingDefAnalysis>();
 440
 441   // Initialize the AliasMap on the first use.
 442   if (AliasMap.empty()) {
 443     // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
 444     // therefore the LiveRegs array.
 445     AliasMap.resize(TRI->getNumRegs());
 446     for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
 447       for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
 448            ++AI)
 449         AliasMap[*AI].push_back(i);
 450   }
 451
 452   // Initialize the MBBOutRegsInfos
 453   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
 454
 455   // Traverse the basic blocks.
 456   LoopTraversal Traversal;
 457   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
 458   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
 459     processBasicBlock(TraversedMBB);
 460   }
 461
 462   for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
 463     for (DomainValue *OutLiveReg : OutLiveRegs) {
 464       if (OutLiveReg)
 465         release(OutLiveReg);
 466     }
 467   }
 468   MBBOutRegsInfos.clear();
 469   Avail.clear();
 470   Allocator.DestroyAll();
 471
 472   return false;
 473 }