119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-- SpillPlacement.h - Optimal Spill Code Placement --------*- C++ -*--===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This analysis computes the optimal spill code placement between basic blocks. 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The runOnMachineFunction() method only precomputes some profiling information 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// about the CFG. The real work is done by prepare(), addConstraints(), and 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// finish() which are called by the register allocator. 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Given a variable that is live across multiple basic blocks, and given 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// constraints on the basic blocks where the variable is live, determine which 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// edge bundles should have the variable in a register and which edge bundles 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// should have the variable in a stack slot. 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The returned bit vector can be used to place optimal spill code at basic 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// block entries and exits. Spill code placement inside a basic block is not 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// considered. 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifndef LLVM_CODEGEN_SPILLPLACEMENT_H 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define LLVM_CODEGEN_SPILLPLACEMENT_H 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/ArrayRef.h" 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallVector.h" 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunctionPass.h" 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass BitVector; 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass EdgeBundles; 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass MachineBasicBlock; 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass MachineLoopInfo; 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass SpillPlacement : public MachineFunctionPass { 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct Node; 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineFunction *MF; 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const EdgeBundles *bundles; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineLoopInfo *loops; 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node *nodes; 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Nodes that are active in the current computation. Owned by the prepare() 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // caller. 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BitVector *ActiveNodes; 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Nodes with active links. Populated by scanActiveBundles. 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<unsigned, 8> Linked; 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Nodes that went positive during the last call to scanActiveBundles or 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // iterate. 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<unsigned, 8> RecentPositive; 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Block frequencies are computed once. Indexed by block number. 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<float, 4> BlockFrequency; 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static char ID; // Pass identification, replacement for typeid. 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ~SpillPlacement() { releaseMemory(); } 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// BorderConstraint - A basic block has separate constraints for entry and 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// exit. 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum BorderConstraint { 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DontCare, ///< Block doesn't care / variable not live. 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrefReg, ///< Block entry/exit prefers a register. 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrefSpill, ///< Block entry/exit prefers a stack slot. 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrefBoth, ///< Block entry prefers both register and stack. 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MustSpill ///< A register is impossible, variable must be spilled. 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// BlockConstraint - Entry and exit constraints for a basic block. 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct BlockConstraint { 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Number; ///< Basic block number (from MBB::getNumber()). 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BorderConstraint Entry : 8; ///< Constraint on block entry. 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BorderConstraint Exit : 8; ///< Constraint on block exit. 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// True when this block changes the value of the live range. This means 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the block has a non-PHI def. When this is false, a live-in value on 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the stack can be live-out on the stack without inserting a spill. 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool ChangesValue; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// prepare - Reset state and prepare for a new spill placement computation. 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param RegBundles Bit vector to receive the edge bundles where the 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// variable should be kept in a register. Each bit 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// corresponds to an edge bundle, a set bit means the 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// variable should be kept in a register through the 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// bundle. A clear bit means the variable should be 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// spilled. This vector is retained. 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void prepare(BitVector &RegBundles); 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// addConstraints - Add constraints and biases. This method may be called 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// more than once to accumulate constraints. 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param LiveBlocks Constraints for blocks that have the variable live in or 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// live out. 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addConstraints(ArrayRef<BlockConstraint> LiveBlocks); 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// equivalent to calling addConstraint with identical BlockConstraints with 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Entry = Exit = PrefSpill, and ChangesValue = false. 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Blocks Array of block numbers that prefer to spill in and out. 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Strong When true, double the negative bias for these blocks. 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong); 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// addLinks - Add transparent blocks with the given numbers. 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addLinks(ArrayRef<unsigned> Links); 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// scanActiveBundles - Perform an initial scan of all bundles activated by 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// addConstraints and addLinks, updating their state. Add all the bundles 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// that now prefer a register to RecentPositive. 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Prepare internal data structures for iterate. 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return true is there are any positive nodes. 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool scanActiveBundles(); 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// iterate - Update the network iteratively until convergence, or new bundles 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// are found. 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void iterate(); 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getRecentPositive - Return an array of bundles that became positive during 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the previous call to scanActiveBundles or iterate. 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArrayRef<unsigned> getRecentPositive() { return RecentPositive; } 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// finish - Compute the optimal spill code placement given the 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// constraints. No MustSpill constraints will be violated, and the smallest 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// possible number of PrefX constraints will be violated, weighted by 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// expected execution frequencies. 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The selected bundles are returned in the bitvector passed to prepare(). 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return True if a perfect solution was found, allowing the variable to be 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// in a register through all relevant bundles. 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool finish(); 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getBlockFrequency - Return the estimated block execution frequency per 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// function invocation. 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman float getBlockFrequency(unsigned Number) const { 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return BlockFrequency[Number]; 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprivate: 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool runOnMachineFunction(MachineFunction&); 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage&) const; 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void releaseMemory(); 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void activate(unsigned); 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} // end namespace llvm 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 157