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