blob: a39503ba2eef65f19359295b961141857176448e [file] [log] [blame]
Lang Hamesa937f222009-12-14 06:49:42 +00001//===------------------------ CalcSpillWeights.cpp ------------------------===//
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#define DEBUG_TYPE "calcspillweights"
11
12#include "llvm/Function.h"
13#include "llvm/ADT/SmallSet.h"
14#include "llvm/CodeGen/CalcSpillWeights.h"
15#include "llvm/CodeGen/LiveIntervalAnalysis.h"
16#include "llvm/CodeGen/MachineFunction.h"
17#include "llvm/CodeGen/MachineLoopInfo.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/SlotIndexes.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22#include "llvm/Target/TargetInstrInfo.h"
Evan Cheng8112b532010-02-10 01:21:02 +000023#include "llvm/Target/TargetMachine.h"
Lang Hamesa937f222009-12-14 06:49:42 +000024#include "llvm/Target/TargetRegisterInfo.h"
Lang Hamesa937f222009-12-14 06:49:42 +000025using namespace llvm;
26
27char CalculateSpillWeights::ID = 0;
Owen Andersond13db2c2010-07-21 22:09:45 +000028INITIALIZE_PASS(CalculateSpillWeights, "calcspillweights",
29 "Calculate spill weights", false, false);
Lang Hamesa937f222009-12-14 06:49:42 +000030
31void CalculateSpillWeights::getAnalysisUsage(AnalysisUsage &au) const {
32 au.addRequired<LiveIntervals>();
33 au.addRequired<MachineLoopInfo>();
34 au.setPreservesAll();
35 MachineFunctionPass::getAnalysisUsage(au);
36}
37
38bool CalculateSpillWeights::runOnMachineFunction(MachineFunction &fn) {
39
David Greene7ed6dd62009-12-24 00:39:02 +000040 DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
Lang Hamesa937f222009-12-14 06:49:42 +000041 << "********** Function: "
42 << fn.getFunction()->getName() << '\n');
43
Jakob Stoklund Olesendf30cf92010-08-10 00:02:26 +000044 LiveIntervals &lis = getAnalysis<LiveIntervals>();
45 VirtRegAuxInfo vrai(fn, lis, getAnalysis<MachineLoopInfo>());
46 for (LiveIntervals::iterator I = lis.begin(), E = lis.end(); I != E; ++I) {
Lang Hamesa937f222009-12-14 06:49:42 +000047 LiveInterval &li = *I->second;
Jakob Stoklund Olesendf30cf92010-08-10 00:02:26 +000048 if (TargetRegisterInfo::isVirtualRegister(li.reg))
49 vrai.CalculateWeightAndHint(li);
Lang Hamesa937f222009-12-14 06:49:42 +000050 }
Lang Hamesa937f222009-12-14 06:49:42 +000051 return false;
52}
53
Jakob Stoklund Olesendf30cf92010-08-10 00:02:26 +000054// Return the preferred allocation register for reg, given a COPY instruction.
55static unsigned copyHint(const MachineInstr *mi, unsigned reg,
56 const TargetRegisterInfo &tri,
57 const MachineRegisterInfo &mri) {
58 unsigned sub, hreg, hsub;
59 if (mi->getOperand(0).getReg() == reg) {
60 sub = mi->getOperand(0).getSubReg();
61 hreg = mi->getOperand(1).getReg();
62 hsub = mi->getOperand(1).getSubReg();
63 } else {
64 sub = mi->getOperand(1).getSubReg();
65 hreg = mi->getOperand(0).getReg();
66 hsub = mi->getOperand(0).getSubReg();
67 }
68
69 if (!hreg)
70 return 0;
71
72 if (TargetRegisterInfo::isVirtualRegister(hreg))
73 return sub == hsub ? hreg : 0;
74
75 const TargetRegisterClass *rc = mri.getRegClass(reg);
76
77 // Only allow physreg hints in rc.
78 if (sub == 0)
79 return rc->contains(hreg) ? hreg : 0;
80
81 // reg:sub should match the physreg hreg.
82 return tri.getMatchingSuperReg(hreg, sub, rc);
Lang Hamesa937f222009-12-14 06:49:42 +000083}
Jakob Stoklund Olesendf30cf92010-08-10 00:02:26 +000084
85void VirtRegAuxInfo::CalculateWeightAndHint(LiveInterval &li) {
86 MachineRegisterInfo &mri = mf_.getRegInfo();
87 const TargetRegisterInfo &tri = *mf_.getTarget().getRegisterInfo();
88 MachineBasicBlock *mbb = 0;
89 MachineLoop *loop = 0;
90 unsigned loopDepth = 0;
91 bool isExiting = false;
92 float totalWeight = 0;
93 SmallPtrSet<MachineInstr*, 8> visited;
94
95 // Find the best physreg hist and the best virtreg hint.
96 float bestPhys = 0, bestVirt = 0;
97 unsigned hintPhys = 0, hintVirt = 0;
98
99 // Don't recompute a target specific hint.
100 bool noHint = mri.getRegAllocationHint(li.reg).first != 0;
101
102 for (MachineRegisterInfo::reg_iterator I = mri.reg_begin(li.reg);
103 MachineInstr *mi = I.skipInstruction();) {
104 if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue())
105 continue;
106 if (!visited.insert(mi))
107 continue;
108
109 // Get loop info for mi.
110 if (mi->getParent() != mbb) {
111 mbb = mi->getParent();
112 loop = loops_.getLoopFor(mbb);
113 loopDepth = loop ? loop->getLoopDepth() : 0;
114 isExiting = loop ? loop->isLoopExiting(mbb) : false;
115 }
116
117 // Calculate instr weight.
118 bool reads, writes;
119 tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
120 float weight = LiveIntervals::getSpillWeight(writes, reads, loopDepth);
121
122 // Give extra weight to what looks like a loop induction variable update.
123 if (writes && isExiting && lis_.isLiveOutOfMBB(li, mbb))
124 weight *= 3;
125
126 totalWeight += weight;
127
128 // Get allocation hints from copies.
129 if (noHint || !mi->isCopy())
130 continue;
131 unsigned hint = copyHint(mi, li.reg, tri, mri);
132 if (!hint)
133 continue;
134 float hweight = hint_[hint] += weight;
135 if (TargetRegisterInfo::isPhysicalRegister(hint)) {
136 if (hweight > bestPhys && lis_.isAllocatable(hint))
137 bestPhys = hweight, hintPhys = hint;
138 } else {
139 if (hweight > bestVirt)
140 bestVirt = hweight, hintVirt = hint;
141 }
142 }
143
144 hint_.clear();
145
146 // Always prefer the physreg hint.
147 if (unsigned hint = hintPhys ? hintPhys : hintVirt) {
148 mri.setRegAllocationHint(li.reg, 0, hint);
149 // Weakly boost the spill weifght of hinted registers.
150 totalWeight *= 1.01F;
151 }
152
153 // Mark li as unspillable if all live ranges are tiny.
154 if (li.isZeroLength()) {
155 li.markNotSpillable();
156 return;
157 }
158
159 // If all of the definitions of the interval are re-materializable,
160 // it is a preferred candidate for spilling. If none of the defs are
161 // loads, then it's potentially very cheap to re-materialize.
162 // FIXME: this gets much more complicated once we support non-trivial
163 // re-materialization.
164 bool isLoad = false;
165 SmallVector<LiveInterval*, 4> spillIs;
166 if (lis_.isReMaterializable(li, spillIs, isLoad)) {
167 if (isLoad)
168 totalWeight *= 0.9F;
169 else
170 totalWeight *= 0.5F;
171 }
172
173 li.weight = totalWeight;
174 lis_.normalizeSpillWeight(li);
175}
176
Jakob Stoklund Olesen9db3ea42010-08-10 18:37:40 +0000177void VirtRegAuxInfo::CalculateRegClass(unsigned reg) {
178 MachineRegisterInfo &mri = mf_.getRegInfo();
179 const TargetRegisterInfo *tri = mf_.getTarget().getRegisterInfo();
180 const TargetRegisterClass *orc = mri.getRegClass(reg);
181 SmallPtrSet<const TargetRegisterClass*,8> rcs;
182
183 for (MachineRegisterInfo::reg_nodbg_iterator I = mri.reg_nodbg_begin(reg),
184 E = mri.reg_nodbg_end(); I != E; ++I)
185 if (const TargetRegisterClass *rc =
186 I->getDesc().getRegClass(I.getOperandNo(), tri))
187 rcs.insert(rc);
188
189 // If we found no regclass constraints, just leave reg as is.
190 // In theory, we could inflate to the largest superclass of reg's existing
191 // class, but that might not be legal for the current cpu setting.
192 // This could happen if reg is only used by COPY instructions, so we may need
193 // to improve on this.
194 if (rcs.empty()) {
195 DEBUG(dbgs() << "Not inflating unconstrained" << orc->getName() << ":%reg"
196 << reg << ".\n");
197 return;
198 }
199
200 // Compute the intersection of all classes in rcs.
201 // This ought to be independent of iteration order, but if the target register
202 // classes don't form a proper algebra, it is possible to get different
203 // results. The solution is to make sure the intersection of any two register
204 // classes is also a register class or the null set.
205 const TargetRegisterClass *rc = 0;
206 for (SmallPtrSet<const TargetRegisterClass*,8>::iterator I = rcs.begin(),
207 E = rcs.end(); I != E; ++I) {
208 rc = rc ? getCommonSubClass(rc, *I) : *I;
209 assert(rc && "Incompatible regclass constraints found");
210 }
211
212 if (rc == orc)
213 return;
214 DEBUG(dbgs() << "Inflating " << orc->getName() << ":%reg" << reg << " to "
215 << rc->getName() <<".\n");
216 mri.setRegClass(reg, rc);
217}