1 //===- bolt/Passes/SplitFunctions.cpp - Pass for splitting function code --===//
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 SplitFunctions pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/SplitFunctions.h"
14 #include "bolt/Core/BinaryFunction.h"
15 #include "bolt/Core/ParallelUtilities.h"
16 #include "llvm/Support/CommandLine.h"
17 
18 #include <vector>
19 
20 #define DEBUG_TYPE "bolt-opts"
21 
22 using namespace llvm;
23 using namespace bolt;
24 
25 namespace opts {
26 
27 extern cl::OptionCategory BoltOptCategory;
28 
29 extern cl::opt<bool> SplitEH;
30 extern cl::opt<unsigned> ExecutionCountThreshold;
31 
32 static cl::opt<bool>
33 AggressiveSplitting("split-all-cold",
34   cl::desc("outline as many cold basic blocks as possible"),
35   cl::ZeroOrMore,
36   cl::cat(BoltOptCategory));
37 
38 static cl::opt<unsigned>
39 SplitAlignThreshold("split-align-threshold",
40   cl::desc("when deciding to split a function, apply this alignment "
41            "while doing the size comparison (see -split-threshold). "
42            "Default value: 2."),
43   cl::init(2),
44   cl::ZeroOrMore,
45   cl::Hidden,
46   cl::cat(BoltOptCategory));
47 
48 static cl::opt<SplitFunctions::SplittingType>
49 SplitFunctions("split-functions",
50   cl::desc("split functions into hot and cold regions"),
51   cl::init(SplitFunctions::ST_NONE),
52   cl::values(clEnumValN(SplitFunctions::ST_NONE, "0",
53                         "do not split any function"),
54              clEnumValN(SplitFunctions::ST_LARGE, "1",
55                         "in non-relocation mode only split functions too large "
56                         "to fit into original code space"),
57              clEnumValN(SplitFunctions::ST_LARGE, "2",
58                         "same as 1 (backwards compatibility)"),
59              clEnumValN(SplitFunctions::ST_ALL, "3",
60                         "split all functions")),
61   cl::ZeroOrMore,
62   cl::cat(BoltOptCategory));
63 
64 static cl::opt<unsigned>
65 SplitThreshold("split-threshold",
66   cl::desc("split function only if its main size is reduced by more than "
67            "given amount of bytes. Default value: 0, i.e. split iff the "
68            "size is reduced. Note that on some architectures the size can "
69            "increase after splitting."),
70   cl::init(0),
71   cl::ZeroOrMore,
72   cl::Hidden,
73   cl::cat(BoltOptCategory));
74 
75 void syncOptions(BinaryContext &BC) {
76   if (!BC.HasRelocations && opts::SplitFunctions == SplitFunctions::ST_LARGE)
77     opts::SplitFunctions = SplitFunctions::ST_ALL;
78 }
79 
80 } // namespace opts
81 
82 namespace llvm {
83 namespace bolt {
84 
85 bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {
86   // Apply execution count threshold
87   if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)
88     return false;
89 
90   return BinaryFunctionPass::shouldOptimize(BF);
91 }
92 
93 void SplitFunctions::runOnFunctions(BinaryContext &BC) {
94   opts::syncOptions(BC);
95 
96   if (opts::SplitFunctions == SplitFunctions::ST_NONE)
97     return;
98 
99   ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
100     splitFunction(BF);
101   };
102 
103   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
104     return !shouldOptimize(BF);
105   };
106 
107   ParallelUtilities::runOnEachFunction(
108       BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR, WorkFun, SkipFunc,
109       "SplitFunctions");
110 
111   if (SplitBytesHot + SplitBytesCold > 0)
112     outs() << "BOLT-INFO: splitting separates " << SplitBytesHot
113            << " hot bytes from " << SplitBytesCold << " cold bytes "
114            << format("(%.2lf%% of split functions is hot).\n",
115                      100.0 * SplitBytesHot / (SplitBytesHot + SplitBytesCold));
116 }
117 
118 void SplitFunctions::splitFunction(BinaryFunction &BF) {
119   if (!BF.size())
120     return;
121 
122   if (!BF.hasValidProfile())
123     return;
124 
125   bool AllCold = true;
126   for (BinaryBasicBlock *BB : BF.layout()) {
127     uint64_t ExecCount = BB->getExecutionCount();
128     if (ExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
129       return;
130     if (ExecCount != 0)
131       AllCold = false;
132   }
133 
134   if (AllCold)
135     return;
136 
137   BinaryFunction::BasicBlockOrderType PreSplitLayout = BF.getLayout();
138 
139   BinaryContext &BC = BF.getBinaryContext();
140   size_t OriginalHotSize;
141   size_t HotSize;
142   size_t ColdSize;
143   if (BC.isX86()) {
144     std::tie(OriginalHotSize, ColdSize) = BC.calculateEmittedSize(BF);
145     LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
146                       << " pre-split is <0x"
147                       << Twine::utohexstr(OriginalHotSize) << ", 0x"
148                       << Twine::utohexstr(ColdSize) << ">\n");
149   }
150 
151   if (opts::SplitFunctions == SplitFunctions::ST_LARGE && !BC.HasRelocations) {
152     // Split only if the function wouldn't fit.
153     if (OriginalHotSize <= BF.getMaxSize())
154       return;
155   }
156 
157   // Never outline the first basic block.
158   BF.layout_front()->setCanOutline(false);
159   for (BinaryBasicBlock *BB : BF.layout()) {
160     if (!BB->canOutline())
161       continue;
162     if (BB->getExecutionCount() != 0) {
163       BB->setCanOutline(false);
164       continue;
165     }
166     // Do not split extra entry points in aarch64. They can be referred by
167     // using ADRs and when this happens, these blocks cannot be placed far
168     // away due to the limited range in ADR instruction.
169     if (BC.isAArch64() && BB->isEntryPoint()) {
170       BB->setCanOutline(false);
171       continue;
172     }
173     if (BF.hasEHRanges() && !opts::SplitEH) {
174       // We cannot move landing pads (or rather entry points for landing
175       // pads).
176       if (BB->isLandingPad()) {
177         BB->setCanOutline(false);
178         continue;
179       }
180       // We cannot move a block that can throw since exception-handling
181       // runtime cannot deal with split functions. However, if we can guarantee
182       // that the block never throws, it is safe to move the block to
183       // decrease the size of the function.
184       for (MCInst &Instr : *BB) {
185         if (BF.getBinaryContext().MIB->isInvoke(Instr)) {
186           BB->setCanOutline(false);
187           break;
188         }
189       }
190     }
191   }
192 
193   if (opts::AggressiveSplitting) {
194     // All blocks with 0 count that we can move go to the end of the function.
195     // Even if they were natural to cluster formation and were seen in-between
196     // hot basic blocks.
197     std::stable_sort(BF.layout_begin(), BF.layout_end(),
198                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
199                        return A->canOutline() < B->canOutline();
200                      });
201   } else if (BF.hasEHRanges() && !opts::SplitEH) {
202     // Typically functions with exception handling have landing pads at the end.
203     // We cannot move beginning of landing pads, but we can move 0-count blocks
204     // comprising landing pads to the end and thus facilitate splitting.
205     auto FirstLP = BF.layout_begin();
206     while ((*FirstLP)->isLandingPad())
207       ++FirstLP;
208 
209     std::stable_sort(FirstLP, BF.layout_end(),
210                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
211                        return A->canOutline() < B->canOutline();
212                      });
213   }
214 
215   // Separate hot from cold starting from the bottom.
216   for (auto I = BF.layout_rbegin(), E = BF.layout_rend(); I != E; ++I) {
217     BinaryBasicBlock *BB = *I;
218     if (!BB->canOutline())
219       break;
220     BB->setIsCold(true);
221   }
222 
223   // Check the new size to see if it's worth splitting the function.
224   if (BC.isX86() && BF.isSplit()) {
225     std::tie(HotSize, ColdSize) = BC.calculateEmittedSize(BF);
226     LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
227                       << " post-split is <0x" << Twine::utohexstr(HotSize)
228                       << ", 0x" << Twine::utohexstr(ColdSize) << ">\n");
229     if (alignTo(OriginalHotSize, opts::SplitAlignThreshold) <=
230         alignTo(HotSize, opts::SplitAlignThreshold) + opts::SplitThreshold) {
231       LLVM_DEBUG(dbgs() << "Reversing splitting of function " << BF << ":\n  0x"
232                         << Twine::utohexstr(HotSize) << ", 0x"
233                         << Twine::utohexstr(ColdSize) << " -> 0x"
234                         << Twine::utohexstr(OriginalHotSize) << '\n');
235 
236       BF.updateBasicBlockLayout(PreSplitLayout);
237       for (BinaryBasicBlock &BB : BF)
238         BB.setIsCold(false);
239     } else {
240       SplitBytesHot += HotSize;
241       SplitBytesCold += ColdSize;
242     }
243   }
244 }
245 
246 } // namespace bolt
247 } // namespace llvm
248