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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 
10 // This pass inserts the necessary  instructions to adjust for the inconsistency
11 // of the call-frame information caused by final machine basic block layout.
12 // The pass relies in constraints LLVM imposes on the placement of
13 // save/restore points (cf. ShrinkWrap):
14 // * there is a single basic block, containing the function prologue
15 // * possibly multiple epilogue blocks, where each epilogue block is
16 //   complete and self-contained, i.e. CSR restore instructions (and the
17 //   corresponding CFI instructions are not split across two or more blocks.
18 // * prologue and epilogue blocks are outside of any loops
19 // Thus, during execution, at the beginning and at the end of each basic block
20 // the function can be in one of two states:
21 //  - "has a call frame", if the function has executed the prologue, and
22 //    has not executed any epilogue
23 //  - "does not have a call frame", if the function has not executed the
24 //    prologue, or has executed an epilogue
25 // which can be computed by a single RPO traversal.
26 
27 // In order to accommodate backends which do not generate unwind info in
28 // epilogues we compute an additional property "strong no call frame on entry",
29 // which is set for the entry point of the function and for every block
30 // reachable from the entry along a path that does not execute the prologue. If
31 // this property holds, it takes precedence over the "has a call frame"
32 // property.
33 
34 // From the point of view of the unwind tables, the "has/does not have call
35 // frame" state at beginning of each block is determined by the state at the end
36 // of the previous block, in layout order. Where these states differ, we insert
37 // compensating CFI instructions, which come in two flavours:
38 
39 //   - CFI instructions, which reset the unwind table state to the initial one.
40 //     This is done by a target specific hook and is expected to be trivial
41 //     to implement, for example it could be:
42 //       .cfi_def_cfa <sp>, 0
43 //       .cfi_same_value <rN>
44 //       .cfi_same_value <rN-1>
45 //       ...
46 //     where <rN> are the callee-saved registers.
47 //   - CFI instructions, which reset the unwind table state to the one
48 //     created by the function prologue. These are
49 //       .cfi_restore_state
50 //       .cfi_remember_state
51 //     In this case we also insert a `.cfi_remember_state` after the last CFI
52 //     instruction in the function prologue.
53 //
54 // Known limitations:
55 //  * the pass cannot handle an epilogue preceding the prologue in the basic
56 //    block layout
57 //  * the pass does not handle functions where SP is used as a frame pointer and
58 //    SP adjustments up and down are done in different basic blocks (TODO)
59 //===----------------------------------------------------------------------===//
60 
61 #include "llvm/CodeGen/CFIFixup.h"
62 
63 #include "llvm/ADT/PostOrderIterator.h"
64 #include "llvm/ADT/SmallBitVector.h"
65 #include "llvm/CodeGen/Passes.h"
66 #include "llvm/CodeGen/TargetFrameLowering.h"
67 #include "llvm/CodeGen/TargetInstrInfo.h"
68 #include "llvm/CodeGen/TargetSubtargetInfo.h"
69 #include "llvm/MC/MCAsmInfo.h"
70 #include "llvm/MC/MCDwarf.h"
71 #include "llvm/Target/TargetMachine.h"
72 
73 using namespace llvm;
74 
75 #define DEBUG_TYPE "cfi-fixup"
76 
77 char CFIFixup::ID = 0;
78 
79 INITIALIZE_PASS(CFIFixup, "cfi-fixup",
80                 "Insert CFI remember/restore state instructions", false, false)
81 FunctionPass *llvm::createCFIFixup() { return new CFIFixup(); }
82 
83 static bool isPrologueCFIInstruction(const MachineInstr &MI) {
84   return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
85          MI.getFlag(MachineInstr::FrameSetup);
86 }
87 
88 static bool containsPrologue(const MachineBasicBlock &MBB) {
89   return llvm::any_of(MBB.instrs(), isPrologueCFIInstruction);
90 }
91 
92 static bool containsEpilogue(const MachineBasicBlock &MBB) {
93   return llvm::any_of(llvm::reverse(MBB), [](const auto &MI) {
94     return MI.getOpcode() == TargetOpcode::CFI_INSTRUCTION &&
95            MI.getFlag(MachineInstr::FrameDestroy);
96   });
97 }
98 
99 bool CFIFixup::runOnMachineFunction(MachineFunction &MF) {
100   const TargetFrameLowering &TFL = *MF.getSubtarget().getFrameLowering();
101   if (!TFL.enableCFIFixup(MF))
102     return false;
103 
104   const unsigned NumBlocks = MF.getNumBlockIDs();
105   if (NumBlocks < 2)
106     return false;
107 
108   struct BlockFlags {
109     bool StrongNoFrameOnEntry : 1;
110     bool HasFrameOnEntry : 1;
111     bool HasFrameOnExit : 1;
112   };
113   SmallVector<BlockFlags, 32> BlockInfo(NumBlocks, {false, false, false});
114   BlockInfo[0].StrongNoFrameOnEntry = true;
115 
116   // Compute the presence/absence of frame at each basic block.
117   MachineBasicBlock *PrologueBlock = nullptr;
118   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
119   for (MachineBasicBlock *MBB : RPOT) {
120     BlockFlags &Info = BlockInfo[MBB->getNumber()];
121 
122     // Set to true if the current block contains the prologue or the epilogue,
123     // respectively.
124     bool HasPrologue = false;
125     bool HasEpilogue = false;
126 
127     if (!PrologueBlock && !Info.HasFrameOnEntry && containsPrologue(*MBB)) {
128       PrologueBlock = MBB;
129       HasPrologue = true;
130     }
131 
132     if (Info.HasFrameOnEntry || HasPrologue)
133       HasEpilogue = containsEpilogue(*MBB);
134 
135     // If the function has a call frame at the entry of the current block or the
136     // current block contains the prologue, then the function has a call frame
137     // at the exit of the block, unless the block contains the epilogue.
138     Info.HasFrameOnExit = (Info.HasFrameOnEntry || HasPrologue) && !HasEpilogue;
139 
140     // Set the successors' state on entry.
141     for (MachineBasicBlock *Succ : MBB->successors()) {
142       BlockFlags &SuccInfo = BlockInfo[Succ->getNumber()];
143       SuccInfo.StrongNoFrameOnEntry |=
144           Info.StrongNoFrameOnEntry && !HasPrologue;
145       SuccInfo.HasFrameOnEntry = Info.HasFrameOnExit;
146     }
147   }
148 
149   if (!PrologueBlock)
150     return false;
151 
152   // Walk the blocks of the function in "physical" order.
153   // Every block inherits the frame state (as recorded in the unwind tables)
154   // of the previous block. If the intended frame state is different, insert
155   // compensating CFI instructions.
156   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
157   bool Change = false;
158   // `InsertPt` always points to the point in a preceding block where we have to
159   // insert a `.cfi_remember_state`, in the case that the current block needs a
160   // `.cfi_restore_state`.
161   MachineBasicBlock *InsertMBB = PrologueBlock;
162   MachineBasicBlock::iterator InsertPt = PrologueBlock->begin();
163   for (MachineInstr &MI : *PrologueBlock)
164     if (isPrologueCFIInstruction(MI))
165       InsertPt = std::next(MI.getIterator());
166 
167   assert(InsertPt != PrologueBlock->begin() &&
168          "Inconsistent notion of \"prologue block\"");
169 
170   // No point starting before the prologue block.
171   // TODO: the unwind tables will still be incorrect if an epilogue physically
172   // preceeds the prologue.
173   MachineFunction::iterator CurrBB = std::next(PrologueBlock->getIterator());
174   bool HasFrame = BlockInfo[PrologueBlock->getNumber()].HasFrameOnExit;
175   while (CurrBB != MF.end()) {
176     auto &Info = BlockInfo[CurrBB->getNumber()];
177 #ifndef NDEBUG
178     if (!Info.StrongNoFrameOnEntry) {
179       for (auto *Pred : CurrBB->predecessors())
180         assert(Info.HasFrameOnEntry ==
181                    BlockInfo[Pred->getNumber()].HasFrameOnExit &&
182                "Inconsistent call frame state");
183     }
184 #endif
185     if (!Info.StrongNoFrameOnEntry && Info.HasFrameOnEntry && !HasFrame) {
186       // Reset to the "after prologue" state.
187 
188       // Insert a `.cfi_remember_state` into the last block known to have a
189       // stack frame.
190       unsigned CFIIndex =
191           MF.addFrameInst(MCCFIInstruction::createRememberState(nullptr));
192       BuildMI(*InsertMBB, InsertPt, DebugLoc(),
193               TII.get(TargetOpcode::CFI_INSTRUCTION))
194           .addCFIIndex(CFIIndex);
195       // Insert a `.cfi_restore_state` at the beginning of the current block.
196       CFIIndex = MF.addFrameInst(MCCFIInstruction::createRestoreState(nullptr));
197       InsertPt = BuildMI(*CurrBB, CurrBB->begin(), DebugLoc(),
198                          TII.get(TargetOpcode::CFI_INSTRUCTION))
199                      .addCFIIndex(CFIIndex);
200       ++InsertPt;
201       InsertMBB = &*CurrBB;
202       Change = true;
203     } else if ((Info.StrongNoFrameOnEntry || !Info.HasFrameOnEntry) &&
204                HasFrame) {
205       // Reset to the state upon function entry.
206       TFL.resetCFIToInitialState(*CurrBB);
207       Change = true;
208     }
209 
210     HasFrame = Info.HasFrameOnExit;
211     ++CurrBB;
212   }
213 
214   return Change;
215 }
216