1 //===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===//
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 implements the spill code placement analysis.
12 // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
13 // basic blocks are weighted by the block frequency and added to become the node
16 // Transparent basic blocks have the variable live through, but don't care if it
17 // is spilled or in a register. These blocks become connections in the Hopfield
18 // network, again weighted by block frequency.
20 // The Hopfield network minimizes (possibly locally) its energy function:
22 // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
24 // The energy function represents the expected spill code execution frequency,
25 // or the cost of spilling. This is a Lyapunov function which never increases
26 // when a node is updated. It is guaranteed to converge to a local minimum.
28 //===----------------------------------------------------------------------===//
30 #include "SpillPlacement.h"
31 #include "llvm/ADT/BitVector.h"
32 #include "llvm/CodeGen/EdgeBundles.h"
33 #include "llvm/CodeGen/MachineBasicBlock.h"
34 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
35 #include "llvm/CodeGen/MachineFunction.h"
36 #include "llvm/CodeGen/MachineLoopInfo.h"
37 #include "llvm/CodeGen/Passes.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/ManagedStatic.h"
43 #define DEBUG_TYPE "spillplacement"
45 char SpillPlacement::ID
= 0;
46 INITIALIZE_PASS_BEGIN(SpillPlacement
, "spill-code-placement",
47 "Spill Code Placement Analysis", true, true)
48 INITIALIZE_PASS_DEPENDENCY(EdgeBundles
)
49 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
50 INITIALIZE_PASS_END(SpillPlacement
, "spill-code-placement",
51 "Spill Code Placement Analysis", true, true)
53 char &llvm::SpillPlacementID
= SpillPlacement::ID
;
55 void SpillPlacement::getAnalysisUsage(AnalysisUsage
&AU
) const {
57 AU
.addRequired
<MachineBlockFrequencyInfo
>();
58 AU
.addRequiredTransitive
<EdgeBundles
>();
59 AU
.addRequiredTransitive
<MachineLoopInfo
>();
60 MachineFunctionPass::getAnalysisUsage(AU
);
63 /// Node - Each edge bundle corresponds to a Hopfield node.
65 /// The node contains precomputed frequency data that only depends on the CFG,
66 /// but Bias and Links are computed each time placeSpills is called.
68 /// The node Value is positive when the variable should be in a register. The
69 /// value can change when linked nodes change, but convergence is very fast
70 /// because all weights are positive.
72 struct SpillPlacement::Node
{
73 /// BiasN - Sum of blocks that prefer a spill.
75 /// BiasP - Sum of blocks that prefer a register.
78 /// Value - Output value of this node computed from the Bias and links.
79 /// This is always on of the values {-1, 0, 1}. A positive number means the
80 /// variable should go in a register through this bundle.
83 typedef SmallVector
<std::pair
<BlockFrequency
, unsigned>, 4> LinkVector
;
85 /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
86 /// bundles. The weights are all positive block frequencies.
89 /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
90 BlockFrequency SumLinkWeights
;
92 /// preferReg - Return true when this node prefers to be in a register.
93 bool preferReg() const {
94 // Undecided nodes (Value==0) go on the stack.
98 /// mustSpill - Return True if this node is so biased that it must spill.
99 bool mustSpill() const {
100 // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
101 // BiasN is saturated when MustSpill is set, make sure this still returns
102 // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
103 return BiasN
>= BiasP
+ SumLinkWeights
;
106 /// clear - Reset per-query data, but preserve frequencies that only depend on
108 void clear(const BlockFrequency
&Threshold
) {
109 BiasN
= BiasP
= Value
= 0;
110 SumLinkWeights
= Threshold
;
114 /// addLink - Add a link to bundle b with weight w.
115 void addLink(unsigned b
, BlockFrequency w
) {
116 // Update cached sum.
119 // There can be multiple links to the same bundle, add them up.
120 for (LinkVector::iterator I
= Links
.begin(), E
= Links
.end(); I
!= E
; ++I
)
121 if (I
->second
== b
) {
125 // This must be the first link to b.
126 Links
.push_back(std::make_pair(w
, b
));
129 /// addBias - Bias this node.
130 void addBias(BlockFrequency freq
, BorderConstraint direction
) {
141 BiasN
= BlockFrequency::getMaxFrequency();
146 /// update - Recompute Value from Bias and Links. Return true when node
147 /// preference changes.
148 bool update(const Node nodes
[], const BlockFrequency
&Threshold
) {
149 // Compute the weighted sum of inputs.
150 BlockFrequency SumN
= BiasN
;
151 BlockFrequency SumP
= BiasP
;
152 for (LinkVector::iterator I
= Links
.begin(), E
= Links
.end(); I
!= E
; ++I
) {
153 if (nodes
[I
->second
].Value
== -1)
155 else if (nodes
[I
->second
].Value
== 1)
159 // Each weighted sum is going to be less than the total frequency of the
160 // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
161 // will add a dead zone around 0 for two reasons:
163 // 1. It avoids arbitrary bias when all links are 0 as is possible during
164 // initial iterations.
165 // 2. It helps tame rounding errors when the links nominally sum to 0.
167 bool Before
= preferReg();
168 if (SumN
>= SumP
+ Threshold
)
170 else if (SumP
>= SumN
+ Threshold
)
174 return Before
!= preferReg();
178 bool SpillPlacement::runOnMachineFunction(MachineFunction
&mf
) {
180 bundles
= &getAnalysis
<EdgeBundles
>();
181 loops
= &getAnalysis
<MachineLoopInfo
>();
183 assert(!nodes
&& "Leaking node array");
184 nodes
= new Node
[bundles
->getNumBundles()];
186 // Compute total ingoing and outgoing block frequencies for all bundles.
187 BlockFrequencies
.resize(mf
.getNumBlockIDs());
188 MBFI
= &getAnalysis
<MachineBlockFrequencyInfo
>();
189 setThreshold(MBFI
->getEntryFreq());
191 unsigned Num
= I
.getNumber();
192 BlockFrequencies
[Num
] = MBFI
->getBlockFreq(&I
);
195 // We never change the function.
199 void SpillPlacement::releaseMemory() {
204 /// activate - mark node n as active if it wasn't already.
205 void SpillPlacement::activate(unsigned n
) {
206 if (ActiveNodes
->test(n
))
209 nodes
[n
].clear(Threshold
);
211 // Very large bundles usually come from big switches, indirect branches,
212 // landing pads, or loops with many 'continue' statements. It is difficult to
213 // allocate registers when so many different blocks are involved.
215 // Give a small negative bias to large bundles such that a substantial
216 // fraction of the connected blocks need to be interested before we consider
217 // expanding the region through the bundle. This helps compile time by
218 // limiting the number of blocks visited and the number of links in the
220 if (bundles
->getBlocks(n
).size() > 100) {
222 nodes
[n
].BiasN
= (MBFI
->getEntryFreq() / 16);
226 /// \brief Set the threshold for a given entry frequency.
228 /// Set the threshold relative to \c Entry. Since the threshold is used as a
229 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
231 void SpillPlacement::setThreshold(const BlockFrequency
&Entry
) {
232 // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
233 // it. Divide by 2^13, rounding as appropriate.
234 uint64_t Freq
= Entry
.getFrequency();
235 uint64_t Scaled
= (Freq
>> 13) + bool(Freq
& (1 << 12));
236 Threshold
= std::max(UINT64_C(1), Scaled
);
239 /// addConstraints - Compute node biases and weights from a set of constraints.
240 /// Set a bit in NodeMask for each active node.
241 void SpillPlacement::addConstraints(ArrayRef
<BlockConstraint
> LiveBlocks
) {
242 for (ArrayRef
<BlockConstraint
>::iterator I
= LiveBlocks
.begin(),
243 E
= LiveBlocks
.end(); I
!= E
; ++I
) {
244 BlockFrequency Freq
= BlockFrequencies
[I
->Number
];
247 if (I
->Entry
!= DontCare
) {
248 unsigned ib
= bundles
->getBundle(I
->Number
, 0);
250 nodes
[ib
].addBias(Freq
, I
->Entry
);
253 // Live-out from block?
254 if (I
->Exit
!= DontCare
) {
255 unsigned ob
= bundles
->getBundle(I
->Number
, 1);
257 nodes
[ob
].addBias(Freq
, I
->Exit
);
262 /// addPrefSpill - Same as addConstraints(PrefSpill)
263 void SpillPlacement::addPrefSpill(ArrayRef
<unsigned> Blocks
, bool Strong
) {
264 for (ArrayRef
<unsigned>::iterator I
= Blocks
.begin(), E
= Blocks
.end();
266 BlockFrequency Freq
= BlockFrequencies
[*I
];
269 unsigned ib
= bundles
->getBundle(*I
, 0);
270 unsigned ob
= bundles
->getBundle(*I
, 1);
273 nodes
[ib
].addBias(Freq
, PrefSpill
);
274 nodes
[ob
].addBias(Freq
, PrefSpill
);
278 void SpillPlacement::addLinks(ArrayRef
<unsigned> Links
) {
279 for (ArrayRef
<unsigned>::iterator I
= Links
.begin(), E
= Links
.end(); I
!= E
;
281 unsigned Number
= *I
;
282 unsigned ib
= bundles
->getBundle(Number
, 0);
283 unsigned ob
= bundles
->getBundle(Number
, 1);
285 // Ignore self-loops.
290 if (nodes
[ib
].Links
.empty() && !nodes
[ib
].mustSpill())
291 Linked
.push_back(ib
);
292 if (nodes
[ob
].Links
.empty() && !nodes
[ob
].mustSpill())
293 Linked
.push_back(ob
);
294 BlockFrequency Freq
= BlockFrequencies
[Number
];
295 nodes
[ib
].addLink(ob
, Freq
);
296 nodes
[ob
].addLink(ib
, Freq
);
300 bool SpillPlacement::scanActiveBundles() {
302 RecentPositive
.clear();
303 for (int n
= ActiveNodes
->find_first(); n
>=0; n
= ActiveNodes
->find_next(n
)) {
304 nodes
[n
].update(nodes
, Threshold
);
305 // A node that must spill, or a node without any links is not going to
306 // change its value ever again, so exclude it from iterations.
307 if (nodes
[n
].mustSpill())
309 if (!nodes
[n
].Links
.empty())
311 if (nodes
[n
].preferReg())
312 RecentPositive
.push_back(n
);
314 return !RecentPositive
.empty();
317 /// iterate - Repeatedly update the Hopfield nodes until stability or the
318 /// maximum number of iterations is reached.
319 /// @param Linked - Numbers of linked nodes that need updating.
320 void SpillPlacement::iterate() {
321 // First update the recently positive nodes. They have likely received new
322 // negative bias that will turn them off.
323 while (!RecentPositive
.empty())
324 nodes
[RecentPositive
.pop_back_val()].update(nodes
, Threshold
);
329 // Run up to 10 iterations. The edge bundle numbering is closely related to
330 // basic block numbering, so there is a strong tendency towards chains of
331 // linked nodes with sequential numbers. By scanning the linked nodes
332 // backwards and forwards, we make it very likely that a single node can
333 // affect the entire network in a single iteration. That means very fast
334 // convergence, usually in a single iteration.
335 for (unsigned iteration
= 0; iteration
!= 10; ++iteration
) {
336 // Scan backwards, skipping the last node when iteration is not zero. When
337 // iteration is not zero, the last node was just updated.
338 bool Changed
= false;
339 for (SmallVectorImpl
<unsigned>::const_reverse_iterator I
=
340 iteration
== 0 ? Linked
.rbegin() : std::next(Linked
.rbegin()),
341 E
= Linked
.rend(); I
!= E
; ++I
) {
343 if (nodes
[n
].update(nodes
, Threshold
)) {
345 if (nodes
[n
].preferReg())
346 RecentPositive
.push_back(n
);
349 if (!Changed
|| !RecentPositive
.empty())
352 // Scan forwards, skipping the first node which was just updated.
354 for (SmallVectorImpl
<unsigned>::const_iterator I
=
355 std::next(Linked
.begin()), E
= Linked
.end(); I
!= E
; ++I
) {
357 if (nodes
[n
].update(nodes
, Threshold
)) {
359 if (nodes
[n
].preferReg())
360 RecentPositive
.push_back(n
);
363 if (!Changed
|| !RecentPositive
.empty())
368 void SpillPlacement::prepare(BitVector
&RegBundles
) {
370 RecentPositive
.clear();
371 // Reuse RegBundles as our ActiveNodes vector.
372 ActiveNodes
= &RegBundles
;
373 ActiveNodes
->clear();
374 ActiveNodes
->resize(bundles
->getNumBundles());
378 SpillPlacement::finish() {
379 assert(ActiveNodes
&& "Call prepare() first");
381 // Write preferences back to ActiveNodes.
383 for (int n
= ActiveNodes
->find_first(); n
>=0; n
= ActiveNodes
->find_next(n
))
384 if (!nodes
[n
].preferReg()) {
385 ActiveNodes
->reset(n
);
388 ActiveNodes
= nullptr;