475 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file This pass verifies incoming and outgoing CFA information of basic10/// blocks. CFA information is information about offset and register set by CFI11/// directives, valid at the start and end of a basic block. This pass checks12/// that outgoing information of predecessors matches incoming information of13/// their successors. Then it checks if blocks have correct CFA calculation rule14/// set and inserts additional CFI instruction at their beginnings if they15/// don't. CFI instructions are inserted if basic blocks have incorrect offset16/// or register set by previous blocks, as a result of a non-linear layout of17/// 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/MCContext.h"29#include "llvm/MC/MCDwarf.h"30using namespace llvm;31 32static cl::opt<bool> VerifyCFI("verify-cfiinstrs",33 cl::desc("Verify Call Frame Information instructions"),34 cl::init(false),35 cl::Hidden);36 37namespace {38class CFIInstrInserter : public MachineFunctionPass {39 public:40 static char ID;41 42 CFIInstrInserter() : MachineFunctionPass(ID) {43 initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry());44 }45 46 void getAnalysisUsage(AnalysisUsage &AU) const override {47 AU.setPreservesAll();48 MachineFunctionPass::getAnalysisUsage(AU);49 }50 51 bool runOnMachineFunction(MachineFunction &MF) override {52 if (!MF.needsFrameMoves())53 return false;54 55 MBBVector.resize(MF.getNumBlockIDs());56 calculateCFAInfo(MF);57 58 if (VerifyCFI) {59 if (unsigned ErrorNum = verify(MF))60 report_fatal_error("Found " + Twine(ErrorNum) +61 " in/out CFI information errors.");62 }63 bool insertedCFI = insertCFIInstrs(MF);64 MBBVector.clear();65 return insertedCFI;66 }67 68 private:69 struct MBBCFAInfo {70 MachineBasicBlock *MBB;71 /// Value of cfa offset valid at basic block entry.72 int64_t IncomingCFAOffset = -1;73 /// Value of cfa offset valid at basic block exit.74 int64_t OutgoingCFAOffset = -1;75 /// Value of cfa register valid at basic block entry.76 unsigned IncomingCFARegister = 0;77 /// Value of cfa register valid at basic block exit.78 unsigned OutgoingCFARegister = 0;79 /// Set of callee saved registers saved at basic block entry.80 BitVector IncomingCSRSaved;81 /// Set of callee saved registers saved at basic block exit.82 BitVector OutgoingCSRSaved;83 /// If in/out cfa offset and register values for this block have already84 /// been set or not.85 bool Processed = false;86 };87 88#define INVALID_REG UINT_MAX89#define INVALID_OFFSET INT_MAX90 /// contains the location where CSR register is saved.91 struct CSRSavedLocation {92 CSRSavedLocation(std::optional<unsigned> R, std::optional<int> O)93 : Reg(R), Offset(O) {}94 std::optional<unsigned> Reg;95 std::optional<int> Offset;96 };97 98 /// Contains cfa offset and register values valid at entry and exit of basic99 /// blocks.100 std::vector<MBBCFAInfo> MBBVector;101 102 /// Map the callee save registers to the locations where they are saved.103 SmallDenseMap<unsigned, CSRSavedLocation, 16> CSRLocMap;104 105 /// Calculate cfa offset and register values valid at entry and exit for all106 /// basic blocks in a function.107 void calculateCFAInfo(MachineFunction &MF);108 /// Calculate cfa offset and register values valid at basic block exit by109 /// checking the block for CFI instructions. Block's incoming CFA info remains110 /// the same.111 void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo);112 /// Update in/out cfa offset and register values for successors of the basic113 /// block.114 void updateSuccCFAInfo(MBBCFAInfo &MBBInfo);115 116 /// Check if incoming CFA information of a basic block matches outgoing CFA117 /// information of the previous block. If it doesn't, insert CFI instruction118 /// at the beginning of the block that corrects the CFA calculation rule for119 /// that block.120 bool insertCFIInstrs(MachineFunction &MF);121 /// Return the cfa offset value that should be set at the beginning of a MBB122 /// if needed. The negated value is needed when creating CFI instructions that123 /// set absolute offset.124 int64_t getCorrectCFAOffset(MachineBasicBlock *MBB) {125 return MBBVector[MBB->getNumber()].IncomingCFAOffset;126 }127 128 void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);129 void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);130 /// Go through each MBB in a function and check that outgoing offset and131 /// register of its predecessors match incoming offset and register of that132 /// MBB, as well as that incoming offset and register of its successors match133 /// outgoing offset and register of the MBB.134 unsigned verify(MachineFunction &MF);135};136} // namespace137 138char CFIInstrInserter::ID = 0;139INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",140 "Check CFA info and insert CFI instructions if needed", false,141 false)142FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }143 144void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {145 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();146 // Initial CFA offset value i.e. the one valid at the beginning of the147 // function.148 int InitialOffset =149 MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);150 // Initial CFA register value i.e. the one valid at the beginning of the151 // function.152 Register InitialRegister =153 MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);154 unsigned DwarfInitialRegister = TRI.getDwarfRegNum(InitialRegister, true);155 unsigned NumRegs = TRI.getNumSupportedRegs(MF);156 157 // Initialize MBBMap.158 for (MachineBasicBlock &MBB : MF) {159 MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];160 MBBInfo.MBB = &MBB;161 MBBInfo.IncomingCFAOffset = InitialOffset;162 MBBInfo.OutgoingCFAOffset = InitialOffset;163 MBBInfo.IncomingCFARegister = DwarfInitialRegister;164 MBBInfo.OutgoingCFARegister = DwarfInitialRegister;165 MBBInfo.IncomingCSRSaved.resize(NumRegs);166 MBBInfo.OutgoingCSRSaved.resize(NumRegs);167 }168 CSRLocMap.clear();169 170 // Set in/out cfa info for all blocks in the function. This traversal is based171 // on the assumption that the first block in the function is the entry block172 // i.e. that it has initial cfa offset and register values as incoming CFA173 // information.174 updateSuccCFAInfo(MBBVector[MF.front().getNumber()]);175}176 177void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {178 // Outgoing cfa offset set by the block.179 int64_t SetOffset = MBBInfo.IncomingCFAOffset;180 // Outgoing cfa register set by the block.181 unsigned SetRegister = MBBInfo.IncomingCFARegister;182 MachineFunction *MF = MBBInfo.MBB->getParent();183 const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions();184 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();185 unsigned NumRegs = TRI.getNumSupportedRegs(*MF);186 BitVector CSRSaved(NumRegs), CSRRestored(NumRegs);187 188#ifndef NDEBUG189 int RememberState = 0;190#endif191 192 // Determine cfa offset and register set by the block.193 for (MachineInstr &MI : *MBBInfo.MBB) {194 if (MI.isCFIInstruction()) {195 std::optional<unsigned> CSRReg;196 std::optional<int64_t> CSROffset;197 unsigned CFIIndex = MI.getOperand(0).getCFIIndex();198 const MCCFIInstruction &CFI = Instrs[CFIIndex];199 switch (CFI.getOperation()) {200 case MCCFIInstruction::OpDefCfaRegister:201 SetRegister = CFI.getRegister();202 break;203 case MCCFIInstruction::OpDefCfaOffset:204 SetOffset = CFI.getOffset();205 break;206 case MCCFIInstruction::OpAdjustCfaOffset:207 SetOffset += CFI.getOffset();208 break;209 case MCCFIInstruction::OpDefCfa:210 SetRegister = CFI.getRegister();211 SetOffset = CFI.getOffset();212 break;213 case MCCFIInstruction::OpOffset:214 CSROffset = CFI.getOffset();215 break;216 case MCCFIInstruction::OpRegister:217 CSRReg = CFI.getRegister2();218 break;219 case MCCFIInstruction::OpRelOffset:220 CSROffset = CFI.getOffset() - SetOffset;221 break;222 case MCCFIInstruction::OpRestore:223 CSRRestored.set(CFI.getRegister());224 break;225 case MCCFIInstruction::OpLLVMDefAspaceCfa:226 // TODO: Add support for handling cfi_def_aspace_cfa.227#ifndef NDEBUG228 report_fatal_error(229 "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA "230 "may be incorrect!\n");231#endif232 break;233 case MCCFIInstruction::OpRememberState:234 // TODO: Add support for handling cfi_remember_state.235#ifndef NDEBUG236 // Currently we need cfi_remember_state and cfi_restore_state to be in237 // the same BB, so it will not impact outgoing CFA.238 ++RememberState;239 if (RememberState != 1)240 MF->getContext().reportError(241 SMLoc(),242 "Support for cfi_remember_state not implemented! Value of CFA "243 "may be incorrect!\n");244#endif245 break;246 case MCCFIInstruction::OpRestoreState:247 // TODO: Add support for handling cfi_restore_state.248#ifndef NDEBUG249 --RememberState;250 if (RememberState != 0)251 MF->getContext().reportError(252 SMLoc(),253 "Support for cfi_restore_state not implemented! Value of CFA may "254 "be incorrect!\n");255#endif256 break;257 // Other CFI directives do not affect CFA value.258 case MCCFIInstruction::OpUndefined:259 case MCCFIInstruction::OpSameValue:260 case MCCFIInstruction::OpEscape:261 case MCCFIInstruction::OpWindowSave:262 case MCCFIInstruction::OpNegateRAState:263 case MCCFIInstruction::OpNegateRAStateWithPC:264 case MCCFIInstruction::OpGnuArgsSize:265 case MCCFIInstruction::OpLabel:266 case MCCFIInstruction::OpValOffset:267 break;268 }269 if (CSRReg || CSROffset) {270 auto It = CSRLocMap.find(CFI.getRegister());271 if (It == CSRLocMap.end()) {272 CSRLocMap.insert(273 {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)});274 } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) {275 reportFatalInternalError(276 "Different saved locations for the same CSR");277 }278 CSRSaved.set(CFI.getRegister());279 }280 }281 }282 283#ifndef NDEBUG284 if (RememberState != 0)285 MF->getContext().reportError(286 SMLoc(),287 "Support for cfi_remember_state not implemented! Value of CFA may be "288 "incorrect!\n");289#endif290 291 MBBInfo.Processed = true;292 293 // Update outgoing CFA info.294 MBBInfo.OutgoingCFAOffset = SetOffset;295 MBBInfo.OutgoingCFARegister = SetRegister;296 297 // Update outgoing CSR info.298 BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; },299 MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved,300 CSRRestored);301}302 303void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {304 SmallVector<MachineBasicBlock *, 4> Stack;305 Stack.push_back(MBBInfo.MBB);306 307 do {308 MachineBasicBlock *Current = Stack.pop_back_val();309 MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];310 calculateOutgoingCFAInfo(CurrentInfo);311 for (auto *Succ : CurrentInfo.MBB->successors()) {312 MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];313 if (!SuccInfo.Processed) {314 SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;315 SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;316 SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved;317 Stack.push_back(Succ);318 }319 }320 } while (!Stack.empty());321}322 323bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {324 const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];325 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();326 bool InsertedCFIInstr = false;327 328 BitVector SetDifference;329 for (MachineBasicBlock &MBB : MF) {330 // Skip the first MBB in a function331 if (MBB.getNumber() == MF.front().getNumber()) continue;332 333 const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];334 auto MBBI = MBBInfo.MBB->begin();335 DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);336 337 // If the current MBB will be placed in a unique section, a full DefCfa338 // must be emitted.339 const bool ForceFullCFA = MBB.isBeginSection();340 341 if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset &&342 PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) ||343 ForceFullCFA) {344 // If both outgoing offset and register of a previous block don't match345 // incoming offset and register of this block, or if this block begins a346 // section, add a def_cfa instruction with the correct offset and347 // register for this block.348 unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa(349 nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));350 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))351 .addCFIIndex(CFIIndex);352 InsertedCFIInstr = true;353 } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {354 // If outgoing offset of a previous block doesn't match incoming offset355 // of this block, add a def_cfa_offset instruction with the correct356 // offset for this block.357 unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset(358 nullptr, getCorrectCFAOffset(&MBB)));359 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))360 .addCFIIndex(CFIIndex);361 InsertedCFIInstr = true;362 } else if (PrevMBBInfo->OutgoingCFARegister !=363 MBBInfo.IncomingCFARegister) {364 unsigned CFIIndex =365 MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(366 nullptr, MBBInfo.IncomingCFARegister));367 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))368 .addCFIIndex(CFIIndex);369 InsertedCFIInstr = true;370 }371 372 if (ForceFullCFA) {373 MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA(374 *MBBInfo.MBB, MBBI);375 InsertedCFIInstr = true;376 PrevMBBInfo = &MBBInfo;377 continue;378 }379 380 BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,381 PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved);382 for (int Reg : SetDifference.set_bits()) {383 unsigned CFIIndex =384 MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg));385 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))386 .addCFIIndex(CFIIndex);387 InsertedCFIInstr = true;388 }389 390 BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,391 MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved);392 for (int Reg : SetDifference.set_bits()) {393 auto it = CSRLocMap.find(Reg);394 assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");395 unsigned CFIIndex;396 CSRSavedLocation RO = it->second;397 if (!RO.Reg && RO.Offset) {398 CFIIndex = MF.addFrameInst(399 MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset));400 } else if (RO.Reg && !RO.Offset) {401 CFIIndex = MF.addFrameInst(402 MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg));403 } else {404 llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid");405 }406 BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))407 .addCFIIndex(CFIIndex);408 InsertedCFIInstr = true;409 }410 411 PrevMBBInfo = &MBBInfo;412 }413 return InsertedCFIInstr;414}415 416void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred,417 const MBBCFAInfo &Succ) {418 errs() << "*** Inconsistent CFA register and/or offset between pred and succ "419 "***\n";420 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()421 << " in " << Pred.MBB->getParent()->getName()422 << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";423 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()424 << " in " << Pred.MBB->getParent()->getName()425 << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";426 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()427 << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";428 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()429 << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";430}431 432void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred,433 const MBBCFAInfo &Succ) {434 errs() << "*** Inconsistent CSR Saved between pred and succ in function "435 << Pred.MBB->getParent()->getName() << " ***\n";436 errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()437 << " outgoing CSR Saved: ";438 for (int Reg : Pred.OutgoingCSRSaved.set_bits())439 errs() << Reg << " ";440 errs() << "\n";441 errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()442 << " incoming CSR Saved: ";443 for (int Reg : Succ.IncomingCSRSaved.set_bits())444 errs() << Reg << " ";445 errs() << "\n";446}447 448unsigned CFIInstrInserter::verify(MachineFunction &MF) {449 unsigned ErrorNum = 0;450 for (auto *CurrMBB : depth_first(&MF)) {451 const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];452 for (MachineBasicBlock *Succ : CurrMBB->successors()) {453 const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];454 // Check that incoming offset and register values of successors match the455 // outgoing offset and register values of CurrMBB456 if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||457 SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {458 // Inconsistent offsets/registers are ok for 'noreturn' blocks because459 // we don't generate epilogues inside such blocks.460 if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())461 continue;462 reportCFAError(CurrMBBInfo, SuccMBBInfo);463 ErrorNum++;464 }465 // Check that IncomingCSRSaved of every successor matches the466 // OutgoingCSRSaved of CurrMBB467 if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) {468 reportCSRError(CurrMBBInfo, SuccMBBInfo);469 ErrorNum++;470 }471 }472 }473 return ErrorNum;474}475