lib/CodeGen/CFIInstrInserter.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file This pass verifies incoming and outgoing CFA information of basic
  10 /// blocks. CFA information is information about offset and register set by CFI
  11 /// directives, valid at the start and end of a basic block. This pass checks
  12 /// that outgoing information of predecessors matches incoming information of
  13 /// their successors. Then it checks if blocks have correct CFA calculation rule
  14 /// set and inserts additional CFI instruction at their beginnings if they
  15 /// don't. CFI instructions are inserted if basic blocks have incorrect offset
  16 /// or register set by previous blocks, as a result of a non-linear layout of
  17 /// 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/MachineModuleInfo.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/TargetFrameLowering.h"
  26 #include "llvm/CodeGen/TargetInstrInfo.h"
  27 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 using namespace llvm;
  30
  31 static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
  32     cl::desc("Verify Call Frame Information instructions"),
  33     cl::init(false),
  34     cl::Hidden);
  35
  36 namespace {
  37 class CFIInstrInserter : public MachineFunctionPass {
  38  public:
  39   static char ID;
  40
  41   CFIInstrInserter() : MachineFunctionPass(ID) {
  42     initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry());
  43   }
  44
  45   void getAnalysisUsage(AnalysisUsage &AU) const override {
  46     AU.setPreservesAll();
  47     MachineFunctionPass::getAnalysisUsage(AU);
  48   }
  49
  50   bool runOnMachineFunction(MachineFunction &MF) override {
  51     if (!MF.getMMI().hasDebugInfo() &&
  52         !MF.getFunction().needsUnwindTableEntry())
  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     int IncomingCFAOffset = -1;
  73     /// Value of cfa offset valid at basic block exit.
  74     int 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     /// If in/out cfa offset and register values for this block have already
  80     /// been set or not.
  81     bool Processed = false;
  82   };
  83
  84   /// Contains cfa offset and register values valid at entry and exit of basic
  85   /// blocks.
  86   std::vector<MBBCFAInfo> MBBVector;
  87
  88   /// Calculate cfa offset and register values valid at entry and exit for all
  89   /// basic blocks in a function.
  90   void calculateCFAInfo(MachineFunction &MF);
  91   /// Calculate cfa offset and register values valid at basic block exit by
  92   /// checking the block for CFI instructions. Block's incoming CFA info remains
  93   /// the same.
  94   void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo);
  95   /// Update in/out cfa offset and register values for successors of the basic
  96   /// block.
  97   void updateSuccCFAInfo(MBBCFAInfo &MBBInfo);
  98
  99   /// Check if incoming CFA information of a basic block matches outgoing CFA
 100   /// information of the previous block. If it doesn't, insert CFI instruction
 101   /// at the beginning of the block that corrects the CFA calculation rule for
 102   /// that block.
 103   bool insertCFIInstrs(MachineFunction &MF);
 104   /// Return the cfa offset value that should be set at the beginning of a MBB
 105   /// if needed. The negated value is needed when creating CFI instructions that
 106   /// set absolute offset.
 107   int getCorrectCFAOffset(MachineBasicBlock *MBB) {
 108     return -MBBVector[MBB->getNumber()].IncomingCFAOffset;
 109   }
 110
 111   void report(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
 112   /// Go through each MBB in a function and check that outgoing offset and
 113   /// register of its predecessors match incoming offset and register of that
 114   /// MBB, as well as that incoming offset and register of its successors match
 115   /// outgoing offset and register of the MBB.
 116   unsigned verify(MachineFunction &MF);
 117 };
 118 }  // namespace
 119
 120 char CFIInstrInserter::ID = 0;
 121 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
 122                 "Check CFA info and insert CFI instructions if needed", false,
 123                 false)
 124 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
 125
 126 void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
 127   // Initial CFA offset value i.e. the one valid at the beginning of the
 128   // function.
 129   int InitialOffset =
 130       MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);
 131   // Initial CFA register value i.e. the one valid at the beginning of the
 132   // function.
 133   unsigned InitialRegister =
 134       MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);
 135
 136   // Initialize MBBMap.
 137   for (MachineBasicBlock &MBB : MF) {
 138     MBBCFAInfo MBBInfo;
 139     MBBInfo.MBB = &MBB;
 140     MBBInfo.IncomingCFAOffset = InitialOffset;
 141     MBBInfo.OutgoingCFAOffset = InitialOffset;
 142     MBBInfo.IncomingCFARegister = InitialRegister;
 143     MBBInfo.OutgoingCFARegister = InitialRegister;
 144     MBBVector[MBB.getNumber()] = MBBInfo;
 145   }
 146
 147   // Set in/out cfa info for all blocks in the function. This traversal is based
 148   // on the assumption that the first block in the function is the entry block
 149   // i.e. that it has initial cfa offset and register values as incoming CFA
 150   // information.
 151   for (MachineBasicBlock &MBB : MF) {
 152     if (MBBVector[MBB.getNumber()].Processed) continue;
 153     updateSuccCFAInfo(MBBVector[MBB.getNumber()]);
 154   }
 155 }
 156
 157 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
 158   // Outgoing cfa offset set by the block.
 159   int SetOffset = MBBInfo.IncomingCFAOffset;
 160   // Outgoing cfa register set by the block.
 161   unsigned SetRegister = MBBInfo.IncomingCFARegister;
 162   const std::vector<MCCFIInstruction> &Instrs =
 163       MBBInfo.MBB->getParent()->getFrameInstructions();
 164
 165   // Determine cfa offset and register set by the block.
 166   for (MachineInstr &MI : *MBBInfo.MBB) {
 167     if (MI.isCFIInstruction()) {
 168       unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
 169       const MCCFIInstruction &CFI = Instrs[CFIIndex];
 170       switch (CFI.getOperation()) {
 171       case MCCFIInstruction::OpDefCfaRegister:
 172         SetRegister = CFI.getRegister();
 173         break;
 174       case MCCFIInstruction::OpDefCfaOffset:
 175         SetOffset = CFI.getOffset();
 176         break;
 177       case MCCFIInstruction::OpAdjustCfaOffset:
 178         SetOffset += CFI.getOffset();
 179         break;
 180       case MCCFIInstruction::OpDefCfa:
 181         SetRegister = CFI.getRegister();
 182         SetOffset = CFI.getOffset();
 183         break;
 184       case MCCFIInstruction::OpRememberState:
 185         // TODO: Add support for handling cfi_remember_state.
 186 #ifndef NDEBUG
 187         report_fatal_error(
 188             "Support for cfi_remember_state not implemented! Value of CFA "
 189             "may be incorrect!\n");
 190 #endif
 191         break;
 192       case MCCFIInstruction::OpRestoreState:
 193         // TODO: Add support for handling cfi_restore_state.
 194 #ifndef NDEBUG
 195         report_fatal_error(
 196             "Support for cfi_restore_state not implemented! Value of CFA may "
 197             "be incorrect!\n");
 198 #endif
 199         break;
 200       // Other CFI directives do not affect CFA value.
 201       case MCCFIInstruction::OpSameValue:
 202       case MCCFIInstruction::OpOffset:
 203       case MCCFIInstruction::OpRelOffset:
 204       case MCCFIInstruction::OpEscape:
 205       case MCCFIInstruction::OpRestore:
 206       case MCCFIInstruction::OpUndefined:
 207       case MCCFIInstruction::OpRegister:
 208       case MCCFIInstruction::OpWindowSave:
 209       case MCCFIInstruction::OpNegateRAState:
 210       case MCCFIInstruction::OpGnuArgsSize:
 211         break;
 212       }
 213     }
 214   }
 215
 216   MBBInfo.Processed = true;
 217
 218   // Update outgoing CFA info.
 219   MBBInfo.OutgoingCFAOffset = SetOffset;
 220   MBBInfo.OutgoingCFARegister = SetRegister;
 221 }
 222
 223 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
 224   SmallVector<MachineBasicBlock *, 4> Stack;
 225   Stack.push_back(MBBInfo.MBB);
 226
 227   do {
 228     MachineBasicBlock *Current = Stack.pop_back_val();
 229     MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
 230     if (CurrentInfo.Processed)
 231       continue;
 232
 233     calculateOutgoingCFAInfo(CurrentInfo);
 234     for (auto *Succ : CurrentInfo.MBB->successors()) {
 235       MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
 236       if (!SuccInfo.Processed) {
 237         SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
 238         SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
 239         Stack.push_back(Succ);
 240       }
 241     }
 242   } while (!Stack.empty());
 243 }
 244
 245 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
 246   const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
 247   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
 248   bool InsertedCFIInstr = false;
 249
 250   for (MachineBasicBlock &MBB : MF) {
 251     // Skip the first MBB in a function
 252     if (MBB.getNumber() == MF.front().getNumber()) continue;
 253
 254     const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
 255     auto MBBI = MBBInfo.MBB->begin();
 256     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
 257
 258     if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
 259       // If both outgoing offset and register of a previous block don't match
 260       // incoming offset and register of this block, add a def_cfa instruction
 261       // with the correct offset and register for this block.
 262       if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) {
 263         unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::createDefCfa(
 264             nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
 265         BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 266             .addCFIIndex(CFIIndex);
 267         // If outgoing offset of a previous block doesn't match incoming offset
 268         // of this block, add a def_cfa_offset instruction with the correct
 269         // offset for this block.
 270       } else {
 271         unsigned CFIIndex =
 272             MF.addFrameInst(MCCFIInstruction::createDefCfaOffset(
 273                 nullptr, getCorrectCFAOffset(&MBB)));
 274         BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 275             .addCFIIndex(CFIIndex);
 276       }
 277       InsertedCFIInstr = true;
 278       // If outgoing register of a previous block doesn't match incoming
 279       // register of this block, add a def_cfa_register instruction with the
 280       // correct register for this block.
 281     } else if (PrevMBBInfo->OutgoingCFARegister !=
 282                MBBInfo.IncomingCFARegister) {
 283       unsigned CFIIndex =
 284           MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
 285               nullptr, MBBInfo.IncomingCFARegister));
 286       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 287           .addCFIIndex(CFIIndex);
 288       InsertedCFIInstr = true;
 289     }
 290     PrevMBBInfo = &MBBInfo;
 291   }
 292   return InsertedCFIInstr;
 293 }
 294
 295 void CFIInstrInserter::report(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ) {
 296   errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
 297             "***\n";
 298   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
 299          << " in " << Pred.MBB->getParent()->getName()
 300          << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
 301   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
 302          << " in " << Pred.MBB->getParent()->getName()
 303          << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
 304   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
 305          << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
 306   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
 307          << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
 308 }
 309
 310 unsigned CFIInstrInserter::verify(MachineFunction &MF) {
 311   unsigned ErrorNum = 0;
 312   for (auto *CurrMBB : depth_first(&MF)) {
 313     const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
 314     for (MachineBasicBlock *Succ : CurrMBB->successors()) {
 315       const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
 316       // Check that incoming offset and register values of successors match the
 317       // outgoing offset and register values of CurrMBB
 318       if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
 319           SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
 320         // Inconsistent offsets/registers are ok for 'noreturn' blocks because
 321         // we don't generate epilogues inside such blocks.
 322         if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
 323           continue;
 324         report(CurrMBBInfo, SuccMBBInfo);
 325         ErrorNum++;
 326       }
 327     }
 328   }
 329   return ErrorNum;
 330 }