1378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===-- PrologEpilogInserter.h - Prolog/Epilog code insertion -*- C++ -* --===// 2378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 3378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// The LLVM Compiler Infrastructure 4378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 5378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This file is distributed under the University of Illinois Open Source 6378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// License. See LICENSE.TXT for details. 7378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 8378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 9378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 10378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This pass is responsible for finalizing the functions frame layout, saving 11378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// callee saved registers, and for emitting prolog & epilog code for the 12378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// function. 13378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 14378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This pass must be run after register allocation. After this pass is 15378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// executed, it is illegal to construct MO_FrameIndex operands. 16378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 17378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This pass also implements a shrink wrapping variant of prolog/epilog 18378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// insertion. 19378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 20378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 21378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 22378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef LLVM_CODEGEN_PEI_H 23378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#define LLVM_CODEGEN_PEI_H 24378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 25378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/CodeGen/Passes.h" 26378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/CodeGen/MachineFunctionPass.h" 27378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/CodeGen/MachineLoopInfo.h" 28378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/ADT/SparseBitVector.h" 29378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/ADT/DenseMap.h" 30b58f498f7502e7e1833decbbbb4df771367c7341Jim Grosbach#include "llvm/Target/TargetRegisterInfo.h" 31378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 32378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbynamespace llvm { 33378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby class RegScavenger; 34378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby class MachineBasicBlock; 35378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 36378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby class PEI : public MachineFunctionPass { 37378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby public: 38378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby static char ID; 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson PEI() : MachineFunctionPass(ID) { 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePEIPass(*PassRegistry::getPassRegistry()); 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 42378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 43378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby virtual void getAnalysisUsage(AnalysisUsage &AU) const; 44378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 45378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby /// runOnMachineFunction - Insert prolog/epilog code and replace abstract 46378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby /// frame indexes with appropriate references. 47378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby /// 48378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool runOnMachineFunction(MachineFunction &Fn); 49378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 50378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby private: 51378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby RegScavenger *RS; 52378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 53378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved 54378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // stack frame indexes. 55378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned MinCSFrameIndex, MaxCSFrameIndex; 56378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 57378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Analysis info for spill/restore placement. 58378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // "CSR": "callee saved register". 59378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 60378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSRegSet contains indices into the Callee Saved Register Info 61378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // vector built by calculateCalleeSavedRegisters() and accessed 62378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // via MF.getFrameInfo()->getCalleeSavedInfo(). 63378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby typedef SparseBitVector<> CSRegSet; 64378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 65378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSRegBlockMap maps MachineBasicBlocks to sets of callee 66378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // saved register indices. 67378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap; 68378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 69378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Set and maps for computing CSR spill/restore placement: 70378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // used in function (UsedCSRegs) 71378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // used in a basic block (CSRUsed) 72378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // anticipatable in a basic block (Antic{In,Out}) 73378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // available in a basic block (Avail{In,Out}) 74378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // to be spilled at the entry to a basic block (CSRSave) 75378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // to be restored at the end of a basic block (CSRRestore) 76378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet UsedCSRegs; 77378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap CSRUsed; 78378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap AnticIn, AnticOut; 79378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap AvailIn, AvailOut; 80378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap CSRSave; 81378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap CSRRestore; 82378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 83378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Entry and return blocks of the current function. 84378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* EntryBlock; 85378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> ReturnBlocks; 86378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 87378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Map of MBBs to top level MachineLoops. 88378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops; 89378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 90378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Flag to control shrink wrapping per-function: 91378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // may choose to skip shrink wrapping for certain 92378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // functions. 93378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool ShrinkWrapThisFunction; 94378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 9565c58daa8b8985d2116216043103009815a55e77Jim Grosbach // Flag to control whether to use the register scavenger to resolve 9665c58daa8b8985d2116216043103009815a55e77Jim Grosbach // frame index materialization registers. Set according to 9765c58daa8b8985d2116216043103009815a55e77Jim Grosbach // TRI->requiresFrameIndexScavenging() for the curren function. 9865c58daa8b8985d2116216043103009815a55e77Jim Grosbach bool FrameIndexVirtualScavenging; 9965c58daa8b8985d2116216043103009815a55e77Jim Grosbach 100378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef NDEBUG 101378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Machine function handle. 102378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineFunction* MF; 103378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 104378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Flag indicating that the current function 105378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // has at least one "short" path in the machine 106378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CFG from the entry block to an exit block. 107378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool HasFastExitPath; 108378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 109378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 110378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool calculateSets(MachineFunction &Fn); 111378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool calcAnticInOut(MachineBasicBlock* MBB); 112378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool calcAvailInOut(MachineBasicBlock* MBB); 113378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void calculateAnticAvail(MachineFunction &Fn); 114378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool addUsesForMEMERegion(MachineBasicBlock* MBB, 115378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4>& blks); 116378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks); 117378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool calcSpillPlacements(MachineBasicBlock* MBB, 118378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> &blks, 119378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap &prevSpills); 120378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool calcRestorePlacements(MachineBasicBlock* MBB, 121378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> &blks, 122378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap &prevRestores); 123378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void placeSpillsAndRestores(MachineFunction &Fn); 124378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void placeCSRSpillsAndRestores(MachineFunction &Fn); 12533b350bf24be396a127c81af045468765731afc7Anton Korobeynikov void calculateCallsInformation(MachineFunction &Fn); 126378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void calculateCalleeSavedRegisters(MachineFunction &Fn); 127378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void insertCSRSpillsAndRestores(MachineFunction &Fn); 128378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void calculateFrameObjectOffsets(MachineFunction &Fn); 129378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void replaceFrameIndices(MachineFunction &Fn); 1303d6cb88a64fe67064de206405951eb326d86fc0cJim Grosbach void scavengeFrameVirtualRegs(MachineFunction &Fn); 131378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void insertPrologEpilogCode(MachineFunction &Fn); 132378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 133378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Initialize DFA sets, called before iterations. 134378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void clearAnticAvailSets(); 135378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Clear all sets constructed by shrink wrapping. 136378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void clearAllSets(); 137378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 138378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Initialize all shrink wrapping data. 139378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void initShrinkWrappingInfo(); 140378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 141378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Convienences for dealing with machine loops. 142378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP); 143378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoop* getTopLevelLoopParent(MachineLoop *LP); 144378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 145378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Propgate CSRs used in MBB to all MBBs of loop LP. 146378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP); 147378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 148378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Convenience for recognizing return blocks. 149378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool isReturnBlock(MachineBasicBlock* MBB); 150378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 151378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef NDEBUG 152378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Debugging methods. 153378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 154378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Mark this function as having fast exit paths. 155378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void findFastExitPath(); 156378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 157378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Verify placement of spills/restores. 158378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void verifySpillRestorePlacement(); 159378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 160378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::string getBasicBlockName(const MachineBasicBlock* MBB); 161378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::string stringifyCSRegSet(const CSRegSet& s); 162378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpSet(const CSRegSet& s); 163378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpUsed(MachineBasicBlock* MBB); 164378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpAllUsed(); 165378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpSets(MachineBasicBlock* MBB); 166378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpSets1(MachineBasicBlock* MBB); 167378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpAllSets(); 168378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby void dumpSRSets(); 169378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 170378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 171378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby }; 172378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} // End llvm namespace 173378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 174