• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- SpillPlacement.h - Optimal Spill Code Placement ---------*- C++ -*--===//
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 // This analysis computes the optimal spill code placement between basic blocks.
11 //
12 // The runOnMachineFunction() method only precomputes some profiling information
13 // about the CFG. The real work is done by prepare(), addConstraints(), and
14 // finish() which are called by the register allocator.
15 //
16 // Given a variable that is live across multiple basic blocks, and given
17 // constraints on the basic blocks where the variable is live, determine which
18 // edge bundles should have the variable in a register and which edge bundles
19 // should have the variable in a stack slot.
20 //
21 // The returned bit vector can be used to place optimal spill code at basic
22 // block entries and exits. Spill code placement inside a basic block is not
23 // considered.
24 //
25 //===----------------------------------------------------------------------===//
26 
27 #ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
28 #define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
29 
30 #include "llvm/ADT/ArrayRef.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/SparseSet.h"
33 #include "llvm/CodeGen/MachineFunctionPass.h"
34 #include "llvm/Support/BlockFrequency.h"
35 
36 namespace llvm {
37 
38 class BitVector;
39 class EdgeBundles;
40 class MachineBlockFrequencyInfo;
41 class MachineFunction;
42 class MachineLoopInfo;
43 
44 class SpillPlacement : public MachineFunctionPass {
45   struct Node;
46   const MachineFunction *MF;
47   const EdgeBundles *bundles;
48   const MachineLoopInfo *loops;
49   const MachineBlockFrequencyInfo *MBFI;
50   Node *nodes = nullptr;
51 
52   // Nodes that are active in the current computation. Owned by the prepare()
53   // caller.
54   BitVector *ActiveNodes;
55 
56   // Nodes with active links. Populated by scanActiveBundles.
57   SmallVector<unsigned, 8> Linked;
58 
59   // Nodes that went positive during the last call to scanActiveBundles or
60   // iterate.
61   SmallVector<unsigned, 8> RecentPositive;
62 
63   // Block frequencies are computed once. Indexed by block number.
64   SmallVector<BlockFrequency, 8> BlockFrequencies;
65 
66   /// Decision threshold. A node gets the output value 0 if the weighted sum of
67   /// its inputs falls in the open interval (-Threshold;Threshold).
68   BlockFrequency Threshold;
69 
70   /// List of nodes that need to be updated in ::iterate.
71   SparseSet<unsigned> TodoList;
72 
73 public:
74   static char ID; // Pass identification, replacement for typeid.
75 
SpillPlacement()76   SpillPlacement() : MachineFunctionPass(ID) {}
~SpillPlacement()77   ~SpillPlacement() override { releaseMemory(); }
78 
79   /// BorderConstraint - A basic block has separate constraints for entry and
80   /// exit.
81   enum BorderConstraint {
82     DontCare,  ///< Block doesn't care / variable not live.
83     PrefReg,   ///< Block entry/exit prefers a register.
84     PrefSpill, ///< Block entry/exit prefers a stack slot.
85     PrefBoth,  ///< Block entry prefers both register and stack.
86     MustSpill  ///< A register is impossible, variable must be spilled.
87   };
88 
89   /// BlockConstraint - Entry and exit constraints for a basic block.
90   struct BlockConstraint {
91     unsigned Number;            ///< Basic block number (from MBB::getNumber()).
92     BorderConstraint Entry : 8; ///< Constraint on block entry.
93     BorderConstraint Exit : 8;  ///< Constraint on block exit.
94 
95     /// True when this block changes the value of the live range. This means
96     /// the block has a non-PHI def.  When this is false, a live-in value on
97     /// the stack can be live-out on the stack without inserting a spill.
98     bool ChangesValue;
99   };
100 
101   /// prepare - Reset state and prepare for a new spill placement computation.
102   /// @param RegBundles Bit vector to receive the edge bundles where the
103   ///                   variable should be kept in a register. Each bit
104   ///                   corresponds to an edge bundle, a set bit means the
105   ///                   variable should be kept in a register through the
106   ///                   bundle. A clear bit means the variable should be
107   ///                   spilled. This vector is retained.
108   void prepare(BitVector &RegBundles);
109 
110   /// addConstraints - Add constraints and biases. This method may be called
111   /// more than once to accumulate constraints.
112   /// @param LiveBlocks Constraints for blocks that have the variable live in or
113   ///                   live out.
114   void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
115 
116   /// addPrefSpill - Add PrefSpill constraints to all blocks listed.  This is
117   /// equivalent to calling addConstraint with identical BlockConstraints with
118   /// Entry = Exit = PrefSpill, and ChangesValue = false.
119   ///
120   /// @param Blocks Array of block numbers that prefer to spill in and out.
121   /// @param Strong When true, double the negative bias for these blocks.
122   void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong);
123 
124   /// addLinks - Add transparent blocks with the given numbers.
125   void addLinks(ArrayRef<unsigned> Links);
126 
127   /// scanActiveBundles - Perform an initial scan of all bundles activated by
128   /// addConstraints and addLinks, updating their state. Add all the bundles
129   /// that now prefer a register to RecentPositive.
130   /// Prepare internal data structures for iterate.
131   /// Return true is there are any positive nodes.
132   bool scanActiveBundles();
133 
134   /// iterate - Update the network iteratively until convergence, or new bundles
135   /// are found.
136   void iterate();
137 
138   /// getRecentPositive - Return an array of bundles that became positive during
139   /// the previous call to scanActiveBundles or iterate.
getRecentPositive()140   ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
141 
142   /// finish - Compute the optimal spill code placement given the
143   /// constraints. No MustSpill constraints will be violated, and the smallest
144   /// possible number of PrefX constraints will be violated, weighted by
145   /// expected execution frequencies.
146   /// The selected bundles are returned in the bitvector passed to prepare().
147   /// @return True if a perfect solution was found, allowing the variable to be
148   ///         in a register through all relevant bundles.
149   bool finish();
150 
151   /// getBlockFrequency - Return the estimated block execution frequency per
152   /// function invocation.
getBlockFrequency(unsigned Number)153   BlockFrequency getBlockFrequency(unsigned Number) const {
154     return BlockFrequencies[Number];
155   }
156 
157 private:
158   bool runOnMachineFunction(MachineFunction &mf) override;
159   void getAnalysisUsage(AnalysisUsage &AU) const override;
160   void releaseMemory() override;
161 
162   void activate(unsigned n);
163   void setThreshold(const BlockFrequency &Entry);
164 
165   bool update(unsigned n);
166 };
167 
168 } // end namespace llvm
169 
170 #endif // LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
171