1 //===-- LiveRegMatrix.cpp - Track register interference -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the LiveRegMatrix analysis pass.
12 //===----------------------------------------------------------------------===//
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"
27 STATISTIC(NumAssigned , "Number of registers assigned");
28 STATISTIC(NumUnassigned , "Number of registers unassigned");
30 char LiveRegMatrix::ID = 0;
31 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
32 "Live Register Matrix", false, false)
33 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
34 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
35 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
36 "Live Register Matrix", false, false)
38 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID),
39 UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {}
41 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
43 AU.addRequiredTransitive<LiveIntervals>();
44 AU.addRequiredTransitive<VirtRegMap>();
45 MachineFunctionPass::getAnalysisUsage(AU);
48 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
49 TRI = MF.getTarget().getRegisterInfo();
50 MRI = &MF.getRegInfo();
51 LIS = &getAnalysis<LiveIntervals>();
52 VRM = &getAnalysis<VirtRegMap>();
54 unsigned NumRegUnits = TRI->getNumRegUnits();
55 if (NumRegUnits != Matrix.size())
56 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
57 Matrix.init(LIUAlloc, NumRegUnits);
59 // Make sure no stale queries get reused.
64 void LiveRegMatrix::releaseMemory() {
65 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
71 void 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);
82 DEBUG(dbgs() << '\n');
85 void 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);
95 DEBUG(dbgs() << '\n');
98 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
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);
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() && !RegMaskUsable.test(PhysReg);
116 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
120 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
121 if (VirtReg.overlaps(LIS->getRegUnit(*Units)))
126 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
128 LiveIntervalUnion::Query &Q = Queries[RegUnit];
129 Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
133 LiveRegMatrix::InterferenceKind
134 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
138 // Regmask interference is the fastest check.
139 if (checkRegMaskInterference(VirtReg, PhysReg))
142 // Check for fixed interference.
143 if (checkRegUnitInterference(VirtReg, PhysReg))
146 // Check the matrix for virtual register interference.
147 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
148 if (query(VirtReg, *Units).checkInterference())