LCOV - code coverage report
Current view: top level - lib/CodeGen - ExecutionDomainFix.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 211 217 97.2 %
Date: 2018-06-17 00:07:59 Functions: 18 18 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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     3984543 : ExecutionDomainFix::regIndices(unsigned Reg) const {
      20             :   assert(Reg < AliasMap.size() && "Invalid register");
      21     3984543 :   const auto &Entry = AliasMap[Reg];
      22     3984543 :   return make_range(Entry.begin(), Entry.end());
      23             : }
      24             : 
      25      524168 : DomainValue *ExecutionDomainFix::alloc(int domain) {
      26      524168 :   DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
      27             :                                   : Avail.pop_back_val();
      28      524168 :   if (domain >= 0)
      29      411491 :     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      524168 :   return dv;
      33             : }
      34             : 
      35     2313259 : void ExecutionDomainFix::release(DomainValue *DV) {
      36     3361521 :   while (DV) {
      37             :     assert(DV->Refs && "Bad DomainValue");
      38     1059801 :     if (--DV->Refs)
      39             :       return;
      40             : 
      41             :     // There are no more DV references. Collapse any contained instructions.
      42     1046502 :     if (DV->AvailableDomains && !DV->isCollapsed())
      43       18300 :       collapse(DV, DV->getFirstDomain());
      44             : 
      45      524131 :     DomainValue *Next = DV->Next;
      46             :     DV->clear();
      47      524131 :     Avail.push_back(DV);
      48             :     // Also release the next DomainValue in the chain.
      49      524131 :     DV = Next;
      50             :   }
      51             : }
      52             : 
      53     7902976 : DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
      54     7902976 :   DomainValue *DV = DVRef;
      55     7902976 :   if (!DV || !DV->Next)
      56             :     return DV;
      57             : 
      58             :   // DV has a chain. Find the end.
      59             :   do
      60         175 :     DV = DV->Next;
      61         175 :   while (DV->Next);
      62             : 
      63             :   // Update DVRef to point to DV.
      64             :   retain(DV);
      65         164 :   release(DVRef);
      66         164 :   DVRef = DV;
      67         164 :   return DV;
      68             : }
      69             : 
      70     1057877 : 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     2115754 :   if (LiveRegs[rx] == dv)
      75             :     return;
      76     1057877 :   if (LiveRegs[rx])
      77       21407 :     release(LiveRegs[rx]);
      78     2115754 :   LiveRegs[rx] = retain(dv);
      79             : }
      80             : 
      81      466374 : void ExecutionDomainFix::kill(int rx) {
      82             :   assert(unsigned(rx) < NumRegs && "Invalid index");
      83             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
      84      932748 :   if (!LiveRegs[rx])
      85             :     return;
      86             : 
      87      346814 :   release(LiveRegs[rx]);
      88      693628 :   LiveRegs[rx] = nullptr;
      89             : }
      90             : 
      91      879956 : void ExecutionDomainFix::force(int rx, unsigned domain) {
      92             :   assert(unsigned(rx) < NumRegs && "Invalid index");
      93             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
      94     1759912 :   if (DomainValue *dv = LiveRegs[rx]) {
      95      487780 :     if (dv->isCollapsed())
      96             :       dv->addDomain(domain);
      97      184520 :     else if (dv->hasDomain(domain))
      98       92142 :       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         118 :       collapse(dv, dv->getFirstDomain());
     103             :       assert(LiveRegs[rx] && "Not live after collapse?");
     104         236 :       LiveRegs[rx]->addDomain(domain);
     105             :     }
     106             :   } else {
     107             :     // Set up basic collapsed DomainValue.
     108      392176 :     setLiveReg(rx, alloc(domain));
     109             :   }
     110      879956 : }
     111             : 
     112      110880 : void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
     113             :   assert(dv->hasDomain(domain) && "Cannot collapse");
     114             : 
     115             :   // Collapse all the instructions.
     116      447212 :   while (!dv->Instrs.empty())
     117      336332 :     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      110880 :   if (!LiveRegs.empty() && dv->Refs > 1)
     122      598130 :     for (unsigned rx = 0; rx != NumRegs; ++rx)
     123      588928 :       if (LiveRegs[rx] == dv)
     124       19315 :         setLiveReg(rx, alloc(domain));
     125      110880 : }
     126             : 
     127        7137 : bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
     128             :   assert(!A->isCollapsed() && "Cannot merge into collapsed");
     129             :   assert(!B->isCollapsed() && "Cannot merge from collapsed");
     130        7137 :   if (A == B)
     131             :     return true;
     132             :   // Restrict to the domains that A and B have in common.
     133        1760 :   unsigned common = A->getCommonDomains(B->AvailableDomains);
     134        1760 :   if (!common)
     135             :     return false;
     136        1760 :   A->AvailableDomains = common;
     137        3520 :   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        1760 :   B->Next = retain(A);
     143             : 
     144      114400 :   for (unsigned rx = 0; rx != NumRegs; ++rx) {
     145             :     assert(!LiveRegs.empty() && "no space allocated for live registers");
     146      112640 :     if (LiveRegs[rx] == B)
     147        2092 :       setLiveReg(rx, A);
     148             :   }
     149             :   return true;
     150             : }
     151             : 
     152      263530 : void ExecutionDomainFix::enterBasicBlock(
     153             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     154             : 
     155      263530 :   MachineBasicBlock *MBB = TraversedMBB.MBB;
     156             : 
     157             :   // Set up LiveRegs to represent registers entering MBB.
     158             :   // Set default domain values to 'no domain' (nullptr)
     159      263530 :   if (LiveRegs.empty())
     160      527060 :     LiveRegs.assign(NumRegs, nullptr);
     161             : 
     162             :   // This is the entry block.
     163      263530 :   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      424221 :   for (MachineBasicBlock *pred : MBB->predecessors()) {
     170             :     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
     171             :            "Should have pre-allocated MBBInfos for all MBBs");
     172      250502 :     LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
     173             :     // Incoming is null if this is a backedge from a BB
     174             :     // we haven't processed yet
     175      250502 :     if (Incoming.empty())
     176        3534 :       continue;
     177             : 
     178    16052920 :     for (unsigned rx = 0; rx != NumRegs; ++rx) {
     179    15805952 :       DomainValue *pdv = resolve(Incoming[rx]);
     180     7902976 :       if (!pdv)
     181     7165709 :         continue;
     182     1992085 :       if (!LiveRegs[rx]) {
     183      517551 :         setLiveReg(rx, pdv);
     184      517551 :         continue;
     185             :       }
     186             : 
     187             :       // We have a live DomainValue from more than one predecessor.
     188      219716 :       if (LiveRegs[rx]->isCollapsed()) {
     189             :         // We are already collapsed, but predecessor is not. Force it.
     190      213760 :         unsigned Domain = LiveRegs[rx]->getFirstDomain();
     191      214086 :         if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
     192         320 :           collapse(pdv, Domain);
     193      213760 :         continue;
     194             :       }
     195             : 
     196             :       // Currently open, merge in predecessor.
     197        5956 :       if (!pdv->isCollapsed())
     198        5703 :         merge(LiveRegs[rx], pdv);
     199             :       else
     200         506 :         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      263530 : void ExecutionDomainFix::leaveBasicBlock(
     209             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     210             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
     211      263530 :   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     1931988 :   for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
     216     1404928 :     release(OldLiveReg);
     217             :   }
     218      527060 :   MBBOutRegsInfos[MBBNumber] = LiveRegs;
     219             :   LiveRegs.clear();
     220      263530 : }
     221             : 
     222     2001179 : bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
     223             :   // Update instructions with explicit execution domains.
     224     2001179 :   std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
     225     2001179 :   if (DomP.first) {
     226      551900 :     if (DomP.second)
     227      278054 :       visitSoftInstr(MI, DomP.second);
     228             :     else
     229      273846 :       visitHardInstr(MI, DomP.first);
     230             :   }
     231             : 
     232     2001179 :   return !DomP.first;
     233             : }
     234             : 
     235     2419317 : void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
     236             :   assert(!MI->isDebugInstr() && "Won't process debug values");
     237     2419317 :   const MCInstrDesc &MCID = MI->getDesc();
     238     1384454 :   for (unsigned i = 0,
     239     2419317 :                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
     240     3803771 :        i != e; ++i) {
     241     1384454 :     MachineOperand &MO = MI->getOperand(i);
     242     1384454 :     if (!MO.isReg())
     243       60580 :       continue;
     244     1323874 :     if (MO.isUse())
     245      118700 :       continue;
     246     1718487 :     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      513313 :       if (Kill)
     252       49952 :         kill(rx);
     253             :     }
     254             :   }
     255     2419317 : }
     256             : 
     257      383697 : void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
     258             :   // Collapse all uses.
     259     1615864 :   for (unsigned i = mi->getDesc().getNumDefs(),
     260      383697 :                 e = mi->getDesc().getNumOperands();
     261     1615864 :        i != e; ++i) {
     262     1232167 :     MachineOperand &mo = mi->getOperand(i);
     263     1232167 :     if (!mo.isReg())
     264      286638 :       continue;
     265     1535556 :     for (int rx : regIndices(mo.getReg())) {
     266      590027 :       force(rx, domain);
     267             :     }
     268             :   }
     269             : 
     270             :   // Kill all defs and force them.
     271     1381914 :   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
     272      307260 :     MachineOperand &mo = mi->getOperand(i);
     273      307260 :     if (!mo.isReg())
     274           0 :       continue;
     275      596936 :     for (int rx : regIndices(mo.getReg())) {
     276      289676 :       kill(rx);
     277      289676 :       force(rx, domain);
     278             :     }
     279             :   }
     280      383697 : }
     281             : 
     282      278054 : 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      278054 :   if (!LiveRegs.empty())
     290     1618091 :     for (unsigned i = mi->getDesc().getNumDefs(),
     291      278054 :                   e = mi->getDesc().getNumOperands();
     292     1618091 :          i != e; ++i) {
     293     1340037 :       MachineOperand &mo = mi->getOperand(i);
     294     1340037 :       if (!mo.isReg())
     295      457706 :         continue;
     296     1099302 :       for (int rx : regIndices(mo.getReg())) {
     297      433942 :         DomainValue *dv = LiveRegs[rx];
     298      216971 :         if (dv == nullptr)
     299       30085 :           continue;
     300             :         // Bitmask of domains that dv and available have in common.
     301      186886 :         unsigned common = dv->getCommonDomains(available);
     302             :         // Is it possible to use this collapsed register for free?
     303      186886 :         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      126012 :           if (common)
     308             :             available = common;
     309       60874 :         } else if (common)
     310             :           // Open DomainValue is compatible, save it for merging.
     311       60871 :           used.push_back(rx);
     312             :         else
     313             :           // Open DomainValue is not compatible with instruction. It is useless
     314             :           // now.
     315           3 :           kill(rx);
     316             :       }
     317             :     }
     318             : 
     319             :   // If the collapsed operands force a single domain, propagate the collapse.
     320             :   if (isPowerOf2_32(available)) {
     321      109851 :     unsigned domain = countTrailingZeros(available);
     322      109851 :     TII->setExecutionDomain(*mi, domain);
     323      109851 :     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      285317 :   for (int rx : used) {
     331             :     assert(!LiveRegs.empty() && "no space allocated for live registers");
     332       58557 :     DomainValue *&LR = LiveRegs[rx];
     333             :     // This useless DomainValue could have been missed above.
     334      117114 :     if (!LR->getCommonDomains(available)) {
     335           0 :       kill(rx);
     336           0 :       continue;
     337             :     }
     338             :     // Sorted insertion.
     339             :     // Enables giving priority to the latest domains during merging.
     340             :     auto I = std::upper_bound(
     341        3031 :         Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
     342        9093 :           return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
     343        9093 :                  RDA->getReachingDef(mi, RC->getRegister(RHS));
     344        3031 :         });
     345       58557 :     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      226760 :   while (!Regs.empty()) {
     352      114083 :     if (!dv) {
     353      111052 :       dv = LiveRegs[Regs.pop_back_val()];
     354             :       // Force the first dv to match the current instruction.
     355      111052 :       dv->AvailableDomains = dv->getCommonDomains(available);
     356             :       assert(dv->AvailableDomains && "Domain should have been filtered");
     357       55526 :       continue;
     358             :     }
     359             : 
     360        6062 :     DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
     361             :     // Skip already merged values.
     362        3031 :     if (Latest == dv || Latest->Next)
     363        1597 :       continue;
     364        1434 :     if (merge(dv, Latest))
     365        1434 :       continue;
     366             : 
     367             :     // If latest didn't merge, it is useless now. Kill all registers using it.
     368           0 :     for (int i : used) {
     369             :       assert(!LiveRegs.empty() && "no space allocated for live registers");
     370           0 :       if (LiveRegs[i] == Latest)
     371           0 :         kill(i);
     372             :     }
     373             :   }
     374             : 
     375             :   // dv is the DomainValue we are going to use for this instruction.
     376      168203 :   if (!dv) {
     377      112677 :     dv = alloc();
     378      112677 :     dv->AvailableDomains = available;
     379             :   }
     380      168203 :   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     2218506 :   for (MachineOperand &mo : mi->operands()) {
     385      941050 :     if (!mo.isReg())
     386      296801 :       continue;
     387      854106 :     for (int rx : regIndices(mo.getReg())) {
     388      573725 :       if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
     389      126743 :         kill(rx);
     390      126743 :         setLiveReg(rx, dv);
     391             :       }
     392             :     }
     393             :   }
     394             : }
     395             : 
     396      263530 : void ExecutionDomainFix::processBasicBlock(
     397             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     398      263530 :   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     3243271 :   for (MachineInstr &MI : *TraversedMBB.MBB) {
     404             :     if (!MI.isDebugInstr()) {
     405             :       bool Kill = false;
     406     2419317 :       if (TraversedMBB.PrimaryPass)
     407     2001179 :         Kill = visitInstr(&MI);
     408     2419317 :       processDefs(&MI, Kill);
     409             :     }
     410             :   }
     411      263530 :   leaveBasicBlock(TraversedMBB);
     412      263530 : }
     413             : 
     414      113733 : bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
     415      113733 :   if (skipFunction(mf.getFunction()))
     416             :     return false;
     417      113617 :   MF = &mf;
     418      113617 :   TII = MF->getSubtarget().getInstrInfo();
     419      113617 :   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      113617 :   const MachineRegisterInfo &MRI = mf.getRegInfo();
     430     1817190 :   for (unsigned Reg : *RC) {
     431      884789 :     if (MRI.isPhysRegUsed(Reg)) {
     432             :       anyregs = true;
     433             :       break;
     434             :     }
     435             :   }
     436      113617 :   if (!anyregs)
     437             :     return false;
     438             : 
     439       89811 :   RDA = &getAnalysis<ReachingDefAnalysis>();
     440             : 
     441             :   // Initialize the AliasMap on the first use.
     442       89811 :   if (AliasMap.empty()) {
     443             :     // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
     444             :     // therefore the LiveRegs array.
     445        6175 :     AliasMap.resize(TRI->getNumRegs());
     446      407550 :     for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
     447     4059744 :       for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
     448     1733472 :            ++AI)
     449     3466944 :         AliasMap[*AI].push_back(i);
     450             :   }
     451             : 
     452             :   // Initialize the MBBOutRegsInfos
     453      179622 :   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
     454             : 
     455             :   // Traverse the basic blocks.
     456             :   LoopTraversal Traversal;
     457       89811 :   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
     458      616871 :   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
     459      263530 :     processBasicBlock(TraversedMBB);
     460             :   }
     461             : 
     462      530759 :   for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
     463     7248506 :     for (DomainValue *OutLiveReg : OutLiveRegs) {
     464     7028032 :       if (OutLiveReg)
     465      539946 :         release(OutLiveReg);
     466             :     }
     467             :   }
     468       89811 :   MBBOutRegsInfos.clear();
     469             :   Avail.clear();
     470       89811 :   Allocator.DestroyAll();
     471             : 
     472             :   return false;
     473             : }

Generated by: LCOV version 1.13