llvm/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/InitializePasses.h"
  24 #include "llvm/MC/LaneBitmask.h"
  25 #include "llvm/MC/MCRegisterInfo.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <cassert>
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "regalloc"
  34
  35 STATISTIC(NumAssigned   , "Number of registers assigned");
  36 STATISTIC(NumUnassigned , "Number of registers unassigned");
  37
  38 char LiveRegMatrix::ID = 0;
  39 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
  40                       "Live Register Matrix", false, false)
  41 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  42 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
  43 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
  44                     "Live Register Matrix", false, false)
  45
  46 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
  47
  48 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
  49   AU.setPreservesAll();
  50   AU.addRequiredTransitive<LiveIntervals>();
  51   AU.addRequiredTransitive<VirtRegMap>();
  52   MachineFunctionPass::getAnalysisUsage(AU);
  53 }
  54
  55 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
  56   TRI = MF.getSubtarget().getRegisterInfo();
  57   LIS = &getAnalysis<LiveIntervals>();
  58   VRM = &getAnalysis<VirtRegMap>();
  59
  60   unsigned NumRegUnits = TRI->getNumRegUnits();
  61   if (NumRegUnits != Matrix.size())
  62     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
  63   Matrix.init(LIUAlloc, NumRegUnits);
  64
  65   // Make sure no stale queries get reused.
  66   invalidateVirtRegs();
  67   return false;
  68 }
  69
  70 void LiveRegMatrix::releaseMemory() {
  71   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
  72     Matrix[i].clear();
  73     // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
  74     // have anything important to clear and LiveRegMatrix's runOnFunction()
  75     // does a std::unique_ptr::reset anyways.
  76   }
  77 }
  78
  79 template <typename Callable>
  80 static bool foreachUnit(const TargetRegisterInfo *TRI,
  81                         const LiveInterval &VRegInterval, MCRegister PhysReg,
  82                         Callable Func) {
  83   if (VRegInterval.hasSubRanges()) {
  84     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
  85       unsigned Unit = (*Units).first;
  86       LaneBitmask Mask = (*Units).second;
  87       for (const LiveInterval::SubRange &S : VRegInterval.subranges()) {
  88         if ((S.LaneMask & Mask).any()) {
  89           if (Func(Unit, S))
  90             return true;
  91           break;
  92         }
  93       }
  94     }
  95   } else {
  96     for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
  97       if (Func(Unit, VRegInterval))
  98         return true;
  99     }
 100   }
 101   return false;
 102 }
 103
 104 void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) {
 105   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "
 106                     << printReg(PhysReg, TRI) << ':');
 107   assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");
 108   VRM->assignVirt2Phys(VirtReg.reg(), PhysReg);
 109
 110   foreachUnit(
 111       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
 112         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
 113         Matrix[Unit].unify(VirtReg, Range);
 114         return false;
 115       });
 116
 117   ++NumAssigned;
 118   LLVM_DEBUG(dbgs() << '\n');
 119 }
 120
 121 void LiveRegMatrix::unassign(const LiveInterval &VirtReg) {
 122   Register PhysReg = VRM->getPhys(VirtReg.reg());
 123   LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
 124                     << " from " << printReg(PhysReg, TRI) << ':');
 125   VRM->clearVirt(VirtReg.reg());
 126
 127   foreachUnit(TRI, VirtReg, PhysReg,
 128               [&](unsigned Unit, const LiveRange &Range) {
 129                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
 130                 Matrix[Unit].extract(VirtReg, Range);
 131                 return false;
 132               });
 133
 134   ++NumUnassigned;
 135   LLVM_DEBUG(dbgs() << '\n');
 136 }
 137
 138 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
 139   for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
 140     if (!Matrix[Unit].empty())
 141       return true;
 142   }
 143   return false;
 144 }
 145
 146 bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg,
 147                                              MCRegister PhysReg) {
 148   // Check if the cached information is valid.
 149   // The same BitVector can be reused for all PhysRegs.
 150   // We could cache multiple VirtRegs if it becomes necessary.
 151   if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {
 152     RegMaskVirtReg = VirtReg.reg();
 153     RegMaskTag = UserTag;
 154     RegMaskUsable.clear();
 155     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
 156   }
 157
 158   // The BitVector is indexed by PhysReg, not register unit.
 159   // Regmask interference is more fine grained than regunits.
 160   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
 161   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
 162 }
 163
 164 bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg,
 165                                              MCRegister PhysReg) {
 166   if (VirtReg.empty())
 167     return false;
 168   CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI);
 169
 170   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
 171                                                        const LiveRange &Range) {
 172     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
 173     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
 174   });
 175   return Result;
 176 }
 177
 178 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
 179                                                MCRegister RegUnit) {
 180   LiveIntervalUnion::Query &Q = Queries[RegUnit];
 181   Q.init(UserTag, LR, Matrix[RegUnit]);
 182   return Q;
 183 }
 184
 185 LiveRegMatrix::InterferenceKind
 186 LiveRegMatrix::checkInterference(const LiveInterval &VirtReg,
 187                                  MCRegister PhysReg) {
 188   if (VirtReg.empty())
 189     return IK_Free;
 190
 191   // Regmask interference is the fastest check.
 192   if (checkRegMaskInterference(VirtReg, PhysReg))
 193     return IK_RegMask;
 194
 195   // Check for fixed interference.
 196   if (checkRegUnitInterference(VirtReg, PhysReg))
 197     return IK_RegUnit;
 198
 199   // Check the matrix for virtual register interference.
 200   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
 201                                   [&](MCRegister Unit, const LiveRange &LR) {
 202                                     return query(LR, Unit).checkInterference();
 203                                   });
 204   if (Interference)
 205     return IK_VirtReg;
 206
 207   return IK_Free;
 208 }
 209
 210 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
 211                                       MCRegister PhysReg) {
 212   // Construct artificial live range containing only one segment [Start, End).
 213   VNInfo valno(0, Start);
 214   LiveRange::Segment Seg(Start, End, &valno);
 215   LiveRange LR;
 216   LR.addSegment(Seg);
 217
 218   // Check for interference with that segment
 219   for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
 220     // LR is stack-allocated. LiveRegMatrix caches queries by a key that
 221     // includes the address of the live range. If (for the same reg unit) this
 222     // checkInterference overload is called twice, without any other query()
 223     // calls in between (on heap-allocated LiveRanges)  - which would invalidate
 224     // the cached query - the LR address seen the second time may well be the
 225     // same as that seen the first time, while the Start/End/valno may not - yet
 226     // the same cached result would be fetched. To avoid that, we don't cache
 227     // this query.
 228     //
 229     // FIXME: the usability of the Query API needs to be improved to avoid
 230     // subtle bugs due to query identity. Avoiding caching, for example, would
 231     // greatly simplify things.
 232     LiveIntervalUnion::Query Q;
 233     Q.reset(UserTag, LR, Matrix[Unit]);
 234     if (Q.checkInterference())
 235       return true;
 236   }
 237   return false;
 238 }
 239
 240 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
 241   const LiveInterval *VRegInterval = nullptr;
 242   for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
 243     if ((VRegInterval = Matrix[Unit].getOneVReg()))
 244       return VRegInterval->reg();
 245   }
 246
 247   return MCRegister::NoRegister;
 248 }