LiveRangeCalc.h revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
1dcefb588d556828af570221b2dc276a6376c8557Jens Axboe//===---- LiveRangeCalc.h - Calculate live ranges ---------------*- C++ -*-===// 2dcefb588d556828af570221b2dc276a6376c8557Jens Axboe// 3dcefb588d556828af570221b2dc276a6376c8557Jens Axboe// The LLVM Compiler Infrastructure 441666588eed4ed830b1fabd0458eb2b0a93f0147Jens Axboe// 5836fcc0fceb233ebcc41ee63b4ea5cae20b678a4Jens Axboe// This file is distributed under the University of Illinois Open Source 6836fcc0fceb233ebcc41ee63b4ea5cae20b678a4Jens Axboe// License. See LICENSE.TXT for details. 741666588eed4ed830b1fabd0458eb2b0a93f0147Jens Axboe// 8ec41265e81c70d8573d1359e27876c37c30c7d9dJens Axboe//===----------------------------------------------------------------------===// 941666588eed4ed830b1fabd0458eb2b0a93f0147Jens Axboe// 10ec41265e81c70d8573d1359e27876c37c30c7d9dJens Axboe// The LiveRangeCalc class can be used to compute live ranges from scratch. It 1167bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// caches information about values in the CFG to speed up repeated operations 1267bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// on the same live range. The cache can be shared by non-overlapping live 1367bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// ranges. SplitKit uses that when computing the live range of split products. 1467bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// 1567bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// A low-level interface is available to clients that know where a variable is 1667bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// live, but don't know which value it has as every point. LiveRangeCalc will 1767bf982340d95ca98098ea050b54b4c7adb116c0Jens Axboe// propagate values down the dominator tree, and even insert PHI-defs where 1856785384eb15a937f275292109603e51a5191365Jens Axboe// needed. SplitKit uses this faster interface when possible. 19dcefb588d556828af570221b2dc276a6376c8557Jens Axboe// 20dcefb588d556828af570221b2dc276a6376c8557Jens Axboe//===----------------------------------------------------------------------===// 210c41214ff4e6f31f8df64aac37be7853aada6f1fRadha Ramachandran 220c41214ff4e6f31f8df64aac37be7853aada6f1fRadha Ramachandran#ifndef LLVM_CODEGEN_LIVERANGECALC_H 230c41214ff4e6f31f8df64aac37be7853aada6f1fRadha Ramachandran#define LLVM_CODEGEN_LIVERANGECALC_H 240c41214ff4e6f31f8df64aac37be7853aada6f1fRadha Ramachandran 2538dad62d5154ffaad445bd0231b271b9a46a5190Jens Axboe#include "llvm/ADT/BitVector.h" 260d29de831183dfd049c97a03008d425ce21e2fa4Jens Axboe#include "llvm/ADT/IndexedMap.h" 271ef2b6be973eded12827990ae1a9eb28b7b20be7Jens Axboe#include "llvm/CodeGen/LiveInterval.h" 2882af2a7ca1a543b41c003de69d5e3c36860f47d5Jens Axboe 29dcefb588d556828af570221b2dc276a6376c8557Jens Axboenamespace llvm { 30dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 31dcefb588d556828af570221b2dc276a6376c8557Jens Axboe/// Forward declarations for MachineDominators.h: 32dcefb588d556828af570221b2dc276a6376c8557Jens Axboeclass MachineDominatorTree; 33dcefb588d556828af570221b2dc276a6376c8557Jens Axboetemplate <class NodeT> class DomTreeNodeBase; 34dcefb588d556828af570221b2dc276a6376c8557Jens Axboetypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 35dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 36dcefb588d556828af570221b2dc276a6376c8557Jens Axboeclass LiveRangeCalc { 37dcefb588d556828af570221b2dc276a6376c8557Jens Axboe const MachineFunction *MF; 38d72be5454c8c5378f16804ff9b8d1afe8729a380Jens Axboe const MachineRegisterInfo *MRI; 39d72be5454c8c5378f16804ff9b8d1afe8729a380Jens Axboe SlotIndexes *Indexes; 40d72be5454c8c5378f16804ff9b8d1afe8729a380Jens Axboe MachineDominatorTree *DomTree; 41d72be5454c8c5378f16804ff9b8d1afe8729a380Jens Axboe VNInfo::Allocator *Alloc; 42dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 43bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe /// Seen - Bit vector of active entries in LiveOut, also used as a visited 44bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe /// set by findReachingDefs. One entry per basic block, indexed by block 45bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe /// number. This is kept as a separate bit vector because it can be cleared 46bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe /// quickly when switching live ranges. 47bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe BitVector Seen; 48bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe 49dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// LiveOutPair - A value and the block that defined it. The domtree node is 50dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)]. 51dcefb588d556828af570221b2dc276a6376c8557Jens Axboe typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 52dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 53da0a7bd224bb9331f27bb4b20394dd5c8fa3acb0Juan Casse /// LiveOutMap - Map basic blocks to the value leaving the block. 54d72be5454c8c5378f16804ff9b8d1afe8729a380Jens Axboe typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 55dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 56dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// LiveOut - Map each basic block where a live range is live out to the 577d9fb455aadc0c0363489591775496f27f4a560aJens Axboe /// live-out value and its defining block. 587d9fb455aadc0c0363489591775496f27f4a560aJens Axboe /// 59363cffa71a96eb4c7595bb8c325a09eb01f766a5Grant Grundler /// For every basic block, MBB, one of these conditions shall be true: 607d9fb455aadc0c0363489591775496f27f4a560aJens Axboe /// 617d9fb455aadc0c0363489591775496f27f4a560aJens Axboe /// 1. !Seen.count(MBB->getNumber()) 62dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// Blocks without a Seen bit are ignored. 63dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// 2. LiveOut[MBB].second.getNode() == MBB 64dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// The live-out value is defined in MBB. 65dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// 3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB] 66dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// The live-out value passses through MBB. All predecessors must carry 67dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// the same value. 689522850758ecad087891710b391b4e77f6bff839Jens Axboe /// 699522850758ecad087891710b391b4e77f6bff839Jens Axboe /// The domtree node may be null, it can be computed. 709522850758ecad087891710b391b4e77f6bff839Jens Axboe /// 719522850758ecad087891710b391b4e77f6bff839Jens Axboe /// The map can be shared by multiple live ranges as long as no two are 729522850758ecad087891710b391b4e77f6bff839Jens Axboe /// live-out of the same block. 739522850758ecad087891710b391b4e77f6bff839Jens Axboe LiveOutMap LiveOut; 74f940128526dbe468a1951cce10c2fe5dbd23875fJens Axboe 75f940128526dbe468a1951cce10c2fe5dbd23875fJens Axboe /// LiveInBlock - Information about a basic block where a live range is known 76225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe /// to be live-in, but the value has not yet been determined. 77225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe struct LiveInBlock { 78225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // The live range set that is live-in to this block. The algorithms can 79225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // handle multiple non-overlapping live ranges simultaneously. 80225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe LiveRange &LR; 81225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe 82225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // DomNode - Dominator tree node for the block. 83225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // Cleared when the final value has been determined and LI has been updated. 84225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe MachineDomTreeNode *DomNode; 85225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe 86225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // Position in block where the live-in range ends, or SlotIndex() if the 87225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // range passes through the block. When the final value has been 88225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // determined, the range from the block start to Kill will be added to LI. 89225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe SlotIndex Kill; 90225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe 91225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe // Live-in value filled in by updateSSA once it is known. 92225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe VNInfo *Value; 93225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe 94225ba9e3433cf27d8ff7b213d9f78b7ef2776c70Jens Axboe LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) 952ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe : LR(LR), DomNode(node), Kill(kill), Value(nullptr) {} 962ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe }; 972ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe 982ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// LiveIn - Work list of blocks where the live-in value has yet to be 992ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// determined. This list is typically computed by findReachingDefs() and 1002ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// used as a work list by updateSSA(). The low-level interface may also be 1012ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// used to add entries directly. 1022ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe SmallVector<LiveInBlock, 16> LiveIn; 1032ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe 1042ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// Assuming that LI is live-in to KillMBB and killed at Kill, find the set 1052ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// of defs that can reach it. 1062ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// 1072ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// If only one def can reach Kill, all paths from the def to kill are added 1082ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// to LI, and the function returns true. 1092ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// 1102ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// If multiple values can reach Kill, the blocks that need LI to be live in 1112ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// are added to the LiveIn array, and the function returns false. 1122ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// 1132ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// PhysReg, when set, is used to verify live-in lists on basic blocks. 1142ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, 1152ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe SlotIndex Kill, unsigned PhysReg); 1162ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe 1172ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// updateSSA - Compute the values that will be live in to all requested 1182ae0b204743d6b4048c6fffd46c6280a70f2ecd1Jens Axboe /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. 119dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// 120dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// Every live-in block must be jointly dominated by the added live-out 121dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// blocks. No values are read from the live ranges. 122dcefb588d556828af570221b2dc276a6376c8557Jens Axboe void updateSSA(); 123dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 124dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// Add liveness as specified in the LiveIn vector. 125dcefb588d556828af570221b2dc276a6376c8557Jens Axboe void updateLiveIns(); 126dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 127dcefb588d556828af570221b2dc276a6376c8557Jens Axboepublic: 128dcefb588d556828af570221b2dc276a6376c8557Jens Axboe LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr), 129dcefb588d556828af570221b2dc276a6376c8557Jens Axboe DomTree(nullptr), Alloc(nullptr) {} 130dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 131dcefb588d556828af570221b2dc276a6376c8557Jens Axboe //===--------------------------------------------------------------------===// 132dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // High-level interface. 133dcefb588d556828af570221b2dc276a6376c8557Jens Axboe //===--------------------------------------------------------------------===// 134dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 135dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // Calculate live ranges from scratch. 136dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 137dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 138dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// reset - Prepare caches for a new set of non-overlapping live ranges. The 139dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// caches must be reset before attempting calculations with a live range 140dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// that may overlap a previously computed live range, and before the first 141dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// live range in a function. If live ranges are not known to be 142dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// non-overlapping, call reset before each. 143dcefb588d556828af570221b2dc276a6376c8557Jens Axboe void reset(const MachineFunction *MF, 144dcefb588d556828af570221b2dc276a6376c8557Jens Axboe SlotIndexes*, 145dcefb588d556828af570221b2dc276a6376c8557Jens Axboe MachineDominatorTree*, 146dcefb588d556828af570221b2dc276a6376c8557Jens Axboe VNInfo::Allocator*); 14736d80bc7c7f7fbc2612941b7dd7ceaf645798c7fJens Axboe 148c73ed24623ad94a5254e8302298797aba2eb1e9aJens Axboe //===--------------------------------------------------------------------===// 149c73ed24623ad94a5254e8302298797aba2eb1e9aJens Axboe // Mid-level interface. 150de890a1e48d40238dac69f302708dde8719de240Steven Lang //===--------------------------------------------------------------------===// 151de890a1e48d40238dac69f302708dde8719de240Steven Lang // 152dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // Modify existing live ranges. 153dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 154dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 155dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// extend - Extend the live range of LI to reach Kill. 1562b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// 1572b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// The existing values in LI must be live so they jointly dominate Kill. If 1582b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// Kill is not dominated by a single existing value, PHI-defs are inserted 1592b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// as required to preserve SSA form. If Kill is known to be dominated by a 1602b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// single existing value, Alloc may be null. 16193bcfd20e37cef8cec350fe06d3a086724c9f257Bruce Cran /// 1622b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe /// PhysReg, when set, is used to verify live-in lists on basic blocks. 1632b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0); 16436d80bc7c7f7fbc2612941b7dd7ceaf645798c7fJens Axboe 16536d80bc7c7f7fbc2612941b7dd7ceaf645798c7fJens Axboe /// createDeadDefs - Create a dead def in LI for every def operand of Reg. 16636d80bc7c7f7fbc2612941b7dd7ceaf645798c7fJens Axboe /// Each instruction defining Reg gets a new VNInfo with a corresponding 167ad705bcb7e79a7cdb9891db17b4c40b13b6c30c3Steven Noonan /// minimal live range. 1682b4f4abec640f36ccdff39de00e74b2234e27116Jens Axboe void createDeadDefs(LiveRange &LR, unsigned Reg); 169dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 170dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// createDeadDefs - Create a dead def in LI for every def of LI->reg. 171a8075704d3392fede7bd7cfa394616fa0eed7ae0Daniel Gollub void createDeadDefs(LiveInterval &LI) { 172a8075704d3392fede7bd7cfa394616fa0eed7ae0Daniel Gollub createDeadDefs(LI, LI.reg); 173a8075704d3392fede7bd7cfa394616fa0eed7ae0Daniel Gollub } 174a8075704d3392fede7bd7cfa394616fa0eed7ae0Daniel Gollub 175a8075704d3392fede7bd7cfa394616fa0eed7ae0Daniel Gollub /// extendToUses - Extend the live range of LI to reach all uses of Reg. 176dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// 177dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// All uses must be jointly dominated by existing liveness. PHI-defs are 178dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// inserted as needed to preserve SSA form. 179dcefb588d556828af570221b2dc276a6376c8557Jens Axboe void extendToUses(LiveRange &LR, unsigned Reg); 180dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 181dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// extendToUses - Extend the live range of LI to reach all uses of LI->reg. 182dcefb588d556828af570221b2dc276a6376c8557Jens Axboe void extendToUses(LiveInterval &LI) { 183dcefb588d556828af570221b2dc276a6376c8557Jens Axboe extendToUses(LI, LI.reg); 184dcefb588d556828af570221b2dc276a6376c8557Jens Axboe } 185dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 186dcefb588d556828af570221b2dc276a6376c8557Jens Axboe //===--------------------------------------------------------------------===// 187dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // Low-level interface. 188dcefb588d556828af570221b2dc276a6376c8557Jens Axboe //===--------------------------------------------------------------------===// 189dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 190dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // These functions can be used to compute live ranges where the live-in and 191de890a1e48d40238dac69f302708dde8719de240Steven Lang // live-out blocks are already known, but the SSA value in each block is 192dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // unknown. 193dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 194de890a1e48d40238dac69f302708dde8719de240Steven Lang // After calling reset(), add known live-out values and known live-in blocks. 195de890a1e48d40238dac69f302708dde8719de240Steven Lang // Then call calculateValues() to compute the actual value that is 196dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // live-in to each block, and add liveness to the live ranges. 197dcefb588d556828af570221b2dc276a6376c8557Jens Axboe // 198dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 199dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// setLiveOutValue - Indicate that VNI is live out from MBB. The 200dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// calculateValues() function will not add liveness for MBB, the caller 201dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// should take care of that. 202f2bba1820a567ac00b09916239ac8feb125cead2Radha Ramachandran /// 203dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// VNI may be null only if MBB is a live-through block also passed to 204100f49f105126a26de6f1069679c20fd75194188Jens Axboe /// addLiveInBlock(). 205100f49f105126a26de6f1069679c20fd75194188Jens Axboe void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { 206dcefb588d556828af570221b2dc276a6376c8557Jens Axboe Seen.set(MBB->getNumber()); 207002e7183cb86d6100efef690b6fa90bf0988b084Jens Axboe LiveOut[MBB] = LiveOutPair(VNI, nullptr); 208dcefb588d556828af570221b2dc276a6376c8557Jens Axboe } 209dcefb588d556828af570221b2dc276a6376c8557Jens Axboe 210cc86c395fd9dd2002ec1edc0967b7c9453debdfbJens Axboe /// addLiveInBlock - Add a block with an unknown live-in value. This 2119c42684e32325da26e862280388798343c5f1305Jens Axboe /// function can only be called once per basic block. Once the live-in value 212dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// has been determined, calculateValues() will add liveness to LI. 213dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// 2143e260a46ea9a8de224c3d0a29a608da3440f284aJens Axboe /// @param LR The live range that is live-in to the block. 215dcefb588d556828af570221b2dc276a6376c8557Jens Axboe /// @param DomNode The domtree node for the block. 2160a28ecda80a78c9d70ae38ced58f3a2fa9c9529dJens Axboe /// @param Kill Index in block where LI is killed. If the value is 217a5f3027cb0495dfe217b2626d248fcc054e7e878Jens Axboe /// live-through, set Kill = SLotIndex() and also call 21844f29692cfba246981bb3c1b894333a6d2209f51Jens Axboe /// setLiveOutValue(MBB, 0). 219c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe void addLiveInBlock(LiveRange &LR, 220c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe MachineDomTreeNode *DomNode, 221c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe SlotIndex Kill = SlotIndex()) { 222c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); 223c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe } 224c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe 225c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// calculateValues - Calculate the value that will be live-in to each block 226c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA 227c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// form. Add liveness to all live-in blocks up to the Kill point, or the 228c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// whole block for live-through blocks. 229c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// 230c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// Every predecessor of a live-in block must have been given a value with 231c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe /// setLiveOutValue, the value may be null for live-trough blocks. 232c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe void calculateValues(); 233c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe}; 234c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe 235c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe} // end namespace llvm 236c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe 237c592b9fe12d4739d99d5bece517e304804876df6Jens Axboe#endif 238bcd5abfa9f230bbe4365dad1289fdea1f5509f74Jens Axboe