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