345 lines · cpp
1//===------ CFIFixup.cpp - Insert CFI remember/restore 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 10// This pass inserts the necessary instructions to adjust for the inconsistency11// of the call-frame information caused by final machine basic block layout.12// The pass relies in constraints LLVM imposes on the placement of13// save/restore points (cf. ShrinkWrap) and has certain preconditions about14// placement of CFI instructions:15// * For any two CFI instructions of the function prologue one dominates16// and is post-dominated by the other.17// * The function possibly contains multiple epilogue blocks, where each18// epilogue block is complete and self-contained, i.e. CSR restore19// instructions (and the corresponding CFI instructions)20// are not split across two or more blocks.21// * CFI instructions are not contained in any loops.22 23// Thus, during execution, at the beginning and at the end of each basic block,24// following the prologue, the function can be in one of two states:25// - "has a call frame", if the function has executed the prologue, and26// has not executed any epilogue27// - "does not have a call frame", if the function has not executed the28// prologue, or has executed an epilogue29// which can be computed by a single RPO traversal.30 31// The location of the prologue is determined by finding the first block in the32// reverse traversal which contains CFI instructions.33 34// In order to accommodate backends which do not generate unwind info in35// epilogues we compute an additional property "strong no call frame on entry",36// which is set for the entry point of the function and for every block37// reachable from the entry along a path that does not execute the prologue. If38// this property holds, it takes precedence over the "has a call frame"39// property.40 41// From the point of view of the unwind tables, the "has/does not have call42// frame" state at beginning of each block is determined by the state at the end43// of the previous block, in layout order. Where these states differ, we insert44// compensating CFI instructions, which come in two flavours:45 46// - CFI instructions, which reset the unwind table state to the initial one.47// This is done by a target specific hook and is expected to be trivial48// to implement, for example it could be:49// .cfi_def_cfa <sp>, 050// .cfi_same_value <rN>51// .cfi_same_value <rN-1>52// ...53// where <rN> are the callee-saved registers.54// - CFI instructions, which reset the unwind table state to the one55// created by the function prologue. These are56// .cfi_restore_state57// .cfi_remember_state58// In this case we also insert a `.cfi_remember_state` after the last CFI59// instruction in the function prologue.60//61// Known limitations:62// * the pass cannot handle an epilogue preceding the prologue in the basic63// block layout64// * the pass does not handle functions where SP is used as a frame pointer and65// SP adjustments up and down are done in different basic blocks (TODO)66//===----------------------------------------------------------------------===//67 68#include "llvm/CodeGen/CFIFixup.h"69 70#include "llvm/ADT/DenseMap.h"71#include "llvm/ADT/PostOrderIterator.h"72#include "llvm/ADT/STLExtras.h"73#include "llvm/ADT/SmallVector.h"74#include "llvm/ADT/iterator_range.h"75#include "llvm/CodeGen/MachineBasicBlock.h"76#include "llvm/CodeGen/MachineFunction.h"77#include "llvm/CodeGen/Passes.h"78#include "llvm/CodeGen/TargetFrameLowering.h"79#include "llvm/CodeGen/TargetInstrInfo.h"80#include "llvm/CodeGen/TargetSubtargetInfo.h"81#include "llvm/MC/MCAsmInfo.h"82#include "llvm/MC/MCDwarf.h"83#include "llvm/Target/TargetMachine.h"84 85#include <iterator>86 87using namespace llvm;88 89#define DEBUG_TYPE "cfi-fixup"90 91char CFIFixup::ID = 0;92 93INITIALIZE_PASS(CFIFixup, "cfi-fixup",94 "Insert CFI remember/restore state instructions", false, false)95FunctionPass *llvm::createCFIFixup() { return new CFIFixup(); }96 97static bool isPrologueCFIInstruction(const MachineInstr &MI) {98 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&99 MI.getFlag(MachineInstr::FrameSetup);100}101 102static bool containsEpilogue(const MachineBasicBlock &MBB) {103 return llvm::any_of(llvm::reverse(MBB), [](const auto &MI) {104 return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&105 MI.getFlag(MachineInstr::FrameDestroy);106 });107}108 109static MachineBasicBlock *110findPrologueEnd(MachineFunction &MF, MachineBasicBlock::iterator &PrologueEnd) {111 // Even though we should theoretically traverse the blocks in post-order, we112 // can't encode correctly cases where prologue blocks are not laid out in113 // topological order. Then, assuming topological order, we can just traverse114 // the function in reverse.115 for (MachineBasicBlock &MBB : reverse(MF)) {116 for (MachineInstr &MI : reverse(MBB.instrs())) {117 if (!isPrologueCFIInstruction(MI))118 continue;119 PrologueEnd = std::next(MI.getIterator());120 return &MBB;121 }122 }123 return nullptr;124}125 126// Represents a basic block's relationship to the call frame. This metadata127// reflects what the state *should* be, which may differ from the actual state128// after final machine basic block layout.129struct BlockFlags {130 bool Reachable : 1;131 bool StrongNoFrameOnEntry : 1;132 bool HasFrameOnEntry : 1;133 bool HasFrameOnExit : 1;134 BlockFlags()135 : Reachable(false), StrongNoFrameOnEntry(false), HasFrameOnEntry(false),136 HasFrameOnExit(false) {}137};138 139// Most functions will have <= 32 basic blocks.140using BlockFlagsVector = SmallVector<BlockFlags, 32>;141 142// Computes the frame information for each block in the function. Frame info143// for a block is inferred from its predecessors.144static BlockFlagsVector145computeBlockInfo(const MachineFunction &MF,146 const MachineBasicBlock *PrologueBlock) {147 BlockFlagsVector BlockInfo(MF.getNumBlockIDs());148 BlockInfo[0].Reachable = true;149 BlockInfo[0].StrongNoFrameOnEntry = true;150 151 // Compute the presence/absence of frame at each basic block.152 ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(&*MF.begin());153 for (const MachineBasicBlock *MBB : RPOT) {154 BlockFlags &Info = BlockInfo[MBB->getNumber()];155 156 // Set to true if the current block contains the prologue or the epilogue,157 // respectively.158 bool HasPrologue = MBB == PrologueBlock;159 bool HasEpilogue = false;160 161 if (Info.HasFrameOnEntry || HasPrologue)162 HasEpilogue = containsEpilogue(*MBB);163 164 // If the function has a call frame at the entry of the current block or the165 // current block contains the prologue, then the function has a call frame166 // at the exit of the block, unless the block contains the epilogue.167 Info.HasFrameOnExit = (Info.HasFrameOnEntry || HasPrologue) && !HasEpilogue;168 169 // Set the successors' state on entry.170 for (MachineBasicBlock *Succ : MBB->successors()) {171 BlockFlags &SuccInfo = BlockInfo[Succ->getNumber()];172 SuccInfo.Reachable = true;173 SuccInfo.StrongNoFrameOnEntry |=174 Info.StrongNoFrameOnEntry && !HasPrologue;175 SuccInfo.HasFrameOnEntry = Info.HasFrameOnExit;176 }177 }178 179 return BlockInfo;180}181 182// Represents the point within a basic block where we can insert an instruction.183// Note that we need the MachineBasicBlock* as well as the iterator since the184// iterator can point to the end of the block. Instructions are inserted185// *before* the iterator.186struct InsertionPoint {187 MachineBasicBlock *MBB = nullptr;188 MachineBasicBlock::iterator Iterator;189};190 191// Inserts a `.cfi_remember_state` instruction before PrologueEnd and a192// `.cfi_restore_state` instruction before DstInsertPt. Returns an iterator193// to the first instruction after the inserted `.cfi_restore_state` instruction.194static InsertionPoint195insertRememberRestorePair(const InsertionPoint &RememberInsertPt,196 const InsertionPoint &RestoreInsertPt) {197 MachineFunction &MF = *RememberInsertPt.MBB->getParent();198 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();199 200 // Insert the `.cfi_remember_state` instruction.201 unsigned CFIIndex =202 MF.addFrameInst(MCCFIInstruction::createRememberState(nullptr));203 BuildMI(*RememberInsertPt.MBB, RememberInsertPt.Iterator, DebugLoc(),204 TII.get(TargetOpcode::CFI_INSTRUCTION))205 .addCFIIndex(CFIIndex);206 207 // Insert the `.cfi_restore_state` instruction.208 CFIIndex = MF.addFrameInst(MCCFIInstruction::createRestoreState(nullptr));209 210 return {RestoreInsertPt.MBB,211 std::next(BuildMI(*RestoreInsertPt.MBB, RestoreInsertPt.Iterator,212 DebugLoc(), TII.get(TargetOpcode::CFI_INSTRUCTION))213 .addCFIIndex(CFIIndex)214 ->getIterator())};215}216 217// Copies all CFI instructions before PrologueEnd and inserts them before218// DstInsertPt. Returns the iterator to the first instruction after the219// inserted instructions.220static InsertionPoint cloneCfiPrologue(const InsertionPoint &PrologueEnd,221 const InsertionPoint &DstInsertPt) {222 MachineFunction &MF = *DstInsertPt.MBB->getParent();223 224 auto cloneCfiInstructions = [&](MachineBasicBlock::iterator Begin,225 MachineBasicBlock::iterator End) {226 auto ToClone = map_range(227 make_filter_range(make_range(Begin, End), isPrologueCFIInstruction),228 [&](const MachineInstr &MI) { return MF.CloneMachineInstr(&MI); });229 DstInsertPt.MBB->insert(DstInsertPt.Iterator, ToClone.begin(),230 ToClone.end());231 };232 233 // Clone all CFI instructions from previous blocks.234 for (auto &MBB : make_range(MF.begin(), PrologueEnd.MBB->getIterator()))235 cloneCfiInstructions(MBB.begin(), MBB.end());236 // Clone all CFI instructions from the final prologue block.237 cloneCfiInstructions(PrologueEnd.MBB->begin(), PrologueEnd.Iterator);238 return DstInsertPt;239}240 241// Fixes up the CFI instructions in a basic block to be consistent with the242// intended frame state, adding or removing CFI instructions as necessary.243// Returns true if a change was made and false otherwise.244static bool245fixupBlock(MachineBasicBlock &CurrBB, const BlockFlagsVector &BlockInfo,246 SmallDenseMap<MBBSectionID, InsertionPoint> &InsertionPts,247 const InsertionPoint &Prologue) {248 const MachineFunction &MF = *CurrBB.getParent();249 const TargetFrameLowering &TFL = *MF.getSubtarget().getFrameLowering();250 const BlockFlags &Info = BlockInfo[CurrBB.getNumber()];251 252 if (!Info.Reachable)253 return false;254 255 // If we don't need to perform full CFI fix up, we only need to fix up the256 // first basic block in the section.257 if (!TFL.enableFullCFIFixup(MF) && !CurrBB.isBeginSection())258 return false;259 260 // If the previous block and the current block are in the same section,261 // the frame info will propagate from the previous block to the current one.262 const BlockFlags &PrevInfo =263 BlockInfo[std::prev(CurrBB.getIterator())->getNumber()];264 bool HasFrame = PrevInfo.HasFrameOnExit && !CurrBB.isBeginSection();265 bool NeedsFrame = Info.HasFrameOnEntry && !Info.StrongNoFrameOnEntry;266 267#ifndef NDEBUG268 if (!Info.StrongNoFrameOnEntry) {269 for (auto *Pred : CurrBB.predecessors()) {270 const BlockFlags &PredInfo = BlockInfo[Pred->getNumber()];271 assert((!PredInfo.Reachable ||272 Info.HasFrameOnEntry == PredInfo.HasFrameOnExit) &&273 "Inconsistent call frame state");274 }275 }276#endif277 278 if (HasFrame == NeedsFrame)279 return false;280 281 if (!NeedsFrame) {282 // Reset to the state upon function entry.283 TFL.resetCFIToInitialState(CurrBB);284 return true;285 }286 287 // Reset to the "after prologue" state.288 InsertionPoint &InsertPt = InsertionPts[CurrBB.getSectionID()];289 if (InsertPt.MBB == nullptr) {290 // CurBB is the first block in its section, so there is no "after291 // prologue" state. Clone the CFI instructions from the prologue block292 // to create it.293 InsertPt = cloneCfiPrologue(Prologue, {&CurrBB, CurrBB.begin()});294 } else {295 // There's an earlier block known to have a stack frame. Insert a296 // `.cfi_remember_state` instruction into that block and a297 // `.cfi_restore_state` instruction at the beginning of the current298 // block.299 InsertPt = insertRememberRestorePair(InsertPt, {&CurrBB, CurrBB.begin()});300 }301 return true;302}303 304bool CFIFixup::runOnMachineFunction(MachineFunction &MF) {305 if (!MF.getSubtarget().getFrameLowering()->enableCFIFixup(MF))306 return false;307 308 if (MF.getNumBlockIDs() < 2)309 return false;310 311 // Find the prologue and the point where we can issue the first312 // `.cfi_remember_state`.313 MachineBasicBlock::iterator PrologueEnd;314 MachineBasicBlock *PrologueBlock = findPrologueEnd(MF, PrologueEnd);315 if (PrologueBlock == nullptr)316 return false;317 318 BlockFlagsVector BlockInfo = computeBlockInfo(MF, PrologueBlock);319 320 // Walk the blocks of the function in "physical" order.321 // Every block inherits the frame state (as recorded in the unwind tables)322 // of the previous block. If the intended frame state is different, insert323 // compensating CFI instructions.324 bool Change = false;325 // `InsertPt[sectionID]` always points to the point in a preceding block where326 // we have to insert a `.cfi_remember_state`, in the case that the current327 // block needs a `.cfi_restore_state`.328 SmallDenseMap<MBBSectionID, InsertionPoint> InsertionPts;329 InsertionPts[PrologueBlock->getSectionID()] = {PrologueBlock, PrologueEnd};330 331 assert(PrologueEnd != PrologueBlock->begin() &&332 "Inconsistent notion of \"prologue block\"");333 334 // No point starting before the prologue block.335 // TODO: the unwind tables will still be incorrect if an epilogue physically336 // preceeds the prologue.337 for (MachineBasicBlock &MBB :338 make_range(std::next(PrologueBlock->getIterator()), MF.end())) {339 Change |=340 fixupBlock(MBB, BlockInfo, InsertionPts, {PrologueBlock, PrologueEnd});341 }342 343 return Change;344}345