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