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()->emitCalleeSavedFrameMoves( 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