SpillPlacement.h revision 8bfe50871f9cb1b022483e0e1307ab5b8c9e5650
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. 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/CodeGen/MachineFunctionPass.h" 31 32namespace llvm { 33 34class BitVector; 35class EdgeBundles; 36class MachineBasicBlock; 37class 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 47 // Nodes that are active in the current computation. Owned by the placeSpills 48 // caller. 49 BitVector *ActiveNodes; 50 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. 59 enum BorderConstraint { 60 DontCare, ///< Block doesn't care / variable not live. 61 PrefReg, ///< Block entry/exit prefers a register. 62 PrefSpill, ///< Block entry/exit prefers a stack slot. 63 MustSpill ///< A register is impossible, variable must be spilled. 64 }; 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 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. 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 86 /// spilled. 87 /// @return True if a perfect solution was found, allowing the variable to be 88 /// in a register through all relevant bundles. 89 bool placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks, 90 BitVector &RegBundles); 91 92private: 93 virtual bool runOnMachineFunction(MachineFunction&); 94 virtual void getAnalysisUsage(AnalysisUsage&) const; 95 virtual void releaseMemory(); 96 97 void activate(unsigned); 98 float getBlockFrequency(const MachineBasicBlock*); 99 void prepareNodes(const SmallVectorImpl<BlockConstraint>&); 100 void iterate(const SmallVectorImpl<unsigned>&); 101}; 102 103} // end namespace llvm 104 105#endif 106