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 #ifndef LLVM_LIB_CODEGEN_SPLITKIT_H 16 #define LLVM_LIB_CODEGEN_SPLITKIT_H 17 18 #include "LiveRangeCalc.h" 19 #include "llvm/ADT/ArrayRef.h" 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/ADT/IntervalMap.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 24 namespace llvm { 25 26 class ConnectedVNInfoEqClasses; 27 class LiveInterval; 28 class LiveIntervals; 29 class LiveRangeEdit; 30 class MachineBlockFrequencyInfo; 31 class MachineInstr; 32 class MachineLoopInfo; 33 class MachineRegisterInfo; 34 class TargetInstrInfo; 35 class TargetRegisterInfo; 36 class VirtRegMap; 37 class VNInfo; 38 class raw_ostream; 39 40 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 41 /// opportunities. 42 class SplitAnalysis { 43 public: 44 const MachineFunction &MF; 45 const VirtRegMap &VRM; 46 const LiveIntervals &LIS; 47 const MachineLoopInfo &Loops; 48 const TargetInstrInfo &TII; 49 50 /// Additional information about basic blocks where the current variable is 51 /// live. Such a block will look like one of these templates: 52 /// 53 /// 1. | o---x | Internal to block. Variable is only live in this block. 54 /// 2. |---x | Live-in, kill. 55 /// 3. | o---| Def, live-out. 56 /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks. 57 /// 5. |---o---o---| Live-through with uses or defs. 58 /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks. 59 /// 60 /// Two BlockInfo entries are created for template 4. One for the live-in 61 /// segment, and one for the live-out segment. These entries look as if the 62 /// block were split in the middle where the live range isn't live. 63 /// 64 /// Live-through blocks without any uses don't get BlockInfo entries. They 65 /// are simply listed in ThroughBlocks instead. 66 /// 67 struct BlockInfo { 68 MachineBasicBlock *MBB; 69 SlotIndex FirstInstr; ///< First instr accessing current reg. 70 SlotIndex LastInstr; ///< Last instr accessing current reg. 71 SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). 72 bool LiveIn; ///< Current reg is live in. 73 bool LiveOut; ///< Current reg is live out. 74 75 /// isOneInstr - Returns true when this BlockInfo describes a single 76 /// instruction. isOneInstrBlockInfo77 bool isOneInstr() const { 78 return SlotIndex::isSameInstr(FirstInstr, LastInstr); 79 } 80 }; 81 82 private: 83 // Current live interval. 84 const LiveInterval *CurLI; 85 86 // Sorted slot indexes of using instructions. 87 SmallVector<SlotIndex, 8> UseSlots; 88 89 /// LastSplitPoint - Last legal split point in each basic block in the current 90 /// function. The first entry is the first terminator, the second entry is the 91 /// last valid split point for a variable that is live in to a landing pad 92 /// successor. 93 SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint; 94 95 /// UseBlocks - Blocks where CurLI has uses. 96 SmallVector<BlockInfo, 8> UseBlocks; 97 98 /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where 99 /// the live range has a gap. 100 unsigned NumGapBlocks; 101 102 /// ThroughBlocks - Block numbers where CurLI is live through without uses. 103 BitVector ThroughBlocks; 104 105 /// NumThroughBlocks - Number of live-through blocks. 106 unsigned NumThroughBlocks; 107 108 /// DidRepairRange - analyze was forced to shrinkToUses(). 109 bool DidRepairRange; 110 111 SlotIndex computeLastSplitPoint(unsigned Num); 112 113 // Sumarize statistics by counting instructions using CurLI. 114 void analyzeUses(); 115 116 /// calcLiveBlockInfo - Compute per-block information about CurLI. 117 bool calcLiveBlockInfo(); 118 119 public: 120 SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 121 const MachineLoopInfo &mli); 122 123 /// analyze - set CurLI to the specified interval, and analyze how it may be 124 /// split. 125 void analyze(const LiveInterval *li); 126 127 /// didRepairRange() - Returns true if CurLI was invalid and has been repaired 128 /// by analyze(). This really shouldn't happen, but sometimes the coalescer 129 /// can create live ranges that end in mid-air. didRepairRange()130 bool didRepairRange() const { return DidRepairRange; } 131 132 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 133 /// new interval. 134 void clear(); 135 136 /// getParent - Return the last analyzed interval. getParent()137 const LiveInterval &getParent() const { return *CurLI; } 138 139 /// getLastSplitPoint - Return the base index of the last valid split point 140 /// in the basic block numbered Num. getLastSplitPoint(unsigned Num)141 SlotIndex getLastSplitPoint(unsigned Num) { 142 // Inline the common simple case. 143 if (LastSplitPoint[Num].first.isValid() && 144 !LastSplitPoint[Num].second.isValid()) 145 return LastSplitPoint[Num].first; 146 return computeLastSplitPoint(Num); 147 } 148 149 /// getLastSplitPointIter - Returns the last split point as an iterator. 150 MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock*); 151 152 /// isOriginalEndpoint - Return true if the original live range was killed or 153 /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 154 /// and 'use' for an early-clobber def. 155 /// This can be used to recognize code inserted by earlier live range 156 /// splitting. 157 bool isOriginalEndpoint(SlotIndex Idx) const; 158 159 /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI. 160 /// This include both use and def operands, at most one entry per instruction. getUseSlots()161 ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; } 162 163 /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 164 /// where CurLI has uses. getUseBlocks()165 ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; } 166 167 /// getNumThroughBlocks - Return the number of through blocks. getNumThroughBlocks()168 unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 169 170 /// isThroughBlock - Return true if CurLI is live through MBB without uses. isThroughBlock(unsigned MBB)171 bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 172 173 /// getThroughBlocks - Return the set of through blocks. getThroughBlocks()174 const BitVector &getThroughBlocks() const { return ThroughBlocks; } 175 176 /// getNumLiveBlocks - Return the number of blocks where CurLI is live. getNumLiveBlocks()177 unsigned getNumLiveBlocks() const { 178 return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks(); 179 } 180 181 /// countLiveBlocks - Return the number of blocks where li is live. This is 182 /// guaranteed to return the same number as getNumLiveBlocks() after calling 183 /// analyze(li). 184 unsigned countLiveBlocks(const LiveInterval *li) const; 185 186 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 187 188 /// shouldSplitSingleBlock - Returns true if it would help to create a local 189 /// live range for the instructions in BI. There is normally no benefit to 190 /// creating a live range for a single instruction, but it does enable 191 /// register class inflation if the instruction has a restricted register 192 /// class. 193 /// 194 /// @param BI The block to be isolated. 195 /// @param SingleInstrs True when single instructions should be isolated. 196 bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; 197 }; 198 199 200 /// SplitEditor - Edit machine code and LiveIntervals for live range 201 /// splitting. 202 /// 203 /// - Create a SplitEditor from a SplitAnalysis. 204 /// - Start a new live interval with openIntv. 205 /// - Mark the places where the new interval is entered using enterIntv* 206 /// - Mark the ranges where the new interval is used with useIntv* 207 /// - Mark the places where the interval is exited with exitIntv*. 208 /// - Finish the current interval with closeIntv and repeat from 2. 209 /// - Rewrite instructions with finish(). 210 /// 211 class SplitEditor { 212 SplitAnalysis &SA; 213 LiveIntervals &LIS; 214 VirtRegMap &VRM; 215 MachineRegisterInfo &MRI; 216 MachineDominatorTree &MDT; 217 const TargetInstrInfo &TII; 218 const TargetRegisterInfo &TRI; 219 const MachineBlockFrequencyInfo &MBFI; 220 221 public: 222 223 /// ComplementSpillMode - Select how the complement live range should be 224 /// created. SplitEditor automatically creates interval 0 to contain 225 /// anything that isn't added to another interval. This complement interval 226 /// can get quite complicated, and it can sometimes be an advantage to allow 227 /// it to overlap the other intervals. If it is going to spill anyway, no 228 /// registers are wasted by keeping a value in two places at the same time. 229 enum ComplementSpillMode { 230 /// SM_Partition(Default) - Try to create the complement interval so it 231 /// doesn't overlap any other intervals, and the original interval is 232 /// partitioned. This may require a large number of back copies and extra 233 /// PHI-defs. Only segments marked with overlapIntv will be overlapping. 234 SM_Partition, 235 236 /// SM_Size - Overlap intervals to minimize the number of inserted COPY 237 /// instructions. Copies to the complement interval are hoisted to their 238 /// common dominator, so only one COPY is required per value in the 239 /// complement interval. This also means that no extra PHI-defs need to be 240 /// inserted in the complement interval. 241 SM_Size, 242 243 /// SM_Speed - Overlap intervals to minimize the expected execution 244 /// frequency of the inserted copies. This is very similar to SM_Size, but 245 /// the complement interval may get some extra PHI-defs. 246 SM_Speed 247 }; 248 249 private: 250 251 /// Edit - The current parent register and new intervals created. 252 LiveRangeEdit *Edit; 253 254 /// Index into Edit of the currently open interval. 255 /// The index 0 is used for the complement, so the first interval started by 256 /// openIntv will be 1. 257 unsigned OpenIdx; 258 259 /// The current spill mode, selected by reset(). 260 ComplementSpillMode SpillMode; 261 262 typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 263 264 /// Allocator for the interval map. This will eventually be shared with 265 /// SlotIndexes and LiveIntervals. 266 RegAssignMap::Allocator Allocator; 267 268 /// RegAssign - Map of the assigned register indexes. 269 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 270 /// Idx. 271 RegAssignMap RegAssign; 272 273 typedef PointerIntPair<VNInfo*, 1> ValueForcePair; 274 typedef DenseMap<std::pair<unsigned, unsigned>, ValueForcePair> ValueMap; 275 276 /// Values - keep track of the mapping from parent values to values in the new 277 /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 278 /// 279 /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 280 /// 2. (Null, false) - the value is mapped to multiple values in 281 /// Edit.get(RegIdx). Each value is represented by a minimal live range at 282 /// its def. The full live range can be inferred exactly from the range 283 /// of RegIdx in RegAssign. 284 /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and 285 /// the live range must be recomputed using LiveRangeCalc::extend(). 286 /// 4. (VNI, false) The value is mapped to a single new value. 287 /// The new value has no live ranges anywhere. 288 ValueMap Values; 289 290 /// LRCalc - Cache for computing live ranges and SSA update. Each instance 291 /// can only handle non-overlapping live ranges, so use a separate 292 /// LiveRangeCalc instance for the complement interval when in spill mode. 293 LiveRangeCalc LRCalc[2]; 294 295 /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the 296 /// complement interval can overlap the other intervals, so it gets its own 297 /// LRCalc instance. When not in spill mode, all intervals can share one. getLRCalc(unsigned RegIdx)298 LiveRangeCalc &getLRCalc(unsigned RegIdx) { 299 return LRCalc[SpillMode != SM_Partition && RegIdx != 0]; 300 } 301 302 /// defValue - define a value in RegIdx from ParentVNI at Idx. 303 /// Idx does not have to be ParentVNI->def, but it must be contained within 304 /// ParentVNI's live range in ParentLI. The new value is added to the value 305 /// map. 306 /// Return the new LI value. 307 VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 308 309 /// forceRecompute - Force the live range of ParentVNI in RegIdx to be 310 /// recomputed by LiveRangeCalc::extend regardless of the number of defs. 311 /// This is used for values whose live range doesn't match RegAssign exactly. 312 /// They could have rematerialized, or back-copies may have been moved. 313 void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI); 314 315 /// defFromParent - Define Reg from ParentVNI at UseIdx using either 316 /// rematerialization or a COPY from parent. Return the new value. 317 VNInfo *defFromParent(unsigned RegIdx, 318 VNInfo *ParentVNI, 319 SlotIndex UseIdx, 320 MachineBasicBlock &MBB, 321 MachineBasicBlock::iterator I); 322 323 /// removeBackCopies - Remove the copy instructions that defines the values 324 /// in the vector in the complement interval. 325 void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies); 326 327 /// getShallowDominator - Returns the least busy dominator of MBB that is 328 /// also dominated by DefMBB. Busy is measured by loop depth. 329 MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, 330 MachineBasicBlock *DefMBB); 331 332 /// hoistCopiesForSize - Hoist back-copies to the complement interval in a 333 /// way that minimizes code size. This implements the SM_Size spill mode. 334 void hoistCopiesForSize(); 335 336 /// transferValues - Transfer values to the new ranges. 337 /// Return true if any ranges were skipped. 338 bool transferValues(); 339 340 /// extendPHIKillRanges - Extend the ranges of all values killed by original 341 /// parent PHIDefs. 342 void extendPHIKillRanges(); 343 344 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 345 void rewriteAssigned(bool ExtendRanges); 346 347 /// deleteRematVictims - Delete defs that are dead after rematerializing. 348 void deleteRematVictims(); 349 350 public: 351 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 352 /// Newly created intervals will be appended to newIntervals. 353 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 354 MachineDominatorTree&, MachineBlockFrequencyInfo &); 355 356 /// reset - Prepare for a new split. 357 void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); 358 359 /// Create a new virtual register and live interval. 360 /// Return the interval index, starting from 1. Interval index 0 is the 361 /// implicit complement interval. 362 unsigned openIntv(); 363 364 /// currentIntv - Return the current interval index. currentIntv()365 unsigned currentIntv() const { return OpenIdx; } 366 367 /// selectIntv - Select a previously opened interval index. 368 void selectIntv(unsigned Idx); 369 370 /// enterIntvBefore - Enter the open interval before the instruction at Idx. 371 /// If the parent interval is not live before Idx, a COPY is not inserted. 372 /// Return the beginning of the new live range. 373 SlotIndex enterIntvBefore(SlotIndex Idx); 374 375 /// enterIntvAfter - Enter the open interval after the instruction at Idx. 376 /// Return the beginning of the new live range. 377 SlotIndex enterIntvAfter(SlotIndex Idx); 378 379 /// enterIntvAtEnd - Enter the open interval at the end of MBB. 380 /// Use the open interval from the inserted copy to the MBB end. 381 /// Return the beginning of the new live range. 382 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 383 384 /// useIntv - indicate that all instructions in MBB should use OpenLI. 385 void useIntv(const MachineBasicBlock &MBB); 386 387 /// useIntv - indicate that all instructions in range should use OpenLI. 388 void useIntv(SlotIndex Start, SlotIndex End); 389 390 /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 391 /// Return the end of the live range. 392 SlotIndex leaveIntvAfter(SlotIndex Idx); 393 394 /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 395 /// Return the end of the live range. 396 SlotIndex leaveIntvBefore(SlotIndex Idx); 397 398 /// leaveIntvAtTop - Leave the interval at the top of MBB. 399 /// Add liveness from the MBB top to the copy. 400 /// Return the end of the live range. 401 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 402 403 /// overlapIntv - Indicate that all instructions in range should use the open 404 /// interval, but also let the complement interval be live. 405 /// 406 /// This doubles the register pressure, but is sometimes required to deal with 407 /// register uses after the last valid split point. 408 /// 409 /// The Start index should be a return value from a leaveIntv* call, and End 410 /// should be in the same basic block. The parent interval must have the same 411 /// value across the range. 412 /// 413 void overlapIntv(SlotIndex Start, SlotIndex End); 414 415 /// finish - after all the new live ranges have been created, compute the 416 /// remaining live range, and rewrite instructions to use the new registers. 417 /// @param LRMap When not null, this vector will map each live range in Edit 418 /// back to the indices returned by openIntv. 419 /// There may be extra indices created by dead code elimination. 420 void finish(SmallVectorImpl<unsigned> *LRMap = nullptr); 421 422 /// dump - print the current interval maping to dbgs(). 423 void dump() const; 424 425 // ===--- High level methods ---=== 426 427 /// splitSingleBlock - Split CurLI into a separate live interval around the 428 /// uses in a single block. This is intended to be used as part of a larger 429 /// split, and doesn't call finish(). 430 void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); 431 432 /// splitLiveThroughBlock - Split CurLI in the given block such that it 433 /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in 434 /// the block, but they will be ignored when placing split points. 435 /// 436 /// @param MBBNum Block number. 437 /// @param IntvIn Interval index entering the block. 438 /// @param LeaveBefore When set, leave IntvIn before this point. 439 /// @param IntvOut Interval index leaving the block. 440 /// @param EnterAfter When set, enter IntvOut after this point. 441 void splitLiveThroughBlock(unsigned MBBNum, 442 unsigned IntvIn, SlotIndex LeaveBefore, 443 unsigned IntvOut, SlotIndex EnterAfter); 444 445 /// splitRegInBlock - Split CurLI in the given block such that it enters the 446 /// block in IntvIn and leaves it on the stack (or not at all). Split points 447 /// are placed in a way that avoids putting uses in the stack interval. This 448 /// may require creating a local interval when there is interference. 449 /// 450 /// @param BI Block descriptor. 451 /// @param IntvIn Interval index entering the block. Not 0. 452 /// @param LeaveBefore When set, leave IntvIn before this point. 453 void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 454 unsigned IntvIn, SlotIndex LeaveBefore); 455 456 /// splitRegOutBlock - Split CurLI in the given block such that it enters the 457 /// block on the stack (or isn't live-in at all) and leaves it in IntvOut. 458 /// Split points are placed to avoid interference and such that the uses are 459 /// not in the stack interval. This may require creating a local interval 460 /// when there is interference. 461 /// 462 /// @param BI Block descriptor. 463 /// @param IntvOut Interval index leaving the block. 464 /// @param EnterAfter When set, enter IntvOut after this point. 465 void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 466 unsigned IntvOut, SlotIndex EnterAfter); 467 }; 468 469 } 470 471 #endif 472