1 //===-- PrologEpilogInserter.h - Prolog/Epilog code insertion -*- 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 pass is responsible for finalizing the functions frame layout, saving 11 // callee saved registers, and for emitting prolog & epilog code for the 12 // function. 13 // 14 // This pass must be run after register allocation. After this pass is 15 // executed, it is illegal to construct MO_FrameIndex operands. 16 // 17 // This pass also implements a shrink wrapping variant of prolog/epilog 18 // insertion. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #ifndef LLVM_CODEGEN_PEI_H 23 #define LLVM_CODEGEN_PEI_H 24 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/CodeGen/MachineFunctionPass.h" 27 #include "llvm/CodeGen/MachineLoopInfo.h" 28 #include "llvm/ADT/SparseBitVector.h" 29 #include "llvm/ADT/DenseMap.h" 30 #include "llvm/Target/TargetRegisterInfo.h" 31 32 namespace llvm { 33 class RegScavenger; 34 class MachineBasicBlock; 35 36 class PEI : public MachineFunctionPass { 37 public: 38 static char ID; PEI()39 PEI() : MachineFunctionPass(ID) { 40 initializePEIPass(*PassRegistry::getPassRegistry()); 41 } 42 43 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 44 45 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract 46 /// frame indexes with appropriate references. 47 /// 48 bool runOnMachineFunction(MachineFunction &Fn); 49 50 private: 51 RegScavenger *RS; 52 53 // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved 54 // stack frame indexes. 55 unsigned MinCSFrameIndex, MaxCSFrameIndex; 56 57 // Analysis info for spill/restore placement. 58 // "CSR": "callee saved register". 59 60 // CSRegSet contains indices into the Callee Saved Register Info 61 // vector built by calculateCalleeSavedRegisters() and accessed 62 // via MF.getFrameInfo()->getCalleeSavedInfo(). 63 typedef SparseBitVector<> CSRegSet; 64 65 // CSRegBlockMap maps MachineBasicBlocks to sets of callee 66 // saved register indices. 67 typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap; 68 69 // Set and maps for computing CSR spill/restore placement: 70 // used in function (UsedCSRegs) 71 // used in a basic block (CSRUsed) 72 // anticipatable in a basic block (Antic{In,Out}) 73 // available in a basic block (Avail{In,Out}) 74 // to be spilled at the entry to a basic block (CSRSave) 75 // to be restored at the end of a basic block (CSRRestore) 76 CSRegSet UsedCSRegs; 77 CSRegBlockMap CSRUsed; 78 CSRegBlockMap AnticIn, AnticOut; 79 CSRegBlockMap AvailIn, AvailOut; 80 CSRegBlockMap CSRSave; 81 CSRegBlockMap CSRRestore; 82 83 // Entry and return blocks of the current function. 84 MachineBasicBlock* EntryBlock; 85 SmallVector<MachineBasicBlock*, 4> ReturnBlocks; 86 87 // Map of MBBs to top level MachineLoops. 88 DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops; 89 90 // Flag to control shrink wrapping per-function: 91 // may choose to skip shrink wrapping for certain 92 // functions. 93 bool ShrinkWrapThisFunction; 94 95 // Flag to control whether to use the register scavenger to resolve 96 // frame index materialization registers. Set according to 97 // TRI->requiresFrameIndexScavenging() for the curren function. 98 bool FrameIndexVirtualScavenging; 99 100 #ifndef NDEBUG 101 // Machine function handle. 102 MachineFunction* MF; 103 104 // Flag indicating that the current function 105 // has at least one "short" path in the machine 106 // CFG from the entry block to an exit block. 107 bool HasFastExitPath; 108 #endif 109 110 bool calculateSets(MachineFunction &Fn); 111 bool calcAnticInOut(MachineBasicBlock* MBB); 112 bool calcAvailInOut(MachineBasicBlock* MBB); 113 void calculateAnticAvail(MachineFunction &Fn); 114 bool addUsesForMEMERegion(MachineBasicBlock* MBB, 115 SmallVector<MachineBasicBlock*, 4>& blks); 116 bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks); 117 bool calcSpillPlacements(MachineBasicBlock* MBB, 118 SmallVector<MachineBasicBlock*, 4> &blks, 119 CSRegBlockMap &prevSpills); 120 bool calcRestorePlacements(MachineBasicBlock* MBB, 121 SmallVector<MachineBasicBlock*, 4> &blks, 122 CSRegBlockMap &prevRestores); 123 void placeSpillsAndRestores(MachineFunction &Fn); 124 void placeCSRSpillsAndRestores(MachineFunction &Fn); 125 void calculateCallsInformation(MachineFunction &Fn); 126 void calculateCalleeSavedRegisters(MachineFunction &Fn); 127 void insertCSRSpillsAndRestores(MachineFunction &Fn); 128 void calculateFrameObjectOffsets(MachineFunction &Fn); 129 void replaceFrameIndices(MachineFunction &Fn); 130 void scavengeFrameVirtualRegs(MachineFunction &Fn); 131 void insertPrologEpilogCode(MachineFunction &Fn); 132 133 // Initialize DFA sets, called before iterations. 134 void clearAnticAvailSets(); 135 // Clear all sets constructed by shrink wrapping. 136 void clearAllSets(); 137 138 // Initialize all shrink wrapping data. 139 void initShrinkWrappingInfo(); 140 141 // Convienences for dealing with machine loops. 142 MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP); 143 MachineLoop* getTopLevelLoopParent(MachineLoop *LP); 144 145 // Propgate CSRs used in MBB to all MBBs of loop LP. 146 void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP); 147 148 // Convenience for recognizing return blocks. 149 bool isReturnBlock(MachineBasicBlock* MBB); 150 151 #ifndef NDEBUG 152 // Debugging methods. 153 154 // Mark this function as having fast exit paths. 155 void findFastExitPath(); 156 157 // Verify placement of spills/restores. 158 void verifySpillRestorePlacement(); 159 160 std::string getBasicBlockName(const MachineBasicBlock* MBB); 161 std::string stringifyCSRegSet(const CSRegSet& s); 162 void dumpSet(const CSRegSet& s); 163 void dumpUsed(MachineBasicBlock* MBB); 164 void dumpAllUsed(); 165 void dumpSets(MachineBasicBlock* MBB); 166 void dumpSets1(MachineBasicBlock* MBB); 167 void dumpAllSets(); 168 void dumpSRSets(); 169 #endif 170 171 }; 172 } // End llvm namespace 173 #endif 174