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/MachineModuleInfo.h"
24#include "llvm/CodeGen/Passes.h"
25#include "llvm/CodeGen/TargetFrameLowering.h"
26#include "llvm/CodeGen/TargetInstrInfo.h"
27#include "llvm/CodeGen/TargetSubtargetInfo.h"
28#include "llvm/InitializePasses.h"
29#include "llvm/Target/TargetMachine.h"
30using namespace llvm;
31
32static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
33    cl::desc("Verify Call Frame Information instructions"),
34    cl::init(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(MF.getNumBlockIDs());
56    calculateCFAInfo(MF);
57
58    if (VerifyCFI) {
59      if (unsigned ErrorNum = verify(MF))
60        report_fatal_error("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    int IncomingCFAOffset = -1;
73    /// Value of cfa offset valid at basic block exit.
74    int 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    /// If in/out cfa offset and register values for this block have already
80    /// been set or not.
81    bool Processed = false;
82  };
83
84  /// Contains cfa offset and register values valid at entry and exit of basic
85  /// blocks.
86  std::vector<MBBCFAInfo> MBBVector;
87
88  /// Calculate cfa offset and register values valid at entry and exit for all
89  /// basic blocks in a function.
90  void calculateCFAInfo(MachineFunction &MF);
91  /// Calculate cfa offset and register values valid at basic block exit by
92  /// checking the block for CFI instructions. Block's incoming CFA info remains
93  /// the same.
94  void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo);
95  /// Update in/out cfa offset and register values for successors of the basic
96  /// block.
97  void updateSuccCFAInfo(MBBCFAInfo &MBBInfo);
98
99  /// Check if incoming CFA information of a basic block matches outgoing CFA
100  /// information of the previous block. If it doesn't, insert CFI instruction
101  /// at the beginning of the block that corrects the CFA calculation rule for
102  /// that block.
103  bool insertCFIInstrs(MachineFunction &MF);
104  /// Return the cfa offset value that should be set at the beginning of a MBB
105  /// if needed. The negated value is needed when creating CFI instructions that
106  /// set absolute offset.
107  int getCorrectCFAOffset(MachineBasicBlock *MBB) {
108    return -MBBVector[MBB->getNumber()].IncomingCFAOffset;
109  }
110
111  void report(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
112  /// Go through each MBB in a function and check that outgoing offset and
113  /// register of its predecessors match incoming offset and register of that
114  /// MBB, as well as that incoming offset and register of its successors match
115  /// outgoing offset and register of the MBB.
116  unsigned verify(MachineFunction &MF);
117};
118}  // namespace
119
120char CFIInstrInserter::ID = 0;
121INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
122                "Check CFA info and insert CFI instructions if needed", false,
123                false)
124FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
125
126void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
127  // Initial CFA offset value i.e. the one valid at the beginning of the
128  // function.
129  int InitialOffset =
130      MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);
131  // Initial CFA register value i.e. the one valid at the beginning of the
132  // function.
133  unsigned InitialRegister =
134      MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);
135
136  // Initialize MBBMap.
137  for (MachineBasicBlock &MBB : MF) {
138    MBBCFAInfo MBBInfo;
139    MBBInfo.MBB = &MBB;
140    MBBInfo.IncomingCFAOffset = InitialOffset;
141    MBBInfo.OutgoingCFAOffset = InitialOffset;
142    MBBInfo.IncomingCFARegister = InitialRegister;
143    MBBInfo.OutgoingCFARegister = InitialRegister;
144    MBBVector[MBB.getNumber()] = MBBInfo;
145  }
146
147  // Set in/out cfa info for all blocks in the function. This traversal is based
148  // on the assumption that the first block in the function is the entry block
149  // i.e. that it has initial cfa offset and register values as incoming CFA
150  // information.
151  for (MachineBasicBlock &MBB : MF) {
152    if (MBBVector[MBB.getNumber()].Processed) continue;
153    updateSuccCFAInfo(MBBVector[MBB.getNumber()]);
154  }
155}
156
157void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
158  // Outgoing cfa offset set by the block.
159  int SetOffset = MBBInfo.IncomingCFAOffset;
160  // Outgoing cfa register set by the block.
161  unsigned SetRegister = MBBInfo.IncomingCFARegister;
162  const std::vector<MCCFIInstruction> &Instrs =
163      MBBInfo.MBB->getParent()->getFrameInstructions();
164
165  // Determine cfa offset and register set by the block.
166  for (MachineInstr &MI : *MBBInfo.MBB) {
167    if (MI.isCFIInstruction()) {
168      unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
169      const MCCFIInstruction &CFI = Instrs[CFIIndex];
170      switch (CFI.getOperation()) {
171      case MCCFIInstruction::OpDefCfaRegister:
172        SetRegister = CFI.getRegister();
173        break;
174      case MCCFIInstruction::OpDefCfaOffset:
175        SetOffset = CFI.getOffset();
176        break;
177      case MCCFIInstruction::OpAdjustCfaOffset:
178        SetOffset += CFI.getOffset();
179        break;
180      case MCCFIInstruction::OpDefCfa:
181        SetRegister = CFI.getRegister();
182        SetOffset = CFI.getOffset();
183        break;
184      case MCCFIInstruction::OpRememberState:
185        // TODO: Add support for handling cfi_remember_state.
186#ifndef NDEBUG
187        report_fatal_error(
188            "Support for cfi_remember_state not implemented! Value of CFA "
189            "may be incorrect!\n");
190#endif
191        break;
192      case MCCFIInstruction::OpRestoreState:
193        // TODO: Add support for handling cfi_restore_state.
194#ifndef NDEBUG
195        report_fatal_error(
196            "Support for cfi_restore_state not implemented! Value of CFA may "
197            "be incorrect!\n");
198#endif
199        break;
200      // Other CFI directives do not affect CFA value.
201      case MCCFIInstruction::OpSameValue:
202      case MCCFIInstruction::OpOffset:
203      case MCCFIInstruction::OpRelOffset:
204      case MCCFIInstruction::OpEscape:
205      case MCCFIInstruction::OpRestore:
206      case MCCFIInstruction::OpUndefined:
207      case MCCFIInstruction::OpRegister:
208      case MCCFIInstruction::OpWindowSave:
209      case MCCFIInstruction::OpNegateRAState:
210      case MCCFIInstruction::OpGnuArgsSize:
211        break;
212      }
213    }
214  }
215
216  MBBInfo.Processed = true;
217
218  // Update outgoing CFA info.
219  MBBInfo.OutgoingCFAOffset = SetOffset;
220  MBBInfo.OutgoingCFARegister = SetRegister;
221}
222
223void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
224  SmallVector<MachineBasicBlock *, 4> Stack;
225  Stack.push_back(MBBInfo.MBB);
226
227  do {
228    MachineBasicBlock *Current = Stack.pop_back_val();
229    MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
230    if (CurrentInfo.Processed)
231      continue;
232
233    calculateOutgoingCFAInfo(CurrentInfo);
234    for (auto *Succ : CurrentInfo.MBB->successors()) {
235      MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
236      if (!SuccInfo.Processed) {
237        SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
238        SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
239        Stack.push_back(Succ);
240      }
241    }
242  } while (!Stack.empty());
243}
244
245bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
246  const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
247  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
248  bool InsertedCFIInstr = false;
249
250  for (MachineBasicBlock &MBB : MF) {
251    // Skip the first MBB in a function
252    if (MBB.getNumber() == MF.front().getNumber()) continue;
253
254    const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
255    auto MBBI = MBBInfo.MBB->begin();
256    DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
257
258    if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
259      // If both outgoing offset and register of a previous block don't match
260      // incoming offset and register of this block, add a def_cfa instruction
261      // with the correct offset and register for this block.
262      if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) {
263        unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createDefCfa(
264            nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
265        BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
266            .addCFIIndex(CFIIndex);
267        // If outgoing offset of a previous block doesn't match incoming offset
268        // of this block, add a def_cfa_offset instruction with the correct
269        // offset for this block.
270      } else {
271        unsigned CFIIndex =
272            MF.addFrameInst(MCCFIInstruction::createDefCfaOffset(
273                nullptr, getCorrectCFAOffset(&MBB)));
274        BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
275            .addCFIIndex(CFIIndex);
276      }
277      InsertedCFIInstr = true;
278      // If outgoing register of a previous block doesn't match incoming
279      // register of this block, add a def_cfa_register instruction with the
280      // correct register for this block.
281    } else if (PrevMBBInfo->OutgoingCFARegister !=
282               MBBInfo.IncomingCFARegister) {
283      unsigned CFIIndex =
284          MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
285              nullptr, MBBInfo.IncomingCFARegister));
286      BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
287          .addCFIIndex(CFIIndex);
288      InsertedCFIInstr = true;
289    }
290    PrevMBBInfo = &MBBInfo;
291  }
292  return InsertedCFIInstr;
293}
294
295void CFIInstrInserter::report(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ) {
296  errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
297            "***\n";
298  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
299         << " in " << Pred.MBB->getParent()->getName()
300         << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
301  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
302         << " in " << Pred.MBB->getParent()->getName()
303         << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
304  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
305         << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
306  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
307         << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
308}
309
310unsigned CFIInstrInserter::verify(MachineFunction &MF) {
311  unsigned ErrorNum = 0;
312  for (auto *CurrMBB : depth_first(&MF)) {
313    const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
314    for (MachineBasicBlock *Succ : CurrMBB->successors()) {
315      const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
316      // Check that incoming offset and register values of successors match the
317      // outgoing offset and register values of CurrMBB
318      if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
319          SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
320        // Inconsistent offsets/registers are ok for 'noreturn' blocks because
321        // we don't generate epilogues inside such blocks.
322        if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
323          continue;
324        report(CurrMBBInfo, SuccMBBInfo);
325        ErrorNum++;
326      }
327    }
328  }
329  return ErrorNum;
330}
331