SplitKit.h revision 0f43811903f10394f7088f4634c0b4f9668cbac0
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 66private: 67 // Current live interval. 68 const LiveInterval *CurLI; 69 70 // Sumarize statistics by counting instructions using CurLI. 71 void analyzeUses(); 72 73 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 74 /// analyzed. 75 bool canAnalyzeBranch(const MachineBasicBlock *MBB); 76 77public: 78 SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 79 const MachineLoopInfo &mli); 80 81 /// analyze - set CurLI to the specified interval, and analyze how it may be 82 /// split. 83 void analyze(const LiveInterval *li); 84 85 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 86 /// new interval. 87 void clear(); 88 89 /// hasUses - Return true if MBB has any uses of CurLI. 90 bool hasUses(const MachineBasicBlock *MBB) const { 91 return UsingBlocks.lookup(MBB); 92 } 93 94 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 95 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 96 97 // Print a set of blocks with use counts. 98 void print(const BlockPtrSet&, raw_ostream&) const; 99 100 // Sets of basic blocks surrounding a machine loop. 101 struct LoopBlocks { 102 BlockPtrSet Loop; // Blocks in the loop. 103 BlockPtrSet Preds; // Loop predecessor blocks. 104 BlockPtrSet Exits; // Loop exit blocks. 105 106 void clear() { 107 Loop.clear(); 108 Preds.clear(); 109 Exits.clear(); 110 } 111 }; 112 113 // Print loop blocks with use counts. 114 void print(const LoopBlocks&, raw_ostream&) const; 115 116 // Calculate the block sets surrounding the loop. 117 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 118 119 /// LoopPeripheralUse - how is a variable used in and around a loop? 120 /// Peripheral blocks are the loop predecessors and exit blocks. 121 enum LoopPeripheralUse { 122 ContainedInLoop, // All uses are inside the loop. 123 SinglePeripheral, // At most one instruction per peripheral block. 124 MultiPeripheral, // Multiple instructions in some peripheral blocks. 125 OutsideLoop // Uses outside loop periphery. 126 }; 127 128 /// analyzeLoopPeripheralUse - Return an enum describing how CurLI is used in 129 /// and around the Loop. 130 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 131 132 /// getCriticalExits - It may be necessary to partially break critical edges 133 /// leaving the loop if an exit block has phi uses of CurLI. Collect the exit 134 /// blocks that need special treatment into CriticalExits. 135 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 136 137 /// canSplitCriticalExits - Return true if it is possible to insert new exit 138 /// blocks before the blocks in CriticalExits. 139 bool canSplitCriticalExits(const LoopBlocks &Blocks, 140 BlockPtrSet &CriticalExits); 141 142 /// getCriticalPreds - Get the set of loop predecessors with critical edges to 143 /// blocks outside the loop that have CurLI live in. We don't have to break 144 /// these edges, but they do require special treatment. 145 void getCriticalPreds(const LoopBlocks &Blocks, BlockPtrSet &CriticalPreds); 146 147 /// getSplitLoops - Get the set of loops that have CurLI uses and would be 148 /// profitable to split. 149 void getSplitLoops(LoopPtrSet&); 150 151 /// getBestSplitLoop - Return the loop where CurLI may best be split to a 152 /// separate register, or NULL. 153 const MachineLoop *getBestSplitLoop(); 154 155 /// isBypassLoop - Return true if CurLI is live through Loop and has no uses 156 /// inside the loop. Bypass loops are candidates for splitting because it can 157 /// prevent interference inside the loop. 158 bool isBypassLoop(const MachineLoop *Loop); 159 160 /// getBypassLoops - Get all the maximal bypass loops. These are the bypass 161 /// loops whose parent is not a bypass loop. 162 void getBypassLoops(LoopPtrSet&); 163 164 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 165 /// having CurLI split to a new live interval. Return true if Blocks can be 166 /// passed to SplitEditor::splitSingleBlocks. 167 bool getMultiUseBlocks(BlockPtrSet &Blocks); 168 169 /// getBlockForInsideSplit - If CurLI is contained inside a single basic 170 /// block, and it would pay to subdivide the interval inside that block, 171 /// return it. Otherwise return NULL. The returned block can be passed to 172 /// SplitEditor::splitInsideBlock. 173 const MachineBasicBlock *getBlockForInsideSplit(); 174}; 175 176 177/// LiveIntervalMap - Map values from a large LiveInterval into a small 178/// interval that is a subset. Insert phi-def values as needed. This class is 179/// used by SplitEditor to create new smaller LiveIntervals. 180/// 181/// ParentLI is the larger interval, LI is the subset interval. Every value 182/// in LI corresponds to exactly one value in ParentLI, and the live range 183/// of the value is contained within the live range of the ParentLI value. 184/// Values in ParentLI may map to any number of OpenLI values, including 0. 185class LiveIntervalMap { 186 LiveIntervals &LIS; 187 MachineDominatorTree &MDT; 188 189 // The parent interval is never changed. 190 const LiveInterval &ParentLI; 191 192 // The child interval's values are fully contained inside ParentLI values. 193 LiveInterval *LI; 194 195 typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 196 197 // Map ParentLI values to simple values in LI that are defined at the same 198 // SlotIndex, or NULL for ParentLI values that have complex LI defs. 199 // Note there is a difference between values mapping to NULL (complex), and 200 // values not present (unknown/unmapped). 201 ValueMap Values; 202 203 typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 204 typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap; 205 206 // LiveOutCache - Map each basic block where LI is live out to the live-out 207 // value and its defining block. One of these conditions shall be true: 208 // 209 // 1. !LiveOutCache.count(MBB) 210 // 2. LiveOutCache[MBB].second.getNode() == MBB 211 // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 212 // 213 // This is only a cache, the values can be computed as: 214 // 215 // VNI = LI->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 216 // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 217 // 218 // The cache is also used as a visiteed set by mapValue(). 219 LiveOutMap LiveOutCache; 220 221 // Dump the live-out cache to dbgs(). 222 void dumpCache(); 223 224public: 225 LiveIntervalMap(LiveIntervals &lis, 226 MachineDominatorTree &mdt, 227 const LiveInterval &parentli) 228 : LIS(lis), MDT(mdt), ParentLI(parentli), LI(0) {} 229 230 /// reset - clear all data structures and start a new live interval. 231 void reset(LiveInterval *); 232 233 /// getLI - return the current live interval. 234 LiveInterval *getLI() const { return LI; } 235 236 /// defValue - define a value in LI from the ParentLI value VNI and Idx. 237 /// Idx does not have to be ParentVNI->def, but it must be contained within 238 /// ParentVNI's live range in ParentLI. 239 /// Return the new LI value. 240 VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 241 242 /// mapValue - map ParentVNI to the corresponding LI value at Idx. It is 243 /// assumed that ParentVNI is live at Idx. 244 /// If ParentVNI has not been defined by defValue, it is assumed that 245 /// ParentVNI->def dominates Idx. 246 /// If ParentVNI has been defined by defValue one or more times, a value that 247 /// dominates Idx will be returned. This may require creating extra phi-def 248 /// values and adding live ranges to LI. 249 /// If simple is not NULL, *simple will indicate if ParentVNI is a simply 250 /// mapped value. 251 VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0); 252 253 // extendTo - Find the last LI value defined in MBB at or before Idx. The 254 // parentli is assumed to be live at Idx. Extend the live range to include 255 // Idx. Return the found VNInfo, or NULL. 256 VNInfo *extendTo(const MachineBasicBlock *MBB, SlotIndex Idx); 257 258 /// isMapped - Return true is ParentVNI is a known mapped value. It may be a 259 /// simple 1-1 mapping or a complex mapping to later defs. 260 bool isMapped(const VNInfo *ParentVNI) const { 261 return Values.count(ParentVNI); 262 } 263 264 /// isComplexMapped - Return true if ParentVNI has received new definitions 265 /// with defValue. 266 bool isComplexMapped(const VNInfo *ParentVNI) const; 267 268 /// markComplexMapped - Mark ParentVNI as complex mapped regardless of the 269 /// number of definitions. 270 void markComplexMapped(const VNInfo *ParentVNI) { Values[ParentVNI] = 0; } 271 272 // addSimpleRange - Add a simple range from ParentLI to LI. 273 // ParentVNI must be live in the [Start;End) interval. 274 void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 275 276 /// addRange - Add live ranges to LI where [Start;End) intersects ParentLI. 277 /// All needed values whose def is not inside [Start;End) must be defined 278 /// beforehand so mapValue will work. 279 void addRange(SlotIndex Start, SlotIndex End); 280}; 281 282 283/// SplitEditor - Edit machine code and LiveIntervals for live range 284/// splitting. 285/// 286/// - Create a SplitEditor from a SplitAnalysis. 287/// - Start a new live interval with openIntv. 288/// - Mark the places where the new interval is entered using enterIntv* 289/// - Mark the ranges where the new interval is used with useIntv* 290/// - Mark the places where the interval is exited with exitIntv*. 291/// - Finish the current interval with closeIntv and repeat from 2. 292/// - Rewrite instructions with finish(). 293/// 294class SplitEditor { 295 SplitAnalysis &sa_; 296 LiveIntervals &LIS; 297 VirtRegMap &VRM; 298 MachineRegisterInfo &MRI; 299 MachineDominatorTree &MDT; 300 const TargetInstrInfo &TII; 301 const TargetRegisterInfo &TRI; 302 303 /// Edit - The current parent register and new intervals created. 304 LiveRangeEdit &Edit; 305 306 /// Index into Edit of the currently open interval. 307 /// The index 0 is used for the complement, so the first interval started by 308 /// openIntv will be 1. 309 unsigned OpenIdx; 310 311 typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 312 313 /// Allocator for the interval map. This will eventually be shared with 314 /// SlotIndexes and LiveIntervals. 315 RegAssignMap::Allocator Allocator; 316 317 /// RegAssign - Map of the assigned register indexes. 318 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 319 /// Idx. 320 RegAssignMap RegAssign; 321 322 /// LIMappers - One LiveIntervalMap or each interval in Edit. 323 SmallVector<LiveIntervalMap, 4> LIMappers; 324 325 /// defFromParent - Define Reg from ParentVNI at UseIdx using either 326 /// rematerialization or a COPY from parent. Return the new value. 327 VNInfo *defFromParent(unsigned RegIdx, 328 VNInfo *ParentVNI, 329 SlotIndex UseIdx, 330 MachineBasicBlock &MBB, 331 MachineBasicBlock::iterator I); 332 333 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 334 void rewriteAssigned(); 335 336 /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq 337 /// classes in ConEQ. 338 /// This must be done when Intvs[0] is styill live at all uses, before calling 339 /// ConEq.Distribute(). 340 void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 341 const ConnectedVNInfoEqClasses &ConEq); 342 343public: 344 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 345 /// Newly created intervals will be appended to newIntervals. 346 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 347 MachineDominatorTree&, LiveRangeEdit&); 348 349 /// getAnalysis - Get the corresponding analysis. 350 SplitAnalysis &getAnalysis() { return sa_; } 351 352 /// Create a new virtual register and live interval. 353 void openIntv(); 354 355 /// enterIntvBefore - Enter OpenLI before the instruction at Idx. If CurLI is 356 /// not live before Idx, a COPY is not inserted. 357 void enterIntvBefore(SlotIndex Idx); 358 359 /// enterIntvAtEnd - Enter OpenLI at the end of MBB. 360 void enterIntvAtEnd(MachineBasicBlock &MBB); 361 362 /// useIntv - indicate that all instructions in MBB should use OpenLI. 363 void useIntv(const MachineBasicBlock &MBB); 364 365 /// useIntv - indicate that all instructions in range should use OpenLI. 366 void useIntv(SlotIndex Start, SlotIndex End); 367 368 /// leaveIntvAfter - Leave OpenLI after the instruction at Idx. 369 void leaveIntvAfter(SlotIndex Idx); 370 371 /// leaveIntvAtTop - Leave the interval at the top of MBB. 372 /// Currently, only one value can leave the interval. 373 void leaveIntvAtTop(MachineBasicBlock &MBB); 374 375 /// closeIntv - Indicate that we are done editing the currently open 376 /// LiveInterval, and ranges can be trimmed. 377 void closeIntv(); 378 379 /// finish - after all the new live ranges have been created, compute the 380 /// remaining live range, and rewrite instructions to use the new registers. 381 void finish(); 382 383 /// dump - print the current interval maping to dbgs(). 384 void dump() const; 385 386 // ===--- High level methods ---=== 387 388 /// splitAroundLoop - Split CurLI into a separate live interval inside 389 /// the loop. 390 void splitAroundLoop(const MachineLoop*); 391 392 /// splitSingleBlocks - Split CurLI into a separate live interval inside each 393 /// basic block in Blocks. 394 void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 395 396 /// splitInsideBlock - Split CurLI into multiple intervals inside MBB. 397 void splitInsideBlock(const MachineBasicBlock *); 398}; 399 400} 401