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