LCOV - code coverage report
Current view: top level - lib/CodeGen - CalcSpillWeights.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 111 112 99.1 %
Date: 2018-07-13 00:08:38 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- CalcSpillWeights.cpp -----------------------------------------------===//
       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/CalcSpillWeights.h"
      11             : #include "llvm/ADT/SmallPtrSet.h"
      12             : #include "llvm/CodeGen/LiveInterval.h"
      13             : #include "llvm/CodeGen/LiveIntervals.h"
      14             : #include "llvm/CodeGen/MachineFunction.h"
      15             : #include "llvm/CodeGen/MachineInstr.h"
      16             : #include "llvm/CodeGen/MachineLoopInfo.h"
      17             : #include "llvm/CodeGen/MachineOperand.h"
      18             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      19             : #include "llvm/CodeGen/TargetInstrInfo.h"
      20             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      21             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      22             : #include "llvm/CodeGen/VirtRegMap.h"
      23             : #include "llvm/Support/Debug.h"
      24             : #include "llvm/Support/raw_ostream.h"
      25             : #include <cassert>
      26             : #include <tuple>
      27             : 
      28             : using namespace llvm;
      29             : 
      30             : #define DEBUG_TYPE "calcspillweights"
      31             : 
      32      181822 : void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS,
      33             :                            MachineFunction &MF,
      34             :                            VirtRegMap *VRM,
      35             :                            const MachineLoopInfo &MLI,
      36             :                            const MachineBlockFrequencyInfo &MBFI,
      37             :                            VirtRegAuxInfo::NormalizingFn norm) {
      38             :   LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
      39             :                     << "********** Function: " << MF.getName() << '\n');
      40             : 
      41      181822 :   MachineRegisterInfo &MRI = MF.getRegInfo();
      42             :   VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
      43     5474594 :   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
      44             :     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
      45     2646386 :     if (MRI.reg_nodbg_empty(Reg))
      46     1355281 :       continue;
      47     1291105 :     VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg));
      48             :   }
      49      181822 : }
      50             : 
      51             : // Return the preferred allocation register for reg, given a COPY instruction.
      52     1084869 : static unsigned copyHint(const MachineInstr *mi, unsigned reg,
      53             :                          const TargetRegisterInfo &tri,
      54             :                          const MachineRegisterInfo &mri) {
      55             :   unsigned sub, hreg, hsub;
      56     1084869 :   if (mi->getOperand(0).getReg() == reg) {
      57             :     sub = mi->getOperand(0).getSubReg();
      58      492908 :     hreg = mi->getOperand(1).getReg();
      59             :     hsub = mi->getOperand(1).getSubReg();
      60             :   } else {
      61             :     sub = mi->getOperand(1).getSubReg();
      62             :     hreg = mi->getOperand(0).getReg();
      63             :     hsub = mi->getOperand(0).getSubReg();
      64             :   }
      65             : 
      66     1084869 :   if (!hreg)
      67             :     return 0;
      68             : 
      69     1084869 :   if (TargetRegisterInfo::isVirtualRegister(hreg))
      70      277611 :     return sub == hsub ? hreg : 0;
      71             : 
      72             :   const TargetRegisterClass *rc = mri.getRegClass(reg);
      73      807258 :   if (!tri.enableMultipleCopyHints()) {
      74             :     // Only allow physreg hints in rc.
      75      592240 :     if (sub == 0)
      76     1161250 :       return rc->contains(hreg) ? hreg : 0;
      77             : 
      78             :     // reg:sub should match the physreg hreg.
      79       23216 :     return tri.getMatchingSuperReg(hreg, sub, rc);
      80             :   }
      81             : 
      82      215018 :   unsigned CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
      83      429475 :   if (rc->contains(CopiedPReg))
      84             :     return CopiedPReg;
      85             : 
      86             :   // Check if reg:sub matches so that a super register could be hinted.
      87       18387 :   if (sub)
      88       16331 :     return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
      89             : 
      90             :   return 0;
      91             : }
      92             : 
      93             : // Check if all values in LI are rematerializable
      94      861059 : static bool isRematerializable(const LiveInterval &LI,
      95             :                                const LiveIntervals &LIS,
      96             :                                VirtRegMap *VRM,
      97             :                                const TargetInstrInfo &TII) {
      98      861059 :   unsigned Reg = LI.reg;
      99      861059 :   unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
     100      210298 :   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
     101     1071357 :        I != E; ++I) {
     102      913725 :     const VNInfo *VNI = *I;
     103      913725 :     if (VNI->isUnused())
     104          20 :       continue;
     105      913705 :     if (VNI->isPHIDef())
     106             :       return false;
     107             : 
     108             :     MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
     109             :     assert(MI && "Dead valno in interval");
     110             : 
     111             :     // Trace copies introduced by live range splitting.  The inline
     112             :     // spiller can rematerialize through these copies, so the spill
     113             :     // weight must reflect this.
     114      902593 :     if (VRM) {
     115       40711 :       while (MI->isFullCopy()) {
     116             :         // The copy destination must match the interval register.
     117      301685 :         if (MI->getOperand(0).getReg() != Reg)
     118      260974 :           return false;
     119             : 
     120             :         // Get the source register.
     121      300905 :         Reg = MI->getOperand(1).getReg();
     122             : 
     123             :         // If the original (pre-splitting) registers match this
     124             :         // copy came from a split.
     125      363375 :         if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
     126             :             VRM->getOriginal(Reg) != Original)
     127             :           return false;
     128             : 
     129             :         // Follow the copy live-in value.
     130             :         const LiveInterval &SrcLI = LIS.getInterval(Reg);
     131       45375 :         LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
     132       45375 :         VNI = SrcQ.valueIn();
     133             :         assert(VNI && "Copy from non-existing value");
     134       45375 :         if (VNI->isPHIDef())
     135             :           return false;
     136             :         MI = LIS.getInstructionFromIndex(VNI->def);
     137             :         assert(MI && "Dead valno in interval");
     138             :       }
     139             :     }
     140             : 
     141      641619 :     if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis()))
     142             :       return false;
     143             :   }
     144             :   return true;
     145             : }
     146             : 
     147     1406307 : void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) {
     148     1406307 :   float weight = weightCalcHelper(li);
     149             :   // Check if unspillable.
     150     1406307 :   if (weight < 0)
     151             :     return;
     152      860285 :   li.weight = weight;
     153             : }
     154             : 
     155         774 : float VirtRegAuxInfo::futureWeight(LiveInterval &li, SlotIndex start,
     156             :                                    SlotIndex end) {
     157         774 :   return weightCalcHelper(li, &start, &end);
     158             : }
     159             : 
     160     1407081 : float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
     161             :                                        SlotIndex *end) {
     162     1407081 :   MachineRegisterInfo &mri = MF.getRegInfo();
     163     1407081 :   const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
     164             :   MachineBasicBlock *mbb = nullptr;
     165             :   MachineLoop *loop = nullptr;
     166             :   bool isExiting = false;
     167             :   float totalWeight = 0;
     168             :   unsigned numInstr = 0; // Number of instructions using li
     169             :   SmallPtrSet<MachineInstr*, 8> visited;
     170             : 
     171     1407081 :   std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
     172             : 
     173             :   // Don't recompute spill weight for an unspillable register.
     174     1407081 :   bool Spillable = li.isSpillable();
     175             : 
     176     1407081 :   bool localSplitArtifact = start && end;
     177             : 
     178             :   // Do not update future local split artifacts.
     179     1407081 :   bool updateLI = !localSplitArtifact;
     180             : 
     181     1407081 :   if (localSplitArtifact) {
     182         774 :     MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
     183             :     assert(localMBB == LIS.getMBBFromIndex(*start) &&
     184             :            "start and end are expected to be in the same basic block");
     185             : 
     186             :     // Local split artifact will have 2 additional copy instructions and they
     187             :     // will be in the same BB.
     188             :     // localLI = COPY other
     189             :     // ...
     190             :     // other   = COPY localLI
     191         774 :     totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
     192         774 :     totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
     193             : 
     194             :     numInstr += 2;
     195             :   }
     196             : 
     197             :   // CopyHint is a sortable hint derived from a COPY instruction.
     198             :   struct CopyHint {
     199             :     unsigned Reg;
     200             :     float Weight;
     201             :     bool IsPhys;
     202             :     unsigned HintOrder;
     203     1027347 :     CopyHint(unsigned R, float W, bool P, unsigned HR) :
     204     1027347 :       Reg(R), Weight(W), IsPhys(P), HintOrder(HR) {}
     205             :     bool operator<(const CopyHint &rhs) const {
     206             :       // Always prefer any physreg hint.
     207     1589080 :       if (IsPhys != rhs.IsPhys)
     208      119244 :         return (IsPhys && !rhs.IsPhys);
     209     1469836 :       if (Weight != rhs.Weight)
     210     1246392 :         return (Weight > rhs.Weight);
     211             : 
     212             :       // This is just a temporary way to achive NFC for targets that don't
     213             :       // enable multiple copy hints. HintOrder should be removed when all
     214             :       // targets return true in enableMultipleCopyHints().
     215      223444 :       return (HintOrder < rhs.HintOrder);
     216             : 
     217             : #if 0 // Should replace the HintOrder check, see above.
     218             :       // (just for the purpose of maintaining the set)
     219             :       return Reg < rhs.Reg;
     220             : #endif
     221             :     }
     222             :   };
     223             :   std::set<CopyHint> CopyHints;
     224             : 
     225             :   // Temporary: see comment for HintOrder above.
     226             :   unsigned CopyHintOrder = 0;
     227             :   for (MachineRegisterInfo::reg_instr_iterator
     228     1407081 :        I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
     229     5959191 :        I != E; ) {
     230             :     MachineInstr *mi = &*(I++);
     231             : 
     232             :     // For local split artifacts, we are interested only in instructions between
     233             :     // the expected start and end of the range.
     234     4552110 :     SlotIndex si = LIS.getInstructionIndex(*mi);
     235     4558801 :     if (localSplitArtifact && ((si < *start) || (si > *end)))
     236     3527914 :       continue;
     237             : 
     238     4547373 :     numInstr++;
     239     4548902 :     if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugInstr())
     240        1529 :       continue;
     241     4763979 :     if (!visited.insert(mi).second)
     242      218135 :       continue;
     243             : 
     244             :     float weight = 1.0f;
     245     4327709 :     if (Spillable) {
     246             :       // Get loop info for mi.
     247     4327705 :       if (mi->getParent() != mbb) {
     248             :         mbb = mi->getParent();
     249     1798270 :         loop = Loops.getLoopFor(mbb);
     250      430810 :         isExiting = loop ? loop->isLoopExiting(mbb) : false;
     251             :       }
     252             : 
     253             :       // Calculate instr weight.
     254             :       bool reads, writes;
     255     8655410 :       std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
     256     4327705 :       weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
     257             : 
     258             :       // Give extra weight to what looks like a loop induction variable update.
     259     4327705 :       if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
     260       19815 :         weight *= 3;
     261             : 
     262     4327705 :       totalWeight += weight;
     263             :     }
     264             : 
     265             :     // Get allocation hints from copies.
     266     7570549 :     if (!mi->isCopy() ||
     267          74 :         (TargetHint.first != 0 && !tri.enableMultipleCopyHints()))
     268     3242840 :       continue;
     269     1084869 :     unsigned hint = copyHint(mi, li.reg, tri, mri);
     270     1084869 :     if (!hint)
     271       55936 :       continue;
     272             :     // Force hweight onto the stack so that x86 doesn't add hidden precision,
     273             :     // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
     274             :     //
     275             :     // FIXME: we probably shouldn't use floats at all.
     276     2057866 :     volatile float hweight = Hint[hint] += weight;
     277     2057866 :     if (TargetRegisterInfo::isVirtualRegister(hint) || mri.isAllocatable(hint))
     278     4109388 :       CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint),
     279     1769815 :                      (tri.enableMultipleCopyHints() ? hint : CopyHintOrder++)));
     280             :   }
     281             : 
     282     1407081 :   Hint.clear();
     283             : 
     284             :   // Pass all the sorted copy hints to mri.
     285     2813388 :   if (updateLI && CopyHints.size()) {
     286             :     // Remove a generic hint if previously added by target.
     287      718896 :     if (TargetHint.first == 0 && TargetHint.second)
     288         851 :       mri.clearSimpleHint(li.reg);
     289             : 
     290     1003754 :     for (auto &Hint : CopyHints) {
     291      780188 :       if (TargetHint.first != 0 && Hint.Reg == TargetHint.second)
     292             :         // Don't add again the target-type hint.
     293           0 :         continue;
     294      780188 :       mri.addRegAllocationHint(li.reg, Hint.Reg);
     295      780188 :       if (!tri.enableMultipleCopyHints())
     296             :         break;
     297             :     }
     298             : 
     299             :     // Weakly boost the spill weight of hinted registers.
     300      718896 :     totalWeight *= 1.01F;
     301             :   }
     302             : 
     303             :   // If the live interval was already unspillable, leave it that way.
     304     1407081 :   if (!Spillable)
     305             :     return -1.0;
     306             : 
     307             :   // Mark li as unspillable if all live ranges are tiny and the interval
     308             :   // is not live at any reg mask.  If the interval is live at a reg mask
     309             :   // spilling may be required.
     310     1953105 :   if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
     311      546026 :       !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
     312             :     li.markNotSpillable();
     313      546020 :     return -1.0;
     314             :   }
     315             : 
     316             :   // If all of the definitions of the interval are re-materializable,
     317             :   // it is a preferred candidate for spilling.
     318             :   // FIXME: this gets much more complicated once we support non-trivial
     319             :   // re-materialization.
     320      861059 :   if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
     321      157632 :     totalWeight *= 0.5F;
     322             : 
     323      861059 :   if (localSplitArtifact)
     324        1548 :     return normalize(totalWeight, start->distance(*end), numInstr);
     325      860285 :   return normalize(totalWeight, li.getSize(), numInstr);
     326             : }

Generated by: LCOV version 1.13