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