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 { 78e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun // The live range set that is live-in to this block. The algorithms can 79b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // handle multiple non-overlapping live ranges simultaneously. 80e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LiveRange &LR; 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 94e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : LR(LR), DomNode(node), Kill(kill), Value(nullptr) {} 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. 114e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, 115e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun SlotIndex Kill, unsigned PhysReg); 116b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 117b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// updateSSA - Compute the values that will be live in to all requested 118b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. 119b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 120b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Every live-in block must be jointly dominated by the added live-out 121b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// blocks. No values are read from the live ranges. 122631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void updateSSA(); 123b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 124beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen /// Add liveness as specified in the LiveIn vector. 125beda6ab879e35b6f7d998da980b30e3844d3bbebJakob Stoklund Olesen void updateLiveIns(); 126b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 127b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesenpublic: 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr), 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DomTree(nullptr), Alloc(nullptr) {} 130631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen 131b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 132b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // High-level interface. 133b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 134b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 135b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Calculate live ranges from scratch. 136b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 137b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 138b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// reset - Prepare caches for a new set of non-overlapping live ranges. The 139b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// caches must be reset before attempting calculations with a live range 140b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// that may overlap a previously computed live range, and before the first 141b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live range in a function. If live ranges are not known to be 142b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// non-overlapping, call reset before each. 143631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void reset(const MachineFunction *MF, 144631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen SlotIndexes*, 145631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen MachineDominatorTree*, 146631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen VNInfo::Allocator*); 147b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 148b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 149b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Mid-level interface. 150b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 151b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 152b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Modify existing live ranges. 153b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 154b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 155b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// extend - Extend the live range of LI to reach Kill. 156b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 157b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// The existing values in LI must be live so they jointly dominate Kill. If 158b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Kill is not dominated by a single existing value, PHI-defs are inserted 159b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// as required to preserve SSA form. If Kill is known to be dominated by a 160b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// single existing value, Alloc may be null. 161c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// 162c8981f2e3d6237742714883256cd778acf0eeebeJakob Stoklund Olesen /// PhysReg, when set, is used to verify live-in lists on basic blocks. 163e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0); 164b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 1654e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDefs - Create a dead def in LI for every def operand of Reg. 1664e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// Each instruction defining Reg gets a new VNInfo with a corresponding 1674e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// minimal live range. 168e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void createDeadDefs(LiveRange &LR, unsigned Reg); 1694e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1704e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDefs - Create a dead def in LI for every def of LI->reg. 171e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void createDeadDefs(LiveInterval &LI) { 172e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun createDeadDefs(LI, LI.reg); 1734e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 1744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// extendToUses - Extend the live range of LI to reach all uses of Reg. 176b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 177b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// All uses must be jointly dominated by existing liveness. PHI-defs are 178b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// inserted as needed to preserve SSA form. 179e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void extendToUses(LiveRange &LR, unsigned Reg); 1804e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 1814e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// extendToUses - Extend the live range of LI to reach all uses of LI->reg. 182e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void extendToUses(LiveInterval &LI) { 183e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun extendToUses(LI, LI.reg); 1844e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 185b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 186b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 187b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Low-level interface. 188b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen //===--------------------------------------------------------------------===// 189b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 190b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // These functions can be used to compute live ranges where the live-in and 191b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // live-out blocks are already known, but the SSA value in each block is 192b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // unknown. 193b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 194b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // After calling reset(), add known live-out values and known live-in blocks. 195b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Then call calculateValues() to compute the actual value that is 196b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // live-in to each block, and add liveness to the live ranges. 197b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // 198b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 199b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue - Indicate that VNI is live out from MBB. The 200b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// calculateValues() function will not add liveness for MBB, the caller 201b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// should take care of that. 202b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 203b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// VNI may be null only if MBB is a live-through block also passed to 204b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// addLiveInBlock(). 205b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { 206b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen Seen.set(MBB->getNumber()); 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LiveOut[MBB] = LiveOutPair(VNI, nullptr); 208b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 209b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 210b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// addLiveInBlock - Add a block with an unknown live-in value. This 211b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// function can only be called once per basic block. Once the live-in value 212b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// has been determined, calculateValues() will add liveness to LI. 213b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 2143b9c5eb589de17694dd4cec116eee5c704e7bd2eNAKAMURA Takumi /// @param LR The live range that is live-in to the block. 215b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// @param DomNode The domtree node for the block. 216b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// @param Kill Index in block where LI is killed. If the value is 217b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// live-through, set Kill = SLotIndex() and also call 218b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue(MBB, 0). 219e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun void addLiveInBlock(LiveRange &LR, 220b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen MachineDomTreeNode *DomNode, 221b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen SlotIndex Kill = SlotIndex()) { 222e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); 223b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen } 224b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 225b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// calculateValues - Calculate the value that will be live-in to each block 226b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA 227b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// form. Add liveness to all live-in blocks up to the Kill point, or the 228b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// whole block for live-through blocks. 229b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// 230b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// Every predecessor of a live-in block must have been given a value with 231b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen /// setLiveOutValue, the value may be null for live-trough blocks. 232631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen void calculateValues(); 233b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen}; 234b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 235b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen} // end namespace llvm 236b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 237b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#endif 238