xref: /llvm-project/bolt/lib/Passes/JTFootprintReduction.cpp (revision 2430a354bfb9e8c08e0dd5f294012b40afb75ce0)
1 //===- bolt/Passes/JTFootprintReduction.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 JTFootprintReduction class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/JTFootprintReduction.h"
14 #include "bolt/Core/BinaryFunctionCallGraph.h"
15 #include "bolt/Passes/DataflowInfoManager.h"
16 #include "llvm/Support/CommandLine.h"
17 
18 #define DEBUG_TYPE "JT"
19 
20 using namespace llvm;
21 using namespace bolt;
22 
23 namespace opts {
24 
25 extern cl::OptionCategory BoltOptCategory;
26 
27 extern cl::opt<unsigned> Verbosity;
28 
29 extern cl::opt<JumpTableSupportLevel> JumpTables;
30 
31 static cl::opt<bool> JTFootprintOnlyPIC(
32     "jt-footprint-optimize-for-icache",
33     cl::desc("with jt-footprint-reduction, only process PIC jumptables and turn"
34              " off other transformations that increase code size"),
35     cl::init(false), cl::ZeroOrMore, cl::cat(BoltOptCategory));
36 
37 } // namespace opts
38 
39 namespace llvm {
40 namespace bolt {
41 
checkOpportunities(BinaryFunction & Function,DataflowInfoManager & Info)42 void JTFootprintReduction::checkOpportunities(BinaryFunction &Function,
43                                               DataflowInfoManager &Info) {
44   BinaryContext &BC = Function.getBinaryContext();
45   std::map<JumpTable *, uint64_t> AllJTs;
46 
47   for (BinaryBasicBlock &BB : Function) {
48     for (MCInst &Inst : BB) {
49       JumpTable *JumpTable = Function.getJumpTable(Inst);
50       if (!JumpTable)
51         continue;
52 
53       AllJTs[JumpTable] += BB.getKnownExecutionCount();
54       ++IndJmps;
55 
56       if (BlacklistedJTs.count(JumpTable)) {
57         ++IndJmpsDenied;
58         continue;
59       }
60 
61       uint64_t Scale;
62       // Try a standard indirect jump matcher
63       std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher =
64           BC.MIB->matchIndJmp(BC.MIB->matchAnyOperand(),
65                               BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
66                               BC.MIB->matchAnyOperand());
67       if (!opts::JTFootprintOnlyPIC &&
68           IndJmpMatcher->match(*BC.MRI, *BC.MIB,
69                                MutableArrayRef<MCInst>(&*BB.begin(), &Inst + 1),
70                                -1) &&
71           Scale == 8) {
72         if (Info.getLivenessAnalysis().scavengeRegAfter(&Inst))
73           continue;
74         BlacklistedJTs.insert(JumpTable);
75         ++IndJmpsDenied;
76         ++NumJTsNoReg;
77         continue;
78       }
79 
80       // Try a PIC matcher. The pattern we are looking for is a PIC JT ind jmp:
81       //    addq    %rdx, %rsi
82       //    addq    %rdx, %rdi
83       //    leaq    DATAat0x402450(%rip), %r11
84       //    movslq  (%r11,%rdx,4), %rcx
85       //    addq    %r11, %rcx
86       //    jmpq    *%rcx # JUMPTABLE @0x402450
87       MCPhysReg BaseReg1;
88       MCPhysReg BaseReg2;
89       uint64_t Offset;
90       std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher =
91           BC.MIB->matchIndJmp(BC.MIB->matchAdd(
92               BC.MIB->matchReg(BaseReg1),
93               BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg2),
94                                 BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
95                                 BC.MIB->matchImm(Offset))));
96       std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICBaseAddrMatcher =
97           BC.MIB->matchIndJmp(
98               BC.MIB->matchAdd(BC.MIB->matchLoadAddr(BC.MIB->matchSymbol()),
99                                BC.MIB->matchAnyOperand()));
100       if (!PICIndJmpMatcher->match(
101               *BC.MRI, *BC.MIB,
102               MutableArrayRef<MCInst>(&*BB.begin(), &Inst + 1), -1) ||
103           Scale != 4 || BaseReg1 != BaseReg2 || Offset != 0 ||
104           !PICBaseAddrMatcher->match(
105               *BC.MRI, *BC.MIB,
106               MutableArrayRef<MCInst>(&*BB.begin(), &Inst + 1), -1)) {
107         BlacklistedJTs.insert(JumpTable);
108         ++IndJmpsDenied;
109         ++NumJTsBadMatch;
110         continue;
111       }
112     }
113   }
114 
115   // Statistics only
116   for (const auto &JTFreq : AllJTs) {
117     JumpTable *JT = JTFreq.first;
118     uint64_t CurScore = JTFreq.second;
119     TotalJTScore += CurScore;
120     if (!BlacklistedJTs.count(JT)) {
121       OptimizedScore += CurScore;
122       if (JT->EntrySize == 8)
123         BytesSaved += JT->getSize() >> 1;
124     }
125   }
126   TotalJTs += AllJTs.size();
127   TotalJTsDenied += BlacklistedJTs.size();
128 }
129 
tryOptimizeNonPIC(BinaryContext & BC,BinaryBasicBlock & BB,BinaryBasicBlock::iterator Inst,uint64_t JTAddr,JumpTable * JumpTable,DataflowInfoManager & Info)130 bool JTFootprintReduction::tryOptimizeNonPIC(
131     BinaryContext &BC, BinaryBasicBlock &BB, BinaryBasicBlock::iterator Inst,
132     uint64_t JTAddr, JumpTable *JumpTable, DataflowInfoManager &Info) {
133   if (opts::JTFootprintOnlyPIC)
134     return false;
135 
136   MCOperand Base;
137   uint64_t Scale;
138   MCPhysReg Index;
139   MCOperand Offset;
140   std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher =
141       BC.MIB->matchIndJmp(BC.MIB->matchAnyOperand(Base),
142                           BC.MIB->matchImm(Scale), BC.MIB->matchReg(Index),
143                           BC.MIB->matchAnyOperand(Offset));
144   if (!IndJmpMatcher->match(*BC.MRI, *BC.MIB,
145                             MutableArrayRef<MCInst>(&*BB.begin(), &*Inst + 1),
146                             -1))
147     return false;
148 
149   assert(Scale == 8 && "Wrong scale");
150 
151   Scale = 4;
152   IndJmpMatcher->annotate(*BC.MIB, "DeleteMe");
153 
154   LivenessAnalysis &LA = Info.getLivenessAnalysis();
155   MCPhysReg Reg = LA.scavengeRegAfter(&*Inst);
156   assert(Reg != 0 && "Register scavenger failed!");
157   MCOperand RegOp = MCOperand::createReg(Reg);
158   SmallVector<MCInst, 4> NewFrag;
159 
160   BC.MIB->createIJmp32Frag(NewFrag, Base, MCOperand::createImm(Scale),
161                            MCOperand::createReg(Index), Offset, RegOp);
162   BC.MIB->setJumpTable(NewFrag.back(), JTAddr, Index);
163 
164   JumpTable->OutputEntrySize = 4;
165 
166   BB.replaceInstruction(Inst, NewFrag.begin(), NewFrag.end());
167   return true;
168 }
169 
tryOptimizePIC(BinaryContext & BC,BinaryBasicBlock & BB,BinaryBasicBlock::iterator Inst,uint64_t JTAddr,JumpTable * JumpTable,DataflowInfoManager & Info)170 bool JTFootprintReduction::tryOptimizePIC(BinaryContext &BC,
171                                           BinaryBasicBlock &BB,
172                                           BinaryBasicBlock::iterator Inst,
173                                           uint64_t JTAddr, JumpTable *JumpTable,
174                                           DataflowInfoManager &Info) {
175   MCPhysReg BaseReg;
176   uint64_t Scale;
177   MCPhysReg Index;
178   MCOperand Offset;
179   MCOperand JumpTableRef;
180   std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher =
181       BC.MIB->matchIndJmp(BC.MIB->matchAdd(
182           BC.MIB->matchLoadAddr(BC.MIB->matchAnyOperand(JumpTableRef)),
183           BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg), BC.MIB->matchImm(Scale),
184                             BC.MIB->matchReg(Index),
185                             BC.MIB->matchAnyOperand())));
186   if (!PICIndJmpMatcher->match(
187           *BC.MRI, *BC.MIB, MutableArrayRef<MCInst>(&*BB.begin(), &*Inst + 1),
188           -1))
189     return false;
190 
191   assert(Scale == 4 && "Wrong scale");
192 
193   PICIndJmpMatcher->annotate(*BC.MIB, "DeleteMe");
194 
195   MCOperand RegOp = MCOperand::createReg(BaseReg);
196   SmallVector<MCInst, 4> NewFrag;
197 
198   BC.MIB->createIJmp32Frag(NewFrag, MCOperand::createReg(0),
199                            MCOperand::createImm(Scale),
200                            MCOperand::createReg(Index), JumpTableRef, RegOp);
201   BC.MIB->setJumpTable(NewFrag.back(), JTAddr, Index);
202 
203   JumpTable->OutputEntrySize = 4;
204   // DePICify
205   JumpTable->Type = JumpTable::JTT_NORMAL;
206 
207   BB.replaceInstruction(Inst, NewFrag.begin(), NewFrag.end());
208   return true;
209 }
210 
optimizeFunction(BinaryFunction & Function,DataflowInfoManager & Info)211 void JTFootprintReduction::optimizeFunction(BinaryFunction &Function,
212                                             DataflowInfoManager &Info) {
213   BinaryContext &BC = Function.getBinaryContext();
214   for (BinaryBasicBlock &BB : Function) {
215     if (!BB.getNumNonPseudos())
216       continue;
217 
218     auto IndJmpRI = BB.getLastNonPseudo();
219     auto IndJmp = std::prev(IndJmpRI.base());
220     const uint64_t JTAddr = BC.MIB->getJumpTable(*IndJmp);
221 
222     if (!JTAddr)
223       continue;
224 
225     JumpTable *JumpTable = Function.getJumpTable(*IndJmp);
226     if (BlacklistedJTs.count(JumpTable))
227       continue;
228 
229     if (tryOptimizeNonPIC(BC, BB, IndJmp, JTAddr, JumpTable, Info) ||
230         tryOptimizePIC(BC, BB, IndJmp, JTAddr, JumpTable, Info)) {
231       Modified.insert(&Function);
232       continue;
233     }
234 
235     llvm_unreachable("Should either optimize PIC or NonPIC successfully");
236   }
237 
238   if (!Modified.count(&Function))
239     return;
240 
241   for (BinaryBasicBlock &BB : Function)
242     for (auto I = BB.begin(); I != BB.end();)
243       if (BC.MIB->hasAnnotation(*I, "DeleteMe"))
244         I = BB.eraseInstruction(I);
245       else
246         ++I;
247 }
248 
runOnFunctions(BinaryContext & BC)249 Error JTFootprintReduction::runOnFunctions(BinaryContext &BC) {
250   if (opts::JumpTables == JTS_BASIC && BC.HasRelocations)
251     return Error::success();
252 
253   std::unique_ptr<RegAnalysis> RA;
254   std::unique_ptr<BinaryFunctionCallGraph> CG;
255   if (!opts::JTFootprintOnlyPIC) {
256     CG.reset(new BinaryFunctionCallGraph(buildCallGraph(BC)));
257     RA.reset(new RegAnalysis(BC, &BC.getBinaryFunctions(), &*CG));
258   }
259   for (auto &BFIt : BC.getBinaryFunctions()) {
260     BinaryFunction &Function = BFIt.second;
261 
262     if (!Function.isSimple() || Function.isIgnored())
263       continue;
264 
265     if (Function.getKnownExecutionCount() == 0)
266       continue;
267 
268     DataflowInfoManager Info(Function, RA.get(), nullptr);
269     BlacklistedJTs.clear();
270     checkOpportunities(Function, Info);
271     optimizeFunction(Function, Info);
272   }
273 
274   if (TotalJTs == TotalJTsDenied) {
275     BC.outs() << "BOLT-INFO: JT Footprint reduction: no changes were made.\n";
276     return Error::success();
277   }
278 
279   BC.outs() << "BOLT-INFO: JT Footprint reduction stats (simple funcs only):\n";
280   if (OptimizedScore)
281     BC.outs() << format("\t   %.2lf%%", (OptimizedScore * 100.0 / TotalJTScore))
282               << " of dynamic JT entries were reduced.\n";
283   BC.outs() << "\t   " << TotalJTs - TotalJTsDenied << " of " << TotalJTs
284             << " jump tables affected.\n";
285   BC.outs() << "\t   " << IndJmps - IndJmpsDenied << " of " << IndJmps
286             << " indirect jumps to JTs affected.\n";
287   BC.outs() << "\t   " << NumJTsBadMatch
288             << " JTs discarded due to unsupported jump pattern.\n";
289   BC.outs() << "\t   " << NumJTsNoReg
290             << " JTs discarded due to register unavailability.\n";
291   BC.outs() << "\t   " << BytesSaved << " bytes saved.\n";
292   return Error::success();
293 }
294 
295 } // namespace bolt
296 } // namespace llvm
297