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