SplitKit.h revision 6a0dc079efe7acf7e71cc4c0948fe814f35ba091
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 18namespace llvm { 19 20class LiveInterval; 21class LiveIntervals; 22class MachineBasicBlock; 23class MachineInstr; 24class MachineFunction; 25class MachineFunctionPass; 26class MachineLoop; 27class MachineLoopInfo; 28class TargetInstrInfo; 29 30class SplitAnalysis { 31 const MachineFunction &mf_; 32 const LiveIntervals &lis_; 33 const MachineLoopInfo &loops_; 34 const TargetInstrInfo &tii_; 35 36 // Current live interval. 37 const LiveInterval *curli_; 38 39 // Instructions using the the current register. 40 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 41 InstrPtrSet usingInstrs_; 42 43 // The number of instructions using curli in each basic block. 44 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 45 BlockCountMap usingBlocks_; 46 47 // Loops where the curent interval is used. 48 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 49 LoopPtrSet usingLoops_; 50 51 // Sumarize statistics by counting instructions using curli_. 52 void analyzeUses(); 53 54 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 55 /// analyzed. 56 bool canAnalyzeBranch(const MachineBasicBlock *MBB); 57 58public: 59 SplitAnalysis(const MachineFunction *mf, const LiveIntervals *lis, 60 const MachineLoopInfo *mli); 61 62 /// analyze - set curli to the specified interval, and analyze how it may be 63 /// split. 64 void analyze(const LiveInterval *li); 65 66 /// clear - clear all data structures so SplitAnalysis is ready to analyze a 67 /// new interval. 68 void clear(); 69 70 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 71 72 // Sets of basic blocks surrounding a machine loop. 73 struct LoopBlocks { 74 BlockPtrSet Loop; // Blocks in the loop. 75 BlockPtrSet Preds; // Loop predecessor blocks. 76 BlockPtrSet Exits; // Loop exit blocks. 77 78 void clear() { 79 Loop.clear(); 80 Preds.clear(); 81 Exits.clear(); 82 } 83 }; 84 85 // Calculate the block sets surrounding the loop. 86 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 87 88 /// LoopPeripheralUse - how is a variable used in and around a loop? 89 /// Peripheral blocks are the loop predecessors and exit blocks. 90 enum LoopPeripheralUse { 91 ContainedInLoop, // All uses are inside the loop. 92 SinglePeripheral, // At most one instruction per peripheral block. 93 MultiPeripheral, // Multiple instructions in some peripheral blocks. 94 OutsideLoop // Uses outside loop periphery. 95 }; 96 97 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 98 /// and around the Loop. 99 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 100 101 /// getCriticalExits - It may be necessary to partially break critical edges 102 /// leaving the loop if an exit block has phi uses of curli. Collect the exit 103 /// blocks that need special treatment into CriticalExits. 104 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 105 106 /// canSplitCriticalExits - Return true if it is possible to insert new exit 107 /// blocks before the blocks in CriticalExits. 108 bool canSplitCriticalExits(const LoopBlocks &Blocks, 109 BlockPtrSet &CriticalExits); 110 111 /// getBestSplitLoop - Return the loop where curli may best be split to a 112 /// separate register, or NULL. 113 const MachineLoop *getBestSplitLoop(); 114}; 115 116/// splitAroundLoop - Try to split curli into a separate live interval inside 117/// the loop. Retun true on success. 118bool splitAroundLoop(SplitAnalysis&, const MachineLoop*); 119 120} 121