| //===------ CFIInstrInserter.cpp - Insert additional CFI instructions -----===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| /// \file This pass verifies incoming and outgoing CFA information of basic |
| /// blocks. CFA information is information about offset and register set by CFI |
| /// directives, valid at the start and end of a basic block. This pass checks |
| /// that outgoing information of predecessors matches incoming information of |
| /// their successors. Then it checks if blocks have correct CFA calculation rule |
| /// set and inserts additional CFI instruction at their beginnings if they |
| /// don't. CFI instructions are inserted if basic blocks have incorrect offset |
| /// or register set by previous blocks, as a result of a non-linear layout of |
| /// blocks in a function. |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/SetOperations.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineModuleInfo.h" |
| #include "llvm/CodeGen/Passes.h" |
| #include "llvm/CodeGen/TargetFrameLowering.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Target/TargetMachine.h" |
| using namespace llvm; |
| |
| static cl::opt<bool> VerifyCFI("verify-cfiinstrs", |
| cl::desc("Verify Call Frame Information instructions"), |
| cl::init(false), |
| cl::Hidden); |
| |
| namespace { |
| class CFIInstrInserter : public MachineFunctionPass { |
| public: |
| static char ID; |
| |
| CFIInstrInserter() : MachineFunctionPass(ID) { |
| initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.setPreservesAll(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| } |
| |
| bool runOnMachineFunction(MachineFunction &MF) override { |
| if (!MF.needsFrameMoves()) |
| return false; |
| |
| MBBVector.resize(MF.getNumBlockIDs()); |
| calculateCFAInfo(MF); |
| |
| if (VerifyCFI) { |
| if (unsigned ErrorNum = verify(MF)) |
| report_fatal_error("Found " + Twine(ErrorNum) + |
| " in/out CFI information errors."); |
| } |
| bool insertedCFI = insertCFIInstrs(MF); |
| MBBVector.clear(); |
| return insertedCFI; |
| } |
| |
| private: |
| struct MBBCFAInfo { |
| MachineBasicBlock *MBB; |
| /// Value of cfa offset valid at basic block entry. |
| int IncomingCFAOffset = -1; |
| /// Value of cfa offset valid at basic block exit. |
| int OutgoingCFAOffset = -1; |
| /// Value of cfa register valid at basic block entry. |
| unsigned IncomingCFARegister = 0; |
| /// Value of cfa register valid at basic block exit. |
| unsigned OutgoingCFARegister = 0; |
| /// Set of callee saved registers saved at basic block entry. |
| BitVector IncomingCSRSaved; |
| /// Set of callee saved registers saved at basic block exit. |
| BitVector OutgoingCSRSaved; |
| /// If in/out cfa offset and register values for this block have already |
| /// been set or not. |
| bool Processed = false; |
| }; |
| |
| #define INVALID_REG UINT_MAX |
| #define INVALID_OFFSET INT_MAX |
| /// contains the location where CSR register is saved. |
| struct CSRSavedLocation { |
| CSRSavedLocation(Optional<unsigned> R, Optional<int> O) |
| : Reg(R), Offset(O) {} |
| Optional<unsigned> Reg; |
| Optional<int> Offset; |
| }; |
| |
| /// Contains cfa offset and register values valid at entry and exit of basic |
| /// blocks. |
| std::vector<MBBCFAInfo> MBBVector; |
| |
| /// Map the callee save registers to the locations where they are saved. |
| SmallDenseMap<unsigned, CSRSavedLocation, 16> CSRLocMap; |
| |
| /// Calculate cfa offset and register values valid at entry and exit for all |
| /// basic blocks in a function. |
| void calculateCFAInfo(MachineFunction &MF); |
| /// Calculate cfa offset and register values valid at basic block exit by |
| /// checking the block for CFI instructions. Block's incoming CFA info remains |
| /// the same. |
| void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo); |
| /// Update in/out cfa offset and register values for successors of the basic |
| /// block. |
| void updateSuccCFAInfo(MBBCFAInfo &MBBInfo); |
| |
| /// Check if incoming CFA information of a basic block matches outgoing CFA |
| /// information of the previous block. If it doesn't, insert CFI instruction |
| /// at the beginning of the block that corrects the CFA calculation rule for |
| /// that block. |
| bool insertCFIInstrs(MachineFunction &MF); |
| /// Return the cfa offset value that should be set at the beginning of a MBB |
| /// if needed. The negated value is needed when creating CFI instructions that |
| /// set absolute offset. |
| int getCorrectCFAOffset(MachineBasicBlock *MBB) { |
| return MBBVector[MBB->getNumber()].IncomingCFAOffset; |
| } |
| |
| void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); |
| void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ); |
| /// Go through each MBB in a function and check that outgoing offset and |
| /// register of its predecessors match incoming offset and register of that |
| /// MBB, as well as that incoming offset and register of its successors match |
| /// outgoing offset and register of the MBB. |
| unsigned verify(MachineFunction &MF); |
| }; |
| } // namespace |
| |
| char CFIInstrInserter::ID = 0; |
| INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter", |
| "Check CFA info and insert CFI instructions if needed", false, |
| false) |
| FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); } |
| |
| void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) { |
| // Initial CFA offset value i.e. the one valid at the beginning of the |
| // function. |
| int InitialOffset = |
| MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF); |
| // Initial CFA register value i.e. the one valid at the beginning of the |
| // function. |
| unsigned InitialRegister = |
| MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF); |
| const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); |
| unsigned NumRegs = TRI.getNumRegs(); |
| |
| // Initialize MBBMap. |
| for (MachineBasicBlock &MBB : MF) { |
| MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()]; |
| MBBInfo.MBB = &MBB; |
| MBBInfo.IncomingCFAOffset = InitialOffset; |
| MBBInfo.OutgoingCFAOffset = InitialOffset; |
| MBBInfo.IncomingCFARegister = InitialRegister; |
| MBBInfo.OutgoingCFARegister = InitialRegister; |
| MBBInfo.IncomingCSRSaved.resize(NumRegs); |
| MBBInfo.OutgoingCSRSaved.resize(NumRegs); |
| } |
| CSRLocMap.clear(); |
| |
| // Set in/out cfa info for all blocks in the function. This traversal is based |
| // on the assumption that the first block in the function is the entry block |
| // i.e. that it has initial cfa offset and register values as incoming CFA |
| // information. |
| updateSuccCFAInfo(MBBVector[MF.front().getNumber()]); |
| } |
| |
| void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) { |
| // Outgoing cfa offset set by the block. |
| int SetOffset = MBBInfo.IncomingCFAOffset; |
| // Outgoing cfa register set by the block. |
| unsigned SetRegister = MBBInfo.IncomingCFARegister; |
| MachineFunction *MF = MBBInfo.MBB->getParent(); |
| const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions(); |
| const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); |
| unsigned NumRegs = TRI.getNumRegs(); |
| BitVector CSRSaved(NumRegs), CSRRestored(NumRegs); |
| |
| // Determine cfa offset and register set by the block. |
| for (MachineInstr &MI : *MBBInfo.MBB) { |
| if (MI.isCFIInstruction()) { |
| Optional<unsigned> CSRReg; |
| Optional<int> CSROffset; |
| unsigned CFIIndex = MI.getOperand(0).getCFIIndex(); |
| const MCCFIInstruction &CFI = Instrs[CFIIndex]; |
| switch (CFI.getOperation()) { |
| case MCCFIInstruction::OpDefCfaRegister: |
| SetRegister = CFI.getRegister(); |
| break; |
| case MCCFIInstruction::OpDefCfaOffset: |
| SetOffset = CFI.getOffset(); |
| break; |
| case MCCFIInstruction::OpAdjustCfaOffset: |
| SetOffset += CFI.getOffset(); |
| break; |
| case MCCFIInstruction::OpDefCfa: |
| SetRegister = CFI.getRegister(); |
| SetOffset = CFI.getOffset(); |
| break; |
| case MCCFIInstruction::OpOffset: |
| CSROffset = CFI.getOffset(); |
| break; |
| case MCCFIInstruction::OpRegister: |
| CSRReg = CFI.getRegister2(); |
| break; |
| case MCCFIInstruction::OpRelOffset: |
| CSROffset = CFI.getOffset() - SetOffset; |
| break; |
| case MCCFIInstruction::OpRestore: |
| CSRRestored.set(CFI.getRegister()); |
| break; |
| case MCCFIInstruction::OpLLVMDefAspaceCfa: |
| // TODO: Add support for handling cfi_def_aspace_cfa. |
| #ifndef NDEBUG |
| report_fatal_error( |
| "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA " |
| "may be incorrect!\n"); |
| #endif |
| break; |
| case MCCFIInstruction::OpRememberState: |
| // TODO: Add support for handling cfi_remember_state. |
| #ifndef NDEBUG |
| report_fatal_error( |
| "Support for cfi_remember_state not implemented! Value of CFA " |
| "may be incorrect!\n"); |
| #endif |
| break; |
| case MCCFIInstruction::OpRestoreState: |
| // TODO: Add support for handling cfi_restore_state. |
| #ifndef NDEBUG |
| report_fatal_error( |
| "Support for cfi_restore_state not implemented! Value of CFA may " |
| "be incorrect!\n"); |
| #endif |
| break; |
| // Other CFI directives do not affect CFA value. |
| case MCCFIInstruction::OpUndefined: |
| case MCCFIInstruction::OpSameValue: |
| case MCCFIInstruction::OpEscape: |
| case MCCFIInstruction::OpWindowSave: |
| case MCCFIInstruction::OpNegateRAState: |
| case MCCFIInstruction::OpGnuArgsSize: |
| break; |
| } |
| if (CSRReg || CSROffset) { |
| auto It = CSRLocMap.find(CFI.getRegister()); |
| if (It == CSRLocMap.end()) { |
| CSRLocMap.insert( |
| {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)}); |
| } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) { |
| llvm_unreachable("Different saved locations for the same CSR"); |
| } |
| CSRSaved.set(CFI.getRegister()); |
| } |
| } |
| } |
| |
| MBBInfo.Processed = true; |
| |
| // Update outgoing CFA info. |
| MBBInfo.OutgoingCFAOffset = SetOffset; |
| MBBInfo.OutgoingCFARegister = SetRegister; |
| |
| // Update outgoing CSR info. |
| BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; }, |
| MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved, |
| CSRRestored); |
| } |
| |
| void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) { |
| SmallVector<MachineBasicBlock *, 4> Stack; |
| Stack.push_back(MBBInfo.MBB); |
| |
| do { |
| MachineBasicBlock *Current = Stack.pop_back_val(); |
| MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()]; |
| calculateOutgoingCFAInfo(CurrentInfo); |
| for (auto *Succ : CurrentInfo.MBB->successors()) { |
| MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()]; |
| if (!SuccInfo.Processed) { |
| SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset; |
| SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister; |
| SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved; |
| Stack.push_back(Succ); |
| } |
| } |
| } while (!Stack.empty()); |
| } |
| |
| bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) { |
| const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()]; |
| const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); |
| bool InsertedCFIInstr = false; |
| |
| BitVector SetDifference; |
| for (MachineBasicBlock &MBB : MF) { |
| // Skip the first MBB in a function |
| if (MBB.getNumber() == MF.front().getNumber()) continue; |
| |
| const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()]; |
| auto MBBI = MBBInfo.MBB->begin(); |
| DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI); |
| |
| // If the current MBB will be placed in a unique section, a full DefCfa |
| // must be emitted. |
| const bool ForceFullCFA = MBB.isBeginSection(); |
| |
| if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset && |
| PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) || |
| ForceFullCFA) { |
| // If both outgoing offset and register of a previous block don't match |
| // incoming offset and register of this block, or if this block begins a |
| // section, add a def_cfa instruction with the correct offset and |
| // register for this block. |
| unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa( |
| nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB))); |
| BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(CFIIndex); |
| InsertedCFIInstr = true; |
| } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) { |
| // If outgoing offset of a previous block doesn't match incoming offset |
| // of this block, add a def_cfa_offset instruction with the correct |
| // offset for this block. |
| unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset( |
| nullptr, getCorrectCFAOffset(&MBB))); |
| BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(CFIIndex); |
| InsertedCFIInstr = true; |
| } else if (PrevMBBInfo->OutgoingCFARegister != |
| MBBInfo.IncomingCFARegister) { |
| unsigned CFIIndex = |
| MF.addFrameInst(MCCFIInstruction::createDefCfaRegister( |
| nullptr, MBBInfo.IncomingCFARegister)); |
| BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(CFIIndex); |
| InsertedCFIInstr = true; |
| } |
| |
| if (ForceFullCFA) { |
| MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMoves( |
| *MBBInfo.MBB, MBBI); |
| InsertedCFIInstr = true; |
| PrevMBBInfo = &MBBInfo; |
| continue; |
| } |
| |
| BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference, |
| PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved); |
| for (int Reg : SetDifference.set_bits()) { |
| unsigned CFIIndex = |
| MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg)); |
| BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(CFIIndex); |
| InsertedCFIInstr = true; |
| } |
| |
| BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference, |
| MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved); |
| for (int Reg : SetDifference.set_bits()) { |
| auto it = CSRLocMap.find(Reg); |
| assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap"); |
| unsigned CFIIndex; |
| CSRSavedLocation RO = it->second; |
| if (!RO.Reg && RO.Offset) { |
| CFIIndex = MF.addFrameInst( |
| MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset)); |
| } else if (RO.Reg && !RO.Offset) { |
| CFIIndex = MF.addFrameInst( |
| MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg)); |
| } else { |
| llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid"); |
| } |
| BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION)) |
| .addCFIIndex(CFIIndex); |
| InsertedCFIInstr = true; |
| } |
| |
| PrevMBBInfo = &MBBInfo; |
| } |
| return InsertedCFIInstr; |
| } |
| |
| void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred, |
| const MBBCFAInfo &Succ) { |
| errs() << "*** Inconsistent CFA register and/or offset between pred and succ " |
| "***\n"; |
| errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() |
| << " in " << Pred.MBB->getParent()->getName() |
| << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n"; |
| errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() |
| << " in " << Pred.MBB->getParent()->getName() |
| << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n"; |
| errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() |
| << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n"; |
| errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() |
| << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n"; |
| } |
| |
| void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred, |
| const MBBCFAInfo &Succ) { |
| errs() << "*** Inconsistent CSR Saved between pred and succ in function " |
| << Pred.MBB->getParent()->getName() << " ***\n"; |
| errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber() |
| << " outgoing CSR Saved: "; |
| for (int Reg : Pred.OutgoingCSRSaved.set_bits()) |
| errs() << Reg << " "; |
| errs() << "\n"; |
| errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber() |
| << " incoming CSR Saved: "; |
| for (int Reg : Succ.IncomingCSRSaved.set_bits()) |
| errs() << Reg << " "; |
| errs() << "\n"; |
| } |
| |
| unsigned CFIInstrInserter::verify(MachineFunction &MF) { |
| unsigned ErrorNum = 0; |
| for (auto *CurrMBB : depth_first(&MF)) { |
| const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()]; |
| for (MachineBasicBlock *Succ : CurrMBB->successors()) { |
| const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()]; |
| // Check that incoming offset and register values of successors match the |
| // outgoing offset and register values of CurrMBB |
| if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset || |
| SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) { |
| // Inconsistent offsets/registers are ok for 'noreturn' blocks because |
| // we don't generate epilogues inside such blocks. |
| if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock()) |
| continue; |
| reportCFAError(CurrMBBInfo, SuccMBBInfo); |
| ErrorNum++; |
| } |
| // Check that IncomingCSRSaved of every successor matches the |
| // OutgoingCSRSaved of CurrMBB |
| if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) { |
| reportCSRError(CurrMBBInfo, SuccMBBInfo); |
| ErrorNum++; |
| } |
| } |
| } |
| return ErrorNum; |
| } |