LiveRegMatrix.cpp revision eb06b0b6aa627c6698471d4df71570f080fb3c5c 
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 "LiveRegMatrix.h"
16#include "VirtRegMap.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/TargetRegisterInfo.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/raw_ostream.h"
24
25using namespace llvm;
26
27STATISTIC(NumAssigned   , "Number of registers assigned");
28STATISTIC(NumUnassigned , "Number of registers unassigned");
29
30char LiveRegMatrix::ID = 0;
31INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
32                      "Live Register Matrix", false, false)
33INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
34INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
35INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
36                    "Live Register Matrix", false, false)
37
38LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID),
39  UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {}
40
41void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
42  AU.setPreservesAll();
43  AU.addRequiredTransitive<LiveIntervals>();
44  AU.addRequiredTransitive<VirtRegMap>();
45  MachineFunctionPass::getAnalysisUsage(AU);
46}
47
48bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
49  TRI = MF.getTarget().getRegisterInfo();
50  MRI = &MF.getRegInfo();
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    Queries[i].clear();
68  }
69}
70
71void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
72  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
73               << " to " << PrintReg(PhysReg, TRI) << ':');
74  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
75  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
76  MRI->setPhysRegUsed(PhysReg);
77  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
78    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
79    Matrix[*Units].unify(VirtReg);
80  }
81  ++NumAssigned;
82  DEBUG(dbgs() << '\n');
83}
84
85void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
86  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
87  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
88               << " from " << PrintReg(PhysReg, TRI) << ':');
89  VRM->clearVirt(VirtReg.reg);
90  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
91    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
92    Matrix[*Units].extract(VirtReg);
93  }
94  ++NumUnassigned;
95  DEBUG(dbgs() << '\n');
96}
97
98bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
99                                             unsigned PhysReg) {
100  // Check if the cached information is valid.
101  // The same BitVector can be reused for all PhysRegs.
102  // We could cache multiple VirtRegs if it becomes necessary.
103  if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
104    RegMaskVirtReg = VirtReg.reg;
105    RegMaskTag = UserTag;
106    RegMaskUsable.clear();
107    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
108  }
109
110  // The BitVector is indexed by PhysReg, not register unit.
111  // Regmask interference is more fine grained than regunits.
112  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
113  return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
114}
115
116bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
117                                             unsigned PhysReg) {
118  if (VirtReg.empty())
119    return false;
120  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
121    if (VirtReg.overlaps(LIS->getRegUnit(*Units)))
122      return true;
123  return false;
124}
125
126LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
127                                               unsigned RegUnit) {
128  LiveIntervalUnion::Query &Q = Queries[RegUnit];
129  Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
130  return Q;
131}
132
133LiveRegMatrix::InterferenceKind
134LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
135  if (VirtReg.empty())
136    return IK_Free;
137
138  // Regmask interference is the fastest check.
139  if (checkRegMaskInterference(VirtReg, PhysReg))
140    return IK_RegMask;
141
142  // Check for fixed interference.
143  if (checkRegUnitInterference(VirtReg, PhysReg))
144    return IK_RegUnit;
145
146  // Check the matrix for virtual register interference.
147  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
148    if (query(VirtReg, *Units).checkInterference())
149      return IK_VirtReg;
150
151  return IK_Free;
152}
153