SplitKit.h revision 9b057771ba22441b8d312404204433477b4be657
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/DenseMap.h" 16#include "llvm/ADT/IntervalMap.h" 17#include "llvm/ADT/SmallPtrSet.h" 18#include "llvm/CodeGen/SlotIndexes.h" 19 20namespace llvm { 21 22class ConnectedVNInfoEqClasses; 23class LiveInterval; 24class LiveIntervals; 25class LiveRangeEdit; 26class MachineInstr; 27class MachineLoop; 28class MachineLoopInfo; 29class MachineRegisterInfo; 30class TargetInstrInfo; 31class TargetRegisterInfo; 32class VirtRegMap; 33class VNInfo; 34class raw_ostream; 35 36/// At some point we should just include MachineDominators.h: 37class MachineDominatorTree; 38template <class NodeT> class DomTreeNodeBase; 39typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 40 41 42/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 43/// opportunities. 44class SplitAnalysis { 45public: 46 const MachineFunction &MF; 47 const LiveIntervals &LIS; 48 const MachineLoopInfo &Loops; 49 const TargetInstrInfo &TII; 50 51 // Instructions using the the current register. 52 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 53 InstrPtrSet UsingInstrs; 54 55 // Sorted slot indexes of using instructions. 56 SmallVector<SlotIndex, 8> UseSlots; 57 58 // The number of instructions using CurLI in each basic block. 59 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 60 BlockCountMap UsingBlocks; 61 62 // The number of basic block using CurLI in each loop. 63 typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 64 LoopCountMap UsingLoops; 65 66 /// Additional information about basic blocks where the current variable is 67 /// live. Such a block will look like one of these templates: 68 /// 69 /// 1. | o---x | Internal to block. Variable is only live in this block. 70 /// 2. |---x | Live-in, kill. 71 /// 3. | o---| Def, live-out. 72 /// 4. |---x o---| Live-in, kill, def, live-out. 73 /// 5. |---o---o---| Live-through with uses or defs. 74 /// 6. |-----------| Live-through without uses. Transparent. 75 /// 76 struct BlockInfo { 77 MachineBasicBlock *MBB; 78 SlotIndex FirstUse; ///< First instr using current reg. 79 SlotIndex LastUse; ///< Last instr using current reg. 80 SlotIndex Kill; ///< Interval end point inside block. 81 SlotIndex Def; ///< Interval start point inside block. 82 /// Last possible point for splitting live ranges. 83 SlotIndex LastSplitPoint; 84 bool Uses; ///< Current reg has uses or defs in block. 85 bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 86 bool LiveIn; ///< Current reg is live in. 87 bool LiveOut; ///< Current reg is live out. 88 89 // Per-interference pattern scratch data. 90 bool OverlapEntry; ///< Interference overlaps entering interval. 91 bool OverlapExit; ///< Interference overlaps exiting interval. 92 }; 93 94 /// Basic blocks where var is live. This array is parallel to 95 /// SpillConstraints. 96 SmallVector<BlockInfo, 8> LiveBlocks; 97 98private: 99 // Current live interval. 100 const LiveInterval *CurLI; 101 102 // Sumarize statistics by counting instructions using CurLI. 103 void analyzeUses(); 104 105 /// calcLiveBlockInfo - Compute per-block information about CurLI. 106 void calcLiveBlockInfo(); 107 108 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 109 /// analyzed. 110 bool canAnalyzeBranch(const MachineBasicBlock *MBB); 111 112public: 113 SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 114 const MachineLoopInfo &mli); 115 116 /// analyze - set CurLI to the specified interval, and analyze how it may be 117 /// split. 118 void analyze(const LiveInterval *li); 119 120 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 121 /// new interval. 122 void clear(); 123 124 /// hasUses - Return true if MBB has any uses of CurLI. 125 bool hasUses(const MachineBasicBlock *MBB) const { 126 return UsingBlocks.lookup(MBB); 127 } 128 129 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 130 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 131 132 // Print a set of blocks with use counts. 133 void print(const BlockPtrSet&, raw_ostream&) const; 134 135 // Sets of basic blocks surrounding a machine loop. 136 struct LoopBlocks { 137 BlockPtrSet Loop; // Blocks in the loop. 138 BlockPtrSet Preds; // Loop predecessor blocks. 139 BlockPtrSet Exits; // Loop exit blocks. 140 141 void clear() { 142 Loop.clear(); 143 Preds.clear(); 144 Exits.clear(); 145 } 146 }; 147 148 // Print loop blocks with use counts. 149 void print(const LoopBlocks&, raw_ostream&) const; 150 151 // Calculate the block sets surrounding the loop. 152 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 153 154 /// LoopPeripheralUse - how is a variable used in and around a loop? 155 /// Peripheral blocks are the loop predecessors and exit blocks. 156 enum LoopPeripheralUse { 157 ContainedInLoop, // All uses are inside the loop. 158 SinglePeripheral, // At most one instruction per peripheral block. 159 MultiPeripheral, // Multiple instructions in some peripheral blocks. 160 OutsideLoop // Uses outside loop periphery. 161 }; 162 163 /// analyzeLoopPeripheralUse - Return an enum describing how CurLI is used in 164 /// and around the Loop. 165 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 166 167 /// getCriticalExits - It may be necessary to partially break critical edges 168 /// leaving the loop if an exit block has phi uses of CurLI. Collect the exit 169 /// blocks that need special treatment into CriticalExits. 170 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 171 172 /// canSplitCriticalExits - Return true if it is possible to insert new exit 173 /// blocks before the blocks in CriticalExits. 174 bool canSplitCriticalExits(const LoopBlocks &Blocks, 175 BlockPtrSet &CriticalExits); 176 177 /// getCriticalPreds - Get the set of loop predecessors with critical edges to 178 /// blocks outside the loop that have CurLI live in. We don't have to break 179 /// these edges, but they do require special treatment. 180 void getCriticalPreds(const LoopBlocks &Blocks, BlockPtrSet &CriticalPreds); 181 182 /// getSplitLoops - Get the set of loops that have CurLI uses and would be 183 /// profitable to split. 184 void getSplitLoops(LoopPtrSet&); 185 186 /// getBestSplitLoop - Return the loop where CurLI may best be split to a 187 /// separate register, or NULL. 188 const MachineLoop *getBestSplitLoop(); 189 190 /// isBypassLoop - Return true if CurLI is live through Loop and has no uses 191 /// inside the loop. Bypass loops are candidates for splitting because it can 192 /// prevent interference inside the loop. 193 bool isBypassLoop(const MachineLoop *Loop); 194 195 /// getBypassLoops - Get all the maximal bypass loops. These are the bypass 196 /// loops whose parent is not a bypass loop. 197 void getBypassLoops(LoopPtrSet&); 198 199 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 200 /// having CurLI split to a new live interval. Return true if Blocks can be 201 /// passed to SplitEditor::splitSingleBlocks. 202 bool getMultiUseBlocks(BlockPtrSet &Blocks); 203 204 /// getBlockForInsideSplit - If CurLI is contained inside a single basic 205 /// block, and it would pay to subdivide the interval inside that block, 206 /// return it. Otherwise return NULL. The returned block can be passed to 207 /// SplitEditor::splitInsideBlock. 208 const MachineBasicBlock *getBlockForInsideSplit(); 209}; 210 211 212/// LiveIntervalMap - Map values from a large LiveInterval into a small 213/// interval that is a subset. Insert phi-def values as needed. This class is 214/// used by SplitEditor to create new smaller LiveIntervals. 215/// 216/// ParentLI is the larger interval, LI is the subset interval. Every value 217/// in LI corresponds to exactly one value in ParentLI, and the live range 218/// of the value is contained within the live range of the ParentLI value. 219/// Values in ParentLI may map to any number of OpenLI values, including 0. 220class LiveIntervalMap { 221 LiveIntervals &LIS; 222 MachineDominatorTree &MDT; 223 224 // The parent interval is never changed. 225 const LiveInterval &ParentLI; 226 227 // The child interval's values are fully contained inside ParentLI values. 228 LiveInterval *LI; 229 230 typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 231 232 // Map ParentLI values to simple values in LI that are defined at the same 233 // SlotIndex, or NULL for ParentLI values that have complex LI defs. 234 // Note there is a difference between values mapping to NULL (complex), and 235 // values not present (unknown/unmapped). 236 ValueMap Values; 237 238 typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 239 typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap; 240 241 // LiveOutCache - Map each basic block where LI is live out to the live-out 242 // value and its defining block. One of these conditions shall be true: 243 // 244 // 1. !LiveOutCache.count(MBB) 245 // 2. LiveOutCache[MBB].second.getNode() == MBB 246 // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 247 // 248 // This is only a cache, the values can be computed as: 249 // 250 // VNI = LI->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 251 // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 252 // 253 // The cache is also used as a visiteed set by mapValue(). 254 LiveOutMap LiveOutCache; 255 256 // Dump the live-out cache to dbgs(). 257 void dumpCache(); 258 259public: 260 LiveIntervalMap(LiveIntervals &lis, 261 MachineDominatorTree &mdt, 262 const LiveInterval &parentli) 263 : LIS(lis), MDT(mdt), ParentLI(parentli), LI(0) {} 264 265 /// reset - clear all data structures and start a new live interval. 266 void reset(LiveInterval *); 267 268 /// getLI - return the current live interval. 269 LiveInterval *getLI() const { return LI; } 270 271 /// defValue - define a value in LI from the ParentLI value VNI and Idx. 272 /// Idx does not have to be ParentVNI->def, but it must be contained within 273 /// ParentVNI's live range in ParentLI. 274 /// Return the new LI value. 275 VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 276 277 /// mapValue - map ParentVNI to the corresponding LI value at Idx. It is 278 /// assumed that ParentVNI is live at Idx. 279 /// If ParentVNI has not been defined by defValue, it is assumed that 280 /// ParentVNI->def dominates Idx. 281 /// If ParentVNI has been defined by defValue one or more times, a value that 282 /// dominates Idx will be returned. This may require creating extra phi-def 283 /// values and adding live ranges to LI. 284 /// If simple is not NULL, *simple will indicate if ParentVNI is a simply 285 /// mapped value. 286 VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0); 287 288 // extendTo - Find the last LI value defined in MBB at or before Idx. The 289 // parentli is assumed to be live at Idx. Extend the live range to include 290 // Idx. Return the found VNInfo, or NULL. 291 VNInfo *extendTo(const MachineBasicBlock *MBB, SlotIndex Idx); 292 293 /// isMapped - Return true is ParentVNI is a known mapped value. It may be a 294 /// simple 1-1 mapping or a complex mapping to later defs. 295 bool isMapped(const VNInfo *ParentVNI) const { 296 return Values.count(ParentVNI); 297 } 298 299 /// isComplexMapped - Return true if ParentVNI has received new definitions 300 /// with defValue. 301 bool isComplexMapped(const VNInfo *ParentVNI) const; 302 303 /// markComplexMapped - Mark ParentVNI as complex mapped regardless of the 304 /// number of definitions. 305 void markComplexMapped(const VNInfo *ParentVNI) { Values[ParentVNI] = 0; } 306 307 // addSimpleRange - Add a simple range from ParentLI to LI. 308 // ParentVNI must be live in the [Start;End) interval. 309 void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 310 311 /// addRange - Add live ranges to LI where [Start;End) intersects ParentLI. 312 /// All needed values whose def is not inside [Start;End) must be defined 313 /// beforehand so mapValue will work. 314 void addRange(SlotIndex Start, SlotIndex End); 315}; 316 317 318/// SplitEditor - Edit machine code and LiveIntervals for live range 319/// splitting. 320/// 321/// - Create a SplitEditor from a SplitAnalysis. 322/// - Start a new live interval with openIntv. 323/// - Mark the places where the new interval is entered using enterIntv* 324/// - Mark the ranges where the new interval is used with useIntv* 325/// - Mark the places where the interval is exited with exitIntv*. 326/// - Finish the current interval with closeIntv and repeat from 2. 327/// - Rewrite instructions with finish(). 328/// 329class SplitEditor { 330 SplitAnalysis &sa_; 331 LiveIntervals &LIS; 332 VirtRegMap &VRM; 333 MachineRegisterInfo &MRI; 334 MachineDominatorTree &MDT; 335 const TargetInstrInfo &TII; 336 const TargetRegisterInfo &TRI; 337 338 /// Edit - The current parent register and new intervals created. 339 LiveRangeEdit &Edit; 340 341 /// Index into Edit of the currently open interval. 342 /// The index 0 is used for the complement, so the first interval started by 343 /// openIntv will be 1. 344 unsigned OpenIdx; 345 346 typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 347 348 /// Allocator for the interval map. This will eventually be shared with 349 /// SlotIndexes and LiveIntervals. 350 RegAssignMap::Allocator Allocator; 351 352 /// RegAssign - Map of the assigned register indexes. 353 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 354 /// Idx. 355 RegAssignMap RegAssign; 356 357 /// LIMappers - One LiveIntervalMap or each interval in Edit. 358 SmallVector<LiveIntervalMap, 4> LIMappers; 359 360 /// defFromParent - Define Reg from ParentVNI at UseIdx using either 361 /// rematerialization or a COPY from parent. Return the new value. 362 VNInfo *defFromParent(unsigned RegIdx, 363 VNInfo *ParentVNI, 364 SlotIndex UseIdx, 365 MachineBasicBlock &MBB, 366 MachineBasicBlock::iterator I); 367 368 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 369 void rewriteAssigned(); 370 371 /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq 372 /// classes in ConEQ. 373 /// This must be done when Intvs[0] is styill live at all uses, before calling 374 /// ConEq.Distribute(). 375 void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 376 const ConnectedVNInfoEqClasses &ConEq); 377 378public: 379 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 380 /// Newly created intervals will be appended to newIntervals. 381 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 382 MachineDominatorTree&, LiveRangeEdit&); 383 384 /// getAnalysis - Get the corresponding analysis. 385 SplitAnalysis &getAnalysis() { return sa_; } 386 387 /// Create a new virtual register and live interval. 388 void openIntv(); 389 390 /// enterIntvBefore - Enter the open interval before the instruction at Idx. 391 /// If the parent interval is not live before Idx, a COPY is not inserted. 392 /// Return the beginning of the new live range. 393 SlotIndex enterIntvBefore(SlotIndex Idx); 394 395 /// enterIntvAtEnd - Enter the open interval at the end of MBB. 396 /// Use the open interval from he inserted copy to the MBB end. 397 /// Return the beginning of the new live range. 398 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 399 400 /// useIntv - indicate that all instructions in MBB should use OpenLI. 401 void useIntv(const MachineBasicBlock &MBB); 402 403 /// useIntv - indicate that all instructions in range should use OpenLI. 404 void useIntv(SlotIndex Start, SlotIndex End); 405 406 /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 407 /// Return the end of the live range. 408 SlotIndex leaveIntvAfter(SlotIndex Idx); 409 410 /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 411 /// Return the end of the live range. 412 SlotIndex leaveIntvBefore(SlotIndex Idx); 413 414 /// leaveIntvAtTop - Leave the interval at the top of MBB. 415 /// Add liveness from the MBB top to the copy. 416 /// Return the end of the live range. 417 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 418 419 /// overlapIntv - Indicate that all instructions in range should use the open 420 /// interval, but also let the complement interval be live. 421 /// 422 /// This doubles the register pressure, but is sometimes required to deal with 423 /// register uses after the last valid split point. 424 /// 425 /// The Start index should be a return value from a leaveIntv* call, and End 426 /// should be in the same basic block. The parent interval must have the same 427 /// value across the range. 428 /// 429 void overlapIntv(SlotIndex Start, SlotIndex End); 430 431 /// closeIntv - Indicate that we are done editing the currently open 432 /// LiveInterval, and ranges can be trimmed. 433 void closeIntv(); 434 435 /// finish - after all the new live ranges have been created, compute the 436 /// remaining live range, and rewrite instructions to use the new registers. 437 void finish(); 438 439 /// dump - print the current interval maping to dbgs(). 440 void dump() const; 441 442 // ===--- High level methods ---=== 443 444 /// splitAroundLoop - Split CurLI into a separate live interval inside 445 /// the loop. 446 void splitAroundLoop(const MachineLoop*); 447 448 /// splitSingleBlocks - Split CurLI into a separate live interval inside each 449 /// basic block in Blocks. 450 void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 451 452 /// splitInsideBlock - Split CurLI into multiple intervals inside MBB. 453 void splitInsideBlock(const MachineBasicBlock *); 454}; 455 456} 457