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(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(MF.getNumBlockIDs());
55    calculateCFAInfo(MF);
56
57    if (VerifyCFI) {
58      if (unsigned ErrorNum = verify(MF))
59        report_fatal_error("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    int IncomingCFAOffset = -1;
72    /// Value of cfa offset valid at basic block exit.
73    int 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  int 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(InitialRegister, 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(NumRegs);
165    MBBInfo.OutgoingCSRSaved.resize(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(MBBVector[MF.front().getNumber()]);
174}
175
176void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
177  // Outgoing cfa offset set by the block.
178  int 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<int> CSROffset;
192      unsigned CFIIndex = MI.getOperand(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        break;
252      }
253      if (CSRReg || CSROffset) {
254        auto It = CSRLocMap.find(CFI.getRegister());
255        if (It == CSRLocMap.end()) {
256          CSRLocMap.insert(
257              {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)});
258        } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) {
259          llvm_unreachable("Different saved locations for the same CSR");
260        }
261        CSRSaved.set(CFI.getRegister());
262      }
263    }
264  }
265
266  MBBInfo.Processed = true;
267
268  // Update outgoing CFA info.
269  MBBInfo.OutgoingCFAOffset = SetOffset;
270  MBBInfo.OutgoingCFARegister = SetRegister;
271
272  // Update outgoing CSR info.
273  BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; },
274                   MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved,
275                   CSRRestored);
276}
277
278void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
279  SmallVector<MachineBasicBlock *, 4> Stack;
280  Stack.push_back(MBBInfo.MBB);
281
282  do {
283    MachineBasicBlock *Current = Stack.pop_back_val();
284    MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
285    calculateOutgoingCFAInfo(CurrentInfo);
286    for (auto *Succ : CurrentInfo.MBB->successors()) {
287      MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
288      if (!SuccInfo.Processed) {
289        SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
290        SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
291        SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved;
292        Stack.push_back(Succ);
293      }
294    }
295  } while (!Stack.empty());
296}
297
298bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
299  const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
300  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
301  bool InsertedCFIInstr = false;
302
303  BitVector SetDifference;
304  for (MachineBasicBlock &MBB : MF) {
305    // Skip the first MBB in a function
306    if (MBB.getNumber() == MF.front().getNumber()) continue;
307
308    const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
309    auto MBBI = MBBInfo.MBB->begin();
310    DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
311
312    // If the current MBB will be placed in a unique section, a full DefCfa
313    // must be emitted.
314    const bool ForceFullCFA = MBB.isBeginSection();
315
316    if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset &&
317         PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) ||
318        ForceFullCFA) {
319      // If both outgoing offset and register of a previous block don't match
320      // incoming offset and register of this block, or if this block begins a
321      // section, add a def_cfa instruction with the correct offset and
322      // register for this block.
323      unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa(
324          nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
325      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
326          .addCFIIndex(CFIIndex);
327      InsertedCFIInstr = true;
328    } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
329      // If outgoing offset of a previous block doesn't match incoming offset
330      // of this block, add a def_cfa_offset instruction with the correct
331      // offset for this block.
332      unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset(
333          nullptr, getCorrectCFAOffset(&MBB)));
334      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
335          .addCFIIndex(CFIIndex);
336      InsertedCFIInstr = true;
337    } else if (PrevMBBInfo->OutgoingCFARegister !=
338               MBBInfo.IncomingCFARegister) {
339      unsigned CFIIndex =
340          MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
341              nullptr, MBBInfo.IncomingCFARegister));
342      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
343          .addCFIIndex(CFIIndex);
344      InsertedCFIInstr = true;
345    }
346
347    if (ForceFullCFA) {
348      MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA(
349          *MBBInfo.MBB, MBBI);
350      InsertedCFIInstr = true;
351      PrevMBBInfo = &MBBInfo;
352      continue;
353    }
354
355    BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
356                     PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved);
357    for (int Reg : SetDifference.set_bits()) {
358      unsigned CFIIndex =
359          MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg));
360      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
361          .addCFIIndex(CFIIndex);
362      InsertedCFIInstr = true;
363    }
364
365    BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
366                     MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved);
367    for (int Reg : SetDifference.set_bits()) {
368      auto it = CSRLocMap.find(Reg);
369      assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");
370      unsigned CFIIndex;
371      CSRSavedLocation RO = it->second;
372      if (!RO.Reg && RO.Offset) {
373        CFIIndex = MF.addFrameInst(
374            MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset));
375      } else if (RO.Reg && !RO.Offset) {
376        CFIIndex = MF.addFrameInst(
377            MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg));
378      } else {
379        llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid");
380      }
381      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
382          .addCFIIndex(CFIIndex);
383      InsertedCFIInstr = true;
384    }
385
386    PrevMBBInfo = &MBBInfo;
387  }
388  return InsertedCFIInstr;
389}
390
391void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred,
392                                      const MBBCFAInfo &Succ) {
393  errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
394            "***\n";
395  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
396         << " in " << Pred.MBB->getParent()->getName()
397         << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
398  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
399         << " in " << Pred.MBB->getParent()->getName()
400         << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
401  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
402         << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
403  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
404         << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
405}
406
407void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred,
408                                      const MBBCFAInfo &Succ) {
409  errs() << "*** Inconsistent CSR Saved between pred and succ in function "
410         << Pred.MBB->getParent()->getName() << " ***\n";
411  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
412         << " outgoing CSR Saved: ";
413  for (int Reg : Pred.OutgoingCSRSaved.set_bits())
414    errs() << Reg << " ";
415  errs() << "\n";
416  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
417         << " incoming CSR Saved: ";
418  for (int Reg : Succ.IncomingCSRSaved.set_bits())
419    errs() << Reg << " ";
420  errs() << "\n";
421}
422
423unsigned CFIInstrInserter::verify(MachineFunction &MF) {
424  unsigned ErrorNum = 0;
425  for (auto *CurrMBB : depth_first(&MF)) {
426    const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
427    for (MachineBasicBlock *Succ : CurrMBB->successors()) {
428      const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
429      // Check that incoming offset and register values of successors match the
430      // outgoing offset and register values of CurrMBB
431      if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
432          SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
433        // Inconsistent offsets/registers are ok for 'noreturn' blocks because
434        // we don't generate epilogues inside such blocks.
435        if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
436          continue;
437        reportCFAError(CurrMBBInfo, SuccMBBInfo);
438        ErrorNum++;
439      }
440      // Check that IncomingCSRSaved of every successor matches the
441      // OutgoingCSRSaved of CurrMBB
442      if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) {
443        reportCSRError(CurrMBBInfo, SuccMBBInfo);
444        ErrorNum++;
445      }
446    }
447  }
448  return ErrorNum;
449}
450