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 52f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Nodes with active links. Populated by scanActiveBundles. 53f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SmallVector<unsigned, 8> Linked; 54f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 55f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Nodes that went positive during the last call to scanActiveBundles or 56f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // iterate. 57f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen SmallVector<unsigned, 8> RecentPositive; 5870d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen 5940a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen // Block frequencies are computed once. Indexed by block number. 6040a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen SmallVector<float, 4> BlockFrequency; 6140a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen 628bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenpublic: 638bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen static char ID; // Pass identification, replacement for typeid. 648bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 658bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} 668bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ~SpillPlacement() { releaseMemory(); } 678bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BorderConstraint - A basic block has separate constraints for entry and 698bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// exit. 708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen enum BorderConstraint { 718bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen DontCare, ///< Block doesn't care / variable not live. 728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefReg, ///< Block entry/exit prefers a register. 738bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen PrefSpill, ///< Block entry/exit prefers a stack slot. 740e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen PrefBoth, ///< Block entry prefers both register and stack. 758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen MustSpill ///< A register is impossible, variable must be spilled. 768bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 778bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 788bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// BlockConstraint - Entry and exit constraints for a basic block. 798bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen struct BlockConstraint { 808bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned Number; ///< Basic block number (from MBB::getNumber()). 818bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Entry : 8; ///< Constraint on block entry. 828bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen BorderConstraint Exit : 8; ///< Constraint on block exit. 830e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen 840e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// True when this block changes the value of the live range. This means 850e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// the block has a non-PHI def. When this is false, a live-in value on 860e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// the stack can be live-out on the stack without inserting a spill. 870e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen bool ChangesValue; 888bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen }; 898bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 909efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// prepare - Reset state and prepare for a new spill placement computation. 918bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @param RegBundles Bit vector to receive the edge bundles where the 928bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// variable should be kept in a register. Each bit 938bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// corresponds to an edge bundle, a set bit means the 948bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// variable should be kept in a register through the 958bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// bundle. A clear bit means the variable should be 969efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// spilled. This vector is retained. 979efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen void prepare(BitVector &RegBundles); 989efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 999efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// addConstraints - Add constraints and biases. This method may be called 1009efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// more than once to accumulate constraints. 1019efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// @param LiveBlocks Constraints for blocks that have the variable live in or 1027b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// live out. 1039efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen void addConstraints(ArrayRef<BlockConstraint> LiveBlocks); 1049efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen 1050e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is 1060e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// equivalent to calling addConstraint with identical BlockConstraints with 1070e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// Entry = Exit = PrefSpill, and ChangesValue = false. 1080e0a8806d49038b60a0c20427d9f410b01cbb012Jakob Stoklund Olesen /// 109e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen /// @param Blocks Array of block numbers that prefer to spill in and out. 110b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen /// @param Strong When true, double the negative bias for these blocks. 111b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong); 112e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen 1137b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen /// addLinks - Add transparent blocks with the given numbers. 1147b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen void addLinks(ArrayRef<unsigned> Links); 1157b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 116f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// scanActiveBundles - Perform an initial scan of all bundles activated by 117f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// addConstraints and addLinks, updating their state. Add all the bundles 118f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// that now prefer a register to RecentPositive. 119f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// Prepare internal data structures for iterate. 120f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// Return true is there are any positive nodes. 121f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool scanActiveBundles(); 122f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 123f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// iterate - Update the network iteratively until convergence, or new bundles 124f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// are found. 125f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen void iterate(); 126f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 127f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// getRecentPositive - Return an array of bundles that became positive during 128f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// the previous call to scanActiveBundles or iterate. 129f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ArrayRef<unsigned> getRecentPositive() { return RecentPositive; } 13070d4370b47cdd375bbea98e50452789fe4f1af04Jakob Stoklund Olesen 1319efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// finish - Compute the optimal spill code placement given the 1329efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// constraints. No MustSpill constraints will be violated, and the smallest 1339efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// possible number of PrefX constraints will be violated, weighted by 1349efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// expected execution frequencies. 1359efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen /// The selected bundles are returned in the bitvector passed to prepare(). 1368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// @return True if a perfect solution was found, allowing the variable to be 1378bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// in a register through all relevant bundles. 1389efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen bool finish(); 1398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 140b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// getBlockFrequency - Return the estimated block execution frequency per 141b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// function invocation. 14240a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen float getBlockFrequency(unsigned Number) const { 14340a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen return BlockFrequency[Number]; 14440a42a2ccaaa19a109667ed7abf224cc8733cd9cJakob Stoklund Olesen } 145b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 1468bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenprivate: 1478bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 1488bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage&) const; 1498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen virtual void releaseMemory(); 1508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void activate(unsigned); 1528bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen}; 1538bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1548bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} // end namespace llvm 1558bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1568bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#endif 157