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/PostOrderIterator.h"
71#include "llvm/ADT/SmallBitVector.h"
72#include "llvm/CodeGen/Passes.h"
73#include "llvm/CodeGen/TargetFrameLowering.h"
74#include "llvm/CodeGen/TargetInstrInfo.h"
75#include "llvm/CodeGen/TargetSubtargetInfo.h"
76#include "llvm/MC/MCAsmInfo.h"
77#include "llvm/MC/MCDwarf.h"
78#include "llvm/Target/TargetMachine.h"
79
80using namespace llvm;
81
82#define DEBUG_TYPE "cfi-fixup"
83
84char CFIFixup::ID = 0;
85
86INITIALIZE_PASS(CFIFixup, "cfi-fixup",
87 "Insert CFI remember/restore state instructions", false, false)
88FunctionPass *llvm::createCFIFixup() { return new CFIFixup(); }
89
90static bool isPrologueCFIInstruction(const MachineInstr &MI) {
91 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
92 MI.getFlag(Flag: MachineInstr::FrameSetup);
93}
94
95static bool containsEpilogue(const MachineBasicBlock &MBB) {
96 return llvm::any_of(Range: llvm::reverse(C: MBB), P: [](const auto &MI) {
97 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
98 MI.getFlag(MachineInstr::FrameDestroy);
99 });
100}
101
102static MachineBasicBlock *
103findPrologueEnd(MachineFunction &MF, MachineBasicBlock::iterator &PrologueEnd) {
104 // Even though we should theoretically traverse the blocks in post-order, we
105 // can't encode correctly cases where prologue blocks are not laid out in
106 // topological order. Then, assuming topological order, we can just traverse
107 // the function in reverse.
108 for (MachineBasicBlock &MBB : reverse(C&: MF)) {
109 for (MachineInstr &MI : reverse(C: MBB.instrs())) {
110 if (!isPrologueCFIInstruction(MI))
111 continue;
112 PrologueEnd = std::next(x: MI.getIterator());
113 return &MBB;
114 }
115 }
116 return nullptr;
117}
118
119bool CFIFixup::runOnMachineFunction(MachineFunction &MF) {
120 const TargetFrameLowering &TFL = *MF.getSubtarget().getFrameLowering();
121 if (!TFL.enableCFIFixup(MF))
122 return false;
123
124 const unsigned NumBlocks = MF.getNumBlockIDs();
125 if (NumBlocks < 2)
126 return false;
127
128 // Find the prologue and the point where we can issue the first
129 // `.cfi_remember_state`.
130 MachineBasicBlock::iterator PrologueEnd;
131 MachineBasicBlock *PrologueBlock = findPrologueEnd(MF, PrologueEnd);
132 if (PrologueBlock == nullptr)
133 return false;
134
135 struct BlockFlags {
136 bool Reachable : 1;
137 bool StrongNoFrameOnEntry : 1;
138 bool HasFrameOnEntry : 1;
139 bool HasFrameOnExit : 1;
140 };
141 SmallVector<BlockFlags, 32> BlockInfo(NumBlocks, {.Reachable: false, .StrongNoFrameOnEntry: false, .HasFrameOnEntry: false, .HasFrameOnExit: false});
142 BlockInfo[0].Reachable = true;
143 BlockInfo[0].StrongNoFrameOnEntry = true;
144
145 // Compute the presence/absence of frame at each basic block.
146 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
147 for (MachineBasicBlock *MBB : RPOT) {
148 BlockFlags &Info = BlockInfo[MBB->getNumber()];
149
150 // Set to true if the current block contains the prologue or the epilogue,
151 // respectively.
152 bool HasPrologue = MBB == PrologueBlock;
153 bool HasEpilogue = false;
154
155 if (Info.HasFrameOnEntry || HasPrologue)
156 HasEpilogue = containsEpilogue(MBB: *MBB);
157
158 // If the function has a call frame at the entry of the current block or the
159 // current block contains the prologue, then the function has a call frame
160 // at the exit of the block, unless the block contains the epilogue.
161 Info.HasFrameOnExit = (Info.HasFrameOnEntry || HasPrologue) && !HasEpilogue;
162
163 // Set the successors' state on entry.
164 for (MachineBasicBlock *Succ : MBB->successors()) {
165 BlockFlags &SuccInfo = BlockInfo[Succ->getNumber()];
166 SuccInfo.Reachable = true;
167 SuccInfo.StrongNoFrameOnEntry |=
168 Info.StrongNoFrameOnEntry && !HasPrologue;
169 SuccInfo.HasFrameOnEntry = Info.HasFrameOnExit;
170 }
171 }
172
173 // Walk the blocks of the function in "physical" order.
174 // Every block inherits the frame state (as recorded in the unwind tables)
175 // of the previous block. If the intended frame state is different, insert
176 // compensating CFI instructions.
177 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
178 bool Change = false;
179 // `InsertPt` always points to the point in a preceding block where we have to
180 // insert a `.cfi_remember_state`, in the case that the current block needs a
181 // `.cfi_restore_state`.
182 MachineBasicBlock *InsertMBB = PrologueBlock;
183 MachineBasicBlock::iterator InsertPt = PrologueEnd;
184
185 assert(InsertPt != PrologueBlock->begin() &&
186 "Inconsistent notion of \"prologue block\"");
187
188 // No point starting before the prologue block.
189 // TODO: the unwind tables will still be incorrect if an epilogue physically
190 // preceeds the prologue.
191 MachineFunction::iterator CurrBB = std::next(x: PrologueBlock->getIterator());
192 bool HasFrame = BlockInfo[PrologueBlock->getNumber()].HasFrameOnExit;
193 while (CurrBB != MF.end()) {
194 const BlockFlags &Info = BlockInfo[CurrBB->getNumber()];
195 if (!Info.Reachable) {
196 ++CurrBB;
197 continue;
198 }
199
200#ifndef NDEBUG
201 if (!Info.StrongNoFrameOnEntry) {
202 for (auto *Pred : CurrBB->predecessors()) {
203 BlockFlags &PredInfo = BlockInfo[Pred->getNumber()];
204 assert((!PredInfo.Reachable ||
205 Info.HasFrameOnEntry == PredInfo.HasFrameOnExit) &&
206 "Inconsistent call frame state");
207 }
208 }
209#endif
210 if (!Info.StrongNoFrameOnEntry && Info.HasFrameOnEntry && !HasFrame) {
211 // Reset to the "after prologue" state.
212
213 // Insert a `.cfi_remember_state` into the last block known to have a
214 // stack frame.
215 unsigned CFIIndex =
216 MF.addFrameInst(Inst: MCCFIInstruction::createRememberState(L: nullptr));
217 BuildMI(BB&: *InsertMBB, I: InsertPt, MIMD: DebugLoc(),
218 MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
219 .addCFIIndex(CFIIndex);
220 // Insert a `.cfi_restore_state` at the beginning of the current block.
221 CFIIndex = MF.addFrameInst(Inst: MCCFIInstruction::createRestoreState(L: nullptr));
222 InsertPt = BuildMI(BB&: *CurrBB, I: CurrBB->begin(), MIMD: DebugLoc(),
223 MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION))
224 .addCFIIndex(CFIIndex);
225 ++InsertPt;
226 InsertMBB = &*CurrBB;
227 Change = true;
228 } else if ((Info.StrongNoFrameOnEntry || !Info.HasFrameOnEntry) &&
229 HasFrame) {
230 // Reset to the state upon function entry.
231 TFL.resetCFIToInitialState(MBB&: *CurrBB);
232 Change = true;
233 }
234
235 HasFrame = Info.HasFrameOnExit;
236 ++CurrBB;
237 }
238
239 return Change;
240}
241