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