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
31using namespace llvm;
32
33#define DEBUG_TYPE "regalloc"
34
35STATISTIC(NumAssigned   , "Number of registers assigned");
36STATISTIC(NumUnassigned , "Number of registers unassigned");
37
38char LiveRegMatrix::ID = 0;
39INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
40                      "Live Register Matrix", false, false)
41INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
42INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
43INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
44                    "Live Register Matrix", false, false)
45
46LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
47
48void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49  AU.setPreservesAll();
50  AU.addRequiredTransitive<LiveIntervals>();
51  AU.addRequiredTransitive<VirtRegMap>();
52  MachineFunctionPass::getAnalysisUsage(AU);
53}
54
55bool 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
70void 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
79template <typename Callable>
80static 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
104void 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
121void 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
138bool 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
146bool 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
164bool 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
178LiveIntervalUnion::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
185LiveRegMatrix::InterferenceKind
186LiveRegMatrix::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
210bool 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
240Register 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}
249