203 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file provides the implementation of a machine pass that adds the flow10// 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/CodeGen/MIRFSDiscriminatorOptions.h"19#include "llvm/CodeGen/Passes.h"20#include "llvm/IR/DebugInfoMetadata.h"21#include "llvm/IR/Function.h"22#include "llvm/IR/Module.h"23#include "llvm/IR/PseudoProbe.h"24#include "llvm/InitializePasses.h"25#include "llvm/Support/CommandLine.h"26#include "llvm/Support/Debug.h"27#include "llvm/Support/raw_ostream.h"28#include "llvm/Support/xxhash.h"29#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"30 31using namespace llvm;32using namespace sampleprof;33using namespace sampleprofutil;34 35#define DEBUG_TYPE "mirfs-discriminators"36 37// TODO(xur): Remove this option and related code once we make true as the38// default.39cl::opt<bool> llvm::ImprovedFSDiscriminator(40 "improved-fs-discriminator", cl::Hidden, cl::init(false),41 cl::desc("New FS discriminators encoding (incompatible with the original "42 "encoding)"));43char MIRAddFSDiscriminators::ID = 0;44 45INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,46 "Add MIR Flow Sensitive Discriminators",47 /* cfg = */ false, /* is_analysis = */ false)48 49char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;50 51FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) {52 return new MIRAddFSDiscriminators(P);53}54 55// TODO(xur): Remove this once we switch to ImprovedFSDiscriminator.56// Compute a hash value using debug line number, and the line numbers from the57// inline stack.58static uint64_t getCallStackHashV0(const MachineBasicBlock &BB,59 const MachineInstr &MI,60 const DILocation *DIL) {61 auto updateHash = [](const StringRef &Str) -> uint64_t {62 if (Str.empty())63 return 0;64 return MD5Hash(Str);65 };66 uint64_t Ret = updateHash(std::to_string(DIL->getLine()));67 Ret ^= updateHash(BB.getName());68 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());69 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {70 Ret ^= updateHash(std::to_string(DIL->getLine()));71 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());72 }73 return Ret;74}75 76static uint64_t getCallStackHash(const DILocation *DIL) {77 auto hashCombine = [](const uint64_t Seed, const uint64_t Val) {78 std::hash<uint64_t> Hasher;79 return Seed ^ (Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2));80 };81 uint64_t Ret = 0;82 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {83 Ret = hashCombine(Ret, xxh3_64bits(ArrayRef<uint8_t>(DIL->getLine())));84 Ret = hashCombine(Ret, xxh3_64bits(DIL->getSubprogramLinkageName()));85 }86 return Ret;87}88 89// Traverse the CFG and assign FD discriminators. If two instructions90// have the same lineno and discriminator, but residing in different BBs,91// the latter instruction will get a new discriminator value. The new92// discriminator keeps the existing discriminator value but sets new bits93// b/w LowBit and HighBit.94bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {95 if (!EnableFSDiscriminator)96 return false;97 98 bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(99 PseudoProbeDescMetadataName);100 101 if (!HasPseudoProbe && !MF.getFunction().shouldEmitDebugInfoForProfiling())102 return false;103 104 bool Changed = false;105 using LocationDiscriminator =106 std::tuple<StringRef, unsigned, unsigned, uint64_t>;107 using BBSet = DenseSet<const MachineBasicBlock *>;108 using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;109 using LocationDiscriminatorCurrPassMap =110 DenseMap<LocationDiscriminator, unsigned>;111 112 LocationDiscriminatorBBMap LDBM;113 LocationDiscriminatorCurrPassMap LDCM;114 115 // Mask of discriminators before this pass.116 // TODO(xur): simplify this once we switch to ImprovedFSDiscriminator.117 unsigned LowBitTemp = LowBit;118 assert(LowBit > 0 && "LowBit in FSDiscriminator cannot be 0");119 if (ImprovedFSDiscriminator)120 LowBitTemp -= 1;121 unsigned BitMaskBefore = getN1Bits(LowBitTemp);122 // Mask of discriminators including this pass.123 unsigned BitMaskNow = getN1Bits(HighBit);124 // Mask of discriminators for bits specific to this pass.125 unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;126 unsigned NumNewD = 0;127 128 LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "129 << MF.getFunction().getName() << " Highbit=" << HighBit130 << "\n");131 132 for (MachineBasicBlock &BB : MF) {133 for (MachineInstr &I : BB) {134 if (HasPseudoProbe) {135 // Only assign discriminators to pseudo probe instructions. Call136 // instructions are excluded since their dwarf discriminators are used137 // for other purposes, i.e, storing probe ids.138 if (!I.isPseudoProbe())139 continue;140 } else if (ImprovedFSDiscriminator && I.isMetaInstruction()) {141 continue;142 }143 const DILocation *DIL = I.getDebugLoc().get();144 if (!DIL)145 continue;146 147 // Use the id of pseudo probe to compute the discriminator.148 unsigned LineNo =149 I.isPseudoProbe() ? I.getOperand(1).getImm() : DIL->getLine();150 if (LineNo == 0)151 continue;152 unsigned Discriminator = DIL->getDiscriminator();153 // Clean up discriminators for pseudo probes at the first FS discriminator154 // pass as their discriminators should not ever be used.155 if ((Pass == FSDiscriminatorPass::Pass1) && I.isPseudoProbe()) {156 Discriminator = 0;157 I.setDebugLoc(DIL->cloneWithDiscriminator(0));158 }159 uint64_t CallStackHashVal = 0;160 if (ImprovedFSDiscriminator)161 CallStackHashVal = getCallStackHash(DIL);162 163 LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator,164 CallStackHashVal};165 auto &BBMap = LDBM[LD];166 auto R = BBMap.insert(&BB);167 if (BBMap.size() == 1)168 continue;169 170 unsigned DiscriminatorCurrPass;171 DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];172 DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;173 if (!ImprovedFSDiscriminator)174 DiscriminatorCurrPass += getCallStackHashV0(BB, I, DIL);175 DiscriminatorCurrPass &= BitMaskThisPass;176 unsigned NewD = Discriminator | DiscriminatorCurrPass;177 const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);178 if (!NewDIL) {179 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "180 << DIL->getFilename() << ":" << DIL->getLine() << ":"181 << DIL->getColumn() << ":" << Discriminator << " "182 << I << "\n");183 continue;184 }185 186 I.setDebugLoc(NewDIL);187 NumNewD++;188 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"189 << DIL->getColumn() << ": add FS discriminator, from "190 << Discriminator << " -> " << NewD << "\n");191 Changed = true;192 }193 }194 195 if (Changed) {196 createFSDiscriminatorVariable(MF.getFunction().getParent());197 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");198 (void) NumNewD;199 }200 201 return Changed;202}203