SplitKit.h revision a17768f5822ab62bc18608e5ba473187bf726b84
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 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/SmallPtrSet.h" 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/CodeGen/SlotIndexes.h" 18 19namespace llvm { 20 21class LiveInterval; 22class LiveIntervals; 23class LiveRangeEdit; 24class MachineInstr; 25class MachineLoop; 26class MachineLoopInfo; 27class MachineRegisterInfo; 28class TargetInstrInfo; 29class VirtRegMap; 30class VNInfo; 31 32/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 33/// opportunities. 34class SplitAnalysis { 35public: 36 const MachineFunction &mf_; 37 const LiveIntervals &lis_; 38 const MachineLoopInfo &loops_; 39 const TargetInstrInfo &tii_; 40 41 // Instructions using the the current register. 42 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 43 InstrPtrSet usingInstrs_; 44 45 // The number of instructions using curli in each basic block. 46 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 47 BlockCountMap usingBlocks_; 48 49 // The number of basic block using curli in each loop. 50 typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 51 LoopCountMap usingLoops_; 52 53private: 54 // Current live interval. 55 const LiveInterval *curli_; 56 57 // Sumarize statistics by counting instructions using curli_. 58 void analyzeUses(); 59 60 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 61 /// analyzed. 62 bool canAnalyzeBranch(const MachineBasicBlock *MBB); 63 64public: 65 SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 66 const MachineLoopInfo &mli); 67 68 /// analyze - set curli to the specified interval, and analyze how it may be 69 /// split. 70 void analyze(const LiveInterval *li); 71 72 const LiveInterval *getCurLI() { return curli_; } 73 74 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 75 /// new interval. 76 void clear(); 77 78 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 79 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 80 81 // Sets of basic blocks surrounding a machine loop. 82 struct LoopBlocks { 83 BlockPtrSet Loop; // Blocks in the loop. 84 BlockPtrSet Preds; // Loop predecessor blocks. 85 BlockPtrSet Exits; // Loop exit blocks. 86 87 void clear() { 88 Loop.clear(); 89 Preds.clear(); 90 Exits.clear(); 91 } 92 }; 93 94 // Calculate the block sets surrounding the loop. 95 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 96 97 /// LoopPeripheralUse - how is a variable used in and around a loop? 98 /// Peripheral blocks are the loop predecessors and exit blocks. 99 enum LoopPeripheralUse { 100 ContainedInLoop, // All uses are inside the loop. 101 SinglePeripheral, // At most one instruction per peripheral block. 102 MultiPeripheral, // Multiple instructions in some peripheral blocks. 103 OutsideLoop // Uses outside loop periphery. 104 }; 105 106 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 107 /// and around the Loop. 108 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 109 110 /// getCriticalExits - It may be necessary to partially break critical edges 111 /// leaving the loop if an exit block has phi uses of curli. Collect the exit 112 /// blocks that need special treatment into CriticalExits. 113 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 114 115 /// canSplitCriticalExits - Return true if it is possible to insert new exit 116 /// blocks before the blocks in CriticalExits. 117 bool canSplitCriticalExits(const LoopBlocks &Blocks, 118 BlockPtrSet &CriticalExits); 119 120 /// getBestSplitLoop - Return the loop where curli may best be split to a 121 /// separate register, or NULL. 122 const MachineLoop *getBestSplitLoop(); 123 124 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 125 /// having curli split to a new live interval. Return true if Blocks can be 126 /// passed to SplitEditor::splitSingleBlocks. 127 bool getMultiUseBlocks(BlockPtrSet &Blocks); 128 129 /// getBlockForInsideSplit - If curli is contained inside a single basic block, 130 /// and it wou pay to subdivide the interval inside that block, return it. 131 /// Otherwise return NULL. The returned block can be passed to 132 /// SplitEditor::splitInsideBlock. 133 const MachineBasicBlock *getBlockForInsideSplit(); 134}; 135 136 137/// LiveIntervalMap - Map values from a large LiveInterval into a small 138/// interval that is a subset. Insert phi-def values as needed. This class is 139/// used by SplitEditor to create new smaller LiveIntervals. 140/// 141/// parentli_ is the larger interval, li_ is the subset interval. Every value 142/// in li_ corresponds to exactly one value in parentli_, and the live range 143/// of the value is contained within the live range of the parentli_ value. 144/// Values in parentli_ may map to any number of openli_ values, including 0. 145class LiveIntervalMap { 146 LiveIntervals &lis_; 147 148 // The parent interval is never changed. 149 const LiveInterval &parentli_; 150 151 // The child interval's values are fully contained inside parentli_ values. 152 LiveInterval *li_; 153 154 typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 155 156 // Map parentli_ values to simple values in li_ that are defined at the same 157 // SlotIndex, or NULL for parentli_ values that have complex li_ defs. 158 // Note there is a difference between values mapping to NULL (complex), and 159 // values not present (unknown/unmapped). 160 ValueMap valueMap_; 161 162public: 163 LiveIntervalMap(LiveIntervals &lis, 164 const LiveInterval &parentli) 165 : lis_(lis), parentli_(parentli), li_(0) {} 166 167 /// reset - clear all data structures and start a new live interval. 168 void reset(LiveInterval *); 169 170 /// getLI - return the current live interval. 171 LiveInterval *getLI() const { return li_; } 172 173 /// defValue - define a value in li_ from the parentli_ value VNI and Idx. 174 /// Idx does not have to be ParentVNI->def, but it must be contained within 175 /// ParentVNI's live range in parentli_. 176 /// Return the new li_ value. 177 VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 178 179 /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is 180 /// assumed that ParentVNI is live at Idx. 181 /// If ParentVNI has not been defined by defValue, it is assumed that 182 /// ParentVNI->def dominates Idx. 183 /// If ParentVNI has been defined by defValue one or more times, a value that 184 /// dominates Idx will be returned. This may require creating extra phi-def 185 /// values and adding live ranges to li_. 186 /// If simple is not NULL, *simple will indicate if ParentVNI is a simply 187 /// mapped value. 188 VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0); 189 190 // extendTo - Find the last li_ value defined in MBB at or before Idx. The 191 // parentli is assumed to be live at Idx. Extend the live range to include 192 // Idx. Return the found VNInfo, or NULL. 193 VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx); 194 195 /// isMapped - Return true is ParentVNI is a known mapped value. It may be a 196 /// simple 1-1 mapping or a complex mapping to later defs. 197 bool isMapped(const VNInfo *ParentVNI) const { 198 return valueMap_.count(ParentVNI); 199 } 200 201 /// isComplexMapped - Return true if ParentVNI has received new definitions 202 /// with defValue. 203 bool isComplexMapped(const VNInfo *ParentVNI) const; 204 205 // addSimpleRange - Add a simple range from parentli_ to li_. 206 // ParentVNI must be live in the [Start;End) interval. 207 void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 208 209 /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_. 210 /// All needed values whose def is not inside [Start;End) must be defined 211 /// beforehand so mapValue will work. 212 void addRange(SlotIndex Start, SlotIndex End); 213 214 /// defByCopyFrom - Insert a copy from Reg to li, assuming that Reg carries 215 /// ParentVNI. Add a minimal live range for the new value and return it. 216 VNInfo *defByCopyFrom(unsigned Reg, 217 const VNInfo *ParentVNI, 218 MachineBasicBlock &MBB, 219 MachineBasicBlock::iterator I); 220 221}; 222 223 224/// SplitEditor - Edit machine code and LiveIntervals for live range 225/// splitting. 226/// 227/// - Create a SplitEditor from a SplitAnalysis. 228/// - Start a new live interval with openIntv. 229/// - Mark the places where the new interval is entered using enterIntv* 230/// - Mark the ranges where the new interval is used with useIntv* 231/// - Mark the places where the interval is exited with exitIntv*. 232/// - Finish the current interval with closeIntv and repeat from 2. 233/// - Rewrite instructions with finish(). 234/// 235class SplitEditor { 236 SplitAnalysis &sa_; 237 LiveIntervals &lis_; 238 VirtRegMap &vrm_; 239 MachineRegisterInfo &mri_; 240 const TargetInstrInfo &tii_; 241 242 /// edit_ - The current parent register and new intervals created. 243 LiveRangeEdit &edit_; 244 245 /// curli_ - The immutable interval we are currently splitting. 246 const LiveInterval *const curli_; 247 248 /// dupli_ - Created as a copy of curli_, ranges are carved out as new 249 /// intervals get added through openIntv / closeIntv. This is used to avoid 250 /// editing curli_. 251 LiveIntervalMap dupli_; 252 253 /// Currently open LiveInterval. 254 LiveIntervalMap openli_; 255 256 /// intervalsLiveAt - Return true if any member of intervals_ is live at Idx. 257 bool intervalsLiveAt(SlotIndex Idx) const; 258 259 /// Values in curli whose live range has been truncated when entering an open 260 /// li. 261 SmallPtrSet<const VNInfo*, 8> truncatedValues; 262 263 /// addTruncSimpleRange - Add the given simple range to dupli_ after 264 /// truncating any overlap with intervals_. 265 void addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI); 266 267 /// computeRemainder - Compute the dupli liveness as the complement of all the 268 /// new intervals. 269 void computeRemainder(); 270 271 /// rewrite - Rewrite all uses of reg to use the new registers. 272 void rewrite(unsigned reg); 273 274public: 275 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 276 /// Newly created intervals will be appended to newIntervals. 277 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, LiveRangeEdit&); 278 279 /// getAnalysis - Get the corresponding analysis. 280 SplitAnalysis &getAnalysis() { return sa_; } 281 282 /// Create a new virtual register and live interval. 283 void openIntv(); 284 285 /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 286 /// not live before Idx, a COPY is not inserted. 287 void enterIntvBefore(SlotIndex Idx); 288 289 /// enterIntvAtEnd - Enter openli at the end of MBB. 290 void enterIntvAtEnd(MachineBasicBlock &MBB); 291 292 /// useIntv - indicate that all instructions in MBB should use openli. 293 void useIntv(const MachineBasicBlock &MBB); 294 295 /// useIntv - indicate that all instructions in range should use openli. 296 void useIntv(SlotIndex Start, SlotIndex End); 297 298 /// leaveIntvAfter - Leave openli after the instruction at Idx. 299 void leaveIntvAfter(SlotIndex Idx); 300 301 /// leaveIntvAtTop - Leave the interval at the top of MBB. 302 /// Currently, only one value can leave the interval. 303 void leaveIntvAtTop(MachineBasicBlock &MBB); 304 305 /// closeIntv - Indicate that we are done editing the currently open 306 /// LiveInterval, and ranges can be trimmed. 307 void closeIntv(); 308 309 /// finish - after all the new live ranges have been created, compute the 310 /// remaining live range, and rewrite instructions to use the new registers. 311 void finish(); 312 313 // ===--- High level methods ---=== 314 315 /// splitAroundLoop - Split curli into a separate live interval inside 316 /// the loop. 317 void splitAroundLoop(const MachineLoop*); 318 319 /// splitSingleBlocks - Split curli into a separate live interval inside each 320 /// basic block in Blocks. 321 void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 322 323 /// splitInsideBlock - Split curli into multiple intervals inside MBB. 324 void splitInsideBlock(const MachineBasicBlock *); 325}; 326 327} 328