1 //===------ CFIInstrInserter.cpp - Insert additional CFI instructions -----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file This pass verifies incoming and outgoing CFA information of basic
11 /// blocks. CFA information is information about offset and register set by CFI
12 /// directives, valid at the start and end of a basic block. This pass checks
13 /// that outgoing information of predecessors matches incoming information of
14 /// their successors. Then it checks if blocks have correct CFA calculation rule
15 /// set and inserts additional CFI instruction at their beginnings if they
16 /// don't. CFI instructions are inserted if basic blocks have incorrect offset
17 /// or register set by previous blocks, as a result of a non-linear layout of
18 /// blocks in a function.
19 //===----------------------------------------------------------------------===//
20 
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/Target/TargetFrameLowering.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/Target/TargetSubtargetInfo.h"
29 using namespace llvm;
30 
31 namespace {
32 class CFIInstrInserter : public MachineFunctionPass {
33  public:
34   static char ID;
35 
36   CFIInstrInserter() : MachineFunctionPass(ID) {
37     initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry());
38   }
39 
40   void getAnalysisUsage(AnalysisUsage &AU) const override {
41     AU.setPreservesAll();
42     MachineFunctionPass::getAnalysisUsage(AU);
43   }
44 
45   bool runOnMachineFunction(MachineFunction &MF) override {
46 
47     if (!MF.getMMI().hasDebugInfo() &&
48         !MF.getFunction()->needsUnwindTableEntry())
49       return false;
50 
51     MBBVector.resize(MF.getNumBlockIDs());
52     calculateCFAInfo(MF);
53 #ifndef NDEBUG
54     unsigned ErrorNum = verify(MF);
55     if (ErrorNum)
56       report_fatal_error("Found " + Twine(ErrorNum) +
57                          " in/out CFI information errors.");
58 #endif
59     bool insertedCFI = insertCFIInstrs(MF);
60     MBBVector.clear();
61     return insertedCFI;
62   }
63 
64  private:
65   struct MBBCFAInfo {
66     MachineBasicBlock *MBB;
67     /// Value of cfa offset valid at basic block entry.
68     int IncomingCFAOffset = -1;
69     /// Value of cfa offset valid at basic block exit.
70     int OutgoingCFAOffset = -1;
71     /// Value of cfa register valid at basic block entry.
72     unsigned IncomingCFARegister = 0;
73     /// Value of cfa register valid at basic block exit.
74     unsigned OutgoingCFARegister = 0;
75     /// If in/out cfa offset and register values for this block have already
76     /// been set or not.
77     bool Processed = false;
78   };
79 
80   /// Contains cfa offset and register values valid at entry and exit of basic
81   /// blocks.
82   SmallVector<struct MBBCFAInfo, 4> MBBVector;
83 
84   /// Calculate cfa offset and register values valid at entry and exit for all
85   /// basic blocks in a function.
86   void calculateCFAInfo(MachineFunction &MF);
87   /// Calculate cfa offset and register values valid at basic block exit by
88   /// checking the block for CFI instructions. Block's incoming CFA info remains
89   /// the same.
90   void calculateOutgoingCFAInfo(struct MBBCFAInfo &MBBInfo);
91   /// Update in/out cfa offset and register values for successors of the basic
92   /// block.
93   void updateSuccCFAInfo(struct MBBCFAInfo &MBBInfo);
94 
95   /// Check if incoming CFA information of a basic block matches outgoing CFA
96   /// information of the previous block. If it doesn't, insert CFI instruction
97   /// at the beginning of the block that corrects the CFA calculation rule for
98   /// that block.
99   bool insertCFIInstrs(MachineFunction &MF);
100   /// Return the cfa offset value that should be set at the beginning of a MBB
101   /// if needed. The negated value is needed when creating CFI instructions that
102   /// set absolute offset.
103   int getCorrectCFAOffset(MachineBasicBlock *MBB) {
104     return -MBBVector[MBB->getNumber()].IncomingCFAOffset;
105   }
106 
107   void report(const char *msg, MachineBasicBlock &MBB);
108   /// Go through each MBB in a function and check that outgoing offset and
109   /// register of its predecessors match incoming offset and register of that
110   /// MBB, as well as that incoming offset and register of its successors match
111   /// outgoing offset and register of the MBB.
112   unsigned verify(MachineFunction &MF);
113 };
114 }
115 
116 char CFIInstrInserter::ID = 0;
117 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
118                 "Check CFA info and insert CFI instructions if needed", false,
119                 false)
120 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
121 
122 void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
123   // Initial CFA offset value i.e. the one valid at the beginning of the
124   // function.
125   int InitialOffset =
126       MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);
127   // Initial CFA register value i.e. the one valid at the beginning of the
128   // function.
129   unsigned InitialRegister =
130       MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);
131 
132   // Initialize MBBMap.
133   for (MachineBasicBlock &MBB : MF) {
134     struct MBBCFAInfo MBBInfo;
135     MBBInfo.MBB = &MBB;
136     MBBInfo.IncomingCFAOffset = InitialOffset;
137     MBBInfo.OutgoingCFAOffset = InitialOffset;
138     MBBInfo.IncomingCFARegister = InitialRegister;
139     MBBInfo.OutgoingCFARegister = InitialRegister;
140     MBBVector[MBB.getNumber()] = MBBInfo;
141   }
142 
143   // Set in/out cfa info for all blocks in the function. This traversal is based
144   // on the assumption that the first block in the function is the entry block
145   // i.e. that it has initial cfa offset and register values as incoming CFA
146   // information.
147   for (MachineBasicBlock &MBB : MF) {
148     if (MBBVector[MBB.getNumber()].Processed) continue;
149     calculateOutgoingCFAInfo(MBBVector[MBB.getNumber()]);
150     updateSuccCFAInfo(MBBVector[MBB.getNumber()]);
151   }
152 }
153 
154 void CFIInstrInserter::calculateOutgoingCFAInfo(struct MBBCFAInfo &MBBInfo) {
155   // Outgoing cfa offset set by the block.
156   int SetOffset = MBBInfo.IncomingCFAOffset;
157   // Outgoing cfa register set by the block.
158   unsigned SetRegister = MBBInfo.IncomingCFARegister;
159   const std::vector<MCCFIInstruction> &Instrs =
160       MBBInfo.MBB->getParent()->getFrameInstructions();
161 
162   // Determine cfa offset and register set by the block.
163   for (MachineInstr &MI :
164        make_range(MBBInfo.MBB->instr_begin(), MBBInfo.MBB->instr_end())) {
165     if (MI.isCFIInstruction()) {
166       unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
167       const MCCFIInstruction &CFI = Instrs[CFIIndex];
168       if (CFI.getOperation() == MCCFIInstruction::OpDefCfaRegister) {
169         SetRegister = CFI.getRegister();
170       } else if (CFI.getOperation() == MCCFIInstruction::OpDefCfaOffset) {
171         SetOffset = CFI.getOffset();
172       } else if (CFI.getOperation() == MCCFIInstruction::OpAdjustCfaOffset) {
173         SetOffset += CFI.getOffset();
174       } else if (CFI.getOperation() == MCCFIInstruction::OpDefCfa) {
175         SetRegister = CFI.getRegister();
176         SetOffset = CFI.getOffset();
177       }
178     }
179   }
180 
181   MBBInfo.Processed = true;
182 
183   // Update outgoing CFA info.
184   MBBInfo.OutgoingCFAOffset = SetOffset;
185   MBBInfo.OutgoingCFARegister = SetRegister;
186 }
187 
188 void CFIInstrInserter::updateSuccCFAInfo(struct MBBCFAInfo &MBBInfo) {
189 
190   for (MachineBasicBlock *Succ : MBBInfo.MBB->successors()) {
191     struct MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
192     if (SuccInfo.Processed) continue;
193     SuccInfo.IncomingCFAOffset = MBBInfo.OutgoingCFAOffset;
194     SuccInfo.IncomingCFARegister = MBBInfo.OutgoingCFARegister;
195     calculateOutgoingCFAInfo(SuccInfo);
196     updateSuccCFAInfo(SuccInfo);
197   }
198 }
199 
200 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
201 
202   const struct MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
203   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
204   bool InsertedCFIInstr = false;
205 
206   for (MachineBasicBlock &MBB : MF) {
207     // Skip the first MBB in a function
208     if (MBB.getNumber() == MF.front().getNumber()) continue;
209 
210     const struct MBBCFAInfo& MBBInfo = MBBVector[MBB.getNumber()];
211     auto MBBI = MBBInfo.MBB->begin();
212     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
213 
214     if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
215       // If both outgoing offset and register of a previous block don't match
216       // incoming offset and register of this block, add a def_cfa instruction
217       // with the correct offset and register for this block.
218       if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) {
219         unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createDefCfa(
220             nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
221         BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
222             .addCFIIndex(CFIIndex);
223         // If outgoing offset of a previous block doesn't match incoming offset
224         // of this block, add a def_cfa_offset instruction with the correct
225         // offset for this block.
226       } else {
227         unsigned CFIIndex =
228             MF.addFrameInst(MCCFIInstruction::createDefCfaOffset(
229                 nullptr, getCorrectCFAOffset(&MBB)));
230         BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
231             .addCFIIndex(CFIIndex);
232       }
233       InsertedCFIInstr = true;
234       // If outgoing register of a previous block doesn't match incoming
235       // register of this block, add a def_cfa_register instruction with the
236       // correct register for this block.
237     } else if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) {
238       unsigned CFIIndex =
239           MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
240               nullptr, MBBInfo.IncomingCFARegister));
241       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
242           .addCFIIndex(CFIIndex);
243       InsertedCFIInstr = true;
244     }
245     PrevMBBInfo = &MBBInfo;
246   }
247   return InsertedCFIInstr;
248 }
249 
250 void CFIInstrInserter::report(const char *msg, MachineBasicBlock &MBB) {
251   errs() << '\n';
252   errs() << "*** " << msg << " ***\n"
253          << "- function:    " << MBB.getParent()->getName() << "\n";
254   errs() << "- basic block: BB#" << MBB.getNumber() << ' ' << MBB.getName()
255          << " (" << (const void *)&MBB << ')';
256   errs() << '\n';
257 }
258 
259 unsigned CFIInstrInserter::verify(MachineFunction &MF) {
260   unsigned ErrorNum = 0;
261   for (MachineBasicBlock &CurrMBB : MF) {
262     const struct MBBCFAInfo& CurrMBBInfo = MBBVector[CurrMBB.getNumber()];
263     for (MachineBasicBlock *Pred : CurrMBB.predecessors()) {
264       const struct MBBCFAInfo& PredMBBInfo = MBBVector[Pred->getNumber()];
265       // Check that outgoing offset values of predecessors match the incoming
266       // offset value of CurrMBB
267       if (PredMBBInfo.OutgoingCFAOffset != CurrMBBInfo.IncomingCFAOffset) {
268         report("The outgoing offset of a predecessor is inconsistent.",
269                CurrMBB);
270         errs() << "Predecessor BB#" << Pred->getNumber()
271                << " has outgoing offset (" << PredMBBInfo.OutgoingCFAOffset
272                << "), while BB#" << CurrMBB.getNumber()
273                << " has incoming offset (" << CurrMBBInfo.IncomingCFAOffset
274                << ").\n";
275         ErrorNum++;
276       }
277       // Check that outgoing register values of predecessors match the incoming
278       // register value of CurrMBB
279       if (PredMBBInfo.OutgoingCFARegister != CurrMBBInfo.IncomingCFARegister) {
280         report("The outgoing register of a predecessor is inconsistent.",
281                CurrMBB);
282         errs() << "Predecessor BB#" << Pred->getNumber()
283                << " has outgoing register (" << PredMBBInfo.OutgoingCFARegister
284                << "), while BB#" << CurrMBB.getNumber()
285                << " has incoming register (" << CurrMBBInfo.IncomingCFARegister
286                << ").\n";
287         ErrorNum++;
288       }
289     }
290 
291     for (MachineBasicBlock *Succ : CurrMBB.successors()) {
292       const struct MBBCFAInfo& SuccMBBInfo = MBBVector[Succ->getNumber()];
293       // Check that incoming offset values of successors match the outgoing
294       // offset value of CurrMBB
295       if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset) {
296         report("The incoming offset of a successor is inconsistent.", CurrMBB);
297         errs() << "Successor BB#" << Succ->getNumber()
298                << " has incoming offset (" << SuccMBBInfo.IncomingCFAOffset
299                << "), while BB#" << CurrMBB.getNumber()
300                << " has outgoing offset (" << CurrMBBInfo.OutgoingCFAOffset
301                << ").\n";
302         ErrorNum++;
303       }
304       // Check that incoming register values of successors match the outgoing
305       // register value of CurrMBB
306       if (SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
307         report("The incoming register of a successor is inconsistent.",
308                CurrMBB);
309         errs() << "Successor BB#" << Succ->getNumber()
310                << " has incoming register (" << SuccMBBInfo.IncomingCFARegister
311                << "), while BB#" << CurrMBB.getNumber()
312                << " has outgoing register (" << CurrMBBInfo.OutgoingCFARegister
313                << ").\n";
314         ErrorNum++;
315       }
316     }
317   }
318   return ErrorNum;
319 }
320