llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-lld-elf Author: None (wdx727) <details> <summary>Changes</summary> We would like to add the matching and inference functionality to Propeller to address the issue that Propeller has zero tolerance for changes in source code and compilation parameters. The complete RFC can be found at the following URL: https://discourse.llvm.org/t/rfc-adding-matching-and-inference-functionality-to-propeller/86238/1. --- Patch is 110.85 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/139008.diff 53 Files Affected: - (modified) clang/include/clang/Basic/CodeGenOptions.h (+3) - (modified) clang/include/clang/Driver/Options.td (+5) - (modified) clang/lib/CodeGen/BackendUtil.cpp (+21-7) - (modified) clang/lib/Driver/ToolChains/Clang.cpp (+12) - (modified) lld/ELF/Config.h (+1) - (modified) lld/ELF/Driver.cpp (+77) - (modified) lld/ELF/LTO.cpp (+1) - (modified) lld/ELF/Options.td (+3) - (added) llvm/include/llvm/CodeGen/FuncHotBBHashesProfileReader.h (+64) - (added) llvm/include/llvm/CodeGen/HotMachineBasicBlockInfoGenerator.h (+51) - (added) llvm/include/llvm/CodeGen/MachineBlockHashInfo.h (+108) - (modified) llvm/include/llvm/CodeGen/Passes.h (+4) - (modified) llvm/include/llvm/InitializePasses.h (+3) - (modified) llvm/include/llvm/LTO/Config.h (+3) - (modified) llvm/include/llvm/Object/ELFTypes.h (+3-2) - (modified) llvm/include/llvm/ObjectYAML/ELFYAML.h (+1) - (modified) llvm/include/llvm/Support/PGOOptions.h (+2) - (modified) llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp (+6) - (modified) llvm/lib/CodeGen/BasicBlockSections.cpp (+43-4) - (modified) llvm/lib/CodeGen/CMakeLists.txt (+3) - (modified) llvm/lib/CodeGen/CodeGen.cpp (+3) - (added) llvm/lib/CodeGen/FuncHotBBHashesProfileReader.cpp (+123) - (added) llvm/lib/CodeGen/HotMachineBasicBlockInfoGenerator.cpp (+202) - (added) llvm/lib/CodeGen/MachineBlockHashInfo.cpp (+104) - (modified) llvm/lib/CodeGen/TargetPassConfig.cpp (+12-1) - (modified) llvm/lib/LTO/LTOBackend.cpp (+15-9) - (modified) llvm/lib/Object/ELF.cpp (+2-1) - (modified) llvm/lib/ObjectYAML/ELFEmitter.cpp (+1) - (modified) llvm/lib/ObjectYAML/ELFYAML.cpp (+1) - (modified) llvm/lib/Support/PGOOptions.cpp (+6-4) - (modified) llvm/test/CodeGen/AArch64/O0-pipeline.ll (+1) - (modified) llvm/test/CodeGen/AArch64/O3-pipeline.ll (+1) - (modified) llvm/test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll (+2) - (modified) llvm/test/CodeGen/X86/O0-pipeline.ll (+1) - (modified) llvm/test/CodeGen/X86/basic-block-address-map-pgo-features.ll (+6) - (modified) llvm/test/CodeGen/X86/basic-block-address-map-with-basic-block-sections.ll (+4-1) - (modified) llvm/test/CodeGen/X86/basic-block-address-map-with-mfs.ll (+3) - (modified) llvm/test/CodeGen/X86/basic-block-address-map.ll (+7-1) - (modified) llvm/test/CodeGen/X86/opt-pipeline.ll (+1) - (modified) llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml (+18) - (modified) llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-symbolize-relocatable.yaml (+7-3) - (modified) llvm/test/tools/llvm-objdump/X86/elf-pgoanalysismap.yaml (+9) - (modified) llvm/test/tools/llvm-readobj/ELF/bb-addr-map-pgo-analysis-map.test (+13-3) - (modified) llvm/test/tools/llvm-readobj/ELF/bb-addr-map-relocatable.test (+10-1) - (modified) llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test (+12-2) - (modified) llvm/test/tools/obj2yaml/ELF/bb-addr-map-pgo-analysis-map.yaml (+10) - (modified) llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml (+10) - (modified) llvm/test/tools/yaml2obj/ELF/bb-addr-map-pgo-analysis-map.yaml (+6-3) - (modified) llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml (+6-3) - (modified) llvm/tools/llvm-readobj/ELFDumper.cpp (+1) - (modified) llvm/tools/obj2yaml/elf2yaml.cpp (+2-1) - (modified) llvm/tools/opt/NewPMDriver.cpp (+15-8) - (modified) llvm/unittests/Object/ELFObjectFileTest.cpp (+58-29) ``````````diff diff --git a/clang/include/clang/Basic/CodeGenOptions.h b/clang/include/clang/Basic/CodeGenOptions.h index e3fa6a55e7608..46ea2ba3a4c56 100644 --- a/clang/include/clang/Basic/CodeGenOptions.h +++ b/clang/include/clang/Basic/CodeGenOptions.h @@ -288,6 +288,9 @@ class CodeGenOptions : public CodeGenOptionsBase { /// Name of the profile file to use with -fprofile-sample-use. std::string SampleProfileFile; + /// Name of the profile file to use with -fpropeller-profile-use. + std::string PropellerProfileFile; + /// Name of the profile file to use as output for with -fmemory-profile. std::string MemoryProfileOutput; diff --git a/clang/include/clang/Driver/Options.td b/clang/include/clang/Driver/Options.td index 351e1ad4e1b03..add5ecc506fa1 100644 --- a/clang/include/clang/Driver/Options.td +++ b/clang/include/clang/Driver/Options.td @@ -1688,6 +1688,11 @@ def fprofile_sample_accurate : Flag<["-"], "fprofile-sample-accurate">, as cold. Otherwise, treat callsites without profile samples as if we have no profile}]>, MarshallingInfoFlag<CodeGenOpts<"ProfileSampleAccurate">>; +def fpropeller_profile_use_EQ : Joined<["-"], "fpropeller-profile-use=">, + Group<f_Group>, Visibility<[ClangOption, CC1Option, CLOption]>, + MetaVarName<"<pathname>">, + HelpText<"Use propeller profile for profile-guided optimization">, + MarshallingInfoString<CodeGenOpts<"PropellerProfileFile">>; def fsample_profile_use_profi : Flag<["-"], "fsample-profile-use-profi">, Visibility<[ClangOption, CC1Option]>, Group<f_Group>, diff --git a/clang/lib/CodeGen/BackendUtil.cpp b/clang/lib/CodeGen/BackendUtil.cpp index 42c59377688b2..4f5f5f677c5c6 100644 --- a/clang/lib/CodeGen/BackendUtil.cpp +++ b/clang/lib/CodeGen/BackendUtil.cpp @@ -837,7 +837,8 @@ void EmitAssemblyHelper::RunOptimizationPipeline( if (CodeGenOpts.hasProfileIRInstr()) // -fprofile-generate. PGOOpt = PGOOptions(getProfileGenName(CodeGenOpts), "", "", - CodeGenOpts.MemoryProfileUsePath, nullptr, + CodeGenOpts.MemoryProfileUsePath, + CodeGenOpts.PropellerProfileFile, nullptr, PGOOptions::IRInstr, PGOOptions::NoCSAction, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling, /*PseudoProbeForProfiling=*/false, @@ -848,30 +849,41 @@ void EmitAssemblyHelper::RunOptimizationPipeline( : PGOOptions::NoCSAction; PGOOpt = PGOOptions(CodeGenOpts.ProfileInstrumentUsePath, "", CodeGenOpts.ProfileRemappingFile, - CodeGenOpts.MemoryProfileUsePath, VFS, + CodeGenOpts.MemoryProfileUsePath, + CodeGenOpts.PropellerProfileFile, VFS, PGOOptions::IRUse, CSAction, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling); } else if (!CodeGenOpts.SampleProfileFile.empty()) // -fprofile-sample-use PGOOpt = PGOOptions( CodeGenOpts.SampleProfileFile, "", CodeGenOpts.ProfileRemappingFile, - CodeGenOpts.MemoryProfileUsePath, VFS, PGOOptions::SampleUse, + CodeGenOpts.MemoryProfileUsePath, + CodeGenOpts.PropellerProfileFile, VFS, PGOOptions::SampleUse, PGOOptions::NoCSAction, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling, CodeGenOpts.PseudoProbeForProfiling); else if (!CodeGenOpts.MemoryProfileUsePath.empty()) // -fmemory-profile-use (without any of the above options) - PGOOpt = PGOOptions("", "", "", CodeGenOpts.MemoryProfileUsePath, VFS, + PGOOpt = PGOOptions("", "", "", CodeGenOpts.MemoryProfileUsePath, + CodeGenOpts.PropellerProfileFile, VFS, PGOOptions::NoAction, PGOOptions::NoCSAction, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling); + else if (!CodeGenOpts.PropellerProfileFile.empty()) + // -fpropeller-profile-use (without any of the above options) + PGOOpt = PGOOptions("", "", "", "", + CodeGenOpts.PropellerProfileFile, VFS, + PGOOptions::NoAction, PGOOptions::NoCSAction, + ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling); else if (CodeGenOpts.PseudoProbeForProfiling) // -fpseudo-probe-for-profiling PGOOpt = - PGOOptions("", "", "", /*MemoryProfile=*/"", nullptr, + PGOOptions("", "", "", /*MemoryProfile=*/"", + /*PropellerProfileFile=*/"", nullptr, PGOOptions::NoAction, PGOOptions::NoCSAction, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling, true); else if (CodeGenOpts.DebugInfoForProfiling) // -fdebug-info-for-profiling - PGOOpt = PGOOptions("", "", "", /*MemoryProfile=*/"", nullptr, + PGOOpt = PGOOptions("", "", "", /*MemoryProfile=*/"", + /*PropellerProfileFile=*/"", nullptr, PGOOptions::NoAction, PGOOptions::NoCSAction, ClPGOColdFuncAttr, true); @@ -889,7 +901,8 @@ void EmitAssemblyHelper::RunOptimizationPipeline( PGOOpt->CSAction = PGOOptions::CSIRInstr; } else PGOOpt = PGOOptions("", getProfileGenName(CodeGenOpts), "", - /*MemoryProfile=*/"", nullptr, PGOOptions::NoAction, + /*MemoryProfile=*/"", /*PropellerProfileFile=*/"", + nullptr, PGOOptions::NoAction, PGOOptions::CSIRInstr, ClPGOColdFuncAttr, CodeGenOpts.DebugInfoForProfiling); } @@ -1338,6 +1351,7 @@ runThinLTOBackend(CompilerInstance &CI, ModuleSummaryIndex *CombinedIndex, Conf.OptLevel = CGOpts.OptimizationLevel; initTargetOptions(CI, Diags, Conf.Options); Conf.SampleProfile = std::move(SampleProfile); + Conf.PropellerProfile = CGOpts.PropellerProfileFile; Conf.PTO.LoopUnrolling = CGOpts.UnrollLoops; Conf.PTO.LoopInterchange = CGOpts.InterchangeLoops; // For historical reasons, loop interleaving is set to mirror setting for loop diff --git a/clang/lib/Driver/ToolChains/Clang.cpp b/clang/lib/Driver/ToolChains/Clang.cpp index f87549baff5e1..4ed102eb77c97 100644 --- a/clang/lib/Driver/ToolChains/Clang.cpp +++ b/clang/lib/Driver/ToolChains/Clang.cpp @@ -6418,6 +6418,18 @@ void Clang::ConstructJob(Compilation &C, const JobAction &JA, CmdArgs.push_back("-sample-profile-use-profi"); } + if (auto *PropellerUseArg = + Args.getLastArg(options::OPT_fpropeller_profile_use_EQ)) { + if (Arg *A = Args.getLastArg(options::OPT_fbasic_block_sections_EQ)) { + StringRef Val = A->getValue(); + if (Val.starts_with("list=")) + D.Diag(diag::err_drv_argument_not_allowed_with) + << PropellerUseArg->getAsString(Args) + << "-fbasic-block-sections=list"; + } + PropellerUseArg->render(Args, CmdArgs); + } + // Add runtime flag for PS4/PS5 when PGO, coverage, or sanitizers are enabled. if (RawTriple.isPS() && !Args.hasArg(options::OPT_nostdlib, options::OPT_nodefaultlibs)) { diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h index f0e9592d85dd6..8de8d65b8a0d1 100644 --- a/lld/ELF/Config.h +++ b/lld/ELF/Config.h @@ -211,6 +211,7 @@ struct Config { llvm::StringRef ltoNewPmPasses; llvm::StringRef ltoObjPath; llvm::StringRef ltoSampleProfile; + llvm::StringRef ltoPropellerProfile; llvm::StringRef mapFile; llvm::StringRef outputFile; llvm::StringRef optRemarksFilename; diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp index e8acdbefa32bb..eb7730da1956a 100644 --- a/lld/ELF/Driver.cpp +++ b/lld/ELF/Driver.cpp @@ -1245,6 +1245,73 @@ static SmallVector<StringRef, 0> getSymbolOrderingFile(Ctx &ctx, return names.takeVector(); } +struct HotBBInfo{ + uint32_t TotalBBSize = 0; + uint32_t HotBBSize = 0; +}; +static SmallVector<StringRef, 0> generateSymbolOrderingFromPropellerProfile(MemoryBufferRef mb) { + SmallVector<std::pair<StringRef, HotBBInfo>> names; + SmallVector<HotBBInfo *> hotBBInfos; + uint32_t line = 0; + for (StringRef s : args::getLines(mb)) { + line++; + if (!s.consume_front("!") || s.empty()) { + error("invalid propeller profile at line: " + Twine(line)); + } + if (s.consume_front("!")) { + SmallVector<StringRef, 3> HotBB; + s.split(HotBB, ' '); + if (HotBB.size() != 3) + error("invalid propeller profile at line: " + Twine(line)); + HotBB[0].consume_front("0x"); + unsigned long long Hash, Freq, BBID; + if (getAsUnsignedInteger(HotBB[0], 16, Hash)) + error("invalid propeller profile at line: " + Twine(line)); + if (getAsUnsignedInteger(HotBB[1], 10, Freq)) + error("invalid propeller profile at line: " + Twine(line)); + if (getAsUnsignedInteger(HotBB[2], 10, BBID)) + error("invalid propeller profile at line: " + Twine(line)); + if (Freq > 0 || BBID == 0) { + for (auto hotBBInfo : hotBBInfos) { + hotBBInfo->HotBBSize++; + } + } + } + else { + hotBBInfos.clear(); + SmallVector<StringRef, 2> NamesWithTotalBBSize; + s.split(NamesWithTotalBBSize, ' '); + if (NamesWithTotalBBSize.size() != 2) + error("invalid propeller profile at line: " + Twine(line)); + unsigned long long TotalBBSize; + if (getAsUnsignedInteger(NamesWithTotalBBSize[1], 10, TotalBBSize)) + error("invalid propeller profile at line: " + Twine(line)); + SmallVector<StringRef> funcNames; + NamesWithTotalBBSize[0].split(funcNames, '/'); + for (auto funcName : funcNames) { + names.push_back({funcName, {static_cast<uint32_t>(TotalBBSize), 0}}); + hotBBInfos.push_back(&names.back().second); + } + } + } + SmallVector<StringRef, 0> symorders; + static std::vector<std::string> storedStrings; + for (auto item : names) { + if (item.second.HotBBSize > 0) { + symorders.push_back(item.first); + } + } + for (auto item : names) { + if (item.second.HotBBSize != item.second.TotalBBSize) { + std::string str(item.first.str()); + str.append(".cold"); + storedStrings.push_back(str); + symorders.emplace_back(storedStrings.back()); + } + } + return symorders; +} + static bool getIsRela(Ctx &ctx, opt::InputArgList &args) { // The psABI specifies the default relocation entry format. bool rela = is_contained({EM_AARCH64, EM_AMDGPU, EM_HEXAGON, EM_LOONGARCH, @@ -1848,6 +1915,16 @@ static void readConfigs(Ctx &ctx, opt::InputArgList &args) { ctx.arg.symbolOrderingFile = getSymbolOrderingFile(ctx, *buffer); } + if (auto *arg = args.getLastArg(OPT_propeller_profile_use)){ + if (args.hasArg(OPT_call_graph_ordering_file) || args.hasArg(OPT_symbol_ordering_file)) + error("--propeller-profile-use and --symbol-ordering-file and --call-graph-order-file " + "may not be used together"); + if (auto buffer = readFile(ctx, arg->getValue())) { + ctx.arg.ltoPropellerProfile = arg->getValue(); + ctx.arg.symbolOrderingFile = generateSymbolOrderingFromPropellerProfile(*buffer); + } + } + assert(ctx.arg.versionDefinitions.empty()); ctx.arg.versionDefinitions.push_back( {"local", (uint16_t)VER_NDX_LOCAL, {}, {}}); diff --git a/lld/ELF/LTO.cpp b/lld/ELF/LTO.cpp index 195526bf390d2..c91b5f7748f8d 100644 --- a/lld/ELF/LTO.cpp +++ b/lld/ELF/LTO.cpp @@ -128,6 +128,7 @@ static lto::Config createConfig(Ctx &ctx) { c.StatsFile = std::string(ctx.arg.optStatsFilename); c.SampleProfile = std::string(ctx.arg.ltoSampleProfile); + c.PropellerProfile = std::string(ctx.arg.ltoPropellerProfile); for (StringRef pluginFn : ctx.arg.passPlugins) c.PassPlugins.push_back(std::string(pluginFn)); c.DebugPassManager = ctx.arg.ltoDebugPassManager; diff --git a/lld/ELF/Options.td b/lld/ELF/Options.td index 76d28096f82c8..dd4c9d2226fbe 100644 --- a/lld/ELF/Options.td +++ b/lld/ELF/Options.td @@ -408,6 +408,9 @@ def print_map: F<"print-map">, def print_memory_usage: F<"print-memory-usage">, HelpText<"Report target memory usage">; +defm propeller_profile_use: + EEq<"propeller-profile-use", "Propeller profile file used to reorder symorder">; + defm relax: BB<"relax", "Enable target-specific relaxations if supported (default)", "Disable target-specific relaxations">; diff --git a/llvm/include/llvm/CodeGen/FuncHotBBHashesProfileReader.h b/llvm/include/llvm/CodeGen/FuncHotBBHashesProfileReader.h new file mode 100644 index 0000000000000..87ac370366f1b --- /dev/null +++ b/llvm/include/llvm/CodeGen/FuncHotBBHashesProfileReader.h @@ -0,0 +1,64 @@ +#ifndef LLVM_CODEGEN_FuncHotBBHashesProfileReader_H +#define LLVM_CODEGEN_FuncHotBBHashesProfileReader_H + +#include "llvm/ADT/SmallString.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/MemoryBuffer.h" + +namespace llvm { + +struct HotBBInfo { + uint64_t BBHash; + uint64_t Freq; +}; + +class FuncHotBBHashesProfileReader : public ImmutablePass { +public: + static char ID; + + FuncHotBBHashesProfileReader(const std::string PropellerProfile); + + FuncHotBBHashesProfileReader(); + + StringRef getPassName() const override { + return "Basic Block Frequency with Hash Profile Reader"; + } + + // return a vector of hit BB hashes for a function. + std::pair<bool, SmallVector<HotBBInfo, 4>> + getHotBBInfosForFunction(StringRef FuncName) const; + + // Reads the profile for matching functions. + bool doInitialization(Module &M) override; + +private: + std::unique_ptr<MemoryBuffer> MBuf; + + StringRef getAliasName(StringRef FuncName) const { + auto R = FuncAliasMap.find(FuncName); + return R == FuncAliasMap.end() ? FuncName : R->second; + } + + // Reads the basic block frequency with hash profile for functions in this module. + Error ReadProfile(); + + // Profile file path. + std::string PropellerFilePath; + + // Some functions have alias names. We use this map to find the main alias + // name for which we have mapping in ProgramBBClusterInfo. + StringMap<StringRef> FuncAliasMap; + + // record the frequency of basic block, + // the basic block is represented by its hash. + StringMap<SmallVector<HotBBInfo, 4>> FuncToHotBBHashes; +}; + +ImmutablePass * +createFuncHotBBHashesProfileReaderPass(const std::string PropellerProfile); + +} // namespace llvm + +#endif // LLVM_CODEGEN_FuncHotBBHashesProfileReader_H \ No newline at end of file diff --git a/llvm/include/llvm/CodeGen/HotMachineBasicBlockInfoGenerator.h b/llvm/include/llvm/CodeGen/HotMachineBasicBlockInfoGenerator.h new file mode 100644 index 0000000000000..d9f0c21100531 --- /dev/null +++ b/llvm/include/llvm/CodeGen/HotMachineBasicBlockInfoGenerator.h @@ -0,0 +1,51 @@ +#ifndef LLVM_CODEGEN_HotMachineBasicBlockInfoGenerator_H +#define LLVM_CODEGEN_HotMachineBasicBlockInfoGenerator_H + +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Transforms/Utils/SampleProfileInference.h" +#include "llvm/CodeGen/FuncHotBBHashesProfileReader.h" + +namespace llvm { + +class HotMachineBasicBlockInfoGenerator : public MachineFunctionPass { +public: + static char ID; + HotMachineBasicBlockInfoGenerator(); + + StringRef getPassName() const override { + return "Basic Block Matching and Inference"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + bool runOnMachineFunction(MachineFunction &F) override; + + std::optional<SmallVector<MachineBasicBlock *, 4>> getHotMBBs(StringRef FuncName) const; + +private: + using Edge = std::pair<const MachineBasicBlock *, const MachineBasicBlock *>; + using BlockWeightMap = DenseMap<const MachineBasicBlock *, uint64_t>; + using EdgeWeightMap = DenseMap<Edge, uint64_t>; + using BlockEdgeMap = + DenseMap<const MachineBasicBlock *, SmallVector<const MachineBasicBlock *, 8>>; + + DenseMap<StringRef, SmallVector<MachineBasicBlock *, 4>> FuncToHotMBBs; + + void matchHotBBsByHashes( + MachineFunction &MF, + SmallVector<HotBBInfo, 4> &HotMBBInfos, + BlockWeightMap &MBBToFreq, + BlockEdgeMap &Successors, + SmallVector<MachineBasicBlock *, 4> &HotBBs); + + void generateHotBBsforFunction( + MachineFunction &MF, + BlockWeightMap &OriBlockWeights, + BlockWeightMap &BlockWeights, + EdgeWeightMap &EdgeWeights, + SmallVector<MachineBasicBlock *, 4> &HotBBs); +}; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_HotMachineBasicBlockInfoGenerator_H \ No newline at end of file diff --git a/llvm/include/llvm/CodeGen/MachineBlockHashInfo.h b/llvm/include/llvm/CodeGen/MachineBlockHashInfo.h new file mode 100644 index 0000000000000..a943f71357e6e --- /dev/null +++ b/llvm/include/llvm/CodeGen/MachineBlockHashInfo.h @@ -0,0 +1,108 @@ +#ifndef LLVM_CODEGEN_MACHINEBLOCKHASHINFO_H +#define LLVM_CODEGEN_MACHINEBLOCKHASHINFO_H + +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +/// An object wrapping several components of a basic block hash. The combined +/// (blended) hash is represented and stored as one uint64_t, while individual +/// components are of smaller size (e.g., uint16_t or uint8_t). +struct BlendedBlockHash { +private: + static uint64_t combineHashes(uint16_t Hash1, uint16_t Hash2, uint16_t Hash3, + uint16_t Hash4) { + uint64_t Hash = 0; + + Hash |= uint64_t(Hash4); + Hash <<= 16; + + Hash |= uint64_t(Hash3); + Hash <<= 16; + + Hash |= uint64_t(Hash2); + Hash <<= 16; + + Hash |= uint64_t(Hash1); + + return Hash; + } + + static void parseHashes(uint64_t Hash, uint16_t &Hash1, uint16_t &Hash2, + uint16_t &Hash3, uint16_t &Hash4) { + Hash1 = Hash & 0xffff; + Hash >>= 16; + + Hash2 = Hash & 0xffff; + Hash >>= 16; + + Hash3 = Hash & 0xffff; + Hash >>= 16; + + Hash4 = Hash & 0xffff; + Hash >>= 16; + } + +public: + explicit BlendedBlockHash() {} + + explicit BlendedBlockHash(uint64_t CombinedHash) { + parseHashes(CombinedHash, Offset, OpcodeHash, InstrHash, NeighborHash); + } + + /// Combine the blended hash into uint64_t. + uint64_t combine() const { + return combineHashes(Offset, OpcodeHash, InstrHash, NeighborHash); + } + + /// Compute a distance between two given blended hashes. The smaller the + /// distance, the more similar two blocks are. For identical basic blocks, + /// the distance is zero. + uint64_t distance(const BlendedBlockHash &BBH) const { + assert(OpcodeHash == BBH.OpcodeHash && + "incorrect blended hash distance computation"); + uint64_t Dist = 0; + // Account for NeighborHash + Dist += NeighborHash == BBH.NeighborHash ? 0 : 1; + Dist <<= 16; + // Account for InstrHash + Dist += InstrHash == BBH.InstrHash ? 0 : 1; + Dist <<= 16; + // Account for Offset + Dist += (Offset >= BBH.Offset ? Offset - BBH.Offset : BBH.Offset - Offset); + return Dist; + } + + /// The offset of the basic block from the function start. + uint16_t Offset{0}; + /// (Loose) Hash of the basic block instructions, excluding operands. + uint16_t OpcodeHash{0}; + /// (Strong) Hash of the basic block instructions, including opcodes and + /// operands. + uint16_t InstrHash{0}; + /// Hash of the (loose) basic block together with (loose) hashes of its + /// successors and predecessors. + uint16_t NeighborHash{0}; +}; + +class MachineBlockHashInfo : public MachineFunctionPass { + DenseMap<unsigned, uint64_t> MBBHashInfo; + +public: + static char ID; + MachineBlockHashInfo(); + + StringRef getPassName() const override { + return "Basic Block Hash Compute"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + bool runOnMachineFunction(MachineFunction &F) override; + + uint64_t getMBBHash(const MachineBasicBlock &MBB); +}; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_MACHINEBLOCKHASHINFO_H \ No newline at end of file diff --git a/llvm/include/llvm/CodeGen/Passes.h b/llvm/include/llvm/CodeGen/Passes.h index d214ab9306c2f..e8a8378257f2b 100644 --- a/llvm/include/llvm/CodeGen/Passes.h +++ b/llvm/include/llvm/CodeGen/Passes.h @@ -61,6 +61,10 @@ namespace llvm { /// This pass garbage-collects such basic blocks. MachineFunctionPass *createGCEmptyBasicBlocksPa... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/139008 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
