1 //===-- SpillPlacement.h - Optimal Spill Code Placement --------*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This analysis computes the optimal spill code placement between basic blocks.
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.
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.
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
25 //===----------------------------------------------------------------------===//
27 #ifndef LLVM_CODEGEN_SPILLPLACEMENT_H
28 #define LLVM_CODEGEN_SPILLPLACEMENT_H
30 #include "llvm/CodeGen/MachineFunctionPass.h"
36 class MachineBasicBlock
;
37 class MachineLoopInfo
;
38 template <typename
> class SmallVectorImpl
;
40 class SpillPlacement
: public MachineFunctionPass
{
42 const MachineFunction
*MF
;
43 const EdgeBundles
*bundles
;
44 const MachineLoopInfo
*loops
;
47 // Nodes that are active in the current computation. Owned by the placeSpills
49 BitVector
*ActiveNodes
;
52 static char ID
; // Pass identification, replacement for typeid.
54 SpillPlacement() : MachineFunctionPass(ID
), nodes(0) {}
55 ~SpillPlacement() { releaseMemory(); }
57 /// BorderConstraint - A basic block has separate constraints for entry and
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.
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.
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
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
);
92 /// getBlockFrequency - Return the estimated block execution frequency per
93 /// function invocation.
94 float getBlockFrequency(const MachineBasicBlock
*);
97 virtual bool runOnMachineFunction(MachineFunction
&);
98 virtual void getAnalysisUsage(AnalysisUsage
&) const;
99 virtual void releaseMemory();
101 void activate(unsigned);
102 void prepareNodes(const SmallVectorImpl
<BlockConstraint
>&);
103 void iterate(const SmallVectorImpl
<unsigned>&);
106 } // end namespace llvm