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