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