LLVM API Documentation

PrologEpilogInserter.h

Go to the documentation of this file.
00001 //===-- PrologEpilogInserter.h - Prolog/Epilog code insertion -*- C++ -* --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass is responsible for finalizing the functions frame layout, saving
00011 // callee saved registers, and for emitting prolog & epilog code for the
00012 // function.
00013 //
00014 // This pass must be run after register allocation.  After this pass is
00015 // executed, it is illegal to construct MO_FrameIndex operands.
00016 //
00017 // This pass also implements a shrink wrapping variant of prolog/epilog
00018 // insertion.
00019 //
00020 //===----------------------------------------------------------------------===//
00021 
00022 #ifndef LLVM_CODEGEN_PEI_H
00023 #define LLVM_CODEGEN_PEI_H
00024 
00025 #include "llvm/CodeGen/Passes.h"
00026 #include "llvm/CodeGen/MachineFunctionPass.h"
00027 #include "llvm/CodeGen/MachineLoopInfo.h"
00028 #include "llvm/ADT/SparseBitVector.h"
00029 #include "llvm/ADT/DenseMap.h"
00030 
00031 namespace llvm {
00032   class RegScavenger;
00033   class MachineBasicBlock;
00034 
00035   class PEI : public MachineFunctionPass {
00036   public:
00037     static char ID;
00038     PEI() : MachineFunctionPass(&ID) {}
00039 
00040     const char *getPassName() const {
00041       return "Prolog/Epilog Insertion & Frame Finalization";
00042     }
00043 
00044     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00045 
00046     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
00047     /// frame indexes with appropriate references.
00048     ///
00049     bool runOnMachineFunction(MachineFunction &Fn);
00050 
00051   private:
00052     RegScavenger *RS;
00053 
00054     // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
00055     // stack frame indexes.
00056     unsigned MinCSFrameIndex, MaxCSFrameIndex;
00057 
00058     // Analysis info for spill/restore placement.
00059     // "CSR": "callee saved register".
00060 
00061     // CSRegSet contains indices into the Callee Saved Register Info
00062     // vector built by calculateCalleeSavedRegisters() and accessed
00063     // via MF.getFrameInfo()->getCalleeSavedInfo().
00064     typedef SparseBitVector<> CSRegSet;
00065 
00066     // CSRegBlockMap maps MachineBasicBlocks to sets of callee
00067     // saved register indices.
00068     typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap;
00069 
00070     // Set and maps for computing CSR spill/restore placement:
00071     //  used in function (UsedCSRegs)
00072     //  used in a basic block (CSRUsed)
00073     //  anticipatable in a basic block (Antic{In,Out})
00074     //  available in a basic block (Avail{In,Out})
00075     //  to be spilled at the entry to a basic block (CSRSave)
00076     //  to be restored at the end of a basic block (CSRRestore)
00077     CSRegSet UsedCSRegs;
00078     CSRegBlockMap CSRUsed;
00079     CSRegBlockMap AnticIn, AnticOut;
00080     CSRegBlockMap AvailIn, AvailOut;
00081     CSRegBlockMap CSRSave;
00082     CSRegBlockMap CSRRestore;
00083 
00084     // Entry and return blocks of the current function.
00085     MachineBasicBlock* EntryBlock;
00086     SmallVector<MachineBasicBlock*, 4> ReturnBlocks;
00087 
00088     // Map of MBBs to top level MachineLoops.
00089     DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops;
00090 
00091     // Flag to control shrink wrapping per-function:
00092     // may choose to skip shrink wrapping for certain
00093     // functions.
00094     bool ShrinkWrapThisFunction;
00095 
00096 #ifndef NDEBUG
00097     // Machine function handle.
00098     MachineFunction* MF;
00099 
00100     // Flag indicating that the current function
00101     // has at least one "short" path in the machine
00102     // CFG from the entry block to an exit block.
00103     bool HasFastExitPath;
00104 #endif
00105 
00106     bool calculateSets(MachineFunction &Fn);
00107     bool calcAnticInOut(MachineBasicBlock* MBB);
00108     bool calcAvailInOut(MachineBasicBlock* MBB);
00109     void calculateAnticAvail(MachineFunction &Fn);
00110     bool addUsesForMEMERegion(MachineBasicBlock* MBB,
00111                               SmallVector<MachineBasicBlock*, 4>& blks);
00112     bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks);
00113     bool calcSpillPlacements(MachineBasicBlock* MBB,
00114                              SmallVector<MachineBasicBlock*, 4> &blks,
00115                              CSRegBlockMap &prevSpills);
00116     bool calcRestorePlacements(MachineBasicBlock* MBB,
00117                                SmallVector<MachineBasicBlock*, 4> &blks,
00118                                CSRegBlockMap &prevRestores);
00119     void placeSpillsAndRestores(MachineFunction &Fn);
00120     void placeCSRSpillsAndRestores(MachineFunction &Fn);
00121     void calculateCallsInformation(MachineFunction &Fn);
00122     void calculateCalleeSavedRegisters(MachineFunction &Fn);
00123     void insertCSRSpillsAndRestores(MachineFunction &Fn);
00124     void calculateFrameObjectOffsets(MachineFunction &Fn);
00125     void replaceFrameIndices(MachineFunction &Fn);
00126     void insertPrologEpilogCode(MachineFunction &Fn);
00127 
00128     // Initialize DFA sets, called before iterations.
00129     void clearAnticAvailSets();
00130     // Clear all sets constructed by shrink wrapping.
00131     void clearAllSets();
00132 
00133     // Initialize all shrink wrapping data.
00134     void initShrinkWrappingInfo();
00135 
00136     // Convienences for dealing with machine loops.
00137     MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP);
00138     MachineLoop* getTopLevelLoopParent(MachineLoop *LP);
00139 
00140     // Propgate CSRs used in MBB to all MBBs of loop LP.
00141     void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
00142 
00143     // Convenience for recognizing return blocks.
00144     bool isReturnBlock(MachineBasicBlock* MBB);
00145 
00146 #ifndef NDEBUG
00147     // Debugging methods.
00148 
00149     // Mark this function as having fast exit paths.
00150     void findFastExitPath();
00151 
00152     // Verify placement of spills/restores.
00153     void verifySpillRestorePlacement();
00154 
00155     std::string getBasicBlockName(const MachineBasicBlock* MBB);
00156     std::string stringifyCSRegSet(const CSRegSet& s);
00157     void dumpSet(const CSRegSet& s);
00158     void dumpUsed(MachineBasicBlock* MBB);
00159     void dumpAllUsed();
00160     void dumpSets(MachineBasicBlock* MBB);
00161     void dumpSets1(MachineBasicBlock* MBB);
00162     void dumpAllSets();
00163     void dumpSRSets();
00164 #endif
00165 
00166   };
00167 } // End llvm namespace
00168 #endif