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/raw_ostream.h"
22#include "llvm/Target/TargetMachine.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.getTarget().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
75void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
76  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
77               << " to " << PrintReg(PhysReg, TRI) << ':');
78  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
79  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
80  MRI->setPhysRegUsed(PhysReg);
81  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
82    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
83    Matrix[*Units].unify(VirtReg);
84  }
85  ++NumAssigned;
86  DEBUG(dbgs() << '\n');
87}
88
89void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
90  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
91  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
92               << " from " << PrintReg(PhysReg, TRI) << ':');
93  VRM->clearVirt(VirtReg.reg);
94  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
95    DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
96    Matrix[*Units].extract(VirtReg);
97  }
98  ++NumUnassigned;
99  DEBUG(dbgs() << '\n');
100}
101
102bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
103                                             unsigned PhysReg) {
104  // Check if the cached information is valid.
105  // The same BitVector can be reused for all PhysRegs.
106  // We could cache multiple VirtRegs if it becomes necessary.
107  if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
108    RegMaskVirtReg = VirtReg.reg;
109    RegMaskTag = UserTag;
110    RegMaskUsable.clear();
111    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
112  }
113
114  // The BitVector is indexed by PhysReg, not register unit.
115  // Regmask interference is more fine grained than regunits.
116  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
117  return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
118}
119
120bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
121                                             unsigned PhysReg) {
122  if (VirtReg.empty())
123    return false;
124  CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
125  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
126    const LiveRange &UnitRange = LIS->getRegUnit(*Units);
127    if (VirtReg.overlaps(UnitRange, CP, *LIS->getSlotIndexes()))
128      return true;
129  }
130  return false;
131}
132
133LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
134                                               unsigned RegUnit) {
135  LiveIntervalUnion::Query &Q = Queries[RegUnit];
136  Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
137  return Q;
138}
139
140LiveRegMatrix::InterferenceKind
141LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
142  if (VirtReg.empty())
143    return IK_Free;
144
145  // Regmask interference is the fastest check.
146  if (checkRegMaskInterference(VirtReg, PhysReg))
147    return IK_RegMask;
148
149  // Check for fixed interference.
150  if (checkRegUnitInterference(VirtReg, PhysReg))
151    return IK_RegUnit;
152
153  // Check the matrix for virtual register interference.
154  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
155    if (query(VirtReg, *Units).checkInterference())
156      return IK_VirtReg;
157
158  return IK_Free;
159}
160