SpillPlacement.h (218893) | SpillPlacement.h (221345) |
---|---|
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 | 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 placeSpills() which is called by the 14// register allocator. | 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_CODEGEN_SPILLPLACEMENT_H 28#define LLVM_CODEGEN_SPILLPLACEMENT_H 29 | 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_CODEGEN_SPILLPLACEMENT_H 28#define LLVM_CODEGEN_SPILLPLACEMENT_H 29 |
30#include "llvm/ADT/ArrayRef.h" 31#include "llvm/ADT/SmallVector.h" |
|
30#include "llvm/CodeGen/MachineFunctionPass.h" 31 32namespace llvm { 33 34class BitVector; 35class EdgeBundles; 36class MachineBasicBlock; 37class MachineLoopInfo; | 32#include "llvm/CodeGen/MachineFunctionPass.h" 33 34namespace llvm { 35 36class BitVector; 37class EdgeBundles; 38class MachineBasicBlock; 39class MachineLoopInfo; |
38template <typename> class SmallVectorImpl; | |
39 40class SpillPlacement : public MachineFunctionPass { 41 struct Node; 42 const MachineFunction *MF; 43 const EdgeBundles *bundles; 44 const MachineLoopInfo *loops; 45 Node *nodes; 46 | 40 41class SpillPlacement : public MachineFunctionPass { 42 struct Node; 43 const MachineFunction *MF; 44 const EdgeBundles *bundles; 45 const MachineLoopInfo *loops; 46 Node *nodes; 47 |
47 // Nodes that are active in the current computation. Owned by the placeSpills | 48 // Nodes that are active in the current computation. Owned by the prepare() |
48 // caller. 49 BitVector *ActiveNodes; 50 | 49 // caller. 50 BitVector *ActiveNodes; 51 |
52 // Nodes with active links. Populated by scanActiveBundles. 53 SmallVector<unsigned, 8> Linked; 54 55 // Nodes that went positive during the last call to scanActiveBundles or 56 // iterate. 57 SmallVector<unsigned, 8> RecentPositive; 58 59 // Block frequencies are computed once. Indexed by block number. 60 SmallVector<float, 4> BlockFrequency; 61 |
|
51public: 52 static char ID; // Pass identification, replacement for typeid. 53 54 SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 55 ~SpillPlacement() { releaseMemory(); } 56 57 /// BorderConstraint - A basic block has separate constraints for entry and 58 /// exit. --- 6 unchanged lines hidden (view full) --- 65 66 /// BlockConstraint - Entry and exit constraints for a basic block. 67 struct BlockConstraint { 68 unsigned Number; ///< Basic block number (from MBB::getNumber()). 69 BorderConstraint Entry : 8; ///< Constraint on block entry. 70 BorderConstraint Exit : 8; ///< Constraint on block exit. 71 }; 72 | 62public: 63 static char ID; // Pass identification, replacement for typeid. 64 65 SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 66 ~SpillPlacement() { releaseMemory(); } 67 68 /// BorderConstraint - A basic block has separate constraints for entry and 69 /// exit. --- 6 unchanged lines hidden (view full) --- 76 77 /// BlockConstraint - Entry and exit constraints for a basic block. 78 struct BlockConstraint { 79 unsigned Number; ///< Basic block number (from MBB::getNumber()). 80 BorderConstraint Entry : 8; ///< Constraint on block entry. 81 BorderConstraint Exit : 8; ///< Constraint on block exit. 82 }; 83 |
73 /// placeSpills - Compute the optimal spill code placement given the 74 /// constraints. No MustSpill constraints will be violated, and the smallest 75 /// possible number of PrefX constraints will be violated, weighted by 76 /// expected execution frequencies. 77 /// @param LiveBlocks Constraints for blocks that have the variable live in or 78 /// live out. DontCare/DontCare means the variable is live 79 /// through the block. DontCare/X means the variable is live 80 /// out, but not live in. | 84 /// prepare - Reset state and prepare for a new spill placement computation. |
81 /// @param RegBundles Bit vector to receive the edge bundles where the 82 /// variable should be kept in a register. Each bit 83 /// corresponds to an edge bundle, a set bit means the 84 /// variable should be kept in a register through the 85 /// bundle. A clear bit means the variable should be | 85 /// @param RegBundles Bit vector to receive the edge bundles where the 86 /// variable should be kept in a register. Each bit 87 /// corresponds to an edge bundle, a set bit means the 88 /// variable should be kept in a register through the 89 /// bundle. A clear bit means the variable should be |
86 /// spilled. | 90 /// spilled. This vector is retained. 91 void prepare(BitVector &RegBundles); 92 93 /// addConstraints - Add constraints and biases. This method may be called 94 /// more than once to accumulate constraints. 95 /// @param LiveBlocks Constraints for blocks that have the variable live in or 96 /// live out. 97 void addConstraints(ArrayRef<BlockConstraint> LiveBlocks); 98 99 /// addLinks - Add transparent blocks with the given numbers. 100 void addLinks(ArrayRef<unsigned> Links); 101 102 /// scanActiveBundles - Perform an initial scan of all bundles activated by 103 /// addConstraints and addLinks, updating their state. Add all the bundles 104 /// that now prefer a register to RecentPositive. 105 /// Prepare internal data structures for iterate. 106 /// Return true is there are any positive nodes. 107 bool scanActiveBundles(); 108 109 /// iterate - Update the network iteratively until convergence, or new bundles 110 /// are found. 111 void iterate(); 112 113 /// getRecentPositive - Return an array of bundles that became positive during 114 /// the previous call to scanActiveBundles or iterate. 115 ArrayRef<unsigned> getRecentPositive() { return RecentPositive; } 116 117 /// finish - Compute the optimal spill code placement given the 118 /// constraints. No MustSpill constraints will be violated, and the smallest 119 /// possible number of PrefX constraints will be violated, weighted by 120 /// expected execution frequencies. 121 /// The selected bundles are returned in the bitvector passed to prepare(). |
87 /// @return True if a perfect solution was found, allowing the variable to be 88 /// in a register through all relevant bundles. | 122 /// @return True if a perfect solution was found, allowing the variable to be 123 /// in a register through all relevant bundles. |
89 bool placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks, 90 BitVector &RegBundles); | 124 bool finish(); |
91 92 /// getBlockFrequency - Return the estimated block execution frequency per 93 /// function invocation. | 125 126 /// getBlockFrequency - Return the estimated block execution frequency per 127 /// function invocation. |
94 float getBlockFrequency(const MachineBasicBlock*); | 128 float getBlockFrequency(unsigned Number) const { 129 return BlockFrequency[Number]; 130 } |
95 96private: 97 virtual bool runOnMachineFunction(MachineFunction&); 98 virtual void getAnalysisUsage(AnalysisUsage&) const; 99 virtual void releaseMemory(); 100 101 void activate(unsigned); | 131 132private: 133 virtual bool runOnMachineFunction(MachineFunction&); 134 virtual void getAnalysisUsage(AnalysisUsage&) const; 135 virtual void releaseMemory(); 136 137 void activate(unsigned); |
102 void prepareNodes(const SmallVectorImpl<BlockConstraint>&); 103 void iterate(const SmallVectorImpl<unsigned>&); | |
104}; 105 106} // end namespace llvm 107 108#endif | 138}; 139 140} // end namespace llvm 141 142#endif |