526 lines · cpp
1//===-- BasicBlockSectionsProfileReader.cpp -------------------------------===//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// Implementation of the basic block sections profile reader pass. It parses10// and stores the basic block sections profile file (which is specified via the11// `-basic-block-sections` flag).12//13//===----------------------------------------------------------------------===//14 15#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"16#include "llvm/ADT/DenseSet.h"17#include "llvm/ADT/SmallSet.h"18#include "llvm/ADT/SmallString.h"19#include "llvm/ADT/SmallVector.h"20#include "llvm/ADT/StringMap.h"21#include "llvm/ADT/StringRef.h"22#include "llvm/IR/DebugInfoMetadata.h"23#include "llvm/Pass.h"24#include "llvm/Support/Error.h"25#include "llvm/Support/ErrorHandling.h"26#include "llvm/Support/LineIterator.h"27#include "llvm/Support/MemoryBuffer.h"28#include "llvm/Support/Path.h"29#include "llvm/Support/UniqueBBID.h"30#include <llvm/ADT/STLExtras.h>31 32using namespace llvm;33 34char BasicBlockSectionsProfileReaderWrapperPass::ID = 0;35INITIALIZE_PASS(BasicBlockSectionsProfileReaderWrapperPass,36 "bbsections-profile-reader",37 "Reads and parses a basic block sections profile.", false,38 false)39 40Expected<UniqueBBID>41BasicBlockSectionsProfileReader::parseUniqueBBID(StringRef S) const {42 SmallVector<StringRef, 2> Parts;43 S.split(Parts, '.');44 if (Parts.size() > 2)45 return createProfileParseError(Twine("unable to parse basic block id: '") +46 S + "'");47 unsigned long long BaseBBID;48 if (getAsUnsignedInteger(Parts[0], 10, BaseBBID))49 return createProfileParseError(50 Twine("unable to parse BB id: '" + Parts[0]) +51 "': unsigned integer expected");52 unsigned long long CloneID = 0;53 if (Parts.size() > 1 && getAsUnsignedInteger(Parts[1], 10, CloneID))54 return createProfileParseError(Twine("unable to parse clone id: '") +55 Parts[1] + "': unsigned integer expected");56 return UniqueBBID{static_cast<unsigned>(BaseBBID),57 static_cast<unsigned>(CloneID)};58}59 60bool BasicBlockSectionsProfileReader::isFunctionHot(StringRef FuncName) const {61 return !getClusterInfoForFunction(FuncName).empty();62}63 64SmallVector<BBClusterInfo>65BasicBlockSectionsProfileReader::getClusterInfoForFunction(66 StringRef FuncName) const {67 auto R = ProgramPathAndClusterInfo.find(getAliasName(FuncName));68 return R != ProgramPathAndClusterInfo.end() ? R->second.ClusterInfo69 : SmallVector<BBClusterInfo>();70}71 72SmallVector<SmallVector<unsigned>>73BasicBlockSectionsProfileReader::getClonePathsForFunction(74 StringRef FuncName) const {75 auto R = ProgramPathAndClusterInfo.find(getAliasName(FuncName));76 return R != ProgramPathAndClusterInfo.end()77 ? R->second.ClonePaths78 : SmallVector<SmallVector<unsigned>>();79}80 81uint64_t BasicBlockSectionsProfileReader::getEdgeCount(82 StringRef FuncName, const UniqueBBID &SrcBBID,83 const UniqueBBID &SinkBBID) const {84 auto It = ProgramPathAndClusterInfo.find(getAliasName(FuncName));85 if (It == ProgramPathAndClusterInfo.end())86 return 0;87 auto NodeIt = It->second.EdgeCounts.find(SrcBBID);88 if (NodeIt == It->second.EdgeCounts.end())89 return 0;90 auto EdgeIt = NodeIt->second.find(SinkBBID);91 if (EdgeIt == NodeIt->second.end())92 return 0;93 return EdgeIt->second;94}95 96// Reads the version 1 basic block sections profile. Profile for each function97// is encoded as follows:98// m <module_name>99// f <function_name_1> <function_name_2> ...100// c <bb_id_1> <bb_id_2> <bb_id_3>101// c <bb_id_4> <bb_id_5>102// ...103// Module name specifier (starting with 'm') is optional and allows104// distinguishing profile for internal-linkage functions with the same name. If105// not specified, it will apply to any function with the same name. Function106// name specifier (starting with 'f') can specify multiple function name107// aliases. Basic block clusters are specified by 'c' and specify the cluster of108// basic blocks, and the internal order in which they must be placed in the same109// section.110// This profile can also specify cloning paths which instruct the compiler to111// clone basic blocks along a path. The cloned blocks are then specified in the112// cluster information.113// The following profile lists two cloning paths (starting with 'p') for114// function bar and places the total 9 blocks within two clusters. The first two115// blocks of a cloning path specify the edge along which the path is cloned. For116// instance, path 1 (1 -> 3 -> 4) instructs that 3 and 4 must be cloned along117// the edge 1->3. Within the given clusters, each cloned block is identified by118// "<original block id>.<clone id>". For instance, 3.1 represents the first119// clone of block 3. Original blocks are specified just with their block ids. A120// block cloned multiple times appears with distinct clone ids. The CFG for bar121// is shown below before and after cloning with its final clusters labeled.122//123// f main124// f bar125// p 1 3 4 # cloning path 1126// p 4 2 # cloning path 2127// c 1 3.1 4.1 6 # basic block cluster 1128// c 0 2 3 4 2.1 5 # basic block cluster 2129// ****************************************************************************130// function bar before and after cloning with basic block clusters shown.131// ****************************************************************************132// .... ..............133// 0 -------+ : 0 :---->: 1 ---> 3.1 :134// | | : | : :........ | :135// v v : v : : v :136// +--> 2 --> 5 1 ~~~~~~> +---: 2 : : 4.1: clsuter 1137// | | | | : | : : | :138// | v | | : v ....... : v :139// | 3 <------+ | : 3 <--+ : : 6 :140// | | | : | | : :....:141// | v | : v | :142// +--- 4 ---> 6 | : 4 | :143// | : | | :144// | : v | :145// | :2.1---+ : cluster 2146// | : | ......:147// | : v :148// +-->: 5 :149// ....150// ****************************************************************************151Error BasicBlockSectionsProfileReader::ReadV1Profile() {152 auto FI = ProgramPathAndClusterInfo.end();153 154 // Current cluster ID corresponding to this function.155 unsigned CurrentCluster = 0;156 // Current position in the current cluster.157 unsigned CurrentPosition = 0;158 159 // Temporary set to ensure every basic block ID appears once in the clusters160 // of a function.161 DenseSet<UniqueBBID> FuncBBIDs;162 163 // Debug-info-based module filename for the current function. Empty string164 // means no filename.165 StringRef DIFilename;166 167 for (; !LineIt.is_at_eof(); ++LineIt) {168 StringRef S(*LineIt);169 char Specifier = S[0];170 S = S.drop_front().trim();171 SmallVector<StringRef, 4> Values;172 S.split(Values, ' ');173 switch (Specifier) {174 case '@':175 continue;176 case 'm': // Module name speicifer.177 if (Values.size() != 1) {178 return createProfileParseError(Twine("invalid module name value: '") +179 S + "'");180 }181 DIFilename = sys::path::remove_leading_dotslash(Values[0]);182 continue;183 case 'f': { // Function names specifier.184 bool FunctionFound = any_of(Values, [&](StringRef Alias) {185 auto It = FunctionNameToDIFilename.find(Alias);186 // No match if this function name is not found in this module.187 if (It == FunctionNameToDIFilename.end())188 return false;189 // Return a match if debug-info-filename is not specified. Otherwise,190 // check for equality.191 return DIFilename.empty() || It->second == DIFilename;192 });193 if (!FunctionFound) {194 // Skip the following profile by setting the profile iterator (FI) to195 // the past-the-end element.196 FI = ProgramPathAndClusterInfo.end();197 DIFilename = "";198 continue;199 }200 for (size_t i = 1; i < Values.size(); ++i)201 FuncAliasMap.try_emplace(Values[i], Values.front());202 203 // Prepare for parsing clusters of this function name.204 // Start a new cluster map for this function name.205 auto R = ProgramPathAndClusterInfo.try_emplace(Values.front());206 // Report error when multiple profiles have been specified for the same207 // function.208 if (!R.second)209 return createProfileParseError("duplicate profile for function '" +210 Values.front() + "'");211 FI = R.first;212 CurrentCluster = 0;213 FuncBBIDs.clear();214 // We won't need DIFilename anymore. Clean it up to avoid its application215 // on the next function.216 DIFilename = "";217 continue;218 }219 case 'c': // Basic block cluster specifier.220 // Skip the profile when we the profile iterator (FI) refers to the221 // past-the-end element.222 if (FI == ProgramPathAndClusterInfo.end())223 continue;224 // Reset current cluster position.225 CurrentPosition = 0;226 for (auto BasicBlockIDStr : Values) {227 auto BasicBlockID = parseUniqueBBID(BasicBlockIDStr);228 if (!BasicBlockID)229 return BasicBlockID.takeError();230 if (!FuncBBIDs.insert(*BasicBlockID).second)231 return createProfileParseError(232 Twine("duplicate basic block id found '") + BasicBlockIDStr +233 "'");234 235 FI->second.ClusterInfo.emplace_back(BBClusterInfo{236 *std::move(BasicBlockID), CurrentCluster, CurrentPosition++});237 }238 CurrentCluster++;239 continue;240 case 'p': { // Basic block cloning path specifier.241 // Skip the profile when we the profile iterator (FI) refers to the242 // past-the-end element.243 if (FI == ProgramPathAndClusterInfo.end())244 continue;245 SmallSet<unsigned, 5> BBsInPath;246 FI->second.ClonePaths.push_back({});247 for (size_t I = 0; I < Values.size(); ++I) {248 auto BaseBBIDStr = Values[I];249 unsigned long long BaseBBID = 0;250 if (getAsUnsignedInteger(BaseBBIDStr, 10, BaseBBID))251 return createProfileParseError(Twine("unsigned integer expected: '") +252 BaseBBIDStr + "'");253 if (I != 0 && !BBsInPath.insert(BaseBBID).second)254 return createProfileParseError(255 Twine("duplicate cloned block in path: '") + BaseBBIDStr + "'");256 FI->second.ClonePaths.back().push_back(BaseBBID);257 }258 continue;259 }260 case 'g': { // CFG profile specifier.261 // Skip the profile when we the profile iterator (FI) refers to the262 // past-the-end element.263 if (FI == ProgramPathAndClusterInfo.end())264 continue;265 // For each node, its CFG profile is encoded as266 // <src>:<count>,<sink_1>:<count_1>,<sink_2>:<count_2>,...267 for (auto BasicBlockEdgeProfile : Values) {268 if (BasicBlockEdgeProfile.empty())269 continue;270 SmallVector<StringRef, 4> NodeEdgeCounts;271 BasicBlockEdgeProfile.split(NodeEdgeCounts, ',');272 UniqueBBID SrcBBID;273 for (size_t i = 0; i < NodeEdgeCounts.size(); ++i) {274 auto [BBIDStr, CountStr] = NodeEdgeCounts[i].split(':');275 auto BBID = parseUniqueBBID(BBIDStr);276 if (!BBID)277 return BBID.takeError();278 unsigned long long Count = 0;279 if (getAsUnsignedInteger(CountStr, 10, Count))280 return createProfileParseError(281 Twine("unsigned integer expected: '") + CountStr + "'");282 if (i == 0) {283 // The first element represents the source and its total count.284 FI->second.NodeCounts[SrcBBID = *BBID] = Count;285 continue;286 }287 FI->second.EdgeCounts[SrcBBID][*BBID] = Count;288 }289 }290 continue;291 }292 case 'h': { // Basic block hash secifier.293 // Skip the profile when the profile iterator (FI) refers to the294 // past-the-end element.295 if (FI == ProgramPathAndClusterInfo.end())296 continue;297 for (auto BBIDHashStr : Values) {298 auto [BBIDStr, HashStr] = BBIDHashStr.split(':');299 unsigned long long BBID = 0, Hash = 0;300 if (getAsUnsignedInteger(BBIDStr, 10, BBID))301 return createProfileParseError(Twine("unsigned integer expected: '") +302 BBIDStr + "'");303 if (getAsUnsignedInteger(HashStr, 16, Hash))304 return createProfileParseError(305 Twine("unsigned integer expected in hex format: '") + HashStr +306 "'");307 FI->second.BBHashes[BBID] = Hash;308 }309 continue;310 }311 default:312 return createProfileParseError(Twine("invalid specifier: '") +313 Twine(Specifier) + "'");314 }315 llvm_unreachable("should not break from this switch statement");316 }317 return Error::success();318}319 320Error BasicBlockSectionsProfileReader::ReadV0Profile() {321 auto FI = ProgramPathAndClusterInfo.end();322 // Current cluster ID corresponding to this function.323 unsigned CurrentCluster = 0;324 // Current position in the current cluster.325 unsigned CurrentPosition = 0;326 327 // Temporary set to ensure every basic block ID appears once in the clusters328 // of a function.329 SmallSet<unsigned, 4> FuncBBIDs;330 331 for (; !LineIt.is_at_eof(); ++LineIt) {332 StringRef S(*LineIt);333 if (S[0] == '@')334 continue;335 // Check for the leading "!"336 if (!S.consume_front("!") || S.empty())337 break;338 // Check for second "!" which indicates a cluster of basic blocks.339 if (S.consume_front("!")) {340 // Skip the profile when we the profile iterator (FI) refers to the341 // past-the-end element.342 if (FI == ProgramPathAndClusterInfo.end())343 continue;344 SmallVector<StringRef, 4> BBIDs;345 S.split(BBIDs, ' ');346 // Reset current cluster position.347 CurrentPosition = 0;348 for (auto BBIDStr : BBIDs) {349 unsigned long long BBID;350 if (getAsUnsignedInteger(BBIDStr, 10, BBID))351 return createProfileParseError(Twine("unsigned integer expected: '") +352 BBIDStr + "'");353 if (!FuncBBIDs.insert(BBID).second)354 return createProfileParseError(355 Twine("duplicate basic block id found '") + BBIDStr + "'");356 357 FI->second.ClusterInfo.emplace_back(358 BBClusterInfo({{static_cast<unsigned>(BBID), 0},359 CurrentCluster,360 CurrentPosition++}));361 }362 CurrentCluster++;363 } else {364 // This is a function name specifier. It may include a debug info filename365 // specifier starting with `M=`.366 auto [AliasesStr, DIFilenameStr] = S.split(' ');367 SmallString<128> DIFilename;368 if (DIFilenameStr.starts_with("M=")) {369 DIFilename =370 sys::path::remove_leading_dotslash(DIFilenameStr.substr(2));371 if (DIFilename.empty())372 return createProfileParseError("empty module name specifier");373 } else if (!DIFilenameStr.empty()) {374 return createProfileParseError("unknown string found: '" +375 DIFilenameStr + "'");376 }377 // Function aliases are separated using '/'. We use the first function378 // name for the cluster info mapping and delegate all other aliases to379 // this one.380 SmallVector<StringRef, 4> Aliases;381 AliasesStr.split(Aliases, '/');382 bool FunctionFound = any_of(Aliases, [&](StringRef Alias) {383 auto It = FunctionNameToDIFilename.find(Alias);384 // No match if this function name is not found in this module.385 if (It == FunctionNameToDIFilename.end())386 return false;387 // Return a match if debug-info-filename is not specified. Otherwise,388 // check for equality.389 return DIFilename.empty() || It->second == DIFilename;390 });391 if (!FunctionFound) {392 // Skip the following profile by setting the profile iterator (FI) to393 // the past-the-end element.394 FI = ProgramPathAndClusterInfo.end();395 continue;396 }397 for (size_t i = 1; i < Aliases.size(); ++i)398 FuncAliasMap.try_emplace(Aliases[i], Aliases.front());399 400 // Prepare for parsing clusters of this function name.401 // Start a new cluster map for this function name.402 auto R = ProgramPathAndClusterInfo.try_emplace(Aliases.front());403 // Report error when multiple profiles have been specified for the same404 // function.405 if (!R.second)406 return createProfileParseError("duplicate profile for function '" +407 Aliases.front() + "'");408 FI = R.first;409 CurrentCluster = 0;410 FuncBBIDs.clear();411 }412 }413 return Error::success();414}415 416// Basic Block Sections can be enabled for a subset of machine basic blocks.417// This is done by passing a file containing names of functions for which basic418// block sections are desired. Additionally, machine basic block ids of the419// functions can also be specified for a finer granularity. Moreover, a cluster420// of basic blocks could be assigned to the same section.421// Optionally, a debug-info filename can be specified for each function to allow422// distinguishing internal-linkage functions of the same name.423// A file with basic block sections for all of function main and three blocks424// for function foo (of which 1 and 2 are placed in a cluster) looks like this:425// (Profile for function foo is only loaded when its debug-info filename426// matches 'path/to/foo_file.cc').427// ----------------------------428// list.txt:429// !main430// !foo M=path/to/foo_file.cc431// !!1 2432// !!4433Error BasicBlockSectionsProfileReader::ReadProfile() {434 assert(MBuf);435 436 unsigned long long Version = 0;437 StringRef FirstLine(*LineIt);438 if (FirstLine.consume_front("v")) {439 if (getAsUnsignedInteger(FirstLine, 10, Version)) {440 return createProfileParseError(Twine("version number expected: '") +441 FirstLine + "'");442 }443 if (Version > 1) {444 return createProfileParseError(Twine("invalid profile version: ") +445 Twine(Version));446 }447 ++LineIt;448 }449 450 switch (Version) {451 case 0:452 // TODO: Deprecate V0 once V1 is fully integrated downstream.453 return ReadV0Profile();454 case 1:455 return ReadV1Profile();456 default:457 llvm_unreachable("Invalid profile version.");458 }459}460 461bool BasicBlockSectionsProfileReaderWrapperPass::doInitialization(Module &M) {462 if (!BBSPR.MBuf)463 return false;464 // Get the function name to debug info filename mapping.465 BBSPR.FunctionNameToDIFilename.clear();466 for (const Function &F : M) {467 SmallString<128> DIFilename;468 if (F.isDeclaration())469 continue;470 DISubprogram *Subprogram = F.getSubprogram();471 if (Subprogram) {472 llvm::DICompileUnit *CU = Subprogram->getUnit();473 if (CU)474 DIFilename = sys::path::remove_leading_dotslash(CU->getFilename());475 }476 [[maybe_unused]] bool inserted =477 BBSPR.FunctionNameToDIFilename.try_emplace(F.getName(), DIFilename)478 .second;479 assert(inserted);480 }481 if (auto Err = BBSPR.ReadProfile())482 report_fatal_error(std::move(Err));483 return false;484}485 486AnalysisKey BasicBlockSectionsProfileReaderAnalysis::Key;487 488BasicBlockSectionsProfileReader489BasicBlockSectionsProfileReaderAnalysis::run(Function &F,490 FunctionAnalysisManager &AM) {491 return BasicBlockSectionsProfileReader(TM->getBBSectionsFuncListBuf());492}493 494bool BasicBlockSectionsProfileReaderWrapperPass::isFunctionHot(495 StringRef FuncName) const {496 return BBSPR.isFunctionHot(FuncName);497}498 499SmallVector<BBClusterInfo>500BasicBlockSectionsProfileReaderWrapperPass::getClusterInfoForFunction(501 StringRef FuncName) const {502 return BBSPR.getClusterInfoForFunction(FuncName);503}504 505SmallVector<SmallVector<unsigned>>506BasicBlockSectionsProfileReaderWrapperPass::getClonePathsForFunction(507 StringRef FuncName) const {508 return BBSPR.getClonePathsForFunction(FuncName);509}510 511uint64_t BasicBlockSectionsProfileReaderWrapperPass::getEdgeCount(512 StringRef FuncName, const UniqueBBID &SrcBBID,513 const UniqueBBID &SinkBBID) const {514 return BBSPR.getEdgeCount(FuncName, SrcBBID, SinkBBID);515}516 517BasicBlockSectionsProfileReader &518BasicBlockSectionsProfileReaderWrapperPass::getBBSPR() {519 return BBSPR;520}521 522ImmutablePass *llvm::createBasicBlockSectionsProfileReaderWrapperPass(523 const MemoryBuffer *Buf) {524 return new BasicBlockSectionsProfileReaderWrapperPass(Buf);525}526