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