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/Passes.h" 24 #include "llvm/CodeGen/TargetFrameLowering.h" 25 #include "llvm/CodeGen/TargetInstrInfo.h" 26 #include "llvm/CodeGen/TargetSubtargetInfo.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/MC/MCDwarf.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 int64_t IncomingCFAOffset = -1; 72 /// Value of cfa offset valid at basic block exit. 73 int64_t 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 /// Set of callee saved registers saved at basic block entry. 79 BitVector IncomingCSRSaved; 80 /// Set of callee saved registers saved at basic block exit. 81 BitVector OutgoingCSRSaved; 82 /// If in/out cfa offset and register values for this block have already 83 /// been set or not. 84 bool Processed = false; 85 }; 86 87 #define INVALID_REG UINT_MAX 88 #define INVALID_OFFSET INT_MAX 89 /// contains the location where CSR register is saved. 90 struct CSRSavedLocation { 91 CSRSavedLocation(std::optional<unsigned> R, std::optional<int> O) 92 : Reg(R), Offset(O) {} 93 std::optional<unsigned> Reg; 94 std::optional<int> Offset; 95 }; 96 97 /// Contains cfa offset and register values valid at entry and exit of basic 98 /// blocks. 99 std::vector<MBBCFAInfo> MBBVector; 100 101 /// Map the callee save registers to the locations where they are saved. 102 SmallDenseMap<unsigned, CSRSavedLocation, 16> CSRLocMap; 103 104 /// Calculate cfa offset and register values valid at entry and exit for all 105 /// basic blocks in a function. 106 void calculateCFAInfo(MachineFunction &MF); 107 /// Calculate cfa offset and register values valid at basic block exit by 108 /// checking the block for CFI instructions. Block's incoming CFA info remains 109 /// the same. 110 void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo); 111 /// Update in/out cfa offset and register values for successors of the basic 112 /// block. 113 void updateSuccCFAInfo(MBBCFAInfo &MBBInfo); 114 115 /// Check if incoming CFA information of a basic block matches outgoing CFA 116 /// information of the previous block. If it doesn't, insert CFI instruction 117 /// at the beginning of the block that corrects the CFA calculation rule for 118 /// that block. 119 bool insertCFIInstrs(MachineFunction &MF); 120 /// Return the cfa offset value that should be set at the beginning of a MBB 121 /// if needed. The negated value is needed when creating CFI instructions that 122 /// set absolute offset. 123 int64_t getCorrectCFAOffset(MachineBasicBlock *MBB) { 124 return MBBVector[MBB->getNumber()].IncomingCFAOffset; 125 } 126 127 void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); 128 void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); 129 /// Go through each MBB in a function and check that outgoing offset and 130 /// register of its predecessors match incoming offset and register of that 131 /// MBB, as well as that incoming offset and register of its successors match 132 /// outgoing offset and register of the MBB. 133 unsigned verify(MachineFunction &MF); 134 }; 135 } // namespace 136 137 char CFIInstrInserter::ID = 0; 138 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter", 139 "Check CFA info and insert CFI instructions if needed", false, 140 false) 141 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); } 142 143 void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) { 144 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 145 // Initial CFA offset value i.e. the one valid at the beginning of the 146 // function. 147 int InitialOffset = 148 MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF); 149 // Initial CFA register value i.e. the one valid at the beginning of the 150 // function. 151 Register InitialRegister = 152 MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF); 153 InitialRegister = TRI.getDwarfRegNum(InitialRegister, true); 154 unsigned NumRegs = TRI.getNumSupportedRegs(MF); 155 156 // Initialize MBBMap. 157 for (MachineBasicBlock &MBB : MF) { 158 MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()]; 159 MBBInfo.MBB = &MBB; 160 MBBInfo.IncomingCFAOffset = InitialOffset; 161 MBBInfo.OutgoingCFAOffset = InitialOffset; 162 MBBInfo.IncomingCFARegister = InitialRegister; 163 MBBInfo.OutgoingCFARegister = InitialRegister; 164 MBBInfo.IncomingCSRSaved.resize(NumRegs); 165 MBBInfo.OutgoingCSRSaved.resize(NumRegs); 166 } 167 CSRLocMap.clear(); 168 169 // Set in/out cfa info for all blocks in the function. This traversal is based 170 // on the assumption that the first block in the function is the entry block 171 // i.e. that it has initial cfa offset and register values as incoming CFA 172 // information. 173 updateSuccCFAInfo(MBBVector[MF.front().getNumber()]); 174 } 175 176 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) { 177 // Outgoing cfa offset set by the block. 178 int64_t SetOffset = MBBInfo.IncomingCFAOffset; 179 // Outgoing cfa register set by the block. 180 unsigned SetRegister = MBBInfo.IncomingCFARegister; 181 MachineFunction *MF = MBBInfo.MBB->getParent(); 182 const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions(); 183 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); 184 unsigned NumRegs = TRI.getNumSupportedRegs(*MF); 185 BitVector CSRSaved(NumRegs), CSRRestored(NumRegs); 186 187 // Determine cfa offset and register set by the block. 188 for (MachineInstr &MI : *MBBInfo.MBB) { 189 if (MI.isCFIInstruction()) { 190 std::optional<unsigned> CSRReg; 191 std::optional<int64_t> CSROffset; 192 unsigned CFIIndex = MI.getOperand(0).getCFIIndex(); 193 const MCCFIInstruction &CFI = Instrs[CFIIndex]; 194 switch (CFI.getOperation()) { 195 case MCCFIInstruction::OpDefCfaRegister: 196 SetRegister = CFI.getRegister(); 197 break; 198 case MCCFIInstruction::OpDefCfaOffset: 199 SetOffset = CFI.getOffset(); 200 break; 201 case MCCFIInstruction::OpAdjustCfaOffset: 202 SetOffset += CFI.getOffset(); 203 break; 204 case MCCFIInstruction::OpDefCfa: 205 SetRegister = CFI.getRegister(); 206 SetOffset = CFI.getOffset(); 207 break; 208 case MCCFIInstruction::OpOffset: 209 CSROffset = CFI.getOffset(); 210 break; 211 case MCCFIInstruction::OpRegister: 212 CSRReg = CFI.getRegister2(); 213 break; 214 case MCCFIInstruction::OpRelOffset: 215 CSROffset = CFI.getOffset() - SetOffset; 216 break; 217 case MCCFIInstruction::OpRestore: 218 CSRRestored.set(CFI.getRegister()); 219 break; 220 case MCCFIInstruction::OpLLVMDefAspaceCfa: 221 // TODO: Add support for handling cfi_def_aspace_cfa. 222 #ifndef NDEBUG 223 report_fatal_error( 224 "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA " 225 "may be incorrect!\n"); 226 #endif 227 break; 228 case MCCFIInstruction::OpRememberState: 229 // TODO: Add support for handling cfi_remember_state. 230 #ifndef NDEBUG 231 report_fatal_error( 232 "Support for cfi_remember_state not implemented! Value of CFA " 233 "may be incorrect!\n"); 234 #endif 235 break; 236 case MCCFIInstruction::OpRestoreState: 237 // TODO: Add support for handling cfi_restore_state. 238 #ifndef NDEBUG 239 report_fatal_error( 240 "Support for cfi_restore_state not implemented! Value of CFA may " 241 "be incorrect!\n"); 242 #endif 243 break; 244 // Other CFI directives do not affect CFA value. 245 case MCCFIInstruction::OpUndefined: 246 case MCCFIInstruction::OpSameValue: 247 case MCCFIInstruction::OpEscape: 248 case MCCFIInstruction::OpWindowSave: 249 case MCCFIInstruction::OpNegateRAState: 250 case MCCFIInstruction::OpGnuArgsSize: 251 case MCCFIInstruction::OpLabel: 252 break; 253 } 254 if (CSRReg || CSROffset) { 255 auto It = CSRLocMap.find(CFI.getRegister()); 256 if (It == CSRLocMap.end()) { 257 CSRLocMap.insert( 258 {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)}); 259 } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) { 260 llvm_unreachable("Different saved locations for the same CSR"); 261 } 262 CSRSaved.set(CFI.getRegister()); 263 } 264 } 265 } 266 267 MBBInfo.Processed = true; 268 269 // Update outgoing CFA info. 270 MBBInfo.OutgoingCFAOffset = SetOffset; 271 MBBInfo.OutgoingCFARegister = SetRegister; 272 273 // Update outgoing CSR info. 274 BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; }, 275 MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved, 276 CSRRestored); 277 } 278 279 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) { 280 SmallVector<MachineBasicBlock *, 4> Stack; 281 Stack.push_back(MBBInfo.MBB); 282 283 do { 284 MachineBasicBlock *Current = Stack.pop_back_val(); 285 MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()]; 286 calculateOutgoingCFAInfo(CurrentInfo); 287 for (auto *Succ : CurrentInfo.MBB->successors()) { 288 MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()]; 289 if (!SuccInfo.Processed) { 290 SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset; 291 SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister; 292 SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved; 293 Stack.push_back(Succ); 294 } 295 } 296 } while (!Stack.empty()); 297 } 298 299 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) { 300 const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()]; 301 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 302 bool InsertedCFIInstr = false; 303 304 BitVector SetDifference; 305 for (MachineBasicBlock &MBB : MF) { 306 // Skip the first MBB in a function 307 if (MBB.getNumber() == MF.front().getNumber()) continue; 308 309 const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()]; 310 auto MBBI = MBBInfo.MBB->begin(); 311 DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI); 312 313 // If the current MBB will be placed in a unique section, a full DefCfa 314 // must be emitted. 315 const bool ForceFullCFA = MBB.isBeginSection(); 316 317 if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset && 318 PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) || 319 ForceFullCFA) { 320 // If both outgoing offset and register of a previous block don't match 321 // incoming offset and register of this block, or if this block begins a 322 // section, add a def_cfa instruction with the correct offset and 323 // register for this block. 324 unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa( 325 nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB))); 326 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 327 .addCFIIndex(CFIIndex); 328 InsertedCFIInstr = true; 329 } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) { 330 // If outgoing offset of a previous block doesn't match incoming offset 331 // of this block, add a def_cfa_offset instruction with the correct 332 // offset for this block. 333 unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset( 334 nullptr, getCorrectCFAOffset(&MBB))); 335 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 336 .addCFIIndex(CFIIndex); 337 InsertedCFIInstr = true; 338 } else if (PrevMBBInfo->OutgoingCFARegister != 339 MBBInfo.IncomingCFARegister) { 340 unsigned CFIIndex = 341 MF.addFrameInst(MCCFIInstruction::createDefCfaRegister( 342 nullptr, MBBInfo.IncomingCFARegister)); 343 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 344 .addCFIIndex(CFIIndex); 345 InsertedCFIInstr = true; 346 } 347 348 if (ForceFullCFA) { 349 MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA( 350 *MBBInfo.MBB, MBBI); 351 InsertedCFIInstr = true; 352 PrevMBBInfo = &MBBInfo; 353 continue; 354 } 355 356 BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference, 357 PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved); 358 for (int Reg : SetDifference.set_bits()) { 359 unsigned CFIIndex = 360 MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg)); 361 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 362 .addCFIIndex(CFIIndex); 363 InsertedCFIInstr = true; 364 } 365 366 BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference, 367 MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved); 368 for (int Reg : SetDifference.set_bits()) { 369 auto it = CSRLocMap.find(Reg); 370 assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap"); 371 unsigned CFIIndex; 372 CSRSavedLocation RO = it->second; 373 if (!RO.Reg && RO.Offset) { 374 CFIIndex = MF.addFrameInst( 375 MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset)); 376 } else if (RO.Reg && !RO.Offset) { 377 CFIIndex = MF.addFrameInst( 378 MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg)); 379 } else { 380 llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid"); 381 } 382 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 383 .addCFIIndex(CFIIndex); 384 InsertedCFIInstr = true; 385 } 386 387 PrevMBBInfo = &MBBInfo; 388 } 389 return InsertedCFIInstr; 390 } 391 392 void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred, 393 const MBBCFAInfo &Succ) { 394 errs() << "*** Inconsistent CFA register and/or offset between pred and succ " 395 "***\n"; 396 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 397 << " in " << Pred.MBB->getParent()->getName() 398 << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n"; 399 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 400 << " in " << Pred.MBB->getParent()->getName() 401 << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n"; 402 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 403 << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n"; 404 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 405 << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n"; 406 } 407 408 void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred, 409 const MBBCFAInfo &Succ) { 410 errs() << "*** Inconsistent CSR Saved between pred and succ in function " 411 << Pred.MBB->getParent()->getName() << " ***\n"; 412 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 413 << " outgoing CSR Saved: "; 414 for (int Reg : Pred.OutgoingCSRSaved.set_bits()) 415 errs() << Reg << " "; 416 errs() << "\n"; 417 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 418 << " incoming CSR Saved: "; 419 for (int Reg : Succ.IncomingCSRSaved.set_bits()) 420 errs() << Reg << " "; 421 errs() << "\n"; 422 } 423 424 unsigned CFIInstrInserter::verify(MachineFunction &MF) { 425 unsigned ErrorNum = 0; 426 for (auto *CurrMBB : depth_first(&MF)) { 427 const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()]; 428 for (MachineBasicBlock *Succ : CurrMBB->successors()) { 429 const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()]; 430 // Check that incoming offset and register values of successors match the 431 // outgoing offset and register values of CurrMBB 432 if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset || 433 SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) { 434 // Inconsistent offsets/registers are ok for 'noreturn' blocks because 435 // we don't generate epilogues inside such blocks. 436 if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock()) 437 continue; 438 reportCFAError(CurrMBBInfo, SuccMBBInfo); 439 ErrorNum++; 440 } 441 // Check that IncomingCSRSaved of every successor matches the 442 // OutgoingCSRSaved of CurrMBB 443 if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) { 444 reportCSRError(CurrMBBInfo, SuccMBBInfo); 445 ErrorNum++; 446 } 447 } 448 } 449 return ErrorNum; 450 } 451