SplitKit.h revision 6c8afd728eb02742ce320ecd39bcf3774d8423b7
1//===-------- SplitKit.h - Toolkit for splitting live ranges ----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the SplitAnalysis class as well as mutator functions for 11// live range splitting. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/BitVector.h" 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/ADT/IndexedMap.h" 18#include "llvm/ADT/IntervalMap.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include "llvm/CodeGen/SlotIndexes.h" 21 22namespace llvm { 23 24class ConnectedVNInfoEqClasses; 25class LiveInterval; 26class LiveIntervals; 27class LiveRangeEdit; 28class MachineInstr; 29class MachineLoopInfo; 30class MachineRegisterInfo; 31class TargetInstrInfo; 32class TargetRegisterInfo; 33class VirtRegMap; 34class VNInfo; 35class raw_ostream; 36 37/// At some point we should just include MachineDominators.h: 38class MachineDominatorTree; 39template <class NodeT> class DomTreeNodeBase; 40typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 41 42 43/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 44/// opportunities. 45class SplitAnalysis { 46public: 47 const MachineFunction &MF; 48 const VirtRegMap &VRM; 49 const LiveIntervals &LIS; 50 const MachineLoopInfo &Loops; 51 const TargetInstrInfo &TII; 52 53 // Instructions using the the current register. 54 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 55 InstrPtrSet UsingInstrs; 56 57 // Sorted slot indexes of using instructions. 58 SmallVector<SlotIndex, 8> UseSlots; 59 60 // The number of instructions using CurLI in each basic block. 61 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 62 BlockCountMap UsingBlocks; 63 64 /// Additional information about basic blocks where the current variable is 65 /// live. Such a block will look like one of these templates: 66 /// 67 /// 1. | o---x | Internal to block. Variable is only live in this block. 68 /// 2. |---x | Live-in, kill. 69 /// 3. | o---| Def, live-out. 70 /// 4. |---x o---| Live-in, kill, def, live-out. 71 /// 5. |---o---o---| Live-through with uses or defs. 72 /// 6. |-----------| Live-through without uses. Transparent. 73 /// 74 struct BlockInfo { 75 MachineBasicBlock *MBB; 76 SlotIndex FirstUse; ///< First instr using current reg. 77 SlotIndex LastUse; ///< Last instr using current reg. 78 SlotIndex Kill; ///< Interval end point inside block. 79 SlotIndex Def; ///< Interval start point inside block. 80 /// Last possible point for splitting live ranges. 81 SlotIndex LastSplitPoint; 82 bool Uses; ///< Current reg has uses or defs in block. 83 bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 84 bool LiveIn; ///< Current reg is live in. 85 bool LiveOut; ///< Current reg is live out. 86 }; 87 88 /// Basic blocks where var is live. This array is parallel to 89 /// SpillConstraints. 90 SmallVector<BlockInfo, 8> LiveBlocks; 91 92private: 93 // Current live interval. 94 const LiveInterval *CurLI; 95 96 // Sumarize statistics by counting instructions using CurLI. 97 void analyzeUses(); 98 99 /// calcLiveBlockInfo - Compute per-block information about CurLI. 100 bool calcLiveBlockInfo(); 101 102 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 103 /// analyzed. 104 bool canAnalyzeBranch(const MachineBasicBlock *MBB); 105 106public: 107 SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 108 const MachineLoopInfo &mli); 109 110 /// analyze - set CurLI to the specified interval, and analyze how it may be 111 /// split. 112 void analyze(const LiveInterval *li); 113 114 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 115 /// new interval. 116 void clear(); 117 118 /// getParent - Return the last analyzed interval. 119 const LiveInterval &getParent() const { return *CurLI; } 120 121 /// hasUses - Return true if MBB has any uses of CurLI. 122 bool hasUses(const MachineBasicBlock *MBB) const { 123 return UsingBlocks.lookup(MBB); 124 } 125 126 /// isOriginalEndpoint - Return true if the original live range was killed or 127 /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 128 /// and 'use' for an early-clobber def. 129 /// This can be used to recognize code inserted by earlier live range 130 /// splitting. 131 bool isOriginalEndpoint(SlotIndex Idx) const; 132 133 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 134 135 // Print a set of blocks with use counts. 136 void print(const BlockPtrSet&, raw_ostream&) const; 137 138 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 139 /// having CurLI split to a new live interval. Return true if Blocks can be 140 /// passed to SplitEditor::splitSingleBlocks. 141 bool getMultiUseBlocks(BlockPtrSet &Blocks); 142}; 143 144 145/// SplitEditor - Edit machine code and LiveIntervals for live range 146/// splitting. 147/// 148/// - Create a SplitEditor from a SplitAnalysis. 149/// - Start a new live interval with openIntv. 150/// - Mark the places where the new interval is entered using enterIntv* 151/// - Mark the ranges where the new interval is used with useIntv* 152/// - Mark the places where the interval is exited with exitIntv*. 153/// - Finish the current interval with closeIntv and repeat from 2. 154/// - Rewrite instructions with finish(). 155/// 156class SplitEditor { 157 SplitAnalysis &SA; 158 LiveIntervals &LIS; 159 VirtRegMap &VRM; 160 MachineRegisterInfo &MRI; 161 MachineDominatorTree &MDT; 162 const TargetInstrInfo &TII; 163 const TargetRegisterInfo &TRI; 164 165 /// Edit - The current parent register and new intervals created. 166 LiveRangeEdit *Edit; 167 168 /// Index into Edit of the currently open interval. 169 /// The index 0 is used for the complement, so the first interval started by 170 /// openIntv will be 1. 171 unsigned OpenIdx; 172 173 typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 174 175 /// Allocator for the interval map. This will eventually be shared with 176 /// SlotIndexes and LiveIntervals. 177 RegAssignMap::Allocator Allocator; 178 179 /// RegAssign - Map of the assigned register indexes. 180 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 181 /// Idx. 182 RegAssignMap RegAssign; 183 184 typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap; 185 186 /// Values - keep track of the mapping from parent values to values in the new 187 /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 188 /// 189 /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 190 /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). 191 /// Each value is represented by a minimal live range at its def. 192 /// 3. A non-null VNInfo - the value is mapped to a single new value. 193 /// The new value has no live ranges anywhere. 194 ValueMap Values; 195 196 typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 197 typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 198 199 // LiveOutCache - Map each basic block where a new register is live out to the 200 // live-out value and its defining block. 201 // One of these conditions shall be true: 202 // 203 // 1. !LiveOutCache.count(MBB) 204 // 2. LiveOutCache[MBB].second.getNode() == MBB 205 // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 206 // 207 // This is only a cache, the values can be computed as: 208 // 209 // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 210 // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 211 // 212 // The cache is also used as a visited set by extendRange(). It can be shared 213 // by all the new registers because at most one is live out of each block. 214 LiveOutMap LiveOutCache; 215 216 // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid 217 // entry in LiveOutCache. 218 BitVector LiveOutSeen; 219 220 /// defValue - define a value in RegIdx from ParentVNI at Idx. 221 /// Idx does not have to be ParentVNI->def, but it must be contained within 222 /// ParentVNI's live range in ParentLI. The new value is added to the value 223 /// map. 224 /// Return the new LI value. 225 VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 226 227 /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless 228 /// of the number of defs. 229 void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); 230 231 /// defFromParent - Define Reg from ParentVNI at UseIdx using either 232 /// rematerialization or a COPY from parent. Return the new value. 233 VNInfo *defFromParent(unsigned RegIdx, 234 VNInfo *ParentVNI, 235 SlotIndex UseIdx, 236 MachineBasicBlock &MBB, 237 MachineBasicBlock::iterator I); 238 239 /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. 240 /// Insert PHIDefs as needed to preserve SSA form. 241 void extendRange(unsigned RegIdx, SlotIndex Idx); 242 243 /// updateSSA - Insert PHIDefs as necessary and update LiveOutCache such that 244 /// Edit.get(RegIdx) is live-in to all the blocks in LiveIn. 245 /// Return the value that is eventually live-in to IdxMBB. 246 VNInfo *updateSSA(unsigned RegIdx, 247 SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 248 SlotIndex Idx, 249 const MachineBasicBlock *IdxMBB); 250 251 /// transferSimpleValues - Transfer simply defined values to the new ranges. 252 /// Return true if any complex ranges were skipped. 253 bool transferSimpleValues(); 254 255 /// extendPHIKillRanges - Extend the ranges of all values killed by original 256 /// parent PHIDefs. 257 void extendPHIKillRanges(); 258 259 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 260 void rewriteAssigned(bool ExtendRanges); 261 262 /// deleteRematVictims - Delete defs that are dead after rematerializing. 263 void deleteRematVictims(); 264 265public: 266 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 267 /// Newly created intervals will be appended to newIntervals. 268 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 269 MachineDominatorTree&); 270 271 /// reset - Prepare for a new split. 272 void reset(LiveRangeEdit&); 273 274 /// Create a new virtual register and live interval. 275 void openIntv(); 276 277 /// enterIntvBefore - Enter the open interval before the instruction at Idx. 278 /// If the parent interval is not live before Idx, a COPY is not inserted. 279 /// Return the beginning of the new live range. 280 SlotIndex enterIntvBefore(SlotIndex Idx); 281 282 /// enterIntvAtEnd - Enter the open interval at the end of MBB. 283 /// Use the open interval from he inserted copy to the MBB end. 284 /// Return the beginning of the new live range. 285 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 286 287 /// useIntv - indicate that all instructions in MBB should use OpenLI. 288 void useIntv(const MachineBasicBlock &MBB); 289 290 /// useIntv - indicate that all instructions in range should use OpenLI. 291 void useIntv(SlotIndex Start, SlotIndex End); 292 293 /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 294 /// Return the end of the live range. 295 SlotIndex leaveIntvAfter(SlotIndex Idx); 296 297 /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 298 /// Return the end of the live range. 299 SlotIndex leaveIntvBefore(SlotIndex Idx); 300 301 /// leaveIntvAtTop - Leave the interval at the top of MBB. 302 /// Add liveness from the MBB top to the copy. 303 /// Return the end of the live range. 304 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 305 306 /// overlapIntv - Indicate that all instructions in range should use the open 307 /// interval, but also let the complement interval be live. 308 /// 309 /// This doubles the register pressure, but is sometimes required to deal with 310 /// register uses after the last valid split point. 311 /// 312 /// The Start index should be a return value from a leaveIntv* call, and End 313 /// should be in the same basic block. The parent interval must have the same 314 /// value across the range. 315 /// 316 void overlapIntv(SlotIndex Start, SlotIndex End); 317 318 /// closeIntv - Indicate that we are done editing the currently open 319 /// LiveInterval, and ranges can be trimmed. 320 void closeIntv(); 321 322 /// finish - after all the new live ranges have been created, compute the 323 /// remaining live range, and rewrite instructions to use the new registers. 324 void finish(); 325 326 /// dump - print the current interval maping to dbgs(). 327 void dump() const; 328 329 // ===--- High level methods ---=== 330 331 /// splitSingleBlocks - Split CurLI into a separate live interval inside each 332 /// basic block in Blocks. 333 void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 334}; 335 336} 337