1 //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
21 //   E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
27 //===----------------------------------------------------------------------===//
45 #define DEBUG_TYPE "spill-code-placement"
64 /// Node - Each edge bundle corresponds to a Hopfield node.
69 /// The node Value is positive when the variable should be in a register. The
71 /// because all weights are positive.
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
87   /// bundles. The weights are all positive block frequencies.
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.  in mustSpill()
107   /// clear - Reset per-query data, but preserve frequencies that only depend on
117   /// addLink - Add a link to bundle b with weight w.
132   /// addBias - Bias this node.
149   /// update - Recompute Value from Bias and Links. Return true when node
156       if (nodes[L.second].Value == -1)  in update()
163     // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we  in update()
172       Value = -1;  in update()
197   nodes = new Node[bundles->getNumBundles()];  in runOnMachineFunction()
199   TodoList.setUniverse(bundles->getNumBundles());  in runOnMachineFunction()
204   setThreshold(MBFI->getEntryFreq());  in runOnMachineFunction()
207     BlockFrequencies[Num] = MBFI->getBlockFreq(&I);  in runOnMachineFunction()
220 /// activate - mark node n as active if it wasn't already.
223   if (ActiveNodes->test(n))  in activate()
225   ActiveNodes->set(n);  in activate()
233   // fraction of the connected blocks need to be interested before we consider  in activate()
237   if (bundles->getBlocks(n).size() > 100) {  in activate()
239     BlockFrequency BiasN = MBFI->getEntryFreq();  in activate()
248 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
258 /// addConstraints - Compute node biases and weights from a set of constraints.
264     // Live-in to block?  in addConstraints()
266       unsigned ib = bundles->getBundle(LB.Number, false);  in addConstraints()
271     // Live-out from block?  in addConstraints()
273       unsigned ob = bundles->getBundle(LB.Number, true);  in addConstraints()
280 /// addPrefSpill - Same as addConstraints(PrefSpill)
286     unsigned ib = bundles->getBundle(B, false);  in addPrefSpill()
287     unsigned ob = bundles->getBundle(B, true);  in addPrefSpill()
297     unsigned ib = bundles->getBundle(Number, false);  in addLinks()
298     unsigned ob = bundles->getBundle(Number, true);  in addLinks()
300     // Ignore self-loops.  in addLinks()
313   for (unsigned n : ActiveNodes->set_bits()) {  in scanActiveBundles()
332 /// iterate - Repeatedly update the Hopfield nodes until stability or the
343   unsigned Limit = bundles->getNumBundles() * 10;  in iterate()
344   while(Limit-- > 0 && !TodoList.empty()) {  in iterate()
358   ActiveNodes->clear();  in prepare()
359   ActiveNodes->resize(bundles->getNumBundles());  in prepare()
368   for (unsigned n : ActiveNodes->set_bits())  in finish()
370       ActiveNodes->reset(n);  in finish()
378   auto toString = [](BorderConstraint C) -> StringRef {  in print()