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