Lines Matching +full:activate +full:- +full:to +full:- +full:activate
1 //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
12 // basic blocks are weighted by the block frequency and added to become the node
21 // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
25 // when a node is updated. It is guaranteed to converge to a local minimum.
27 //===----------------------------------------------------------------------===//
45 #define DEBUG_TYPE "spill-code-placement"
64 /// Node - Each edge bundle corresponds to a Hopfield node.
73 /// BiasN - Sum of blocks that prefer a spill.
76 /// BiasP - Sum of blocks that prefer a register.
79 /// Value - Output value of this node computed from the Bias and links.
80 /// This is always on of the values {-1, 0, 1}. A positive number means the
86 /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
90 /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
93 /// preferReg - Return true when this node prefers to be in a register.
99 /// mustSpill - Return True if this node is so biased that it must spill.
101 // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
107 /// clear - Reset per-query data, but preserve frequencies that only depend on
117 /// addLink - Add a link to bundle b with weight w.
122 // There can be multiple links to the same bundle, add them up.
128 // This must be the first link to b.
132 /// addBias - Bias this node.
149 /// update - Recompute Value from Bias and Links. Return true when node
156 if (nodes[L.second].Value == -1)
162 // Each weighted sum is going to be less than the total frequency of the
163 // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
168 // 2. It helps tame rounding errors when the links nominally sum to 0.
172 Value = -1;
184 // Neighbors that already have the same value are not going to
197 nodes = new Node[bundles->getNumBundles()];
199 TodoList.setUniverse(bundles->getNumBundles());
204 setThreshold(MBFI->getEntryFreq());
207 BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
220 /// activate - mark node n as active if it wasn't already.
221 void SpillPlacement::activate(unsigned n) {
223 if (ActiveNodes->test(n))
225 ActiveNodes->set(n);
229 // landing pads, or loops with many 'continue' statements. It is difficult to
232 // Give a small negative bias to large bundles such that a substantial
233 // fraction of the connected blocks need to be interested before we consider
237 if (bundles->getBlocks(n).size() > 100) {
239 BlockFrequency BiasN = MBFI->getEntryFreq();
247 /// Set the threshold relative to \c Entry. Since the threshold is used as a
248 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
251 // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
258 /// addConstraints - Compute node biases and weights from a set of constraints.
264 // Live-in to block?
266 unsigned ib = bundles->getBundle(LB.Number, false);
267 activate(ib);
271 // Live-out from block?
273 unsigned ob = bundles->getBundle(LB.Number, true);
274 activate(ob);
280 /// addPrefSpill - Same as addConstraints(PrefSpill)
286 unsigned ib = bundles->getBundle(B, false);
287 unsigned ob = bundles->getBundle(B, true);
288 activate(ib);
289 activate(ob);
297 unsigned ib = bundles->getBundle(Number, false);
298 unsigned ob = bundles->getBundle(Number, true);
300 // Ignore self-loops.
303 activate(ib);
304 activate(ob);
313 for (unsigned n : ActiveNodes->set_bits()) {
315 // A node that must spill, or a node without any links is not going to
332 /// iterate - Repeatedly update the Hopfield nodes until stability or the
335 // We do not need to push those node in the todolist.
340 // to addConstraints, addLinks, and co.
342 // The call to ::update will add the nodes that changed into the todolist.
343 unsigned Limit = bundles->getNumBundles() * 10;
344 while(Limit-- > 0 && !TodoList.empty()) {
358 ActiveNodes->clear();
359 ActiveNodes->resize(bundles->getNumBundles());
366 // Write preferences back to ActiveNodes.
368 for (unsigned n : ActiveNodes->set_bits())
370 ActiveNodes->reset(n);
378 auto toString = [](BorderConstraint C) -> StringRef {