https://github.com/Lukasdoe updated https://github.com/llvm/llvm-project/pull/146230
From e4b0ccd8e1ac579066c559e890c3d610bbf226fc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Lukas=20D=C3=B6llerer?= <cont...@lukas-doellerer.de> Date: Wed, 2 Jul 2025 10:14:20 +0200 Subject: [PATCH] [LLVM][WebAssembly] Implement branch hinting proposal This commit implements the WebAssembly branch hinting proposal, as detailed at https://webassembly.github.io/branch-hinting/metadata/code/binary.html. This proposal introduces a mechanism to convey branch likelihood information to the WebAssembly engine, allowing for more effective performance optimizations. The proposal specifies a new custom section named `metadata.code.branch_hint`. This section can contain a sequence of hints, where each hint is a single byte that applies to a corresponding `br_if` or `if` instruction. The hint values are: - `0x00` (`unlikely`): The branch is unlikely to be taken. - `0x01` (`likely`): The branch is likely to be taken. This implementation includes the following changes: - Addition of the "branch-hinting" feature (flag) - Collection of edge probabilities in CFGStackify pass - Outputting of `metadata.code.branch_hint` section in WebAssemblyAsmPrinter - Addition of the `WebAssembly::Specifier::S_DEBUG_REF` symbol ref specifier - Custom relaxation of leb128 fragments for storage of uleb128 encoded function indices and instruction offsets - Custom handling of code metadata sections in lld, required since the proposal requires code metadata sections to start with a combined count of function hints, followed by an ordered list of function hints. This change is purely an optimization and does not alter the semantics of WebAssembly programs. --- clang/include/clang/Driver/Options.td | 2 + clang/lib/Basic/Targets/WebAssembly.cpp | 12 ++ clang/lib/Basic/Targets/WebAssembly.h | 1 + lld/test/wasm/code-metadata-branch-hints.ll | 115 ++++++++++++++++ lld/wasm/OutputSections.cpp | 56 ++++++++ lld/wasm/OutputSections.h | 9 ++ lld/wasm/SyntheticSections.h | 3 +- lld/wasm/Writer.cpp | 31 ++++- llvm/include/llvm/BinaryFormat/Wasm.h | 16 +++ llvm/include/llvm/Object/Wasm.h | 8 ++ llvm/include/llvm/ObjectYAML/WasmYAML.h | 44 ++++++ llvm/lib/Object/WasmObjectFile.cpp | 40 ++++++ llvm/lib/ObjectYAML/WasmYAML.cpp | 35 +++++ .../MCTargetDesc/WebAssemblyAsmBackend.cpp | 25 ++++ .../MCTargetDesc/WebAssemblyMCAsmInfo.cpp | 1 + .../MCTargetDesc/WebAssemblyMCAsmInfo.h | 1 + .../WebAssemblyWasmObjectWriter.cpp | 6 +- llvm/lib/Target/WebAssembly/WebAssembly.td | 12 +- .../WebAssembly/WebAssemblyAsmPrinter.cpp | 81 +++++++++++ .../WebAssembly/WebAssemblyAsmPrinter.h | 17 +++ .../WebAssembly/WebAssemblyCFGStackify.cpp | 19 +++ .../WebAssembly/WebAssemblyInstrInfo.td | 4 + .../WebAssemblyMachineFunctionInfo.h | 2 + .../Target/WebAssembly/WebAssemblySubtarget.h | 2 + .../WebAssembly/target-features-cpus.ll | 7 +- ...branch-hints-custom-high-low-thresholds.ll | 127 ++++++++++++++++++ llvm/test/MC/WebAssembly/branch-hints.ll | 122 +++++++++++++++++ llvm/tools/obj2yaml/wasm2yaml.cpp | 17 +++ 28 files changed, 803 insertions(+), 12 deletions(-) create mode 100644 lld/test/wasm/code-metadata-branch-hints.ll create mode 100644 llvm/test/MC/WebAssembly/branch-hints-custom-high-low-thresholds.ll create mode 100644 llvm/test/MC/WebAssembly/branch-hints.ll diff --git a/clang/include/clang/Driver/Options.td b/clang/include/clang/Driver/Options.td index 9911d752966e3..8778a7d7ab8a3 100644 --- a/clang/include/clang/Driver/Options.td +++ b/clang/include/clang/Driver/Options.td @@ -5244,6 +5244,8 @@ def mharden_sls_EQ : Joined<["-"], "mharden-sls=">, Group<m_Group>, def matomics : Flag<["-"], "matomics">, Group<m_wasm_Features_Group>; def mno_atomics : Flag<["-"], "mno-atomics">, Group<m_wasm_Features_Group>; +def mbranch_hinting : Flag<["-"], "mbranch-hinting">, Group<m_wasm_Features_Group>; +def mno_branch_hinting : Flag<["-"], "mno-branch-hinting">, Group<m_wasm_Features_Group>; def mbulk_memory : Flag<["-"], "mbulk-memory">, Group<m_wasm_Features_Group>; def mno_bulk_memory : Flag<["-"], "mno-bulk-memory">, Group<m_wasm_Features_Group>; def mbulk_memory_opt : Flag<["-"], "mbulk-memory-opt">, Group<m_wasm_Features_Group>; diff --git a/clang/lib/Basic/Targets/WebAssembly.cpp b/clang/lib/Basic/Targets/WebAssembly.cpp index f19c57f1a3a50..2436d8d5e336e 100644 --- a/clang/lib/Basic/Targets/WebAssembly.cpp +++ b/clang/lib/Basic/Targets/WebAssembly.cpp @@ -53,6 +53,7 @@ bool WebAssemblyTargetInfo::setABI(const std::string &Name) { bool WebAssemblyTargetInfo::hasFeature(StringRef Feature) const { return llvm::StringSwitch<bool>(Feature) .Case("atomics", HasAtomics) + .Case("branch-hinting", HasBranchHinting) .Case("bulk-memory", HasBulkMemory) .Case("bulk-memory-opt", HasBulkMemoryOpt) .Case("call-indirect-overlong", HasCallIndirectOverlong) @@ -86,6 +87,8 @@ void WebAssemblyTargetInfo::getTargetDefines(const LangOptions &Opts, defineCPUMacros(Builder, "wasm", /*Tuning=*/false); if (HasAtomics) Builder.defineMacro("__wasm_atomics__"); + if (HasBranchHinting) + Builder.defineMacro("__wasm_branch_hinting__"); if (HasBulkMemory) Builder.defineMacro("__wasm_bulk_memory__"); if (HasBulkMemoryOpt) @@ -188,6 +191,7 @@ bool WebAssemblyTargetInfo::initFeatureMap( auto addBleedingEdgeFeatures = [&]() { addGenericFeatures(); Features["atomics"] = true; + Features["branch-hinting"] = true; Features["exception-handling"] = true; Features["extended-const"] = true; Features["fp16"] = true; @@ -218,6 +222,14 @@ bool WebAssemblyTargetInfo::handleTargetFeatures( HasAtomics = false; continue; } + if (Feature == "+branch-hinting") { + HasBranchHinting = true; + continue; + } + if (Feature == "-branch-hinting") { + HasBranchHinting = false; + continue; + } if (Feature == "+bulk-memory") { HasBulkMemory = true; continue; diff --git a/clang/lib/Basic/Targets/WebAssembly.h b/clang/lib/Basic/Targets/WebAssembly.h index d5aee5c0bd0eb..563c41144b190 100644 --- a/clang/lib/Basic/Targets/WebAssembly.h +++ b/clang/lib/Basic/Targets/WebAssembly.h @@ -58,6 +58,7 @@ class LLVM_LIBRARY_VISIBILITY WebAssemblyTargetInfo : public TargetInfo { } SIMDLevel = NoSIMD; bool HasAtomics = false; + bool HasBranchHinting = false; bool HasBulkMemory = false; bool HasBulkMemoryOpt = false; bool HasCallIndirectOverlong = false; diff --git a/lld/test/wasm/code-metadata-branch-hints.ll b/lld/test/wasm/code-metadata-branch-hints.ll new file mode 100644 index 0000000000000..68266e1de3975 --- /dev/null +++ b/lld/test/wasm/code-metadata-branch-hints.ll @@ -0,0 +1,115 @@ +# RUN: rm -rf %t; split-file %s %t +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %t/f1.ll -o %t/f1.o -mattr=+branch-hinting +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %t/f2.ll -o %t/f2.o -mattr=+branch-hinting +; RUN: wasm-ld --export-all -o %t.wasm %t/f2.o %t/f1.o +; RUN: obj2yaml %t.wasm | FileCheck --check-prefixes=CHECK %s + +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %t/f1.ll -o %t/f1.o -mattr=-branch-hinting +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %t/f2.ll -o %t/f2.o -mattr=-branch-hinting +; RUN: wasm-ld --export-all -o %t.wasm %t/f2.o %t/f1.o +; RUN: obj2yaml %t.wasm | FileCheck --check-prefixes=NCHECK %s + +; CHECK: - Type: CUSTOM +; CHECK: Name: metadata.code.branch_hint +; CHECK-NEXT: Entries: +; CHECK-NEXT: - FuncIdx: 1 +; CHECK-NEXT: Hints: +; CHECK-NEXT: - Offset: 7 +; CHECK-NEXT: Size: 1 +; CHECK-NEXT: Data: UNLIKELY +; CHECK-NEXT: - Offset: 14 +; CHECK-NEXT: Size: 1 +; CHECK-NEXT: Data: LIKELY +; CHECK-NEXT: - FuncIdx: 2 +; CHECK-NEXT: Hints: +; CHECK-NEXT: - Offset: 5 +; CHECK-NEXT: Size: 1 +; CHECK-NEXT: Data: LIKELY +; CHECK-NEXT: - FuncIdx: 3 +; CHECK-NEXT: Hints: +; CHECK-NEXT: - Offset: 5 +; CHECK-NEXT: Size: 1 +; CHECK-NEXT: Data: UNLIKELY +; CHECK-NEXT: - FuncIdx: 4 +; CHECK-NEXT: Hints: +; CHECK-NEXT: - Offset: 5 +; CHECK-NEXT: Size: 1 +; CHECK-NEXT: Data: LIKELY + +; CHECK: - Type: CUSTOM +; CHECK-NEXT: Name: name +; CHECK-NEXT: FunctionNames: +; CHECK-NEXT: - Index: 0 +; CHECK-NEXT: Name: __wasm_call_ctors +; CHECK-NEXT: - Index: 1 +; CHECK-NEXT: Name: test0 +; CHECK-NEXT: - Index: 2 +; CHECK-NEXT: Name: test1 +; CHECK-NEXT: - Index: 3 +; CHECK-NEXT: Name: _start +; CHECK-NEXT: - Index: 4 +; CHECK-NEXT: Name: test_func1 + +; CHECK: - Type: CUSTOM +; CHECK: Name: target_features +; CHECK-NEXT: Features: +; CHECK-NEXT: - Prefix: USED +; CHECK-NEXT: Name: branch-hinting + + +; NCHECK-NOT: Name: metadata.code.branch_hint +; NCHECK-NOT: Name: branch-hinting + +#--- f1.ll +define i32 @_start(i32 %a) { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %if.then, label %if.else, !prof !0 +if.then: + ret i32 1 +if.else: + ret i32 2 +} + +define i32 @test_func1(i32 %a) { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %if.then, label %if.else, !prof !1 +if.then: + ret i32 1 +if.else: + ret i32 2 +} + +!0 = !{!"branch_weights", i32 2000, i32 1} +!1 = !{!"branch_weights", i32 1, i32 2000} + +#--- f2.ll +target triple = "wasm32-unknown-unknown" + +define i32 @test0(i32 %a) { +entry: + %cmp0 = icmp eq i32 %a, 0 + br i1 %cmp0, label %if.then, label %ret1, !prof !0 +if.then: + %cmp1 = icmp eq i32 %a, 1 + br i1 %cmp1, label %ret1, label %ret2, !prof !1 +ret1: + ret i32 2 +ret2: + ret i32 1 +} + +define i32 @test1(i32 %a) { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %if.then, label %if.else, !prof !1 +if.then: + ret i32 1 +if.else: + ret i32 2 +} + +; the resulting branch hint is actually reversed, since llvm-br is turned into br_unless, inverting branch probs +!0 = !{!"branch_weights", i32 2000, i32 1} +!1 = !{!"branch_weights", i32 1, i32 2000} diff --git a/lld/wasm/OutputSections.cpp b/lld/wasm/OutputSections.cpp index 8ccd38f7895cb..c4fed3742dc6f 100644 --- a/lld/wasm/OutputSections.cpp +++ b/lld/wasm/OutputSections.cpp @@ -270,6 +270,62 @@ void CustomSection::writeTo(uint8_t *buf) { section->writeTo(buf); } +void CodeMetaDataSection::writeTo(uint8_t *buf) { + log("writing " + toString(*this) + " offset=" + Twine(offset) + + " size=" + Twine(getSize()) + " chunks=" + Twine(inputSections.size())); + + assert(offset); + buf += offset; + + // Write section header + memcpy(buf, header.data(), header.size()); + buf += header.size(); + memcpy(buf, nameData.data(), nameData.size()); + buf += nameData.size(); + + uint32_t TotalNumHints = 0; + for (const InputChunk *section : + make_range(inputSections.rbegin(), inputSections.rend())) { + section->writeTo(buf); + unsigned EncodingSize; + uint32_t NumHints = + decodeULEB128(buf + section->outSecOff, &EncodingSize, nullptr); + if (EncodingSize != 5) { + fatal("Unexpected encoding size for function hint vec size in " + name + + ": must be exactly 5 bytes."); + } + TotalNumHints += NumHints; + } + encodeULEB128(TotalNumHints, buf, 5); +} + +void CodeMetaDataSection::finalizeContents() { + finalizeInputSections(); + + raw_string_ostream os(nameData); + encodeULEB128(name.size(), os); + os << name; + + bool firstSection = true; + for (InputChunk *section : inputSections) { + assert(!section->discarded); + payloadSize = alignTo(payloadSize, section->alignment); + if (firstSection) { + section->outSecOff = payloadSize; + payloadSize += section->getSize(); + firstSection = false; + } else { + // adjust output offset so that each section write overwrites exactly the + // subsequent section's function hint vector size (which deduplicates) + section->outSecOff = payloadSize - 5; + // payload size should not include the hint vector size, which is deduped + payloadSize += section->getSize() - 5; + } + } + + createHeader(payloadSize + nameData.size()); +} + uint32_t CustomSection::getNumRelocations() const { uint32_t count = 0; for (const InputChunk *inputSect : inputSections) diff --git a/lld/wasm/OutputSections.h b/lld/wasm/OutputSections.h index 4b0329dd16cf2..6580c71ab6f5a 100644 --- a/lld/wasm/OutputSections.h +++ b/lld/wasm/OutputSections.h @@ -132,6 +132,15 @@ class CustomSection : public OutputSection { std::string nameData; }; +class CodeMetaDataSection : public CustomSection { +public: + CodeMetaDataSection(std::string name, ArrayRef<InputChunk *> inputSections) + : CustomSection(name, inputSections) {} + + void writeTo(uint8_t *buf) override; + void finalizeContents() override; +}; + } // namespace wasm } // namespace lld diff --git a/lld/wasm/SyntheticSections.h b/lld/wasm/SyntheticSections.h index 068fbed11f4a7..5592941a80cd4 100644 --- a/lld/wasm/SyntheticSections.h +++ b/lld/wasm/SyntheticSections.h @@ -43,7 +43,8 @@ class SyntheticSection : public OutputSection { void writeTo(uint8_t *buf) override { assert(offset); - log("writing " + toString(*this)); + log("writing " + toString(*this) + " offset=" + Twine(offset) + + " size=" + Twine(getSize())); memcpy(buf + offset, header.data(), header.size()); memcpy(buf + offset + header.size(), body.data(), body.size()); } diff --git a/lld/wasm/Writer.cpp b/lld/wasm/Writer.cpp index b704677d36c93..2944d060e7b0e 100644 --- a/lld/wasm/Writer.cpp +++ b/lld/wasm/Writer.cpp @@ -94,6 +94,8 @@ class Writer { void addSections(); void createCustomSections(); + // branch hint custom section must be placed before code section + void createBranchHintSection(); void createSyntheticSections(); void createSyntheticSectionsPostLayout(); void finalizeSections(); @@ -164,15 +166,34 @@ void Writer::createCustomSections() { log("createCustomSections"); for (auto &pair : customSectionMapping) { StringRef name = pair.first; + if (name == "metadata.code.branch_hint") { + // Branch hint section is created separately. + continue; + } LLVM_DEBUG(dbgs() << "createCustomSection: " << name << "\n"); + OutputSection *Sec = make<CustomSection>(std::string(name), pair.second); + if (ctx.arg.relocatable || ctx.arg.emitRelocs) { + auto *sym = make<OutputSectionSymbol>(Sec); + out.linkingSec->addToSymtab(sym); + Sec->sectionSym = sym; + } + addSection(Sec); + } +} - OutputSection *sec = make<CustomSection>(std::string(name), pair.second); +void Writer::createBranchHintSection() { + log("createBranchHintSection"); + std::string SectionName = "metadata.code.branch_hint"; + if (const auto &Ins = customSectionMapping.find(SectionName); + Ins != customSectionMapping.end()) { + OutputSection *Sec = + make<CodeMetaDataSection>(std::move(SectionName), Ins->second); if (ctx.arg.relocatable || ctx.arg.emitRelocs) { - auto *sym = make<OutputSectionSymbol>(sec); + auto *sym = make<OutputSectionSymbol>(Sec); out.linkingSec->addToSymtab(sym); - sec->sectionSym = sym; + Sec->sectionSym = sym; } - addSection(sec); + addSection(Sec); } } @@ -544,6 +565,8 @@ void Writer::addSections() { addSection(out.elemSec); addSection(out.dataCountSec); + createBranchHintSection(); + addSection(make<CodeSection>(out.functionSec->inputFunctions)); addSection(make<DataSection>(segments)); diff --git a/llvm/include/llvm/BinaryFormat/Wasm.h b/llvm/include/llvm/BinaryFormat/Wasm.h index 604104ff3cca3..3f6909888f080 100644 --- a/llvm/include/llvm/BinaryFormat/Wasm.h +++ b/llvm/include/llvm/BinaryFormat/Wasm.h @@ -517,6 +517,22 @@ struct WasmSignature { WasmSignature() = default; }; +template <typename T> struct WasmCodeMetadataItemEntry { + uint32_t Offset; + uint32_t Size; + T Data; +}; + +template <typename T> struct WasmCodeMetadataFuncEntry { + uint32_t FuncIdx; + std::vector<WasmCodeMetadataItemEntry<T>> Hints; +}; + +enum class WasmCodeMetadataBranchHint : uint8_t { + UNLIKELY = 0x0, + LIKELY = 0x1, +}; + // Useful comparison operators inline bool operator==(const WasmSignature &LHS, const WasmSignature &RHS) { return LHS.State == RHS.State && LHS.Returns == RHS.Returns && diff --git a/llvm/include/llvm/Object/Wasm.h b/llvm/include/llvm/Object/Wasm.h index b4ba50778c152..4a292446df957 100644 --- a/llvm/include/llvm/Object/Wasm.h +++ b/llvm/include/llvm/Object/Wasm.h @@ -142,6 +142,10 @@ class LLVM_ABI WasmObjectFile : public ObjectFile { ArrayRef<wasm::WasmFeatureEntry> getTargetFeatures() const { return TargetFeatures; } + ArrayRef<wasm::WasmCodeMetadataFuncEntry<wasm::WasmCodeMetadataBranchHint>> + getBranchHints() const { + return BranchHints; + } ArrayRef<wasm::WasmSignature> types() const { return Signatures; } ArrayRef<wasm::WasmImport> imports() const { return Imports; } ArrayRef<wasm::WasmTable> tables() const { return Tables; } @@ -275,12 +279,16 @@ class LLVM_ABI WasmObjectFile : public ObjectFile { Error parseProducersSection(ReadContext &Ctx); Error parseTargetFeaturesSection(ReadContext &Ctx); Error parseRelocSection(StringRef Name, ReadContext &Ctx); + Error parseCodeMetadataSection(StringRef Name, ReadContext &Ctx); + Error parseBranchHintSection(ReadContext &Ctx); wasm::WasmObjectHeader Header; std::vector<WasmSection> Sections; wasm::WasmDylinkInfo DylinkInfo; wasm::WasmProducerInfo ProducerInfo; std::vector<wasm::WasmFeatureEntry> TargetFeatures; + std::vector<wasm::WasmCodeMetadataFuncEntry<wasm::WasmCodeMetadataBranchHint>> + BranchHints; std::vector<wasm::WasmSignature> Signatures; std::vector<wasm::WasmTable> Tables; std::vector<wasm::WasmLimits> Memories; diff --git a/llvm/include/llvm/ObjectYAML/WasmYAML.h b/llvm/include/llvm/ObjectYAML/WasmYAML.h index b0ab04d1d8ac3..f1bb215c050ac 100644 --- a/llvm/include/llvm/ObjectYAML/WasmYAML.h +++ b/llvm/include/llvm/ObjectYAML/WasmYAML.h @@ -39,6 +39,7 @@ LLVM_YAML_STRONG_TYPEDEF(uint32_t, SegmentFlags) LLVM_YAML_STRONG_TYPEDEF(uint32_t, LimitFlags) LLVM_YAML_STRONG_TYPEDEF(uint32_t, ComdatKind) LLVM_YAML_STRONG_TYPEDEF(uint32_t, FeaturePolicyPrefix) +LLVM_YAML_STRONG_TYPEDEF(uint32_t, BranchHint) struct FileHeader { yaml::Hex32 Version; @@ -144,6 +145,17 @@ struct FeatureEntry { std::string Name; }; +template <typename T> struct CodeMetadataItemEntry { + uint32_t Offset; + uint32_t Size; + T Data; +}; + +template <typename T> struct CodeMetadataFuncEntry { + uint32_t FuncIdx; + std::vector<CodeMetadataItemEntry<T>> Hints; +}; + struct SegmentInfo { uint32_t Index; StringRef Name; @@ -286,6 +298,22 @@ struct TargetFeaturesSection : CustomSection { std::vector<FeatureEntry> Features; }; +template <typename T> struct CodeMetadataSection : CustomSection { + CodeMetadataSection(const StringRef Name) : CustomSection(Name) {} + std::vector<CodeMetadataFuncEntry<T>> Entries; +}; + +struct BranchHintSection : CodeMetadataSection<BranchHint> { + BranchHintSection() : CodeMetadataSection("metadata.code.branch_hint") {} + + static bool classof(const Section *S) { + auto C = dyn_cast<CustomSection>(S); + return C && C->Name == "metadata.code.branch_hint"; + } + + std::vector<CodeMetadataFuncEntry<BranchHint>> Entries; +}; + struct TypeSection : Section { TypeSection() : Section(wasm::WASM_SEC_TYPE) {} @@ -447,6 +475,10 @@ LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::ComdatEntry) LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::Comdat) LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::DylinkImportInfo) LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::DylinkExportInfo) +LLVM_YAML_IS_SEQUENCE_VECTOR( + llvm::WasmYAML::CodeMetadataItemEntry<llvm::WasmYAML::BranchHint>) +LLVM_YAML_IS_SEQUENCE_VECTOR( + llvm::WasmYAML::CodeMetadataFuncEntry<llvm::WasmYAML::BranchHint>) namespace llvm { namespace yaml { @@ -527,10 +559,22 @@ template <> struct ScalarEnumerationTraits<WasmYAML::FeaturePolicyPrefix> { static void enumeration(IO &IO, WasmYAML::FeaturePolicyPrefix &Prefix); }; +template <> struct ScalarEnumerationTraits<WasmYAML::BranchHint> { + static void enumeration(IO &IO, WasmYAML::BranchHint &BranchHint); +}; + template <> struct MappingTraits<WasmYAML::FeatureEntry> { static void mapping(IO &IO, WasmYAML::FeatureEntry &FeatureEntry); }; +template <typename T> struct MappingTraits<WasmYAML::CodeMetadataFuncEntry<T>> { + static void mapping(IO &IO, WasmYAML::CodeMetadataFuncEntry<T> &FuncEntry); +}; + +template <typename T> struct MappingTraits<WasmYAML::CodeMetadataItemEntry<T>> { + static void mapping(IO &IO, WasmYAML::CodeMetadataItemEntry<T> &ItemEntry); +}; + template <> struct MappingTraits<WasmYAML::SegmentInfo> { static void mapping(IO &IO, WasmYAML::SegmentInfo &SegmentInfo); }; diff --git a/llvm/lib/Object/WasmObjectFile.cpp b/llvm/lib/Object/WasmObjectFile.cpp index ee7a3068af91d..964c96712c1f4 100644 --- a/llvm/lib/Object/WasmObjectFile.cpp +++ b/llvm/lib/Object/WasmObjectFile.cpp @@ -1030,6 +1030,43 @@ Error WasmObjectFile::parseTargetFeaturesSection(ReadContext &Ctx) { return Error::success(); } +Error WasmObjectFile::parseCodeMetadataSection(StringRef Name, + ReadContext &Ctx) { + const auto HintTypeName = Name.substr(14 /* "code_metadata." */); + if (HintTypeName == "branch_hint") { + return parseBranchHintSection(Ctx); + } else { + return make_error<GenericBinaryError>( + "invalid code metadata section: " + Name, object_error::parse_failed); + } +} + +Error WasmObjectFile::parseBranchHintSection(ReadContext &Ctx) { + const uint32_t NumFuncs = readVaruint32(Ctx); + BranchHints.reserve(NumFuncs); + for (size_t i = 0; i < NumFuncs; ++i) { + wasm::WasmCodeMetadataFuncEntry<wasm::WasmCodeMetadataBranchHint> FuncEntry; + FuncEntry.FuncIdx = readVaruint32(Ctx); + const uint32_t NumHints = readVaruint32(Ctx); + for (size_t j = 0; j < NumHints; ++j) { + wasm::WasmCodeMetadataItemEntry<wasm::WasmCodeMetadataBranchHint> Hint; + Hint.Offset = readVaruint32(Ctx); + Hint.Size = readVaruint32(Ctx); + uint8_t Data = readUint8(Ctx); + if (Data > 0x1) + return make_error<GenericBinaryError>("invalid branch hint data", + object_error::parse_failed); + Hint.Data = static_cast<wasm::WasmCodeMetadataBranchHint>(Data); + FuncEntry.Hints.push_back(Hint); + } + BranchHints.push_back(std::move(FuncEntry)); + } + if (Ctx.Ptr != Ctx.End) + return make_error<GenericBinaryError>( + "branch hint section ended prematurely", object_error::parse_failed); + return Error::success(); +} + Error WasmObjectFile::parseRelocSection(StringRef Name, ReadContext &Ctx) { uint32_t SectionIndex = readVaruint32(Ctx); if (SectionIndex >= Sections.size()) @@ -1183,6 +1220,9 @@ Error WasmObjectFile::parseCustomSection(WasmSection &Sec, ReadContext &Ctx) { } else if (Sec.Name == "target_features") { if (Error Err = parseTargetFeaturesSection(Ctx)) return Err; + } else if (Sec.Name.starts_with("metadata.code.")) { + if (Error Err = parseCodeMetadataSection(Sec.Name, Ctx)) + return Err; } else if (Sec.Name.starts_with("reloc.")) { if (Error Err = parseRelocSection(Sec.Name, Ctx)) return Err; diff --git a/llvm/lib/ObjectYAML/WasmYAML.cpp b/llvm/lib/ObjectYAML/WasmYAML.cpp index edbcb3c6ead11..1bbb2d1598097 100644 --- a/llvm/lib/ObjectYAML/WasmYAML.cpp +++ b/llvm/lib/ObjectYAML/WasmYAML.cpp @@ -94,6 +94,12 @@ static void sectionMapping(IO &IO, WasmYAML::TargetFeaturesSection &Section) { IO.mapRequired("Features", Section.Features); } +static void sectionMapping(IO &IO, WasmYAML::BranchHintSection &Section) { + commonSectionMapping(IO, Section); + IO.mapRequired("Name", Section.Name); + IO.mapRequired("Entries", Section.Entries); +} + static void sectionMapping(IO &IO, WasmYAML::CustomSection &Section) { commonSectionMapping(IO, Section); IO.mapRequired("Name", Section.Name); @@ -202,6 +208,10 @@ void MappingTraits<std::unique_ptr<WasmYAML::Section>>::mapping( if (!IO.outputting()) Section.reset(new WasmYAML::TargetFeaturesSection()); sectionMapping(IO, *cast<WasmYAML::TargetFeaturesSection>(Section.get())); + } else if (SectionName == "metadata.code.branch_hint") { + if (!IO.outputting()) + Section.reset(new WasmYAML::BranchHintSection()); + sectionMapping(IO, *cast<WasmYAML::BranchHintSection>(Section.get())); } else { if (!IO.outputting()) Section.reset(new WasmYAML::CustomSection(SectionName)); @@ -353,6 +363,31 @@ void MappingTraits<WasmYAML::FeatureEntry>::mapping( IO.mapRequired("Name", FeatureEntry.Name); } +template <> +void MappingTraits<WasmYAML::CodeMetadataFuncEntry<WasmYAML::BranchHint>>:: + mapping(IO &IO, + WasmYAML::CodeMetadataFuncEntry<WasmYAML::BranchHint> &FuncEntry) { + IO.mapRequired("FuncIdx", FuncEntry.FuncIdx); + IO.mapRequired("Hints", FuncEntry.Hints); +} + +template <> +void MappingTraits<WasmYAML::CodeMetadataItemEntry<WasmYAML::BranchHint>>:: + mapping(IO &IO, + WasmYAML::CodeMetadataItemEntry<WasmYAML::BranchHint> &ItemEntry) { + IO.mapRequired("Offset", ItemEntry.Offset); + IO.mapRequired("Size", ItemEntry.Size); + IO.mapRequired("Data", ItemEntry.Data); +} + +void ScalarEnumerationTraits<WasmYAML::BranchHint>::enumeration( + IO &IO, WasmYAML::BranchHint &BranchHint) { + IO.enumCase(BranchHint, "UNLIKELY", + static_cast<uint8_t>(wasm::WasmCodeMetadataBranchHint::UNLIKELY)); + IO.enumCase(BranchHint, "LIKELY", + static_cast<uint8_t>(wasm::WasmCodeMetadataBranchHint::LIKELY)); +} + void MappingTraits<WasmYAML::SegmentInfo>::mapping( IO &IO, WasmYAML::SegmentInfo &SegmentInfo) { IO.mapRequired("Index", SegmentInfo.Index); diff --git a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyAsmBackend.cpp b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyAsmBackend.cpp index 7bc672c069476..218ab188a9d38 100644 --- a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyAsmBackend.cpp +++ b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyAsmBackend.cpp @@ -13,6 +13,7 @@ #include "MCTargetDesc/WebAssemblyFixupKinds.h" #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" +#include "WebAssemblyMCAsmInfo.h" #include "llvm/MC/MCAsmBackend.h" #include "llvm/MC/MCAssembler.h" #include "llvm/MC/MCExpr.h" @@ -21,6 +22,7 @@ #include "llvm/MC/MCSubtargetInfo.h" #include "llvm/MC/MCSymbol.h" #include "llvm/MC/MCWasmObjectWriter.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -44,6 +46,9 @@ class WebAssemblyAsmBackend final : public MCAsmBackend { std::unique_ptr<MCObjectTargetWriter> createObjectTargetWriter() const override; + std::pair<bool, bool> relaxLEB128(MCLEBFragment &LF, + int64_t &Value) const override; + bool writeNopData(raw_ostream &OS, uint64_t Count, const MCSubtargetInfo *STI) const override; }; @@ -70,6 +75,26 @@ WebAssemblyAsmBackend::getFixupKindInfo(MCFixupKind Kind) const { return Infos[Kind - FirstTargetFixupKind]; } +std::pair<bool, bool> WebAssemblyAsmBackend::relaxLEB128(MCLEBFragment &LF, + int64_t &Value) const { + const MCExpr &Expr = LF.getValue(); + if (Expr.getKind() == MCExpr::ExprKind::SymbolRef) { + const MCSymbolRefExpr &SymExpr = llvm::cast<MCSymbolRefExpr>(Expr); + if (static_cast<WebAssembly::Specifier>(SymExpr.getSpecifier()) == + WebAssembly::S_DEBUG_REF) { + Value = Asm->getSymbolOffset(SymExpr.getSymbol()); + return std::make_pair(true, false); + } + } + // currently, this is only used for leb128 encoded function indices + // that require relocations + LF.getFixups().push_back( + MCFixup::create(0, &Expr, WebAssembly::fixup_uleb128_i32, Expr.getLoc())); + // ensure that the stored placeholder is large enough to hold any 32-bit val + Value = UINT32_MAX; + return std::make_pair(true, false); +} + bool WebAssemblyAsmBackend::writeNopData(raw_ostream &OS, uint64_t Count, const MCSubtargetInfo *STI) const { for (uint64_t I = 0; I < Count; ++I) diff --git a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.cpp b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.cpp index 3987b086195a4..bc11fc6b00d89 100644 --- a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.cpp +++ b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.cpp @@ -29,6 +29,7 @@ const MCAsmInfo::AtSpecifier atSpecifiers[] = { {WebAssembly::S_GOT, "GOT"}, {WebAssembly::S_GOT_TLS, "GOT@TLS"}, {WebAssembly::S_FUNCINDEX, "FUNCINDEX"}, + {WebAssembly::S_DEBUG_REF, "DEBUGREF"}, }; WebAssemblyMCAsmInfo::~WebAssemblyMCAsmInfo() = default; // anchor. diff --git a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.h b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.h index 0b3778b36d6ac..bfb5c59b1b80c 100644 --- a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.h +++ b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCAsmInfo.h @@ -37,6 +37,7 @@ enum Specifier { S_TBREL, // Table index relative to __table_base S_TLSREL, // Memory address relative to __tls_base S_TYPEINDEX, // Reference to a symbol's type (signature) + S_DEBUG_REF, // Marker placed for generation of metadata.code.* section }; } } // end namespace llvm diff --git a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyWasmObjectWriter.cpp b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyWasmObjectWriter.cpp index 2cf4bec077385..b910f1f1529e4 100644 --- a/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyWasmObjectWriter.cpp +++ b/llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyWasmObjectWriter.cpp @@ -91,12 +91,16 @@ unsigned WebAssemblyWasmObjectWriter::getRelocType( case WebAssembly::S_TYPEINDEX: return wasm::R_WASM_TYPE_INDEX_LEB; case WebAssembly::S_None: + case WebAssembly::S_DEBUG_REF: break; case WebAssembly::S_FUNCINDEX: + if (static_cast<unsigned>(Fixup.getKind()) == + WebAssembly::fixup_uleb128_i32) + return wasm::R_WASM_FUNCTION_INDEX_LEB; return wasm::R_WASM_FUNCTION_INDEX_I32; } - switch (unsigned(Fixup.getKind())) { + switch (static_cast<unsigned>(Fixup.getKind())) { case WebAssembly::fixup_sleb128_i32: if (SymA.isFunction()) return wasm::R_WASM_TABLE_INDEX_SLEB; diff --git a/llvm/lib/Target/WebAssembly/WebAssembly.td b/llvm/lib/Target/WebAssembly/WebAssembly.td index 13603f8181198..b327029d4c7c0 100644 --- a/llvm/lib/Target/WebAssembly/WebAssembly.td +++ b/llvm/lib/Target/WebAssembly/WebAssembly.td @@ -25,6 +25,10 @@ include "llvm/Target/Target.td" def FeatureAtomics : SubtargetFeature<"atomics", "HasAtomics", "true", "Enable Atomics">; +def FeatureBranchHinting : + SubtargetFeature<"branch-hinting", "HasBranchHinting", "true", + "Enable branch hints for branch instructions">; + def FeatureBulkMemory : SubtargetFeature<"bulk-memory", "HasBulkMemory", "true", "Enable bulk memory operations">; @@ -136,10 +140,10 @@ def : ProcessorModel<"lime1", NoSchedModel, // Latest and greatest experimental version of WebAssembly. Bugs included! def : ProcessorModel<"bleeding-edge", NoSchedModel, - [FeatureAtomics, FeatureBulkMemory, FeatureBulkMemoryOpt, - FeatureCallIndirectOverlong, FeatureExceptionHandling, - FeatureExtendedConst, FeatureFP16, FeatureMultiMemory, - FeatureMultivalue, FeatureMutableGlobals, + [FeatureAtomics, FeatureBranchHinting, FeatureBulkMemory, + FeatureBulkMemoryOpt, FeatureCallIndirectOverlong, + FeatureExceptionHandling, FeatureExtendedConst, FeatureFP16, + FeatureMultiMemory, FeatureMultivalue, FeatureMutableGlobals, FeatureNontrappingFPToInt, FeatureRelaxedSIMD, FeatureReferenceTypes, FeatureSIMD128, FeatureSignExt, FeatureTailCall]>; diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp index 44a19e4baaf62..0abc18a61585b 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp +++ b/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp @@ -55,6 +55,17 @@ using namespace llvm; #define DEBUG_TYPE "asm-printer" extern cl::opt<bool> WasmKeepRegisters; +// values are divided by 1<<31 to calculate the probability +static cl::opt<float> + WasmHighBranchProb("wasm-branch-prob-high", cl::Hidden, + cl::desc("lowest branch probability to not be annotated " + "as likely taken (range [0.0-1.0])"), + cl::init(0.5f)); +static cl::opt<float> + WasmLowBranchProb("wasm-branch-prob-low", cl::Hidden, + cl::desc("highest branch probability to be annotated as " + "unlikely taken (range [0.0-1.0])"), + cl::init(0.5f)); //===----------------------------------------------------------------------===// // Helpers. @@ -442,6 +453,40 @@ void WebAssemblyAsmPrinter::emitEndOfAsmFile(Module &M) { EmitProducerInfo(M); EmitTargetFeatures(M); EmitFunctionAttributes(M); + + // Subtarget may be null if no functions have been defined in file + if (Subtarget && Subtarget->hasBranchHinting()) + emitBranchHintSection(); +} + +void WebAssemblyAsmPrinter::emitBranchHintSection() const { + MCSectionWasm *BranchHintsSection = OutContext.getWasmSection( + "metadata.code.branch_hint", SectionKind::getMetadata()); + OutStreamer->pushSection(); + OutStreamer->switchSection(BranchHintsSection); + const uint32_t NumFunctionHints = + std::count_if(BranchHints.begin(), BranchHints.end(), + [](const auto &BHR) { return !BHR.Hints.empty(); }); + OutStreamer->emitULEB128IntValue(NumFunctionHints, 5); + for (const auto &BHR : BranchHints) { + if (BHR.Hints.empty()) + continue; + // emit relocatable function index for the function symbol + OutStreamer->emitULEB128Value(MCSymbolRefExpr::create( + BHR.FuncSym, WebAssembly::S_FUNCINDEX, OutContext)); + // emit the number of hints for this function (is constant -> does not need + // handling by target streamer for reloc) + OutStreamer->emitULEB128IntValue(BHR.Hints.size()); + for (const auto &[instrSym, hint] : BHR.Hints) { + assert(hint == 0 || hint == 1); + // offset from function start + OutStreamer->emitULEB128Value(MCSymbolRefExpr::create( + instrSym, WebAssembly::S_DEBUG_REF, OutContext)); + OutStreamer->emitULEB128IntValue(1); // hint size + OutStreamer->emitULEB128IntValue(hint); + } + } + OutStreamer->popSection(); } void WebAssemblyAsmPrinter::EmitProducerInfo(Module &M) { @@ -697,6 +742,42 @@ void WebAssemblyAsmPrinter::emitInstruction(const MachineInstr *MI) { WebAssemblyMCInstLower MCInstLowering(OutContext, *this); MCInst TmpInst; MCInstLowering.lower(MI, TmpInst); + if (Subtarget->hasBranchHinting() && MFI) { + if (const auto Prob = MFI->BranchProbabilities.find(MI); + Prob != MFI->BranchProbabilities.end()) { + const float ThresholdProbLow = WasmLowBranchProb.getValue(); + const float ThresholdProbHigh = WasmHighBranchProb.getValue(); + assert(ThresholdProbLow >= 0.0f && ThresholdProbLow <= 1.0f && + ThresholdProbHigh >= 0.0f && ThresholdProbHigh <= 1.0f && + "Branch probability thresholds must be in range [0.0-1.0]"); + + MCSymbol *BrIfSym = OutContext.createTempSymbol(); + OutStreamer->emitLabel(BrIfSym); + constexpr uint8_t HintLikely = 0x01; + constexpr uint8_t HintUnlikely = 0x00; + const uint32_t D = BranchProbability::getOne().getDenominator(); + uint8_t HintValue; + if (Prob->getSecond() > + BranchProbability::getRaw(ThresholdProbHigh * D)) + HintValue = HintLikely; + else if (Prob->getSecond() <= + BranchProbability::getRaw(ThresholdProbLow * D)) + HintValue = HintUnlikely; + else + goto emit; // Don't emit branch hint between thresholds + + // we know that we only emit branch hints for internal functions, + // therefore we can directly cast and don't need getMCSymbolForFunction + MCSymbol *FuncSym = cast<MCSymbolWasm>(getSymbol(&MF->getFunction())); + const uint32_t LocalFuncIdx = MF->getFunctionNumber(); + if (BranchHints.size() <= LocalFuncIdx) { + BranchHints.resize(LocalFuncIdx + 1); + BranchHints[LocalFuncIdx].FuncSym = FuncSym; + } + BranchHints[LocalFuncIdx].Hints.emplace_back(BrIfSym, HintValue); + } + } + emit: EmitToStreamer(*OutStreamer, TmpInst); break; } diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.h b/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.h index 46063bbe0fba1..1876840248053 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.h +++ b/llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.h @@ -12,12 +12,19 @@ #include "WebAssemblyMachineFunctionInfo.h" #include "WebAssemblySubtarget.h" #include "llvm/CodeGen/AsmPrinter.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/IR/Module.h" #include "llvm/MC/MCStreamer.h" #include "llvm/Target/TargetMachine.h" namespace llvm { class WebAssemblyTargetStreamer; +struct BranchHintRecord { + MCSymbol *FuncSym; + SmallVector<std::pair<MCSymbol *, uint8_t>, 0> Hints; +}; + class LLVM_LIBRARY_VISIBILITY WebAssemblyAsmPrinter final : public AsmPrinter { public: static char ID; @@ -28,6 +35,9 @@ class LLVM_LIBRARY_VISIBILITY WebAssemblyAsmPrinter final : public AsmPrinter { WebAssemblyFunctionInfo *MFI; bool signaturesEmitted = false; + // vec idx == local func_idx + SmallVector<BranchHintRecord> BranchHints; + public: explicit WebAssemblyAsmPrinter(TargetMachine &TM, std::unique_ptr<MCStreamer> Streamer) @@ -48,6 +58,12 @@ class LLVM_LIBRARY_VISIBILITY WebAssemblyAsmPrinter final : public AsmPrinter { Subtarget = &MF.getSubtarget<WebAssemblySubtarget>(); MRI = &MF.getRegInfo(); MFI = MF.getInfo<WebAssemblyFunctionInfo>(); + + if (Subtarget->hasBranchHinting()) { + const uint32_t LocalFuncIdx = MF.getFunctionNumber(); + BranchHints.resize(MMI->getModule()->getFunctionList().size()); + BranchHints[LocalFuncIdx].FuncSym = getSymbol(&MF.getFunction()); + } return AsmPrinter::runOnMachineFunction(MF); } @@ -59,6 +75,7 @@ class LLVM_LIBRARY_VISIBILITY WebAssemblyAsmPrinter final : public AsmPrinter { void EmitProducerInfo(Module &M); void EmitTargetFeatures(Module &M); void EmitFunctionAttributes(Module &M); + void emitBranchHintSection() const; void emitSymbolType(const MCSymbolWasm *Sym); void emitGlobalVariable(const GlobalVariable *GV) override; void emitJumpTableInfo() override; diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp index 640be5fe8e8c9..0e6eddcdb06c4 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp +++ b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp @@ -31,6 +31,7 @@ #include "WebAssemblyUtilities.h" #include "llvm/ADT/Statistic.h" #include "llvm/BinaryFormat/Wasm.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" @@ -48,6 +49,7 @@ STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found"); namespace { class WebAssemblyCFGStackify final : public MachineFunctionPass { MachineDominatorTree *MDT; + MachineBranchProbabilityInfo *MBPI; StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } @@ -55,6 +57,7 @@ class WebAssemblyCFGStackify final : public MachineFunctionPass { AU.addRequired<MachineDominatorTreeWrapperPass>(); AU.addRequired<MachineLoopInfoWrapperPass>(); AU.addRequired<WebAssemblyExceptionInfo>(); + AU.addRequired<MachineBranchProbabilityInfoWrapperPass>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -2608,6 +2611,21 @@ void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { Stack.push_back(std::make_pair(&MBB, &MI)); break; + case WebAssembly::BR_IF: { + // this is the last place where we can easily calculate the branch + // probabilities. We do not emit if-blocks, meaning only br_ifs have + // to be annotated with branch probabilities. + if (MF.getSubtarget<WebAssemblySubtarget>().hasBranchHinting() && + MI.getParent()->hasSuccessorProbabilities()) { + const auto Prob = MBPI->getEdgeProbability( + MI.getParent(), MI.operands().begin()->getMBB()); + WebAssemblyFunctionInfo *MFI = MF.getInfo<WebAssemblyFunctionInfo>(); + assert(!MFI->BranchProbabilities.contains(&MI)); + MFI->BranchProbabilities[&MI] = Prob; + } + RewriteOperands(MI); + break; + } default: if (MI.isTerminator()) RewriteOperands(MI); @@ -2639,6 +2657,7 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { << MF.getName() << '\n'); const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree(); + MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI(); releaseMemory(); diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td b/llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td index b5e723e2a48d3..d1d9d01ae656b 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td +++ b/llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td @@ -26,6 +26,10 @@ def HasAtomics : Predicate<"Subtarget->hasAtomics()">, AssemblerPredicate<(all_of FeatureAtomics), "atomics">; +def HasBranchHinting : + Predicate<"Subtarget->hasBranchHinting()">, + AssemblerPredicate<(all_of FeatureBranchHinting), "branch-hinting">; + def HasBulkMemory : Predicate<"Subtarget->hasBulkMemory()">, AssemblerPredicate<(all_of FeatureBulkMemory), "bulk-memory">; diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h b/llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h index 40ae4aef1d7f2..343168b570bef 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h +++ b/llvm/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h @@ -153,6 +153,8 @@ class WebAssemblyFunctionInfo final : public MachineFunctionInfo { bool isCFGStackified() const { return CFGStackified; } void setCFGStackified(bool Value = true) { CFGStackified = Value; } + + DenseMap<const MachineInstr *, BranchProbability> BranchProbabilities; }; void computeLegalValueVTs(const WebAssemblyTargetLowering &TLI, diff --git a/llvm/lib/Target/WebAssembly/WebAssemblySubtarget.h b/llvm/lib/Target/WebAssembly/WebAssemblySubtarget.h index 591ce25611e3e..96a24a1d40ef7 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblySubtarget.h +++ b/llvm/lib/Target/WebAssembly/WebAssemblySubtarget.h @@ -54,6 +54,7 @@ class WebAssemblySubtarget final : public WebAssemblyGenSubtargetInfo { bool HasSignExt = false; bool HasTailCall = false; bool HasWideArithmetic = false; + bool HasBranchHinting = false; /// What processor and OS we're targeting. Triple TargetTriple; @@ -112,6 +113,7 @@ class WebAssemblySubtarget final : public WebAssemblyGenSubtargetInfo { bool hasSIMD128() const { return SIMDLevel >= SIMD128; } bool hasTailCall() const { return HasTailCall; } bool hasWideArithmetic() const { return HasWideArithmetic; } + bool hasBranchHinting() const { return HasBranchHinting; } /// Parses features string setting specified subtarget options. Definition of /// function is auto generated by tblgen. diff --git a/llvm/test/CodeGen/WebAssembly/target-features-cpus.ll b/llvm/test/CodeGen/WebAssembly/target-features-cpus.ll index 1c77ad5c049a5..17f125c5e020f 100644 --- a/llvm/test/CodeGen/WebAssembly/target-features-cpus.ll +++ b/llvm/test/CodeGen/WebAssembly/target-features-cpus.ll @@ -66,17 +66,20 @@ target triple = "wasm32-unknown-unknown" ; LIME1-NEXT: .int8 8 ; LIME1-NEXT: .ascii "sign-ext" -; bleeding-edge: +atomics, +bulk-memory, +bulk-memory-opt, +; bleeding-edge: +atomics, +branch-hinting, +bulk-memory, +bulk-memory-opt, ; +call-indirect-overlong, +exception-handling, ; +extended-const, +fp16, +multimemory, +multivalue, ; +mutable-globals, +nontrapping-fptoint, +relaxed-simd, ; +reference-types, +simd128, +sign-ext, +tail-call ; BLEEDING-EDGE-LABEL: .section .custom_section.target_features,"",@ -; BLEEDING-EDGE-NEXT: .int8 16 +; BLEEDING-EDGE-NEXT: .int8 17 ; BLEEDING-EDGE-NEXT: .int8 43 ; BLEEDING-EDGE-NEXT: .int8 7 ; BLEEDING-EDGE-NEXT: .ascii "atomics" ; BLEEDING-EDGE-NEXT: .int8 43 +; BLEEDING-EDGE-NEXT: .int8 14 +; BLEEDING-EDGE-NEXT: .ascii "branch-hinting" +; BLEEDING-EDGE-NEXT: .int8 43 ; BLEEDING-EDGE-NEXT: .int8 11 ; BLEEDING-EDGE-NEXT: .ascii "bulk-memory" ; BLEEDING-EDGE-NEXT: .int8 43 diff --git a/llvm/test/MC/WebAssembly/branch-hints-custom-high-low-thresholds.ll b/llvm/test/MC/WebAssembly/branch-hints-custom-high-low-thresholds.ll new file mode 100644 index 0000000000000..9125de49e941e --- /dev/null +++ b/llvm/test/MC/WebAssembly/branch-hints-custom-high-low-thresholds.ll @@ -0,0 +1,127 @@ +; RUN: llc -mcpu=mvp -filetype=obj %s -mattr=+branch-hinting -wasm-branch-prob-high=.5 -wasm-branch-prob-low=0.5 -o - | obj2yaml | FileCheck --check-prefixes=C1 %s +; RUN: llc -mcpu=mvp -filetype=obj %s -mattr=+branch-hinting -wasm-branch-prob-high=.76 -wasm-branch-prob-low=0 -o - | obj2yaml | FileCheck --check-prefixes=C2 %s +; RUN: llc -mcpu=mvp -filetype=obj %s -mattr=+branch-hinting -wasm-branch-prob-high=.75 -wasm-branch-prob-low=0 -o - | obj2yaml | FileCheck --check-prefixes=C3 %s + +; This test checks that branch weight metadata (!prof) is correctly translated to webassembly branch hints +; We set the prob-thresholds so that "likely" branches are only emitted if prob > 75% and "unlikely" branches +; if prob <= 0%. + +; C1: - Type: CUSTOM +; C1-NEXT: Relocations: +; C1-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C1-NEXT: Index: 0 +; C1-NEXT: Offset: 0x5 +; C1-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C1-NEXT: Index: 1 +; C1-NEXT: Offset: 0xE +; C1-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C1-NEXT: Index: 2 +; C1-NEXT: Offset: 0x17 +; C1-NEXT: Name: metadata.code.branch_hint +; C1-NEXT: Entries: +; C1-NEXT: - FuncIdx: 0 +; C1-NEXT: Hints: +; C1-NEXT: - Offset: 5 +; C1-NEXT: Size: 1 +; C1-NEXT: Data: LIKELY +; C1-NEXT: - FuncIdx: 1 +; C1-NEXT: Hints: +; C1-NEXT: - Offset: 5 +; C1-NEXT: Size: 1 +; C1-NEXT: Data: UNLIKELY +; C1-NEXT: - FuncIdx: 2 +; C1-NEXT: Hints: +; C1-NEXT: - Offset: 5 +; C1-NEXT: Size: 1 +; C1-NEXT: Data: UNLIKELY + +; C2: - Type: CUSTOM +; C2-NEXT: Relocations: +; C2-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C2-NEXT: Index: 2 +; C2-NEXT: Offset: 0x5 +; C2-NEXT: Name: metadata.code.branch_hint +; C2-NEXT: Entries: +; C2-NEXT: - FuncIdx: 2 +; C2-NEXT: Hints: +; C2-NEXT: - Offset: 5 +; C2-NEXT: Size: 1 +; C2-NEXT: Data: UNLIKELY + +; C3: - Type: CUSTOM +; C3-NEXT: Relocations: +; C3-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C3-NEXT: Index: 0 +; C3-NEXT: Offset: 0x5 +; C3-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; C3-NEXT: Index: 2 +; C3-NEXT: Offset: 0xE +; C3-NEXT: Name: metadata.code.branch_hint +; C3-NEXT: Entries: +; C3-NEXT: - FuncIdx: 0 +; C3-NEXT: Hints: +; C3-NEXT: - Offset: 5 +; C3-NEXT: Size: 1 +; C3-NEXT: Data: LIKELY +; C3-NEXT: - FuncIdx: 2 +; C3-NEXT: Hints: +; C3-NEXT: - Offset: 5 +; C3-NEXT: Size: 1 +; C3-NEXT: Data: UNLIKELY + +; CHECK: - Type: CUSTOM +; CHECK-NEXT: Name: linking +; CHECK-NEXT: Version: 2 +; CHECK-NEXT: SymbolTable: +; CHECK-NEXT: - Index: 0 +; CHECK-NEXT: Kind: FUNCTION +; CHECK-NEXT: Name: test0 +; CHECK-NEXT: Flags: [ ] +; CHECK-NEXT: Function: 0 +; CHECK-NEXT: - Index: 1 +; CHECK-NEXT: Kind: FUNCTION +; CHECK-NEXT: Name: test1 +; CHECK-NEXT: Flags: [ ] +; CHECK-NEXT: Function: 1 +; CHECK-NEXT: - Index: 2 +; CHECK-NEXT: Kind: FUNCTION +; CHECK-NEXT: Name: test2 +; CHECK-NEXT: Flags: [ ] +; CHECK-NEXT: Function: 2 + +target triple = "wasm32-unknown-unknown" + +define i32 @test0(i32 %a) { +entry: + %cmp0 = icmp eq i32 %a, 0 + br i1 %cmp0, label %if_then, label %if_else, !prof !0 +if_then: + ret i32 1 +if_else: + ret i32 0 +} + +define i32 @test1(i32 %a) { +entry: + %cmp0 = icmp eq i32 %a, 0 + br i1 %cmp0, label %if_then, label %if_else, !prof !1 +if_then: + ret i32 1 +if_else: + ret i32 0 +} + +define i32 @test2(i32 %a) { +entry: + %cmp0 = icmp eq i32 %a, 0 + br i1 %cmp0, label %if_then, label %if_else, !prof !2 +if_then: + ret i32 1 +if_else: + ret i32 0 +} + +; the resulting branch hint is actually reversed, since llvm-br is turned into br_unless, inverting branch probs +!0 = !{!"branch_weights", !"expected", i32 100, i32 310} ; prob 75.61% +!1 = !{!"branch_weights", i32 1, i32 1} ; prob == 50% (no hint) +!2 = !{!"branch_weights", i32 1, i32 0} ; prob == 0% (unlikely hint) diff --git a/llvm/test/MC/WebAssembly/branch-hints.ll b/llvm/test/MC/WebAssembly/branch-hints.ll new file mode 100644 index 0000000000000..301a81bf92b34 --- /dev/null +++ b/llvm/test/MC/WebAssembly/branch-hints.ll @@ -0,0 +1,122 @@ +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=asm %s -mattr=+branch-hinting -o - | FileCheck --check-prefixes=ASM-CHECK %s +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=asm %s -mattr=-branch-hinting -o - | FileCheck --check-prefixes=ASM-NCHECK %s +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=asm %s -o - | FileCheck --check-prefixes=ASM-NCHECK %s +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %s -mattr=+branch-hinting -o - | obj2yaml | FileCheck --check-prefixes=YAML-CHECK %s +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %s -mattr=-branch-hinting -o - | obj2yaml | FileCheck --check-prefixes=YAML-NCHECK %s +; RUN: llc -mcpu=mvp -mtriple=wasm32-unknown-unknown -filetype=obj %s -o - | obj2yaml | FileCheck --check-prefixes=YAML-NCHECK %s + +; This test checks that branch weight metadata (!prof) is correctly lowered to +; the WebAssembly branch hint custom section. + +; ASM-CHECK: test_unlikely_likely_branch: # @test_unlikely_likely_branch +; ASM-CHECK: .Ltmp0: +; ASM-CHECK-NEXT: br_if 0 # 0: down to label1 +; ASM-CHECK: .Ltmp1: +; ASM-CHECK-NEXT: br_if 1 # 1: down to label0 + +; ASM-CHECK: test_likely_branch: # @test_likely_branch +; ASM-CHECK: .Ltmp2: +; ASM-CHECK-NEXT: br_if 0 # 0: down to label2 + +; ASM-CHECK: .section .custom_section.target_features,"",@ +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .int8 43 +; ASM-CHECK-NEXT: .int8 14 +; ASM-CHECK-NEXT: .ascii "branch-hinting" + +; ASM-CHECK: .section metadata.code.branch_hint,"",@ +; ASM-CHECK-NEXT: .asciz "\202\200\200\200" +; ASM-CHECK-NEXT: .uleb128 test_unlikely_likely_branch@FUNCINDEX +; ASM-CHECK-NEXT: .int8 2 +; ASM-CHECK-NEXT: .uleb128 .Ltmp0@DEBUGREF +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .int8 0 +; ASM-CHECK-NEXT: .uleb128 .Ltmp1@DEBUGREF +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .uleb128 test_likely_branch@FUNCINDEX +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .uleb128 .Ltmp2@DEBUGREF +; ASM-CHECK-NEXT: .int8 1 +; ASM-CHECK-NEXT: .int8 1 + +; ASM-NCHECK-NOT: .ascii "branch-hinting" +; ASM-NCHECK-NOT: .section metadata.code.branch_hint,"",@ + +; YAML-CHECK: - Type: CUSTOM +; YAML-CHECK-NEXT: Relocations: +; YAML-CHECK-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; YAML-CHECK-NEXT: Index: 0 +; YAML-CHECK-NEXT: Offset: 0x5 +; YAML-CHECK-NEXT: - Type: R_WASM_FUNCTION_INDEX_LEB +; YAML-CHECK-NEXT: Index: 1 +; YAML-CHECK-NEXT: Offset: 0x11 +; YAML-CHECK-NEXT: Name: metadata.code.branch_hint +; YAML-CHECK-NEXT: Entries: +; YAML-CHECK-NEXT: - FuncIdx: 0 +; YAML-CHECK-NEXT: Hints: +; YAML-CHECK-NEXT: - Offset: 7 +; YAML-CHECK-NEXT: Size: 1 +; YAML-CHECK-NEXT: Data: UNLIKELY +; YAML-CHECK-NEXT: - Offset: 14 +; YAML-CHECK-NEXT: Size: 1 +; YAML-CHECK-NEXT: Data: LIKELY +; YAML-CHECK-NEXT: - FuncIdx: 1 +; YAML-CHECK-NEXT: Hints: +; YAML-CHECK-NEXT: - Offset: 5 +; YAML-CHECK-NEXT: Size: 1 +; YAML-CHECK-NEXT: Data: LIKELY + +; YAML-CHECK: - Type: CUSTOM +; YAML-CHECK-NEXT: Name: linking +; YAML-CHECK-NEXT: Version: 2 +; YAML-CHECK-NEXT: SymbolTable: +; YAML-CHECK-NEXT: - Index: 0 +; YAML-CHECK-NEXT: Kind: FUNCTION +; YAML-CHECK-NEXT: Name: test_unlikely_likely_branch +; YAML-CHECK-NEXT: Flags: [ ] +; YAML-CHECK-NEXT: Function: 0 +; YAML-CHECK-NEXT: - Index: 1 +; YAML-CHECK-NEXT: Kind: FUNCTION +; YAML-CHECK-NEXT: Name: test_likely_branch +; YAML-CHECK-NEXT: Flags: [ ] +; YAML-CHECK-NEXT: Function: 1 + +; YAML-CHECK: - Type: CUSTOM +; YAML-CHECK-NEXT: Name: target_features +; YAML-CHECK-NEXT: Features: +; YAML-CHECK-NEXT: - Prefix: USED +; YAML-CHECK-NEXT: Name: branch-hinting + +; YAML-NCHECK-NOT: Name: metadata.code.branch_hint +; YAML-NCHECK-NOT: Name: branch-hinting + +target triple = "wasm32-unknown-unknown" + +define i32 @test_unlikely_likely_branch(i32 %a) { +entry: + %cmp0 = icmp eq i32 %a, 0 + ; This metadata hints that the true branch is overwhelmingly likely. + br i1 %cmp0, label %if.then, label %ret1, !prof !0 +if.then: + %cmp1 = icmp eq i32 %a, 1 + br i1 %cmp1, label %ret1, label %ret2, !prof !1 +ret1: + ret i32 2 +ret2: + ret i32 1 +} + +define i32 @test_likely_branch(i32 %a) { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %if.then, label %if.else, !prof !1 +if.then: + ret i32 1 +if.else: + ret i32 2 +} + +; the resulting branch hint is actually reversed, since llvm-br is turned into br_unless, inverting branch probs +!0 = !{!"branch_weights", i32 2000, i32 1} +!1 = !{!"branch_weights", i32 1, i32 2000} diff --git a/llvm/tools/obj2yaml/wasm2yaml.cpp b/llvm/tools/obj2yaml/wasm2yaml.cpp index 7b504faa5ae4e..bcc67db3ef967 100644 --- a/llvm/tools/obj2yaml/wasm2yaml.cpp +++ b/llvm/tools/obj2yaml/wasm2yaml.cpp @@ -189,6 +189,23 @@ WasmDumper::dumpCustomSection(const WasmSection &WasmSec) { TargetFeaturesSec->Features.push_back(Feature); } CustomSec = std::move(TargetFeaturesSec); + } else if (WasmSec.Name == "metadata.code.branch_hint") { + std::unique_ptr<WasmYAML::BranchHintSection> BranchHintSec = + std::make_unique<WasmYAML::BranchHintSection>(); + for (auto &E : Obj.getBranchHints()) { + WasmYAML::CodeMetadataFuncEntry<WasmYAML::BranchHint> FuncEntry; + FuncEntry.FuncIdx = E.FuncIdx; + for (const auto &[Offset, Size, Data] : E.Hints) { + WasmYAML::CodeMetadataItemEntry<WasmYAML::BranchHint> ItemEntry; + ItemEntry.Offset = Offset; + ItemEntry.Size = Size; + ItemEntry.Data = + static_cast<WasmYAML::BranchHint>(static_cast<uint8_t>(Data)); + FuncEntry.Hints.push_back(ItemEntry); + } + BranchHintSec->Entries.push_back(std::move(FuncEntry)); + } + CustomSec = std::move(BranchHintSec); } else { CustomSec = std::make_unique<WasmYAML::CustomSection>(WasmSec.Name); } _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
