LiveRegMatrix.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
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#define DEBUG_TYPE "regalloc"
15#include "llvm/CodeGen/LiveRegMatrix.h"
16#include "RegisterCoalescer.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/CodeGen/LiveIntervalAnalysis.h"
19#include "llvm/CodeGen/MachineRegisterInfo.h"
20#include "llvm/CodeGen/VirtRegMap.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.h"
23#include "llvm/Target/TargetMachine.h"
24#include "llvm/Target/TargetRegisterInfo.h"
25
26using namespace llvm;
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.getTarget().getRegisterInfo();
51  MRI = &MF.getRegInfo();
52  LIS = &getAnalysis<LiveIntervals>();
53  VRM = &getAnalysis<VirtRegMap>();
54
55  unsigned NumRegUnits = TRI->getNumRegUnits();
56  if (NumRegUnits != Matrix.size())
57    Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
58  Matrix.init(LIUAlloc, NumRegUnits);
59
60  // Make sure no stale queries get reused.
61  invalidateVirtRegs();
62  return false;
63}
64
65void LiveRegMatrix::releaseMemory() {
66  for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
67    Matrix[i].clear();
68    // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
69    // have anything important to clear and LiveRegMatrix's runOnFunction()
70    // does a std::unique_ptr::reset anyways.
71  }
72}
73
74void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
75  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
76               << " to " << PrintReg(PhysReg, TRI) << ':');
77  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
78  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
79  MRI->setPhysRegUsed(PhysReg);
80  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
81    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
82    Matrix[*Units].unify(VirtReg);
83  }
84  ++NumAssigned;
85  DEBUG(dbgs() << '\n');
86}
87
88void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
89  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
90  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
91               << " from " << PrintReg(PhysReg, TRI) << ':');
92  VRM->clearVirt(VirtReg.reg);
93  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
94    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
95    Matrix[*Units].extract(VirtReg);
96  }
97  ++NumUnassigned;
98  DEBUG(dbgs() << '\n');
99}
100
101bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
102                                             unsigned PhysReg) {
103  // Check if the cached information is valid.
104  // The same BitVector can be reused for all PhysRegs.
105  // We could cache multiple VirtRegs if it becomes necessary.
106  if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
107    RegMaskVirtReg = VirtReg.reg;
108    RegMaskTag = UserTag;
109    RegMaskUsable.clear();
110    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
111  }
112
113  // The BitVector is indexed by PhysReg, not register unit.
114  // Regmask interference is more fine grained than regunits.
115  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
116  return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
117}
118
119bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
120                                             unsigned PhysReg) {
121  if (VirtReg.empty())
122    return false;
123  CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
124  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
125    const LiveRange &UnitRange = LIS->getRegUnit(*Units);
126    if (VirtReg.overlaps(UnitRange, CP, *LIS->getSlotIndexes()))
127      return true;
128  }
129  return false;
130}
131
132LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
133                                               unsigned RegUnit) {
134  LiveIntervalUnion::Query &Q = Queries[RegUnit];
135  Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
136  return Q;
137}
138
139LiveRegMatrix::InterferenceKind
140LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
141  if (VirtReg.empty())
142    return IK_Free;
143
144  // Regmask interference is the fastest check.
145  if (checkRegMaskInterference(VirtReg, PhysReg))
146    return IK_RegMask;
147
148  // Check for fixed interference.
149  if (checkRegUnitInterference(VirtReg, PhysReg))
150    return IK_RegUnit;
151
152  // Check the matrix for virtual register interference.
153  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
154    if (query(VirtReg, *Units).checkInterference())
155      return IK_VirtReg;
156
157  return IK_Free;
158}
159