lib/CodeGen/PrologEpilogInserter.h

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