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