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