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/SetOperations.h" 22 #include "llvm/CodeGen/MachineFunctionPass.h" 23 #include "llvm/CodeGen/MachineInstrBuilder.h" 24 #include "llvm/CodeGen/MachineModuleInfo.h" 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/CodeGen/TargetFrameLowering.h" 27 #include "llvm/CodeGen/TargetInstrInfo.h" 28 #include "llvm/CodeGen/TargetSubtargetInfo.h" 29 #include "llvm/InitializePasses.h" 30 #include "llvm/Target/TargetMachine.h" 31 using namespace llvm; 32 33 static cl::opt<bool> VerifyCFI("verify-cfiinstrs", 34 cl::desc("Verify Call Frame Information instructions"), 35 cl::init(false), 36 cl::Hidden); 37 38 namespace { 39 class CFIInstrInserter : public MachineFunctionPass { 40 public: 41 static char ID; 42 43 CFIInstrInserter() : MachineFunctionPass(ID) { 44 initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry()); 45 } 46 47 void getAnalysisUsage(AnalysisUsage &AU) const override { 48 AU.setPreservesAll(); 49 MachineFunctionPass::getAnalysisUsage(AU); 50 } 51 52 bool runOnMachineFunction(MachineFunction &MF) override { 53 if (!MF.needsFrameMoves()) 54 return false; 55 56 MBBVector.resize(MF.getNumBlockIDs()); 57 calculateCFAInfo(MF); 58 59 if (VerifyCFI) { 60 if (unsigned ErrorNum = verify(MF)) 61 report_fatal_error("Found " + Twine(ErrorNum) + 62 " in/out CFI information errors."); 63 } 64 bool insertedCFI = insertCFIInstrs(MF); 65 MBBVector.clear(); 66 return insertedCFI; 67 } 68 69 private: 70 struct MBBCFAInfo { 71 MachineBasicBlock *MBB; 72 /// Value of cfa offset valid at basic block entry. 73 int IncomingCFAOffset = -1; 74 /// Value of cfa offset valid at basic block exit. 75 int OutgoingCFAOffset = -1; 76 /// Value of cfa register valid at basic block entry. 77 unsigned IncomingCFARegister = 0; 78 /// Value of cfa register valid at basic block exit. 79 unsigned OutgoingCFARegister = 0; 80 /// Set of callee saved registers saved at basic block entry. 81 BitVector IncomingCSRSaved; 82 /// Set of callee saved registers saved at basic block exit. 83 BitVector OutgoingCSRSaved; 84 /// If in/out cfa offset and register values for this block have already 85 /// been set or not. 86 bool Processed = false; 87 }; 88 89 /// Contains cfa offset and register values valid at entry and exit of basic 90 /// blocks. 91 std::vector<MBBCFAInfo> MBBVector; 92 93 /// Calculate cfa offset and register values valid at entry and exit for all 94 /// basic blocks in a function. 95 void calculateCFAInfo(MachineFunction &MF); 96 /// Calculate cfa offset and register values valid at basic block exit by 97 /// checking the block for CFI instructions. Block's incoming CFA info remains 98 /// the same. 99 void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo); 100 /// Update in/out cfa offset and register values for successors of the basic 101 /// block. 102 void updateSuccCFAInfo(MBBCFAInfo &MBBInfo); 103 104 /// Check if incoming CFA information of a basic block matches outgoing CFA 105 /// information of the previous block. If it doesn't, insert CFI instruction 106 /// at the beginning of the block that corrects the CFA calculation rule for 107 /// that block. 108 bool insertCFIInstrs(MachineFunction &MF); 109 /// Return the cfa offset value that should be set at the beginning of a MBB 110 /// if needed. The negated value is needed when creating CFI instructions that 111 /// set absolute offset. 112 int getCorrectCFAOffset(MachineBasicBlock *MBB) { 113 return -MBBVector[MBB->getNumber()].IncomingCFAOffset; 114 } 115 116 void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); 117 void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); 118 /// Go through each MBB in a function and check that outgoing offset and 119 /// register of its predecessors match incoming offset and register of that 120 /// MBB, as well as that incoming offset and register of its successors match 121 /// outgoing offset and register of the MBB. 122 unsigned verify(MachineFunction &MF); 123 }; 124 } // namespace 125 126 char CFIInstrInserter::ID = 0; 127 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter", 128 "Check CFA info and insert CFI instructions if needed", false, 129 false) 130 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); } 131 132 void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) { 133 // Initial CFA offset value i.e. the one valid at the beginning of the 134 // function. 135 int InitialOffset = 136 MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF); 137 // Initial CFA register value i.e. the one valid at the beginning of the 138 // function. 139 unsigned InitialRegister = 140 MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF); 141 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 142 unsigned NumRegs = TRI.getNumRegs(); 143 144 // Initialize MBBMap. 145 for (MachineBasicBlock &MBB : MF) { 146 MBBCFAInfo MBBInfo; 147 MBBInfo.MBB = &MBB; 148 MBBInfo.IncomingCFAOffset = InitialOffset; 149 MBBInfo.OutgoingCFAOffset = InitialOffset; 150 MBBInfo.IncomingCFARegister = InitialRegister; 151 MBBInfo.OutgoingCFARegister = InitialRegister; 152 MBBInfo.IncomingCSRSaved.resize(NumRegs); 153 MBBInfo.OutgoingCSRSaved.resize(NumRegs); 154 MBBVector[MBB.getNumber()] = MBBInfo; 155 } 156 157 // Set in/out cfa info for all blocks in the function. This traversal is based 158 // on the assumption that the first block in the function is the entry block 159 // i.e. that it has initial cfa offset and register values as incoming CFA 160 // information. 161 for (MachineBasicBlock &MBB : MF) { 162 if (MBBVector[MBB.getNumber()].Processed) continue; 163 updateSuccCFAInfo(MBBVector[MBB.getNumber()]); 164 } 165 } 166 167 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) { 168 // Outgoing cfa offset set by the block. 169 int SetOffset = MBBInfo.IncomingCFAOffset; 170 // Outgoing cfa register set by the block. 171 unsigned SetRegister = MBBInfo.IncomingCFARegister; 172 MachineFunction *MF = MBBInfo.MBB->getParent(); 173 const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions(); 174 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); 175 unsigned NumRegs = TRI.getNumRegs(); 176 BitVector CSRSaved(NumRegs), CSRRestored(NumRegs); 177 178 // Determine cfa offset and register set by the block. 179 for (MachineInstr &MI : *MBBInfo.MBB) { 180 if (MI.isCFIInstruction()) { 181 unsigned CFIIndex = MI.getOperand(0).getCFIIndex(); 182 const MCCFIInstruction &CFI = Instrs[CFIIndex]; 183 switch (CFI.getOperation()) { 184 case MCCFIInstruction::OpDefCfaRegister: 185 SetRegister = CFI.getRegister(); 186 break; 187 case MCCFIInstruction::OpDefCfaOffset: 188 SetOffset = CFI.getOffset(); 189 break; 190 case MCCFIInstruction::OpAdjustCfaOffset: 191 SetOffset += CFI.getOffset(); 192 break; 193 case MCCFIInstruction::OpDefCfa: 194 SetRegister = CFI.getRegister(); 195 SetOffset = CFI.getOffset(); 196 break; 197 case MCCFIInstruction::OpOffset: 198 case MCCFIInstruction::OpRegister: 199 case MCCFIInstruction::OpRelOffset: 200 CSRSaved.set(CFI.getRegister()); 201 break; 202 case MCCFIInstruction::OpRestore: 203 case MCCFIInstruction::OpUndefined: 204 CSRRestored.set(CFI.getRegister()); 205 break; 206 case MCCFIInstruction::OpRememberState: 207 // TODO: Add support for handling cfi_remember_state. 208 #ifndef NDEBUG 209 report_fatal_error( 210 "Support for cfi_remember_state not implemented! Value of CFA " 211 "may be incorrect!\n"); 212 #endif 213 break; 214 case MCCFIInstruction::OpRestoreState: 215 // TODO: Add support for handling cfi_restore_state. 216 #ifndef NDEBUG 217 report_fatal_error( 218 "Support for cfi_restore_state not implemented! Value of CFA may " 219 "be incorrect!\n"); 220 #endif 221 break; 222 // Other CFI directives do not affect CFA value. 223 case MCCFIInstruction::OpSameValue: 224 case MCCFIInstruction::OpEscape: 225 case MCCFIInstruction::OpWindowSave: 226 case MCCFIInstruction::OpNegateRAState: 227 case MCCFIInstruction::OpGnuArgsSize: 228 break; 229 } 230 } 231 } 232 233 MBBInfo.Processed = true; 234 235 // Update outgoing CFA info. 236 MBBInfo.OutgoingCFAOffset = SetOffset; 237 MBBInfo.OutgoingCFARegister = SetRegister; 238 239 // Update outgoing CSR info. 240 MBBInfo.OutgoingCSRSaved = MBBInfo.IncomingCSRSaved; 241 MBBInfo.OutgoingCSRSaved |= CSRSaved; 242 MBBInfo.OutgoingCSRSaved.reset(CSRRestored); 243 } 244 245 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) { 246 SmallVector<MachineBasicBlock *, 4> Stack; 247 Stack.push_back(MBBInfo.MBB); 248 249 do { 250 MachineBasicBlock *Current = Stack.pop_back_val(); 251 MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()]; 252 if (CurrentInfo.Processed) 253 continue; 254 255 calculateOutgoingCFAInfo(CurrentInfo); 256 for (auto *Succ : CurrentInfo.MBB->successors()) { 257 MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()]; 258 if (!SuccInfo.Processed) { 259 SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset; 260 SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister; 261 SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved; 262 Stack.push_back(Succ); 263 } 264 } 265 } while (!Stack.empty()); 266 } 267 268 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) { 269 const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()]; 270 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 271 bool InsertedCFIInstr = false; 272 273 for (MachineBasicBlock &MBB : MF) { 274 // Skip the first MBB in a function 275 if (MBB.getNumber() == MF.front().getNumber()) continue; 276 277 const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()]; 278 auto MBBI = MBBInfo.MBB->begin(); 279 DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI); 280 281 if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) { 282 // If both outgoing offset and register of a previous block don't match 283 // incoming offset and register of this block, add a def_cfa instruction 284 // with the correct offset and register for this block. 285 if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) { 286 unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createDefCfa( 287 nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB))); 288 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 289 .addCFIIndex(CFIIndex); 290 // If outgoing offset of a previous block doesn't match incoming offset 291 // of this block, add a def_cfa_offset instruction with the correct 292 // offset for this block. 293 } else { 294 unsigned CFIIndex = 295 MF.addFrameInst(MCCFIInstruction::createDefCfaOffset( 296 nullptr, getCorrectCFAOffset(&MBB))); 297 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 298 .addCFIIndex(CFIIndex); 299 } 300 InsertedCFIInstr = true; 301 // If outgoing register of a previous block doesn't match incoming 302 // register of this block, add a def_cfa_register instruction with the 303 // correct register for this block. 304 } else if (PrevMBBInfo->OutgoingCFARegister != 305 MBBInfo.IncomingCFARegister) { 306 unsigned CFIIndex = 307 MF.addFrameInst(MCCFIInstruction::createDefCfaRegister( 308 nullptr, MBBInfo.IncomingCFARegister)); 309 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 310 .addCFIIndex(CFIIndex); 311 InsertedCFIInstr = true; 312 } 313 314 BitVector SetDifference = PrevMBBInfo->OutgoingCSRSaved; 315 SetDifference.reset(MBBInfo.IncomingCSRSaved); 316 for (int Reg : SetDifference.set_bits()) { 317 unsigned CFIIndex = 318 MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg)); 319 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) 320 .addCFIIndex(CFIIndex); 321 InsertedCFIInstr = true; 322 } 323 PrevMBBInfo = &MBBInfo; 324 } 325 return InsertedCFIInstr; 326 } 327 328 void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred, 329 const MBBCFAInfo &Succ) { 330 errs() << "*** Inconsistent CFA register and/or offset between pred and succ " 331 "***\n"; 332 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 333 << " in " << Pred.MBB->getParent()->getName() 334 << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n"; 335 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 336 << " in " << Pred.MBB->getParent()->getName() 337 << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n"; 338 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 339 << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n"; 340 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 341 << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n"; 342 } 343 344 void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred, 345 const MBBCFAInfo &Succ) { 346 errs() << "*** Inconsistent CSR Saved between pred and succ in function " 347 << Pred.MBB->getParent()->getName() << " ***\n"; 348 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() 349 << " outgoing CSR Saved: "; 350 for (int Reg : Pred.OutgoingCSRSaved.set_bits()) 351 errs() << Reg << " "; 352 errs() << "\n"; 353 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() 354 << " incoming CSR Saved: "; 355 for (int Reg : Succ.IncomingCSRSaved.set_bits()) 356 errs() << Reg << " "; 357 errs() << "\n"; 358 } 359 360 unsigned CFIInstrInserter::verify(MachineFunction &MF) { 361 unsigned ErrorNum = 0; 362 for (auto *CurrMBB : depth_first(&MF)) { 363 const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()]; 364 for (MachineBasicBlock *Succ : CurrMBB->successors()) { 365 const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()]; 366 // Check that incoming offset and register values of successors match the 367 // outgoing offset and register values of CurrMBB 368 if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset || 369 SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) { 370 // Inconsistent offsets/registers are ok for 'noreturn' blocks because 371 // we don't generate epilogues inside such blocks. 372 if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock()) 373 continue; 374 reportCFAError(CurrMBBInfo, SuccMBBInfo); 375 ErrorNum++; 376 } 377 // Check that IncomingCSRSaved of every successor matches the 378 // OutgoingCSRSaved of CurrMBB 379 if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) { 380 reportCSRError(CurrMBBInfo, SuccMBBInfo); 381 ErrorNum++; 382 } 383 } 384 } 385 return ErrorNum; 386 } 387