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
25 using namespace llvm;
26
27 #define DEBUG_TYPE "regalloc"
28
29 STATISTIC(NumAssigned , "Number of registers assigned");
30 STATISTIC(NumUnassigned , "Number of registers unassigned");
31
32 char LiveRegMatrix::ID = 0;
33 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
34 "Live Register Matrix", false, false)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)35 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
36 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
37 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
38 "Live Register Matrix", false, false)
39
40 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID),
41 UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {}
42
getAnalysisUsage(AnalysisUsage & AU) const43 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
44 AU.setPreservesAll();
45 AU.addRequiredTransitive<LiveIntervals>();
46 AU.addRequiredTransitive<VirtRegMap>();
47 MachineFunctionPass::getAnalysisUsage(AU);
48 }
49
runOnMachineFunction(MachineFunction & MF)50 bool 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
releaseMemory()66 void 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
assign(LiveInterval & VirtReg,unsigned PhysReg)75 void 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
unassign(LiveInterval & VirtReg)89 void 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
checkRegMaskInterference(LiveInterval & VirtReg,unsigned PhysReg)102 bool 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
checkRegUnitInterference(LiveInterval & VirtReg,unsigned PhysReg)120 bool 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
query(LiveInterval & VirtReg,unsigned RegUnit)133 LiveIntervalUnion::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
140 LiveRegMatrix::InterferenceKind
checkInterference(LiveInterval & VirtReg,unsigned PhysReg)141 LiveRegMatrix::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