PrologEpilogInserter.h revision abd0e3ddaf34e1589bae68eecb9fcfb7f14ac297 
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
31namespace 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 calculateCallsInformation(MachineFunction &Fn);
122    void calculateCalleeSavedRegisters(MachineFunction &Fn);
123    void insertCSRSpillsAndRestores(MachineFunction &Fn);
124    void calculateFrameObjectOffsets(MachineFunction &Fn);
125    void replaceFrameIndices(MachineFunction &Fn);
126    void scavengeFrameVirtualRegs(MachineFunction &Fn);
127    void insertPrologEpilogCode(MachineFunction &Fn);
128
129    // Initialize DFA sets, called before iterations.
130    void clearAnticAvailSets();
131    // Clear all sets constructed by shrink wrapping.
132    void clearAllSets();
133
134    // Initialize all shrink wrapping data.
135    void initShrinkWrappingInfo();
136
137    // Convienences for dealing with machine loops.
138    MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP);
139    MachineLoop* getTopLevelLoopParent(MachineLoop *LP);
140
141    // Propgate CSRs used in MBB to all MBBs of loop LP.
142    void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
143
144    // Convenience for recognizing return blocks.
145    bool isReturnBlock(MachineBasicBlock* MBB);
146
147#ifndef NDEBUG
148    // Debugging methods.
149
150    // Mark this function as having fast exit paths.
151    void findFastExitPath();
152
153    // Verify placement of spills/restores.
154    void verifySpillRestorePlacement();
155
156    std::string getBasicBlockName(const MachineBasicBlock* MBB);
157    std::string stringifyCSRegSet(const CSRegSet& s);
158    void dumpSet(const CSRegSet& s);
159    void dumpUsed(MachineBasicBlock* MBB);
160    void dumpAllUsed();
161    void dumpSets(MachineBasicBlock* MBB);
162    void dumpSets1(MachineBasicBlock* MBB);
163    void dumpAllSets();
164    void dumpSRSets();
165#endif
166
167  };
168} // End llvm namespace
169#endif
170