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"
30 using namespace llvm;
31 
32 static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
33     cl::desc("Verify Call Frame Information instructions"),
34     cl::init(false),
35     cl::Hidden);
36 
37 namespace {
38 class 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 
120 char CFIInstrInserter::ID = 0;
121 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
122                 "Check CFA info and insert CFI instructions if needed", false,
123                 false)
124 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
125 
126 void 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 
157 void 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 
223 void 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 
245 bool 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 
295 void 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 
310 unsigned 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