SplitKit.h revision 212793
1170530Ssam//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 2170530Ssam// 3170530Ssam// The LLVM Compiler Infrastructure 4170530Ssam// 5170530Ssam// This file is distributed under the University of Illinois Open Source 6170530Ssam// License. See LICENSE.TXT for details. 7170530Ssam// 8170530Ssam//===----------------------------------------------------------------------===// 9170530Ssam// 10170530Ssam// This file contains the SplitAnalysis class as well as mutator functions for 11170530Ssam// live range splitting. 12170530Ssam// 13170530Ssam//===----------------------------------------------------------------------===// 14170530Ssam 15170530Ssam#include "llvm/ADT/SmallPtrSet.h" 16170530Ssam#include "llvm/ADT/DenseMap.h" 17170530Ssam#include "llvm/CodeGen/SlotIndexes.h" 18170530Ssam 19170530Ssamnamespace llvm { 20170530Ssam 21170530Ssamclass LiveInterval; 22170530Ssamclass LiveIntervals; 23170530Ssamclass MachineInstr; 24170530Ssamclass MachineLoop; 25170530Ssamclass MachineLoopInfo; 26170530Ssamclass MachineRegisterInfo; 27170530Ssamclass TargetInstrInfo; 28170530Ssamclass VirtRegMap; 29170530Ssamclass VNInfo; 30170530Ssam 31170530Ssam/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 32170530Ssam/// opportunities. 33170530Ssamclass SplitAnalysis { 34170530Ssampublic: 35170530Ssam const MachineFunction &mf_; 36170530Ssam const LiveIntervals &lis_; 37170530Ssam const MachineLoopInfo &loops_; 38170530Ssam const TargetInstrInfo &tii_; 39170530Ssam 40170530Ssam // Instructions using the the current register. 41170530Ssam typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 42170530Ssam InstrPtrSet usingInstrs_; 43170530Ssam 44170530Ssam // The number of instructions using curli in each basic block. 45170530Ssam typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 46170530Ssam BlockCountMap usingBlocks_; 47170530Ssam 48170530Ssam // The number of basic block using curli in each loop. 49170530Ssam typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 50170530Ssam LoopCountMap usingLoops_; 51170530Ssam 52170530Ssamprivate: 53170530Ssam // Current live interval. 54170530Ssam const LiveInterval *curli_; 55170530Ssam 56170530Ssam // Sumarize statistics by counting instructions using curli_. 57170530Ssam void analyzeUses(); 58170530Ssam 59170530Ssam /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 60170530Ssam /// analyzed. 61170530Ssam bool canAnalyzeBranch(const MachineBasicBlock *MBB); 62170530Ssam 63170530Ssampublic: 64170530Ssam SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 65170530Ssam const MachineLoopInfo &mli); 66170530Ssam 67170530Ssam /// analyze - set curli to the specified interval, and analyze how it may be 68170530Ssam /// split. 69170530Ssam void analyze(const LiveInterval *li); 70170530Ssam 71170530Ssam /// removeUse - Update statistics by noting that mi no longer uses curli. 72170530Ssam void removeUse(const MachineInstr *mi); 73170530Ssam 74170530Ssam const LiveInterval *getCurLI() { return curli_; } 75170530Ssam 76170530Ssam /// clear - clear all data structures so SplitAnalysis is ready to analyze a 77170530Ssam /// new interval. 78170530Ssam void clear(); 79170530Ssam 80170530Ssam typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 81170530Ssam typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 82173273Ssam 83173273Ssam // Sets of basic blocks surrounding a machine loop. 84173273Ssam struct LoopBlocks { 85173273Ssam BlockPtrSet Loop; // Blocks in the loop. 86173273Ssam BlockPtrSet Preds; // Loop predecessor blocks. 87173273Ssam BlockPtrSet Exits; // Loop exit blocks. 88170530Ssam 89170530Ssam void clear() { 90170530Ssam Loop.clear(); 91170530Ssam Preds.clear(); 92170530Ssam Exits.clear(); 93170530Ssam } 94170530Ssam }; 95170530Ssam 96170530Ssam // Calculate the block sets surrounding the loop. 97170530Ssam void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 98170530Ssam 99170530Ssam /// LoopPeripheralUse - how is a variable used in and around a loop? 100170530Ssam /// Peripheral blocks are the loop predecessors and exit blocks. 101170530Ssam enum LoopPeripheralUse { 102170530Ssam ContainedInLoop, // All uses are inside the loop. 103170530Ssam SinglePeripheral, // At most one instruction per peripheral block. 104170530Ssam MultiPeripheral, // Multiple instructions in some peripheral blocks. 105170530Ssam OutsideLoop // Uses outside loop periphery. 106173273Ssam }; 107173273Ssam 108173273Ssam /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 109173273Ssam /// and around the Loop. 110170530Ssam LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 111170530Ssam 112170530Ssam /// getCriticalExits - It may be necessary to partially break critical edges 113170530Ssam /// leaving the loop if an exit block has phi uses of curli. Collect the exit 114170530Ssam /// blocks that need special treatment into CriticalExits. 115170530Ssam void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 116170530Ssam 117170530Ssam /// canSplitCriticalExits - Return true if it is possible to insert new exit 118173273Ssam /// blocks before the blocks in CriticalExits. 119173273Ssam bool canSplitCriticalExits(const LoopBlocks &Blocks, 120173273Ssam BlockPtrSet &CriticalExits); 121173273Ssam 122173273Ssam /// getBestSplitLoop - Return the loop where curli may best be split to a 123173273Ssam /// separate register, or NULL. 124173273Ssam const MachineLoop *getBestSplitLoop(); 125173273Ssam 126173273Ssam /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 127173273Ssam /// having curli split to a new live interval. Return true if Blocks can be 128170530Ssam /// passed to SplitEditor::splitSingleBlocks. 129173273Ssam bool getMultiUseBlocks(BlockPtrSet &Blocks); 130173273Ssam 131170530Ssam /// getBlockForInsideSplit - If curli is contained inside a single basic block, 132170530Ssam /// and it wou pay to subdivide the interval inside that block, return it. 133170530Ssam /// Otherwise return NULL. The returned block can be passed to 134170530Ssam /// SplitEditor::splitInsideBlock. 135170530Ssam const MachineBasicBlock *getBlockForInsideSplit(); 136170530Ssam}; 137170530Ssam 138173273Ssam 139170530Ssam/// LiveIntervalMap - Map values from a large LiveInterval into a small 140170530Ssam/// interval that is a subset. Insert phi-def values as needed. This class is 141170530Ssam/// used by SplitEditor to create new smaller LiveIntervals. 142170530Ssam/// 143170530Ssam/// parentli_ is the larger interval, li_ is the subset interval. Every value 144170530Ssam/// in li_ corresponds to exactly one value in parentli_, and the live range 145170530Ssam/// of the value is contained within the live range of the parentli_ value. 146170530Ssam/// Values in parentli_ may map to any number of openli_ values, including 0. 147170530Ssamclass LiveIntervalMap { 148170530Ssam LiveIntervals &lis_; 149170530Ssam 150170530Ssam // The parent interval is never changed. 151170530Ssam const LiveInterval &parentli_; 152170530Ssam 153170530Ssam // The child interval's values are fully contained inside parentli_ values. 154170530Ssam LiveInterval &li_; 155170530Ssam 156170530Ssam typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 157170530Ssam 158170530Ssam // Map parentli_ values to simple values in li_ that are defined at the same 159170530Ssam // SlotIndex, or NULL for parentli_ values that have complex li_ defs. 160170530Ssam // Note there is a difference between values mapping to NULL (complex), and 161170530Ssam // values not present (unknown/unmapped). 162170530Ssam ValueMap valueMap_; 163170530Ssam 164170530Ssam // extendTo - Find the last li_ value defined in MBB at or before Idx. The 165170530Ssam // parentli_ is assumed to be live at Idx. Extend the live range to Idx. 166170530Ssam // Return the found VNInfo, or NULL. 167170530Ssam VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx); 168172226Ssam 169172226Ssam // addSimpleRange - Add a simple range from parentli_ to li_. 170170530Ssam // ParentVNI must be live in the [Start;End) interval. 171170530Ssam void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 172170530Ssam 173170530Ssampublic: 174170530Ssam LiveIntervalMap(LiveIntervals &lis, 175170530Ssam const LiveInterval &parentli, 176170530Ssam LiveInterval &li) 177170530Ssam : lis_(lis), parentli_(parentli), li_(li) {} 178170530Ssam 179170530Ssam /// defValue - define a value in li_ from the parentli_ value VNI and Idx. 180170530Ssam /// Idx does not have to be ParentVNI->def, but it must be contained within 181170530Ssam /// ParentVNI's live range in parentli_. 182170530Ssam /// Return the new li_ value. 183170530Ssam VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 184170530Ssam 185170530Ssam /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is 186170530Ssam /// assumed that ParentVNI is live at Idx. 187170530Ssam /// If ParentVNI has not been defined by defValue, it is assumed that 188170530Ssam /// ParentVNI->def dominates Idx. 189170530Ssam /// If ParentVNI has been defined by defValue one or more times, a value that 190170530Ssam /// dominates Idx will be returned. This may require creating extra phi-def 191170530Ssam /// values and adding live ranges to li_. 192173273Ssam VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx); 193170530Ssam 194170530Ssam /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_. 195170530Ssam /// All needed values whose def is not inside [Start;End) must be defined 196170530Ssam /// beforehand so mapValue will work. 197170530Ssam void addRange(SlotIndex Start, SlotIndex End); 198170530Ssam}; 199170530Ssam 200170530Ssam 201170530Ssam/// SplitEditor - Edit machine code and LiveIntervals for live range 202170530Ssam/// splitting. 203170530Ssam/// 204170530Ssam/// - Create a SplitEditor from a SplitAnalysis. 205170530Ssam/// - Start a new live interval with openIntv. 206170530Ssam/// - Mark the places where the new interval is entered using enterIntv* 207170530Ssam/// - Mark the ranges where the new interval is used with useIntv* 208173462Ssam/// - Mark the places where the interval is exited with exitIntv*. 209170530Ssam/// - Finish the current interval with closeIntv and repeat from 2. 210170530Ssam/// - Rewrite instructions with rewrite(). 211170530Ssam/// 212170530Ssamclass SplitEditor { 213170530Ssam SplitAnalysis &sa_; 214170530Ssam LiveIntervals &lis_; 215170530Ssam VirtRegMap &vrm_; 216170530Ssam MachineRegisterInfo &mri_; 217170530Ssam const TargetInstrInfo &tii_; 218170530Ssam 219170530Ssam /// curli_ - The immutable interval we are currently splitting. 220170530Ssam const LiveInterval *const curli_; 221170530Ssam 222170530Ssam /// dupli_ - Created as a copy of curli_, ranges are carved out as new 223170530Ssam /// intervals get added through openIntv / closeIntv. This is used to avoid 224170530Ssam /// editing curli_. 225170530Ssam LiveInterval *dupli_; 226173462Ssam 227170530Ssam /// Currently open LiveInterval. 228170530Ssam LiveInterval *openli_; 229170530Ssam 230173462Ssam /// createInterval - Create a new virtual register and LiveInterval with same 231170530Ssam /// register class and spill slot as curli. 232170530Ssam LiveInterval *createInterval(); 233170530Ssam 234170530Ssam /// getDupLI - Ensure dupli is created and return it. 235170530Ssam LiveInterval *getDupLI(); 236170530Ssam 237170530Ssam /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1 238170530Ssam /// mappings, and do not include values created by inserted copies. 239170530Ssam DenseMap<const VNInfo*, VNInfo*> valueMap_; 240170530Ssam 241170530Ssam /// mapValue - Return the openIntv value that corresponds to the given curli 242170530Ssam /// value. 243170530Ssam VNInfo *mapValue(const VNInfo *curliVNI); 244170530Ssam 245170530Ssam /// A dupli value is live through openIntv. 246170530Ssam bool liveThrough_; 247170530Ssam 248170530Ssam /// All the new intervals created for this split are added to intervals_. 249170530Ssam SmallVectorImpl<LiveInterval*> &intervals_; 250170530Ssam 251170530Ssam /// The index into intervals_ of the first interval we added. There may be 252170530Ssam /// others from before we got it. 253170530Ssam unsigned firstInterval; 254170530Ssam 255170530Ssam /// Insert a COPY instruction curli -> li. Allocate a new value from li 256170530Ssam /// defined by the COPY 257170530Ssam VNInfo *insertCopy(LiveInterval &LI, 258170530Ssam MachineBasicBlock &MBB, 259170530Ssam MachineBasicBlock::iterator I); 260170530Ssam 261170530Ssampublic: 262170530Ssam /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 263170530Ssam /// Newly created intervals will be appended to newIntervals. 264170530Ssam SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 265170530Ssam SmallVectorImpl<LiveInterval*> &newIntervals); 266170530Ssam 267170530Ssam /// getAnalysis - Get the corresponding analysis. 268170530Ssam SplitAnalysis &getAnalysis() { return sa_; } 269170530Ssam 270170530Ssam /// Create a new virtual register and live interval. 271170530Ssam void openIntv(); 272170530Ssam 273170530Ssam /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 274170530Ssam /// not live before Idx, a COPY is not inserted. 275170530Ssam void enterIntvBefore(SlotIndex Idx); 276170530Ssam 277170530Ssam /// enterIntvAtEnd - Enter openli at the end of MBB. 278170530Ssam /// PhiMBB is a successor inside openli where a PHI value is created. 279170530Ssam /// Currently, all entries must share the same PhiMBB. 280170530Ssam void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB); 281170530Ssam 282170530Ssam /// useIntv - indicate that all instructions in MBB should use openli. 283170530Ssam void useIntv(const MachineBasicBlock &MBB); 284170530Ssam 285170530Ssam /// useIntv - indicate that all instructions in range should use openli. 286170530Ssam void useIntv(SlotIndex Start, SlotIndex End); 287170530Ssam 288170530Ssam /// leaveIntvAfter - Leave openli after the instruction at Idx. 289170530Ssam void leaveIntvAfter(SlotIndex Idx); 290170530Ssam 291170530Ssam /// leaveIntvAtTop - Leave the interval at the top of MBB. 292170530Ssam /// Currently, only one value can leave the interval. 293170530Ssam void leaveIntvAtTop(MachineBasicBlock &MBB); 294170530Ssam 295170530Ssam /// closeIntv - Indicate that we are done editing the currently open 296170530Ssam /// LiveInterval, and ranges can be trimmed. 297170530Ssam void closeIntv(); 298170530Ssam 299170530Ssam /// rewrite - after all the new live ranges have been created, rewrite 300170530Ssam /// instructions using curli to use the new intervals. 301170530Ssam void rewrite(); 302170530Ssam 303170530Ssam // ===--- High level methods ---=== 304170530Ssam 305170530Ssam /// splitAroundLoop - Split curli into a separate live interval inside 306170530Ssam /// the loop. Return true if curli has been completely replaced, false if 307170530Ssam /// curli is still intact, and needs to be spilled or split further. 308170530Ssam bool splitAroundLoop(const MachineLoop*); 309170530Ssam 310170530Ssam /// splitSingleBlocks - Split curli into a separate live interval inside each 311170530Ssam /// basic block in Blocks. Return true if curli has been completely replaced, 312170530Ssam /// false if curli is still intact, and needs to be spilled or split further. 313170530Ssam bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 314170530Ssam 315170530Ssam /// splitInsideBlock - Split curli into multiple intervals inside MBB. Return 316170530Ssam /// true if curli has been completely replaced, false if curli is still 317170530Ssam /// intact, and needs to be spilled or split further. 318170530Ssam bool splitInsideBlock(const MachineBasicBlock *); 319170530Ssam}; 320170530Ssam 321170530Ssam} 322170530Ssam