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;
103 // Machine function handle.
106 // Flag indicating that the current function
107 // has at least one "short" path in the machine
108 // CFG from the entry block to an exit block.
109 bool HasFastExitPath;
112 bool calculateSets(MachineFunction &Fn);
113 bool calcAnticInOut(MachineBasicBlock* MBB);
114 bool calcAvailInOut(MachineBasicBlock* MBB);
115 void calculateAnticAvail(MachineFunction &Fn);
116 bool addUsesForMEMERegion(MachineBasicBlock* MBB,
117 SmallVector<MachineBasicBlock*, 4>& blks);
118 bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks);
119 bool calcSpillPlacements(MachineBasicBlock* MBB,
120 SmallVector<MachineBasicBlock*, 4> &blks,
121 CSRegBlockMap &prevSpills);
122 bool calcRestorePlacements(MachineBasicBlock* MBB,
123 SmallVector<MachineBasicBlock*, 4> &blks,
124 CSRegBlockMap &prevRestores);
125 void placeSpillsAndRestores(MachineFunction &Fn);
126 void placeCSRSpillsAndRestores(MachineFunction &Fn);
127 void calculateCallsInformation(MachineFunction &Fn);
128 void calculateCalleeSavedRegisters(MachineFunction &Fn);
129 void insertCSRSpillsAndRestores(MachineFunction &Fn);
130 void calculateFrameObjectOffsets(MachineFunction &Fn);
131 void replaceFrameIndices(MachineFunction &Fn);
132 void scavengeFrameVirtualRegs(MachineFunction &Fn);
133 void insertPrologEpilogCode(MachineFunction &Fn);
135 // Initialize DFA sets, called before iterations.
136 void clearAnticAvailSets();
137 // Clear all sets constructed by shrink wrapping.
140 // Initialize all shrink wrapping data.
141 void initShrinkWrappingInfo();
143 // Convienences for dealing with machine loops.
144 MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP);
145 MachineLoop* getTopLevelLoopParent(MachineLoop *LP);
147 // Propgate CSRs used in MBB to all MBBs of loop LP.
148 void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
150 // Convenience for recognizing return blocks.
151 bool isReturnBlock(MachineBasicBlock* MBB);
154 // Debugging methods.
156 // Mark this function as having fast exit paths.
157 void findFastExitPath();
159 // Verify placement of spills/restores.
160 void verifySpillRestorePlacement();
162 std::string getBasicBlockName(const MachineBasicBlock* MBB);
163 std::string stringifyCSRegSet(const CSRegSet& s);
164 void dumpSet(const CSRegSet& s);
165 void dumpUsed(MachineBasicBlock* MBB);
167 void dumpSets(MachineBasicBlock* MBB);
168 void dumpSets1(MachineBasicBlock* MBB);
174 } // End llvm namespace