[BOLT] Optimize basic block loops to avoid n^2 loop #156243
Conversation
|
Thank you for submitting a Pull Request (PR) to the LLVM Project! This PR will be automatically labeled and the relevant teams will be notified. If you wish to, you can add reviewers by using the "Reviewers" section on this page. If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers. If you have further questions, they may be answered by the LLVM GitHub User Guide. You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums. |
|
@llvm/pr-subscribers-bolt Author: Mark Rousskov (Mark-Simulacrum) ChangesThis improves BOLT runtime when optimizing rustc_driver.so from 15 minutes to 7 minutes (or 49 minutes to 37 minutes of userspace time). Full diff: https://github.com/llvm/llvm-project/pull/156243.diff 1 Files Affected:
diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
index 6cac2d0cca2cb..a86e204cae974 100644
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -3591,6 +3591,18 @@ void BinaryFunction::fixBranches() {
auto &MIB = BC.MIB;
MCContext *Ctx = BC.Ctx.get();
+ // Caches `FunctionLayout::nextBasicBlock(IgnoreSplits = false)`.
+ // nextBasicBlock uses linear search to find the next block, so the loop
+ // below becomes O(n^2). This avoids that.
+ DenseMap<BinaryBasicBlock *, BinaryBasicBlock *> nextBasicBlock(
+ Layout.block_size());
+ for (size_t i = 0; i + 1 < Layout.block_size(); i++) {
+ auto current = Layout.block_begin() + i;
+ auto next = Layout.block_begin() + i + 1;
+ if (next != Layout.getFragment((*current)->getFragmentNum()).end())
+ nextBasicBlock.insert(std::pair(*current, *next));
+ }
+
for (BinaryBasicBlock *BB : BasicBlocks) {
const MCSymbol *TBB = nullptr;
const MCSymbol *FBB = nullptr;
@@ -3605,7 +3617,7 @@ void BinaryFunction::fixBranches() {
// Basic block that follows the current one in the final layout.
const BinaryBasicBlock *const NextBB =
- Layout.getBasicBlockAfter(BB, /*IgnoreSplits=*/false);
+ nextBasicBlock.lookup_or(BB, nullptr);
if (BB->succ_size() == 1) {
// __builtin_unreachable() could create a conditional branch that
|
There was a problem hiding this comment.
Hey @Mark-Simulacrum,
Thanks for your patch. Tests appear to hang, however, your current version includes 69ccc39 (now reverted) which caused some issues.
Could you rebase to latest main so we can verify that?
This improves BOLT runtime when optimizing rustc_driver.so from 15 minutes to 7 minutes (49 minutes to 37 minutes of userspace time).
f833920 to
480d48e
Compare
|
Rebased. Can you clarify how you're running tests, so I can iterate locally as well? |
This improves BOLT runtime when optimizing rustc_driver.so from 15 minutes to 7 minutes (or 49 minutes to 37 minutes of userspace time).