[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/aaupov updated
https://github.com/llvm/llvm-project/pull/145258
>From 9aef8e0a499fa4b9e6bbde910a678a65a0ab7f92 Mon Sep 17 00:00:00 2001
From: Amir Ayupov
Date: Mon, 23 Jun 2025 12:54:06 -0700
Subject: [PATCH] unified checkReturn and checkUncondJump, logging
Created using spr 1.3.4
---
bolt/include/bolt/Profile/DataAggregator.h | 34 ++-
bolt/lib/Profile/DataAggregator.cpp| 49 ++
2 files changed, 46 insertions(+), 37 deletions(-)
diff --git a/bolt/include/bolt/Profile/DataAggregator.h
b/bolt/include/bolt/Profile/DataAggregator.h
index 00c6f56520fdc..364dbdbed841c 100644
--- a/bolt/include/bolt/Profile/DataAggregator.h
+++ b/bolt/include/bolt/Profile/DataAggregator.h
@@ -137,7 +137,7 @@ class DataAggregator : public DataReader {
std::vector> Traces;
/// Pre-populated addresses of returns, coming from pre-aggregated data or
/// disassembly. Used to disambiguate call-continuation fall-throughs.
- std::unordered_set Returns;
+ std::unordered_map Returns;
std::unordered_map BasicSamples;
std::vector MemSamples;
@@ -514,6 +514,38 @@ class DataAggregator : public DataReader {
void printBasicSamplesDiagnostics(uint64_t OutOfRangeSamples) const;
void printBranchStacksDiagnostics(uint64_t IgnoredSamples) const;
+ template
+ std::optional
+ testInstructionAt(const uint64_t Addr,
+std::function Callback) const {
+BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
+if (!Func)
+ return std::nullopt;
+const uint64_t Offset = Addr - Func->getAddress();
+if (Func->hasInstructions()) {
+ if (auto *MI = Func->getInstructionAtOffset(Offset))
+return Callback(*MI);
+} else {
+ if (auto MI = Func->disassembleInstructionAtOffset(Offset))
+return Callback(*MI);
+}
+return std::nullopt;
+ }
+
+ template
+ std::optional testAndSet(const uint64_t Addr,
+ std::function Callback,
+ std::unordered_map &Map) {
+auto It = Map.find(Addr);
+if (It != Map.end())
+ return It->second;
+if (std::optional Res = testInstructionAt(Addr, Callback)) {
+ Map.emplace(Addr, *Res);
+ return *Res;
+}
+return std::nullopt;
+ }
+
public:
/// If perf.data was collected without build ids, the buildid-list may
contain
/// incomplete entries. Return true if the buffer containing
diff --git a/bolt/lib/Profile/DataAggregator.cpp
b/bolt/lib/Profile/DataAggregator.cpp
index 2fcc2561cc212..1323c4f30049d 100644
--- a/bolt/lib/Profile/DataAggregator.cpp
+++ b/bolt/lib/Profile/DataAggregator.cpp
@@ -546,23 +546,10 @@ void DataAggregator::imputeFallThroughs() {
// Helper map with whether the instruction is a call/ret/unconditional branch
std::unordered_map IsUncondJumpMap;
auto checkUncondJump = [&](const uint64_t Addr) {
-auto isUncondJump = [&](auto MI) {
- return MI && BC->MIB->IsUnconditionalJump(*MI);
+auto isUncondJump = [&](const MCInst &MI) -> bool {
+ return BC->MIB->IsUnconditionalJump(MI);
};
-auto It = IsUncondJumpMap.find(Addr);
-if (It != IsUncondJumpMap.end())
- return It->second;
-BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
-if (!Func)
- return false;
-const uint64_t Offset = Addr - Func->getAddress();
-if (Func->hasInstructions()
-? isUncondJump(Func->getInstructionAtOffset(Offset))
-: isUncondJump(Func->disassembleInstructionAtOffset(Offset))) {
- IsUncondJumpMap.emplace(Addr, true);
- return true;
-}
-return false;
+return testAndSet(Addr, isUncondJump,
IsUncondJumpMap).value_or(true);
};
for (auto &[Trace, Info] : Traces) {
@@ -574,7 +561,8 @@ void DataAggregator::imputeFallThroughs() {
? AggregateFallthroughSize / AggregateCount
: !checkUncondJump(Trace.From);
Trace.To = Trace.From + InferredBytes;
- outs() << "Inferred " << Trace << " " << InferredBytes << '\n';
+ LLVM_DEBUG(dbgs() << "imputed " << Trace << " (" << InferredBytes
+<< " bytes)\n");
++InferredTraces;
} else {
if (CurrentBranch != PrevBranch)
@@ -585,7 +573,8 @@ void DataAggregator::imputeFallThroughs() {
}
PrevBranch = CurrentBranch;
}
- outs() << "Inferred " << InferredTraces << " traces\n";
+ if (opts::Verbosity >= 1)
+outs() << "BOLT-INFO: imputed " << InferredTraces << " traces\n";
}
Error DataAggregator::preprocessProfile(BinaryContext &BC) {
@@ -804,22 +793,10 @@ bool DataAggregator::doInterBranch(BinaryFunction
*FromFunc,
}
bool DataAggregator::checkReturn(uint64_t Addr) {
- auto isReturn = [&](auto MI) { return MI && BC->MIB->isReturn(*MI); };
- if (llvm::is_contained(Returns, Addr))
-return true;
-
- BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
- if (!Func)
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/aaupov updated
https://github.com/llvm/llvm-project/pull/145258
>From 9aef8e0a499fa4b9e6bbde910a678a65a0ab7f92 Mon Sep 17 00:00:00 2001
From: Amir Ayupov
Date: Mon, 23 Jun 2025 12:54:06 -0700
Subject: [PATCH] unified checkReturn and checkUncondJump, logging
Created using spr 1.3.4
---
bolt/include/bolt/Profile/DataAggregator.h | 34 ++-
bolt/lib/Profile/DataAggregator.cpp| 49 ++
2 files changed, 46 insertions(+), 37 deletions(-)
diff --git a/bolt/include/bolt/Profile/DataAggregator.h
b/bolt/include/bolt/Profile/DataAggregator.h
index 00c6f56520fdc..364dbdbed841c 100644
--- a/bolt/include/bolt/Profile/DataAggregator.h
+++ b/bolt/include/bolt/Profile/DataAggregator.h
@@ -137,7 +137,7 @@ class DataAggregator : public DataReader {
std::vector> Traces;
/// Pre-populated addresses of returns, coming from pre-aggregated data or
/// disassembly. Used to disambiguate call-continuation fall-throughs.
- std::unordered_set Returns;
+ std::unordered_map Returns;
std::unordered_map BasicSamples;
std::vector MemSamples;
@@ -514,6 +514,38 @@ class DataAggregator : public DataReader {
void printBasicSamplesDiagnostics(uint64_t OutOfRangeSamples) const;
void printBranchStacksDiagnostics(uint64_t IgnoredSamples) const;
+ template
+ std::optional
+ testInstructionAt(const uint64_t Addr,
+std::function Callback) const {
+BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
+if (!Func)
+ return std::nullopt;
+const uint64_t Offset = Addr - Func->getAddress();
+if (Func->hasInstructions()) {
+ if (auto *MI = Func->getInstructionAtOffset(Offset))
+return Callback(*MI);
+} else {
+ if (auto MI = Func->disassembleInstructionAtOffset(Offset))
+return Callback(*MI);
+}
+return std::nullopt;
+ }
+
+ template
+ std::optional testAndSet(const uint64_t Addr,
+ std::function Callback,
+ std::unordered_map &Map) {
+auto It = Map.find(Addr);
+if (It != Map.end())
+ return It->second;
+if (std::optional Res = testInstructionAt(Addr, Callback)) {
+ Map.emplace(Addr, *Res);
+ return *Res;
+}
+return std::nullopt;
+ }
+
public:
/// If perf.data was collected without build ids, the buildid-list may
contain
/// incomplete entries. Return true if the buffer containing
diff --git a/bolt/lib/Profile/DataAggregator.cpp
b/bolt/lib/Profile/DataAggregator.cpp
index 2fcc2561cc212..1323c4f30049d 100644
--- a/bolt/lib/Profile/DataAggregator.cpp
+++ b/bolt/lib/Profile/DataAggregator.cpp
@@ -546,23 +546,10 @@ void DataAggregator::imputeFallThroughs() {
// Helper map with whether the instruction is a call/ret/unconditional branch
std::unordered_map IsUncondJumpMap;
auto checkUncondJump = [&](const uint64_t Addr) {
-auto isUncondJump = [&](auto MI) {
- return MI && BC->MIB->IsUnconditionalJump(*MI);
+auto isUncondJump = [&](const MCInst &MI) -> bool {
+ return BC->MIB->IsUnconditionalJump(MI);
};
-auto It = IsUncondJumpMap.find(Addr);
-if (It != IsUncondJumpMap.end())
- return It->second;
-BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
-if (!Func)
- return false;
-const uint64_t Offset = Addr - Func->getAddress();
-if (Func->hasInstructions()
-? isUncondJump(Func->getInstructionAtOffset(Offset))
-: isUncondJump(Func->disassembleInstructionAtOffset(Offset))) {
- IsUncondJumpMap.emplace(Addr, true);
- return true;
-}
-return false;
+return testAndSet(Addr, isUncondJump,
IsUncondJumpMap).value_or(true);
};
for (auto &[Trace, Info] : Traces) {
@@ -574,7 +561,8 @@ void DataAggregator::imputeFallThroughs() {
? AggregateFallthroughSize / AggregateCount
: !checkUncondJump(Trace.From);
Trace.To = Trace.From + InferredBytes;
- outs() << "Inferred " << Trace << " " << InferredBytes << '\n';
+ LLVM_DEBUG(dbgs() << "imputed " << Trace << " (" << InferredBytes
+<< " bytes)\n");
++InferredTraces;
} else {
if (CurrentBranch != PrevBranch)
@@ -585,7 +573,8 @@ void DataAggregator::imputeFallThroughs() {
}
PrevBranch = CurrentBranch;
}
- outs() << "Inferred " << InferredTraces << " traces\n";
+ if (opts::Verbosity >= 1)
+outs() << "BOLT-INFO: imputed " << InferredTraces << " traces\n";
}
Error DataAggregator::preprocessProfile(BinaryContext &BC) {
@@ -804,22 +793,10 @@ bool DataAggregator::doInterBranch(BinaryFunction
*FromFunc,
}
bool DataAggregator::checkReturn(uint64_t Addr) {
- auto isReturn = [&](auto MI) { return MI && BC->MIB->isReturn(*MI); };
- if (llvm::is_contained(Returns, Addr))
-return true;
-
- BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
- if (!Func)
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/ShatianWang edited https://github.com/llvm/llvm-project/pull/145258 ___ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
@@ -529,6 +534,49 @@ void DataAggregator::parsePerfData(BinaryContext &BC) {
deleteTempFiles();
}
+void DataAggregator::imputeFallThroughs() {
+ if (Traces.empty())
+return;
+
+ std::pair PrevBranch(Trace::EXTERNAL, Trace::EXTERNAL);
+ uint64_t AggregateCount = 0;
+ uint64_t AggregateFallthroughSize = 0;
+ uint64_t InferredTraces = 0;
+
+ // Helper map with whether the instruction is a call/ret/unconditional branch
+ std::unordered_map IsUncondJumpMap;
+ auto checkUncondJump = [&](const uint64_t Addr) {
+auto isUncondJump = [&](const MCInst &MI) -> bool {
+ return BC->MIB->IsUnconditionalJump(MI);
+};
+return testAndSet(Addr, isUncondJump,
IsUncondJumpMap).value_or(true);
+ };
+
+ for (auto &[Trace, Info] : Traces) {
+if (Trace.From == Trace::EXTERNAL)
+ continue;
+std::pair CurrentBranch(Trace.Branch, Trace.From);
+if (Trace.To == Trace::BR_ONLY) {
+ uint64_t InferredBytes = PrevBranch == CurrentBranch
ShatianWang wrote:
nit: could you add a comment here to explain what this code does (if average is
not available... then...) and why it would work (traces are sorted and BR_ONLY
trace comes last in the group).
Although the information is in the PR summary, putting it down as a comment
here would help future readers to understand the code faster.
https://github.com/llvm/llvm-project/pull/145258
___
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/ShatianWang approved this pull request. This is a simple and elegant solution to the fallthrough undercounting problem. Thanks for working on it. I added a nit comment, but otherwise LGTM. https://github.com/llvm/llvm-project/pull/145258 ___ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/aaupov updated
https://github.com/llvm/llvm-project/pull/145258
>From 9aef8e0a499fa4b9e6bbde910a678a65a0ab7f92 Mon Sep 17 00:00:00 2001
From: Amir Ayupov
Date: Mon, 23 Jun 2025 12:54:06 -0700
Subject: [PATCH] unified checkReturn and checkUncondJump, logging
Created using spr 1.3.4
---
bolt/include/bolt/Profile/DataAggregator.h | 34 ++-
bolt/lib/Profile/DataAggregator.cpp| 49 ++
2 files changed, 46 insertions(+), 37 deletions(-)
diff --git a/bolt/include/bolt/Profile/DataAggregator.h
b/bolt/include/bolt/Profile/DataAggregator.h
index 00c6f56520fdc..364dbdbed841c 100644
--- a/bolt/include/bolt/Profile/DataAggregator.h
+++ b/bolt/include/bolt/Profile/DataAggregator.h
@@ -137,7 +137,7 @@ class DataAggregator : public DataReader {
std::vector> Traces;
/// Pre-populated addresses of returns, coming from pre-aggregated data or
/// disassembly. Used to disambiguate call-continuation fall-throughs.
- std::unordered_set Returns;
+ std::unordered_map Returns;
std::unordered_map BasicSamples;
std::vector MemSamples;
@@ -514,6 +514,38 @@ class DataAggregator : public DataReader {
void printBasicSamplesDiagnostics(uint64_t OutOfRangeSamples) const;
void printBranchStacksDiagnostics(uint64_t IgnoredSamples) const;
+ template
+ std::optional
+ testInstructionAt(const uint64_t Addr,
+std::function Callback) const {
+BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
+if (!Func)
+ return std::nullopt;
+const uint64_t Offset = Addr - Func->getAddress();
+if (Func->hasInstructions()) {
+ if (auto *MI = Func->getInstructionAtOffset(Offset))
+return Callback(*MI);
+} else {
+ if (auto MI = Func->disassembleInstructionAtOffset(Offset))
+return Callback(*MI);
+}
+return std::nullopt;
+ }
+
+ template
+ std::optional testAndSet(const uint64_t Addr,
+ std::function Callback,
+ std::unordered_map &Map) {
+auto It = Map.find(Addr);
+if (It != Map.end())
+ return It->second;
+if (std::optional Res = testInstructionAt(Addr, Callback)) {
+ Map.emplace(Addr, *Res);
+ return *Res;
+}
+return std::nullopt;
+ }
+
public:
/// If perf.data was collected without build ids, the buildid-list may
contain
/// incomplete entries. Return true if the buffer containing
diff --git a/bolt/lib/Profile/DataAggregator.cpp
b/bolt/lib/Profile/DataAggregator.cpp
index 2fcc2561cc212..1323c4f30049d 100644
--- a/bolt/lib/Profile/DataAggregator.cpp
+++ b/bolt/lib/Profile/DataAggregator.cpp
@@ -546,23 +546,10 @@ void DataAggregator::imputeFallThroughs() {
// Helper map with whether the instruction is a call/ret/unconditional branch
std::unordered_map IsUncondJumpMap;
auto checkUncondJump = [&](const uint64_t Addr) {
-auto isUncondJump = [&](auto MI) {
- return MI && BC->MIB->IsUnconditionalJump(*MI);
+auto isUncondJump = [&](const MCInst &MI) -> bool {
+ return BC->MIB->IsUnconditionalJump(MI);
};
-auto It = IsUncondJumpMap.find(Addr);
-if (It != IsUncondJumpMap.end())
- return It->second;
-BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
-if (!Func)
- return false;
-const uint64_t Offset = Addr - Func->getAddress();
-if (Func->hasInstructions()
-? isUncondJump(Func->getInstructionAtOffset(Offset))
-: isUncondJump(Func->disassembleInstructionAtOffset(Offset))) {
- IsUncondJumpMap.emplace(Addr, true);
- return true;
-}
-return false;
+return testAndSet(Addr, isUncondJump,
IsUncondJumpMap).value_or(true);
};
for (auto &[Trace, Info] : Traces) {
@@ -574,7 +561,8 @@ void DataAggregator::imputeFallThroughs() {
? AggregateFallthroughSize / AggregateCount
: !checkUncondJump(Trace.From);
Trace.To = Trace.From + InferredBytes;
- outs() << "Inferred " << Trace << " " << InferredBytes << '\n';
+ LLVM_DEBUG(dbgs() << "imputed " << Trace << " (" << InferredBytes
+<< " bytes)\n");
++InferredTraces;
} else {
if (CurrentBranch != PrevBranch)
@@ -585,7 +573,8 @@ void DataAggregator::imputeFallThroughs() {
}
PrevBranch = CurrentBranch;
}
- outs() << "Inferred " << InferredTraces << " traces\n";
+ if (opts::Verbosity >= 1)
+outs() << "BOLT-INFO: imputed " << InferredTraces << " traces\n";
}
Error DataAggregator::preprocessProfile(BinaryContext &BC) {
@@ -804,22 +793,10 @@ bool DataAggregator::doInterBranch(BinaryFunction
*FromFunc,
}
bool DataAggregator::checkReturn(uint64_t Addr) {
- auto isReturn = [&](auto MI) { return MI && BC->MIB->isReturn(*MI); };
- if (llvm::is_contained(Returns, Addr))
-return true;
-
- BinaryFunction *Func = getBinaryFunctionContainingAddress(Addr);
- if (!Func)
[llvm-branch-commits] [llvm] [BOLT] Impute missing trace fall-through (PR #145258)
https://github.com/aaupov edited https://github.com/llvm/llvm-project/pull/145258 ___ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
