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