1//===------ CFIFixup.cpp - Insert CFI remember/restore instructions -------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9
10// This pass inserts the necessary instructions to adjust for the inconsistency
11// of the call-frame information caused by final machine basic block layout.
12// The pass relies in constraints LLVM imposes on the placement of
13// save/restore points (cf. ShrinkWrap) and has certain preconditions about
14// placement of CFI instructions:
15// * For any two CFI instructions of the function prologue one dominates
16// and is post-dominated by the other.
17// * The function possibly contains multiple epilogue blocks, where each
18// epilogue block is complete and self-contained, i.e. CSR restore
19// instructions (and the corresponding CFI instructions)
20// are not split across two or more blocks.
21// * CFI instructions are not contained in any loops.
22
23// Thus, during execution, at the beginning and at the end of each basic block,
24// following the prologue, the function can be in one of two states:
25// - "has a call frame", if the function has executed the prologue, and
26// has not executed any epilogue
27// - "does not have a call frame", if the function has not executed the
28// prologue, or has executed an epilogue
29// which can be computed by a single RPO traversal.
30
31// The location of the prologue is determined by finding the first block in the
32// reverse traversal which contains CFI instructions.
33
34// In order to accommodate backends which do not generate unwind info in
35// epilogues we compute an additional property "strong no call frame on entry",
36// which is set for the entry point of the function and for every block
37// reachable from the entry along a path that does not execute the prologue. If
38// this property holds, it takes precedence over the "has a call frame"
39// property.
40
41// From the point of view of the unwind tables, the "has/does not have call
42// frame" state at beginning of each block is determined by the state at the end
43// of the previous block, in layout order. Where these states differ, we insert
44// compensating CFI instructions, which come in two flavours:
45
46// - CFI instructions, which reset the unwind table state to the initial one.
47// This is done by a target specific hook and is expected to be trivial
48// to implement, for example it could be:
49// .cfi_def_cfa <sp>, 0
50// .cfi_same_value <rN>
51// .cfi_same_value <rN-1>
52// ...
53// where <rN> are the callee-saved registers.
54// - CFI instructions, which reset the unwind table state to the one
55// created by the function prologue. These are
56// .cfi_restore_state
57// .cfi_remember_state
58// In this case we also insert a `.cfi_remember_state` after the last CFI
59// instruction in the function prologue.
60//
61// Known limitations:
62// * the pass cannot handle an epilogue preceding the prologue in the basic
63// block layout
64// * the pass does not handle functions where SP is used as a frame pointer and
65// SP adjustments up and down are done in different basic blocks (TODO)
66//===----------------------------------------------------------------------===//
67
68#include "llvm/CodeGen/CFIFixup.h"
69
70#include "llvm/ADT/DenseMap.h"
71#include "llvm/ADT/PostOrderIterator.h"
72#include "llvm/ADT/STLExtras.h"
73#include "llvm/ADT/SmallVector.h"
74#include "llvm/ADT/iterator_range.h"
75#include "llvm/CodeGen/MachineBasicBlock.h"
76#include "llvm/CodeGen/MachineFunction.h"
77#include "llvm/CodeGen/Passes.h"
78#include "llvm/CodeGen/TargetFrameLowering.h"
79#include "llvm/CodeGen/TargetInstrInfo.h"
80#include "llvm/CodeGen/TargetSubtargetInfo.h"
81#include "llvm/MC/MCAsmInfo.h"
82#include "llvm/MC/MCDwarf.h"
83#include "llvm/Target/TargetMachine.h"
84
85#include <iterator>
86
87using namespace llvm;
88
89#define DEBUG_TYPE "cfi-fixup"
90
91char CFIFixup::ID = 0;
92
93INITIALIZE_PASS(CFIFixup, "cfi-fixup",
94 "Insert CFI remember/restore state instructions", false, false)
95FunctionPass *llvm::createCFIFixup() { return new CFIFixup(); }
96
97static bool isPrologueCFIInstruction(const MachineInstr &MI) {
98 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
99 MI.getFlag(Flag: MachineInstr::FrameSetup);
100}
101
102static bool containsEpilogue(const MachineBasicBlock &MBB) {
103 return llvm::any_of(Range: llvm::reverse(C: MBB), P: [](const auto &MI) {
104 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
105 MI.getFlag(MachineInstr::FrameDestroy);
106 });
107}
108
109static MachineBasicBlock *
110findPrologueEnd(MachineFunction &MF, MachineBasicBlock::iterator &PrologueEnd) {
111 // Even though we should theoretically traverse the blocks in post-order, we
112 // can't encode correctly cases where prologue blocks are not laid out in
113 // topological order. Then, assuming topological order, we can just traverse
114 // the function in reverse.
115 for (MachineBasicBlock &MBB : reverse(C&: MF)) {
116 for (MachineInstr &MI : reverse(C: MBB.instrs())) {
117 if (!isPrologueCFIInstruction(MI))
118 continue;
119 PrologueEnd = std::next(x: MI.getIterator());
120 return &MBB;
121 }
122 }
123 return nullptr;
124}
125
126// Represents a basic block's relationship to the call frame. This metadata
127// reflects what the state *should* be, which may differ from the actual state
128// after final machine basic block layout.
129struct BlockFlags {
130 bool Reachable : 1;
131 bool StrongNoFrameOnEntry : 1;
132 bool HasFrameOnEntry : 1;
133 bool HasFrameOnExit : 1;
134 BlockFlags()
135 : Reachable(false), StrongNoFrameOnEntry(false), HasFrameOnEntry(false),
136 HasFrameOnExit(false) {}
137};
138
139// Most functions will have <= 32 basic blocks.
140using BlockFlagsVector = SmallVector<BlockFlags, 32>;
141
142// Computes the frame information for each block in the function. Frame info
143// for a block is inferred from its predecessors.
144static BlockFlagsVector
145computeBlockInfo(const MachineFunction &MF,
146 const MachineBasicBlock *PrologueBlock) {
147 BlockFlagsVector BlockInfo(MF.getNumBlockIDs());
148 BlockInfo[0].Reachable = true;
149 BlockInfo[0].StrongNoFrameOnEntry = true;
150
151 // Compute the presence/absence of frame at each basic block.
152 ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(&*MF.begin());
153 for (const MachineBasicBlock *MBB : RPOT) {
154 BlockFlags &Info = BlockInfo[MBB->getNumber()];
155
156 // Set to true if the current block contains the prologue or the epilogue,
157 // respectively.
158 bool HasPrologue = MBB == PrologueBlock;
159 bool HasEpilogue = false;
160
161 if (Info.HasFrameOnEntry || HasPrologue)
162 HasEpilogue = containsEpilogue(MBB: *MBB);
163
164 // If the function has a call frame at the entry of the current block or the
165 // current block contains the prologue, then the function has a call frame
166 // at the exit of the block, unless the block contains the epilogue.
167 Info.HasFrameOnExit = (Info.HasFrameOnEntry || HasPrologue) && !HasEpilogue;
168
169 // Set the successors' state on entry.
170 for (MachineBasicBlock *Succ : MBB->successors()) {
171 BlockFlags &SuccInfo = BlockInfo[Succ->getNumber()];
172 SuccInfo.Reachable = true;
173 SuccInfo.StrongNoFrameOnEntry |=
174 Info.StrongNoFrameOnEntry && !HasPrologue;
175 SuccInfo.HasFrameOnEntry = Info.HasFrameOnExit;
176 }
177 }
178
179 return BlockInfo;
180}
181
182// Represents the point within a basic block where we can insert an instruction.
183// Note that we need the MachineBasicBlock* as well as the iterator since the
184// iterator can point to the end of the block. Instructions are inserted
185// *before* the iterator.
186struct InsertionPoint {
187 MachineBasicBlock *MBB = nullptr;
188 MachineBasicBlock::iterator Iterator;
189};
190
191// Inserts a `.cfi_remember_state` instruction before PrologueEnd and a
192// `.cfi_restore_state` instruction before DstInsertPt. Returns an iterator
193// to the first instruction after the inserted `.cfi_restore_state` instruction.
194static InsertionPoint
195insertRememberRestorePair(const InsertionPoint &RememberInsertPt,
196 const InsertionPoint &RestoreInsertPt) {
197 MachineFunction &MF = *RememberInsertPt.MBB->getParent();
198 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
199
200 // Insert the `.cfi_remember_state` instruction.
201 unsigned CFIIndex =
202 MF.addFrameInst(Inst: MCCFIInstruction::createRememberState(L: nullptr));
203 BuildMI(BB&: *RememberInsertPt.MBB, I: RememberInsertPt.Iterator, MIMD: DebugLoc(),
204 MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
205 .addCFIIndex(CFIIndex);
206
207 // Insert the `.cfi_restore_state` instruction.
208 CFIIndex = MF.addFrameInst(Inst: MCCFIInstruction::createRestoreState(L: nullptr));
209
210 return {.MBB: RestoreInsertPt.MBB,
211 .Iterator: std::next(x: BuildMI(BB&: *RestoreInsertPt.MBB, I: RestoreInsertPt.Iterator,
212 MIMD: DebugLoc(), MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
213 .addCFIIndex(CFIIndex)
214 ->getIterator())};
215}
216
217// Copies all CFI instructions before PrologueEnd and inserts them before
218// DstInsertPt. Returns the iterator to the first instruction after the
219// inserted instructions.
220static InsertionPoint cloneCfiPrologue(const InsertionPoint &PrologueEnd,
221 const InsertionPoint &DstInsertPt) {
222 MachineFunction &MF = *DstInsertPt.MBB->getParent();
223
224 auto cloneCfiInstructions = [&](MachineBasicBlock::iterator Begin,
225 MachineBasicBlock::iterator End) {
226 auto ToClone = map_range(
227 C: make_filter_range(Range: make_range(x: Begin, y: End), Pred: isPrologueCFIInstruction),
228 F: [&](const MachineInstr &MI) { return MF.CloneMachineInstr(Orig: &MI); });
229 DstInsertPt.MBB->insert(I: DstInsertPt.Iterator, S: ToClone.begin(),
230 E: ToClone.end());
231 };
232
233 // Clone all CFI instructions from previous blocks.
234 for (auto &MBB : make_range(x: MF.begin(), y: PrologueEnd.MBB->getIterator()))
235 cloneCfiInstructions(MBB.begin(), MBB.end());
236 // Clone all CFI instructions from the final prologue block.
237 cloneCfiInstructions(PrologueEnd.MBB->begin(), PrologueEnd.Iterator);
238 return DstInsertPt;
239}
240
241// Fixes up the CFI instructions in a basic block to be consistent with the
242// intended frame state, adding or removing CFI instructions as necessary.
243// Returns true if a change was made and false otherwise.
244static bool
245fixupBlock(MachineBasicBlock &CurrBB, const BlockFlagsVector &BlockInfo,
246 SmallDenseMap<MBBSectionID, InsertionPoint> &InsertionPts,
247 const InsertionPoint &Prologue) {
248 const MachineFunction &MF = *CurrBB.getParent();
249 const TargetFrameLowering &TFL = *MF.getSubtarget().getFrameLowering();
250 const BlockFlags &Info = BlockInfo[CurrBB.getNumber()];
251
252 if (!Info.Reachable)
253 return false;
254
255 // If we don't need to perform full CFI fix up, we only need to fix up the
256 // first basic block in the section.
257 if (!TFL.enableFullCFIFixup(MF) && !CurrBB.isBeginSection())
258 return false;
259
260 // If the previous block and the current block are in the same section,
261 // the frame info will propagate from the previous block to the current one.
262 const BlockFlags &PrevInfo =
263 BlockInfo[std::prev(x: CurrBB.getIterator())->getNumber()];
264 bool HasFrame = PrevInfo.HasFrameOnExit && !CurrBB.isBeginSection();
265 bool NeedsFrame = Info.HasFrameOnEntry && !Info.StrongNoFrameOnEntry;
266
267#ifndef NDEBUG
268 if (!Info.StrongNoFrameOnEntry) {
269 for (auto *Pred : CurrBB.predecessors()) {
270 const BlockFlags &PredInfo = BlockInfo[Pred->getNumber()];
271 assert((!PredInfo.Reachable ||
272 Info.HasFrameOnEntry == PredInfo.HasFrameOnExit) &&
273 "Inconsistent call frame state");
274 }
275 }
276#endif
277
278 if (HasFrame == NeedsFrame)
279 return false;
280
281 if (!NeedsFrame) {
282 // Reset to the state upon function entry.
283 TFL.resetCFIToInitialState(MBB&: CurrBB);
284 return true;
285 }
286
287 // Reset to the "after prologue" state.
288 InsertionPoint &InsertPt = InsertionPts[CurrBB.getSectionID()];
289 if (InsertPt.MBB == nullptr) {
290 // CurBB is the first block in its section, so there is no "after
291 // prologue" state. Clone the CFI instructions from the prologue block
292 // to create it.
293 InsertPt = cloneCfiPrologue(PrologueEnd: Prologue, DstInsertPt: {.MBB: &CurrBB, .Iterator: CurrBB.begin()});
294 } else {
295 // There's an earlier block known to have a stack frame. Insert a
296 // `.cfi_remember_state` instruction into that block and a
297 // `.cfi_restore_state` instruction at the beginning of the current
298 // block.
299 InsertPt = insertRememberRestorePair(RememberInsertPt: InsertPt, RestoreInsertPt: {.MBB: &CurrBB, .Iterator: CurrBB.begin()});
300 }
301 return true;
302}
303
304bool CFIFixup::runOnMachineFunction(MachineFunction &MF) {
305 if (!MF.getSubtarget().getFrameLowering()->enableCFIFixup(MF))
306 return false;
307
308 if (MF.getNumBlockIDs() < 2)
309 return false;
310
311 // Find the prologue and the point where we can issue the first
312 // `.cfi_remember_state`.
313 MachineBasicBlock::iterator PrologueEnd;
314 MachineBasicBlock *PrologueBlock = findPrologueEnd(MF, PrologueEnd);
315 if (PrologueBlock == nullptr)
316 return false;
317
318 BlockFlagsVector BlockInfo = computeBlockInfo(MF, PrologueBlock);
319
320 // Walk the blocks of the function in "physical" order.
321 // Every block inherits the frame state (as recorded in the unwind tables)
322 // of the previous block. If the intended frame state is different, insert
323 // compensating CFI instructions.
324 bool Change = false;
325 // `InsertPt[sectionID]` always points to the point in a preceding block where
326 // we have to insert a `.cfi_remember_state`, in the case that the current
327 // block needs a `.cfi_restore_state`.
328 SmallDenseMap<MBBSectionID, InsertionPoint> InsertionPts;
329 InsertionPts[PrologueBlock->getSectionID()] = {.MBB: PrologueBlock, .Iterator: PrologueEnd};
330
331 assert(PrologueEnd != PrologueBlock->begin() &&
332 "Inconsistent notion of \"prologue block\"");
333
334 // No point starting before the prologue block.
335 // TODO: the unwind tables will still be incorrect if an epilogue physically
336 // preceeds the prologue.
337 for (MachineBasicBlock &MBB :
338 make_range(x: std::next(x: PrologueBlock->getIterator()), y: MF.end())) {
339 Change |=
340 fixupBlock(CurrBB&: MBB, BlockInfo, InsertionPts, Prologue: {.MBB: PrologueBlock, .Iterator: PrologueEnd});
341 }
342
343 return Change;
344}
345