PrologEpilogInserter.h revision bafa3d9f6aaf24d721476ded7b1211ad57dd46c3 
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
33namespace 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
183