1 //===-------- MIRFSDiscriminator.cpp: Flow Sensitive Discriminator --------===// 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 // This file provides the implementation of a machine pass that adds the flow 10 // sensitive discriminator to the instruction debug information. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/MIRFSDiscriminator.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/DenseSet.h" 17 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 18 #include "llvm/IR/Function.h" 19 #include "llvm/Support/CommandLine.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/raw_ostream.h" 22 #include <unordered_map> 23 24 using namespace llvm; 25 26 #define DEBUG_TYPE "mirfs-discriminators" 27 28 char MIRAddFSDiscriminators::ID = 0; 29 30 INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE, 31 "Add MIR Flow Sensitive Discriminators", 32 /* cfg = */ false, /* is_analysis = */ false) 33 34 char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID; 35 36 FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(unsigned LowBit, 37 unsigned HighBit) { 38 return new MIRAddFSDiscriminators(LowBit, HighBit); 39 } 40 41 // Compute a hash value using debug line number, and the line numbers from the 42 // inline stack. 43 static uint64_t getCallStackHash(const MachineBasicBlock &BB, 44 const MachineInstr &MI, 45 const DILocation *DIL) { 46 auto updateHash = [](const StringRef &Str) -> uint64_t { 47 if (Str.empty()) 48 return 0; 49 return MD5Hash(Str); 50 }; 51 uint64_t Ret = updateHash(std::to_string(DIL->getLine())); 52 Ret ^= updateHash(BB.getName()); 53 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName()); 54 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) { 55 Ret ^= updateHash(std::to_string(DIL->getLine())); 56 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName()); 57 } 58 return Ret; 59 } 60 61 // Traverse the CFG and assign FD discriminators. If two instructions 62 // have the same lineno and discriminator, but residing in different BBs, 63 // the latter instruction will get a new discriminator value. The new 64 // discriminator keeps the existing discriminator value but sets new bits 65 // b/w LowBit and HighBit. 66 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) { 67 if (!EnableFSDiscriminator) 68 return false; 69 70 bool Changed = false; 71 using LocationDiscriminator = std::tuple<StringRef, unsigned, unsigned>; 72 using BBSet = DenseSet<const MachineBasicBlock *>; 73 using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>; 74 using LocationDiscriminatorCurrPassMap = 75 DenseMap<LocationDiscriminator, unsigned>; 76 77 LocationDiscriminatorBBMap LDBM; 78 LocationDiscriminatorCurrPassMap LDCM; 79 80 // Mask of discriminators before this pass. 81 unsigned BitMaskBefore = getN1Bits(LowBit); 82 // Mask of discriminators including this pass. 83 unsigned BitMaskNow = getN1Bits(HighBit); 84 // Mask of discriminators for bits specific to this pass. 85 unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore; 86 unsigned NumNewD = 0; 87 88 LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: " 89 << MF.getFunction().getName() << "\n"); 90 for (MachineBasicBlock &BB : MF) { 91 for (MachineInstr &I : BB) { 92 const DILocation *DIL = I.getDebugLoc().get(); 93 if (!DIL) 94 continue; 95 unsigned LineNo = DIL->getLine(); 96 if (LineNo == 0) 97 continue; 98 unsigned Discriminator = DIL->getDiscriminator(); 99 LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator}; 100 auto &BBMap = LDBM[LD]; 101 auto R = BBMap.insert(&BB); 102 if (BBMap.size() == 1) 103 continue; 104 105 unsigned DiscriminatorCurrPass; 106 DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD]; 107 DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit; 108 DiscriminatorCurrPass += getCallStackHash(BB, I, DIL); 109 DiscriminatorCurrPass &= BitMaskThisPass; 110 unsigned NewD = Discriminator | DiscriminatorCurrPass; 111 const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD); 112 if (!NewDIL) { 113 LLVM_DEBUG(dbgs() << "Could not encode discriminator: " 114 << DIL->getFilename() << ":" << DIL->getLine() << ":" 115 << DIL->getColumn() << ":" << Discriminator << " " 116 << I << "\n"); 117 continue; 118 } 119 120 I.setDebugLoc(NewDIL); 121 NumNewD++; 122 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" 123 << DIL->getColumn() << ": add FS discriminator, from " 124 << Discriminator << " -> " << NewD << "\n"); 125 Changed = true; 126 } 127 } 128 129 if (Changed) { 130 Module *M = MF.getFunction().getParent(); 131 const char *FSDiscriminatorVar = "__llvm_fs_discriminator__"; 132 if (!M->getGlobalVariable(FSDiscriminatorVar)) { 133 auto &Context = M->getContext(); 134 // Create a global variable to flag that FSDiscriminators are used. 135 new GlobalVariable(*M, Type::getInt1Ty(Context), true, 136 GlobalValue::WeakAnyLinkage, 137 ConstantInt::getTrue(Context), FSDiscriminatorVar); 138 } 139 140 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n"); 141 } 142 143 return Changed; 144 } 145