LiveRangeCalc.h revision 55c06ae7afa3f862a6bb4a4441fe485c135f5b5e
1b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===---- LiveRangeCalc.h - Calculate live ranges ---------------*- C++ -*-===// 2b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 3b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 5b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 8b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 10b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// The LiveRangeCalc class can be used to compute live ranges from scratch. It 11b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// caches information about values in the CFG to speed up repeated operations 12b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// on the same live range. The cache can be shared by non-overlapping live 13b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// ranges. SplitKit uses that when computing the live range of split products. 14b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 15b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// A low-level interface is available to clients that know where a variable is 16b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// live, but don't know which value it has as every point. LiveRangeCalc will 17b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// propagate values down the dominator tree, and even insert PHI-defs where 18b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// needed. SplitKit uses this faster interface when possible. 19b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen// 20b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 21b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 22b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#ifndef LLVM_CODEGEN_LIVERANGECALC_H 23b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#define LLVM_CODEGEN_LIVERANGECALC_H 24b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 25b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "llvm/ADT/BitVector.h" 26b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 27b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "llvm/CodeGen/LiveInterval.h" 28b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 29b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesennamespace llvm { 30b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 31b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen/// Forward declarations for MachineDominators.h: 32b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenclass MachineDominatorTree; 33b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 34b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 35b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 3655c06ae7afa3f862a6bb4a4441fe485c135f5b5eBenjamin Kramerclass LiveRangeCalc { 37beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen const MachineFunction *MF; 38631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen const MachineRegisterInfo *MRI; 39631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndexes *Indexes; 40631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MachineDominatorTree *DomTree; 41631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo::Allocator *Alloc; 42631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen 43b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Seen - Bit vector of active entries in LiveOut, also used as a visited 44b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// set by findReachingDefs. One entry per basic block, indexed by block 45b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// number. This is kept as a separate bit vector because it can be cleared 46b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// quickly when switching live ranges. 47b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen BitVector Seen; 48b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 49b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// LiveOutPair - A value and the block that defined it. The domtree node is 50b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)]. 51b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 52b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 53b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// LiveOutMap - Map basic blocks to the value leaving the block. 54b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 55b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 56b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// LiveOut - Map each basic block where a live range is live out to the 57b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live-out value and its defining block. 58b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 59b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// For every basic block, MBB, one of these conditions shall be true: 60b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 61b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 1. !Seen.count(MBB->getNumber()) 62b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Blocks without a Seen bit are ignored. 63b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 2. LiveOut[MBB].second.getNode() == MBB 64b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The live-out value is defined in MBB. 65b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB] 66b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The live-out value passses through MBB. All predecessors must carry 67b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// the same value. 68b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 69b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The domtree node may be null, it can be computed. 70b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 71b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The map can be shared by multiple live ranges as long as no two are 72b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live-out of the same block. 73b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveOutMap LiveOut; 74b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 75b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// LiveInBlock - Information about a basic block where a live range is known 76b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// to be live-in, but the value has not yet been determined. 77b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen struct LiveInBlock { 78b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // LI - The live range that is live-in to this block. The algorithms can 79b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // handle multiple non-overlapping live ranges simultaneously. 80b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveInterval *LI; 81b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 82b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // DomNode - Dominator tree node for the block. 83b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Cleared when the final value has been determined and LI has been updated. 84b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *DomNode; 85b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 86b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Position in block where the live-in range ends, or SlotIndex() if the 87b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // range passes through the block. When the final value has been 88b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // determined, the range from the block start to Kill will be added to LI. 89b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Kill; 90b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 91b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Live-in value filled in by updateSSA once it is known. 92b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen VNInfo *Value; 93b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 94b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveInBlock(LiveInterval *li, MachineDomTreeNode *node, SlotIndex kill) 95b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen : LI(li), DomNode(node), Kill(kill), Value(0) {} 96b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen }; 97b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 98b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// LiveIn - Work list of blocks where the live-in value has yet to be 99b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// determined. This list is typically computed by findReachingDefs() and 100b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// used as a work list by updateSSA(). The low-level interface may also be 101b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// used to add entries directly. 102b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SmallVector<LiveInBlock, 16> LiveIn; 103b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 104beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// Assuming that LI is live-in to KillMBB and killed at Kill, find the set 105beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// of defs that can reach it. 106beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// 107beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// If only one def can reach Kill, all paths from the def to kill are added 108beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// to LI, and the function returns true. 109beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// 110beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// If multiple values can reach Kill, the blocks that need LI to be live in 111beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// are added to the LiveIn array, and the function returns false. 112c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// 113c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// PhysReg, when set, is used to verify live-in lists on basic blocks. 114beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen bool findReachingDefs(LiveInterval *LI, 115beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen MachineBasicBlock *KillMBB, 116beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen SlotIndex Kill, 117beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen unsigned PhysReg); 118b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 119b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// updateSSA - Compute the values that will be live in to all requested 120b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. 121b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 122b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Every live-in block must be jointly dominated by the added live-out 123b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// blocks. No values are read from the live ranges. 124631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void updateSSA(); 125b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 126beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// Add liveness as specified in the LiveIn vector. 127beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen void updateLiveIns(); 128b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 129b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenpublic: 130beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen LiveRangeCalc() : MF(0), MRI(0), Indexes(0), DomTree(0), Alloc(0) {} 131631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen 132b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 133b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // High-level interface. 134b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 135b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 136b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Calculate live ranges from scratch. 137b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 138b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 139b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// reset - Prepare caches for a new set of non-overlapping live ranges. The 140b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// caches must be reset before attempting calculations with a live range 141b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// that may overlap a previously computed live range, and before the first 142b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live range in a function. If live ranges are not known to be 143b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// non-overlapping, call reset before each. 144631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void reset(const MachineFunction *MF, 145631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndexes*, 146631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MachineDominatorTree*, 147631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo::Allocator*); 148b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 149b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 150b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Mid-level interface. 151b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 152b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 153b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Modify existing live ranges. 154b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 155b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 156b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// extend - Extend the live range of LI to reach Kill. 157b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 158b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The existing values in LI must be live so they jointly dominate Kill. If 159b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Kill is not dominated by a single existing value, PHI-defs are inserted 160b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// as required to preserve SSA form. If Kill is known to be dominated by a 161b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// single existing value, Alloc may be null. 162c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// 163c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// PhysReg, when set, is used to verify live-in lists on basic blocks. 164c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen void extend(LiveInterval *LI, SlotIndex Kill, unsigned PhysReg = 0); 165b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 1664e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDefs - Create a dead def in LI for every def operand of Reg. 1674e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// Each instruction defining Reg gets a new VNInfo with a corresponding 1684e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// minimal live range. 1694e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen void createDeadDefs(LiveInterval *LI, unsigned Reg); 1704e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1714e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDefs - Create a dead def in LI for every def of LI->reg. 1724e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen void createDeadDefs(LiveInterval *LI) { 1734e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen createDeadDefs(LI, LI->reg); 1744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 1754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1764e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// extendToUses - Extend the live range of LI to reach all uses of Reg. 177b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 178b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// All uses must be jointly dominated by existing liveness. PHI-defs are 179b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// inserted as needed to preserve SSA form. 1804e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen void extendToUses(LiveInterval *LI, unsigned Reg); 1814e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1824e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// extendToUses - Extend the live range of LI to reach all uses of LI->reg. 1834e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen void extendToUses(LiveInterval *LI) { 1844e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen extendToUses(LI, LI->reg); 1854e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 186b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 187b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 188b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Low-level interface. 189b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 190b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 191b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // These functions can be used to compute live ranges where the live-in and 192b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // live-out blocks are already known, but the SSA value in each block is 193b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // unknown. 194b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 195b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // After calling reset(), add known live-out values and known live-in blocks. 196b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Then call calculateValues() to compute the actual value that is 197b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // live-in to each block, and add liveness to the live ranges. 198b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 199b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 200b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue - Indicate that VNI is live out from MBB. The 201b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// calculateValues() function will not add liveness for MBB, the caller 202b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// should take care of that. 203b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 204b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// VNI may be null only if MBB is a live-through block also passed to 205b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// addLiveInBlock(). 206b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { 207b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.set(MBB->getNumber()); 208edd4f8ba4bed5b999c6a726b7991241cf1840350NAKAMURA Takumi LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0); 209b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 210b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 211b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// addLiveInBlock - Add a block with an unknown live-in value. This 212b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// function can only be called once per basic block. Once the live-in value 213b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// has been determined, calculateValues() will add liveness to LI. 214b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 215b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// @param LI The live range that is live-in to the block. 216b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// @param DomNode The domtree node for the block. 217b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// @param Kill Index in block where LI is killed. If the value is 218b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live-through, set Kill = SLotIndex() and also call 219b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue(MBB, 0). 220b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen void addLiveInBlock(LiveInterval *LI, 221b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *DomNode, 222b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Kill = SlotIndex()) { 223b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen LiveIn.push_back(LiveInBlock(LI, DomNode, Kill)); 224b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 225b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 226b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// calculateValues - Calculate the value that will be live-in to each block 227b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA 228b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// form. Add liveness to all live-in blocks up to the Kill point, or the 229b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// whole block for live-through blocks. 230b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 231b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Every predecessor of a live-in block must have been given a value with 232b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue, the value may be null for live-trough blocks. 233631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void calculateValues(); 234b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen}; 235b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 236b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} // end namespace llvm 237b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 238b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#endif 239