1 //===-- PrologEpilogInserter.h - Prolog/Epilog code insertion -*- C++ -* --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass is responsible for finalizing the functions frame layout, saving
11 // callee saved registers, and for emitting prolog & epilog code for the
14 // This pass must be run after register allocation. After this pass is
15 // executed, it is illegal to construct MO_FrameIndex operands.
17 // This pass also implements a shrink wrapping variant of prolog/epilog
20 //===----------------------------------------------------------------------===//
22 #ifndef LLVM_CODEGEN_PEI_H
23 #define LLVM_CODEGEN_PEI_H
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"
34 class MachineBasicBlock;
36 class PEI : public MachineFunctionPass {
39 PEI() : MachineFunctionPass(&ID) {}
41 const char *getPassName() const {
42 return "Prolog/Epilog Insertion & Frame Finalization";
45 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
47 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
48 /// frame indexes with appropriate references.
50 bool runOnMachineFunction(MachineFunction &Fn);
55 // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
56 // stack frame indexes.
57 unsigned MinCSFrameIndex, MaxCSFrameIndex;
59 // Analysis info for spill/restore placement.
60 // "CSR": "callee saved register".
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;
67 // CSRegBlockMap maps MachineBasicBlocks to sets of callee
68 // saved register indices.
69 typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap;
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)
79 CSRegBlockMap CSRUsed;
80 CSRegBlockMap AnticIn, AnticOut;
81 CSRegBlockMap AvailIn, AvailOut;
82 CSRegBlockMap CSRSave;
83 CSRegBlockMap CSRRestore;
85 // Entry and return blocks of the current function.
86 MachineBasicBlock* EntryBlock;
87 SmallVector<MachineBasicBlock*, 4> ReturnBlocks;
89 // Map of MBBs to top level MachineLoops.
90 DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops;
92 // Flag to control shrink wrapping per-function:
93 // may choose to skip shrink wrapping for certain
95 bool ShrinkWrapThisFunction;
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;
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;
109 // Machine function handle.
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;
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);
141 // Initialize DFA sets, called before iterations.
142 void clearAnticAvailSets();
143 // Clear all sets constructed by shrink wrapping.
146 // Initialize all shrink wrapping data.
147 void initShrinkWrappingInfo();
149 // Convienences for dealing with machine loops.
150 MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP);
151 MachineLoop* getTopLevelLoopParent(MachineLoop *LP);
153 // Propgate CSRs used in MBB to all MBBs of loop LP.
154 void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
156 // Convenience for recognizing return blocks.
157 bool isReturnBlock(MachineBasicBlock* MBB);
160 // Debugging methods.
162 // Mark this function as having fast exit paths.
163 void findFastExitPath();
165 // Verify placement of spills/restores.
166 void verifySpillRestorePlacement();
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);
173 void dumpSets(MachineBasicBlock* MBB);
174 void dumpSets1(MachineBasicBlock* MBB);
180 } // End llvm namespace