SpillPlacement.h revision 70d4370b47cdd375bbea98e50452789fe4f1af04
18bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===-- SpillPlacement.h - Optimal Spill Code Placement --------*- C++ -*--===// 28bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 38bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 48bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 58bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 78bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 88bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 98bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 108bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// This analysis computes the optimal spill code placement between basic blocks. 118bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 128bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The runOnMachineFunction() method only precomputes some profiling information 139efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen// about the CFG. The real work is done by prepare(), addConstraints(), and 149efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen// finish() which are called by the register allocator. 158bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 168bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// Given a variable that is live across multiple basic blocks, and given 178bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// constraints on the basic blocks where the variable is live, determine which 188bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// edge bundles should have the variable in a register and which edge bundles 198bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// should have the variable in a stack slot. 208bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 218bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The returned bit vector can be used to place optimal spill code at basic 228bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// block entries and exits. Spill code placement inside a basic block is not 238bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// considered. 248bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 258bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#ifndef LLVM_CODEGEN_SPILLPLACEMENT_H 288bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#define LLVM_CODEGEN_SPILLPLACEMENT_H 298bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 309efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen#include "llvm/ADT/ArrayRef.h" 3140a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 328bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 338bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 348bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesennamespace llvm { 358bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass BitVector; 378bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass EdgeBundles; 388bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass MachineBasicBlock; 398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass MachineLoopInfo; 408bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 418bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass SpillPlacement : public MachineFunctionPass { 428bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen struct Node; 438bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const MachineFunction *MF; 448bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const EdgeBundles *bundles; 458bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const MachineLoopInfo *loops; 468bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Node *nodes; 478bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 489efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen // Nodes that are active in the current computation. Owned by the prepare() 498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // caller. 508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BitVector *ActiveNodes; 518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 5270d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen // The number of active nodes with a positive bias. 5370d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen unsigned PositiveNodes; 5470d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen 5540a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen // Block frequencies are computed once. Indexed by block number. 5640a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen SmallVector<float, 4> BlockFrequency; 5740a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen 588bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenpublic: 598bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen static char ID; // Pass identification, replacement for typeid. 608bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 618bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 628bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ~SpillPlacement() { releaseMemory(); } 638bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 648bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BorderConstraint - A basic block has separate constraints for entry and 658bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// exit. 668bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen enum BorderConstraint { 678bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen DontCare, ///< Block doesn't care / variable not live. 688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefReg, ///< Block entry/exit prefers a register. 698bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefSpill, ///< Block entry/exit prefers a stack slot. 708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen MustSpill ///< A register is impossible, variable must be spilled. 718bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 738bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BlockConstraint - Entry and exit constraints for a basic block. 748bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen struct BlockConstraint { 758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned Number; ///< Basic block number (from MBB::getNumber()). 768bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Entry : 8; ///< Constraint on block entry. 778bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Exit : 8; ///< Constraint on block exit. 788bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 798bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 809efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// prepare - Reset state and prepare for a new spill placement computation. 818bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @param RegBundles Bit vector to receive the edge bundles where the 828bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// variable should be kept in a register. Each bit 838bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// corresponds to an edge bundle, a set bit means the 848bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// variable should be kept in a register through the 858bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// bundle. A clear bit means the variable should be 869efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// spilled. This vector is retained. 879efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen void prepare(BitVector &RegBundles); 889efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 899efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// addConstraints - Add constraints and biases. This method may be called 909efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// more than once to accumulate constraints. 919efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// @param LiveBlocks Constraints for blocks that have the variable live in or 929efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// live out. DontCare/DontCare means the variable is live 939efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// through the block. DontCare/X means the variable is live 949efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// out, but not live in. 959efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen void addConstraints(ArrayRef<BlockConstraint> LiveBlocks); 969efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 9770d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen /// getPositiveNodes - Return the total number of graph nodes with a positive 9870d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen /// bias after adding constraints. 9970d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen unsigned getPositiveNodes() const { return PositiveNodes; } 10070d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen 1019efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// finish - Compute the optimal spill code placement given the 1029efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// constraints. No MustSpill constraints will be violated, and the smallest 1039efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// possible number of PrefX constraints will be violated, weighted by 1049efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// expected execution frequencies. 1059efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// The selected bundles are returned in the bitvector passed to prepare(). 1068bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @return True if a perfect solution was found, allowing the variable to be 1078bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// in a register through all relevant bundles. 1089efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen bool finish(); 1098bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 110b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// getBlockFrequency - Return the estimated block execution frequency per 111b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// function invocation. 11240a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen float getBlockFrequency(unsigned Number) const { 11340a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen return BlockFrequency[Number]; 11440a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen } 115b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1168bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenprivate: 1178bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 1188bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage&) const; 1198bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void releaseMemory(); 1208bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1218bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void activate(unsigned); 1228bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void iterate(const SmallVectorImpl<unsigned>&); 1238bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen}; 1248bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1258bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} // end namespace llvm 1268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#endif 128