229 lines · cpp
1//===- ProfileVerify.cpp - Verify profile info for testing ----------------===//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#include "llvm/Transforms/Utils/ProfileVerify.h"10#include "llvm/ADT/DynamicAPInt.h"11#include "llvm/ADT/STLExtras.h"12#include "llvm/Analysis/BranchProbabilityInfo.h"13#include "llvm/IR/Analysis.h"14#include "llvm/IR/Dominators.h"15#include "llvm/IR/Function.h"16#include "llvm/IR/Instructions.h"17#include "llvm/IR/LLVMContext.h"18#include "llvm/IR/MDBuilder.h"19#include "llvm/IR/ProfDataUtils.h"20#include "llvm/Support/BranchProbability.h"21#include "llvm/Support/CommandLine.h"22 23using namespace llvm;24static cl::opt<int64_t>25 DefaultFunctionEntryCount("profcheck-default-function-entry-count",26 cl::init(1000));27static cl::opt<bool>28 AnnotateSelect("profcheck-annotate-select", cl::init(true),29 cl::desc("Also inject (if missing) and verify MD_prof for "30 "`select` instructions"));31static cl::opt<bool>32 WeightsForTest("profcheck-weights-for-test", cl::init(false),33 cl::desc("Generate weights with small values for tests."));34 35static cl::opt<uint32_t> SelectTrueWeight(36 "profcheck-default-select-true-weight", cl::init(2U),37 cl::desc("When annotating `select` instructions, this value will be used "38 "for the first ('true') case."));39static cl::opt<uint32_t> SelectFalseWeight(40 "profcheck-default-select-false-weight", cl::init(3U),41 cl::desc("When annotating `select` instructions, this value will be used "42 "for the second ('false') case."));43namespace {44class ProfileInjector {45 Function &F;46 FunctionAnalysisManager &FAM;47 48public:49 static const Instruction *50 getTerminatorBenefitingFromMDProf(const BasicBlock &BB) {51 if (succ_size(&BB) < 2)52 return nullptr;53 auto *Term = BB.getTerminator();54 return (isa<BranchInst>(Term) || isa<SwitchInst>(Term) ||55 isa<IndirectBrInst>(Term) || isa<CallBrInst>(Term))56 ? Term57 : nullptr;58 }59 60 static Instruction *getTerminatorBenefitingFromMDProf(BasicBlock &BB) {61 return const_cast<Instruction *>(62 getTerminatorBenefitingFromMDProf(const_cast<const BasicBlock &>(BB)));63 }64 65 ProfileInjector(Function &F, FunctionAnalysisManager &FAM) : F(F), FAM(FAM) {}66 bool inject();67};68 69bool isAsmOnly(const Function &F) {70 if (!F.hasFnAttribute(Attribute::AttrKind::Naked))71 return false;72 for (const auto &BB : F)73 for (const auto &I : drop_end(BB.instructionsWithoutDebug())) {74 const auto *CB = dyn_cast<CallBase>(&I);75 if (!CB || !CB->isInlineAsm())76 return false;77 }78 return true;79}80} // namespace81 82// FIXME: currently this injects only for terminators. Select isn't yet83// supported.84bool ProfileInjector::inject() {85 // skip purely asm functions86 if (isAsmOnly(F))87 return false;88 // Get whatever branch probability info can be derived from the given IR -89 // whether it has or not metadata. The main intention for this pass is to90 // ensure that other passes don't drop or "forget" to update MD_prof. We do91 // this as a mode in which lit tests would run. We want to avoid changing the92 // behavior of those tests. A pass may use BPI (or BFI, which is computed from93 // BPI). If no metadata is present, BPI is guesstimated by94 // BranchProbabilityAnalysis. The injector (this pass) only persists whatever95 // information the analysis provides, in other words, the pass being tested96 // will get the same BPI it does if the injector wasn't running.97 auto &BPI = FAM.getResult<BranchProbabilityAnalysis>(F);98 99 // Inject a function count if there's none. It's reasonable for a pass to100 // want to clear the MD_prof of a function with zero entry count. If the101 // original profile (iFDO or AFDO) is empty for a function, it's simpler to102 // require assigning it the 0-entry count explicitly than to mark every branch103 // as cold (we do want some explicit information in the spirit of what this104 // verifier wants to achieve - make dropping / corrupting MD_prof105 // unit-testable)106 if (!F.getEntryCount(/*AllowSynthetic=*/true))107 F.setEntryCount(DefaultFunctionEntryCount);108 // If there is an entry count that's 0, then don't bother injecting. We won't109 // verify these either.110 if (F.getEntryCount(/*AllowSynthetic=*/true)->getCount() == 0)111 return false;112 bool Changed = false;113 // Cycle through the weights list. If we didn't, tests with more than (say)114 // one conditional branch would have the same !prof metadata on all of them,115 // and numerically that may make for a poor unit test.116 uint32_t WeightsForTestOffset = 0;117 for (auto &BB : F) {118 if (AnnotateSelect) {119 for (auto &I : BB) {120 if (auto *SI = dyn_cast<SelectInst>(&I)) {121 if (SI->getCondition()->getType()->isVectorTy())122 continue;123 if (I.getMetadata(LLVMContext::MD_prof))124 continue;125 setBranchWeights(I, {SelectTrueWeight, SelectFalseWeight},126 /*IsExpected=*/false);127 }128 }129 }130 auto *Term = getTerminatorBenefitingFromMDProf(BB);131 if (!Term || Term->getMetadata(LLVMContext::MD_prof))132 continue;133 SmallVector<BranchProbability> Probs;134 135 SmallVector<uint32_t> Weights;136 Weights.reserve(Term->getNumSuccessors());137 if (WeightsForTest) {138 static const std::array Primes{3, 5, 7, 11, 13, 17, 19, 23, 29, 31,139 37, 41, 43, 47, 53, 59, 61, 67, 71};140 for (uint32_t I = 0, E = Term->getNumSuccessors(); I < E; ++I)141 Weights.emplace_back(142 Primes[(WeightsForTestOffset + I) % Primes.size()]);143 ++WeightsForTestOffset;144 } else {145 Probs.reserve(Term->getNumSuccessors());146 for (auto I = 0U, E = Term->getNumSuccessors(); I < E; ++I)147 Probs.emplace_back(BPI.getEdgeProbability(&BB, Term->getSuccessor(I)));148 149 assert(llvm::find_if(Probs,150 [](const BranchProbability &P) {151 return P.isUnknown();152 }) == Probs.end() &&153 "All branch probabilities should be valid");154 const auto *FirstZeroDenominator =155 find_if(Probs, [](const BranchProbability &P) {156 return P.getDenominator() == 0;157 });158 (void)FirstZeroDenominator;159 assert(FirstZeroDenominator == Probs.end());160 const auto *FirstNonZeroNumerator = find_if(161 Probs, [](const BranchProbability &P) { return !P.isZero(); });162 assert(FirstNonZeroNumerator != Probs.end());163 DynamicAPInt LCM(Probs[0].getDenominator());164 DynamicAPInt GCD(FirstNonZeroNumerator->getNumerator());165 for (const auto &Prob : drop_begin(Probs)) {166 if (!Prob.getNumerator())167 continue;168 LCM = llvm::lcm(LCM, DynamicAPInt(Prob.getDenominator()));169 GCD = llvm::gcd(GCD, DynamicAPInt(Prob.getNumerator()));170 }171 for (const auto &Prob : Probs) {172 DynamicAPInt W =173 (Prob.getNumerator() * LCM / GCD) / Prob.getDenominator();174 Weights.emplace_back(static_cast<uint32_t>((int64_t)W));175 }176 }177 setBranchWeights(*Term, Weights, /*IsExpected=*/false);178 Changed = true;179 }180 return Changed;181}182 183PreservedAnalyses ProfileInjectorPass::run(Function &F,184 FunctionAnalysisManager &FAM) {185 ProfileInjector PI(F, FAM);186 if (!PI.inject())187 return PreservedAnalyses::all();188 189 return PreservedAnalyses::none();190}191 192PreservedAnalyses ProfileVerifierPass::run(Function &F,193 FunctionAnalysisManager &FAM) {194 // skip purely asm functions195 if (isAsmOnly(F))196 return PreservedAnalyses::all();197 198 const auto EntryCount = F.getEntryCount(/*AllowSynthetic=*/true);199 if (!EntryCount) {200 auto *MD = F.getMetadata(LLVMContext::MD_prof);201 if (!MD || !isExplicitlyUnknownProfileMetadata(*MD)) {202 F.getContext().emitError("Profile verification failed: function entry "203 "count missing (set to 0 if cold)");204 return PreservedAnalyses::all();205 }206 } else if (EntryCount->getCount() == 0) {207 return PreservedAnalyses::all();208 }209 for (const auto &BB : F) {210 if (AnnotateSelect) {211 for (const auto &I : BB)212 if (auto *SI = dyn_cast<SelectInst>(&I)) {213 if (SI->getCondition()->getType()->isVectorTy())214 continue;215 if (I.getMetadata(LLVMContext::MD_prof))216 continue;217 F.getContext().emitError(218 "Profile verification failed: select annotation missing");219 }220 }221 if (const auto *Term =222 ProfileInjector::getTerminatorBenefitingFromMDProf(BB))223 if (!Term->getMetadata(LLVMContext::MD_prof))224 F.getContext().emitError(225 "Profile verification failed: branch annotation missing");226 }227 return PreservedAnalyses::all();228}229