1 //===- bolt/Passes/LoopInversionPass.cpp ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the LoopInversionPass class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "bolt/Passes/LoopInversionPass.h"
14 #include "bolt/Core/ParallelUtilities.h"
15
16 using namespace llvm;
17
18 namespace opts {
19 extern cl::OptionCategory BoltCategory;
20
21 extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks;
22
23 static cl::opt<bool> LoopReorder(
24 "loop-inversion-opt",
25 cl::desc("reorder unconditional jump instructions in loops optimization"),
26 cl::init(true), cl::cat(BoltCategory), cl::ReallyHidden);
27 } // namespace opts
28
29 namespace llvm {
30 namespace bolt {
31
runOnFunction(BinaryFunction & BF)32 bool LoopInversionPass::runOnFunction(BinaryFunction &BF) {
33 bool IsChanged = false;
34 if (BF.getLayout().block_size() < 3 || !BF.hasValidProfile())
35 return false;
36
37 BF.getLayout().updateLayoutIndices();
38 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
39 if (BB->succ_size() != 1 || BB->pred_size() != 1)
40 continue;
41
42 BinaryBasicBlock *SuccBB = *BB->succ_begin();
43 BinaryBasicBlock *PredBB = *BB->pred_begin();
44 const unsigned BBIndex = BB->getLayoutIndex();
45 const unsigned SuccBBIndex = SuccBB->getLayoutIndex();
46 if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 &&
47 SuccBB->succ_size() == 2 && BB->isCold() == SuccBB->isCold()) {
48 // Get the second successor (after loop BB)
49 BinaryBasicBlock *SecondSucc = nullptr;
50 for (BinaryBasicBlock *Succ : SuccBB->successors()) {
51 if (Succ != &*BB) {
52 SecondSucc = Succ;
53 break;
54 }
55 }
56
57 assert(SecondSucc != nullptr && "Unable to find a second BB successor");
58 const uint64_t LoopCount = SuccBB->getBranchInfo(*BB).Count;
59 const uint64_t ExitCount = SuccBB->getBranchInfo(*SecondSucc).Count;
60
61 if (LoopCount < ExitCount) {
62 if (BBIndex > SuccBBIndex)
63 continue;
64 } else if (BBIndex < SuccBBIndex) {
65 continue;
66 }
67
68 IsChanged = true;
69 BB->setLayoutIndex(SuccBBIndex);
70 SuccBB->setLayoutIndex(BBIndex);
71 }
72 }
73
74 if (IsChanged) {
75 BinaryFunction::BasicBlockOrderType NewOrder(BF.getLayout().block_begin(),
76 BF.getLayout().block_end());
77 llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) {
78 return BB1->getLayoutIndex() < BB2->getLayoutIndex();
79 });
80 BF.getLayout().update(NewOrder);
81 }
82
83 return IsChanged;
84 }
85
runOnFunctions(BinaryContext & BC)86 void LoopInversionPass::runOnFunctions(BinaryContext &BC) {
87 std::atomic<uint64_t> ModifiedFuncCount{0};
88 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE ||
89 opts::LoopReorder == false)
90 return;
91
92 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
93 if (runOnFunction(BF))
94 ++ModifiedFuncCount;
95 };
96
97 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
98 return !shouldOptimize(BF);
99 };
100
101 ParallelUtilities::runOnEachFunction(
102 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc,
103 "LoopInversionPass");
104
105 outs() << "BOLT-INFO: " << ModifiedFuncCount
106 << " Functions were reordered by LoopInversionPass\n";
107 }
108
109 } // end namespace bolt
110 } // end namespace llvm
111