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