1//===------ CFIInstrInserter.cpp - Insert additional CFI 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/// \file This pass verifies incoming and outgoing CFA information of basic
10/// blocks. CFA information is information about offset and register set by CFI
11/// directives, valid at the start and end of a basic block. This pass checks
12/// that outgoing information of predecessors matches incoming information of
13/// their successors. Then it checks if blocks have correct CFA calculation rule
14/// set and inserts additional CFI instruction at their beginnings if they
15/// don't. CFI instructions are inserted if basic blocks have incorrect offset
16/// or register set by previous blocks, as a result of a non-linear layout of
17/// blocks in a function.
18//===----------------------------------------------------------------------===//
19
20#include "llvm/ADT/DepthFirstIterator.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/Passes.h"
24#include "llvm/CodeGen/TargetFrameLowering.h"
25#include "llvm/CodeGen/TargetInstrInfo.h"
26#include "llvm/CodeGen/TargetSubtargetInfo.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/MC/MCDwarf.h"
29using namespace llvm;
30
31static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
32 cl::desc("Verify Call Frame Information instructions"),
33 cl::init(Val: false),
34 cl::Hidden);
35
36namespace {
37class CFIInstrInserter : public MachineFunctionPass {
38 public:
39 static char ID;
40
41 CFIInstrInserter() : MachineFunctionPass(ID) {
42 initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry());
43 }
44
45 void getAnalysisUsage(AnalysisUsage &AU) const override {
46 AU.setPreservesAll();
47 MachineFunctionPass::getAnalysisUsage(AU);
48 }
49
50 bool runOnMachineFunction(MachineFunction &MF) override {
51 if (!MF.needsFrameMoves())
52 return false;
53
54 MBBVector.resize(new_size: MF.getNumBlockIDs());
55 calculateCFAInfo(MF);
56
57 if (VerifyCFI) {
58 if (unsigned ErrorNum = verify(MF))
59 report_fatal_error(reason: "Found " + Twine(ErrorNum) +
60 " in/out CFI information errors.");
61 }
62 bool insertedCFI = insertCFIInstrs(MF);
63 MBBVector.clear();
64 return insertedCFI;
65 }
66
67 private:
68 struct MBBCFAInfo {
69 MachineBasicBlock *MBB;
70 /// Value of cfa offset valid at basic block entry.
71 int64_t IncomingCFAOffset = -1;
72 /// Value of cfa offset valid at basic block exit.
73 int64_t OutgoingCFAOffset = -1;
74 /// Value of cfa register valid at basic block entry.
75 unsigned IncomingCFARegister = 0;
76 /// Value of cfa register valid at basic block exit.
77 unsigned OutgoingCFARegister = 0;
78 /// Set of callee saved registers saved at basic block entry.
79 BitVector IncomingCSRSaved;
80 /// Set of callee saved registers saved at basic block exit.
81 BitVector OutgoingCSRSaved;
82 /// If in/out cfa offset and register values for this block have already
83 /// been set or not.
84 bool Processed = false;
85 };
86
87#define INVALID_REG UINT_MAX
88#define INVALID_OFFSET INT_MAX
89 /// contains the location where CSR register is saved.
90 struct CSRSavedLocation {
91 CSRSavedLocation(std::optional<unsigned> R, std::optional<int> O)
92 : Reg(R), Offset(O) {}
93 std::optional<unsigned> Reg;
94 std::optional<int> Offset;
95 };
96
97 /// Contains cfa offset and register values valid at entry and exit of basic
98 /// blocks.
99 std::vector<MBBCFAInfo> MBBVector;
100
101 /// Map the callee save registers to the locations where they are saved.
102 SmallDenseMap<unsigned, CSRSavedLocation, 16> CSRLocMap;
103
104 /// Calculate cfa offset and register values valid at entry and exit for all
105 /// basic blocks in a function.
106 void calculateCFAInfo(MachineFunction &MF);
107 /// Calculate cfa offset and register values valid at basic block exit by
108 /// checking the block for CFI instructions. Block's incoming CFA info remains
109 /// the same.
110 void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo);
111 /// Update in/out cfa offset and register values for successors of the basic
112 /// block.
113 void updateSuccCFAInfo(MBBCFAInfo &MBBInfo);
114
115 /// Check if incoming CFA information of a basic block matches outgoing CFA
116 /// information of the previous block. If it doesn't, insert CFI instruction
117 /// at the beginning of the block that corrects the CFA calculation rule for
118 /// that block.
119 bool insertCFIInstrs(MachineFunction &MF);
120 /// Return the cfa offset value that should be set at the beginning of a MBB
121 /// if needed. The negated value is needed when creating CFI instructions that
122 /// set absolute offset.
123 int64_t getCorrectCFAOffset(MachineBasicBlock *MBB) {
124 return MBBVector[MBB->getNumber()].IncomingCFAOffset;
125 }
126
127 void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
128 void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
129 /// Go through each MBB in a function and check that outgoing offset and
130 /// register of its predecessors match incoming offset and register of that
131 /// MBB, as well as that incoming offset and register of its successors match
132 /// outgoing offset and register of the MBB.
133 unsigned verify(MachineFunction &MF);
134};
135} // namespace
136
137char CFIInstrInserter::ID = 0;
138INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
139 "Check CFA info and insert CFI instructions if needed", false,
140 false)
141FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
142
143void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
144 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
145 // Initial CFA offset value i.e. the one valid at the beginning of the
146 // function.
147 int InitialOffset =
148 MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);
149 // Initial CFA register value i.e. the one valid at the beginning of the
150 // function.
151 Register InitialRegister =
152 MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);
153 InitialRegister = TRI.getDwarfRegNum(RegNum: InitialRegister, isEH: true);
154 unsigned NumRegs = TRI.getNumSupportedRegs(MF);
155
156 // Initialize MBBMap.
157 for (MachineBasicBlock &MBB : MF) {
158 MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
159 MBBInfo.MBB = &MBB;
160 MBBInfo.IncomingCFAOffset = InitialOffset;
161 MBBInfo.OutgoingCFAOffset = InitialOffset;
162 MBBInfo.IncomingCFARegister = InitialRegister;
163 MBBInfo.OutgoingCFARegister = InitialRegister;
164 MBBInfo.IncomingCSRSaved.resize(N: NumRegs);
165 MBBInfo.OutgoingCSRSaved.resize(N: NumRegs);
166 }
167 CSRLocMap.clear();
168
169 // Set in/out cfa info for all blocks in the function. This traversal is based
170 // on the assumption that the first block in the function is the entry block
171 // i.e. that it has initial cfa offset and register values as incoming CFA
172 // information.
173 updateSuccCFAInfo(MBBInfo&: MBBVector[MF.front().getNumber()]);
174}
175
176void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
177 // Outgoing cfa offset set by the block.
178 int64_t SetOffset = MBBInfo.IncomingCFAOffset;
179 // Outgoing cfa register set by the block.
180 unsigned SetRegister = MBBInfo.IncomingCFARegister;
181 MachineFunction *MF = MBBInfo.MBB->getParent();
182 const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions();
183 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
184 unsigned NumRegs = TRI.getNumSupportedRegs(*MF);
185 BitVector CSRSaved(NumRegs), CSRRestored(NumRegs);
186
187 // Determine cfa offset and register set by the block.
188 for (MachineInstr &MI : *MBBInfo.MBB) {
189 if (MI.isCFIInstruction()) {
190 std::optional<unsigned> CSRReg;
191 std::optional<int64_t> CSROffset;
192 unsigned CFIIndex = MI.getOperand(i: 0).getCFIIndex();
193 const MCCFIInstruction &CFI = Instrs[CFIIndex];
194 switch (CFI.getOperation()) {
195 case MCCFIInstruction::OpDefCfaRegister:
196 SetRegister = CFI.getRegister();
197 break;
198 case MCCFIInstruction::OpDefCfaOffset:
199 SetOffset = CFI.getOffset();
200 break;
201 case MCCFIInstruction::OpAdjustCfaOffset:
202 SetOffset += CFI.getOffset();
203 break;
204 case MCCFIInstruction::OpDefCfa:
205 SetRegister = CFI.getRegister();
206 SetOffset = CFI.getOffset();
207 break;
208 case MCCFIInstruction::OpOffset:
209 CSROffset = CFI.getOffset();
210 break;
211 case MCCFIInstruction::OpRegister:
212 CSRReg = CFI.getRegister2();
213 break;
214 case MCCFIInstruction::OpRelOffset:
215 CSROffset = CFI.getOffset() - SetOffset;
216 break;
217 case MCCFIInstruction::OpRestore:
218 CSRRestored.set(CFI.getRegister());
219 break;
220 case MCCFIInstruction::OpLLVMDefAspaceCfa:
221 // TODO: Add support for handling cfi_def_aspace_cfa.
222#ifndef NDEBUG
223 report_fatal_error(
224 "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA "
225 "may be incorrect!\n");
226#endif
227 break;
228 case MCCFIInstruction::OpRememberState:
229 // TODO: Add support for handling cfi_remember_state.
230#ifndef NDEBUG
231 report_fatal_error(
232 "Support for cfi_remember_state not implemented! Value of CFA "
233 "may be incorrect!\n");
234#endif
235 break;
236 case MCCFIInstruction::OpRestoreState:
237 // TODO: Add support for handling cfi_restore_state.
238#ifndef NDEBUG
239 report_fatal_error(
240 "Support for cfi_restore_state not implemented! Value of CFA may "
241 "be incorrect!\n");
242#endif
243 break;
244 // Other CFI directives do not affect CFA value.
245 case MCCFIInstruction::OpUndefined:
246 case MCCFIInstruction::OpSameValue:
247 case MCCFIInstruction::OpEscape:
248 case MCCFIInstruction::OpWindowSave:
249 case MCCFIInstruction::OpNegateRAState:
250 case MCCFIInstruction::OpGnuArgsSize:
251 case MCCFIInstruction::OpLabel:
252 break;
253 }
254 if (CSRReg || CSROffset) {
255 auto It = CSRLocMap.find(Val: CFI.getRegister());
256 if (It == CSRLocMap.end()) {
257 CSRLocMap.insert(
258 KV: {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)});
259 } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) {
260 llvm_unreachable("Different saved locations for the same CSR");
261 }
262 CSRSaved.set(CFI.getRegister());
263 }
264 }
265 }
266
267 MBBInfo.Processed = true;
268
269 // Update outgoing CFA info.
270 MBBInfo.OutgoingCFAOffset = SetOffset;
271 MBBInfo.OutgoingCFARegister = SetRegister;
272
273 // Update outgoing CSR info.
274 BitVector::apply(f: [](auto x, auto y, auto z) { return (x | y) & ~z; },
275 Out&: MBBInfo.OutgoingCSRSaved, Arg: MBBInfo.IncomingCSRSaved, Args: CSRSaved,
276 Args: CSRRestored);
277}
278
279void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
280 SmallVector<MachineBasicBlock *, 4> Stack;
281 Stack.push_back(Elt: MBBInfo.MBB);
282
283 do {
284 MachineBasicBlock *Current = Stack.pop_back_val();
285 MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
286 calculateOutgoingCFAInfo(MBBInfo&: CurrentInfo);
287 for (auto *Succ : CurrentInfo.MBB->successors()) {
288 MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
289 if (!SuccInfo.Processed) {
290 SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
291 SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
292 SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved;
293 Stack.push_back(Elt: Succ);
294 }
295 }
296 } while (!Stack.empty());
297}
298
299bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
300 const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
301 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
302 bool InsertedCFIInstr = false;
303
304 BitVector SetDifference;
305 for (MachineBasicBlock &MBB : MF) {
306 // Skip the first MBB in a function
307 if (MBB.getNumber() == MF.front().getNumber()) continue;
308
309 const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
310 auto MBBI = MBBInfo.MBB->begin();
311 DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
312
313 // If the current MBB will be placed in a unique section, a full DefCfa
314 // must be emitted.
315 const bool ForceFullCFA = MBB.isBeginSection();
316
317 if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset &&
318 PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) ||
319 ForceFullCFA) {
320 // If both outgoing offset and register of a previous block don't match
321 // incoming offset and register of this block, or if this block begins a
322 // section, add a def_cfa instruction with the correct offset and
323 // register for this block.
324 unsigned CFIIndex = MF.addFrameInst(Inst: MCCFIInstruction::cfiDefCfa(
325 L: nullptr, Register: MBBInfo.IncomingCFARegister, Offset: getCorrectCFAOffset(MBB: &MBB)));
326 BuildMI(BB&: *MBBInfo.MBB, I: MBBI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION))
327 .addCFIIndex(CFIIndex);
328 InsertedCFIInstr = true;
329 } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
330 // If outgoing offset of a previous block doesn't match incoming offset
331 // of this block, add a def_cfa_offset instruction with the correct
332 // offset for this block.
333 unsigned CFIIndex = MF.addFrameInst(Inst: MCCFIInstruction::cfiDefCfaOffset(
334 L: nullptr, Offset: getCorrectCFAOffset(MBB: &MBB)));
335 BuildMI(BB&: *MBBInfo.MBB, I: MBBI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION))
336 .addCFIIndex(CFIIndex);
337 InsertedCFIInstr = true;
338 } else if (PrevMBBInfo->OutgoingCFARegister !=
339 MBBInfo.IncomingCFARegister) {
340 unsigned CFIIndex =
341 MF.addFrameInst(Inst: MCCFIInstruction::createDefCfaRegister(
342 L: nullptr, Register: MBBInfo.IncomingCFARegister));
343 BuildMI(BB&: *MBBInfo.MBB, I: MBBI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION))
344 .addCFIIndex(CFIIndex);
345 InsertedCFIInstr = true;
346 }
347
348 if (ForceFullCFA) {
349 MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA(
350 MBB&: *MBBInfo.MBB, MBBI);
351 InsertedCFIInstr = true;
352 PrevMBBInfo = &MBBInfo;
353 continue;
354 }
355
356 BitVector::apply(f: [](auto x, auto y) { return x & ~y; }, Out&: SetDifference,
357 Arg: PrevMBBInfo->OutgoingCSRSaved, Args: MBBInfo.IncomingCSRSaved);
358 for (int Reg : SetDifference.set_bits()) {
359 unsigned CFIIndex =
360 MF.addFrameInst(Inst: MCCFIInstruction::createRestore(L: nullptr, Register: Reg));
361 BuildMI(BB&: *MBBInfo.MBB, I: MBBI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION))
362 .addCFIIndex(CFIIndex);
363 InsertedCFIInstr = true;
364 }
365
366 BitVector::apply(f: [](auto x, auto y) { return x & ~y; }, Out&: SetDifference,
367 Arg: MBBInfo.IncomingCSRSaved, Args: PrevMBBInfo->OutgoingCSRSaved);
368 for (int Reg : SetDifference.set_bits()) {
369 auto it = CSRLocMap.find(Val: Reg);
370 assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");
371 unsigned CFIIndex;
372 CSRSavedLocation RO = it->second;
373 if (!RO.Reg && RO.Offset) {
374 CFIIndex = MF.addFrameInst(
375 Inst: MCCFIInstruction::createOffset(L: nullptr, Register: Reg, Offset: *RO.Offset));
376 } else if (RO.Reg && !RO.Offset) {
377 CFIIndex = MF.addFrameInst(
378 Inst: MCCFIInstruction::createRegister(L: nullptr, Register1: Reg, Register2: *RO.Reg));
379 } else {
380 llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid");
381 }
382 BuildMI(BB&: *MBBInfo.MBB, I: MBBI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION))
383 .addCFIIndex(CFIIndex);
384 InsertedCFIInstr = true;
385 }
386
387 PrevMBBInfo = &MBBInfo;
388 }
389 return InsertedCFIInstr;
390}
391
392void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred,
393 const MBBCFAInfo &Succ) {
394 errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
395 "***\n";
396 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
397 << " in " << Pred.MBB->getParent()->getName()
398 << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
399 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
400 << " in " << Pred.MBB->getParent()->getName()
401 << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
402 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
403 << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
404 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
405 << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
406}
407
408void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred,
409 const MBBCFAInfo &Succ) {
410 errs() << "*** Inconsistent CSR Saved between pred and succ in function "
411 << Pred.MBB->getParent()->getName() << " ***\n";
412 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
413 << " outgoing CSR Saved: ";
414 for (int Reg : Pred.OutgoingCSRSaved.set_bits())
415 errs() << Reg << " ";
416 errs() << "\n";
417 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
418 << " incoming CSR Saved: ";
419 for (int Reg : Succ.IncomingCSRSaved.set_bits())
420 errs() << Reg << " ";
421 errs() << "\n";
422}
423
424unsigned CFIInstrInserter::verify(MachineFunction &MF) {
425 unsigned ErrorNum = 0;
426 for (auto *CurrMBB : depth_first(G: &MF)) {
427 const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
428 for (MachineBasicBlock *Succ : CurrMBB->successors()) {
429 const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
430 // Check that incoming offset and register values of successors match the
431 // outgoing offset and register values of CurrMBB
432 if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
433 SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
434 // Inconsistent offsets/registers are ok for 'noreturn' blocks because
435 // we don't generate epilogues inside such blocks.
436 if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
437 continue;
438 reportCFAError(Pred: CurrMBBInfo, Succ: SuccMBBInfo);
439 ErrorNum++;
440 }
441 // Check that IncomingCSRSaved of every successor matches the
442 // OutgoingCSRSaved of CurrMBB
443 if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) {
444 reportCSRError(Pred: CurrMBBInfo, Succ: SuccMBBInfo);
445 ErrorNum++;
446 }
447 }
448 }
449 return ErrorNum;
450}
451