lib/CodeGen/LiveRegMatrix.cpp

   1 //===- LiveRegMatrix.cpp - Track register interference --------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines the LiveRegMatrix analysis pass.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/LiveRegMatrix.h"
  14 #include "RegisterCoalescer.h"
  15 #include "llvm/ADT/Statistic.h"
  16 #include "llvm/CodeGen/LiveInterval.h"
  17 #include "llvm/CodeGen/LiveIntervalUnion.h"
  18 #include "llvm/CodeGen/LiveIntervals.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  22 #include "llvm/CodeGen/VirtRegMap.h"
  23 #include "llvm/MC/LaneBitmask.h"
  24 #include "llvm/MC/MCRegisterInfo.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <cassert>
  29
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "regalloc"
  33
  34 STATISTIC(NumAssigned   , "Number of registers assigned");
  35 STATISTIC(NumUnassigned , "Number of registers unassigned");
  36
  37 char LiveRegMatrix::ID = 0;
  38 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
  39                       "Live Register Matrix", false, false)
  40 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  41 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
  42 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
  43                     "Live Register Matrix", false, false)
  44
  45 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
  46
  47 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
  48   AU.setPreservesAll();
  49   AU.addRequiredTransitive<LiveIntervals>();
  50   AU.addRequiredTransitive<VirtRegMap>();
  51   MachineFunctionPass::getAnalysisUsage(AU);
  52 }
  53
  54 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
  55   TRI = MF.getSubtarget().getRegisterInfo();
  56   LIS = &getAnalysis<LiveIntervals>();
  57   VRM = &getAnalysis<VirtRegMap>();
  58
  59   unsigned NumRegUnits = TRI->getNumRegUnits();
  60   if (NumRegUnits != Matrix.size())
  61     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
  62   Matrix.init(LIUAlloc, NumRegUnits);
  63
  64   // Make sure no stale queries get reused.
  65   invalidateVirtRegs();
  66   return false;
  67 }
  68
  69 void LiveRegMatrix::releaseMemory() {
  70   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
  71     Matrix[i].clear();
  72     // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
  73     // have anything important to clear and LiveRegMatrix's runOnFunction()
  74     // does a std::unique_ptr::reset anyways.
  75   }
  76 }
  77
  78 template <typename Callable>
  79 static bool foreachUnit(const TargetRegisterInfo *TRI,
  80                         LiveInterval &VRegInterval, unsigned PhysReg,
  81                         Callable Func) {
  82   if (VRegInterval.hasSubRanges()) {
  83     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
  84       unsigned Unit = (*Units).first;
  85       LaneBitmask Mask = (*Units).second;
  86       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
  87         if ((S.LaneMask & Mask).any()) {
  88           if (Func(Unit, S))
  89             return true;
  90           break;
  91         }
  92       }
  93     }
  94   } else {
  95     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
  96       if (Func(*Units, VRegInterval))
  97         return true;
  98     }
  99   }
 100   return false;
 101 }
 102
 103 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
 104   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
 105                     << printReg(PhysReg, TRI) << ':');
 106   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
 107   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
 108
 109   foreachUnit(
 110       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
 111         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
 112         Matrix[Unit].unify(VirtReg, Range);
 113         return false;
 114       });
 115
 116   ++NumAssigned;
 117   LLVM_DEBUG(dbgs() << '\n');
 118 }
 119
 120 void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
 121   Register PhysReg = VRM->getPhys(VirtReg.reg);
 122   LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
 123                     << printReg(PhysReg, TRI) << ':');
 124   VRM->clearVirt(VirtReg.reg);
 125
 126   foreachUnit(TRI, VirtReg, PhysReg,
 127               [&](unsigned Unit, const LiveRange &Range) {
 128                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
 129                 Matrix[Unit].extract(VirtReg, Range);
 130                 return false;
 131               });
 132
 133   ++NumUnassigned;
 134   LLVM_DEBUG(dbgs() << '\n');
 135 }
 136
 137 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
 138   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
 139     if (!Matrix[*Unit].empty())
 140       return true;
 141   }
 142   return false;
 143 }
 144
 145 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
 146                                              unsigned PhysReg) {
 147   // Check if the cached information is valid.
 148   // The same BitVector can be reused for all PhysRegs.
 149   // We could cache multiple VirtRegs if it becomes necessary.
 150   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
 151     RegMaskVirtReg = VirtReg.reg;
 152     RegMaskTag = UserTag;
 153     RegMaskUsable.clear();
 154     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
 155   }
 156
 157   // The BitVector is indexed by PhysReg, not register unit.
 158   // Regmask interference is more fine grained than regunits.
 159   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
 160   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
 161 }
 162
 163 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
 164                                              unsigned PhysReg) {
 165   if (VirtReg.empty())
 166     return false;
 167   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
 168
 169   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
 170                                                        const LiveRange &Range) {
 171     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
 172     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
 173   });
 174   return Result;
 175 }
 176
 177 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
 178                                                unsigned RegUnit) {
 179   LiveIntervalUnion::Query &Q = Queries[RegUnit];
 180   Q.init(UserTag, LR, Matrix[RegUnit]);
 181   return Q;
 182 }
 183
 184 LiveRegMatrix::InterferenceKind
 185 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
 186   if (VirtReg.empty())
 187     return IK_Free;
 188
 189   // Regmask interference is the fastest check.
 190   if (checkRegMaskInterference(VirtReg, PhysReg))
 191     return IK_RegMask;
 192
 193   // Check for fixed interference.
 194   if (checkRegUnitInterference(VirtReg, PhysReg))
 195     return IK_RegUnit;
 196
 197   // Check the matrix for virtual register interference.
 198   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
 199                                   [&](unsigned Unit, const LiveRange &LR) {
 200     return query(LR, Unit).checkInterference();
 201   });
 202   if (Interference)
 203     return IK_VirtReg;
 204
 205   return IK_Free;
 206 }
 207
 208 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
 209                                       unsigned PhysReg) {
 210   // Construct artificial live range containing only one segment [Start, End).
 211   VNInfo valno(0, Start);
 212   LiveRange::Segment Seg(Start, End, &valno);
 213   LiveRange LR;
 214   LR.addSegment(Seg);
 215
 216   // Check for interference with that segment
 217   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
 218     if (query(LR, *Units).checkInterference())
 219       return true;
 220   }
 221   return false;
 222 }