181ad6265SDimitry Andric //===------ CFIFixup.cpp - Insert CFI remember/restore instructions -------===//
281ad6265SDimitry Andric //
381ad6265SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
481ad6265SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
581ad6265SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
681ad6265SDimitry Andric //
781ad6265SDimitry Andric //===----------------------------------------------------------------------===//
881ad6265SDimitry Andric //
981ad6265SDimitry Andric
1081ad6265SDimitry Andric // This pass inserts the necessary instructions to adjust for the inconsistency
1181ad6265SDimitry Andric // of the call-frame information caused by final machine basic block layout.
1281ad6265SDimitry Andric // The pass relies in constraints LLVM imposes on the placement of
13*5f757f3fSDimitry Andric // save/restore points (cf. ShrinkWrap) and has certain preconditions about
14*5f757f3fSDimitry Andric // placement of CFI instructions:
15*5f757f3fSDimitry Andric // * For any two CFI instructions of the function prologue one dominates
16*5f757f3fSDimitry Andric // and is post-dominated by the other.
17*5f757f3fSDimitry Andric // * The function possibly contains multiple epilogue blocks, where each
18*5f757f3fSDimitry Andric // epilogue block is complete and self-contained, i.e. CSR restore
19*5f757f3fSDimitry Andric // instructions (and the corresponding CFI instructions)
20*5f757f3fSDimitry Andric // are not split across two or more blocks.
21*5f757f3fSDimitry Andric // * CFI instructions are not contained in any loops.
22*5f757f3fSDimitry Andric
23*5f757f3fSDimitry Andric // Thus, during execution, at the beginning and at the end of each basic block,
24*5f757f3fSDimitry Andric // following the prologue, the function can be in one of two states:
2581ad6265SDimitry Andric // - "has a call frame", if the function has executed the prologue, and
2681ad6265SDimitry Andric // has not executed any epilogue
2781ad6265SDimitry Andric // - "does not have a call frame", if the function has not executed the
2881ad6265SDimitry Andric // prologue, or has executed an epilogue
2981ad6265SDimitry Andric // which can be computed by a single RPO traversal.
3081ad6265SDimitry Andric
31*5f757f3fSDimitry Andric // The location of the prologue is determined by finding the first block in the
32*5f757f3fSDimitry Andric // reverse traversal which contains CFI instructions.
33*5f757f3fSDimitry Andric
3481ad6265SDimitry Andric // In order to accommodate backends which do not generate unwind info in
3581ad6265SDimitry Andric // epilogues we compute an additional property "strong no call frame on entry",
3681ad6265SDimitry Andric // which is set for the entry point of the function and for every block
3781ad6265SDimitry Andric // reachable from the entry along a path that does not execute the prologue. If
3881ad6265SDimitry Andric // this property holds, it takes precedence over the "has a call frame"
3981ad6265SDimitry Andric // property.
4081ad6265SDimitry Andric
4181ad6265SDimitry Andric // From the point of view of the unwind tables, the "has/does not have call
4281ad6265SDimitry Andric // frame" state at beginning of each block is determined by the state at the end
4381ad6265SDimitry Andric // of the previous block, in layout order. Where these states differ, we insert
4481ad6265SDimitry Andric // compensating CFI instructions, which come in two flavours:
4581ad6265SDimitry Andric
4681ad6265SDimitry Andric // - CFI instructions, which reset the unwind table state to the initial one.
4781ad6265SDimitry Andric // This is done by a target specific hook and is expected to be trivial
4881ad6265SDimitry Andric // to implement, for example it could be:
4981ad6265SDimitry Andric // .cfi_def_cfa <sp>, 0
5081ad6265SDimitry Andric // .cfi_same_value <rN>
5181ad6265SDimitry Andric // .cfi_same_value <rN-1>
5281ad6265SDimitry Andric // ...
5381ad6265SDimitry Andric // where <rN> are the callee-saved registers.
5481ad6265SDimitry Andric // - CFI instructions, which reset the unwind table state to the one
5581ad6265SDimitry Andric // created by the function prologue. These are
5681ad6265SDimitry Andric // .cfi_restore_state
5781ad6265SDimitry Andric // .cfi_remember_state
5881ad6265SDimitry Andric // In this case we also insert a `.cfi_remember_state` after the last CFI
5981ad6265SDimitry Andric // instruction in the function prologue.
6081ad6265SDimitry Andric //
6181ad6265SDimitry Andric // Known limitations:
6281ad6265SDimitry Andric // * the pass cannot handle an epilogue preceding the prologue in the basic
6381ad6265SDimitry Andric // block layout
6481ad6265SDimitry Andric // * the pass does not handle functions where SP is used as a frame pointer and
6581ad6265SDimitry Andric // SP adjustments up and down are done in different basic blocks (TODO)
6681ad6265SDimitry Andric //===----------------------------------------------------------------------===//
6781ad6265SDimitry Andric
6881ad6265SDimitry Andric #include "llvm/CodeGen/CFIFixup.h"
6981ad6265SDimitry Andric
7081ad6265SDimitry Andric #include "llvm/ADT/PostOrderIterator.h"
7181ad6265SDimitry Andric #include "llvm/ADT/SmallBitVector.h"
7281ad6265SDimitry Andric #include "llvm/CodeGen/Passes.h"
7381ad6265SDimitry Andric #include "llvm/CodeGen/TargetFrameLowering.h"
7481ad6265SDimitry Andric #include "llvm/CodeGen/TargetInstrInfo.h"
7581ad6265SDimitry Andric #include "llvm/CodeGen/TargetSubtargetInfo.h"
7681ad6265SDimitry Andric #include "llvm/MC/MCAsmInfo.h"
7781ad6265SDimitry Andric #include "llvm/MC/MCDwarf.h"
7881ad6265SDimitry Andric #include "llvm/Target/TargetMachine.h"
7981ad6265SDimitry Andric
8081ad6265SDimitry Andric using namespace llvm;
8181ad6265SDimitry Andric
8281ad6265SDimitry Andric #define DEBUG_TYPE "cfi-fixup"
8381ad6265SDimitry Andric
8481ad6265SDimitry Andric char CFIFixup::ID = 0;
8581ad6265SDimitry Andric
8681ad6265SDimitry Andric INITIALIZE_PASS(CFIFixup, "cfi-fixup",
8781ad6265SDimitry Andric "Insert CFI remember/restore state instructions", false, false)
createCFIFixup()8881ad6265SDimitry Andric FunctionPass *llvm::createCFIFixup() { return new CFIFixup(); }
8981ad6265SDimitry Andric
isPrologueCFIInstruction(const MachineInstr & MI)9081ad6265SDimitry Andric static bool isPrologueCFIInstruction(const MachineInstr &MI) {
9181ad6265SDimitry Andric return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
9281ad6265SDimitry Andric MI.getFlag(MachineInstr::FrameSetup);
9381ad6265SDimitry Andric }
9481ad6265SDimitry Andric
containsEpilogue(const MachineBasicBlock & MBB)9581ad6265SDimitry Andric static bool containsEpilogue(const MachineBasicBlock &MBB) {
9681ad6265SDimitry Andric return llvm::any_of(llvm::reverse(MBB), [](const auto &MI) {
9781ad6265SDimitry Andric return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
9881ad6265SDimitry Andric MI.getFlag(MachineInstr::FrameDestroy);
9981ad6265SDimitry Andric });
10081ad6265SDimitry Andric }
10181ad6265SDimitry Andric
102*5f757f3fSDimitry Andric static MachineBasicBlock *
findPrologueEnd(MachineFunction & MF,MachineBasicBlock::iterator & PrologueEnd)103*5f757f3fSDimitry Andric findPrologueEnd(MachineFunction &MF, MachineBasicBlock::iterator &PrologueEnd) {
104*5f757f3fSDimitry Andric // Even though we should theoretically traverse the blocks in post-order, we
105*5f757f3fSDimitry Andric // can't encode correctly cases where prologue blocks are not laid out in
106*5f757f3fSDimitry Andric // topological order. Then, assuming topological order, we can just traverse
107*5f757f3fSDimitry Andric // the function in reverse.
108*5f757f3fSDimitry Andric for (MachineBasicBlock &MBB : reverse(MF)) {
109*5f757f3fSDimitry Andric for (MachineInstr &MI : reverse(MBB.instrs())) {
110*5f757f3fSDimitry Andric if (!isPrologueCFIInstruction(MI))
111*5f757f3fSDimitry Andric continue;
112*5f757f3fSDimitry Andric PrologueEnd = std::next(MI.getIterator());
113*5f757f3fSDimitry Andric return &MBB;
114*5f757f3fSDimitry Andric }
115*5f757f3fSDimitry Andric }
116*5f757f3fSDimitry Andric return nullptr;
117*5f757f3fSDimitry Andric }
118*5f757f3fSDimitry Andric
runOnMachineFunction(MachineFunction & MF)11981ad6265SDimitry Andric bool CFIFixup::runOnMachineFunction(MachineFunction &MF) {
12081ad6265SDimitry Andric const TargetFrameLowering &TFL = *MF.getSubtarget().getFrameLowering();
12181ad6265SDimitry Andric if (!TFL.enableCFIFixup(MF))
12281ad6265SDimitry Andric return false;
12381ad6265SDimitry Andric
12481ad6265SDimitry Andric const unsigned NumBlocks = MF.getNumBlockIDs();
12581ad6265SDimitry Andric if (NumBlocks < 2)
12681ad6265SDimitry Andric return false;
12781ad6265SDimitry Andric
128*5f757f3fSDimitry Andric // Find the prologue and the point where we can issue the first
129*5f757f3fSDimitry Andric // `.cfi_remember_state`.
130*5f757f3fSDimitry Andric MachineBasicBlock::iterator PrologueEnd;
131*5f757f3fSDimitry Andric MachineBasicBlock *PrologueBlock = findPrologueEnd(MF, PrologueEnd);
132*5f757f3fSDimitry Andric if (PrologueBlock == nullptr)
133*5f757f3fSDimitry Andric return false;
134*5f757f3fSDimitry Andric
13581ad6265SDimitry Andric struct BlockFlags {
13681ad6265SDimitry Andric bool Reachable : 1;
13781ad6265SDimitry Andric bool StrongNoFrameOnEntry : 1;
13881ad6265SDimitry Andric bool HasFrameOnEntry : 1;
13981ad6265SDimitry Andric bool HasFrameOnExit : 1;
14081ad6265SDimitry Andric };
14181ad6265SDimitry Andric SmallVector<BlockFlags, 32> BlockInfo(NumBlocks, {false, false, false, false});
14281ad6265SDimitry Andric BlockInfo[0].Reachable = true;
14381ad6265SDimitry Andric BlockInfo[0].StrongNoFrameOnEntry = true;
14481ad6265SDimitry Andric
14581ad6265SDimitry Andric // Compute the presence/absence of frame at each basic block.
14681ad6265SDimitry Andric ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
14781ad6265SDimitry Andric for (MachineBasicBlock *MBB : RPOT) {
14881ad6265SDimitry Andric BlockFlags &Info = BlockInfo[MBB->getNumber()];
14981ad6265SDimitry Andric
15081ad6265SDimitry Andric // Set to true if the current block contains the prologue or the epilogue,
15181ad6265SDimitry Andric // respectively.
152*5f757f3fSDimitry Andric bool HasPrologue = MBB == PrologueBlock;
15381ad6265SDimitry Andric bool HasEpilogue = false;
15481ad6265SDimitry Andric
15581ad6265SDimitry Andric if (Info.HasFrameOnEntry || HasPrologue)
15681ad6265SDimitry Andric HasEpilogue = containsEpilogue(*MBB);
15781ad6265SDimitry Andric
15881ad6265SDimitry Andric // If the function has a call frame at the entry of the current block or the
15981ad6265SDimitry Andric // current block contains the prologue, then the function has a call frame
16081ad6265SDimitry Andric // at the exit of the block, unless the block contains the epilogue.
16181ad6265SDimitry Andric Info.HasFrameOnExit = (Info.HasFrameOnEntry || HasPrologue) && !HasEpilogue;
16281ad6265SDimitry Andric
16381ad6265SDimitry Andric // Set the successors' state on entry.
16481ad6265SDimitry Andric for (MachineBasicBlock *Succ : MBB->successors()) {
16581ad6265SDimitry Andric BlockFlags &SuccInfo = BlockInfo[Succ->getNumber()];
16681ad6265SDimitry Andric SuccInfo.Reachable = true;
16781ad6265SDimitry Andric SuccInfo.StrongNoFrameOnEntry |=
16881ad6265SDimitry Andric Info.StrongNoFrameOnEntry && !HasPrologue;
16981ad6265SDimitry Andric SuccInfo.HasFrameOnEntry = Info.HasFrameOnExit;
17081ad6265SDimitry Andric }
17181ad6265SDimitry Andric }
17281ad6265SDimitry Andric
17381ad6265SDimitry Andric // Walk the blocks of the function in "physical" order.
17481ad6265SDimitry Andric // Every block inherits the frame state (as recorded in the unwind tables)
17581ad6265SDimitry Andric // of the previous block. If the intended frame state is different, insert
17681ad6265SDimitry Andric // compensating CFI instructions.
17781ad6265SDimitry Andric const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
17881ad6265SDimitry Andric bool Change = false;
17981ad6265SDimitry Andric // `InsertPt` always points to the point in a preceding block where we have to
18081ad6265SDimitry Andric // insert a `.cfi_remember_state`, in the case that the current block needs a
18181ad6265SDimitry Andric // `.cfi_restore_state`.
18281ad6265SDimitry Andric MachineBasicBlock *InsertMBB = PrologueBlock;
183*5f757f3fSDimitry Andric MachineBasicBlock::iterator InsertPt = PrologueEnd;
18481ad6265SDimitry Andric
18581ad6265SDimitry Andric assert(InsertPt != PrologueBlock->begin() &&
18681ad6265SDimitry Andric "Inconsistent notion of \"prologue block\"");
18781ad6265SDimitry Andric
18881ad6265SDimitry Andric // No point starting before the prologue block.
18981ad6265SDimitry Andric // TODO: the unwind tables will still be incorrect if an epilogue physically
19081ad6265SDimitry Andric // preceeds the prologue.
19181ad6265SDimitry Andric MachineFunction::iterator CurrBB = std::next(PrologueBlock->getIterator());
19281ad6265SDimitry Andric bool HasFrame = BlockInfo[PrologueBlock->getNumber()].HasFrameOnExit;
19381ad6265SDimitry Andric while (CurrBB != MF.end()) {
19481ad6265SDimitry Andric const BlockFlags &Info = BlockInfo[CurrBB->getNumber()];
19581ad6265SDimitry Andric if (!Info.Reachable) {
19681ad6265SDimitry Andric ++CurrBB;
19781ad6265SDimitry Andric continue;
19881ad6265SDimitry Andric }
19981ad6265SDimitry Andric
20081ad6265SDimitry Andric #ifndef NDEBUG
20181ad6265SDimitry Andric if (!Info.StrongNoFrameOnEntry) {
20281ad6265SDimitry Andric for (auto *Pred : CurrBB->predecessors()) {
20381ad6265SDimitry Andric BlockFlags &PredInfo = BlockInfo[Pred->getNumber()];
20481ad6265SDimitry Andric assert((!PredInfo.Reachable ||
20581ad6265SDimitry Andric Info.HasFrameOnEntry == PredInfo.HasFrameOnExit) &&
20681ad6265SDimitry Andric "Inconsistent call frame state");
20781ad6265SDimitry Andric }
20881ad6265SDimitry Andric }
20981ad6265SDimitry Andric #endif
21081ad6265SDimitry Andric if (!Info.StrongNoFrameOnEntry && Info.HasFrameOnEntry && !HasFrame) {
21181ad6265SDimitry Andric // Reset to the "after prologue" state.
21281ad6265SDimitry Andric
21381ad6265SDimitry Andric // Insert a `.cfi_remember_state` into the last block known to have a
21481ad6265SDimitry Andric // stack frame.
21581ad6265SDimitry Andric unsigned CFIIndex =
21681ad6265SDimitry Andric MF.addFrameInst(MCCFIInstruction::createRememberState(nullptr));
21781ad6265SDimitry Andric BuildMI(*InsertMBB, InsertPt, DebugLoc(),
21881ad6265SDimitry Andric TII.get(TargetOpcode::CFI_INSTRUCTION))
21981ad6265SDimitry Andric .addCFIIndex(CFIIndex);
22081ad6265SDimitry Andric // Insert a `.cfi_restore_state` at the beginning of the current block.
22181ad6265SDimitry Andric CFIIndex = MF.addFrameInst(MCCFIInstruction::createRestoreState(nullptr));
22281ad6265SDimitry Andric InsertPt = BuildMI(*CurrBB, CurrBB->begin(), DebugLoc(),
22381ad6265SDimitry Andric TII.get(TargetOpcode::CFI_INSTRUCTION))
22481ad6265SDimitry Andric .addCFIIndex(CFIIndex);
22581ad6265SDimitry Andric ++InsertPt;
22681ad6265SDimitry Andric InsertMBB = &*CurrBB;
22781ad6265SDimitry Andric Change = true;
22881ad6265SDimitry Andric } else if ((Info.StrongNoFrameOnEntry || !Info.HasFrameOnEntry) &&
22981ad6265SDimitry Andric HasFrame) {
23081ad6265SDimitry Andric // Reset to the state upon function entry.
23181ad6265SDimitry Andric TFL.resetCFIToInitialState(*CurrBB);
23281ad6265SDimitry Andric Change = true;
23381ad6265SDimitry Andric }
23481ad6265SDimitry Andric
23581ad6265SDimitry Andric HasFrame = Info.HasFrameOnExit;
23681ad6265SDimitry Andric ++CurrBB;
23781ad6265SDimitry Andric }
23881ad6265SDimitry Andric
23981ad6265SDimitry Andric return Change;
24081ad6265SDimitry Andric }
241