SpillPlacement.h revision b5fa9333431673aac2ced8dea80152349a85cf6f
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 138bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// about the CFG. The real work is done by placeSpills() which is called by the 148bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 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 308bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 318bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 328bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesennamespace llvm { 338bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 348bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass BitVector; 358bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass EdgeBundles; 368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass MachineBasicBlock; 378bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass MachineLoopInfo; 388bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesentemplate <typename> class SmallVectorImpl; 398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 408bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenclass SpillPlacement : public MachineFunctionPass { 418bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen struct Node; 428bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const MachineFunction *MF; 438bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const EdgeBundles *bundles; 448bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen const MachineLoopInfo *loops; 458bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Node *nodes; 468bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 478bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Nodes that are active in the current computation. Owned by the placeSpills 488bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // caller. 498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BitVector *ActiveNodes; 508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenpublic: 528bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen static char ID; // Pass identification, replacement for typeid. 538bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 548bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 558bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ~SpillPlacement() { releaseMemory(); } 568bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 578bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BorderConstraint - A basic block has separate constraints for entry and 588bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// exit. 598bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen enum BorderConstraint { 608bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen DontCare, ///< Block doesn't care / variable not live. 618bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefReg, ///< Block entry/exit prefers a register. 628bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefSpill, ///< Block entry/exit prefers a stack slot. 638bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen MustSpill ///< A register is impossible, variable must be spilled. 648bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 658bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 668bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BlockConstraint - Entry and exit constraints for a basic block. 678bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen struct BlockConstraint { 688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned Number; ///< Basic block number (from MBB::getNumber()). 698bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Entry : 8; ///< Constraint on block entry. 708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Exit : 8; ///< Constraint on block exit. 718bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 738bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// placeSpills - Compute the optimal spill code placement given the 748bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// constraints. No MustSpill constraints will be violated, and the smallest 758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// possible number of PrefX constraints will be violated, weighted by 768bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// expected execution frequencies. 778bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @param LiveBlocks Constraints for blocks that have the variable live in or 788bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// live out. DontCare/DontCare means the variable is live 798bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// through the block. DontCare/X means the variable is live 808bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// out, but not live in. 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 868bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// spilled. 878bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @return True if a perfect solution was found, allowing the variable to be 888bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// in a register through all relevant bundles. 898bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks, 908bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BitVector &RegBundles); 918bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 92b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// getBlockFrequency - Return the estimated block execution frequency per 93b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// function invocation. 94b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen float getBlockFrequency(const MachineBasicBlock*); 95b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 968bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenprivate: 978bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 988bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage&) const; 998bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void releaseMemory(); 1008bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1018bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void activate(unsigned); 1028bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void prepareNodes(const SmallVectorImpl<BlockConstraint>&); 1038bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void iterate(const SmallVectorImpl<unsigned>&); 1048bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen}; 1058bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1068bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} // end namespace llvm 1078bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1088bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#endif 109