llvm/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/ADT/Optional.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstrBuilder.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/InitializePasses.h"
  29 #include "llvm/MC/MCDwarf.h"
  30 using namespace llvm;
  31
  32 static cl::opt<bool> VerifyCFI("verify-cfiinstrs",
  33     cl::desc("Verify Call Frame Information instructions"),
  34     cl::init(false),
  35     cl::Hidden);
  36
  37 namespace {
  38 class CFIInstrInserter : public MachineFunctionPass {
  39  public:
  40   static char ID;
  41
  42   CFIInstrInserter() : MachineFunctionPass(ID) {
  43     initializeCFIInstrInserterPass(*PassRegistry::getPassRegistry());
  44   }
  45
  46   void getAnalysisUsage(AnalysisUsage &AU) const override {
  47     AU.setPreservesAll();
  48     MachineFunctionPass::getAnalysisUsage(AU);
  49   }
  50
  51   bool runOnMachineFunction(MachineFunction &MF) override {
  52     if (!MF.needsFrameMoves())
  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     /// Set of callee saved registers saved at basic block entry.
  80     BitVector IncomingCSRSaved;
  81     /// Set of callee saved registers saved at basic block exit.
  82     BitVector OutgoingCSRSaved;
  83     /// If in/out cfa offset and register values for this block have already
  84     /// been set or not.
  85     bool Processed = false;
  86   };
  87
  88 #define INVALID_REG UINT_MAX
  89 #define INVALID_OFFSET INT_MAX
  90   /// contains the location where CSR register is saved.
  91   struct CSRSavedLocation {
  92     CSRSavedLocation(Optional<unsigned> R, Optional<int> O)
  93         : Reg(R), Offset(O) {}
  94     Optional<unsigned> Reg;
  95     Optional<int> Offset;
  96   };
  97
  98   /// Contains cfa offset and register values valid at entry and exit of basic
  99   /// blocks.
 100   std::vector<MBBCFAInfo> MBBVector;
 101
 102   /// Map the callee save registers to the locations where they are saved.
 103   SmallDenseMap<unsigned, CSRSavedLocation, 16> CSRLocMap;
 104
 105   /// Calculate cfa offset and register values valid at entry and exit for all
 106   /// basic blocks in a function.
 107   void calculateCFAInfo(MachineFunction &MF);
 108   /// Calculate cfa offset and register values valid at basic block exit by
 109   /// checking the block for CFI instructions. Block's incoming CFA info remains
 110   /// the same.
 111   void calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo);
 112   /// Update in/out cfa offset and register values for successors of the basic
 113   /// block.
 114   void updateSuccCFAInfo(MBBCFAInfo &MBBInfo);
 115
 116   /// Check if incoming CFA information of a basic block matches outgoing CFA
 117   /// information of the previous block. If it doesn't, insert CFI instruction
 118   /// at the beginning of the block that corrects the CFA calculation rule for
 119   /// that block.
 120   bool insertCFIInstrs(MachineFunction &MF);
 121   /// Return the cfa offset value that should be set at the beginning of a MBB
 122   /// if needed. The negated value is needed when creating CFI instructions that
 123   /// set absolute offset.
 124   int getCorrectCFAOffset(MachineBasicBlock *MBB) {
 125     return MBBVector[MBB->getNumber()].IncomingCFAOffset;
 126   }
 127
 128   void reportCFAError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
 129   void reportCSRError(const MBBCFAInfo &Pred, const MBBCFAInfo &Succ);
 130   /// Go through each MBB in a function and check that outgoing offset and
 131   /// register of its predecessors match incoming offset and register of that
 132   /// MBB, as well as that incoming offset and register of its successors match
 133   /// outgoing offset and register of the MBB.
 134   unsigned verify(MachineFunction &MF);
 135 };
 136 }  // namespace
 137
 138 char CFIInstrInserter::ID = 0;
 139 INITIALIZE_PASS(CFIInstrInserter, "cfi-instr-inserter",
 140                 "Check CFA info and insert CFI instructions if needed", false,
 141                 false)
 142 FunctionPass *llvm::createCFIInstrInserter() { return new CFIInstrInserter(); }
 143
 144 void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
 145   // Initial CFA offset value i.e. the one valid at the beginning of the
 146   // function.
 147   int InitialOffset =
 148       MF.getSubtarget().getFrameLowering()->getInitialCFAOffset(MF);
 149   // Initial CFA register value i.e. the one valid at the beginning of the
 150   // function.
 151   unsigned InitialRegister =
 152       MF.getSubtarget().getFrameLowering()->getInitialCFARegister(MF);
 153   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
 154   unsigned NumRegs = TRI.getNumRegs();
 155
 156   // Initialize MBBMap.
 157   for (MachineBasicBlock &MBB : MF) {
 158     MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
 159     MBBInfo.MBB = &MBB;
 160     MBBInfo.IncomingCFAOffset = InitialOffset;
 161     MBBInfo.OutgoingCFAOffset = InitialOffset;
 162     MBBInfo.IncomingCFARegister = InitialRegister;
 163     MBBInfo.OutgoingCFARegister = InitialRegister;
 164     MBBInfo.IncomingCSRSaved.resize(NumRegs);
 165     MBBInfo.OutgoingCSRSaved.resize(NumRegs);
 166   }
 167   CSRLocMap.clear();
 168
 169   // Set in/out cfa info for all blocks in the function. This traversal is based
 170   // on the assumption that the first block in the function is the entry block
 171   // i.e. that it has initial cfa offset and register values as incoming CFA
 172   // information.
 173   updateSuccCFAInfo(MBBVector[MF.front().getNumber()]);
 174 }
 175
 176 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
 177   // Outgoing cfa offset set by the block.
 178   int SetOffset = MBBInfo.IncomingCFAOffset;
 179   // Outgoing cfa register set by the block.
 180   unsigned SetRegister = MBBInfo.IncomingCFARegister;
 181   MachineFunction *MF = MBBInfo.MBB->getParent();
 182   const std::vector<MCCFIInstruction> &Instrs = MF->getFrameInstructions();
 183   const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
 184   unsigned NumRegs = TRI.getNumRegs();
 185   BitVector CSRSaved(NumRegs), CSRRestored(NumRegs);
 186
 187   // Determine cfa offset and register set by the block.
 188   for (MachineInstr &MI : *MBBInfo.MBB) {
 189     if (MI.isCFIInstruction()) {
 190       Optional<unsigned> CSRReg;
 191       Optional<int> CSROffset;
 192       unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
 193       const MCCFIInstruction &CFI = Instrs[CFIIndex];
 194       switch (CFI.getOperation()) {
 195       case MCCFIInstruction::OpDefCfaRegister:
 196         SetRegister = CFI.getRegister();
 197         break;
 198       case MCCFIInstruction::OpDefCfaOffset:
 199         SetOffset = CFI.getOffset();
 200         break;
 201       case MCCFIInstruction::OpAdjustCfaOffset:
 202         SetOffset += CFI.getOffset();
 203         break;
 204       case MCCFIInstruction::OpDefCfa:
 205         SetRegister = CFI.getRegister();
 206         SetOffset = CFI.getOffset();
 207         break;
 208       case MCCFIInstruction::OpOffset:
 209         CSROffset = CFI.getOffset();
 210         break;
 211       case MCCFIInstruction::OpRegister:
 212         CSRReg = CFI.getRegister2();
 213         break;
 214       case MCCFIInstruction::OpRelOffset:
 215         CSROffset = CFI.getOffset() - SetOffset;
 216         break;
 217       case MCCFIInstruction::OpRestore:
 218         CSRRestored.set(CFI.getRegister());
 219         break;
 220       case MCCFIInstruction::OpLLVMDefAspaceCfa:
 221         // TODO: Add support for handling cfi_def_aspace_cfa.
 222 #ifndef NDEBUG
 223         report_fatal_error(
 224             "Support for cfi_llvm_def_aspace_cfa not implemented! Value of CFA "
 225             "may be incorrect!\n");
 226 #endif
 227         break;
 228       case MCCFIInstruction::OpRememberState:
 229         // TODO: Add support for handling cfi_remember_state.
 230 #ifndef NDEBUG
 231         report_fatal_error(
 232             "Support for cfi_remember_state not implemented! Value of CFA "
 233             "may be incorrect!\n");
 234 #endif
 235         break;
 236       case MCCFIInstruction::OpRestoreState:
 237         // TODO: Add support for handling cfi_restore_state.
 238 #ifndef NDEBUG
 239         report_fatal_error(
 240             "Support for cfi_restore_state not implemented! Value of CFA may "
 241             "be incorrect!\n");
 242 #endif
 243         break;
 244       // Other CFI directives do not affect CFA value.
 245       case MCCFIInstruction::OpUndefined:
 246       case MCCFIInstruction::OpSameValue:
 247       case MCCFIInstruction::OpEscape:
 248       case MCCFIInstruction::OpWindowSave:
 249       case MCCFIInstruction::OpNegateRAState:
 250       case MCCFIInstruction::OpGnuArgsSize:
 251         break;
 252       }
 253       if (CSRReg || CSROffset) {
 254         auto It = CSRLocMap.find(CFI.getRegister());
 255         if (It == CSRLocMap.end()) {
 256           CSRLocMap.insert(
 257               {CFI.getRegister(), CSRSavedLocation(CSRReg, CSROffset)});
 258         } else if (It->second.Reg != CSRReg || It->second.Offset != CSROffset) {
 259           llvm_unreachable("Different saved locations for the same CSR");
 260         }
 261         CSRSaved.set(CFI.getRegister());
 262       }
 263     }
 264   }
 265
 266   MBBInfo.Processed = true;
 267
 268   // Update outgoing CFA info.
 269   MBBInfo.OutgoingCFAOffset = SetOffset;
 270   MBBInfo.OutgoingCFARegister = SetRegister;
 271
 272   // Update outgoing CSR info.
 273   BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; },
 274                    MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved,
 275                    CSRRestored);
 276 }
 277
 278 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
 279   SmallVector<MachineBasicBlock *, 4> Stack;
 280   Stack.push_back(MBBInfo.MBB);
 281
 282   do {
 283     MachineBasicBlock *Current = Stack.pop_back_val();
 284     MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
 285     calculateOutgoingCFAInfo(CurrentInfo);
 286     for (auto *Succ : CurrentInfo.MBB->successors()) {
 287       MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
 288       if (!SuccInfo.Processed) {
 289         SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
 290         SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
 291         SuccInfo.IncomingCSRSaved = CurrentInfo.OutgoingCSRSaved;
 292         Stack.push_back(Succ);
 293       }
 294     }
 295   } while (!Stack.empty());
 296 }
 297
 298 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
 299   const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
 300   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
 301   bool InsertedCFIInstr = false;
 302
 303   BitVector SetDifference;
 304   for (MachineBasicBlock &MBB : MF) {
 305     // Skip the first MBB in a function
 306     if (MBB.getNumber() == MF.front().getNumber()) continue;
 307
 308     const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
 309     auto MBBI = MBBInfo.MBB->begin();
 310     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
 311
 312     // If the current MBB will be placed in a unique section, a full DefCfa
 313     // must be emitted.
 314     const bool ForceFullCFA = MBB.isBeginSection();
 315
 316     if ((PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset &&
 317          PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) ||
 318         ForceFullCFA) {
 319       // If both outgoing offset and register of a previous block don't match
 320       // incoming offset and register of this block, or if this block begins a
 321       // section, add a def_cfa instruction with the correct offset and
 322       // register for this block.
 323       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfa(
 324           nullptr, MBBInfo.IncomingCFARegister, getCorrectCFAOffset(&MBB)));
 325       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 326           .addCFIIndex(CFIIndex);
 327       InsertedCFIInstr = true;
 328     } else if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
 329       // If outgoing offset of a previous block doesn't match incoming offset
 330       // of this block, add a def_cfa_offset instruction with the correct
 331       // offset for this block.
 332       unsigned CFIIndex = MF.addFrameInst(MCCFIInstruction::cfiDefCfaOffset(
 333           nullptr, getCorrectCFAOffset(&MBB)));
 334       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 335           .addCFIIndex(CFIIndex);
 336       InsertedCFIInstr = true;
 337     } else if (PrevMBBInfo->OutgoingCFARegister !=
 338                MBBInfo.IncomingCFARegister) {
 339       unsigned CFIIndex =
 340           MF.addFrameInst(MCCFIInstruction::createDefCfaRegister(
 341               nullptr, MBBInfo.IncomingCFARegister));
 342       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 343           .addCFIIndex(CFIIndex);
 344       InsertedCFIInstr = true;
 345     }
 346
 347     if (ForceFullCFA) {
 348       MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMovesFullCFA(
 349           *MBBInfo.MBB, MBBI);
 350       InsertedCFIInstr = true;
 351       PrevMBBInfo = &MBBInfo;
 352       continue;
 353     }
 354
 355     BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
 356                      PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved);
 357     for (int Reg : SetDifference.set_bits()) {
 358       unsigned CFIIndex =
 359           MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg));
 360       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 361           .addCFIIndex(CFIIndex);
 362       InsertedCFIInstr = true;
 363     }
 364
 365     BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
 366                      MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved);
 367     for (int Reg : SetDifference.set_bits()) {
 368       auto it = CSRLocMap.find(Reg);
 369       assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");
 370       unsigned CFIIndex;
 371       CSRSavedLocation RO = it->second;
 372       if (!RO.Reg && RO.Offset) {
 373         CFIIndex = MF.addFrameInst(
 374             MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset));
 375       } else if (RO.Reg && !RO.Offset) {
 376         CFIIndex = MF.addFrameInst(
 377             MCCFIInstruction::createRegister(nullptr, Reg, *RO.Reg));
 378       } else {
 379         llvm_unreachable("RO.Reg and RO.Offset cannot both be valid/invalid");
 380       }
 381       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
 382           .addCFIIndex(CFIIndex);
 383       InsertedCFIInstr = true;
 384     }
 385
 386     PrevMBBInfo = &MBBInfo;
 387   }
 388   return InsertedCFIInstr;
 389 }
 390
 391 void CFIInstrInserter::reportCFAError(const MBBCFAInfo &Pred,
 392                                       const MBBCFAInfo &Succ) {
 393   errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
 394             "***\n";
 395   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
 396          << " in " << Pred.MBB->getParent()->getName()
 397          << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
 398   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
 399          << " in " << Pred.MBB->getParent()->getName()
 400          << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
 401   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
 402          << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
 403   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
 404          << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
 405 }
 406
 407 void CFIInstrInserter::reportCSRError(const MBBCFAInfo &Pred,
 408                                       const MBBCFAInfo &Succ) {
 409   errs() << "*** Inconsistent CSR Saved between pred and succ in function "
 410          << Pred.MBB->getParent()->getName() << " ***\n";
 411   errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
 412          << " outgoing CSR Saved: ";
 413   for (int Reg : Pred.OutgoingCSRSaved.set_bits())
 414     errs() << Reg << " ";
 415   errs() << "\n";
 416   errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
 417          << " incoming CSR Saved: ";
 418   for (int Reg : Succ.IncomingCSRSaved.set_bits())
 419     errs() << Reg << " ";
 420   errs() << "\n";
 421 }
 422
 423 unsigned CFIInstrInserter::verify(MachineFunction &MF) {
 424   unsigned ErrorNum = 0;
 425   for (auto *CurrMBB : depth_first(&MF)) {
 426     const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
 427     for (MachineBasicBlock *Succ : CurrMBB->successors()) {
 428       const MBBCFAInfo &SuccMBBInfo = MBBVector[Succ->getNumber()];
 429       // Check that incoming offset and register values of successors match the
 430       // outgoing offset and register values of CurrMBB
 431       if (SuccMBBInfo.IncomingCFAOffset != CurrMBBInfo.OutgoingCFAOffset ||
 432           SuccMBBInfo.IncomingCFARegister != CurrMBBInfo.OutgoingCFARegister) {
 433         // Inconsistent offsets/registers are ok for 'noreturn' blocks because
 434         // we don't generate epilogues inside such blocks.
 435         if (SuccMBBInfo.MBB->succ_empty() && !SuccMBBInfo.MBB->isReturnBlock())
 436           continue;
 437         reportCFAError(CurrMBBInfo, SuccMBBInfo);
 438         ErrorNum++;
 439       }
 440       // Check that IncomingCSRSaved of every successor matches the
 441       // OutgoingCSRSaved of CurrMBB
 442       if (SuccMBBInfo.IncomingCSRSaved != CurrMBBInfo.OutgoingCSRSaved) {
 443         reportCSRError(CurrMBBInfo, SuccMBBInfo);
 444         ErrorNum++;
 445       }
 446     }
 447   }
 448   return ErrorNum;
 449 }