xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/CFIInstrInserter.cpp (revision 3e8eb5c7f4909209c042403ddee340b2ee7003a5)
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"
32 using namespace llvm;
33 
34 static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
35     cl::desc("Verify Call Frame Information instructions"),
36     cl::init(false),
37     cl::Hidden);
38 
39 namespace {
40 class 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 
140 char CFIInstrInserter::ID = 0;
141 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
142                 "Check CFA info and insert CFI instructions if needed", false,
143                 false)
144 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
145 
146 void 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 = MBBVector[MBB.getNumber()];
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   }
169   CSRLocMap.clear();
170 
171   // Set in/out cfa info for all blocks in the function. This traversal is based
172   // on the assumption that the first block in the function is the entry block
173   // i.e. that it has initial cfa offset and register values as incoming CFA
174   // information.
175   updateSuccCFAInfo(MBBVector[MF.front().getNumber()]);
176 }
177 
178 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
179   // Outgoing cfa offset set by the block.
180   int SetOffset = MBBInfo.IncomingCFAOffset;
181   // Outgoing cfa register set by the block.
182   unsigned SetRegister = MBBInfo.IncomingCFARegister;
183   MachineFunction *MF = MBBInfo.MBB->getParent();
184   const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions();
185   const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
186   unsigned NumRegs = TRI.getNumRegs();
187   BitVector CSRSaved(NumRegs), CSRRestored(NumRegs);
188 
189   // Determine cfa offset and register set by the block.
190   for (MachineInstr &MI : *MBBInfo.MBB) {
191     if (MI.isCFIInstruction()) {
192       Optional<unsigned> CSRReg;
193       Optional<int> CSROffset;
194       unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
195       const MCCFIInstruction &CFI = Instrs[CFIIndex];
196       switch (CFI.getOperation()) {
197       case MCCFIInstruction::OpDefCfaRegister:
198         SetRegister = CFI.getRegister();
199         break;
200       case MCCFIInstruction::OpDefCfaOffset:
201         SetOffset = CFI.getOffset();
202         break;
203       case MCCFIInstruction::OpAdjustCfaOffset:
204         SetOffset += CFI.getOffset();
205         break;
206       case MCCFIInstruction::OpDefCfa:
207         SetRegister = CFI.getRegister();
208         SetOffset = CFI.getOffset();
209         break;
210       case MCCFIInstruction::OpOffset:
211         CSROffset = CFI.getOffset();
212         break;
213       case MCCFIInstruction::OpRegister:
214         CSRReg = CFI.getRegister2();
215         break;
216       case MCCFIInstruction::OpRelOffset:
217         CSROffset = CFI.getOffset() - SetOffset;
218         break;
219       case MCCFIInstruction::OpRestore:
220         CSRRestored.set(CFI.getRegister());
221         break;
222       case MCCFIInstruction::OpLLVMDefAspaceCfa:
223         // TODO: Add support for handling cfi_def_aspace_cfa.
224 #ifndef NDEBUG
225         report_fatal_error(
226             "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA "
227             "may be incorrect!\n");
228 #endif
229         break;
230       case MCCFIInstruction::OpRememberState:
231         // TODO: Add support for handling cfi_remember_state.
232 #ifndef NDEBUG
233         report_fatal_error(
234             "Support for cfi_remember_state not implemented! Value of CFA "
235             "may be incorrect!\n");
236 #endif
237         break;
238       case MCCFIInstruction::OpRestoreState:
239         // TODO: Add support for handling cfi_restore_state.
240 #ifndef NDEBUG
241         report_fatal_error(
242             "Support for cfi_restore_state not implemented! Value of CFA may "
243             "be incorrect!\n");
244 #endif
245         break;
246       // Other CFI directives do not affect CFA value.
247       case MCCFIInstruction::OpUndefined:
248       case MCCFIInstruction::OpSameValue:
249       case MCCFIInstruction::OpEscape:
250       case MCCFIInstruction::OpWindowSave:
251       case MCCFIInstruction::OpNegateRAState:
252       case MCCFIInstruction::OpGnuArgsSize:
253         break;
254       }
255       if (CSRReg || CSROffset) {
256         auto It = CSRLocMap.find(CFI.getRegister());
257         if (It == CSRLocMap.end()) {
258           CSRLocMap.insert(
259               {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)});
260         } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) {
261           llvm_unreachable("Different saved locations for the same CSR");
262         }
263         CSRSaved.set(CFI.getRegister());
264       }
265     }
266   }
267 
268   MBBInfo.Processed = true;
269 
270   // Update outgoing CFA info.
271   MBBInfo.OutgoingCFAOffset = SetOffset;
272   MBBInfo.OutgoingCFARegister = SetRegister;
273 
274   // Update outgoing CSR info.
275   BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; },
276                    MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved,
277                    CSRRestored);
278 }
279 
280 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
281   SmallVector<MachineBasicBlock *, 4> Stack;
282   Stack.push_back(MBBInfo.MBB);
283 
284   do {
285     MachineBasicBlock *Current = Stack.pop_back_val();
286     MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
287     calculateOutgoingCFAInfo(CurrentInfo);
288     for (auto *Succ : CurrentInfo.MBB->successors()) {
289       MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
290       if (!SuccInfo.Processed) {
291         SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
292         SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
293         SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved;
294         Stack.push_back(Succ);
295       }
296     }
297   } while (!Stack.empty());
298 }
299 
300 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
301   const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
302   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
303   bool InsertedCFIInstr = false;
304 
305   BitVector SetDifference;
306   for (MachineBasicBlock &MBB : MF) {
307     // Skip the first MBB in a function
308     if (MBB.getNumber() == MF.front().getNumber()) continue;
309 
310     const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
311     auto MBBI = MBBInfo.MBB->begin();
312     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
313 
314     // If the current MBB will be placed in a unique section, a full DefCfa
315     // must be emitted.
316     const bool ForceFullCFA = MBB.isBeginSection();
317 
318     if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset &&
319          PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) ||
320         ForceFullCFA) {
321       // If both outgoing offset and register of a previous block don't match
322       // incoming offset and register of this block, or if this block begins a
323       // section, add a def_cfa instruction with the correct offset and
324       // register for this block.
325       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa(
326           nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
327       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
328           .addCFIIndex(CFIIndex);
329       InsertedCFIInstr = true;
330     } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
331       // If outgoing offset of a previous block doesn't match incoming offset
332       // of this block, add a def_cfa_offset instruction with the correct
333       // offset for this block.
334       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset(
335           nullptr, getCorrectCFAOffset(&MBB)));
336       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
337           .addCFIIndex(CFIIndex);
338       InsertedCFIInstr = true;
339     } else if (PrevMBBInfo->OutgoingCFARegister !=
340                MBBInfo.IncomingCFARegister) {
341       unsigned CFIIndex =
342           MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
343               nullptr, MBBInfo.IncomingCFARegister));
344       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
345           .addCFIIndex(CFIIndex);
346       InsertedCFIInstr = true;
347     }
348 
349     if (ForceFullCFA) {
350       MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA(
351           *MBBInfo.MBB, MBBI);
352       InsertedCFIInstr = true;
353       PrevMBBInfo = &MBBInfo;
354       continue;
355     }
356 
357     BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
358                      PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved);
359     for (int Reg : SetDifference.set_bits()) {
360       unsigned CFIIndex =
361           MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg));
362       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
363           .addCFIIndex(CFIIndex);
364       InsertedCFIInstr = true;
365     }
366 
367     BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
368                      MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved);
369     for (int Reg : SetDifference.set_bits()) {
370       auto it = CSRLocMap.find(Reg);
371       assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");
372       unsigned CFIIndex;
373       CSRSavedLocation RO = it->second;
374       if (!RO.Reg && RO.Offset) {
375         CFIIndex = MF.addFrameInst(
376             MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset));
377       } else if (RO.Reg && !RO.Offset) {
378         CFIIndex = MF.addFrameInst(
379             MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg));
380       } else {
381         llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid");
382       }
383       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
384           .addCFIIndex(CFIIndex);
385       InsertedCFIInstr = true;
386     }
387 
388     PrevMBBInfo = &MBBInfo;
389   }
390   return InsertedCFIInstr;
391 }
392 
393 void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred,
394                                       const MBBCFAInfo &Succ) {
395   errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
396             "***\n";
397   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
398          << " in " << Pred.MBB->getParent()->getName()
399          << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
400   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
401          << " in " << Pred.MBB->getParent()->getName()
402          << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
403   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
404          << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
405   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
406          << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
407 }
408 
409 void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred,
410                                       const MBBCFAInfo &Succ) {
411   errs() << "*** Inconsistent CSR Saved between pred and succ in function "
412          << Pred.MBB->getParent()->getName() << " ***\n";
413   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
414          << " outgoing CSR Saved: ";
415   for (int Reg : Pred.OutgoingCSRSaved.set_bits())
416     errs() << Reg << " ";
417   errs() << "\n";
418   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
419          << " incoming CSR Saved: ";
420   for (int Reg : Succ.IncomingCSRSaved.set_bits())
421     errs() << Reg << " ";
422   errs() << "\n";
423 }
424 
425 unsigned CFIInstrInserter::verify(MachineFunction &MF) {
426   unsigned ErrorNum = 0;
427   for (auto *CurrMBB : depth_first(&MF)) {
428     const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
429     for (MachineBasicBlock *Succ : CurrMBB->successors()) {
430       const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
431       // Check that incoming offset and register values of successors match the
432       // outgoing offset and register values of CurrMBB
433       if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
434           SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
435         // Inconsistent offsets/registers are ok for 'noreturn' blocks because
436         // we don't generate epilogues inside such blocks.
437         if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
438           continue;
439         reportCFAError(CurrMBBInfo, SuccMBBInfo);
440         ErrorNum++;
441       }
442       // Check that IncomingCSRSaved of every successor matches the
443       // OutgoingCSRSaved of CurrMBB
444       if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) {
445         reportCSRError(CurrMBBInfo, SuccMBBInfo);
446         ErrorNum++;
447       }
448     }
449   }
450   return ErrorNum;
451 }
452