File: | build/source/bolt/lib/Core/BinaryFunction.cpp |
Warning: | line 4167, column 33 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- bolt/Core/BinaryFunction.cpp - Low-level function ------------------===// | |||
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 BinaryFunction class. | |||
10 | // | |||
11 | //===----------------------------------------------------------------------===// | |||
12 | ||||
13 | #include "bolt/Core/BinaryFunction.h" | |||
14 | #include "bolt/Core/BinaryBasicBlock.h" | |||
15 | #include "bolt/Core/BinaryDomTree.h" | |||
16 | #include "bolt/Core/DynoStats.h" | |||
17 | #include "bolt/Core/HashUtilities.h" | |||
18 | #include "bolt/Core/MCPlusBuilder.h" | |||
19 | #include "bolt/Utils/NameResolver.h" | |||
20 | #include "bolt/Utils/NameShortener.h" | |||
21 | #include "bolt/Utils/Utils.h" | |||
22 | #include "llvm/ADT/STLExtras.h" | |||
23 | #include "llvm/ADT/SmallSet.h" | |||
24 | #include "llvm/ADT/StringExtras.h" | |||
25 | #include "llvm/ADT/StringRef.h" | |||
26 | #include "llvm/Demangle/Demangle.h" | |||
27 | #include "llvm/MC/MCAsmInfo.h" | |||
28 | #include "llvm/MC/MCAsmLayout.h" | |||
29 | #include "llvm/MC/MCContext.h" | |||
30 | #include "llvm/MC/MCDisassembler/MCDisassembler.h" | |||
31 | #include "llvm/MC/MCExpr.h" | |||
32 | #include "llvm/MC/MCInst.h" | |||
33 | #include "llvm/MC/MCInstPrinter.h" | |||
34 | #include "llvm/MC/MCRegisterInfo.h" | |||
35 | #include "llvm/MC/MCSymbol.h" | |||
36 | #include "llvm/Object/ObjectFile.h" | |||
37 | #include "llvm/Support/CommandLine.h" | |||
38 | #include "llvm/Support/Debug.h" | |||
39 | #include "llvm/Support/GraphWriter.h" | |||
40 | #include "llvm/Support/LEB128.h" | |||
41 | #include "llvm/Support/Regex.h" | |||
42 | #include "llvm/Support/Timer.h" | |||
43 | #include "llvm/Support/raw_ostream.h" | |||
44 | #include <functional> | |||
45 | #include <limits> | |||
46 | #include <numeric> | |||
47 | #include <string> | |||
48 | ||||
49 | #define DEBUG_TYPE"bolt" "bolt" | |||
50 | ||||
51 | using namespace llvm; | |||
52 | using namespace bolt; | |||
53 | ||||
54 | namespace opts { | |||
55 | ||||
56 | extern cl::OptionCategory BoltCategory; | |||
57 | extern cl::OptionCategory BoltOptCategory; | |||
58 | extern cl::OptionCategory BoltRelocCategory; | |||
59 | ||||
60 | extern cl::opt<bool> EnableBAT; | |||
61 | extern cl::opt<bool> Instrument; | |||
62 | extern cl::opt<bool> StrictMode; | |||
63 | extern cl::opt<bool> UpdateDebugSections; | |||
64 | extern cl::opt<unsigned> Verbosity; | |||
65 | ||||
66 | extern bool processAllFunctions(); | |||
67 | ||||
68 | cl::opt<bool> CheckEncoding( | |||
69 | "check-encoding", | |||
70 | cl::desc("perform verification of LLVM instruction encoding/decoding. " | |||
71 | "Every instruction in the input is decoded and re-encoded. " | |||
72 | "If the resulting bytes do not match the input, a warning message " | |||
73 | "is printed."), | |||
74 | cl::Hidden, cl::cat(BoltCategory)); | |||
75 | ||||
76 | static cl::opt<bool> DotToolTipCode( | |||
77 | "dot-tooltip-code", | |||
78 | cl::desc("add basic block instructions as tool tips on nodes"), cl::Hidden, | |||
79 | cl::cat(BoltCategory)); | |||
80 | ||||
81 | cl::opt<JumpTableSupportLevel> | |||
82 | JumpTables("jump-tables", | |||
83 | cl::desc("jump tables support (default=basic)"), | |||
84 | cl::init(JTS_BASIC), | |||
85 | cl::values( | |||
86 | clEnumValN(JTS_NONE, "none",llvm::cl::OptionEnumValue { "none", int(JTS_NONE), "do not optimize functions with jump tables" } | |||
87 | "do not optimize functions with jump tables")llvm::cl::OptionEnumValue { "none", int(JTS_NONE), "do not optimize functions with jump tables" }, | |||
88 | clEnumValN(JTS_BASIC, "basic",llvm::cl::OptionEnumValue { "basic", int(JTS_BASIC), "optimize functions with jump tables" } | |||
89 | "optimize functions with jump tables")llvm::cl::OptionEnumValue { "basic", int(JTS_BASIC), "optimize functions with jump tables" }, | |||
90 | clEnumValN(JTS_MOVE, "move",llvm::cl::OptionEnumValue { "move", int(JTS_MOVE), "move jump tables to a separate section" } | |||
91 | "move jump tables to a separate section")llvm::cl::OptionEnumValue { "move", int(JTS_MOVE), "move jump tables to a separate section" }, | |||
92 | clEnumValN(JTS_SPLIT, "split",llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on " "function execution frequency" } | |||
93 | "split jump tables section into hot and cold based on "llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on " "function execution frequency" } | |||
94 | "function execution frequency")llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on " "function execution frequency" }, | |||
95 | clEnumValN(JTS_AGGRESSIVE, "aggressive",llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE) , "aggressively split jump tables section based on usage " "of the tables" } | |||
96 | "aggressively split jump tables section based on usage "llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE) , "aggressively split jump tables section based on usage " "of the tables" } | |||
97 | "of the tables")llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE) , "aggressively split jump tables section based on usage " "of the tables" }), | |||
98 | cl::ZeroOrMore, | |||
99 | cl::cat(BoltOptCategory)); | |||
100 | ||||
101 | static cl::opt<bool> NoScan( | |||
102 | "no-scan", | |||
103 | cl::desc( | |||
104 | "do not scan cold functions for external references (may result in " | |||
105 | "slower binary)"), | |||
106 | cl::Hidden, cl::cat(BoltOptCategory)); | |||
107 | ||||
108 | cl::opt<bool> | |||
109 | PreserveBlocksAlignment("preserve-blocks-alignment", | |||
110 | cl::desc("try to preserve basic block alignment"), | |||
111 | cl::cat(BoltOptCategory)); | |||
112 | ||||
113 | cl::opt<bool> | |||
114 | PrintDynoStats("dyno-stats", | |||
115 | cl::desc("print execution info based on profile"), | |||
116 | cl::cat(BoltCategory)); | |||
117 | ||||
118 | static cl::opt<bool> | |||
119 | PrintDynoStatsOnly("print-dyno-stats-only", | |||
120 | cl::desc("while printing functions output dyno-stats and skip instructions"), | |||
121 | cl::init(false), | |||
122 | cl::Hidden, | |||
123 | cl::cat(BoltCategory)); | |||
124 | ||||
125 | static cl::list<std::string> | |||
126 | PrintOnly("print-only", | |||
127 | cl::CommaSeparated, | |||
128 | cl::desc("list of functions to print"), | |||
129 | cl::value_desc("func1,func2,func3,..."), | |||
130 | cl::Hidden, | |||
131 | cl::cat(BoltCategory)); | |||
132 | ||||
133 | cl::opt<bool> | |||
134 | TimeBuild("time-build", | |||
135 | cl::desc("print time spent constructing binary functions"), | |||
136 | cl::Hidden, cl::cat(BoltCategory)); | |||
137 | ||||
138 | cl::opt<bool> | |||
139 | TrapOnAVX512("trap-avx512", | |||
140 | cl::desc("in relocation mode trap upon entry to any function that uses " | |||
141 | "AVX-512 instructions"), | |||
142 | cl::init(false), | |||
143 | cl::ZeroOrMore, | |||
144 | cl::Hidden, | |||
145 | cl::cat(BoltCategory)); | |||
146 | ||||
147 | bool shouldPrint(const BinaryFunction &Function) { | |||
148 | if (Function.isIgnored()) | |||
149 | return false; | |||
150 | ||||
151 | if (PrintOnly.empty()) | |||
152 | return true; | |||
153 | ||||
154 | for (std::string &Name : opts::PrintOnly) { | |||
155 | if (Function.hasNameRegex(Name)) { | |||
156 | return true; | |||
157 | } | |||
158 | } | |||
159 | ||||
160 | return false; | |||
161 | } | |||
162 | ||||
163 | } // namespace opts | |||
164 | ||||
165 | namespace llvm { | |||
166 | namespace bolt { | |||
167 | ||||
168 | constexpr unsigned BinaryFunction::MinAlign; | |||
169 | ||||
170 | template <typename R> static bool emptyRange(const R &Range) { | |||
171 | return Range.begin() == Range.end(); | |||
172 | } | |||
173 | ||||
174 | /// Gets debug line information for the instruction located at the given | |||
175 | /// address in the original binary. The SMLoc's pointer is used | |||
176 | /// to point to this information, which is represented by a | |||
177 | /// DebugLineTableRowRef. The returned pointer is null if no debug line | |||
178 | /// information for this instruction was found. | |||
179 | static SMLoc findDebugLineInformationForInstructionAt( | |||
180 | uint64_t Address, DWARFUnit *Unit, | |||
181 | const DWARFDebugLine::LineTable *LineTable) { | |||
182 | // We use the pointer in SMLoc to store an instance of DebugLineTableRowRef, | |||
183 | // which occupies 64 bits. Thus, we can only proceed if the struct fits into | |||
184 | // the pointer itself. | |||
185 | assert(sizeof(decltype(SMLoc().getPointer())) >=(static_cast <bool> (sizeof(decltype(SMLoc().getPointer ())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer" ) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\"" , "bolt/lib/Core/BinaryFunction.cpp", 187, __extension__ __PRETTY_FUNCTION__ )) | |||
186 | sizeof(DebugLineTableRowRef) &&(static_cast <bool> (sizeof(decltype(SMLoc().getPointer ())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer" ) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\"" , "bolt/lib/Core/BinaryFunction.cpp", 187, __extension__ __PRETTY_FUNCTION__ )) | |||
187 | "Cannot fit instruction debug line information into SMLoc's pointer")(static_cast <bool> (sizeof(decltype(SMLoc().getPointer ())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer" ) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\"" , "bolt/lib/Core/BinaryFunction.cpp", 187, __extension__ __PRETTY_FUNCTION__ )); | |||
188 | ||||
189 | SMLoc NullResult = DebugLineTableRowRef::NULL_ROW.toSMLoc(); | |||
190 | uint32_t RowIndex = LineTable->lookupAddress( | |||
191 | {Address, object::SectionedAddress::UndefSection}); | |||
192 | if (RowIndex == LineTable->UnknownRowIndex) | |||
193 | return NullResult; | |||
194 | ||||
195 | assert(RowIndex < LineTable->Rows.size() &&(static_cast <bool> (RowIndex < LineTable->Rows.size () && "Line Table lookup returned invalid index.") ? void (0) : __assert_fail ("RowIndex < LineTable->Rows.size() && \"Line Table lookup returned invalid index.\"" , "bolt/lib/Core/BinaryFunction.cpp", 196, __extension__ __PRETTY_FUNCTION__ )) | |||
196 | "Line Table lookup returned invalid index.")(static_cast <bool> (RowIndex < LineTable->Rows.size () && "Line Table lookup returned invalid index.") ? void (0) : __assert_fail ("RowIndex < LineTable->Rows.size() && \"Line Table lookup returned invalid index.\"" , "bolt/lib/Core/BinaryFunction.cpp", 196, __extension__ __PRETTY_FUNCTION__ )); | |||
197 | ||||
198 | decltype(SMLoc().getPointer()) Ptr; | |||
199 | DebugLineTableRowRef *InstructionLocation = | |||
200 | reinterpret_cast<DebugLineTableRowRef *>(&Ptr); | |||
201 | ||||
202 | InstructionLocation->DwCompileUnitIndex = Unit->getOffset(); | |||
203 | InstructionLocation->RowIndex = RowIndex + 1; | |||
204 | ||||
205 | return SMLoc::getFromPointer(Ptr); | |||
206 | } | |||
207 | ||||
208 | static std::string buildSectionName(StringRef Prefix, StringRef Name, | |||
209 | const BinaryContext &BC) { | |||
210 | if (BC.isELF()) | |||
211 | return (Prefix + Name).str(); | |||
212 | static NameShortener NS; | |||
213 | return (Prefix + Twine(NS.getID(Name))).str(); | |||
214 | } | |||
215 | ||||
216 | static raw_ostream &operator<<(raw_ostream &OS, | |||
217 | const BinaryFunction::State State) { | |||
218 | switch (State) { | |||
219 | case BinaryFunction::State::Empty: OS << "empty"; break; | |||
220 | case BinaryFunction::State::Disassembled: OS << "disassembled"; break; | |||
221 | case BinaryFunction::State::CFG: OS << "CFG constructed"; break; | |||
222 | case BinaryFunction::State::CFG_Finalized: OS << "CFG finalized"; break; | |||
223 | case BinaryFunction::State::EmittedCFG: OS << "emitted with CFG"; break; | |||
224 | case BinaryFunction::State::Emitted: OS << "emitted"; break; | |||
225 | } | |||
226 | ||||
227 | return OS; | |||
228 | } | |||
229 | ||||
230 | std::string BinaryFunction::buildCodeSectionName(StringRef Name, | |||
231 | const BinaryContext &BC) { | |||
232 | return buildSectionName(BC.isELF() ? ".local.text." : ".l.text.", Name, BC); | |||
233 | } | |||
234 | ||||
235 | std::string BinaryFunction::buildColdCodeSectionName(StringRef Name, | |||
236 | const BinaryContext &BC) { | |||
237 | return buildSectionName(BC.isELF() ? ".local.cold.text." : ".l.c.text.", Name, | |||
238 | BC); | |||
239 | } | |||
240 | ||||
241 | uint64_t BinaryFunction::Count = 0; | |||
242 | ||||
243 | std::optional<StringRef> | |||
244 | BinaryFunction::hasNameRegex(const StringRef Name) const { | |||
245 | const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str(); | |||
246 | Regex MatchName(RegexName); | |||
247 | return forEachName( | |||
248 | [&MatchName](StringRef Name) { return MatchName.match(Name); }); | |||
249 | } | |||
250 | ||||
251 | std::optional<StringRef> | |||
252 | BinaryFunction::hasRestoredNameRegex(const StringRef Name) const { | |||
253 | const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str(); | |||
254 | Regex MatchName(RegexName); | |||
255 | return forEachName([&MatchName](StringRef Name) { | |||
256 | return MatchName.match(NameResolver::restore(Name)); | |||
257 | }); | |||
258 | } | |||
259 | ||||
260 | std::string BinaryFunction::getDemangledName() const { | |||
261 | StringRef MangledName = NameResolver::restore(getOneName()); | |||
262 | return demangle(MangledName.str()); | |||
263 | } | |||
264 | ||||
265 | BinaryBasicBlock * | |||
266 | BinaryFunction::getBasicBlockContainingOffset(uint64_t Offset) { | |||
267 | if (Offset > Size) | |||
268 | return nullptr; | |||
269 | ||||
270 | if (BasicBlockOffsets.empty()) | |||
271 | return nullptr; | |||
272 | ||||
273 | /* | |||
274 | * This is commented out because it makes BOLT too slow. | |||
275 | * assert(std::is_sorted(BasicBlockOffsets.begin(), | |||
276 | * BasicBlockOffsets.end(), | |||
277 | * CompareBasicBlockOffsets()))); | |||
278 | */ | |||
279 | auto I = | |||
280 | llvm::upper_bound(BasicBlockOffsets, BasicBlockOffset(Offset, nullptr), | |||
281 | CompareBasicBlockOffsets()); | |||
282 | assert(I != BasicBlockOffsets.begin() && "first basic block not at offset 0")(static_cast <bool> (I != BasicBlockOffsets.begin() && "first basic block not at offset 0") ? void (0) : __assert_fail ("I != BasicBlockOffsets.begin() && \"first basic block not at offset 0\"" , "bolt/lib/Core/BinaryFunction.cpp", 282, __extension__ __PRETTY_FUNCTION__ )); | |||
283 | --I; | |||
284 | BinaryBasicBlock *BB = I->second; | |||
285 | return (Offset < BB->getOffset() + BB->getOriginalSize()) ? BB : nullptr; | |||
286 | } | |||
287 | ||||
288 | void BinaryFunction::markUnreachableBlocks() { | |||
289 | std::stack<BinaryBasicBlock *> Stack; | |||
290 | ||||
291 | for (BinaryBasicBlock &BB : blocks()) | |||
292 | BB.markValid(false); | |||
293 | ||||
294 | // Add all entries and landing pads as roots. | |||
295 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
296 | if (isEntryPoint(*BB) || BB->isLandingPad()) { | |||
297 | Stack.push(BB); | |||
298 | BB->markValid(true); | |||
299 | continue; | |||
300 | } | |||
301 | // FIXME: | |||
302 | // Also mark BBs with indirect jumps as reachable, since we do not | |||
303 | // support removing unused jump tables yet (GH-issue20). | |||
304 | for (const MCInst &Inst : *BB) { | |||
305 | if (BC.MIB->getJumpTable(Inst)) { | |||
306 | Stack.push(BB); | |||
307 | BB->markValid(true); | |||
308 | break; | |||
309 | } | |||
310 | } | |||
311 | } | |||
312 | ||||
313 | // Determine reachable BBs from the entry point | |||
314 | while (!Stack.empty()) { | |||
315 | BinaryBasicBlock *BB = Stack.top(); | |||
316 | Stack.pop(); | |||
317 | for (BinaryBasicBlock *Succ : BB->successors()) { | |||
318 | if (Succ->isValid()) | |||
319 | continue; | |||
320 | Succ->markValid(true); | |||
321 | Stack.push(Succ); | |||
322 | } | |||
323 | } | |||
324 | } | |||
325 | ||||
326 | // Any unnecessary fallthrough jumps revealed after calling eraseInvalidBBs | |||
327 | // will be cleaned up by fixBranches(). | |||
328 | std::pair<unsigned, uint64_t> BinaryFunction::eraseInvalidBBs() { | |||
329 | DenseSet<const BinaryBasicBlock *> InvalidBBs; | |||
330 | unsigned Count = 0; | |||
331 | uint64_t Bytes = 0; | |||
332 | for (BinaryBasicBlock *const BB : BasicBlocks) { | |||
333 | if (!BB->isValid()) { | |||
334 | assert(!isEntryPoint(*BB) && "all entry blocks must be valid")(static_cast <bool> (!isEntryPoint(*BB) && "all entry blocks must be valid" ) ? void (0) : __assert_fail ("!isEntryPoint(*BB) && \"all entry blocks must be valid\"" , "bolt/lib/Core/BinaryFunction.cpp", 334, __extension__ __PRETTY_FUNCTION__ )); | |||
335 | InvalidBBs.insert(BB); | |||
336 | ++Count; | |||
337 | Bytes += BC.computeCodeSize(BB->begin(), BB->end()); | |||
338 | } | |||
339 | } | |||
340 | ||||
341 | Layout.eraseBasicBlocks(InvalidBBs); | |||
342 | ||||
343 | BasicBlockListType NewBasicBlocks; | |||
344 | for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) { | |||
345 | BinaryBasicBlock *BB = *I; | |||
346 | if (InvalidBBs.contains(BB)) { | |||
347 | // Make sure the block is removed from the list of predecessors. | |||
348 | BB->removeAllSuccessors(); | |||
349 | DeletedBasicBlocks.push_back(BB); | |||
350 | } else { | |||
351 | NewBasicBlocks.push_back(BB); | |||
352 | } | |||
353 | } | |||
354 | BasicBlocks = std::move(NewBasicBlocks); | |||
355 | ||||
356 | assert(BasicBlocks.size() == Layout.block_size())(static_cast <bool> (BasicBlocks.size() == Layout.block_size ()) ? void (0) : __assert_fail ("BasicBlocks.size() == Layout.block_size()" , "bolt/lib/Core/BinaryFunction.cpp", 356, __extension__ __PRETTY_FUNCTION__ )); | |||
357 | ||||
358 | // Update CFG state if needed | |||
359 | if (Count > 0) | |||
360 | recomputeLandingPads(); | |||
361 | ||||
362 | return std::make_pair(Count, Bytes); | |||
363 | } | |||
364 | ||||
365 | bool BinaryFunction::isForwardCall(const MCSymbol *CalleeSymbol) const { | |||
366 | // This function should work properly before and after function reordering. | |||
367 | // In order to accomplish this, we use the function index (if it is valid). | |||
368 | // If the function indices are not valid, we fall back to the original | |||
369 | // addresses. This should be ok because the functions without valid indices | |||
370 | // should have been ordered with a stable sort. | |||
371 | const BinaryFunction *CalleeBF = BC.getFunctionForSymbol(CalleeSymbol); | |||
372 | if (CalleeBF) { | |||
373 | if (CalleeBF->isInjected()) | |||
374 | return true; | |||
375 | ||||
376 | if (hasValidIndex() && CalleeBF->hasValidIndex()) { | |||
377 | return getIndex() < CalleeBF->getIndex(); | |||
378 | } else if (hasValidIndex() && !CalleeBF->hasValidIndex()) { | |||
379 | return true; | |||
380 | } else if (!hasValidIndex() && CalleeBF->hasValidIndex()) { | |||
381 | return false; | |||
382 | } else { | |||
383 | return getAddress() < CalleeBF->getAddress(); | |||
384 | } | |||
385 | } else { | |||
386 | // Absolute symbol. | |||
387 | ErrorOr<uint64_t> CalleeAddressOrError = BC.getSymbolValue(*CalleeSymbol); | |||
388 | assert(CalleeAddressOrError && "unregistered symbol found")(static_cast <bool> (CalleeAddressOrError && "unregistered symbol found" ) ? void (0) : __assert_fail ("CalleeAddressOrError && \"unregistered symbol found\"" , "bolt/lib/Core/BinaryFunction.cpp", 388, __extension__ __PRETTY_FUNCTION__ )); | |||
389 | return *CalleeAddressOrError > getAddress(); | |||
390 | } | |||
391 | } | |||
392 | ||||
393 | void BinaryFunction::dump() const { | |||
394 | // getDynoStats calls FunctionLayout::updateLayoutIndices and | |||
395 | // BasicBlock::analyzeBranch. The former cannot be const, but should be | |||
396 | // removed, the latter should be made const, but seems to require refactoring. | |||
397 | // Forcing all callers to have a non-const reference to BinaryFunction to call | |||
398 | // dump non-const however is not ideal either. Adding this const_cast is right | |||
399 | // now the best solution. It is safe, because BinaryFunction itself is not | |||
400 | // modified. Only BinaryBasicBlocks are actually modified (if it all) and we | |||
401 | // have mutable pointers to those regardless whether this function is | |||
402 | // const-qualified or not. | |||
403 | const_cast<BinaryFunction &>(*this).print(dbgs(), ""); | |||
404 | } | |||
405 | ||||
406 | void BinaryFunction::print(raw_ostream &OS, std::string Annotation) { | |||
407 | if (!opts::shouldPrint(*this)) | |||
408 | return; | |||
409 | ||||
410 | StringRef SectionName = | |||
411 | OriginSection ? OriginSection->getName() : "<no origin section>"; | |||
412 | OS << "Binary Function \"" << *this << "\" " << Annotation << " {"; | |||
413 | std::vector<StringRef> AllNames = getNames(); | |||
414 | if (AllNames.size() > 1) { | |||
415 | OS << "\n All names : "; | |||
416 | const char *Sep = ""; | |||
417 | for (const StringRef &Name : AllNames) { | |||
418 | OS << Sep << Name; | |||
419 | Sep = "\n "; | |||
420 | } | |||
421 | } | |||
422 | OS << "\n Number : " << FunctionNumber; | |||
423 | OS << "\n State : " << CurrentState; | |||
424 | OS << "\n Address : 0x" << Twine::utohexstr(Address); | |||
425 | OS << "\n Size : 0x" << Twine::utohexstr(Size); | |||
426 | OS << "\n MaxSize : 0x" << Twine::utohexstr(MaxSize); | |||
427 | OS << "\n Offset : 0x" << Twine::utohexstr(getFileOffset()); | |||
428 | OS << "\n Section : " << SectionName; | |||
429 | OS << "\n Orc Section : " << getCodeSectionName(); | |||
430 | OS << "\n LSDA : 0x" << Twine::utohexstr(getLSDAAddress()); | |||
431 | OS << "\n IsSimple : " << IsSimple; | |||
432 | OS << "\n IsMultiEntry: " << isMultiEntry(); | |||
433 | OS << "\n IsSplit : " << isSplit(); | |||
434 | OS << "\n BB Count : " << size(); | |||
435 | ||||
436 | if (HasFixedIndirectBranch) | |||
437 | OS << "\n HasFixedIndirectBranch : true"; | |||
438 | if (HasUnknownControlFlow) | |||
439 | OS << "\n Unknown CF : true"; | |||
440 | if (getPersonalityFunction()) | |||
441 | OS << "\n Personality : " << getPersonalityFunction()->getName(); | |||
442 | if (IsFragment) | |||
443 | OS << "\n IsFragment : true"; | |||
444 | if (isFolded()) | |||
445 | OS << "\n FoldedInto : " << *getFoldedIntoFunction(); | |||
446 | for (BinaryFunction *ParentFragment : ParentFragments) | |||
447 | OS << "\n Parent : " << *ParentFragment; | |||
448 | if (!Fragments.empty()) { | |||
449 | OS << "\n Fragments : "; | |||
450 | ListSeparator LS; | |||
451 | for (BinaryFunction *Frag : Fragments) | |||
452 | OS << LS << *Frag; | |||
453 | } | |||
454 | if (hasCFG()) | |||
455 | OS << "\n Hash : " << Twine::utohexstr(computeHash()); | |||
456 | if (isMultiEntry()) { | |||
457 | OS << "\n Secondary Entry Points : "; | |||
458 | ListSeparator LS; | |||
459 | for (const auto &KV : SecondaryEntryPoints) | |||
460 | OS << LS << KV.second->getName(); | |||
461 | } | |||
462 | if (FrameInstructions.size()) | |||
463 | OS << "\n CFI Instrs : " << FrameInstructions.size(); | |||
464 | if (!Layout.block_empty()) { | |||
465 | OS << "\n BB Layout : "; | |||
466 | ListSeparator LS; | |||
467 | for (const BinaryBasicBlock *BB : Layout.blocks()) | |||
468 | OS << LS << BB->getName(); | |||
469 | } | |||
470 | if (getImageAddress()) | |||
471 | OS << "\n Image : 0x" << Twine::utohexstr(getImageAddress()); | |||
472 | if (ExecutionCount != COUNT_NO_PROFILE) { | |||
473 | OS << "\n Exec Count : " << ExecutionCount; | |||
474 | OS << "\n Branch Count: " << RawBranchCount; | |||
475 | OS << "\n Profile Acc : " << format("%.1f%%", ProfileMatchRatio * 100.0f); | |||
476 | } | |||
477 | ||||
478 | if (opts::PrintDynoStats && !getLayout().block_empty()) { | |||
479 | OS << '\n'; | |||
480 | DynoStats dynoStats = getDynoStats(*this); | |||
481 | OS << dynoStats; | |||
482 | } | |||
483 | ||||
484 | OS << "\n}\n"; | |||
485 | ||||
486 | if (opts::PrintDynoStatsOnly || !BC.InstPrinter) | |||
487 | return; | |||
488 | ||||
489 | // Offset of the instruction in function. | |||
490 | uint64_t Offset = 0; | |||
491 | ||||
492 | if (BasicBlocks.empty() && !Instructions.empty()) { | |||
493 | // Print before CFG was built. | |||
494 | for (const std::pair<const uint32_t, MCInst> &II : Instructions) { | |||
495 | Offset = II.first; | |||
496 | ||||
497 | // Print label if exists at this offset. | |||
498 | auto LI = Labels.find(Offset); | |||
499 | if (LI != Labels.end()) { | |||
500 | if (const MCSymbol *EntrySymbol = | |||
501 | getSecondaryEntryPointSymbol(LI->second)) | |||
502 | OS << EntrySymbol->getName() << " (Entry Point):\n"; | |||
503 | OS << LI->second->getName() << ":\n"; | |||
504 | } | |||
505 | ||||
506 | BC.printInstruction(OS, II.second, Offset, this); | |||
507 | } | |||
508 | } | |||
509 | ||||
510 | StringRef SplitPointMsg = ""; | |||
511 | for (const FunctionFragment &FF : Layout.fragments()) { | |||
512 | OS << SplitPointMsg; | |||
513 | SplitPointMsg = "------- HOT-COLD SPLIT POINT -------\n\n"; | |||
514 | for (const BinaryBasicBlock *BB : FF) { | |||
515 | OS << BB->getName() << " (" << BB->size() | |||
516 | << " instructions, align : " << BB->getAlignment() << ")\n"; | |||
517 | ||||
518 | if (isEntryPoint(*BB)) { | |||
519 | if (MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB)) | |||
520 | OS << " Secondary Entry Point: " << EntrySymbol->getName() << '\n'; | |||
521 | else | |||
522 | OS << " Entry Point\n"; | |||
523 | } | |||
524 | ||||
525 | if (BB->isLandingPad()) | |||
526 | OS << " Landing Pad\n"; | |||
527 | ||||
528 | uint64_t BBExecCount = BB->getExecutionCount(); | |||
529 | if (hasValidProfile()) { | |||
530 | OS << " Exec Count : "; | |||
531 | if (BB->getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE) | |||
532 | OS << BBExecCount << '\n'; | |||
533 | else | |||
534 | OS << "<unknown>\n"; | |||
535 | } | |||
536 | if (BB->getCFIState() >= 0) | |||
537 | OS << " CFI State : " << BB->getCFIState() << '\n'; | |||
538 | if (opts::EnableBAT) { | |||
539 | OS << " Input offset: " << Twine::utohexstr(BB->getInputOffset()) | |||
540 | << "\n"; | |||
541 | } | |||
542 | if (!BB->pred_empty()) { | |||
543 | OS << " Predecessors: "; | |||
544 | ListSeparator LS; | |||
545 | for (BinaryBasicBlock *Pred : BB->predecessors()) | |||
546 | OS << LS << Pred->getName(); | |||
547 | OS << '\n'; | |||
548 | } | |||
549 | if (!BB->throw_empty()) { | |||
550 | OS << " Throwers: "; | |||
551 | ListSeparator LS; | |||
552 | for (BinaryBasicBlock *Throw : BB->throwers()) | |||
553 | OS << LS << Throw->getName(); | |||
554 | OS << '\n'; | |||
555 | } | |||
556 | ||||
557 | Offset = alignTo(Offset, BB->getAlignment()); | |||
558 | ||||
559 | // Note: offsets are imprecise since this is happening prior to | |||
560 | // relaxation. | |||
561 | Offset = BC.printInstructions(OS, BB->begin(), BB->end(), Offset, this); | |||
562 | ||||
563 | if (!BB->succ_empty()) { | |||
564 | OS << " Successors: "; | |||
565 | // For more than 2 successors, sort them based on frequency. | |||
566 | std::vector<uint64_t> Indices(BB->succ_size()); | |||
567 | std::iota(Indices.begin(), Indices.end(), 0); | |||
568 | if (BB->succ_size() > 2 && BB->getKnownExecutionCount()) { | |||
569 | llvm::stable_sort(Indices, [&](const uint64_t A, const uint64_t B) { | |||
570 | return BB->BranchInfo[B] < BB->BranchInfo[A]; | |||
571 | }); | |||
572 | } | |||
573 | ListSeparator LS; | |||
574 | for (unsigned I = 0; I < Indices.size(); ++I) { | |||
575 | BinaryBasicBlock *Succ = BB->Successors[Indices[I]]; | |||
576 | const BinaryBasicBlock::BinaryBranchInfo &BI = | |||
577 | BB->BranchInfo[Indices[I]]; | |||
578 | OS << LS << Succ->getName(); | |||
579 | if (ExecutionCount != COUNT_NO_PROFILE && | |||
580 | BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) { | |||
581 | OS << " (mispreds: " << BI.MispredictedCount | |||
582 | << ", count: " << BI.Count << ")"; | |||
583 | } else if (ExecutionCount != COUNT_NO_PROFILE && | |||
584 | BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE) { | |||
585 | OS << " (inferred count: " << BI.Count << ")"; | |||
586 | } | |||
587 | } | |||
588 | OS << '\n'; | |||
589 | } | |||
590 | ||||
591 | if (!BB->lp_empty()) { | |||
592 | OS << " Landing Pads: "; | |||
593 | ListSeparator LS; | |||
594 | for (BinaryBasicBlock *LP : BB->landing_pads()) { | |||
595 | OS << LS << LP->getName(); | |||
596 | if (ExecutionCount != COUNT_NO_PROFILE) { | |||
597 | OS << " (count: " << LP->getExecutionCount() << ")"; | |||
598 | } | |||
599 | } | |||
600 | OS << '\n'; | |||
601 | } | |||
602 | ||||
603 | // In CFG_Finalized state we can miscalculate CFI state at exit. | |||
604 | if (CurrentState == State::CFG) { | |||
605 | const int32_t CFIStateAtExit = BB->getCFIStateAtExit(); | |||
606 | if (CFIStateAtExit >= 0) | |||
607 | OS << " CFI State: " << CFIStateAtExit << '\n'; | |||
608 | } | |||
609 | ||||
610 | OS << '\n'; | |||
611 | } | |||
612 | } | |||
613 | ||||
614 | // Dump new exception ranges for the function. | |||
615 | if (!CallSites.empty()) { | |||
616 | OS << "EH table:\n"; | |||
617 | for (const FunctionFragment &FF : getLayout().fragments()) { | |||
618 | for (const auto &FCSI : getCallSites(FF.getFragmentNum())) { | |||
619 | const CallSite &CSI = FCSI.second; | |||
620 | OS << " [" << *CSI.Start << ", " << *CSI.End << ") landing pad : "; | |||
621 | if (CSI.LP) | |||
622 | OS << *CSI.LP; | |||
623 | else | |||
624 | OS << "0"; | |||
625 | OS << ", action : " << CSI.Action << '\n'; | |||
626 | } | |||
627 | } | |||
628 | OS << '\n'; | |||
629 | } | |||
630 | ||||
631 | // Print all jump tables. | |||
632 | for (const std::pair<const uint64_t, JumpTable *> &JTI : JumpTables) | |||
633 | JTI.second->print(OS); | |||
634 | ||||
635 | OS << "DWARF CFI Instructions:\n"; | |||
636 | if (OffsetToCFI.size()) { | |||
637 | // Pre-buildCFG information | |||
638 | for (const std::pair<const uint32_t, uint32_t> &Elmt : OffsetToCFI) { | |||
639 | OS << format(" %08x:\t", Elmt.first); | |||
640 | assert(Elmt.second < FrameInstructions.size() && "Incorrect CFI offset")(static_cast <bool> (Elmt.second < FrameInstructions .size() && "Incorrect CFI offset") ? void (0) : __assert_fail ("Elmt.second < FrameInstructions.size() && \"Incorrect CFI offset\"" , "bolt/lib/Core/BinaryFunction.cpp", 640, __extension__ __PRETTY_FUNCTION__ )); | |||
641 | BinaryContext::printCFI(OS, FrameInstructions[Elmt.second]); | |||
642 | OS << "\n"; | |||
643 | } | |||
644 | } else { | |||
645 | // Post-buildCFG information | |||
646 | for (uint32_t I = 0, E = FrameInstructions.size(); I != E; ++I) { | |||
647 | const MCCFIInstruction &CFI = FrameInstructions[I]; | |||
648 | OS << format(" %d:\t", I); | |||
649 | BinaryContext::printCFI(OS, CFI); | |||
650 | OS << "\n"; | |||
651 | } | |||
652 | } | |||
653 | if (FrameInstructions.empty()) | |||
654 | OS << " <empty>\n"; | |||
655 | ||||
656 | OS << "End of Function \"" << *this << "\"\n\n"; | |||
657 | } | |||
658 | ||||
659 | void BinaryFunction::printRelocations(raw_ostream &OS, uint64_t Offset, | |||
660 | uint64_t Size) const { | |||
661 | const char *Sep = " # Relocs: "; | |||
662 | ||||
663 | auto RI = Relocations.lower_bound(Offset); | |||
664 | while (RI != Relocations.end() && RI->first < Offset + Size) { | |||
665 | OS << Sep << "(R: " << RI->second << ")"; | |||
666 | Sep = ", "; | |||
667 | ++RI; | |||
668 | } | |||
669 | } | |||
670 | ||||
671 | static std::string mutateDWARFExpressionTargetReg(const MCCFIInstruction &Instr, | |||
672 | MCPhysReg NewReg) { | |||
673 | StringRef ExprBytes = Instr.getValues(); | |||
674 | assert(ExprBytes.size() > 1 && "DWARF expression CFI is too short")(static_cast <bool> (ExprBytes.size() > 1 && "DWARF expression CFI is too short") ? void (0) : __assert_fail ("ExprBytes.size() > 1 && \"DWARF expression CFI is too short\"" , "bolt/lib/Core/BinaryFunction.cpp", 674, __extension__ __PRETTY_FUNCTION__ )); | |||
675 | uint8_t Opcode = ExprBytes[0]; | |||
676 | assert((Opcode == dwarf::DW_CFA_expression ||(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI" ) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\"" , "bolt/lib/Core/BinaryFunction.cpp", 678, __extension__ __PRETTY_FUNCTION__ )) | |||
677 | Opcode == dwarf::DW_CFA_val_expression) &&(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI" ) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\"" , "bolt/lib/Core/BinaryFunction.cpp", 678, __extension__ __PRETTY_FUNCTION__ )) | |||
678 | "invalid DWARF expression CFI")(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI" ) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\"" , "bolt/lib/Core/BinaryFunction.cpp", 678, __extension__ __PRETTY_FUNCTION__ )); | |||
679 | (void)Opcode; | |||
680 | const uint8_t *const Start = | |||
681 | reinterpret_cast<const uint8_t *>(ExprBytes.drop_front(1).data()); | |||
682 | const uint8_t *const End = | |||
683 | reinterpret_cast<const uint8_t *>(Start + ExprBytes.size() - 1); | |||
684 | unsigned Size = 0; | |||
685 | decodeULEB128(Start, &Size, End); | |||
686 | assert(Size > 0 && "Invalid reg encoding for DWARF expression CFI")(static_cast <bool> (Size > 0 && "Invalid reg encoding for DWARF expression CFI" ) ? void (0) : __assert_fail ("Size > 0 && \"Invalid reg encoding for DWARF expression CFI\"" , "bolt/lib/Core/BinaryFunction.cpp", 686, __extension__ __PRETTY_FUNCTION__ )); | |||
687 | SmallString<8> Tmp; | |||
688 | raw_svector_ostream OSE(Tmp); | |||
689 | encodeULEB128(NewReg, OSE); | |||
690 | return Twine(ExprBytes.slice(0, 1)) | |||
691 | .concat(OSE.str()) | |||
692 | .concat(ExprBytes.drop_front(1 + Size)) | |||
693 | .str(); | |||
694 | } | |||
695 | ||||
696 | void BinaryFunction::mutateCFIRegisterFor(const MCInst &Instr, | |||
697 | MCPhysReg NewReg) { | |||
698 | const MCCFIInstruction *OldCFI = getCFIFor(Instr); | |||
699 | assert(OldCFI && "invalid CFI instr")(static_cast <bool> (OldCFI && "invalid CFI instr" ) ? void (0) : __assert_fail ("OldCFI && \"invalid CFI instr\"" , "bolt/lib/Core/BinaryFunction.cpp", 699, __extension__ __PRETTY_FUNCTION__ )); | |||
700 | switch (OldCFI->getOperation()) { | |||
701 | default: | |||
702 | llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "bolt/lib/Core/BinaryFunction.cpp" , 702); | |||
703 | case MCCFIInstruction::OpDefCfa: | |||
704 | setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, NewReg, | |||
705 | OldCFI->getOffset())); | |||
706 | break; | |||
707 | case MCCFIInstruction::OpDefCfaRegister: | |||
708 | setCFIFor(Instr, MCCFIInstruction::createDefCfaRegister(nullptr, NewReg)); | |||
709 | break; | |||
710 | case MCCFIInstruction::OpOffset: | |||
711 | setCFIFor(Instr, MCCFIInstruction::createOffset(nullptr, NewReg, | |||
712 | OldCFI->getOffset())); | |||
713 | break; | |||
714 | case MCCFIInstruction::OpRegister: | |||
715 | setCFIFor(Instr, MCCFIInstruction::createRegister(nullptr, NewReg, | |||
716 | OldCFI->getRegister2())); | |||
717 | break; | |||
718 | case MCCFIInstruction::OpSameValue: | |||
719 | setCFIFor(Instr, MCCFIInstruction::createSameValue(nullptr, NewReg)); | |||
720 | break; | |||
721 | case MCCFIInstruction::OpEscape: | |||
722 | setCFIFor(Instr, | |||
723 | MCCFIInstruction::createEscape( | |||
724 | nullptr, | |||
725 | StringRef(mutateDWARFExpressionTargetReg(*OldCFI, NewReg)))); | |||
726 | break; | |||
727 | case MCCFIInstruction::OpRestore: | |||
728 | setCFIFor(Instr, MCCFIInstruction::createRestore(nullptr, NewReg)); | |||
729 | break; | |||
730 | case MCCFIInstruction::OpUndefined: | |||
731 | setCFIFor(Instr, MCCFIInstruction::createUndefined(nullptr, NewReg)); | |||
732 | break; | |||
733 | } | |||
734 | } | |||
735 | ||||
736 | const MCCFIInstruction *BinaryFunction::mutateCFIOffsetFor(const MCInst &Instr, | |||
737 | int64_t NewOffset) { | |||
738 | const MCCFIInstruction *OldCFI = getCFIFor(Instr); | |||
739 | assert(OldCFI && "invalid CFI instr")(static_cast <bool> (OldCFI && "invalid CFI instr" ) ? void (0) : __assert_fail ("OldCFI && \"invalid CFI instr\"" , "bolt/lib/Core/BinaryFunction.cpp", 739, __extension__ __PRETTY_FUNCTION__ )); | |||
740 | switch (OldCFI->getOperation()) { | |||
741 | default: | |||
742 | llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "bolt/lib/Core/BinaryFunction.cpp" , 742); | |||
743 | case MCCFIInstruction::OpDefCfaOffset: | |||
744 | setCFIFor(Instr, MCCFIInstruction::cfiDefCfaOffset(nullptr, NewOffset)); | |||
745 | break; | |||
746 | case MCCFIInstruction::OpAdjustCfaOffset: | |||
747 | setCFIFor(Instr, | |||
748 | MCCFIInstruction::createAdjustCfaOffset(nullptr, NewOffset)); | |||
749 | break; | |||
750 | case MCCFIInstruction::OpDefCfa: | |||
751 | setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, OldCFI->getRegister(), | |||
752 | NewOffset)); | |||
753 | break; | |||
754 | case MCCFIInstruction::OpOffset: | |||
755 | setCFIFor(Instr, MCCFIInstruction::createOffset( | |||
756 | nullptr, OldCFI->getRegister(), NewOffset)); | |||
757 | break; | |||
758 | } | |||
759 | return getCFIFor(Instr); | |||
760 | } | |||
761 | ||||
762 | IndirectBranchType | |||
763 | BinaryFunction::processIndirectBranch(MCInst &Instruction, unsigned Size, | |||
764 | uint64_t Offset, | |||
765 | uint64_t &TargetAddress) { | |||
766 | const unsigned PtrSize = BC.AsmInfo->getCodePointerSize(); | |||
767 | ||||
768 | // The instruction referencing memory used by the branch instruction. | |||
769 | // It could be the branch instruction itself or one of the instructions | |||
770 | // setting the value of the register used by the branch. | |||
771 | MCInst *MemLocInstr; | |||
772 | ||||
773 | // Address of the table referenced by MemLocInstr. Could be either an | |||
774 | // array of function pointers, or a jump table. | |||
775 | uint64_t ArrayStart = 0; | |||
776 | ||||
777 | unsigned BaseRegNum, IndexRegNum; | |||
778 | int64_t DispValue; | |||
779 | const MCExpr *DispExpr; | |||
780 | ||||
781 | // In AArch, identify the instruction adding the PC-relative offset to | |||
782 | // jump table entries to correctly decode it. | |||
783 | MCInst *PCRelBaseInstr; | |||
784 | uint64_t PCRelAddr = 0; | |||
785 | ||||
786 | auto Begin = Instructions.begin(); | |||
787 | if (BC.isAArch64()) { | |||
788 | PreserveNops = BC.HasRelocations; | |||
789 | // Start at the last label as an approximation of the current basic block. | |||
790 | // This is a heuristic, since the full set of labels have yet to be | |||
791 | // determined | |||
792 | for (const uint32_t Offset : | |||
793 | llvm::make_first_range(llvm::reverse(Labels))) { | |||
794 | auto II = Instructions.find(Offset); | |||
795 | if (II != Instructions.end()) { | |||
796 | Begin = II; | |||
797 | break; | |||
798 | } | |||
799 | } | |||
800 | } | |||
801 | ||||
802 | IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch( | |||
803 | Instruction, Begin, Instructions.end(), PtrSize, MemLocInstr, BaseRegNum, | |||
804 | IndexRegNum, DispValue, DispExpr, PCRelBaseInstr); | |||
805 | ||||
806 | if (BranchType == IndirectBranchType::UNKNOWN && !MemLocInstr) | |||
807 | return BranchType; | |||
808 | ||||
809 | if (MemLocInstr != &Instruction) | |||
810 | IndexRegNum = BC.MIB->getNoRegister(); | |||
811 | ||||
812 | if (BC.isAArch64()) { | |||
813 | const MCSymbol *Sym = BC.MIB->getTargetSymbol(*PCRelBaseInstr, 1); | |||
814 | assert(Sym && "Symbol extraction failed")(static_cast <bool> (Sym && "Symbol extraction failed" ) ? void (0) : __assert_fail ("Sym && \"Symbol extraction failed\"" , "bolt/lib/Core/BinaryFunction.cpp", 814, __extension__ __PRETTY_FUNCTION__ )); | |||
815 | ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*Sym); | |||
816 | if (SymValueOrError) { | |||
817 | PCRelAddr = *SymValueOrError; | |||
818 | } else { | |||
819 | for (std::pair<const uint32_t, MCSymbol *> &Elmt : Labels) { | |||
820 | if (Elmt.second == Sym) { | |||
821 | PCRelAddr = Elmt.first + getAddress(); | |||
822 | break; | |||
823 | } | |||
824 | } | |||
825 | } | |||
826 | uint64_t InstrAddr = 0; | |||
827 | for (auto II = Instructions.rbegin(); II != Instructions.rend(); ++II) { | |||
828 | if (&II->second == PCRelBaseInstr) { | |||
829 | InstrAddr = II->first + getAddress(); | |||
830 | break; | |||
831 | } | |||
832 | } | |||
833 | assert(InstrAddr != 0 && "instruction not found")(static_cast <bool> (InstrAddr != 0 && "instruction not found" ) ? void (0) : __assert_fail ("InstrAddr != 0 && \"instruction not found\"" , "bolt/lib/Core/BinaryFunction.cpp", 833, __extension__ __PRETTY_FUNCTION__ )); | |||
834 | // We do this to avoid spurious references to code locations outside this | |||
835 | // function (for example, if the indirect jump lives in the last basic | |||
836 | // block of the function, it will create a reference to the next function). | |||
837 | // This replaces a symbol reference with an immediate. | |||
838 | BC.MIB->replaceMemOperandDisp(*PCRelBaseInstr, | |||
839 | MCOperand::createImm(PCRelAddr - InstrAddr)); | |||
840 | // FIXME: Disable full jump table processing for AArch64 until we have a | |||
841 | // proper way of determining the jump table limits. | |||
842 | return IndirectBranchType::UNKNOWN; | |||
843 | } | |||
844 | ||||
845 | // RIP-relative addressing should be converted to symbol form by now | |||
846 | // in processed instructions (but not in jump). | |||
847 | if (DispExpr) { | |||
848 | const MCSymbol *TargetSym; | |||
849 | uint64_t TargetOffset; | |||
850 | std::tie(TargetSym, TargetOffset) = BC.MIB->getTargetSymbolInfo(DispExpr); | |||
851 | ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*TargetSym); | |||
852 | assert(SymValueOrError && "global symbol needs a value")(static_cast <bool> (SymValueOrError && "global symbol needs a value" ) ? void (0) : __assert_fail ("SymValueOrError && \"global symbol needs a value\"" , "bolt/lib/Core/BinaryFunction.cpp", 852, __extension__ __PRETTY_FUNCTION__ )); | |||
853 | ArrayStart = *SymValueOrError + TargetOffset; | |||
854 | BaseRegNum = BC.MIB->getNoRegister(); | |||
855 | if (BC.isAArch64()) { | |||
856 | ArrayStart &= ~0xFFFULL; | |||
857 | ArrayStart += DispValue & 0xFFFULL; | |||
858 | } | |||
859 | } else { | |||
860 | ArrayStart = static_cast<uint64_t>(DispValue); | |||
861 | } | |||
862 | ||||
863 | if (BaseRegNum == BC.MRI->getProgramCounter()) | |||
864 | ArrayStart += getAddress() + Offset + Size; | |||
865 | ||||
866 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addressed memory is 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: addressed memory is 0x" << Twine::utohexstr(ArrayStart) << '\n'; } } while (false) | |||
867 | << Twine::utohexstr(ArrayStart) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: addressed memory is 0x" << Twine::utohexstr(ArrayStart) << '\n'; } } while (false); | |||
868 | ||||
869 | ErrorOr<BinarySection &> Section = BC.getSectionForAddress(ArrayStart); | |||
870 | if (!Section) { | |||
871 | // No section - possibly an absolute address. Since we don't allow | |||
872 | // internal function addresses to escape the function scope - we | |||
873 | // consider it a tail call. | |||
874 | if (opts::Verbosity >= 1) { | |||
875 | errs() << "BOLT-WARNING: no section for address 0x" | |||
876 | << Twine::utohexstr(ArrayStart) << " referenced from function " | |||
877 | << *this << '\n'; | |||
878 | } | |||
879 | return IndirectBranchType::POSSIBLE_TAIL_CALL; | |||
880 | } | |||
881 | if (Section->isVirtual()) { | |||
882 | // The contents are filled at runtime. | |||
883 | return IndirectBranchType::POSSIBLE_TAIL_CALL; | |||
884 | } | |||
885 | ||||
886 | if (BranchType == IndirectBranchType::POSSIBLE_FIXED_BRANCH) { | |||
887 | ErrorOr<uint64_t> Value = BC.getPointerAtAddress(ArrayStart); | |||
888 | if (!Value) | |||
889 | return IndirectBranchType::UNKNOWN; | |||
890 | ||||
891 | if (BC.getSectionForAddress(ArrayStart)->isWritable()) | |||
892 | return IndirectBranchType::UNKNOWN; | |||
893 | ||||
894 | outs() << "BOLT-INFO: fixed indirect branch detected in " << *this | |||
895 | << " at 0x" << Twine::utohexstr(getAddress() + Offset) | |||
896 | << " referencing data at 0x" << Twine::utohexstr(ArrayStart) | |||
897 | << " the destination value is 0x" << Twine::utohexstr(*Value) | |||
898 | << '\n'; | |||
899 | ||||
900 | TargetAddress = *Value; | |||
901 | return BranchType; | |||
902 | } | |||
903 | ||||
904 | // Check if there's already a jump table registered at this address. | |||
905 | MemoryContentsType MemType; | |||
906 | if (JumpTable *JT = BC.getJumpTableContainingAddress(ArrayStart)) { | |||
907 | switch (JT->Type) { | |||
908 | case JumpTable::JTT_NORMAL: | |||
909 | MemType = MemoryContentsType::POSSIBLE_JUMP_TABLE; | |||
910 | break; | |||
911 | case JumpTable::JTT_PIC: | |||
912 | MemType = MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE; | |||
913 | break; | |||
914 | } | |||
915 | } else { | |||
916 | MemType = BC.analyzeMemoryAt(ArrayStart, *this); | |||
917 | } | |||
918 | ||||
919 | // Check that jump table type in instruction pattern matches memory contents. | |||
920 | JumpTable::JumpTableType JTType; | |||
921 | if (BranchType == IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE) { | |||
922 | if (MemType != MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE) | |||
923 | return IndirectBranchType::UNKNOWN; | |||
924 | JTType = JumpTable::JTT_PIC; | |||
925 | } else { | |||
926 | if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE) | |||
927 | return IndirectBranchType::UNKNOWN; | |||
928 | ||||
929 | if (MemType == MemoryContentsType::UNKNOWN) | |||
930 | return IndirectBranchType::POSSIBLE_TAIL_CALL; | |||
931 | ||||
932 | BranchType = IndirectBranchType::POSSIBLE_JUMP_TABLE; | |||
933 | JTType = JumpTable::JTT_NORMAL; | |||
934 | } | |||
935 | ||||
936 | // Convert the instruction into jump table branch. | |||
937 | const MCSymbol *JTLabel = BC.getOrCreateJumpTable(*this, ArrayStart, JTType); | |||
938 | BC.MIB->replaceMemOperandDisp(*MemLocInstr, JTLabel, BC.Ctx.get()); | |||
939 | BC.MIB->setJumpTable(Instruction, ArrayStart, IndexRegNum); | |||
940 | ||||
941 | JTSites.emplace_back(Offset, ArrayStart); | |||
942 | ||||
943 | return BranchType; | |||
944 | } | |||
945 | ||||
946 | MCSymbol *BinaryFunction::getOrCreateLocalLabel(uint64_t Address, | |||
947 | bool CreatePastEnd) { | |||
948 | const uint64_t Offset = Address - getAddress(); | |||
949 | ||||
950 | if ((Offset == getSize()) && CreatePastEnd) | |||
951 | return getFunctionEndLabel(); | |||
952 | ||||
953 | auto LI = Labels.find(Offset); | |||
954 | if (LI != Labels.end()) | |||
955 | return LI->second; | |||
956 | ||||
957 | // For AArch64, check if this address is part of a constant island. | |||
958 | if (BC.isAArch64()) { | |||
959 | if (MCSymbol *IslandSym = getOrCreateIslandAccess(Address)) | |||
960 | return IslandSym; | |||
961 | } | |||
962 | ||||
963 | MCSymbol *Label = BC.Ctx->createNamedTempSymbol(); | |||
964 | Labels[Offset] = Label; | |||
965 | ||||
966 | return Label; | |||
967 | } | |||
968 | ||||
969 | ErrorOr<ArrayRef<uint8_t>> BinaryFunction::getData() const { | |||
970 | BinarySection &Section = *getOriginSection(); | |||
971 | assert(Section.containsRange(getAddress(), getMaxSize()) &&(static_cast <bool> (Section.containsRange(getAddress() , getMaxSize()) && "wrong section for function") ? void (0) : __assert_fail ("Section.containsRange(getAddress(), getMaxSize()) && \"wrong section for function\"" , "bolt/lib/Core/BinaryFunction.cpp", 972, __extension__ __PRETTY_FUNCTION__ )) | |||
972 | "wrong section for function")(static_cast <bool> (Section.containsRange(getAddress() , getMaxSize()) && "wrong section for function") ? void (0) : __assert_fail ("Section.containsRange(getAddress(), getMaxSize()) && \"wrong section for function\"" , "bolt/lib/Core/BinaryFunction.cpp", 972, __extension__ __PRETTY_FUNCTION__ )); | |||
973 | ||||
974 | if (!Section.isText() || Section.isVirtual() || !Section.getSize()) | |||
975 | return std::make_error_code(std::errc::bad_address); | |||
976 | ||||
977 | StringRef SectionContents = Section.getContents(); | |||
978 | ||||
979 | assert(SectionContents.size() == Section.getSize() &&(static_cast <bool> (SectionContents.size() == Section. getSize() && "section size mismatch") ? void (0) : __assert_fail ("SectionContents.size() == Section.getSize() && \"section size mismatch\"" , "bolt/lib/Core/BinaryFunction.cpp", 980, __extension__ __PRETTY_FUNCTION__ )) | |||
980 | "section size mismatch")(static_cast <bool> (SectionContents.size() == Section. getSize() && "section size mismatch") ? void (0) : __assert_fail ("SectionContents.size() == Section.getSize() && \"section size mismatch\"" , "bolt/lib/Core/BinaryFunction.cpp", 980, __extension__ __PRETTY_FUNCTION__ )); | |||
981 | ||||
982 | // Function offset from the section start. | |||
983 | uint64_t Offset = getAddress() - Section.getAddress(); | |||
984 | auto *Bytes = reinterpret_cast<const uint8_t *>(SectionContents.data()); | |||
985 | return ArrayRef<uint8_t>(Bytes + Offset, getMaxSize()); | |||
986 | } | |||
987 | ||||
988 | size_t BinaryFunction::getSizeOfDataInCodeAt(uint64_t Offset) const { | |||
989 | if (!Islands) | |||
990 | return 0; | |||
991 | ||||
992 | if (!llvm::is_contained(Islands->DataOffsets, Offset)) | |||
993 | return 0; | |||
994 | ||||
995 | auto Iter = Islands->CodeOffsets.upper_bound(Offset); | |||
996 | if (Iter != Islands->CodeOffsets.end()) | |||
997 | return *Iter - Offset; | |||
998 | return getSize() - Offset; | |||
999 | } | |||
1000 | ||||
1001 | bool BinaryFunction::isZeroPaddingAt(uint64_t Offset) const { | |||
1002 | ArrayRef<uint8_t> FunctionData = *getData(); | |||
1003 | uint64_t EndOfCode = getSize(); | |||
1004 | if (Islands) { | |||
1005 | auto Iter = Islands->DataOffsets.upper_bound(Offset); | |||
1006 | if (Iter != Islands->DataOffsets.end()) | |||
1007 | EndOfCode = *Iter; | |||
1008 | } | |||
1009 | for (uint64_t I = Offset; I < EndOfCode; ++I) | |||
1010 | if (FunctionData[I] != 0) | |||
1011 | return false; | |||
1012 | ||||
1013 | return true; | |||
1014 | } | |||
1015 | ||||
1016 | void BinaryFunction::handlePCRelOperand(MCInst &Instruction, uint64_t Address, | |||
1017 | uint64_t Size) { | |||
1018 | auto &MIB = BC.MIB; | |||
1019 | uint64_t TargetAddress = 0; | |||
1020 | if (!MIB->evaluateMemOperandTarget(Instruction, TargetAddress, Address, | |||
1021 | Size)) { | |||
1022 | errs() << "BOLT-ERROR: PC-relative operand can't be evaluated:\n"; | |||
1023 | BC.InstPrinter->printInst(&Instruction, 0, "", *BC.STI, errs()); | |||
1024 | errs() << '\n'; | |||
1025 | Instruction.dump_pretty(errs(), BC.InstPrinter.get()); | |||
1026 | errs() << '\n'; | |||
1027 | errs() << "BOLT-ERROR: cannot handle PC-relative operand at 0x" | |||
1028 | << Twine::utohexstr(Address) << ". Skipping function " << *this | |||
1029 | << ".\n"; | |||
1030 | if (BC.HasRelocations) | |||
1031 | exit(1); | |||
1032 | IsSimple = false; | |||
1033 | return; | |||
1034 | } | |||
1035 | if (TargetAddress == 0 && opts::Verbosity >= 1) { | |||
1036 | outs() << "BOLT-INFO: PC-relative operand is zero in function " << *this | |||
1037 | << '\n'; | |||
1038 | } | |||
1039 | ||||
1040 | const MCSymbol *TargetSymbol; | |||
1041 | uint64_t TargetOffset; | |||
1042 | std::tie(TargetSymbol, TargetOffset) = | |||
1043 | BC.handleAddressRef(TargetAddress, *this, /*IsPCRel*/ true); | |||
1044 | ||||
1045 | bool ReplaceSuccess = MIB->replaceMemOperandDisp( | |||
1046 | Instruction, TargetSymbol, static_cast<int64_t>(TargetOffset), &*BC.Ctx); | |||
1047 | (void)ReplaceSuccess; | |||
1048 | assert(ReplaceSuccess && "Failed to replace mem operand with symbol+off.")(static_cast <bool> (ReplaceSuccess && "Failed to replace mem operand with symbol+off." ) ? void (0) : __assert_fail ("ReplaceSuccess && \"Failed to replace mem operand with symbol+off.\"" , "bolt/lib/Core/BinaryFunction.cpp", 1048, __extension__ __PRETTY_FUNCTION__ )); | |||
1049 | } | |||
1050 | ||||
1051 | MCSymbol *BinaryFunction::handleExternalReference(MCInst &Instruction, | |||
1052 | uint64_t Size, | |||
1053 | uint64_t Offset, | |||
1054 | uint64_t TargetAddress, | |||
1055 | bool &IsCall) { | |||
1056 | auto &MIB = BC.MIB; | |||
1057 | ||||
1058 | const uint64_t AbsoluteInstrAddr = getAddress() + Offset; | |||
1059 | BC.addInterproceduralReference(this, TargetAddress); | |||
1060 | if (opts::Verbosity >= 2 && !IsCall && Size == 2 && !BC.HasRelocations) { | |||
1061 | errs() << "BOLT-WARNING: relaxed tail call detected at 0x" | |||
1062 | << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this | |||
1063 | << ". Code size will be increased.\n"; | |||
1064 | } | |||
1065 | ||||
1066 | assert(!MIB->isTailCall(Instruction) &&(static_cast <bool> (!MIB->isTailCall(Instruction) && "synthetic tail call instruction found") ? void (0) : __assert_fail ("!MIB->isTailCall(Instruction) && \"synthetic tail call instruction found\"" , "bolt/lib/Core/BinaryFunction.cpp", 1067, __extension__ __PRETTY_FUNCTION__ )) | |||
1067 | "synthetic tail call instruction found")(static_cast <bool> (!MIB->isTailCall(Instruction) && "synthetic tail call instruction found") ? void (0) : __assert_fail ("!MIB->isTailCall(Instruction) && \"synthetic tail call instruction found\"" , "bolt/lib/Core/BinaryFunction.cpp", 1067, __extension__ __PRETTY_FUNCTION__ )); | |||
1068 | ||||
1069 | // This is a call regardless of the opcode. | |||
1070 | // Assign proper opcode for tail calls, so that they could be | |||
1071 | // treated as calls. | |||
1072 | if (!IsCall) { | |||
1073 | if (!MIB->convertJmpToTailCall(Instruction)) { | |||
1074 | assert(MIB->isConditionalBranch(Instruction) &&(static_cast <bool> (MIB->isConditionalBranch(Instruction ) && "unknown tail call instruction") ? void (0) : __assert_fail ("MIB->isConditionalBranch(Instruction) && \"unknown tail call instruction\"" , "bolt/lib/Core/BinaryFunction.cpp", 1075, __extension__ __PRETTY_FUNCTION__ )) | |||
1075 | "unknown tail call instruction")(static_cast <bool> (MIB->isConditionalBranch(Instruction ) && "unknown tail call instruction") ? void (0) : __assert_fail ("MIB->isConditionalBranch(Instruction) && \"unknown tail call instruction\"" , "bolt/lib/Core/BinaryFunction.cpp", 1075, __extension__ __PRETTY_FUNCTION__ )); | |||
1076 | if (opts::Verbosity >= 2) { | |||
1077 | errs() << "BOLT-WARNING: conditional tail call detected in " | |||
1078 | << "function " << *this << " at 0x" | |||
1079 | << Twine::utohexstr(AbsoluteInstrAddr) << ".\n"; | |||
1080 | } | |||
1081 | } | |||
1082 | IsCall = true; | |||
1083 | } | |||
1084 | ||||
1085 | if (opts::Verbosity >= 2 && TargetAddress == 0) { | |||
1086 | // We actually see calls to address 0 in presence of weak | |||
1087 | // symbols originating from libraries. This code is never meant | |||
1088 | // to be executed. | |||
1089 | outs() << "BOLT-INFO: Function " << *this | |||
1090 | << " has a call to address zero.\n"; | |||
1091 | } | |||
1092 | ||||
1093 | return BC.getOrCreateGlobalSymbol(TargetAddress, "FUNCat"); | |||
1094 | } | |||
1095 | ||||
1096 | void BinaryFunction::handleIndirectBranch(MCInst &Instruction, uint64_t Size, | |||
1097 | uint64_t Offset) { | |||
1098 | auto &MIB = BC.MIB; | |||
1099 | uint64_t IndirectTarget = 0; | |||
1100 | IndirectBranchType Result = | |||
1101 | processIndirectBranch(Instruction, Size, Offset, IndirectTarget); | |||
1102 | switch (Result) { | |||
1103 | default: | |||
1104 | llvm_unreachable("unexpected result")::llvm::llvm_unreachable_internal("unexpected result", "bolt/lib/Core/BinaryFunction.cpp" , 1104); | |||
1105 | case IndirectBranchType::POSSIBLE_TAIL_CALL: { | |||
1106 | bool Result = MIB->convertJmpToTailCall(Instruction); | |||
1107 | (void)Result; | |||
1108 | assert(Result)(static_cast <bool> (Result) ? void (0) : __assert_fail ("Result", "bolt/lib/Core/BinaryFunction.cpp", 1108, __extension__ __PRETTY_FUNCTION__)); | |||
1109 | break; | |||
1110 | } | |||
1111 | case IndirectBranchType::POSSIBLE_JUMP_TABLE: | |||
1112 | case IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE: | |||
1113 | if (opts::JumpTables == JTS_NONE) | |||
1114 | IsSimple = false; | |||
1115 | break; | |||
1116 | case IndirectBranchType::POSSIBLE_FIXED_BRANCH: { | |||
1117 | if (containsAddress(IndirectTarget)) { | |||
1118 | const MCSymbol *TargetSymbol = getOrCreateLocalLabel(IndirectTarget); | |||
1119 | Instruction.clear(); | |||
1120 | MIB->createUncondBranch(Instruction, TargetSymbol, BC.Ctx.get()); | |||
1121 | TakenBranches.emplace_back(Offset, IndirectTarget - getAddress()); | |||
1122 | HasFixedIndirectBranch = true; | |||
1123 | } else { | |||
1124 | MIB->convertJmpToTailCall(Instruction); | |||
1125 | BC.addInterproceduralReference(this, IndirectTarget); | |||
1126 | } | |||
1127 | break; | |||
1128 | } | |||
1129 | case IndirectBranchType::UNKNOWN: | |||
1130 | // Keep processing. We'll do more checks and fixes in | |||
1131 | // postProcessIndirectBranches(). | |||
1132 | UnknownIndirectBranchOffsets.emplace(Offset); | |||
1133 | break; | |||
1134 | } | |||
1135 | } | |||
1136 | ||||
1137 | void BinaryFunction::handleAArch64IndirectCall(MCInst &Instruction, | |||
1138 | const uint64_t Offset) { | |||
1139 | auto &MIB = BC.MIB; | |||
1140 | const uint64_t AbsoluteInstrAddr = getAddress() + Offset; | |||
1141 | MCInst *TargetHiBits, *TargetLowBits; | |||
1142 | uint64_t TargetAddress, Count; | |||
1143 | Count = MIB->matchLinkerVeneer(Instructions.begin(), Instructions.end(), | |||
1144 | AbsoluteInstrAddr, Instruction, TargetHiBits, | |||
1145 | TargetLowBits, TargetAddress); | |||
1146 | if (Count) { | |||
1147 | MIB->addAnnotation(Instruction, "AArch64Veneer", true); | |||
1148 | --Count; | |||
1149 | for (auto It = std::prev(Instructions.end()); Count != 0; | |||
1150 | It = std::prev(It), --Count) { | |||
1151 | MIB->addAnnotation(It->second, "AArch64Veneer", true); | |||
1152 | } | |||
1153 | ||||
1154 | BC.addAdrpAddRelocAArch64(*this, *TargetLowBits, *TargetHiBits, | |||
1155 | TargetAddress); | |||
1156 | } | |||
1157 | } | |||
1158 | ||||
1159 | bool BinaryFunction::disassemble() { | |||
1160 | NamedRegionTimer T("disassemble", "Disassemble function", "buildfuncs", | |||
1161 | "Build Binary Functions", opts::TimeBuild); | |||
1162 | ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData(); | |||
1163 | assert(ErrorOrFunctionData && "function data is not available")(static_cast <bool> (ErrorOrFunctionData && "function data is not available" ) ? void (0) : __assert_fail ("ErrorOrFunctionData && \"function data is not available\"" , "bolt/lib/Core/BinaryFunction.cpp", 1163, __extension__ __PRETTY_FUNCTION__ )); | |||
1164 | ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData; | |||
1165 | assert(FunctionData.size() == getMaxSize() &&(static_cast <bool> (FunctionData.size() == getMaxSize( ) && "function size does not match raw data size") ? void (0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\"" , "bolt/lib/Core/BinaryFunction.cpp", 1166, __extension__ __PRETTY_FUNCTION__ )) | |||
1166 | "function size does not match raw data size")(static_cast <bool> (FunctionData.size() == getMaxSize( ) && "function size does not match raw data size") ? void (0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\"" , "bolt/lib/Core/BinaryFunction.cpp", 1166, __extension__ __PRETTY_FUNCTION__ )); | |||
1167 | ||||
1168 | auto &Ctx = BC.Ctx; | |||
1169 | auto &MIB = BC.MIB; | |||
1170 | ||||
1171 | BC.SymbolicDisAsm->setSymbolizer(MIB->createTargetSymbolizer(*this)); | |||
1172 | ||||
1173 | // Insert a label at the beginning of the function. This will be our first | |||
1174 | // basic block. | |||
1175 | Labels[0] = Ctx->createNamedTempSymbol("BB0"); | |||
1176 | ||||
1177 | uint64_t Size = 0; // instruction size | |||
1178 | for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) { | |||
1179 | MCInst Instruction; | |||
1180 | const uint64_t AbsoluteInstrAddr = getAddress() + Offset; | |||
1181 | ||||
1182 | // Check for data inside code and ignore it | |||
1183 | if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) { | |||
1184 | Size = DataInCodeSize; | |||
1185 | continue; | |||
1186 | } | |||
1187 | ||||
1188 | if (!BC.SymbolicDisAsm->getInstruction(Instruction, Size, | |||
1189 | FunctionData.slice(Offset), | |||
1190 | AbsoluteInstrAddr, nulls())) { | |||
1191 | // Functions with "soft" boundaries, e.g. coming from assembly source, | |||
1192 | // can have 0-byte padding at the end. | |||
1193 | if (isZeroPaddingAt(Offset)) | |||
1194 | break; | |||
1195 | ||||
1196 | errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x" | |||
1197 | << Twine::utohexstr(Offset) << " (address 0x" | |||
1198 | << Twine::utohexstr(AbsoluteInstrAddr) << ") in function " << *this | |||
1199 | << '\n'; | |||
1200 | // Some AVX-512 instructions could not be disassembled at all. | |||
1201 | if (BC.HasRelocations && opts::TrapOnAVX512 && BC.isX86()) { | |||
1202 | setTrapOnEntry(); | |||
1203 | BC.TrappedFunctions.push_back(this); | |||
1204 | } else { | |||
1205 | setIgnored(); | |||
1206 | } | |||
1207 | ||||
1208 | break; | |||
1209 | } | |||
1210 | ||||
1211 | // Check integrity of LLVM assembler/disassembler. | |||
1212 | if (opts::CheckEncoding && !BC.MIB->isBranch(Instruction) && | |||
1213 | !BC.MIB->isCall(Instruction) && !BC.MIB->isNoop(Instruction)) { | |||
1214 | if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) { | |||
1215 | errs() << "BOLT-WARNING: mismatching LLVM encoding detected in " | |||
1216 | << "function " << *this << " for instruction :\n"; | |||
1217 | BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr); | |||
1218 | errs() << '\n'; | |||
1219 | } | |||
1220 | } | |||
1221 | ||||
1222 | // Special handling for AVX-512 instructions. | |||
1223 | if (MIB->hasEVEXEncoding(Instruction)) { | |||
1224 | if (BC.HasRelocations && opts::TrapOnAVX512) { | |||
1225 | setTrapOnEntry(); | |||
1226 | BC.TrappedFunctions.push_back(this); | |||
1227 | break; | |||
1228 | } | |||
1229 | ||||
1230 | if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) { | |||
1231 | errs() << "BOLT-WARNING: internal assembler/disassembler error " | |||
1232 | "detected for AVX512 instruction:\n"; | |||
1233 | BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr); | |||
1234 | errs() << " in function " << *this << '\n'; | |||
1235 | setIgnored(); | |||
1236 | break; | |||
1237 | } | |||
1238 | } | |||
1239 | ||||
1240 | if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) { | |||
1241 | uint64_t TargetAddress = 0; | |||
1242 | if (MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size, | |||
1243 | TargetAddress)) { | |||
1244 | // Check if the target is within the same function. Otherwise it's | |||
1245 | // a call, possibly a tail call. | |||
1246 | // | |||
1247 | // If the target *is* the function address it could be either a branch | |||
1248 | // or a recursive call. | |||
1249 | bool IsCall = MIB->isCall(Instruction); | |||
1250 | const bool IsCondBranch = MIB->isConditionalBranch(Instruction); | |||
1251 | MCSymbol *TargetSymbol = nullptr; | |||
1252 | ||||
1253 | if (BC.MIB->isUnsupportedBranch(Instruction.getOpcode())) { | |||
1254 | setIgnored(); | |||
1255 | if (BinaryFunction *TargetFunc = | |||
1256 | BC.getBinaryFunctionContainingAddress(TargetAddress)) | |||
1257 | TargetFunc->setIgnored(); | |||
1258 | } | |||
1259 | ||||
1260 | if (IsCall && containsAddress(TargetAddress)) { | |||
1261 | if (TargetAddress == getAddress()) { | |||
1262 | // Recursive call. | |||
1263 | TargetSymbol = getSymbol(); | |||
1264 | } else { | |||
1265 | if (BC.isX86()) { | |||
1266 | // Dangerous old-style x86 PIC code. We may need to freeze this | |||
1267 | // function, so preserve the function as is for now. | |||
1268 | PreserveNops = true; | |||
1269 | } else { | |||
1270 | errs() << "BOLT-WARNING: internal call detected at 0x" | |||
1271 | << Twine::utohexstr(AbsoluteInstrAddr) << " in function " | |||
1272 | << *this << ". Skipping.\n"; | |||
1273 | IsSimple = false; | |||
1274 | } | |||
1275 | } | |||
1276 | } | |||
1277 | ||||
1278 | if (!TargetSymbol) { | |||
1279 | // Create either local label or external symbol. | |||
1280 | if (containsAddress(TargetAddress)) { | |||
1281 | TargetSymbol = getOrCreateLocalLabel(TargetAddress); | |||
1282 | } else { | |||
1283 | if (TargetAddress == getAddress() + getSize() && | |||
1284 | TargetAddress < getAddress() + getMaxSize() && | |||
1285 | !(BC.isAArch64() && | |||
1286 | BC.handleAArch64Veneer(TargetAddress, /*MatchOnly*/ true))) { | |||
1287 | // Result of __builtin_unreachable(). | |||
1288 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: jump past end detected at 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x" << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this << " : replacing with nop.\n"; } } while (false) | |||
1289 | << Twine::utohexstr(AbsoluteInstrAddr)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x" << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this << " : replacing with nop.\n"; } } while (false) | |||
1290 | << " in function " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x" << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this << " : replacing with nop.\n"; } } while (false) | |||
1291 | << " : replacing with nop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x" << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this << " : replacing with nop.\n"; } } while (false); | |||
1292 | BC.MIB->createNoop(Instruction); | |||
1293 | if (IsCondBranch) { | |||
1294 | // Register branch offset for profile validation. | |||
1295 | IgnoredBranches.emplace_back(Offset, Offset + Size); | |||
1296 | } | |||
1297 | goto add_instruction; | |||
1298 | } | |||
1299 | // May update Instruction and IsCall | |||
1300 | TargetSymbol = handleExternalReference(Instruction, Size, Offset, | |||
1301 | TargetAddress, IsCall); | |||
1302 | } | |||
1303 | } | |||
1304 | ||||
1305 | if (!IsCall) { | |||
1306 | // Add taken branch info. | |||
1307 | TakenBranches.emplace_back(Offset, TargetAddress - getAddress()); | |||
1308 | } | |||
1309 | BC.MIB->replaceBranchTarget(Instruction, TargetSymbol, &*Ctx); | |||
1310 | ||||
1311 | // Mark CTC. | |||
1312 | if (IsCondBranch && IsCall) | |||
1313 | MIB->setConditionalTailCall(Instruction, TargetAddress); | |||
1314 | } else { | |||
1315 | // Could not evaluate branch. Should be an indirect call or an | |||
1316 | // indirect branch. Bail out on the latter case. | |||
1317 | if (MIB->isIndirectBranch(Instruction)) | |||
1318 | handleIndirectBranch(Instruction, Size, Offset); | |||
1319 | // Indirect call. We only need to fix it if the operand is RIP-relative. | |||
1320 | if (IsSimple && MIB->hasPCRelOperand(Instruction)) | |||
1321 | handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size); | |||
1322 | ||||
1323 | if (BC.isAArch64()) | |||
1324 | handleAArch64IndirectCall(Instruction, Offset); | |||
1325 | } | |||
1326 | } else if (BC.isAArch64()) { | |||
1327 | // Check if there's a relocation associated with this instruction. | |||
1328 | bool UsedReloc = false; | |||
1329 | for (auto Itr = Relocations.lower_bound(Offset), | |||
1330 | ItrE = Relocations.lower_bound(Offset + Size); | |||
1331 | Itr != ItrE; ++Itr) { | |||
1332 | const Relocation &Relocation = Itr->second; | |||
1333 | int64_t Value = Relocation.Value; | |||
1334 | const bool Result = BC.MIB->replaceImmWithSymbolRef( | |||
1335 | Instruction, Relocation.Symbol, Relocation.Addend, Ctx.get(), Value, | |||
1336 | Relocation.Type); | |||
1337 | (void)Result; | |||
1338 | assert(Result && "cannot replace immediate with relocation")(static_cast <bool> (Result && "cannot replace immediate with relocation" ) ? void (0) : __assert_fail ("Result && \"cannot replace immediate with relocation\"" , "bolt/lib/Core/BinaryFunction.cpp", 1338, __extension__ __PRETTY_FUNCTION__ )); | |||
1339 | ||||
1340 | // For aarch64, if we replaced an immediate with a symbol from a | |||
1341 | // relocation, we mark it so we do not try to further process a | |||
1342 | // pc-relative operand. All we need is the symbol. | |||
1343 | UsedReloc = true; | |||
1344 | } | |||
1345 | ||||
1346 | if (MIB->hasPCRelOperand(Instruction) && !UsedReloc) | |||
1347 | handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size); | |||
1348 | } | |||
1349 | ||||
1350 | add_instruction: | |||
1351 | if (getDWARFLineTable()) { | |||
1352 | Instruction.setLoc(findDebugLineInformationForInstructionAt( | |||
1353 | AbsoluteInstrAddr, getDWARFUnit(), getDWARFLineTable())); | |||
1354 | } | |||
1355 | ||||
1356 | // Record offset of the instruction for profile matching. | |||
1357 | if (BC.keepOffsetForInstruction(Instruction)) | |||
1358 | MIB->setOffset(Instruction, static_cast<uint32_t>(Offset)); | |||
1359 | ||||
1360 | if (BC.MIB->isNoop(Instruction)) { | |||
1361 | // NOTE: disassembly loses the correct size information for noops. | |||
1362 | // E.g. nopw 0x0(%rax,%rax,1) is 9 bytes, but re-encoded it's only | |||
1363 | // 5 bytes. Preserve the size info using annotations. | |||
1364 | MIB->addAnnotation(Instruction, "Size", static_cast<uint32_t>(Size)); | |||
1365 | } | |||
1366 | ||||
1367 | addInstruction(Offset, std::move(Instruction)); | |||
1368 | } | |||
1369 | ||||
1370 | // Reset symbolizer for the disassembler. | |||
1371 | BC.SymbolicDisAsm->setSymbolizer(nullptr); | |||
1372 | ||||
1373 | if (uint64_t Offset = getFirstInstructionOffset()) | |||
1374 | Labels[Offset] = BC.Ctx->createNamedTempSymbol(); | |||
1375 | ||||
1376 | clearList(Relocations); | |||
1377 | ||||
1378 | if (!IsSimple) { | |||
1379 | clearList(Instructions); | |||
1380 | return false; | |||
1381 | } | |||
1382 | ||||
1383 | updateState(State::Disassembled); | |||
1384 | ||||
1385 | return true; | |||
1386 | } | |||
1387 | ||||
1388 | bool BinaryFunction::scanExternalRefs() { | |||
1389 | bool Success = true; | |||
1390 | bool DisassemblyFailed = false; | |||
1391 | ||||
1392 | // Ignore pseudo functions. | |||
1393 | if (isPseudo()) | |||
1394 | return Success; | |||
1395 | ||||
1396 | if (opts::NoScan) { | |||
1397 | clearList(Relocations); | |||
1398 | clearList(ExternallyReferencedOffsets); | |||
1399 | ||||
1400 | return false; | |||
1401 | } | |||
1402 | ||||
1403 | // List of external references for this function. | |||
1404 | std::vector<Relocation> FunctionRelocations; | |||
1405 | ||||
1406 | static BinaryContext::IndependentCodeEmitter Emitter = | |||
1407 | BC.createIndependentMCCodeEmitter(); | |||
1408 | ||||
1409 | ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData(); | |||
1410 | assert(ErrorOrFunctionData && "function data is not available")(static_cast <bool> (ErrorOrFunctionData && "function data is not available" ) ? void (0) : __assert_fail ("ErrorOrFunctionData && \"function data is not available\"" , "bolt/lib/Core/BinaryFunction.cpp", 1410, __extension__ __PRETTY_FUNCTION__ )); | |||
1411 | ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData; | |||
1412 | assert(FunctionData.size() == getMaxSize() &&(static_cast <bool> (FunctionData.size() == getMaxSize( ) && "function size does not match raw data size") ? void (0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\"" , "bolt/lib/Core/BinaryFunction.cpp", 1413, __extension__ __PRETTY_FUNCTION__ )) | |||
1413 | "function size does not match raw data size")(static_cast <bool> (FunctionData.size() == getMaxSize( ) && "function size does not match raw data size") ? void (0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\"" , "bolt/lib/Core/BinaryFunction.cpp", 1413, __extension__ __PRETTY_FUNCTION__ )); | |||
1414 | ||||
1415 | uint64_t Size = 0; // instruction size | |||
1416 | for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) { | |||
1417 | // Check for data inside code and ignore it | |||
1418 | if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) { | |||
1419 | Size = DataInCodeSize; | |||
1420 | continue; | |||
1421 | } | |||
1422 | ||||
1423 | const uint64_t AbsoluteInstrAddr = getAddress() + Offset; | |||
1424 | MCInst Instruction; | |||
1425 | if (!BC.DisAsm->getInstruction(Instruction, Size, | |||
1426 | FunctionData.slice(Offset), | |||
1427 | AbsoluteInstrAddr, nulls())) { | |||
1428 | if (opts::Verbosity >= 1 && !isZeroPaddingAt(Offset)) { | |||
1429 | errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x" | |||
1430 | << Twine::utohexstr(Offset) << " (address 0x" | |||
1431 | << Twine::utohexstr(AbsoluteInstrAddr) << ") in function " | |||
1432 | << *this << '\n'; | |||
1433 | } | |||
1434 | Success = false; | |||
1435 | DisassemblyFailed = true; | |||
1436 | break; | |||
1437 | } | |||
1438 | ||||
1439 | // Return true if we can skip handling the Target function reference. | |||
1440 | auto ignoreFunctionRef = [&](const BinaryFunction &Target) { | |||
1441 | if (&Target == this) | |||
1442 | return true; | |||
1443 | ||||
1444 | // Note that later we may decide not to emit Target function. In that | |||
1445 | // case, we conservatively create references that will be ignored or | |||
1446 | // resolved to the same function. | |||
1447 | if (!BC.shouldEmit(Target)) | |||
1448 | return true; | |||
1449 | ||||
1450 | return false; | |||
1451 | }; | |||
1452 | ||||
1453 | // Return true if we can ignore reference to the symbol. | |||
1454 | auto ignoreReference = [&](const MCSymbol *TargetSymbol) { | |||
1455 | if (!TargetSymbol) | |||
1456 | return true; | |||
1457 | ||||
1458 | if (BC.forceSymbolRelocations(TargetSymbol->getName())) | |||
1459 | return false; | |||
1460 | ||||
1461 | BinaryFunction *TargetFunction = BC.getFunctionForSymbol(TargetSymbol); | |||
1462 | if (!TargetFunction) | |||
1463 | return true; | |||
1464 | ||||
1465 | return ignoreFunctionRef(*TargetFunction); | |||
1466 | }; | |||
1467 | ||||
1468 | // Detect if the instruction references an address. | |||
1469 | // Without relocations, we can only trust PC-relative address modes. | |||
1470 | uint64_t TargetAddress = 0; | |||
1471 | bool IsPCRel = false; | |||
1472 | bool IsBranch = false; | |||
1473 | if (BC.MIB->hasPCRelOperand(Instruction)) { | |||
1474 | IsPCRel = BC.MIB->evaluateMemOperandTarget(Instruction, TargetAddress, | |||
1475 | AbsoluteInstrAddr, Size); | |||
1476 | } else if (BC.MIB->isCall(Instruction) || BC.MIB->isBranch(Instruction)) { | |||
1477 | IsBranch = BC.MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size, | |||
1478 | TargetAddress); | |||
1479 | } | |||
1480 | ||||
1481 | MCSymbol *TargetSymbol = nullptr; | |||
1482 | ||||
1483 | // Create an entry point at reference address if needed. | |||
1484 | BinaryFunction *TargetFunction = | |||
1485 | BC.getBinaryFunctionContainingAddress(TargetAddress); | |||
1486 | if (TargetFunction && !ignoreFunctionRef(*TargetFunction)) { | |||
1487 | const uint64_t FunctionOffset = | |||
1488 | TargetAddress - TargetFunction->getAddress(); | |||
1489 | TargetSymbol = FunctionOffset | |||
1490 | ? TargetFunction->addEntryPointAtOffset(FunctionOffset) | |||
1491 | : TargetFunction->getSymbol(); | |||
1492 | } | |||
1493 | ||||
1494 | // Can't find more references and not creating relocations. | |||
1495 | if (!BC.HasRelocations) | |||
1496 | continue; | |||
1497 | ||||
1498 | // Create a relocation against the TargetSymbol as the symbol might get | |||
1499 | // moved. | |||
1500 | if (TargetSymbol) { | |||
1501 | if (IsBranch) { | |||
1502 | BC.MIB->replaceBranchTarget(Instruction, TargetSymbol, | |||
1503 | Emitter.LocalCtx.get()); | |||
1504 | } else if (IsPCRel) { | |||
1505 | const MCExpr *Expr = MCSymbolRefExpr::create( | |||
1506 | TargetSymbol, MCSymbolRefExpr::VK_None, *Emitter.LocalCtx.get()); | |||
1507 | BC.MIB->replaceMemOperandDisp( | |||
1508 | Instruction, MCOperand::createExpr(BC.MIB->getTargetExprFor( | |||
1509 | Instruction, Expr, *Emitter.LocalCtx.get(), 0))); | |||
1510 | } | |||
1511 | } | |||
1512 | ||||
1513 | // Create more relocations based on input file relocations. | |||
1514 | bool HasRel = false; | |||
1515 | for (auto Itr = Relocations.lower_bound(Offset), | |||
1516 | ItrE = Relocations.lower_bound(Offset + Size); | |||
1517 | Itr != ItrE; ++Itr) { | |||
1518 | Relocation &Relocation = Itr->second; | |||
1519 | if (Relocation.isPCRelative() && BC.isX86()) | |||
1520 | continue; | |||
1521 | if (ignoreReference(Relocation.Symbol)) | |||
1522 | continue; | |||
1523 | ||||
1524 | int64_t Value = Relocation.Value; | |||
1525 | const bool Result = BC.MIB->replaceImmWithSymbolRef( | |||
1526 | Instruction, Relocation.Symbol, Relocation.Addend, | |||
1527 | Emitter.LocalCtx.get(), Value, Relocation.Type); | |||
1528 | (void)Result; | |||
1529 | assert(Result && "cannot replace immediate with relocation")(static_cast <bool> (Result && "cannot replace immediate with relocation" ) ? void (0) : __assert_fail ("Result && \"cannot replace immediate with relocation\"" , "bolt/lib/Core/BinaryFunction.cpp", 1529, __extension__ __PRETTY_FUNCTION__ )); | |||
1530 | ||||
1531 | HasRel = true; | |||
1532 | } | |||
1533 | ||||
1534 | if (!TargetSymbol && !HasRel) | |||
1535 | continue; | |||
1536 | ||||
1537 | // Emit the instruction using temp emitter and generate relocations. | |||
1538 | SmallString<256> Code; | |||
1539 | SmallVector<MCFixup, 4> Fixups; | |||
1540 | Emitter.MCE->encodeInstruction(Instruction, Code, Fixups, *BC.STI); | |||
1541 | ||||
1542 | // Create relocation for every fixup. | |||
1543 | for (const MCFixup &Fixup : Fixups) { | |||
1544 | std::optional<Relocation> Rel = BC.MIB->createRelocation(Fixup, *BC.MAB); | |||
1545 | if (!Rel) { | |||
1546 | Success = false; | |||
1547 | continue; | |||
1548 | } | |||
1549 | ||||
1550 | if (Relocation::getSizeForType(Rel->Type) < 4) { | |||
1551 | // If the instruction uses a short form, then we might not be able | |||
1552 | // to handle the rewrite without relaxation, and hence cannot reliably | |||
1553 | // create an external reference relocation. | |||
1554 | Success = false; | |||
1555 | continue; | |||
1556 | } | |||
1557 | Rel->Offset += getAddress() - getOriginSection()->getAddress() + Offset; | |||
1558 | FunctionRelocations.push_back(*Rel); | |||
1559 | } | |||
1560 | ||||
1561 | if (!Success) | |||
1562 | break; | |||
1563 | } | |||
1564 | ||||
1565 | // Add relocations unless disassembly failed for this function. | |||
1566 | if (!DisassemblyFailed) | |||
1567 | for (Relocation &Rel : FunctionRelocations) | |||
1568 | getOriginSection()->addPendingRelocation(Rel); | |||
1569 | ||||
1570 | // Inform BinaryContext that this function symbols will not be defined and | |||
1571 | // relocations should not be created against them. | |||
1572 | if (BC.HasRelocations) { | |||
1573 | for (std::pair<const uint32_t, MCSymbol *> &LI : Labels) | |||
1574 | BC.UndefinedSymbols.insert(LI.second); | |||
1575 | for (MCSymbol *const EndLabel : FunctionEndLabels) | |||
1576 | if (EndLabel) | |||
1577 | BC.UndefinedSymbols.insert(EndLabel); | |||
1578 | } | |||
1579 | ||||
1580 | clearList(Relocations); | |||
1581 | clearList(ExternallyReferencedOffsets); | |||
1582 | ||||
1583 | if (Success && BC.HasRelocations) | |||
1584 | HasExternalRefRelocations = true; | |||
1585 | ||||
1586 | if (opts::Verbosity >= 1 && !Success) | |||
1587 | outs() << "BOLT-INFO: failed to scan refs for " << *this << '\n'; | |||
1588 | ||||
1589 | return Success; | |||
1590 | } | |||
1591 | ||||
1592 | void BinaryFunction::postProcessEntryPoints() { | |||
1593 | if (!isSimple()) | |||
1594 | return; | |||
1595 | ||||
1596 | for (auto &KV : Labels) { | |||
1597 | MCSymbol *Label = KV.second; | |||
1598 | if (!getSecondaryEntryPointSymbol(Label)) | |||
1599 | continue; | |||
1600 | ||||
1601 | // In non-relocation mode there's potentially an external undetectable | |||
1602 | // reference to the entry point and hence we cannot move this entry | |||
1603 | // point. Optimizing without moving could be difficult. | |||
1604 | if (!BC.HasRelocations) | |||
1605 | setSimple(false); | |||
1606 | ||||
1607 | const uint32_t Offset = KV.first; | |||
1608 | ||||
1609 | // If we are at Offset 0 and there is no instruction associated with it, | |||
1610 | // this means this is an empty function. Just ignore. If we find an | |||
1611 | // instruction at this offset, this entry point is valid. | |||
1612 | if (!Offset || getInstructionAtOffset(Offset)) | |||
1613 | continue; | |||
1614 | ||||
1615 | // On AArch64 there are legitimate reasons to have references past the | |||
1616 | // end of the function, e.g. jump tables. | |||
1617 | if (BC.isAArch64() && Offset == getSize()) | |||
1618 | continue; | |||
1619 | ||||
1620 | errs() << "BOLT-WARNING: reference in the middle of instruction " | |||
1621 | "detected in function " | |||
1622 | << *this << " at offset 0x" << Twine::utohexstr(Offset) << '\n'; | |||
1623 | if (BC.HasRelocations) | |||
1624 | setIgnored(); | |||
1625 | setSimple(false); | |||
1626 | return; | |||
1627 | } | |||
1628 | } | |||
1629 | ||||
1630 | void BinaryFunction::postProcessJumpTables() { | |||
1631 | // Create labels for all entries. | |||
1632 | for (auto &JTI : JumpTables) { | |||
1633 | JumpTable &JT = *JTI.second; | |||
1634 | if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) { | |||
1635 | opts::JumpTables = JTS_MOVE; | |||
1636 | outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was " | |||
1637 | "detected in function " | |||
1638 | << *this << '\n'; | |||
1639 | } | |||
1640 | if (JT.Entries.empty()) { | |||
1641 | bool HasOneParent = (JT.Parents.size() == 1); | |||
1642 | for (unsigned I = 0; I < JT.EntriesAsAddress.size(); ++I) { | |||
1643 | uint64_t EntryAddress = JT.EntriesAsAddress[I]; | |||
1644 | // builtin_unreachable does not belong to any function | |||
1645 | // Need to handle separately | |||
1646 | bool IsBuiltIn = false; | |||
1647 | for (BinaryFunction *Parent : JT.Parents) { | |||
1648 | if (EntryAddress == Parent->getAddress() + Parent->getSize()) { | |||
1649 | IsBuiltIn = true; | |||
1650 | // Specify second parameter as true to accept builtin_unreachable | |||
1651 | MCSymbol *Label = getOrCreateLocalLabel(EntryAddress, true); | |||
1652 | JT.Entries.push_back(Label); | |||
1653 | break; | |||
1654 | } | |||
1655 | } | |||
1656 | if (IsBuiltIn) | |||
1657 | continue; | |||
1658 | // Create local label for targets cannot be reached by other fragments | |||
1659 | // Otherwise, secondary entry point to target function | |||
1660 | BinaryFunction *TargetBF = | |||
1661 | BC.getBinaryFunctionContainingAddress(EntryAddress); | |||
1662 | if (TargetBF->getAddress() != EntryAddress) { | |||
1663 | MCSymbol *Label = | |||
1664 | (HasOneParent && TargetBF == this) | |||
1665 | ? getOrCreateLocalLabel(JT.EntriesAsAddress[I], true) | |||
1666 | : TargetBF->addEntryPointAtOffset(EntryAddress - | |||
1667 | TargetBF->getAddress()); | |||
1668 | JT.Entries.push_back(Label); | |||
1669 | } | |||
1670 | } | |||
1671 | } | |||
1672 | ||||
1673 | const uint64_t BDSize = | |||
1674 | BC.getBinaryDataAtAddress(JT.getAddress())->getSize(); | |||
1675 | if (!BDSize) { | |||
1676 | BC.setBinaryDataSize(JT.getAddress(), JT.getSize()); | |||
1677 | } else { | |||
1678 | assert(BDSize >= JT.getSize() &&(static_cast <bool> (BDSize >= JT.getSize() && "jump table cannot be larger than the containing object") ? void (0) : __assert_fail ("BDSize >= JT.getSize() && \"jump table cannot be larger than the containing object\"" , "bolt/lib/Core/BinaryFunction.cpp", 1679, __extension__ __PRETTY_FUNCTION__ )) | |||
1679 | "jump table cannot be larger than the containing object")(static_cast <bool> (BDSize >= JT.getSize() && "jump table cannot be larger than the containing object") ? void (0) : __assert_fail ("BDSize >= JT.getSize() && \"jump table cannot be larger than the containing object\"" , "bolt/lib/Core/BinaryFunction.cpp", 1679, __extension__ __PRETTY_FUNCTION__ )); | |||
1680 | } | |||
1681 | } | |||
1682 | ||||
1683 | // Add TakenBranches from JumpTables. | |||
1684 | // | |||
1685 | // We want to do it after initial processing since we don't know jump tables' | |||
1686 | // boundaries until we process them all. | |||
1687 | for (auto &JTSite : JTSites) { | |||
1688 | const uint64_t JTSiteOffset = JTSite.first; | |||
1689 | const uint64_t JTAddress = JTSite.second; | |||
1690 | const JumpTable *JT = getJumpTableContainingAddress(JTAddress); | |||
1691 | assert(JT && "cannot find jump table for address")(static_cast <bool> (JT && "cannot find jump table for address" ) ? void (0) : __assert_fail ("JT && \"cannot find jump table for address\"" , "bolt/lib/Core/BinaryFunction.cpp", 1691, __extension__ __PRETTY_FUNCTION__ )); | |||
1692 | ||||
1693 | uint64_t EntryOffset = JTAddress - JT->getAddress(); | |||
1694 | while (EntryOffset < JT->getSize()) { | |||
1695 | uint64_t EntryAddress = JT->EntriesAsAddress[EntryOffset / JT->EntrySize]; | |||
1696 | uint64_t TargetOffset = EntryAddress - getAddress(); | |||
1697 | if (TargetOffset < getSize()) { | |||
1698 | TakenBranches.emplace_back(JTSiteOffset, TargetOffset); | |||
1699 | ||||
1700 | if (opts::StrictMode) | |||
1701 | registerReferencedOffset(TargetOffset); | |||
1702 | } | |||
1703 | ||||
1704 | EntryOffset += JT->EntrySize; | |||
1705 | ||||
1706 | // A label at the next entry means the end of this jump table. | |||
1707 | if (JT->Labels.count(EntryOffset)) | |||
1708 | break; | |||
1709 | } | |||
1710 | } | |||
1711 | clearList(JTSites); | |||
1712 | ||||
1713 | // Conservatively populate all possible destinations for unknown indirect | |||
1714 | // branches. | |||
1715 | if (opts::StrictMode && hasInternalReference()) { | |||
1716 | for (uint64_t Offset : UnknownIndirectBranchOffsets) { | |||
1717 | for (uint64_t PossibleDestination : ExternallyReferencedOffsets) { | |||
1718 | // Ignore __builtin_unreachable(). | |||
1719 | if (PossibleDestination == getSize()) | |||
1720 | continue; | |||
1721 | TakenBranches.emplace_back(Offset, PossibleDestination); | |||
1722 | } | |||
1723 | } | |||
1724 | } | |||
1725 | ||||
1726 | // Remove duplicates branches. We can get a bunch of them from jump tables. | |||
1727 | // Without doing jump table value profiling we don't have use for extra | |||
1728 | // (duplicate) branches. | |||
1729 | llvm::sort(TakenBranches); | |||
1730 | auto NewEnd = std::unique(TakenBranches.begin(), TakenBranches.end()); | |||
1731 | TakenBranches.erase(NewEnd, TakenBranches.end()); | |||
1732 | } | |||
1733 | ||||
1734 | bool BinaryFunction::validateExternallyReferencedOffsets() { | |||
1735 | SmallPtrSet<MCSymbol *, 4> JTTargets; | |||
1736 | for (const JumpTable *JT : llvm::make_second_range(JumpTables)) | |||
1737 | JTTargets.insert(JT->Entries.begin(), JT->Entries.end()); | |||
1738 | ||||
1739 | bool HasUnclaimedReference = false; | |||
1740 | for (uint64_t Destination : ExternallyReferencedOffsets) { | |||
1741 | // Ignore __builtin_unreachable(). | |||
1742 | if (Destination == getSize()) | |||
1743 | continue; | |||
1744 | // Ignore constant islands | |||
1745 | if (isInConstantIsland(Destination + getAddress())) | |||
1746 | continue; | |||
1747 | ||||
1748 | if (BinaryBasicBlock *BB = getBasicBlockAtOffset(Destination)) { | |||
1749 | // Check if the externally referenced offset is a recognized jump table | |||
1750 | // target. | |||
1751 | if (JTTargets.contains(BB->getLabel())) | |||
1752 | continue; | |||
1753 | ||||
1754 | if (opts::Verbosity >= 1) { | |||
1755 | errs() << "BOLT-WARNING: unclaimed data to code reference (possibly " | |||
1756 | << "an unrecognized jump table entry) to " << BB->getName() | |||
1757 | << " in " << *this << "\n"; | |||
1758 | } | |||
1759 | auto L = BC.scopeLock(); | |||
1760 | addEntryPoint(*BB); | |||
1761 | } else { | |||
1762 | errs() << "BOLT-WARNING: unknown data to code reference to offset " | |||
1763 | << Twine::utohexstr(Destination) << " in " << *this << "\n"; | |||
1764 | setIgnored(); | |||
1765 | } | |||
1766 | HasUnclaimedReference = true; | |||
1767 | } | |||
1768 | return !HasUnclaimedReference; | |||
1769 | } | |||
1770 | ||||
1771 | bool BinaryFunction::postProcessIndirectBranches( | |||
1772 | MCPlusBuilder::AllocatorIdTy AllocId) { | |||
1773 | auto addUnknownControlFlow = [&](BinaryBasicBlock &BB) { | |||
1774 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding unknown control flow in " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: adding unknown control flow in " << *this << " for " << BB.getName() << "\n"; } } while (false) | |||
1775 | << " for " << BB.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: adding unknown control flow in " << *this << " for " << BB.getName() << "\n"; } } while (false); | |||
1776 | HasUnknownControlFlow = true; | |||
1777 | BB.removeAllSuccessors(); | |||
1778 | for (uint64_t PossibleDestination : ExternallyReferencedOffsets) | |||
1779 | if (BinaryBasicBlock *SuccBB = getBasicBlockAtOffset(PossibleDestination)) | |||
1780 | BB.addSuccessor(SuccBB); | |||
1781 | }; | |||
1782 | ||||
1783 | uint64_t NumIndirectJumps = 0; | |||
1784 | MCInst *LastIndirectJump = nullptr; | |||
1785 | BinaryBasicBlock *LastIndirectJumpBB = nullptr; | |||
1786 | uint64_t LastJT = 0; | |||
1787 | uint16_t LastJTIndexReg = BC.MIB->getNoRegister(); | |||
1788 | for (BinaryBasicBlock &BB : blocks()) { | |||
1789 | for (MCInst &Instr : BB) { | |||
1790 | if (!BC.MIB->isIndirectBranch(Instr)) | |||
1791 | continue; | |||
1792 | ||||
1793 | // If there's an indirect branch in a single-block function - | |||
1794 | // it must be a tail call. | |||
1795 | if (BasicBlocks.size() == 1) { | |||
1796 | BC.MIB->convertJmpToTailCall(Instr); | |||
1797 | return true; | |||
1798 | } | |||
1799 | ||||
1800 | ++NumIndirectJumps; | |||
1801 | ||||
1802 | if (opts::StrictMode && !hasInternalReference()) { | |||
1803 | BC.MIB->convertJmpToTailCall(Instr); | |||
1804 | break; | |||
1805 | } | |||
1806 | ||||
1807 | // Validate the tail call or jump table assumptions now that we know | |||
1808 | // basic block boundaries. | |||
1809 | if (BC.MIB->isTailCall(Instr) || BC.MIB->getJumpTable(Instr)) { | |||
1810 | const unsigned PtrSize = BC.AsmInfo->getCodePointerSize(); | |||
1811 | MCInst *MemLocInstr; | |||
1812 | unsigned BaseRegNum, IndexRegNum; | |||
1813 | int64_t DispValue; | |||
1814 | const MCExpr *DispExpr; | |||
1815 | MCInst *PCRelBaseInstr; | |||
1816 | IndirectBranchType Type = BC.MIB->analyzeIndirectBranch( | |||
1817 | Instr, BB.begin(), BB.end(), PtrSize, MemLocInstr, BaseRegNum, | |||
1818 | IndexRegNum, DispValue, DispExpr, PCRelBaseInstr); | |||
1819 | if (Type != IndirectBranchType::UNKNOWN || MemLocInstr != nullptr) | |||
1820 | continue; | |||
1821 | ||||
1822 | if (!opts::StrictMode) | |||
1823 | return false; | |||
1824 | ||||
1825 | if (BC.MIB->isTailCall(Instr)) { | |||
1826 | BC.MIB->convertTailCallToJmp(Instr); | |||
1827 | } else { | |||
1828 | LastIndirectJump = &Instr; | |||
1829 | LastIndirectJumpBB = &BB; | |||
1830 | LastJT = BC.MIB->getJumpTable(Instr); | |||
1831 | LastJTIndexReg = BC.MIB->getJumpTableIndexReg(Instr); | |||
1832 | BC.MIB->unsetJumpTable(Instr); | |||
1833 | ||||
1834 | JumpTable *JT = BC.getJumpTableContainingAddress(LastJT); | |||
1835 | if (JT->Type == JumpTable::JTT_NORMAL) { | |||
1836 | // Invalidating the jump table may also invalidate other jump table | |||
1837 | // boundaries. Until we have/need a support for this, mark the | |||
1838 | // function as non-simple. | |||
1839 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: rejected jump table reference"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: rejected jump table reference" << JT->getName() << " in " << *this << '\n'; } } while (false) | |||
1840 | << JT->getName() << " in " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: rejected jump table reference" << JT->getName() << " in " << *this << '\n'; } } while (false); | |||
1841 | return false; | |||
1842 | } | |||
1843 | } | |||
1844 | ||||
1845 | addUnknownControlFlow(BB); | |||
1846 | continue; | |||
1847 | } | |||
1848 | ||||
1849 | // If this block contains an epilogue code and has an indirect branch, | |||
1850 | // then most likely it's a tail call. Otherwise, we cannot tell for sure | |||
1851 | // what it is and conservatively reject the function's CFG. | |||
1852 | bool IsEpilogue = llvm::any_of(BB, [&](const MCInst &Instr) { | |||
1853 | return BC.MIB->isLeave(Instr) || BC.MIB->isPop(Instr); | |||
1854 | }); | |||
1855 | if (IsEpilogue) { | |||
1856 | BC.MIB->convertJmpToTailCall(Instr); | |||
1857 | BB.removeAllSuccessors(); | |||
1858 | continue; | |||
1859 | } | |||
1860 | ||||
1861 | if (opts::Verbosity >= 2) { | |||
1862 | outs() << "BOLT-INFO: rejected potential indirect tail call in " | |||
1863 | << "function " << *this << " in basic block " << BB.getName() | |||
1864 | << ".\n"; | |||
1865 | LLVM_DEBUG(BC.printInstructions(dbgs(), BB.begin(), BB.end(),do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { BC.printInstructions(dbgs(), BB.begin(), BB.end() , BB.getOffset(), this, true); } } while (false) | |||
1866 | BB.getOffset(), this, true))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { BC.printInstructions(dbgs(), BB.begin(), BB.end() , BB.getOffset(), this, true); } } while (false); | |||
1867 | } | |||
1868 | ||||
1869 | if (!opts::StrictMode) | |||
1870 | return false; | |||
1871 | ||||
1872 | addUnknownControlFlow(BB); | |||
1873 | } | |||
1874 | } | |||
1875 | ||||
1876 | if (HasInternalLabelReference) | |||
1877 | return false; | |||
1878 | ||||
1879 | // If there's only one jump table, and one indirect jump, and no other | |||
1880 | // references, then we should be able to derive the jump table even if we | |||
1881 | // fail to match the pattern. | |||
1882 | if (HasUnknownControlFlow && NumIndirectJumps == 1 && | |||
1883 | JumpTables.size() == 1 && LastIndirectJump && | |||
1884 | !BC.getJumpTableContainingAddress(LastJT)->IsSplit) { | |||
1885 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: unsetting unknown control flow in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: unsetting unknown control flow in " << *this << '\n'; } } while (false) | |||
1886 | << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: unsetting unknown control flow in " << *this << '\n'; } } while (false); | |||
1887 | BC.MIB->setJumpTable(*LastIndirectJump, LastJT, LastJTIndexReg, AllocId); | |||
1888 | HasUnknownControlFlow = false; | |||
1889 | ||||
1890 | LastIndirectJumpBB->updateJumpTableSuccessors(); | |||
1891 | } | |||
1892 | ||||
1893 | if (HasFixedIndirectBranch) | |||
1894 | return false; | |||
1895 | ||||
1896 | // Validate that all data references to function offsets are claimed by | |||
1897 | // recognized jump tables. Register externally referenced blocks as entry | |||
1898 | // points. | |||
1899 | if (!opts::StrictMode && hasInternalReference()) { | |||
1900 | if (!validateExternallyReferencedOffsets()) | |||
1901 | return false; | |||
1902 | } | |||
1903 | ||||
1904 | if (HasUnknownControlFlow && !BC.HasRelocations) | |||
1905 | return false; | |||
1906 | ||||
1907 | return true; | |||
1908 | } | |||
1909 | ||||
1910 | void BinaryFunction::recomputeLandingPads() { | |||
1911 | updateBBIndices(0); | |||
1912 | ||||
1913 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
1914 | BB->LandingPads.clear(); | |||
1915 | BB->Throwers.clear(); | |||
1916 | } | |||
1917 | ||||
1918 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
1919 | std::unordered_set<const BinaryBasicBlock *> BBLandingPads; | |||
1920 | for (MCInst &Instr : *BB) { | |||
1921 | if (!BC.MIB->isInvoke(Instr)) | |||
1922 | continue; | |||
1923 | ||||
1924 | const std::optional<MCPlus::MCLandingPad> EHInfo = | |||
1925 | BC.MIB->getEHInfo(Instr); | |||
1926 | if (!EHInfo || !EHInfo->first) | |||
1927 | continue; | |||
1928 | ||||
1929 | BinaryBasicBlock *LPBlock = getBasicBlockForLabel(EHInfo->first); | |||
1930 | if (!BBLandingPads.count(LPBlock)) { | |||
1931 | BBLandingPads.insert(LPBlock); | |||
1932 | BB->LandingPads.emplace_back(LPBlock); | |||
1933 | LPBlock->Throwers.emplace_back(BB); | |||
1934 | } | |||
1935 | } | |||
1936 | } | |||
1937 | } | |||
1938 | ||||
1939 | bool BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) { | |||
1940 | auto &MIB = BC.MIB; | |||
1941 | ||||
1942 | if (!isSimple()) { | |||
1943 | assert(!BC.HasRelocations &&(static_cast <bool> (!BC.HasRelocations && "cannot process file with non-simple function in relocs mode" ) ? void (0) : __assert_fail ("!BC.HasRelocations && \"cannot process file with non-simple function in relocs mode\"" , "bolt/lib/Core/BinaryFunction.cpp", 1944, __extension__ __PRETTY_FUNCTION__ )) | |||
1944 | "cannot process file with non-simple function in relocs mode")(static_cast <bool> (!BC.HasRelocations && "cannot process file with non-simple function in relocs mode" ) ? void (0) : __assert_fail ("!BC.HasRelocations && \"cannot process file with non-simple function in relocs mode\"" , "bolt/lib/Core/BinaryFunction.cpp", 1944, __extension__ __PRETTY_FUNCTION__ )); | |||
1945 | return false; | |||
1946 | } | |||
1947 | ||||
1948 | if (CurrentState != State::Disassembled) | |||
1949 | return false; | |||
1950 | ||||
1951 | assert(BasicBlocks.empty() && "basic block list should be empty")(static_cast <bool> (BasicBlocks.empty() && "basic block list should be empty" ) ? void (0) : __assert_fail ("BasicBlocks.empty() && \"basic block list should be empty\"" , "bolt/lib/Core/BinaryFunction.cpp", 1951, __extension__ __PRETTY_FUNCTION__ )); | |||
1952 | assert((Labels.find(getFirstInstructionOffset()) != Labels.end()) &&(static_cast <bool> ((Labels.find(getFirstInstructionOffset ()) != Labels.end()) && "first instruction should always have a label" ) ? void (0) : __assert_fail ("(Labels.find(getFirstInstructionOffset()) != Labels.end()) && \"first instruction should always have a label\"" , "bolt/lib/Core/BinaryFunction.cpp", 1953, __extension__ __PRETTY_FUNCTION__ )) | |||
1953 | "first instruction should always have a label")(static_cast <bool> ((Labels.find(getFirstInstructionOffset ()) != Labels.end()) && "first instruction should always have a label" ) ? void (0) : __assert_fail ("(Labels.find(getFirstInstructionOffset()) != Labels.end()) && \"first instruction should always have a label\"" , "bolt/lib/Core/BinaryFunction.cpp", 1953, __extension__ __PRETTY_FUNCTION__ )); | |||
1954 | ||||
1955 | // Create basic blocks in the original layout order: | |||
1956 | // | |||
1957 | // * Every instruction with associated label marks | |||
1958 | // the beginning of a basic block. | |||
1959 | // * Conditional instruction marks the end of a basic block, | |||
1960 | // except when the following instruction is an | |||
1961 | // unconditional branch, and the unconditional branch is not | |||
1962 | // a destination of another branch. In the latter case, the | |||
1963 | // basic block will consist of a single unconditional branch | |||
1964 | // (missed "double-jump" optimization). | |||
1965 | // | |||
1966 | // Created basic blocks are sorted in layout order since they are | |||
1967 | // created in the same order as instructions, and instructions are | |||
1968 | // sorted by offsets. | |||
1969 | BinaryBasicBlock *InsertBB = nullptr; | |||
1970 | BinaryBasicBlock *PrevBB = nullptr; | |||
1971 | bool IsLastInstrNop = false; | |||
1972 | // Offset of the last non-nop instruction. | |||
1973 | uint64_t LastInstrOffset = 0; | |||
1974 | ||||
1975 | auto addCFIPlaceholders = [this](uint64_t CFIOffset, | |||
1976 | BinaryBasicBlock *InsertBB) { | |||
1977 | for (auto FI = OffsetToCFI.lower_bound(CFIOffset), | |||
1978 | FE = OffsetToCFI.upper_bound(CFIOffset); | |||
1979 | FI != FE; ++FI) { | |||
1980 | addCFIPseudo(InsertBB, InsertBB->end(), FI->second); | |||
1981 | } | |||
1982 | }; | |||
1983 | ||||
1984 | // For profiling purposes we need to save the offset of the last instruction | |||
1985 | // in the basic block. | |||
1986 | // NOTE: nops always have an Offset annotation. Annotate the last non-nop as | |||
1987 | // older profiles ignored nops. | |||
1988 | auto updateOffset = [&](uint64_t Offset) { | |||
1989 | assert(PrevBB && PrevBB != InsertBB && "invalid previous block")(static_cast <bool> (PrevBB && PrevBB != InsertBB && "invalid previous block") ? void (0) : __assert_fail ("PrevBB && PrevBB != InsertBB && \"invalid previous block\"" , "bolt/lib/Core/BinaryFunction.cpp", 1989, __extension__ __PRETTY_FUNCTION__ )); | |||
1990 | MCInst *LastNonNop = nullptr; | |||
1991 | for (BinaryBasicBlock::reverse_iterator RII = PrevBB->getLastNonPseudo(), | |||
1992 | E = PrevBB->rend(); | |||
1993 | RII != E; ++RII) { | |||
1994 | if (!BC.MIB->isPseudo(*RII) && !BC.MIB->isNoop(*RII)) { | |||
1995 | LastNonNop = &*RII; | |||
1996 | break; | |||
1997 | } | |||
1998 | } | |||
1999 | if (LastNonNop && !MIB->getOffset(*LastNonNop)) | |||
2000 | MIB->setOffset(*LastNonNop, static_cast<uint32_t>(Offset), AllocatorId); | |||
2001 | }; | |||
2002 | ||||
2003 | for (auto I = Instructions.begin(), E = Instructions.end(); I != E; ++I) { | |||
2004 | const uint32_t Offset = I->first; | |||
2005 | MCInst &Instr = I->second; | |||
2006 | ||||
2007 | auto LI = Labels.find(Offset); | |||
2008 | if (LI != Labels.end()) { | |||
2009 | // Always create new BB at branch destination. | |||
2010 | PrevBB = InsertBB ? InsertBB : PrevBB; | |||
2011 | InsertBB = addBasicBlockAt(LI->first, LI->second); | |||
2012 | if (opts::PreserveBlocksAlignment && IsLastInstrNop) | |||
2013 | InsertBB->setDerivedAlignment(); | |||
2014 | ||||
2015 | if (PrevBB) | |||
2016 | updateOffset(LastInstrOffset); | |||
2017 | } | |||
2018 | ||||
2019 | const uint64_t InstrInputAddr = I->first + Address; | |||
2020 | bool IsSDTMarker = | |||
2021 | MIB->isNoop(Instr) && BC.SDTMarkers.count(InstrInputAddr); | |||
2022 | bool IsLKMarker = BC.LKMarkers.count(InstrInputAddr); | |||
2023 | // Mark all nops with Offset for profile tracking purposes. | |||
2024 | if (MIB->isNoop(Instr) || IsLKMarker) { | |||
2025 | if (!MIB->getOffset(Instr)) | |||
2026 | MIB->setOffset(Instr, static_cast<uint32_t>(Offset), AllocatorId); | |||
2027 | if (IsSDTMarker || IsLKMarker) | |||
2028 | HasSDTMarker = true; | |||
2029 | else | |||
2030 | // Annotate ordinary nops, so we can safely delete them if required. | |||
2031 | MIB->addAnnotation(Instr, "NOP", static_cast<uint32_t>(1), AllocatorId); | |||
2032 | } | |||
2033 | ||||
2034 | if (!InsertBB) { | |||
2035 | // It must be a fallthrough or unreachable code. Create a new block unless | |||
2036 | // we see an unconditional branch following a conditional one. The latter | |||
2037 | // should not be a conditional tail call. | |||
2038 | assert(PrevBB && "no previous basic block for a fall through")(static_cast <bool> (PrevBB && "no previous basic block for a fall through" ) ? void (0) : __assert_fail ("PrevBB && \"no previous basic block for a fall through\"" , "bolt/lib/Core/BinaryFunction.cpp", 2038, __extension__ __PRETTY_FUNCTION__ )); | |||
2039 | MCInst *PrevInstr = PrevBB->getLastNonPseudoInstr(); | |||
2040 | assert(PrevInstr && "no previous instruction for a fall through")(static_cast <bool> (PrevInstr && "no previous instruction for a fall through" ) ? void (0) : __assert_fail ("PrevInstr && \"no previous instruction for a fall through\"" , "bolt/lib/Core/BinaryFunction.cpp", 2040, __extension__ __PRETTY_FUNCTION__ )); | |||
2041 | if (MIB->isUnconditionalBranch(Instr) && | |||
2042 | !MIB->isIndirectBranch(*PrevInstr) && | |||
2043 | !MIB->isUnconditionalBranch(*PrevInstr) && | |||
2044 | !MIB->getConditionalTailCall(*PrevInstr) && | |||
2045 | !MIB->isReturn(*PrevInstr)) { | |||
2046 | // Temporarily restore inserter basic block. | |||
2047 | InsertBB = PrevBB; | |||
2048 | } else { | |||
2049 | MCSymbol *Label; | |||
2050 | { | |||
2051 | auto L = BC.scopeLock(); | |||
2052 | Label = BC.Ctx->createNamedTempSymbol("FT"); | |||
2053 | } | |||
2054 | InsertBB = addBasicBlockAt(Offset, Label); | |||
2055 | if (opts::PreserveBlocksAlignment && IsLastInstrNop) | |||
2056 | InsertBB->setDerivedAlignment(); | |||
2057 | updateOffset(LastInstrOffset); | |||
2058 | } | |||
2059 | } | |||
2060 | if (Offset == getFirstInstructionOffset()) { | |||
2061 | // Add associated CFI pseudos in the first offset | |||
2062 | addCFIPlaceholders(Offset, InsertBB); | |||
2063 | } | |||
2064 | ||||
2065 | const bool IsBlockEnd = MIB->isTerminator(Instr); | |||
2066 | IsLastInstrNop = MIB->isNoop(Instr); | |||
2067 | if (!IsLastInstrNop) | |||
2068 | LastInstrOffset = Offset; | |||
2069 | InsertBB->addInstruction(std::move(Instr)); | |||
2070 | ||||
2071 | // Add associated CFI instrs. We always add the CFI instruction that is | |||
2072 | // located immediately after this instruction, since the next CFI | |||
2073 | // instruction reflects the change in state caused by this instruction. | |||
2074 | auto NextInstr = std::next(I); | |||
2075 | uint64_t CFIOffset; | |||
2076 | if (NextInstr != E) | |||
2077 | CFIOffset = NextInstr->first; | |||
2078 | else | |||
2079 | CFIOffset = getSize(); | |||
2080 | ||||
2081 | // Note: this potentially invalidates instruction pointers/iterators. | |||
2082 | addCFIPlaceholders(CFIOffset, InsertBB); | |||
2083 | ||||
2084 | if (IsBlockEnd) { | |||
2085 | PrevBB = InsertBB; | |||
2086 | InsertBB = nullptr; | |||
2087 | } | |||
2088 | } | |||
2089 | ||||
2090 | if (BasicBlocks.empty()) { | |||
2091 | setSimple(false); | |||
2092 | return false; | |||
2093 | } | |||
2094 | ||||
2095 | // Intermediate dump. | |||
2096 | LLVM_DEBUG(print(dbgs(), "after creating basic blocks"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { print(dbgs(), "after creating basic blocks"); } } while (false); | |||
2097 | ||||
2098 | // TODO: handle properly calls to no-return functions, | |||
2099 | // e.g. exit(3), etc. Otherwise we'll see a false fall-through | |||
2100 | // blocks. | |||
2101 | ||||
2102 | for (std::pair<uint32_t, uint32_t> &Branch : TakenBranches) { | |||
2103 | LLVM_DEBUG(dbgs() << "registering branch [0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "registering branch [0x" << Twine::utohexstr(Branch.first) << "] -> [0x" << Twine::utohexstr(Branch.second) << "]\n"; } } while (false ) | |||
2104 | << Twine::utohexstr(Branch.first) << "] -> [0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "registering branch [0x" << Twine::utohexstr(Branch.first) << "] -> [0x" << Twine::utohexstr(Branch.second) << "]\n"; } } while (false ) | |||
2105 | << Twine::utohexstr(Branch.second) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "registering branch [0x" << Twine::utohexstr(Branch.first) << "] -> [0x" << Twine::utohexstr(Branch.second) << "]\n"; } } while (false ); | |||
2106 | BinaryBasicBlock *FromBB = getBasicBlockContainingOffset(Branch.first); | |||
2107 | BinaryBasicBlock *ToBB = getBasicBlockAtOffset(Branch.second); | |||
2108 | if (!FromBB || !ToBB) { | |||
2109 | if (!FromBB) | |||
2110 | errs() << "BOLT-ERROR: cannot find BB containing the branch.\n"; | |||
2111 | if (!ToBB) | |||
2112 | errs() << "BOLT-ERROR: cannot find BB containing branch destination.\n"; | |||
2113 | BC.exitWithBugReport("disassembly failed - inconsistent branch found.", | |||
2114 | *this); | |||
2115 | } | |||
2116 | ||||
2117 | FromBB->addSuccessor(ToBB); | |||
2118 | } | |||
2119 | ||||
2120 | // Add fall-through branches. | |||
2121 | PrevBB = nullptr; | |||
2122 | bool IsPrevFT = false; // Is previous block a fall-through. | |||
2123 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
2124 | if (IsPrevFT) | |||
2125 | PrevBB->addSuccessor(BB); | |||
2126 | ||||
2127 | if (BB->empty()) { | |||
2128 | IsPrevFT = true; | |||
2129 | PrevBB = BB; | |||
2130 | continue; | |||
2131 | } | |||
2132 | ||||
2133 | MCInst *LastInstr = BB->getLastNonPseudoInstr(); | |||
2134 | assert(LastInstr &&(static_cast <bool> (LastInstr && "should have non-pseudo instruction in non-empty block" ) ? void (0) : __assert_fail ("LastInstr && \"should have non-pseudo instruction in non-empty block\"" , "bolt/lib/Core/BinaryFunction.cpp", 2135, __extension__ __PRETTY_FUNCTION__ )) | |||
2135 | "should have non-pseudo instruction in non-empty block")(static_cast <bool> (LastInstr && "should have non-pseudo instruction in non-empty block" ) ? void (0) : __assert_fail ("LastInstr && \"should have non-pseudo instruction in non-empty block\"" , "bolt/lib/Core/BinaryFunction.cpp", 2135, __extension__ __PRETTY_FUNCTION__ )); | |||
2136 | ||||
2137 | if (BB->succ_size() == 0) { | |||
2138 | // Since there's no existing successors, we know the last instruction is | |||
2139 | // not a conditional branch. Thus if it's a terminator, it shouldn't be a | |||
2140 | // fall-through. | |||
2141 | // | |||
2142 | // Conditional tail call is a special case since we don't add a taken | |||
2143 | // branch successor for it. | |||
2144 | IsPrevFT = !MIB->isTerminator(*LastInstr) || | |||
2145 | MIB->getConditionalTailCall(*LastInstr); | |||
2146 | } else if (BB->succ_size() == 1) { | |||
2147 | IsPrevFT = MIB->isConditionalBranch(*LastInstr); | |||
2148 | } else { | |||
2149 | IsPrevFT = false; | |||
2150 | } | |||
2151 | ||||
2152 | PrevBB = BB; | |||
2153 | } | |||
2154 | ||||
2155 | // Assign landing pads and throwers info. | |||
2156 | recomputeLandingPads(); | |||
2157 | ||||
2158 | // Assign CFI information to each BB entry. | |||
2159 | annotateCFIState(); | |||
2160 | ||||
2161 | // Annotate invoke instructions with GNU_args_size data. | |||
2162 | propagateGnuArgsSizeInfo(AllocatorId); | |||
2163 | ||||
2164 | // Set the basic block layout to the original order and set end offsets. | |||
2165 | PrevBB = nullptr; | |||
2166 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
2167 | Layout.addBasicBlock(BB); | |||
2168 | if (PrevBB) | |||
2169 | PrevBB->setEndOffset(BB->getOffset()); | |||
2170 | PrevBB = BB; | |||
2171 | } | |||
2172 | PrevBB->setEndOffset(getSize()); | |||
2173 | ||||
2174 | Layout.updateLayoutIndices(); | |||
2175 | ||||
2176 | normalizeCFIState(); | |||
2177 | ||||
2178 | // Clean-up memory taken by intermediate structures. | |||
2179 | // | |||
2180 | // NB: don't clear Labels list as we may need them if we mark the function | |||
2181 | // as non-simple later in the process of discovering extra entry points. | |||
2182 | clearList(Instructions); | |||
2183 | clearList(OffsetToCFI); | |||
2184 | clearList(TakenBranches); | |||
2185 | ||||
2186 | // Update the state. | |||
2187 | CurrentState = State::CFG; | |||
2188 | ||||
2189 | // Make any necessary adjustments for indirect branches. | |||
2190 | if (!postProcessIndirectBranches(AllocatorId)) { | |||
2191 | if (opts::Verbosity) { | |||
2192 | errs() << "BOLT-WARNING: failed to post-process indirect branches for " | |||
2193 | << *this << '\n'; | |||
2194 | } | |||
2195 | // In relocation mode we want to keep processing the function but avoid | |||
2196 | // optimizing it. | |||
2197 | setSimple(false); | |||
2198 | } | |||
2199 | ||||
2200 | clearList(ExternallyReferencedOffsets); | |||
2201 | clearList(UnknownIndirectBranchOffsets); | |||
2202 | ||||
2203 | return true; | |||
2204 | } | |||
2205 | ||||
2206 | void BinaryFunction::postProcessCFG() { | |||
2207 | if (isSimple() && !BasicBlocks.empty()) { | |||
2208 | // Convert conditional tail call branches to conditional branches that jump | |||
2209 | // to a tail call. | |||
2210 | removeConditionalTailCalls(); | |||
2211 | ||||
2212 | postProcessProfile(); | |||
2213 | ||||
2214 | // Eliminate inconsistencies between branch instructions and CFG. | |||
2215 | postProcessBranches(); | |||
2216 | } | |||
2217 | ||||
2218 | calculateMacroOpFusionStats(); | |||
2219 | ||||
2220 | // The final cleanup of intermediate structures. | |||
2221 | clearList(IgnoredBranches); | |||
2222 | ||||
2223 | // Remove "Offset" annotations, unless we need an address-translation table | |||
2224 | // later. This has no cost, since annotations are allocated by a bumpptr | |||
2225 | // allocator and won't be released anyway until late in the pipeline. | |||
2226 | if (!requiresAddressTranslation() && !opts::Instrument) { | |||
2227 | for (BinaryBasicBlock &BB : blocks()) | |||
2228 | for (MCInst &Inst : BB) | |||
2229 | BC.MIB->clearOffset(Inst); | |||
2230 | } | |||
2231 | ||||
2232 | assert((!isSimple() || validateCFG()) &&(static_cast <bool> ((!isSimple() || validateCFG()) && "invalid CFG detected after post-processing") ? void (0) : __assert_fail ("(!isSimple() || validateCFG()) && \"invalid CFG detected after post-processing\"" , "bolt/lib/Core/BinaryFunction.cpp", 2233, __extension__ __PRETTY_FUNCTION__ )) | |||
2233 | "invalid CFG detected after post-processing")(static_cast <bool> ((!isSimple() || validateCFG()) && "invalid CFG detected after post-processing") ? void (0) : __assert_fail ("(!isSimple() || validateCFG()) && \"invalid CFG detected after post-processing\"" , "bolt/lib/Core/BinaryFunction.cpp", 2233, __extension__ __PRETTY_FUNCTION__ )); | |||
2234 | } | |||
2235 | ||||
2236 | void BinaryFunction::calculateMacroOpFusionStats() { | |||
2237 | if (!getBinaryContext().isX86()) | |||
2238 | return; | |||
2239 | for (const BinaryBasicBlock &BB : blocks()) { | |||
2240 | auto II = BB.getMacroOpFusionPair(); | |||
2241 | if (II == BB.end()) | |||
2242 | continue; | |||
2243 | ||||
2244 | // Check offset of the second instruction. | |||
2245 | // FIXME: arch-specific. | |||
2246 | const uint32_t Offset = BC.MIB->getOffsetWithDefault(*std::next(II), 0); | |||
2247 | if (!Offset || (getAddress() + Offset) % 64) | |||
2248 | continue; | |||
2249 | ||||
2250 | LLVM_DEBUG(dbgs() << "\nmissed macro-op fusion at address 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x" << Twine::utohexstr(getAddress() + Offset) << " in function " << *this << "; executed " << BB.getKnownExecutionCount () << " times.\n"; } } while (false) | |||
2251 | << Twine::utohexstr(getAddress() + Offset)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x" << Twine::utohexstr(getAddress() + Offset) << " in function " << *this << "; executed " << BB.getKnownExecutionCount () << " times.\n"; } } while (false) | |||
2252 | << " in function " << *this << "; executed "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x" << Twine::utohexstr(getAddress() + Offset) << " in function " << *this << "; executed " << BB.getKnownExecutionCount () << " times.\n"; } } while (false) | |||
2253 | << BB.getKnownExecutionCount() << " times.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x" << Twine::utohexstr(getAddress() + Offset) << " in function " << *this << "; executed " << BB.getKnownExecutionCount () << " times.\n"; } } while (false); | |||
2254 | ++BC.MissedMacroFusionPairs; | |||
2255 | BC.MissedMacroFusionExecCount += BB.getKnownExecutionCount(); | |||
2256 | } | |||
2257 | } | |||
2258 | ||||
2259 | void BinaryFunction::removeTagsFromProfile() { | |||
2260 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
2261 | if (BB->ExecutionCount == BinaryBasicBlock::COUNT_NO_PROFILE) | |||
2262 | BB->ExecutionCount = 0; | |||
2263 | for (BinaryBasicBlock::BinaryBranchInfo &BI : BB->branch_info()) { | |||
2264 | if (BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE && | |||
2265 | BI.MispredictedCount != BinaryBasicBlock::COUNT_NO_PROFILE) | |||
2266 | continue; | |||
2267 | BI.Count = 0; | |||
2268 | BI.MispredictedCount = 0; | |||
2269 | } | |||
2270 | } | |||
2271 | } | |||
2272 | ||||
2273 | void BinaryFunction::removeConditionalTailCalls() { | |||
2274 | // Blocks to be appended at the end. | |||
2275 | std::vector<std::unique_ptr<BinaryBasicBlock>> NewBlocks; | |||
2276 | ||||
2277 | for (auto BBI = begin(); BBI != end(); ++BBI) { | |||
2278 | BinaryBasicBlock &BB = *BBI; | |||
2279 | MCInst *CTCInstr = BB.getLastNonPseudoInstr(); | |||
2280 | if (!CTCInstr) | |||
2281 | continue; | |||
2282 | ||||
2283 | std::optional<uint64_t> TargetAddressOrNone = | |||
2284 | BC.MIB->getConditionalTailCall(*CTCInstr); | |||
2285 | if (!TargetAddressOrNone) | |||
2286 | continue; | |||
2287 | ||||
2288 | // Gather all necessary information about CTC instruction before | |||
2289 | // annotations are destroyed. | |||
2290 | const int32_t CFIStateBeforeCTC = BB.getCFIStateAtInstr(CTCInstr); | |||
2291 | uint64_t CTCTakenCount = BinaryBasicBlock::COUNT_NO_PROFILE; | |||
2292 | uint64_t CTCMispredCount = BinaryBasicBlock::COUNT_NO_PROFILE; | |||
2293 | if (hasValidProfile()) { | |||
2294 | CTCTakenCount = BC.MIB->getAnnotationWithDefault<uint64_t>( | |||
2295 | *CTCInstr, "CTCTakenCount"); | |||
2296 | CTCMispredCount = BC.MIB->getAnnotationWithDefault<uint64_t>( | |||
2297 | *CTCInstr, "CTCMispredCount"); | |||
2298 | } | |||
2299 | ||||
2300 | // Assert that the tail call does not throw. | |||
2301 | assert(!BC.MIB->getEHInfo(*CTCInstr) &&(static_cast <bool> (!BC.MIB->getEHInfo(*CTCInstr) && "found tail call with associated landing pad") ? void (0) : __assert_fail ("!BC.MIB->getEHInfo(*CTCInstr) && \"found tail call with associated landing pad\"" , "bolt/lib/Core/BinaryFunction.cpp", 2302, __extension__ __PRETTY_FUNCTION__ )) | |||
2302 | "found tail call with associated landing pad")(static_cast <bool> (!BC.MIB->getEHInfo(*CTCInstr) && "found tail call with associated landing pad") ? void (0) : __assert_fail ("!BC.MIB->getEHInfo(*CTCInstr) && \"found tail call with associated landing pad\"" , "bolt/lib/Core/BinaryFunction.cpp", 2302, __extension__ __PRETTY_FUNCTION__ )); | |||
2303 | ||||
2304 | // Create a basic block with an unconditional tail call instruction using | |||
2305 | // the same destination. | |||
2306 | const MCSymbol *CTCTargetLabel = BC.MIB->getTargetSymbol(*CTCInstr); | |||
2307 | assert(CTCTargetLabel && "symbol expected for conditional tail call")(static_cast <bool> (CTCTargetLabel && "symbol expected for conditional tail call" ) ? void (0) : __assert_fail ("CTCTargetLabel && \"symbol expected for conditional tail call\"" , "bolt/lib/Core/BinaryFunction.cpp", 2307, __extension__ __PRETTY_FUNCTION__ )); | |||
2308 | MCInst TailCallInstr; | |||
2309 | BC.MIB->createTailCall(TailCallInstr, CTCTargetLabel, BC.Ctx.get()); | |||
2310 | // Link new BBs to the original input offset of the BB where the CTC | |||
2311 | // is, so we can map samples recorded in new BBs back to the original BB | |||
2312 | // seem in the input binary (if using BAT) | |||
2313 | std::unique_ptr<BinaryBasicBlock> TailCallBB = | |||
2314 | createBasicBlock(BC.Ctx->createNamedTempSymbol("TC")); | |||
2315 | TailCallBB->setOffset(BB.getInputOffset()); | |||
2316 | TailCallBB->addInstruction(TailCallInstr); | |||
2317 | TailCallBB->setCFIState(CFIStateBeforeCTC); | |||
2318 | ||||
2319 | // Add CFG edge with profile info from BB to TailCallBB. | |||
2320 | BB.addSuccessor(TailCallBB.get(), CTCTakenCount, CTCMispredCount); | |||
2321 | ||||
2322 | // Add execution count for the block. | |||
2323 | TailCallBB->setExecutionCount(CTCTakenCount); | |||
2324 | ||||
2325 | BC.MIB->convertTailCallToJmp(*CTCInstr); | |||
2326 | ||||
2327 | BC.MIB->replaceBranchTarget(*CTCInstr, TailCallBB->getLabel(), | |||
2328 | BC.Ctx.get()); | |||
2329 | ||||
2330 | // Add basic block to the list that will be added to the end. | |||
2331 | NewBlocks.emplace_back(std::move(TailCallBB)); | |||
2332 | ||||
2333 | // Swap edges as the TailCallBB corresponds to the taken branch. | |||
2334 | BB.swapConditionalSuccessors(); | |||
2335 | ||||
2336 | // This branch is no longer a conditional tail call. | |||
2337 | BC.MIB->unsetConditionalTailCall(*CTCInstr); | |||
2338 | } | |||
2339 | ||||
2340 | insertBasicBlocks(std::prev(end()), std::move(NewBlocks), | |||
2341 | /* UpdateLayout */ true, | |||
2342 | /* UpdateCFIState */ false); | |||
2343 | } | |||
2344 | ||||
2345 | uint64_t BinaryFunction::getFunctionScore() const { | |||
2346 | if (FunctionScore != -1) | |||
2347 | return FunctionScore; | |||
2348 | ||||
2349 | if (!isSimple() || !hasValidProfile()) { | |||
2350 | FunctionScore = 0; | |||
2351 | return FunctionScore; | |||
2352 | } | |||
2353 | ||||
2354 | uint64_t TotalScore = 0ULL; | |||
2355 | for (const BinaryBasicBlock &BB : blocks()) { | |||
2356 | uint64_t BBExecCount = BB.getExecutionCount(); | |||
2357 | if (BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE) | |||
2358 | continue; | |||
2359 | TotalScore += BBExecCount * BB.getNumNonPseudos(); | |||
2360 | } | |||
2361 | FunctionScore = TotalScore; | |||
2362 | return FunctionScore; | |||
2363 | } | |||
2364 | ||||
2365 | void BinaryFunction::annotateCFIState() { | |||
2366 | assert(CurrentState == State::Disassembled && "unexpected function state")(static_cast <bool> (CurrentState == State::Disassembled && "unexpected function state") ? void (0) : __assert_fail ("CurrentState == State::Disassembled && \"unexpected function state\"" , "bolt/lib/Core/BinaryFunction.cpp", 2366, __extension__ __PRETTY_FUNCTION__ )); | |||
2367 | assert(!BasicBlocks.empty() && "basic block list should not be empty")(static_cast <bool> (!BasicBlocks.empty() && "basic block list should not be empty" ) ? void (0) : __assert_fail ("!BasicBlocks.empty() && \"basic block list should not be empty\"" , "bolt/lib/Core/BinaryFunction.cpp", 2367, __extension__ __PRETTY_FUNCTION__ )); | |||
2368 | ||||
2369 | // This is an index of the last processed CFI in FDE CFI program. | |||
2370 | uint32_t State = 0; | |||
2371 | ||||
2372 | // This is an index of RememberState CFI reflecting effective state right | |||
2373 | // after execution of RestoreState CFI. | |||
2374 | // | |||
2375 | // It differs from State iff the CFI at (State-1) | |||
2376 | // was RestoreState (modulo GNU_args_size CFIs, which are ignored). | |||
2377 | // | |||
2378 | // This allows us to generate shorter replay sequences when producing new | |||
2379 | // CFI programs. | |||
2380 | uint32_t EffectiveState = 0; | |||
2381 | ||||
2382 | // For tracking RememberState/RestoreState sequences. | |||
2383 | std::stack<uint32_t> StateStack; | |||
2384 | ||||
2385 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
2386 | BB->setCFIState(EffectiveState); | |||
2387 | ||||
2388 | for (const MCInst &Instr : *BB) { | |||
2389 | const MCCFIInstruction *CFI = getCFIFor(Instr); | |||
2390 | if (!CFI) | |||
2391 | continue; | |||
2392 | ||||
2393 | ++State; | |||
2394 | ||||
2395 | switch (CFI->getOperation()) { | |||
2396 | case MCCFIInstruction::OpRememberState: | |||
2397 | StateStack.push(EffectiveState); | |||
2398 | EffectiveState = State; | |||
2399 | break; | |||
2400 | case MCCFIInstruction::OpRestoreState: | |||
2401 | assert(!StateStack.empty() && "corrupt CFI stack")(static_cast <bool> (!StateStack.empty() && "corrupt CFI stack" ) ? void (0) : __assert_fail ("!StateStack.empty() && \"corrupt CFI stack\"" , "bolt/lib/Core/BinaryFunction.cpp", 2401, __extension__ __PRETTY_FUNCTION__ )); | |||
2402 | EffectiveState = StateStack.top(); | |||
2403 | StateStack.pop(); | |||
2404 | break; | |||
2405 | case MCCFIInstruction::OpGnuArgsSize: | |||
2406 | // OpGnuArgsSize CFIs do not affect the CFI state. | |||
2407 | break; | |||
2408 | default: | |||
2409 | // Any other CFI updates the state. | |||
2410 | EffectiveState = State; | |||
2411 | break; | |||
2412 | } | |||
2413 | } | |||
2414 | } | |||
2415 | ||||
2416 | assert(StateStack.empty() && "corrupt CFI stack")(static_cast <bool> (StateStack.empty() && "corrupt CFI stack" ) ? void (0) : __assert_fail ("StateStack.empty() && \"corrupt CFI stack\"" , "bolt/lib/Core/BinaryFunction.cpp", 2416, __extension__ __PRETTY_FUNCTION__ )); | |||
2417 | } | |||
2418 | ||||
2419 | namespace { | |||
2420 | ||||
2421 | /// Our full interpretation of a DWARF CFI machine state at a given point | |||
2422 | struct CFISnapshot { | |||
2423 | /// CFA register number and offset defining the canonical frame at this | |||
2424 | /// point, or the number of a rule (CFI state) that computes it with a | |||
2425 | /// DWARF expression. This number will be negative if it refers to a CFI | |||
2426 | /// located in the CIE instead of the FDE. | |||
2427 | uint32_t CFAReg; | |||
2428 | int32_t CFAOffset; | |||
2429 | int32_t CFARule; | |||
2430 | /// Mapping of rules (CFI states) that define the location of each | |||
2431 | /// register. If absent, no rule defining the location of such register | |||
2432 | /// was ever read. This number will be negative if it refers to a CFI | |||
2433 | /// located in the CIE instead of the FDE. | |||
2434 | DenseMap<int32_t, int32_t> RegRule; | |||
2435 | ||||
2436 | /// References to CIE, FDE and expanded instructions after a restore state | |||
2437 | const BinaryFunction::CFIInstrMapType &CIE; | |||
2438 | const BinaryFunction::CFIInstrMapType &FDE; | |||
2439 | const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents; | |||
2440 | ||||
2441 | /// Current FDE CFI number representing the state where the snapshot is at | |||
2442 | int32_t CurState; | |||
2443 | ||||
2444 | /// Used when we don't have information about which state/rule to apply | |||
2445 | /// to recover the location of either the CFA or a specific register | |||
2446 | constexpr static int32_t UNKNOWN = std::numeric_limits<int32_t>::min(); | |||
2447 | ||||
2448 | private: | |||
2449 | /// Update our snapshot by executing a single CFI | |||
2450 | void update(const MCCFIInstruction &Instr, int32_t RuleNumber) { | |||
2451 | switch (Instr.getOperation()) { | |||
2452 | case MCCFIInstruction::OpSameValue: | |||
2453 | case MCCFIInstruction::OpRelOffset: | |||
2454 | case MCCFIInstruction::OpOffset: | |||
2455 | case MCCFIInstruction::OpRestore: | |||
2456 | case MCCFIInstruction::OpUndefined: | |||
2457 | case MCCFIInstruction::OpRegister: | |||
2458 | RegRule[Instr.getRegister()] = RuleNumber; | |||
2459 | break; | |||
2460 | case MCCFIInstruction::OpDefCfaRegister: | |||
2461 | CFAReg = Instr.getRegister(); | |||
2462 | CFARule = UNKNOWN; | |||
2463 | break; | |||
2464 | case MCCFIInstruction::OpDefCfaOffset: | |||
2465 | CFAOffset = Instr.getOffset(); | |||
2466 | CFARule = UNKNOWN; | |||
2467 | break; | |||
2468 | case MCCFIInstruction::OpDefCfa: | |||
2469 | CFAReg = Instr.getRegister(); | |||
2470 | CFAOffset = Instr.getOffset(); | |||
2471 | CFARule = UNKNOWN; | |||
2472 | break; | |||
2473 | case MCCFIInstruction::OpEscape: { | |||
2474 | std::optional<uint8_t> Reg = | |||
2475 | readDWARFExpressionTargetReg(Instr.getValues()); | |||
2476 | // Handle DW_CFA_def_cfa_expression | |||
2477 | if (!Reg) { | |||
2478 | CFARule = RuleNumber; | |||
2479 | break; | |||
2480 | } | |||
2481 | RegRule[*Reg] = RuleNumber; | |||
2482 | break; | |||
2483 | } | |||
2484 | case MCCFIInstruction::OpAdjustCfaOffset: | |||
2485 | case MCCFIInstruction::OpWindowSave: | |||
2486 | case MCCFIInstruction::OpNegateRAState: | |||
2487 | case MCCFIInstruction::OpLLVMDefAspaceCfa: | |||
2488 | llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp" , 2488); | |||
2489 | break; | |||
2490 | case MCCFIInstruction::OpRememberState: | |||
2491 | case MCCFIInstruction::OpRestoreState: | |||
2492 | case MCCFIInstruction::OpGnuArgsSize: | |||
2493 | // do not affect CFI state | |||
2494 | break; | |||
2495 | } | |||
2496 | } | |||
2497 | ||||
2498 | public: | |||
2499 | /// Advance state reading FDE CFI instructions up to State number | |||
2500 | void advanceTo(int32_t State) { | |||
2501 | for (int32_t I = CurState, E = State; I != E; ++I) { | |||
2502 | const MCCFIInstruction &Instr = FDE[I]; | |||
2503 | if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) { | |||
2504 | update(Instr, I); | |||
2505 | continue; | |||
2506 | } | |||
2507 | // If restore state instruction, fetch the equivalent CFIs that have | |||
2508 | // the same effect of this restore. This is used to ensure remember- | |||
2509 | // restore pairs are completely removed. | |||
2510 | auto Iter = FrameRestoreEquivalents.find(I); | |||
2511 | if (Iter == FrameRestoreEquivalents.end()) | |||
2512 | continue; | |||
2513 | for (int32_t RuleNumber : Iter->second) | |||
2514 | update(FDE[RuleNumber], RuleNumber); | |||
2515 | } | |||
2516 | ||||
2517 | assert(((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) ||(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?" ) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\"" , "bolt/lib/Core/BinaryFunction.cpp", 2519, __extension__ __PRETTY_FUNCTION__ )) | |||
2518 | CFARule != UNKNOWN) &&(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?" ) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\"" , "bolt/lib/Core/BinaryFunction.cpp", 2519, __extension__ __PRETTY_FUNCTION__ )) | |||
2519 | "CIE did not define default CFA?")(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?" ) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\"" , "bolt/lib/Core/BinaryFunction.cpp", 2519, __extension__ __PRETTY_FUNCTION__ )); | |||
2520 | ||||
2521 | CurState = State; | |||
2522 | } | |||
2523 | ||||
2524 | /// Interpret all CIE and FDE instructions up until CFI State number and | |||
2525 | /// populate this snapshot | |||
2526 | CFISnapshot( | |||
2527 | const BinaryFunction::CFIInstrMapType &CIE, | |||
2528 | const BinaryFunction::CFIInstrMapType &FDE, | |||
2529 | const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents, | |||
2530 | int32_t State) | |||
2531 | : CIE(CIE), FDE(FDE), FrameRestoreEquivalents(FrameRestoreEquivalents) { | |||
2532 | CFAReg = UNKNOWN; | |||
2533 | CFAOffset = UNKNOWN; | |||
2534 | CFARule = UNKNOWN; | |||
2535 | CurState = 0; | |||
2536 | ||||
2537 | for (int32_t I = 0, E = CIE.size(); I != E; ++I) { | |||
2538 | const MCCFIInstruction &Instr = CIE[I]; | |||
2539 | update(Instr, -I); | |||
2540 | } | |||
2541 | ||||
2542 | advanceTo(State); | |||
2543 | } | |||
2544 | }; | |||
2545 | ||||
2546 | /// A CFI snapshot with the capability of checking if incremental additions to | |||
2547 | /// it are redundant. This is used to ensure we do not emit two CFI instructions | |||
2548 | /// back-to-back that are doing the same state change, or to avoid emitting a | |||
2549 | /// CFI at all when the state at that point would not be modified after that CFI | |||
2550 | struct CFISnapshotDiff : public CFISnapshot { | |||
2551 | bool RestoredCFAReg{false}; | |||
2552 | bool RestoredCFAOffset{false}; | |||
2553 | DenseMap<int32_t, bool> RestoredRegs; | |||
2554 | ||||
2555 | CFISnapshotDiff(const CFISnapshot &S) : CFISnapshot(S) {} | |||
2556 | ||||
2557 | CFISnapshotDiff( | |||
2558 | const BinaryFunction::CFIInstrMapType &CIE, | |||
2559 | const BinaryFunction::CFIInstrMapType &FDE, | |||
2560 | const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents, | |||
2561 | int32_t State) | |||
2562 | : CFISnapshot(CIE, FDE, FrameRestoreEquivalents, State) {} | |||
2563 | ||||
2564 | /// Return true if applying Instr to this state is redundant and can be | |||
2565 | /// dismissed. | |||
2566 | bool isRedundant(const MCCFIInstruction &Instr) { | |||
2567 | switch (Instr.getOperation()) { | |||
2568 | case MCCFIInstruction::OpSameValue: | |||
2569 | case MCCFIInstruction::OpRelOffset: | |||
2570 | case MCCFIInstruction::OpOffset: | |||
2571 | case MCCFIInstruction::OpRestore: | |||
2572 | case MCCFIInstruction::OpUndefined: | |||
2573 | case MCCFIInstruction::OpRegister: | |||
2574 | case MCCFIInstruction::OpEscape: { | |||
2575 | uint32_t Reg; | |||
2576 | if (Instr.getOperation() != MCCFIInstruction::OpEscape) { | |||
2577 | Reg = Instr.getRegister(); | |||
2578 | } else { | |||
2579 | std::optional<uint8_t> R = | |||
2580 | readDWARFExpressionTargetReg(Instr.getValues()); | |||
2581 | // Handle DW_CFA_def_cfa_expression | |||
2582 | if (!R) { | |||
2583 | if (RestoredCFAReg && RestoredCFAOffset) | |||
2584 | return true; | |||
2585 | RestoredCFAReg = true; | |||
2586 | RestoredCFAOffset = true; | |||
2587 | return false; | |||
2588 | } | |||
2589 | Reg = *R; | |||
2590 | } | |||
2591 | if (RestoredRegs[Reg]) | |||
2592 | return true; | |||
2593 | RestoredRegs[Reg] = true; | |||
2594 | const int32_t CurRegRule = RegRule.contains(Reg) ? RegRule[Reg] : UNKNOWN; | |||
2595 | if (CurRegRule == UNKNOWN) { | |||
2596 | if (Instr.getOperation() == MCCFIInstruction::OpRestore || | |||
2597 | Instr.getOperation() == MCCFIInstruction::OpSameValue) | |||
2598 | return true; | |||
2599 | return false; | |||
2600 | } | |||
2601 | const MCCFIInstruction &LastDef = | |||
2602 | CurRegRule < 0 ? CIE[-CurRegRule] : FDE[CurRegRule]; | |||
2603 | return LastDef == Instr; | |||
2604 | } | |||
2605 | case MCCFIInstruction::OpDefCfaRegister: | |||
2606 | if (RestoredCFAReg) | |||
2607 | return true; | |||
2608 | RestoredCFAReg = true; | |||
2609 | return CFAReg == Instr.getRegister(); | |||
2610 | case MCCFIInstruction::OpDefCfaOffset: | |||
2611 | if (RestoredCFAOffset) | |||
2612 | return true; | |||
2613 | RestoredCFAOffset = true; | |||
2614 | return CFAOffset == Instr.getOffset(); | |||
2615 | case MCCFIInstruction::OpDefCfa: | |||
2616 | if (RestoredCFAReg && RestoredCFAOffset) | |||
2617 | return true; | |||
2618 | RestoredCFAReg = true; | |||
2619 | RestoredCFAOffset = true; | |||
2620 | return CFAReg == Instr.getRegister() && CFAOffset == Instr.getOffset(); | |||
2621 | case MCCFIInstruction::OpAdjustCfaOffset: | |||
2622 | case MCCFIInstruction::OpWindowSave: | |||
2623 | case MCCFIInstruction::OpNegateRAState: | |||
2624 | case MCCFIInstruction::OpLLVMDefAspaceCfa: | |||
2625 | llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp" , 2625); | |||
2626 | return false; | |||
2627 | case MCCFIInstruction::OpRememberState: | |||
2628 | case MCCFIInstruction::OpRestoreState: | |||
2629 | case MCCFIInstruction::OpGnuArgsSize: | |||
2630 | // do not affect CFI state | |||
2631 | return true; | |||
2632 | } | |||
2633 | return false; | |||
2634 | } | |||
2635 | }; | |||
2636 | ||||
2637 | } // end anonymous namespace | |||
2638 | ||||
2639 | bool BinaryFunction::replayCFIInstrs(int32_t FromState, int32_t ToState, | |||
2640 | BinaryBasicBlock *InBB, | |||
2641 | BinaryBasicBlock::iterator InsertIt) { | |||
2642 | if (FromState == ToState) | |||
2643 | return true; | |||
2644 | assert(FromState < ToState && "can only replay CFIs forward")(static_cast <bool> (FromState < ToState && "can only replay CFIs forward" ) ? void (0) : __assert_fail ("FromState < ToState && \"can only replay CFIs forward\"" , "bolt/lib/Core/BinaryFunction.cpp", 2644, __extension__ __PRETTY_FUNCTION__ )); | |||
2645 | ||||
2646 | CFISnapshotDiff CFIDiff(CIEFrameInstructions, FrameInstructions, | |||
2647 | FrameRestoreEquivalents, FromState); | |||
2648 | ||||
2649 | std::vector<uint32_t> NewCFIs; | |||
2650 | for (int32_t CurState = FromState; CurState < ToState; ++CurState) { | |||
2651 | MCCFIInstruction *Instr = &FrameInstructions[CurState]; | |||
2652 | if (Instr->getOperation() == MCCFIInstruction::OpRestoreState) { | |||
2653 | auto Iter = FrameRestoreEquivalents.find(CurState); | |||
2654 | assert(Iter != FrameRestoreEquivalents.end())(static_cast <bool> (Iter != FrameRestoreEquivalents.end ()) ? void (0) : __assert_fail ("Iter != FrameRestoreEquivalents.end()" , "bolt/lib/Core/BinaryFunction.cpp", 2654, __extension__ __PRETTY_FUNCTION__ )); | |||
2655 | NewCFIs.insert(NewCFIs.end(), Iter->second.begin(), Iter->second.end()); | |||
2656 | // RestoreState / Remember will be filtered out later by CFISnapshotDiff, | |||
2657 | // so we might as well fall-through here. | |||
2658 | } | |||
2659 | NewCFIs.push_back(CurState); | |||
2660 | } | |||
2661 | ||||
2662 | // Replay instructions while avoiding duplicates | |||
2663 | for (int32_t State : llvm::reverse(NewCFIs)) { | |||
2664 | if (CFIDiff.isRedundant(FrameInstructions[State])) | |||
2665 | continue; | |||
2666 | InsertIt = addCFIPseudo(InBB, InsertIt, State); | |||
2667 | } | |||
2668 | ||||
2669 | return true; | |||
2670 | } | |||
2671 | ||||
2672 | SmallVector<int32_t, 4> | |||
2673 | BinaryFunction::unwindCFIState(int32_t FromState, int32_t ToState, | |||
2674 | BinaryBasicBlock *InBB, | |||
2675 | BinaryBasicBlock::iterator &InsertIt) { | |||
2676 | SmallVector<int32_t, 4> NewStates; | |||
2677 | ||||
2678 | CFISnapshot ToCFITable(CIEFrameInstructions, FrameInstructions, | |||
2679 | FrameRestoreEquivalents, ToState); | |||
2680 | CFISnapshotDiff FromCFITable(ToCFITable); | |||
2681 | FromCFITable.advanceTo(FromState); | |||
2682 | ||||
2683 | auto undoStateDefCfa = [&]() { | |||
2684 | if (ToCFITable.CFARule == CFISnapshot::UNKNOWN) { | |||
2685 | FrameInstructions.emplace_back(MCCFIInstruction::cfiDefCfa( | |||
2686 | nullptr, ToCFITable.CFAReg, ToCFITable.CFAOffset)); | |||
2687 | if (FromCFITable.isRedundant(FrameInstructions.back())) { | |||
2688 | FrameInstructions.pop_back(); | |||
2689 | return; | |||
2690 | } | |||
2691 | NewStates.push_back(FrameInstructions.size() - 1); | |||
2692 | InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1); | |||
2693 | ++InsertIt; | |||
2694 | } else if (ToCFITable.CFARule < 0) { | |||
2695 | if (FromCFITable.isRedundant(CIEFrameInstructions[-ToCFITable.CFARule])) | |||
2696 | return; | |||
2697 | NewStates.push_back(FrameInstructions.size()); | |||
2698 | InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size()); | |||
2699 | ++InsertIt; | |||
2700 | FrameInstructions.emplace_back(CIEFrameInstructions[-ToCFITable.CFARule]); | |||
2701 | } else if (!FromCFITable.isRedundant( | |||
2702 | FrameInstructions[ToCFITable.CFARule])) { | |||
2703 | NewStates.push_back(ToCFITable.CFARule); | |||
2704 | InsertIt = addCFIPseudo(InBB, InsertIt, ToCFITable.CFARule); | |||
2705 | ++InsertIt; | |||
2706 | } | |||
2707 | }; | |||
2708 | ||||
2709 | auto undoState = [&](const MCCFIInstruction &Instr) { | |||
2710 | switch (Instr.getOperation()) { | |||
2711 | case MCCFIInstruction::OpRememberState: | |||
2712 | case MCCFIInstruction::OpRestoreState: | |||
2713 | break; | |||
2714 | case MCCFIInstruction::OpSameValue: | |||
2715 | case MCCFIInstruction::OpRelOffset: | |||
2716 | case MCCFIInstruction::OpOffset: | |||
2717 | case MCCFIInstruction::OpRestore: | |||
2718 | case MCCFIInstruction::OpUndefined: | |||
2719 | case MCCFIInstruction::OpEscape: | |||
2720 | case MCCFIInstruction::OpRegister: { | |||
2721 | uint32_t Reg; | |||
2722 | if (Instr.getOperation() != MCCFIInstruction::OpEscape) { | |||
2723 | Reg = Instr.getRegister(); | |||
2724 | } else { | |||
2725 | std::optional<uint8_t> R = | |||
2726 | readDWARFExpressionTargetReg(Instr.getValues()); | |||
2727 | // Handle DW_CFA_def_cfa_expression | |||
2728 | if (!R) { | |||
2729 | undoStateDefCfa(); | |||
2730 | return; | |||
2731 | } | |||
2732 | Reg = *R; | |||
2733 | } | |||
2734 | ||||
2735 | if (!ToCFITable.RegRule.contains(Reg)) { | |||
2736 | FrameInstructions.emplace_back( | |||
2737 | MCCFIInstruction::createRestore(nullptr, Reg)); | |||
2738 | if (FromCFITable.isRedundant(FrameInstructions.back())) { | |||
2739 | FrameInstructions.pop_back(); | |||
2740 | break; | |||
2741 | } | |||
2742 | NewStates.push_back(FrameInstructions.size() - 1); | |||
2743 | InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1); | |||
2744 | ++InsertIt; | |||
2745 | break; | |||
2746 | } | |||
2747 | const int32_t Rule = ToCFITable.RegRule[Reg]; | |||
2748 | if (Rule < 0) { | |||
2749 | if (FromCFITable.isRedundant(CIEFrameInstructions[-Rule])) | |||
2750 | break; | |||
2751 | NewStates.push_back(FrameInstructions.size()); | |||
2752 | InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size()); | |||
2753 | ++InsertIt; | |||
2754 | FrameInstructions.emplace_back(CIEFrameInstructions[-Rule]); | |||
2755 | break; | |||
2756 | } | |||
2757 | if (FromCFITable.isRedundant(FrameInstructions[Rule])) | |||
2758 | break; | |||
2759 | NewStates.push_back(Rule); | |||
2760 | InsertIt = addCFIPseudo(InBB, InsertIt, Rule); | |||
2761 | ++InsertIt; | |||
2762 | break; | |||
2763 | } | |||
2764 | case MCCFIInstruction::OpDefCfaRegister: | |||
2765 | case MCCFIInstruction::OpDefCfaOffset: | |||
2766 | case MCCFIInstruction::OpDefCfa: | |||
2767 | undoStateDefCfa(); | |||
2768 | break; | |||
2769 | case MCCFIInstruction::OpAdjustCfaOffset: | |||
2770 | case MCCFIInstruction::OpWindowSave: | |||
2771 | case MCCFIInstruction::OpNegateRAState: | |||
2772 | case MCCFIInstruction::OpLLVMDefAspaceCfa: | |||
2773 | llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp" , 2773); | |||
2774 | break; | |||
2775 | case MCCFIInstruction::OpGnuArgsSize: | |||
2776 | // do not affect CFI state | |||
2777 | break; | |||
2778 | } | |||
2779 | }; | |||
2780 | ||||
2781 | // Undo all modifications from ToState to FromState | |||
2782 | for (int32_t I = ToState, E = FromState; I != E; ++I) { | |||
2783 | const MCCFIInstruction &Instr = FrameInstructions[I]; | |||
2784 | if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) { | |||
2785 | undoState(Instr); | |||
2786 | continue; | |||
2787 | } | |||
2788 | auto Iter = FrameRestoreEquivalents.find(I); | |||
2789 | if (Iter == FrameRestoreEquivalents.end()) | |||
2790 | continue; | |||
2791 | for (int32_t State : Iter->second) | |||
2792 | undoState(FrameInstructions[State]); | |||
2793 | } | |||
2794 | ||||
2795 | return NewStates; | |||
2796 | } | |||
2797 | ||||
2798 | void BinaryFunction::normalizeCFIState() { | |||
2799 | // Reordering blocks with remember-restore state instructions can be specially | |||
2800 | // tricky. When rewriting the CFI, we omit remember-restore state instructions | |||
2801 | // entirely. For restore state, we build a map expanding each restore to the | |||
2802 | // equivalent unwindCFIState sequence required at that point to achieve the | |||
2803 | // same effect of the restore. All remember state are then just ignored. | |||
2804 | std::stack<int32_t> Stack; | |||
2805 | for (BinaryBasicBlock *CurBB : Layout.blocks()) { | |||
2806 | for (auto II = CurBB->begin(); II != CurBB->end(); ++II) { | |||
2807 | if (const MCCFIInstruction *CFI = getCFIFor(*II)) { | |||
2808 | if (CFI->getOperation() == MCCFIInstruction::OpRememberState) { | |||
2809 | Stack.push(II->getOperand(0).getImm()); | |||
2810 | continue; | |||
2811 | } | |||
2812 | if (CFI->getOperation() == MCCFIInstruction::OpRestoreState) { | |||
2813 | const int32_t RememberState = Stack.top(); | |||
2814 | const int32_t CurState = II->getOperand(0).getImm(); | |||
2815 | FrameRestoreEquivalents[CurState] = | |||
2816 | unwindCFIState(CurState, RememberState, CurBB, II); | |||
2817 | Stack.pop(); | |||
2818 | } | |||
2819 | } | |||
2820 | } | |||
2821 | } | |||
2822 | } | |||
2823 | ||||
2824 | bool BinaryFunction::finalizeCFIState() { | |||
2825 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "Trying to fix CFI states for each BB after reordering.\n" ; } } while (false) | |||
2826 | dbgs() << "Trying to fix CFI states for each BB after reordering.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "Trying to fix CFI states for each BB after reordering.\n" ; } } while (false); | |||
2827 | LLVM_DEBUG(dbgs() << "This is the list of CFI states for each BB of " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "This is the list of CFI states for each BB of " << *this << ": "; } } while (false) | |||
2828 | << ": ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "This is the list of CFI states for each BB of " << *this << ": "; } } while (false); | |||
2829 | ||||
2830 | const char *Sep = ""; | |||
2831 | (void)Sep; | |||
2832 | for (FunctionFragment &FF : Layout.fragments()) { | |||
2833 | // Hot-cold border: at start of each region (with a different FDE) we need | |||
2834 | // to reset the CFI state. | |||
2835 | int32_t State = 0; | |||
2836 | ||||
2837 | for (BinaryBasicBlock *BB : FF) { | |||
2838 | const int32_t CFIStateAtExit = BB->getCFIStateAtExit(); | |||
2839 | ||||
2840 | // We need to recover the correct state if it doesn't match expected | |||
2841 | // state at BB entry point. | |||
2842 | if (BB->getCFIState() < State) { | |||
2843 | // In this case, State is currently higher than what this BB expect it | |||
2844 | // to be. To solve this, we need to insert CFI instructions to undo | |||
2845 | // the effect of all CFI from BB's state to current State. | |||
2846 | auto InsertIt = BB->begin(); | |||
2847 | unwindCFIState(State, BB->getCFIState(), BB, InsertIt); | |||
2848 | } else if (BB->getCFIState() > State) { | |||
2849 | // If BB's CFI state is greater than State, it means we are behind in | |||
2850 | // the state. Just emit all instructions to reach this state at the | |||
2851 | // beginning of this BB. If this sequence of instructions involve | |||
2852 | // remember state or restore state, bail out. | |||
2853 | if (!replayCFIInstrs(State, BB->getCFIState(), BB, BB->begin())) | |||
2854 | return false; | |||
2855 | } | |||
2856 | ||||
2857 | State = CFIStateAtExit; | |||
2858 | LLVM_DEBUG(dbgs() << Sep << State; Sep = ", ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << Sep << State; Sep = ", "; } } while (false); | |||
2859 | } | |||
2860 | } | |||
2861 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "\n"; } } while (false); | |||
2862 | ||||
2863 | for (BinaryBasicBlock &BB : blocks()) { | |||
2864 | for (auto II = BB.begin(); II != BB.end();) { | |||
2865 | const MCCFIInstruction *CFI = getCFIFor(*II); | |||
2866 | if (CFI && (CFI->getOperation() == MCCFIInstruction::OpRememberState || | |||
2867 | CFI->getOperation() == MCCFIInstruction::OpRestoreState)) { | |||
2868 | II = BB.eraseInstruction(II); | |||
2869 | } else { | |||
2870 | ++II; | |||
2871 | } | |||
2872 | } | |||
2873 | } | |||
2874 | ||||
2875 | return true; | |||
2876 | } | |||
2877 | ||||
2878 | bool BinaryFunction::requiresAddressTranslation() const { | |||
2879 | return opts::EnableBAT || hasSDTMarker() || hasPseudoProbe(); | |||
2880 | } | |||
2881 | ||||
2882 | uint64_t BinaryFunction::getInstructionCount() const { | |||
2883 | uint64_t Count = 0; | |||
2884 | for (const BinaryBasicBlock &BB : blocks()) | |||
2885 | Count += BB.getNumNonPseudos(); | |||
2886 | return Count; | |||
2887 | } | |||
2888 | ||||
2889 | void BinaryFunction::clearDisasmState() { | |||
2890 | clearList(Instructions); | |||
2891 | clearList(IgnoredBranches); | |||
2892 | clearList(TakenBranches); | |||
2893 | ||||
2894 | if (BC.HasRelocations) { | |||
2895 | for (std::pair<const uint32_t, MCSymbol *> &LI : Labels) | |||
2896 | BC.UndefinedSymbols.insert(LI.second); | |||
2897 | for (MCSymbol *const EndLabel : FunctionEndLabels) | |||
2898 | if (EndLabel) | |||
2899 | BC.UndefinedSymbols.insert(EndLabel); | |||
2900 | } | |||
2901 | } | |||
2902 | ||||
2903 | void BinaryFunction::setTrapOnEntry() { | |||
2904 | clearDisasmState(); | |||
2905 | ||||
2906 | forEachEntryPoint([&](uint64_t Offset, const MCSymbol *Label) -> bool { | |||
2907 | MCInst TrapInstr; | |||
2908 | BC.MIB->createTrap(TrapInstr); | |||
2909 | addInstruction(Offset, std::move(TrapInstr)); | |||
2910 | return true; | |||
2911 | }); | |||
2912 | ||||
2913 | TrapsOnEntry = true; | |||
2914 | } | |||
2915 | ||||
2916 | void BinaryFunction::setIgnored() { | |||
2917 | if (opts::processAllFunctions()) { | |||
2918 | // We can accept ignored functions before they've been disassembled. | |||
2919 | // In that case, they would still get disassembled and emited, but not | |||
2920 | // optimized. | |||
2921 | assert(CurrentState == State::Empty &&(static_cast <bool> (CurrentState == State::Empty && "cannot ignore non-empty functions in current mode") ? void ( 0) : __assert_fail ("CurrentState == State::Empty && \"cannot ignore non-empty functions in current mode\"" , "bolt/lib/Core/BinaryFunction.cpp", 2922, __extension__ __PRETTY_FUNCTION__ )) | |||
2922 | "cannot ignore non-empty functions in current mode")(static_cast <bool> (CurrentState == State::Empty && "cannot ignore non-empty functions in current mode") ? void ( 0) : __assert_fail ("CurrentState == State::Empty && \"cannot ignore non-empty functions in current mode\"" , "bolt/lib/Core/BinaryFunction.cpp", 2922, __extension__ __PRETTY_FUNCTION__ )); | |||
2923 | IsIgnored = true; | |||
2924 | return; | |||
2925 | } | |||
2926 | ||||
2927 | clearDisasmState(); | |||
2928 | ||||
2929 | // Clear CFG state too. | |||
2930 | if (hasCFG()) { | |||
2931 | releaseCFG(); | |||
2932 | ||||
2933 | for (BinaryBasicBlock *BB : BasicBlocks) | |||
2934 | delete BB; | |||
2935 | clearList(BasicBlocks); | |||
2936 | ||||
2937 | for (BinaryBasicBlock *BB : DeletedBasicBlocks) | |||
2938 | delete BB; | |||
2939 | clearList(DeletedBasicBlocks); | |||
2940 | ||||
2941 | Layout.clear(); | |||
2942 | } | |||
2943 | ||||
2944 | CurrentState = State::Empty; | |||
2945 | ||||
2946 | IsIgnored = true; | |||
2947 | IsSimple = false; | |||
2948 | LLVM_DEBUG(dbgs() << "Ignoring " << getPrintName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "Ignoring " << getPrintName () << '\n'; } } while (false); | |||
2949 | } | |||
2950 | ||||
2951 | void BinaryFunction::duplicateConstantIslands() { | |||
2952 | assert(Islands && "function expected to have constant islands")(static_cast <bool> (Islands && "function expected to have constant islands" ) ? void (0) : __assert_fail ("Islands && \"function expected to have constant islands\"" , "bolt/lib/Core/BinaryFunction.cpp", 2952, __extension__ __PRETTY_FUNCTION__ )); | |||
2953 | ||||
2954 | for (BinaryBasicBlock *BB : getLayout().blocks()) { | |||
2955 | if (!BB->isCold()) | |||
2956 | continue; | |||
2957 | ||||
2958 | for (MCInst &Inst : *BB) { | |||
2959 | int OpNum = 0; | |||
2960 | for (MCOperand &Operand : Inst) { | |||
2961 | if (!Operand.isExpr()) { | |||
2962 | ++OpNum; | |||
2963 | continue; | |||
2964 | } | |||
2965 | const MCSymbol *Symbol = BC.MIB->getTargetSymbol(Inst, OpNum); | |||
2966 | // Check if this is an island symbol | |||
2967 | if (!Islands->Symbols.count(Symbol) && | |||
2968 | !Islands->ProxySymbols.count(Symbol)) | |||
2969 | continue; | |||
2970 | ||||
2971 | // Create cold symbol, if missing | |||
2972 | auto ISym = Islands->ColdSymbols.find(Symbol); | |||
2973 | MCSymbol *ColdSymbol; | |||
2974 | if (ISym != Islands->ColdSymbols.end()) { | |||
2975 | ColdSymbol = ISym->second; | |||
2976 | } else { | |||
2977 | ColdSymbol = BC.Ctx->getOrCreateSymbol(Symbol->getName() + ".cold"); | |||
2978 | Islands->ColdSymbols[Symbol] = ColdSymbol; | |||
2979 | // Check if this is a proxy island symbol and update owner proxy map | |||
2980 | if (Islands->ProxySymbols.count(Symbol)) { | |||
2981 | BinaryFunction *Owner = Islands->ProxySymbols[Symbol]; | |||
2982 | auto IProxiedSym = Owner->Islands->Proxies[this].find(Symbol); | |||
2983 | Owner->Islands->ColdProxies[this][IProxiedSym->second] = ColdSymbol; | |||
2984 | } | |||
2985 | } | |||
2986 | ||||
2987 | // Update instruction reference | |||
2988 | Operand = MCOperand::createExpr(BC.MIB->getTargetExprFor( | |||
2989 | Inst, | |||
2990 | MCSymbolRefExpr::create(ColdSymbol, MCSymbolRefExpr::VK_None, | |||
2991 | *BC.Ctx), | |||
2992 | *BC.Ctx, 0)); | |||
2993 | ++OpNum; | |||
2994 | } | |||
2995 | } | |||
2996 | } | |||
2997 | } | |||
2998 | ||||
2999 | #ifndef MAX_PATH255 | |||
3000 | #define MAX_PATH255 255 | |||
3001 | #endif | |||
3002 | ||||
3003 | static std::string constructFilename(std::string Filename, | |||
3004 | std::string Annotation, | |||
3005 | std::string Suffix) { | |||
3006 | std::replace(Filename.begin(), Filename.end(), '/', '-'); | |||
3007 | if (!Annotation.empty()) | |||
3008 | Annotation.insert(0, "-"); | |||
3009 | if (Filename.size() + Annotation.size() + Suffix.size() > MAX_PATH255) { | |||
3010 | assert(Suffix.size() + Annotation.size() <= MAX_PATH)(static_cast <bool> (Suffix.size() + Annotation.size() <= 255) ? void (0) : __assert_fail ("Suffix.size() + Annotation.size() <= MAX_PATH" , "bolt/lib/Core/BinaryFunction.cpp", 3010, __extension__ __PRETTY_FUNCTION__ )); | |||
3011 | if (opts::Verbosity >= 1) { | |||
3012 | errs() << "BOLT-WARNING: Filename \"" << Filename << Annotation << Suffix | |||
3013 | << "\" exceeds the " << MAX_PATH255 << " size limit, truncating.\n"; | |||
3014 | } | |||
3015 | Filename.resize(MAX_PATH255 - (Suffix.size() + Annotation.size())); | |||
3016 | } | |||
3017 | Filename += Annotation; | |||
3018 | Filename += Suffix; | |||
3019 | return Filename; | |||
3020 | } | |||
3021 | ||||
3022 | static std::string formatEscapes(const std::string &Str) { | |||
3023 | std::string Result; | |||
3024 | for (unsigned I = 0; I < Str.size(); ++I) { | |||
3025 | char C = Str[I]; | |||
3026 | switch (C) { | |||
3027 | case '\n': | |||
3028 | Result += " "; | |||
3029 | break; | |||
3030 | case '"': | |||
3031 | break; | |||
3032 | default: | |||
3033 | Result += C; | |||
3034 | break; | |||
3035 | } | |||
3036 | } | |||
3037 | return Result; | |||
3038 | } | |||
3039 | ||||
3040 | void BinaryFunction::dumpGraph(raw_ostream &OS) const { | |||
3041 | OS << "digraph \"" << getPrintName() << "\" {\n" | |||
3042 | << "node [fontname=courier, shape=box, style=filled, colorscheme=brbg9]\n"; | |||
3043 | uint64_t Offset = Address; | |||
3044 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
3045 | auto LayoutPos = find(Layout.blocks(), BB); | |||
3046 | unsigned LayoutIndex = LayoutPos - Layout.block_begin(); | |||
3047 | const char *ColdStr = BB->isCold() ? " (cold)" : ""; | |||
3048 | std::vector<std::string> Attrs; | |||
3049 | // Bold box for entry points | |||
3050 | if (isEntryPoint(*BB)) | |||
3051 | Attrs.push_back("penwidth=2"); | |||
3052 | if (BLI && BLI->getLoopFor(BB)) { | |||
3053 | // Distinguish innermost loops | |||
3054 | const BinaryLoop *Loop = BLI->getLoopFor(BB); | |||
3055 | if (Loop->isInnermost()) | |||
3056 | Attrs.push_back("fillcolor=6"); | |||
3057 | else // some outer loop | |||
3058 | Attrs.push_back("fillcolor=4"); | |||
3059 | } else { // non-loopy code | |||
3060 | Attrs.push_back("fillcolor=5"); | |||
3061 | } | |||
3062 | ListSeparator LS; | |||
3063 | OS << "\"" << BB->getName() << "\" ["; | |||
3064 | for (StringRef Attr : Attrs) | |||
3065 | OS << LS << Attr; | |||
3066 | OS << "]\n"; | |||
3067 | OS << format("\"%s\" [label=\"%s%s\\n(C:%lu,O:%lu,I:%u,L:%u,CFI:%u)\\n", | |||
3068 | BB->getName().data(), BB->getName().data(), ColdStr, | |||
3069 | BB->getKnownExecutionCount(), BB->getOffset(), getIndex(BB), | |||
3070 | LayoutIndex, BB->getCFIState()); | |||
3071 | ||||
3072 | if (opts::DotToolTipCode) { | |||
3073 | std::string Str; | |||
3074 | raw_string_ostream CS(Str); | |||
3075 | Offset = BC.printInstructions(CS, BB->begin(), BB->end(), Offset, this, | |||
3076 | /* PrintMCInst = */ false, | |||
3077 | /* PrintMemData = */ false, | |||
3078 | /* PrintRelocations = */ false, | |||
3079 | /* Endl = */ R"(\\l)"); | |||
3080 | OS << formatEscapes(CS.str()) << '\n'; | |||
3081 | } | |||
3082 | OS << "\"]\n"; | |||
3083 | ||||
3084 | // analyzeBranch is just used to get the names of the branch | |||
3085 | // opcodes. | |||
3086 | const MCSymbol *TBB = nullptr; | |||
3087 | const MCSymbol *FBB = nullptr; | |||
3088 | MCInst *CondBranch = nullptr; | |||
3089 | MCInst *UncondBranch = nullptr; | |||
3090 | const bool Success = BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch); | |||
3091 | ||||
3092 | const MCInst *LastInstr = BB->getLastNonPseudoInstr(); | |||
3093 | const bool IsJumpTable = LastInstr && BC.MIB->getJumpTable(*LastInstr); | |||
3094 | ||||
3095 | auto BI = BB->branch_info_begin(); | |||
3096 | for (BinaryBasicBlock *Succ : BB->successors()) { | |||
3097 | std::string Branch; | |||
3098 | if (Success) { | |||
3099 | if (Succ == BB->getConditionalSuccessor(true)) { | |||
3100 | Branch = CondBranch ? std::string(BC.InstPrinter->getOpcodeName( | |||
3101 | CondBranch->getOpcode())) | |||
3102 | : "TB"; | |||
3103 | } else if (Succ == BB->getConditionalSuccessor(false)) { | |||
3104 | Branch = UncondBranch ? std::string(BC.InstPrinter->getOpcodeName( | |||
3105 | UncondBranch->getOpcode())) | |||
3106 | : "FB"; | |||
3107 | } else { | |||
3108 | Branch = "FT"; | |||
3109 | } | |||
3110 | } | |||
3111 | if (IsJumpTable) | |||
3112 | Branch = "JT"; | |||
3113 | OS << format("\"%s\" -> \"%s\" [label=\"%s", BB->getName().data(), | |||
3114 | Succ->getName().data(), Branch.c_str()); | |||
3115 | ||||
3116 | if (BB->getExecutionCount() != COUNT_NO_PROFILE && | |||
3117 | BI->MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) { | |||
3118 | OS << "\\n(C:" << BI->Count << ",M:" << BI->MispredictedCount << ")"; | |||
3119 | } else if (ExecutionCount != COUNT_NO_PROFILE && | |||
3120 | BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE) { | |||
3121 | OS << "\\n(IC:" << BI->Count << ")"; | |||
3122 | } | |||
3123 | OS << "\"]\n"; | |||
3124 | ||||
3125 | ++BI; | |||
3126 | } | |||
3127 | for (BinaryBasicBlock *LP : BB->landing_pads()) { | |||
3128 | OS << format("\"%s\" -> \"%s\" [constraint=false style=dashed]\n", | |||
3129 | BB->getName().data(), LP->getName().data()); | |||
3130 | } | |||
3131 | } | |||
3132 | OS << "}\n"; | |||
3133 | } | |||
3134 | ||||
3135 | void BinaryFunction::viewGraph() const { | |||
3136 | SmallString<MAX_PATH255> Filename; | |||
3137 | if (std::error_code EC = | |||
3138 | sys::fs::createTemporaryFile("bolt-cfg", "dot", Filename)) { | |||
3139 | errs() << "BOLT-ERROR: " << EC.message() << ", unable to create " | |||
3140 | << " bolt-cfg-XXXXX.dot temporary file.\n"; | |||
3141 | return; | |||
3142 | } | |||
3143 | dumpGraphToFile(std::string(Filename)); | |||
3144 | if (DisplayGraph(Filename)) | |||
3145 | errs() << "BOLT-ERROR: Can't display " << Filename << " with graphviz.\n"; | |||
3146 | if (std::error_code EC = sys::fs::remove(Filename)) { | |||
3147 | errs() << "BOLT-WARNING: " << EC.message() << ", failed to remove " | |||
3148 | << Filename << "\n"; | |||
3149 | } | |||
3150 | } | |||
3151 | ||||
3152 | void BinaryFunction::dumpGraphForPass(std::string Annotation) const { | |||
3153 | if (!opts::shouldPrint(*this)) | |||
3154 | return; | |||
3155 | ||||
3156 | std::string Filename = constructFilename(getPrintName(), Annotation, ".dot"); | |||
3157 | if (opts::Verbosity >= 1) | |||
3158 | outs() << "BOLT-INFO: dumping CFG to " << Filename << "\n"; | |||
3159 | dumpGraphToFile(Filename); | |||
3160 | } | |||
3161 | ||||
3162 | void BinaryFunction::dumpGraphToFile(std::string Filename) const { | |||
3163 | std::error_code EC; | |||
3164 | raw_fd_ostream of(Filename, EC, sys::fs::OF_None); | |||
3165 | if (EC) { | |||
3166 | if (opts::Verbosity >= 1) { | |||
3167 | errs() << "BOLT-WARNING: " << EC.message() << ", unable to open " | |||
3168 | << Filename << " for output.\n"; | |||
3169 | } | |||
3170 | return; | |||
3171 | } | |||
3172 | dumpGraph(of); | |||
3173 | } | |||
3174 | ||||
3175 | bool BinaryFunction::validateCFG() const { | |||
3176 | bool Valid = true; | |||
3177 | for (BinaryBasicBlock *BB : BasicBlocks) | |||
3178 | Valid &= BB->validateSuccessorInvariants(); | |||
3179 | ||||
3180 | if (!Valid) | |||
3181 | return Valid; | |||
3182 | ||||
3183 | // Make sure all blocks in CFG are valid. | |||
3184 | auto validateBlock = [this](const BinaryBasicBlock *BB, StringRef Desc) { | |||
3185 | if (!BB->isValid()) { | |||
3186 | errs() << "BOLT-ERROR: deleted " << Desc << " " << BB->getName() | |||
3187 | << " detected in:\n"; | |||
3188 | this->dump(); | |||
3189 | return false; | |||
3190 | } | |||
3191 | return true; | |||
3192 | }; | |||
3193 | for (const BinaryBasicBlock *BB : BasicBlocks) { | |||
3194 | if (!validateBlock(BB, "block")) | |||
3195 | return false; | |||
3196 | for (const BinaryBasicBlock *PredBB : BB->predecessors()) | |||
3197 | if (!validateBlock(PredBB, "predecessor")) | |||
3198 | return false; | |||
3199 | for (const BinaryBasicBlock *SuccBB : BB->successors()) | |||
3200 | if (!validateBlock(SuccBB, "successor")) | |||
3201 | return false; | |||
3202 | for (const BinaryBasicBlock *LP : BB->landing_pads()) | |||
3203 | if (!validateBlock(LP, "landing pad")) | |||
3204 | return false; | |||
3205 | for (const BinaryBasicBlock *Thrower : BB->throwers()) | |||
3206 | if (!validateBlock(Thrower, "thrower")) | |||
3207 | return false; | |||
3208 | } | |||
3209 | ||||
3210 | for (const BinaryBasicBlock *BB : BasicBlocks) { | |||
3211 | std::unordered_set<const BinaryBasicBlock *> BBLandingPads; | |||
3212 | for (const BinaryBasicBlock *LP : BB->landing_pads()) { | |||
3213 | if (BBLandingPads.count(LP)) { | |||
3214 | errs() << "BOLT-ERROR: duplicate landing pad detected in" | |||
3215 | << BB->getName() << " in function " << *this << '\n'; | |||
3216 | return false; | |||
3217 | } | |||
3218 | BBLandingPads.insert(LP); | |||
3219 | } | |||
3220 | ||||
3221 | std::unordered_set<const BinaryBasicBlock *> BBThrowers; | |||
3222 | for (const BinaryBasicBlock *Thrower : BB->throwers()) { | |||
3223 | if (BBThrowers.count(Thrower)) { | |||
3224 | errs() << "BOLT-ERROR: duplicate thrower detected in" << BB->getName() | |||
3225 | << " in function " << *this << '\n'; | |||
3226 | return false; | |||
3227 | } | |||
3228 | BBThrowers.insert(Thrower); | |||
3229 | } | |||
3230 | ||||
3231 | for (const BinaryBasicBlock *LPBlock : BB->landing_pads()) { | |||
3232 | if (!llvm::is_contained(LPBlock->throwers(), BB)) { | |||
3233 | errs() << "BOLT-ERROR: inconsistent landing pad detected in " << *this | |||
3234 | << ": " << BB->getName() << " is in LandingPads but not in " | |||
3235 | << LPBlock->getName() << " Throwers\n"; | |||
3236 | return false; | |||
3237 | } | |||
3238 | } | |||
3239 | for (const BinaryBasicBlock *Thrower : BB->throwers()) { | |||
3240 | if (!llvm::is_contained(Thrower->landing_pads(), BB)) { | |||
3241 | errs() << "BOLT-ERROR: inconsistent thrower detected in " << *this | |||
3242 | << ": " << BB->getName() << " is in Throwers list but not in " | |||
3243 | << Thrower->getName() << " LandingPads\n"; | |||
3244 | return false; | |||
3245 | } | |||
3246 | } | |||
3247 | } | |||
3248 | ||||
3249 | return Valid; | |||
3250 | } | |||
3251 | ||||
3252 | void BinaryFunction::fixBranches() { | |||
3253 | auto &MIB = BC.MIB; | |||
3254 | MCContext *Ctx = BC.Ctx.get(); | |||
3255 | ||||
3256 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
3257 | const MCSymbol *TBB = nullptr; | |||
3258 | const MCSymbol *FBB = nullptr; | |||
3259 | MCInst *CondBranch = nullptr; | |||
3260 | MCInst *UncondBranch = nullptr; | |||
3261 | if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch)) | |||
3262 | continue; | |||
3263 | ||||
3264 | // We will create unconditional branch with correct destination if needed. | |||
3265 | if (UncondBranch) | |||
3266 | BB->eraseInstruction(BB->findInstruction(UncondBranch)); | |||
3267 | ||||
3268 | // Basic block that follows the current one in the final layout. | |||
3269 | const BinaryBasicBlock *NextBB = | |||
3270 | Layout.getBasicBlockAfter(BB, /*IgnoreSplits=*/false); | |||
3271 | ||||
3272 | if (BB->succ_size() == 1) { | |||
3273 | // __builtin_unreachable() could create a conditional branch that | |||
3274 | // falls-through into the next function - hence the block will have only | |||
3275 | // one valid successor. Since behaviour is undefined - we replace | |||
3276 | // the conditional branch with an unconditional if required. | |||
3277 | if (CondBranch) | |||
3278 | BB->eraseInstruction(BB->findInstruction(CondBranch)); | |||
3279 | if (BB->getSuccessor() == NextBB) | |||
3280 | continue; | |||
3281 | BB->addBranchInstruction(BB->getSuccessor()); | |||
3282 | } else if (BB->succ_size() == 2) { | |||
3283 | assert(CondBranch && "conditional branch expected")(static_cast <bool> (CondBranch && "conditional branch expected" ) ? void (0) : __assert_fail ("CondBranch && \"conditional branch expected\"" , "bolt/lib/Core/BinaryFunction.cpp", 3283, __extension__ __PRETTY_FUNCTION__ )); | |||
3284 | const BinaryBasicBlock *TSuccessor = BB->getConditionalSuccessor(true); | |||
3285 | const BinaryBasicBlock *FSuccessor = BB->getConditionalSuccessor(false); | |||
3286 | // Check whether we support reversing this branch direction | |||
3287 | const bool IsSupported = | |||
3288 | !MIB->isUnsupportedBranch(CondBranch->getOpcode()); | |||
3289 | if (NextBB && NextBB == TSuccessor && IsSupported) { | |||
3290 | std::swap(TSuccessor, FSuccessor); | |||
3291 | { | |||
3292 | auto L = BC.scopeLock(); | |||
3293 | MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(), Ctx); | |||
3294 | } | |||
3295 | BB->swapConditionalSuccessors(); | |||
3296 | } else { | |||
3297 | auto L = BC.scopeLock(); | |||
3298 | MIB->replaceBranchTarget(*CondBranch, TSuccessor->getLabel(), Ctx); | |||
3299 | } | |||
3300 | if (TSuccessor == FSuccessor) | |||
3301 | BB->removeDuplicateConditionalSuccessor(CondBranch); | |||
3302 | if (!NextBB || | |||
3303 | ((NextBB != TSuccessor || !IsSupported) && NextBB != FSuccessor)) { | |||
3304 | // If one of the branches is guaranteed to be "long" while the other | |||
3305 | // could be "short", then prioritize short for "taken". This will | |||
3306 | // generate a sequence 1 byte shorter on x86. | |||
3307 | if (IsSupported && BC.isX86() && | |||
3308 | TSuccessor->getFragmentNum() != FSuccessor->getFragmentNum() && | |||
3309 | BB->getFragmentNum() != TSuccessor->getFragmentNum()) { | |||
3310 | std::swap(TSuccessor, FSuccessor); | |||
3311 | { | |||
3312 | auto L = BC.scopeLock(); | |||
3313 | MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(), | |||
3314 | Ctx); | |||
3315 | } | |||
3316 | BB->swapConditionalSuccessors(); | |||
3317 | } | |||
3318 | BB->addBranchInstruction(FSuccessor); | |||
3319 | } | |||
3320 | } | |||
3321 | // Cases where the number of successors is 0 (block ends with a | |||
3322 | // terminator) or more than 2 (switch table) don't require branch | |||
3323 | // instruction adjustments. | |||
3324 | } | |||
3325 | assert((!isSimple() || validateCFG()) &&(static_cast <bool> ((!isSimple() || validateCFG()) && "Invalid CFG detected after fixing branches") ? void (0) : __assert_fail ("(!isSimple() || validateCFG()) && \"Invalid CFG detected after fixing branches\"" , "bolt/lib/Core/BinaryFunction.cpp", 3326, __extension__ __PRETTY_FUNCTION__ )) | |||
3326 | "Invalid CFG detected after fixing branches")(static_cast <bool> ((!isSimple() || validateCFG()) && "Invalid CFG detected after fixing branches") ? void (0) : __assert_fail ("(!isSimple() || validateCFG()) && \"Invalid CFG detected after fixing branches\"" , "bolt/lib/Core/BinaryFunction.cpp", 3326, __extension__ __PRETTY_FUNCTION__ )); | |||
3327 | } | |||
3328 | ||||
3329 | void BinaryFunction::propagateGnuArgsSizeInfo( | |||
3330 | MCPlusBuilder::AllocatorIdTy AllocId) { | |||
3331 | assert(CurrentState == State::Disassembled && "unexpected function state")(static_cast <bool> (CurrentState == State::Disassembled && "unexpected function state") ? void (0) : __assert_fail ("CurrentState == State::Disassembled && \"unexpected function state\"" , "bolt/lib/Core/BinaryFunction.cpp", 3331, __extension__ __PRETTY_FUNCTION__ )); | |||
3332 | ||||
3333 | if (!hasEHRanges() || !usesGnuArgsSize()) | |||
3334 | return; | |||
3335 | ||||
3336 | // The current value of DW_CFA_GNU_args_size affects all following | |||
3337 | // invoke instructions until the next CFI overrides it. | |||
3338 | // It is important to iterate basic blocks in the original order when | |||
3339 | // assigning the value. | |||
3340 | uint64_t CurrentGnuArgsSize = 0; | |||
3341 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
3342 | for (auto II = BB->begin(); II != BB->end();) { | |||
3343 | MCInst &Instr = *II; | |||
3344 | if (BC.MIB->isCFI(Instr)) { | |||
3345 | const MCCFIInstruction *CFI = getCFIFor(Instr); | |||
3346 | if (CFI->getOperation() == MCCFIInstruction::OpGnuArgsSize) { | |||
3347 | CurrentGnuArgsSize = CFI->getOffset(); | |||
3348 | // Delete DW_CFA_GNU_args_size instructions and only regenerate | |||
3349 | // during the final code emission. The information is embedded | |||
3350 | // inside call instructions. | |||
3351 | II = BB->erasePseudoInstruction(II); | |||
3352 | continue; | |||
3353 | } | |||
3354 | } else if (BC.MIB->isInvoke(Instr)) { | |||
3355 | // Add the value of GNU_args_size as an extra operand to invokes. | |||
3356 | BC.MIB->addGnuArgsSize(Instr, CurrentGnuArgsSize, AllocId); | |||
3357 | } | |||
3358 | ++II; | |||
3359 | } | |||
3360 | } | |||
3361 | } | |||
3362 | ||||
3363 | void BinaryFunction::postProcessBranches() { | |||
3364 | if (!isSimple()) | |||
3365 | return; | |||
3366 | for (BinaryBasicBlock &BB : blocks()) { | |||
3367 | auto LastInstrRI = BB.getLastNonPseudo(); | |||
3368 | if (BB.succ_size() == 1) { | |||
3369 | if (LastInstrRI != BB.rend() && | |||
3370 | BC.MIB->isConditionalBranch(*LastInstrRI)) { | |||
3371 | // __builtin_unreachable() could create a conditional branch that | |||
3372 | // falls-through into the next function - hence the block will have only | |||
3373 | // one valid successor. Such behaviour is undefined and thus we remove | |||
3374 | // the conditional branch while leaving a valid successor. | |||
3375 | BB.eraseInstruction(std::prev(LastInstrRI.base())); | |||
3376 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: erasing conditional branch in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: erasing conditional branch in " << BB.getName() << " in function " << *this << '\n'; } } while (false) | |||
3377 | << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: erasing conditional branch in " << BB.getName() << " in function " << *this << '\n'; } } while (false); | |||
3378 | } | |||
3379 | } else if (BB.succ_size() == 0) { | |||
3380 | // Ignore unreachable basic blocks. | |||
3381 | if (BB.pred_size() == 0 || BB.isLandingPad()) | |||
3382 | continue; | |||
3383 | ||||
3384 | // If it's the basic block that does not end up with a terminator - we | |||
3385 | // insert a return instruction unless it's a call instruction. | |||
3386 | if (LastInstrRI == BB.rend()) { | |||
3387 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB " << BB.getName() << " in function " << *this << '\n'; } } while (false) | |||
3388 | dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB " << BB.getName() << " in function " << *this << '\n'; } } while (false) | |||
3389 | << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB " << BB.getName() << " in function " << *this << '\n'; } } while (false); | |||
3390 | continue; | |||
3391 | } | |||
3392 | if (!BC.MIB->isTerminator(*LastInstrRI) && | |||
3393 | !BC.MIB->isCall(*LastInstrRI)) { | |||
3394 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding return to basic block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: adding return to basic block " << BB.getName() << " in function " << *this << '\n'; } } while (false) | |||
3395 | << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: adding return to basic block " << BB.getName() << " in function " << *this << '\n'; } } while (false); | |||
3396 | MCInst ReturnInstr; | |||
3397 | BC.MIB->createReturn(ReturnInstr); | |||
3398 | BB.addInstruction(ReturnInstr); | |||
3399 | } | |||
3400 | } | |||
3401 | } | |||
3402 | assert(validateCFG() && "invalid CFG")(static_cast <bool> (validateCFG() && "invalid CFG" ) ? void (0) : __assert_fail ("validateCFG() && \"invalid CFG\"" , "bolt/lib/Core/BinaryFunction.cpp", 3402, __extension__ __PRETTY_FUNCTION__ )); | |||
3403 | } | |||
3404 | ||||
3405 | MCSymbol *BinaryFunction::addEntryPointAtOffset(uint64_t Offset) { | |||
3406 | assert(Offset && "cannot add primary entry point")(static_cast <bool> (Offset && "cannot add primary entry point" ) ? void (0) : __assert_fail ("Offset && \"cannot add primary entry point\"" , "bolt/lib/Core/BinaryFunction.cpp", 3406, __extension__ __PRETTY_FUNCTION__ )); | |||
3407 | assert(CurrentState == State::Empty || CurrentState == State::Disassembled)(static_cast <bool> (CurrentState == State::Empty || CurrentState == State::Disassembled) ? void (0) : __assert_fail ("CurrentState == State::Empty || CurrentState == State::Disassembled" , "bolt/lib/Core/BinaryFunction.cpp", 3407, __extension__ __PRETTY_FUNCTION__ )); | |||
3408 | ||||
3409 | const uint64_t EntryPointAddress = getAddress() + Offset; | |||
3410 | MCSymbol *LocalSymbol = getOrCreateLocalLabel(EntryPointAddress); | |||
3411 | ||||
3412 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(LocalSymbol); | |||
3413 | if (EntrySymbol) | |||
3414 | return EntrySymbol; | |||
3415 | ||||
3416 | if (BinaryData *EntryBD = BC.getBinaryDataAtAddress(EntryPointAddress)) { | |||
3417 | EntrySymbol = EntryBD->getSymbol(); | |||
3418 | } else { | |||
3419 | EntrySymbol = BC.getOrCreateGlobalSymbol( | |||
3420 | EntryPointAddress, Twine("__ENTRY_") + getOneName() + "@"); | |||
3421 | } | |||
3422 | SecondaryEntryPoints[LocalSymbol] = EntrySymbol; | |||
3423 | ||||
3424 | BC.setSymbolToFunctionMap(EntrySymbol, this); | |||
3425 | ||||
3426 | return EntrySymbol; | |||
3427 | } | |||
3428 | ||||
3429 | MCSymbol *BinaryFunction::addEntryPoint(const BinaryBasicBlock &BB) { | |||
3430 | assert(CurrentState == State::CFG &&(static_cast <bool> (CurrentState == State::CFG && "basic block can be added as an entry only in a function with CFG" ) ? void (0) : __assert_fail ("CurrentState == State::CFG && \"basic block can be added as an entry only in a function with CFG\"" , "bolt/lib/Core/BinaryFunction.cpp", 3431, __extension__ __PRETTY_FUNCTION__ )) | |||
3431 | "basic block can be added as an entry only in a function with CFG")(static_cast <bool> (CurrentState == State::CFG && "basic block can be added as an entry only in a function with CFG" ) ? void (0) : __assert_fail ("CurrentState == State::CFG && \"basic block can be added as an entry only in a function with CFG\"" , "bolt/lib/Core/BinaryFunction.cpp", 3431, __extension__ __PRETTY_FUNCTION__ )); | |||
3432 | ||||
3433 | if (&BB == BasicBlocks.front()) | |||
3434 | return getSymbol(); | |||
3435 | ||||
3436 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB); | |||
3437 | if (EntrySymbol) | |||
3438 | return EntrySymbol; | |||
3439 | ||||
3440 | EntrySymbol = | |||
3441 | BC.Ctx->getOrCreateSymbol("__ENTRY_" + BB.getLabel()->getName()); | |||
3442 | ||||
3443 | SecondaryEntryPoints[BB.getLabel()] = EntrySymbol; | |||
3444 | ||||
3445 | BC.setSymbolToFunctionMap(EntrySymbol, this); | |||
3446 | ||||
3447 | return EntrySymbol; | |||
3448 | } | |||
3449 | ||||
3450 | MCSymbol *BinaryFunction::getSymbolForEntryID(uint64_t EntryID) { | |||
3451 | if (EntryID == 0) | |||
3452 | return getSymbol(); | |||
3453 | ||||
3454 | if (!isMultiEntry()) | |||
3455 | return nullptr; | |||
3456 | ||||
3457 | uint64_t NumEntries = 0; | |||
3458 | if (hasCFG()) { | |||
3459 | for (BinaryBasicBlock *BB : BasicBlocks) { | |||
3460 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB); | |||
3461 | if (!EntrySymbol) | |||
3462 | continue; | |||
3463 | if (NumEntries == EntryID) | |||
3464 | return EntrySymbol; | |||
3465 | ++NumEntries; | |||
3466 | } | |||
3467 | } else { | |||
3468 | for (std::pair<const uint32_t, MCSymbol *> &KV : Labels) { | |||
3469 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second); | |||
3470 | if (!EntrySymbol) | |||
3471 | continue; | |||
3472 | if (NumEntries == EntryID) | |||
3473 | return EntrySymbol; | |||
3474 | ++NumEntries; | |||
3475 | } | |||
3476 | } | |||
3477 | ||||
3478 | return nullptr; | |||
3479 | } | |||
3480 | ||||
3481 | uint64_t BinaryFunction::getEntryIDForSymbol(const MCSymbol *Symbol) const { | |||
3482 | if (!isMultiEntry()) | |||
3483 | return 0; | |||
3484 | ||||
3485 | for (const MCSymbol *FunctionSymbol : getSymbols()) | |||
3486 | if (FunctionSymbol == Symbol) | |||
3487 | return 0; | |||
3488 | ||||
3489 | // Check all secondary entries available as either basic blocks or lables. | |||
3490 | uint64_t NumEntries = 0; | |||
3491 | for (const BinaryBasicBlock *BB : BasicBlocks) { | |||
3492 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB); | |||
3493 | if (!EntrySymbol) | |||
3494 | continue; | |||
3495 | if (EntrySymbol == Symbol) | |||
3496 | return NumEntries; | |||
3497 | ++NumEntries; | |||
3498 | } | |||
3499 | NumEntries = 0; | |||
3500 | for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) { | |||
3501 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second); | |||
3502 | if (!EntrySymbol) | |||
3503 | continue; | |||
3504 | if (EntrySymbol == Symbol) | |||
3505 | return NumEntries; | |||
3506 | ++NumEntries; | |||
3507 | } | |||
3508 | ||||
3509 | llvm_unreachable("symbol not found")::llvm::llvm_unreachable_internal("symbol not found", "bolt/lib/Core/BinaryFunction.cpp" , 3509); | |||
3510 | } | |||
3511 | ||||
3512 | bool BinaryFunction::forEachEntryPoint(EntryPointCallbackTy Callback) const { | |||
3513 | bool Status = Callback(0, getSymbol()); | |||
3514 | if (!isMultiEntry()) | |||
3515 | return Status; | |||
3516 | ||||
3517 | for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) { | |||
3518 | if (!Status) | |||
3519 | break; | |||
3520 | ||||
3521 | MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second); | |||
3522 | if (!EntrySymbol) | |||
3523 | continue; | |||
3524 | ||||
3525 | Status = Callback(KV.first, EntrySymbol); | |||
3526 | } | |||
3527 | ||||
3528 | return Status; | |||
3529 | } | |||
3530 | ||||
3531 | BinaryFunction::BasicBlockListType BinaryFunction::dfs() const { | |||
3532 | BasicBlockListType DFS; | |||
3533 | unsigned Index = 0; | |||
3534 | std::stack<BinaryBasicBlock *> Stack; | |||
3535 | ||||
3536 | // Push entry points to the stack in reverse order. | |||
3537 | // | |||
3538 | // NB: we rely on the original order of entries to match. | |||
3539 | SmallVector<BinaryBasicBlock *> EntryPoints; | |||
3540 | llvm::copy_if(BasicBlocks, std::back_inserter(EntryPoints), | |||
3541 | [&](const BinaryBasicBlock *const BB) { return isEntryPoint(*BB); }); | |||
3542 | // Sort entry points by their offset to make sure we got them in the right | |||
3543 | // order. | |||
3544 | llvm::stable_sort(EntryPoints, [](const BinaryBasicBlock *const A, | |||
3545 | const BinaryBasicBlock *const B) { | |||
3546 | return A->getOffset() < B->getOffset(); | |||
3547 | }); | |||
3548 | for (BinaryBasicBlock *const BB : reverse(EntryPoints)) | |||
3549 | Stack.push(BB); | |||
3550 | ||||
3551 | for (BinaryBasicBlock &BB : blocks()) | |||
3552 | BB.setLayoutIndex(BinaryBasicBlock::InvalidIndex); | |||
3553 | ||||
3554 | while (!Stack.empty()) { | |||
3555 | BinaryBasicBlock *BB = Stack.top(); | |||
3556 | Stack.pop(); | |||
3557 | ||||
3558 | if (BB->getLayoutIndex() != BinaryBasicBlock::InvalidIndex) | |||
3559 | continue; | |||
3560 | ||||
3561 | BB->setLayoutIndex(Index++); | |||
3562 | DFS.push_back(BB); | |||
3563 | ||||
3564 | for (BinaryBasicBlock *SuccBB : BB->landing_pads()) { | |||
3565 | Stack.push(SuccBB); | |||
3566 | } | |||
3567 | ||||
3568 | const MCSymbol *TBB = nullptr; | |||
3569 | const MCSymbol *FBB = nullptr; | |||
3570 | MCInst *CondBranch = nullptr; | |||
3571 | MCInst *UncondBranch = nullptr; | |||
3572 | if (BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch) && CondBranch && | |||
3573 | BB->succ_size() == 2) { | |||
3574 | if (BC.MIB->getCanonicalBranchCondCode(BC.MIB->getCondCode( | |||
3575 | *CondBranch)) == BC.MIB->getCondCode(*CondBranch)) { | |||
3576 | Stack.push(BB->getConditionalSuccessor(true)); | |||
3577 | Stack.push(BB->getConditionalSuccessor(false)); | |||
3578 | } else { | |||
3579 | Stack.push(BB->getConditionalSuccessor(false)); | |||
3580 | Stack.push(BB->getConditionalSuccessor(true)); | |||
3581 | } | |||
3582 | } else { | |||
3583 | for (BinaryBasicBlock *SuccBB : BB->successors()) { | |||
3584 | Stack.push(SuccBB); | |||
3585 | } | |||
3586 | } | |||
3587 | } | |||
3588 | ||||
3589 | return DFS; | |||
3590 | } | |||
3591 | ||||
3592 | size_t BinaryFunction::computeHash(bool UseDFS, | |||
3593 | OperandHashFuncTy OperandHashFunc) const { | |||
3594 | if (size() == 0) | |||
3595 | return 0; | |||
3596 | ||||
3597 | assert(hasCFG() && "function is expected to have CFG")(static_cast <bool> (hasCFG() && "function is expected to have CFG" ) ? void (0) : __assert_fail ("hasCFG() && \"function is expected to have CFG\"" , "bolt/lib/Core/BinaryFunction.cpp", 3597, __extension__ __PRETTY_FUNCTION__ )); | |||
3598 | ||||
3599 | SmallVector<const BinaryBasicBlock *, 0> Order; | |||
3600 | if (UseDFS) | |||
3601 | llvm::copy(dfs(), std::back_inserter(Order)); | |||
3602 | else | |||
3603 | llvm::copy(Layout.blocks(), std::back_inserter(Order)); | |||
3604 | ||||
3605 | // The hash is computed by creating a string of all instruction opcodes and | |||
3606 | // possibly their operands and then hashing that string with std::hash. | |||
3607 | std::string HashString; | |||
3608 | for (const BinaryBasicBlock *BB : Order) | |||
3609 | HashString.append(hashBlock(BC, *BB, OperandHashFunc)); | |||
3610 | ||||
3611 | return Hash = std::hash<std::string>{}(HashString); | |||
3612 | } | |||
3613 | ||||
3614 | void BinaryFunction::computeBlockHashes() const { | |||
3615 | for (const BinaryBasicBlock *BB : BasicBlocks) { | |||
3616 | std::string Hash = | |||
3617 | hashBlock(BC, *BB, [](const MCOperand &Op) { return std::string(); }); | |||
3618 | BB->setHash(std::hash<std::string>{}(Hash)); | |||
3619 | } | |||
3620 | } | |||
3621 | ||||
3622 | void BinaryFunction::insertBasicBlocks( | |||
3623 | BinaryBasicBlock *Start, | |||
3624 | std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs, | |||
3625 | const bool UpdateLayout, const bool UpdateCFIState, | |||
3626 | const bool RecomputeLandingPads) { | |||
3627 | const int64_t StartIndex = Start ? getIndex(Start) : -1LL; | |||
3628 | const size_t NumNewBlocks = NewBBs.size(); | |||
3629 | ||||
3630 | BasicBlocks.insert(BasicBlocks.begin() + (StartIndex + 1), NumNewBlocks, | |||
3631 | nullptr); | |||
3632 | ||||
3633 | int64_t I = StartIndex + 1; | |||
3634 | for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) { | |||
3635 | assert(!BasicBlocks[I])(static_cast <bool> (!BasicBlocks[I]) ? void (0) : __assert_fail ("!BasicBlocks[I]", "bolt/lib/Core/BinaryFunction.cpp", 3635 , __extension__ __PRETTY_FUNCTION__)); | |||
3636 | BasicBlocks[I++] = BB.release(); | |||
3637 | } | |||
3638 | ||||
3639 | if (RecomputeLandingPads) | |||
3640 | recomputeLandingPads(); | |||
3641 | else | |||
3642 | updateBBIndices(0); | |||
3643 | ||||
3644 | if (UpdateLayout) | |||
3645 | updateLayout(Start, NumNewBlocks); | |||
3646 | ||||
3647 | if (UpdateCFIState) | |||
3648 | updateCFIState(Start, NumNewBlocks); | |||
3649 | } | |||
3650 | ||||
3651 | BinaryFunction::iterator BinaryFunction::insertBasicBlocks( | |||
3652 | BinaryFunction::iterator StartBB, | |||
3653 | std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs, | |||
3654 | const bool UpdateLayout, const bool UpdateCFIState, | |||
3655 | const bool RecomputeLandingPads) { | |||
3656 | const unsigned StartIndex = getIndex(&*StartBB); | |||
3657 | const size_t NumNewBlocks = NewBBs.size(); | |||
3658 | ||||
3659 | BasicBlocks.insert(BasicBlocks.begin() + StartIndex + 1, NumNewBlocks, | |||
3660 | nullptr); | |||
3661 | auto RetIter = BasicBlocks.begin() + StartIndex + 1; | |||
3662 | ||||
3663 | unsigned I = StartIndex + 1; | |||
3664 | for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) { | |||
3665 | assert(!BasicBlocks[I])(static_cast <bool> (!BasicBlocks[I]) ? void (0) : __assert_fail ("!BasicBlocks[I]", "bolt/lib/Core/BinaryFunction.cpp", 3665 , __extension__ __PRETTY_FUNCTION__)); | |||
3666 | BasicBlocks[I++] = BB.release(); | |||
3667 | } | |||
3668 | ||||
3669 | if (RecomputeLandingPads) | |||
3670 | recomputeLandingPads(); | |||
3671 | else | |||
3672 | updateBBIndices(0); | |||
3673 | ||||
3674 | if (UpdateLayout) | |||
3675 | updateLayout(*std::prev(RetIter), NumNewBlocks); | |||
3676 | ||||
3677 | if (UpdateCFIState) | |||
3678 | updateCFIState(*std::prev(RetIter), NumNewBlocks); | |||
3679 | ||||
3680 | return RetIter; | |||
3681 | } | |||
3682 | ||||
3683 | void BinaryFunction::updateBBIndices(const unsigned StartIndex) { | |||
3684 | for (unsigned I = StartIndex; I < BasicBlocks.size(); ++I) | |||
3685 | BasicBlocks[I]->Index = I; | |||
3686 | } | |||
3687 | ||||
3688 | void BinaryFunction::updateCFIState(BinaryBasicBlock *Start, | |||
3689 | const unsigned NumNewBlocks) { | |||
3690 | const int32_t CFIState = Start->getCFIStateAtExit(); | |||
3691 | const unsigned StartIndex = getIndex(Start) + 1; | |||
3692 | for (unsigned I = 0; I < NumNewBlocks; ++I) | |||
3693 | BasicBlocks[StartIndex + I]->setCFIState(CFIState); | |||
3694 | } | |||
3695 | ||||
3696 | void BinaryFunction::updateLayout(BinaryBasicBlock *Start, | |||
3697 | const unsigned NumNewBlocks) { | |||
3698 | BasicBlockListType::iterator Begin; | |||
3699 | BasicBlockListType::iterator End; | |||
3700 | ||||
3701 | // If start not provided copy new blocks from the beginning of BasicBlocks | |||
3702 | if (!Start) { | |||
3703 | Begin = BasicBlocks.begin(); | |||
3704 | End = BasicBlocks.begin() + NumNewBlocks; | |||
3705 | } else { | |||
3706 | unsigned StartIndex = getIndex(Start); | |||
3707 | Begin = std::next(BasicBlocks.begin(), StartIndex + 1); | |||
3708 | End = std::next(BasicBlocks.begin(), StartIndex + NumNewBlocks + 1); | |||
3709 | } | |||
3710 | ||||
3711 | // Insert new blocks in the layout immediately after Start. | |||
3712 | Layout.insertBasicBlocks(Start, {Begin, End}); | |||
3713 | Layout.updateLayoutIndices(); | |||
3714 | } | |||
3715 | ||||
3716 | bool BinaryFunction::checkForAmbiguousJumpTables() { | |||
3717 | SmallSet<uint64_t, 4> JumpTables; | |||
3718 | for (BinaryBasicBlock *&BB : BasicBlocks) { | |||
3719 | for (MCInst &Inst : *BB) { | |||
3720 | if (!BC.MIB->isIndirectBranch(Inst)) | |||
3721 | continue; | |||
3722 | uint64_t JTAddress = BC.MIB->getJumpTable(Inst); | |||
3723 | if (!JTAddress) | |||
3724 | continue; | |||
3725 | // This address can be inside another jump table, but we only consider | |||
3726 | // it ambiguous when the same start address is used, not the same JT | |||
3727 | // object. | |||
3728 | if (!JumpTables.count(JTAddress)) { | |||
3729 | JumpTables.insert(JTAddress); | |||
3730 | continue; | |||
3731 | } | |||
3732 | return true; | |||
3733 | } | |||
3734 | } | |||
3735 | return false; | |||
3736 | } | |||
3737 | ||||
3738 | void BinaryFunction::disambiguateJumpTables( | |||
3739 | MCPlusBuilder::AllocatorIdTy AllocId) { | |||
3740 | assert((opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations)(static_cast <bool> ((opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations) ? void (0) : __assert_fail ("(opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations" , "bolt/lib/Core/BinaryFunction.cpp", 3740, __extension__ __PRETTY_FUNCTION__ )); | |||
3741 | SmallPtrSet<JumpTable *, 4> JumpTables; | |||
3742 | for (BinaryBasicBlock *&BB : BasicBlocks) { | |||
3743 | for (MCInst &Inst : *BB) { | |||
3744 | if (!BC.MIB->isIndirectBranch(Inst)) | |||
3745 | continue; | |||
3746 | JumpTable *JT = getJumpTable(Inst); | |||
3747 | if (!JT) | |||
3748 | continue; | |||
3749 | auto Iter = JumpTables.find(JT); | |||
3750 | if (Iter == JumpTables.end()) { | |||
3751 | JumpTables.insert(JT); | |||
3752 | continue; | |||
3753 | } | |||
3754 | // This instruction is an indirect jump using a jump table, but it is | |||
3755 | // using the same jump table of another jump. Try all our tricks to | |||
3756 | // extract the jump table symbol and make it point to a new, duplicated JT | |||
3757 | MCPhysReg BaseReg1; | |||
3758 | uint64_t Scale; | |||
3759 | const MCSymbol *Target; | |||
3760 | // In case we match if our first matcher, first instruction is the one to | |||
3761 | // patch | |||
3762 | MCInst *JTLoadInst = &Inst; | |||
3763 | // Try a standard indirect jump matcher, scale 8 | |||
3764 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher = | |||
3765 | BC.MIB->matchIndJmp(BC.MIB->matchReg(BaseReg1), | |||
3766 | BC.MIB->matchImm(Scale), BC.MIB->matchReg(), | |||
3767 | /*Offset=*/BC.MIB->matchSymbol(Target)); | |||
3768 | if (!IndJmpMatcher->match( | |||
3769 | *BC.MRI, *BC.MIB, | |||
3770 | MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) || | |||
3771 | BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) { | |||
3772 | MCPhysReg BaseReg2; | |||
3773 | uint64_t Offset; | |||
3774 | // Standard JT matching failed. Trying now: | |||
3775 | // movq "jt.2397/1"(,%rax,8), %rax | |||
3776 | // jmpq *%rax | |||
3777 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> LoadMatcherOwner = | |||
3778 | BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg1), | |||
3779 | BC.MIB->matchImm(Scale), BC.MIB->matchReg(), | |||
3780 | /*Offset=*/BC.MIB->matchSymbol(Target)); | |||
3781 | MCPlusBuilder::MCInstMatcher *LoadMatcher = LoadMatcherOwner.get(); | |||
3782 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher2 = | |||
3783 | BC.MIB->matchIndJmp(std::move(LoadMatcherOwner)); | |||
3784 | if (!IndJmpMatcher2->match( | |||
3785 | *BC.MRI, *BC.MIB, | |||
3786 | MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) || | |||
3787 | BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) { | |||
3788 | // JT matching failed. Trying now: | |||
3789 | // PIC-style matcher, scale 4 | |||
3790 | // addq %rdx, %rsi | |||
3791 | // addq %rdx, %rdi | |||
3792 | // leaq DATAat0x402450(%rip), %r11 | |||
3793 | // movslq (%r11,%rdx,4), %rcx | |||
3794 | // addq %r11, %rcx | |||
3795 | // jmpq *%rcx # JUMPTABLE @0x402450 | |||
3796 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher = | |||
3797 | BC.MIB->matchIndJmp(BC.MIB->matchAdd( | |||
3798 | BC.MIB->matchReg(BaseReg1), | |||
3799 | BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg2), | |||
3800 | BC.MIB->matchImm(Scale), BC.MIB->matchReg(), | |||
3801 | BC.MIB->matchImm(Offset)))); | |||
3802 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> LEAMatcherOwner = | |||
3803 | BC.MIB->matchLoadAddr(BC.MIB->matchSymbol(Target)); | |||
3804 | MCPlusBuilder::MCInstMatcher *LEAMatcher = LEAMatcherOwner.get(); | |||
3805 | std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICBaseAddrMatcher = | |||
3806 | BC.MIB->matchIndJmp(BC.MIB->matchAdd(std::move(LEAMatcherOwner), | |||
3807 | BC.MIB->matchAnyOperand())); | |||
3808 | if (!PICIndJmpMatcher->match( | |||
3809 | *BC.MRI, *BC.MIB, | |||
3810 | MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) || | |||
3811 | Scale != 4 || BaseReg1 != BaseReg2 || Offset != 0 || | |||
3812 | !PICBaseAddrMatcher->match( | |||
3813 | *BC.MRI, *BC.MIB, | |||
3814 | MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1)) { | |||
3815 | llvm_unreachable("Failed to extract jump table base")::llvm::llvm_unreachable_internal("Failed to extract jump table base" , "bolt/lib/Core/BinaryFunction.cpp", 3815); | |||
3816 | continue; | |||
3817 | } | |||
3818 | // Matched PIC, identify the instruction with the reference to the JT | |||
3819 | JTLoadInst = LEAMatcher->CurInst; | |||
3820 | } else { | |||
3821 | // Matched non-PIC | |||
3822 | JTLoadInst = LoadMatcher->CurInst; | |||
3823 | } | |||
3824 | } | |||
3825 | ||||
3826 | uint64_t NewJumpTableID = 0; | |||
3827 | const MCSymbol *NewJTLabel; | |||
3828 | std::tie(NewJumpTableID, NewJTLabel) = | |||
3829 | BC.duplicateJumpTable(*this, JT, Target); | |||
3830 | { | |||
3831 | auto L = BC.scopeLock(); | |||
3832 | BC.MIB->replaceMemOperandDisp(*JTLoadInst, NewJTLabel, BC.Ctx.get()); | |||
3833 | } | |||
3834 | // We use a unique ID with the high bit set as address for this "injected" | |||
3835 | // jump table (not originally in the input binary). | |||
3836 | BC.MIB->setJumpTable(Inst, NewJumpTableID, 0, AllocId); | |||
3837 | } | |||
3838 | } | |||
3839 | } | |||
3840 | ||||
3841 | bool BinaryFunction::replaceJumpTableEntryIn(BinaryBasicBlock *BB, | |||
3842 | BinaryBasicBlock *OldDest, | |||
3843 | BinaryBasicBlock *NewDest) { | |||
3844 | MCInst *Instr = BB->getLastNonPseudoInstr(); | |||
3845 | if (!Instr || !BC.MIB->isIndirectBranch(*Instr)) | |||
3846 | return false; | |||
3847 | uint64_t JTAddress = BC.MIB->getJumpTable(*Instr); | |||
3848 | assert(JTAddress && "Invalid jump table address")(static_cast <bool> (JTAddress && "Invalid jump table address" ) ? void (0) : __assert_fail ("JTAddress && \"Invalid jump table address\"" , "bolt/lib/Core/BinaryFunction.cpp", 3848, __extension__ __PRETTY_FUNCTION__ )); | |||
3849 | JumpTable *JT = getJumpTableContainingAddress(JTAddress); | |||
3850 | assert(JT && "No jump table structure for this indirect branch")(static_cast <bool> (JT && "No jump table structure for this indirect branch" ) ? void (0) : __assert_fail ("JT && \"No jump table structure for this indirect branch\"" , "bolt/lib/Core/BinaryFunction.cpp", 3850, __extension__ __PRETTY_FUNCTION__ )); | |||
3851 | bool Patched = JT->replaceDestination(JTAddress, OldDest->getLabel(), | |||
3852 | NewDest->getLabel()); | |||
3853 | (void)Patched; | |||
3854 | assert(Patched && "Invalid entry to be replaced in jump table")(static_cast <bool> (Patched && "Invalid entry to be replaced in jump table" ) ? void (0) : __assert_fail ("Patched && \"Invalid entry to be replaced in jump table\"" , "bolt/lib/Core/BinaryFunction.cpp", 3854, __extension__ __PRETTY_FUNCTION__ )); | |||
3855 | return true; | |||
3856 | } | |||
3857 | ||||
3858 | BinaryBasicBlock *BinaryFunction::splitEdge(BinaryBasicBlock *From, | |||
3859 | BinaryBasicBlock *To) { | |||
3860 | // Create intermediate BB | |||
3861 | MCSymbol *Tmp; | |||
3862 | { | |||
3863 | auto L = BC.scopeLock(); | |||
3864 | Tmp = BC.Ctx->createNamedTempSymbol("SplitEdge"); | |||
3865 | } | |||
3866 | // Link new BBs to the original input offset of the From BB, so we can map | |||
3867 | // samples recorded in new BBs back to the original BB seem in the input | |||
3868 | // binary (if using BAT) | |||
3869 | std::unique_ptr<BinaryBasicBlock> NewBB = createBasicBlock(Tmp); | |||
3870 | NewBB->setOffset(From->getInputOffset()); | |||
3871 | BinaryBasicBlock *NewBBPtr = NewBB.get(); | |||
3872 | ||||
3873 | // Update "From" BB | |||
3874 | auto I = From->succ_begin(); | |||
3875 | auto BI = From->branch_info_begin(); | |||
3876 | for (; I != From->succ_end(); ++I) { | |||
3877 | if (*I == To) | |||
3878 | break; | |||
3879 | ++BI; | |||
3880 | } | |||
3881 | assert(I != From->succ_end() && "Invalid CFG edge in splitEdge!")(static_cast <bool> (I != From->succ_end() && "Invalid CFG edge in splitEdge!") ? void (0) : __assert_fail ("I != From->succ_end() && \"Invalid CFG edge in splitEdge!\"" , "bolt/lib/Core/BinaryFunction.cpp", 3881, __extension__ __PRETTY_FUNCTION__ )); | |||
3882 | uint64_t OrigCount = BI->Count; | |||
3883 | uint64_t OrigMispreds = BI->MispredictedCount; | |||
3884 | replaceJumpTableEntryIn(From, To, NewBBPtr); | |||
3885 | From->replaceSuccessor(To, NewBBPtr, OrigCount, OrigMispreds); | |||
3886 | ||||
3887 | NewBB->addSuccessor(To, OrigCount, OrigMispreds); | |||
3888 | NewBB->setExecutionCount(OrigCount); | |||
3889 | NewBB->setIsCold(From->isCold()); | |||
3890 | ||||
3891 | // Update CFI and BB layout with new intermediate BB | |||
3892 | std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs; | |||
3893 | NewBBs.emplace_back(std::move(NewBB)); | |||
3894 | insertBasicBlocks(From, std::move(NewBBs), true, true, | |||
3895 | /*RecomputeLandingPads=*/false); | |||
3896 | return NewBBPtr; | |||
3897 | } | |||
3898 | ||||
3899 | void BinaryFunction::deleteConservativeEdges() { | |||
3900 | // Our goal is to aggressively remove edges from the CFG that we believe are | |||
3901 | // wrong. This is used for instrumentation, where it is safe to remove | |||
3902 | // fallthrough edges because we won't reorder blocks. | |||
3903 | for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) { | |||
3904 | BinaryBasicBlock *BB = *I; | |||
3905 | if (BB->succ_size() != 1 || BB->size() == 0) | |||
3906 | continue; | |||
3907 | ||||
3908 | auto NextBB = std::next(I); | |||
3909 | MCInst *Last = BB->getLastNonPseudoInstr(); | |||
3910 | // Fallthrough is a landing pad? Delete this edge (as long as we don't | |||
3911 | // have a direct jump to it) | |||
3912 | if ((*BB->succ_begin())->isLandingPad() && NextBB != E && | |||
3913 | *BB->succ_begin() == *NextBB && Last && !BC.MIB->isBranch(*Last)) { | |||
3914 | BB->removeAllSuccessors(); | |||
3915 | continue; | |||
3916 | } | |||
3917 | ||||
3918 | // Look for suspicious calls at the end of BB where gcc may optimize it and | |||
3919 | // remove the jump to the epilogue when it knows the call won't return. | |||
3920 | if (!Last || !BC.MIB->isCall(*Last)) | |||
3921 | continue; | |||
3922 | ||||
3923 | const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(*Last); | |||
3924 | if (!CalleeSymbol) | |||
3925 | continue; | |||
3926 | ||||
3927 | StringRef CalleeName = CalleeSymbol->getName(); | |||
3928 | if (CalleeName != "__cxa_throw@PLT" && CalleeName != "_Unwind_Resume@PLT" && | |||
3929 | CalleeName != "__cxa_rethrow@PLT" && CalleeName != "exit@PLT" && | |||
3930 | CalleeName != "abort@PLT") | |||
3931 | continue; | |||
3932 | ||||
3933 | BB->removeAllSuccessors(); | |||
3934 | } | |||
3935 | } | |||
3936 | ||||
3937 | bool BinaryFunction::isSymbolValidInScope(const SymbolRef &Symbol, | |||
3938 | uint64_t SymbolSize) const { | |||
3939 | // If this symbol is in a different section from the one where the | |||
3940 | // function symbol is, don't consider it as valid. | |||
3941 | if (!getOriginSection()->containsAddress( | |||
3942 | cantFail(Symbol.getAddress(), "cannot get symbol address"))) | |||
3943 | return false; | |||
3944 | ||||
3945 | // Some symbols are tolerated inside function bodies, others are not. | |||
3946 | // The real function boundaries may not be known at this point. | |||
3947 | if (BC.isMarker(Symbol)) | |||
3948 | return true; | |||
3949 | ||||
3950 | // It's okay to have a zero-sized symbol in the middle of non-zero-sized | |||
3951 | // function. | |||
3952 | if (SymbolSize == 0 && containsAddress(cantFail(Symbol.getAddress()))) | |||
3953 | return true; | |||
3954 | ||||
3955 | if (cantFail(Symbol.getType()) != SymbolRef::ST_Unknown) | |||
3956 | return false; | |||
3957 | ||||
3958 | if (cantFail(Symbol.getFlags()) & SymbolRef::SF_Global) | |||
3959 | return false; | |||
3960 | ||||
3961 | return true; | |||
3962 | } | |||
3963 | ||||
3964 | void BinaryFunction::adjustExecutionCount(uint64_t Count) { | |||
3965 | if (getKnownExecutionCount() == 0 || Count == 0) | |||
3966 | return; | |||
3967 | ||||
3968 | if (ExecutionCount < Count) | |||
3969 | Count = ExecutionCount; | |||
3970 | ||||
3971 | double AdjustmentRatio = ((double)ExecutionCount - Count) / ExecutionCount; | |||
3972 | if (AdjustmentRatio < 0.0) | |||
3973 | AdjustmentRatio = 0.0; | |||
3974 | ||||
3975 | for (BinaryBasicBlock &BB : blocks()) | |||
3976 | BB.adjustExecutionCount(AdjustmentRatio); | |||
3977 | ||||
3978 | ExecutionCount -= Count; | |||
3979 | } | |||
3980 | ||||
3981 | BinaryFunction::~BinaryFunction() { | |||
3982 | for (BinaryBasicBlock *BB : BasicBlocks) | |||
3983 | delete BB; | |||
3984 | for (BinaryBasicBlock *BB : DeletedBasicBlocks) | |||
3985 | delete BB; | |||
3986 | } | |||
3987 | ||||
3988 | void BinaryFunction::calculateLoopInfo() { | |||
3989 | // Discover loops. | |||
3990 | BinaryDominatorTree DomTree; | |||
3991 | DomTree.recalculate(*this); | |||
3992 | BLI.reset(new BinaryLoopInfo()); | |||
3993 | BLI->analyze(DomTree); | |||
3994 | ||||
3995 | // Traverse discovered loops and add depth and profile information. | |||
3996 | std::stack<BinaryLoop *> St; | |||
3997 | for (auto I = BLI->begin(), E = BLI->end(); I != E; ++I) { | |||
3998 | St.push(*I); | |||
3999 | ++BLI->OuterLoops; | |||
4000 | } | |||
4001 | ||||
4002 | while (!St.empty()) { | |||
4003 | BinaryLoop *L = St.top(); | |||
4004 | St.pop(); | |||
4005 | ++BLI->TotalLoops; | |||
4006 | BLI->MaximumDepth = std::max(L->getLoopDepth(), BLI->MaximumDepth); | |||
4007 | ||||
4008 | // Add nested loops in the stack. | |||
4009 | for (BinaryLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) | |||
4010 | St.push(*I); | |||
4011 | ||||
4012 | // Skip if no valid profile is found. | |||
4013 | if (!hasValidProfile()) { | |||
4014 | L->EntryCount = COUNT_NO_PROFILE; | |||
4015 | L->ExitCount = COUNT_NO_PROFILE; | |||
4016 | L->TotalBackEdgeCount = COUNT_NO_PROFILE; | |||
4017 | continue; | |||
4018 | } | |||
4019 | ||||
4020 | // Compute back edge count. | |||
4021 | SmallVector<BinaryBasicBlock *, 1> Latches; | |||
4022 | L->getLoopLatches(Latches); | |||
4023 | ||||
4024 | for (BinaryBasicBlock *Latch : Latches) { | |||
4025 | auto BI = Latch->branch_info_begin(); | |||
4026 | for (BinaryBasicBlock *Succ : Latch->successors()) { | |||
4027 | if (Succ == L->getHeader()) { | |||
4028 | assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&(static_cast <bool> (BI->Count != BinaryBasicBlock:: COUNT_NO_PROFILE && "profile data not found") ? void ( 0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\"" , "bolt/lib/Core/BinaryFunction.cpp", 4029, __extension__ __PRETTY_FUNCTION__ )) | |||
4029 | "profile data not found")(static_cast <bool> (BI->Count != BinaryBasicBlock:: COUNT_NO_PROFILE && "profile data not found") ? void ( 0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\"" , "bolt/lib/Core/BinaryFunction.cpp", 4029, __extension__ __PRETTY_FUNCTION__ )); | |||
4030 | L->TotalBackEdgeCount += BI->Count; | |||
4031 | } | |||
4032 | ++BI; | |||
4033 | } | |||
4034 | } | |||
4035 | ||||
4036 | // Compute entry count. | |||
4037 | L->EntryCount = L->getHeader()->getExecutionCount() - L->TotalBackEdgeCount; | |||
4038 | ||||
4039 | // Compute exit count. | |||
4040 | SmallVector<BinaryLoop::Edge, 1> ExitEdges; | |||
4041 | L->getExitEdges(ExitEdges); | |||
4042 | for (BinaryLoop::Edge &Exit : ExitEdges) { | |||
4043 | const BinaryBasicBlock *Exiting = Exit.first; | |||
4044 | const BinaryBasicBlock *ExitTarget = Exit.second; | |||
4045 | auto BI = Exiting->branch_info_begin(); | |||
4046 | for (BinaryBasicBlock *Succ : Exiting->successors()) { | |||
4047 | if (Succ == ExitTarget) { | |||
4048 | assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&(static_cast <bool> (BI->Count != BinaryBasicBlock:: COUNT_NO_PROFILE && "profile data not found") ? void ( 0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\"" , "bolt/lib/Core/BinaryFunction.cpp", 4049, __extension__ __PRETTY_FUNCTION__ )) | |||
4049 | "profile data not found")(static_cast <bool> (BI->Count != BinaryBasicBlock:: COUNT_NO_PROFILE && "profile data not found") ? void ( 0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\"" , "bolt/lib/Core/BinaryFunction.cpp", 4049, __extension__ __PRETTY_FUNCTION__ )); | |||
4050 | L->ExitCount += BI->Count; | |||
4051 | } | |||
4052 | ++BI; | |||
4053 | } | |||
4054 | } | |||
4055 | } | |||
4056 | } | |||
4057 | ||||
4058 | void BinaryFunction::updateOutputValues(const MCAsmLayout &Layout) { | |||
4059 | if (!isEmitted()) { | |||
| ||||
4060 | assert(!isInjected() && "injected function should be emitted")(static_cast <bool> (!isInjected() && "injected function should be emitted" ) ? void (0) : __assert_fail ("!isInjected() && \"injected function should be emitted\"" , "bolt/lib/Core/BinaryFunction.cpp", 4060, __extension__ __PRETTY_FUNCTION__ )); | |||
4061 | setOutputAddress(getAddress()); | |||
4062 | setOutputSize(getSize()); | |||
4063 | return; | |||
4064 | } | |||
4065 | ||||
4066 | const uint64_t BaseAddress = getCodeSection()->getOutputAddress(); | |||
4067 | if (BC.HasRelocations || isInjected()) { | |||
4068 | const uint64_t StartOffset = Layout.getSymbolOffset(*getSymbol()); | |||
4069 | const uint64_t EndOffset = Layout.getSymbolOffset(*getFunctionEndLabel()); | |||
4070 | setOutputAddress(BaseAddress + StartOffset); | |||
4071 | setOutputSize(EndOffset - StartOffset); | |||
4072 | if (hasConstantIsland()) { | |||
4073 | const uint64_t DataOffset = | |||
4074 | Layout.getSymbolOffset(*getFunctionConstantIslandLabel()); | |||
4075 | setOutputDataAddress(BaseAddress + DataOffset); | |||
4076 | for (auto It : Islands->Offsets) { | |||
4077 | const uint64_t OldOffset = It.first; | |||
4078 | BinaryData *BD = BC.getBinaryDataAtAddress(getAddress() + OldOffset); | |||
4079 | if (!BD) | |||
4080 | continue; | |||
4081 | ||||
4082 | MCSymbol *Symbol = It.second; | |||
4083 | const uint64_t NewOffset = Layout.getSymbolOffset(*Symbol); | |||
4084 | BD->setOutputLocation(*getCodeSection(), NewOffset); | |||
4085 | } | |||
4086 | } | |||
4087 | if (isSplit()) { | |||
4088 | for (FunctionFragment &FF : getLayout().getSplitFragments()) { | |||
4089 | ErrorOr<BinarySection &> ColdSection = | |||
4090 | getCodeSection(FF.getFragmentNum()); | |||
4091 | // If fragment is empty, cold section might not exist | |||
4092 | if (FF.empty() && ColdSection.getError()) | |||
4093 | continue; | |||
4094 | const uint64_t ColdBaseAddress = ColdSection->getOutputAddress(); | |||
4095 | ||||
4096 | const MCSymbol *ColdStartSymbol = getSymbol(FF.getFragmentNum()); | |||
4097 | // If fragment is empty, symbol might have not been emitted | |||
4098 | if (FF.empty() && (!ColdStartSymbol || !ColdStartSymbol->isDefined()) && | |||
4099 | !hasConstantIsland()) | |||
4100 | continue; | |||
4101 | assert(ColdStartSymbol && ColdStartSymbol->isDefined() &&(static_cast <bool> (ColdStartSymbol && ColdStartSymbol ->isDefined() && "split function should have defined cold symbol" ) ? void (0) : __assert_fail ("ColdStartSymbol && ColdStartSymbol->isDefined() && \"split function should have defined cold symbol\"" , "bolt/lib/Core/BinaryFunction.cpp", 4102, __extension__ __PRETTY_FUNCTION__ )) | |||
4102 | "split function should have defined cold symbol")(static_cast <bool> (ColdStartSymbol && ColdStartSymbol ->isDefined() && "split function should have defined cold symbol" ) ? void (0) : __assert_fail ("ColdStartSymbol && ColdStartSymbol->isDefined() && \"split function should have defined cold symbol\"" , "bolt/lib/Core/BinaryFunction.cpp", 4102, __extension__ __PRETTY_FUNCTION__ )); | |||
4103 | const MCSymbol *ColdEndSymbol = | |||
4104 | getFunctionEndLabel(FF.getFragmentNum()); | |||
4105 | assert(ColdEndSymbol && ColdEndSymbol->isDefined() &&(static_cast <bool> (ColdEndSymbol && ColdEndSymbol ->isDefined() && "split function should have defined cold end symbol" ) ? void (0) : __assert_fail ("ColdEndSymbol && ColdEndSymbol->isDefined() && \"split function should have defined cold end symbol\"" , "bolt/lib/Core/BinaryFunction.cpp", 4106, __extension__ __PRETTY_FUNCTION__ )) | |||
4106 | "split function should have defined cold end symbol")(static_cast <bool> (ColdEndSymbol && ColdEndSymbol ->isDefined() && "split function should have defined cold end symbol" ) ? void (0) : __assert_fail ("ColdEndSymbol && ColdEndSymbol->isDefined() && \"split function should have defined cold end symbol\"" , "bolt/lib/Core/BinaryFunction.cpp", 4106, __extension__ __PRETTY_FUNCTION__ )); | |||
4107 | const uint64_t ColdStartOffset = | |||
4108 | Layout.getSymbolOffset(*ColdStartSymbol); | |||
4109 | const uint64_t ColdEndOffset = Layout.getSymbolOffset(*ColdEndSymbol); | |||
4110 | FF.setAddress(ColdBaseAddress + ColdStartOffset); | |||
4111 | FF.setImageSize(ColdEndOffset - ColdStartOffset); | |||
4112 | if (hasConstantIsland()) { | |||
4113 | const uint64_t DataOffset = | |||
4114 | Layout.getSymbolOffset(*getFunctionColdConstantIslandLabel()); | |||
4115 | setOutputColdDataAddress(ColdBaseAddress + DataOffset); | |||
4116 | } | |||
4117 | } | |||
4118 | } | |||
4119 | } else { | |||
4120 | setOutputAddress(getAddress()); | |||
4121 | setOutputSize(Layout.getSymbolOffset(*getFunctionEndLabel())); | |||
4122 | } | |||
4123 | ||||
4124 | // Update basic block output ranges for the debug info, if we have | |||
4125 | // secondary entry points in the symbol table to update or if writing BAT. | |||
4126 | if (!opts::UpdateDebugSections && !isMultiEntry() && | |||
4127 | !requiresAddressTranslation()) | |||
4128 | return; | |||
4129 | ||||
4130 | // Output ranges should match the input if the body hasn't changed. | |||
4131 | if (!isSimple() && !BC.HasRelocations) | |||
4132 | return; | |||
4133 | ||||
4134 | // AArch64 may have functions that only contains a constant island (no code). | |||
4135 | if (getLayout().block_empty()) | |||
4136 | return; | |||
4137 | ||||
4138 | for (FunctionFragment &FF : getLayout().fragments()) { | |||
4139 | if (FF.empty()) | |||
4140 | continue; | |||
4141 | ||||
4142 | const uint64_t FragmentBaseAddress = | |||
4143 | getCodeSection(isSimple() ? FF.getFragmentNum() : FragmentNum::main()) | |||
4144 | ->getOutputAddress(); | |||
4145 | ||||
4146 | BinaryBasicBlock *PrevBB = nullptr; | |||
4147 | for (BinaryBasicBlock *const BB : FF) { | |||
4148 | assert(BB->getLabel()->isDefined() && "symbol should be defined")(static_cast <bool> (BB->getLabel()->isDefined() && "symbol should be defined") ? void (0) : __assert_fail ("BB->getLabel()->isDefined() && \"symbol should be defined\"" , "bolt/lib/Core/BinaryFunction.cpp", 4148, __extension__ __PRETTY_FUNCTION__ )); | |||
4149 | if (!BC.HasRelocations) { | |||
4150 | if (BB->isSplit()) | |||
4151 | assert(FragmentBaseAddress == FF.getAddress())(static_cast <bool> (FragmentBaseAddress == FF.getAddress ()) ? void (0) : __assert_fail ("FragmentBaseAddress == FF.getAddress()" , "bolt/lib/Core/BinaryFunction.cpp", 4151, __extension__ __PRETTY_FUNCTION__ )); | |||
4152 | else | |||
4153 | assert(FragmentBaseAddress == getOutputAddress())(static_cast <bool> (FragmentBaseAddress == getOutputAddress ()) ? void (0) : __assert_fail ("FragmentBaseAddress == getOutputAddress()" , "bolt/lib/Core/BinaryFunction.cpp", 4153, __extension__ __PRETTY_FUNCTION__ )); | |||
4154 | } | |||
4155 | ||||
4156 | const uint64_t BBOffset = Layout.getSymbolOffset(*BB->getLabel()); | |||
4157 | const uint64_t BBAddress = FragmentBaseAddress + BBOffset; | |||
4158 | BB->setOutputStartAddress(BBAddress); | |||
4159 | ||||
4160 | if (PrevBB) | |||
4161 | PrevBB->setOutputEndAddress(BBAddress); | |||
4162 | PrevBB = BB; | |||
4163 | ||||
4164 | BB->updateOutputValues(Layout); | |||
4165 | } | |||
4166 | ||||
4167 | PrevBB->setOutputEndAddress(PrevBB->isSplit() | |||
| ||||
4168 | ? FF.getAddress() + FF.getImageSize() | |||
4169 | : getOutputAddress() + getOutputSize()); | |||
4170 | } | |||
4171 | } | |||
4172 | ||||
4173 | DebugAddressRangesVector BinaryFunction::getOutputAddressRanges() const { | |||
4174 | DebugAddressRangesVector OutputRanges; | |||
4175 | ||||
4176 | if (isFolded()) | |||
4177 | return OutputRanges; | |||
4178 | ||||
4179 | if (IsFragment) | |||
4180 | return OutputRanges; | |||
4181 | ||||
4182 | OutputRanges.emplace_back(getOutputAddress(), | |||
4183 | getOutputAddress() + getOutputSize()); | |||
4184 | if (isSplit()) { | |||
4185 | assert(isEmitted() && "split function should be emitted")(static_cast <bool> (isEmitted() && "split function should be emitted" ) ? void (0) : __assert_fail ("isEmitted() && \"split function should be emitted\"" , "bolt/lib/Core/BinaryFunction.cpp", 4185, __extension__ __PRETTY_FUNCTION__ )); | |||
4186 | for (const FunctionFragment &FF : getLayout().getSplitFragments()) | |||
4187 | OutputRanges.emplace_back(FF.getAddress(), | |||
4188 | FF.getAddress() + FF.getImageSize()); | |||
4189 | } | |||
4190 | ||||
4191 | if (isSimple()) | |||
4192 | return OutputRanges; | |||
4193 | ||||
4194 | for (BinaryFunction *Frag : Fragments) { | |||
4195 | assert(!Frag->isSimple() &&(static_cast <bool> (!Frag->isSimple() && "fragment of non-simple function should also be non-simple" ) ? void (0) : __assert_fail ("!Frag->isSimple() && \"fragment of non-simple function should also be non-simple\"" , "bolt/lib/Core/BinaryFunction.cpp", 4196, __extension__ __PRETTY_FUNCTION__ )) | |||
4196 | "fragment of non-simple function should also be non-simple")(static_cast <bool> (!Frag->isSimple() && "fragment of non-simple function should also be non-simple" ) ? void (0) : __assert_fail ("!Frag->isSimple() && \"fragment of non-simple function should also be non-simple\"" , "bolt/lib/Core/BinaryFunction.cpp", 4196, __extension__ __PRETTY_FUNCTION__ )); | |||
4197 | OutputRanges.emplace_back(Frag->getOutputAddress(), | |||
4198 | Frag->getOutputAddress() + Frag->getOutputSize()); | |||
4199 | } | |||
4200 | ||||
4201 | return OutputRanges; | |||
4202 | } | |||
4203 | ||||
4204 | uint64_t BinaryFunction::translateInputToOutputAddress(uint64_t Address) const { | |||
4205 | if (isFolded()) | |||
4206 | return 0; | |||
4207 | ||||
4208 | // If the function hasn't changed return the same address. | |||
4209 | if (!isEmitted()) | |||
4210 | return Address; | |||
4211 | ||||
4212 | if (Address < getAddress()) | |||
4213 | return 0; | |||
4214 | ||||
4215 | // Check if the address is associated with an instruction that is tracked | |||
4216 | // by address translation. | |||
4217 | auto KV = InputOffsetToAddressMap.find(Address - getAddress()); | |||
4218 | if (KV != InputOffsetToAddressMap.end()) | |||
4219 | return KV->second; | |||
4220 | ||||
4221 | // FIXME: #18950828 - we rely on relative offsets inside basic blocks to stay | |||
4222 | // intact. Instead we can use pseudo instructions and/or annotations. | |||
4223 | const uint64_t Offset = Address - getAddress(); | |||
4224 | const BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset); | |||
4225 | if (!BB) { | |||
4226 | // Special case for address immediately past the end of the function. | |||
4227 | if (Offset == getSize()) | |||
4228 | return getOutputAddress() + getOutputSize(); | |||
4229 | ||||
4230 | return 0; | |||
4231 | } | |||
4232 | ||||
4233 | return std::min(BB->getOutputAddressRange().first + Offset - BB->getOffset(), | |||
4234 | BB->getOutputAddressRange().second); | |||
4235 | } | |||
4236 | ||||
4237 | DebugAddressRangesVector BinaryFunction::translateInputToOutputRanges( | |||
4238 | const DWARFAddressRangesVector &InputRanges) const { | |||
4239 | DebugAddressRangesVector OutputRanges; | |||
4240 | ||||
4241 | if (isFolded()) | |||
4242 | return OutputRanges; | |||
4243 | ||||
4244 | // If the function hasn't changed return the same ranges. | |||
4245 | if (!isEmitted()) { | |||
4246 | OutputRanges.resize(InputRanges.size()); | |||
4247 | llvm::transform(InputRanges, OutputRanges.begin(), | |||
4248 | [](const DWARFAddressRange &Range) { | |||
4249 | return DebugAddressRange(Range.LowPC, Range.HighPC); | |||
4250 | }); | |||
4251 | return OutputRanges; | |||
4252 | } | |||
4253 | ||||
4254 | // Even though we will merge ranges in a post-processing pass, we attempt to | |||
4255 | // merge them in a main processing loop as it improves the processing time. | |||
4256 | uint64_t PrevEndAddress = 0; | |||
4257 | for (const DWARFAddressRange &Range : InputRanges) { | |||
4258 | if (!containsAddress(Range.LowPC)) { | |||
4259 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4260 | dbgs() << "BOLT-DEBUG: invalid debug address range detected for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4261 | << *this << " : [0x" << Twine::utohexstr(Range.LowPC) << ", 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4262 | << Twine::utohexstr(Range.HighPC) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false); | |||
4263 | PrevEndAddress = 0; | |||
4264 | continue; | |||
4265 | } | |||
4266 | uint64_t InputOffset = Range.LowPC - getAddress(); | |||
4267 | const uint64_t InputEndOffset = | |||
4268 | std::min(Range.HighPC - getAddress(), getSize()); | |||
4269 | ||||
4270 | auto BBI = llvm::upper_bound(BasicBlockOffsets, | |||
4271 | BasicBlockOffset(InputOffset, nullptr), | |||
4272 | CompareBasicBlockOffsets()); | |||
4273 | --BBI; | |||
4274 | do { | |||
4275 | const BinaryBasicBlock *BB = BBI->second; | |||
4276 | if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) { | |||
4277 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4278 | dbgs() << "BOLT-DEBUG: invalid debug address range detected for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4279 | << *this << " : [0x" << Twine::utohexstr(Range.LowPC)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false) | |||
4280 | << ", 0x" << Twine::utohexstr(Range.HighPC) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for " << *this << " : [0x" << Twine::utohexstr(Range .LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC ) << "]\n"; } } while (false); | |||
4281 | PrevEndAddress = 0; | |||
4282 | break; | |||
4283 | } | |||
4284 | ||||
4285 | // Skip the range if the block was deleted. | |||
4286 | if (const uint64_t OutputStart = BB->getOutputAddressRange().first) { | |||
4287 | const uint64_t StartAddress = | |||
4288 | OutputStart + InputOffset - BB->getOffset(); | |||
4289 | uint64_t EndAddress = BB->getOutputAddressRange().second; | |||
4290 | if (InputEndOffset < BB->getEndOffset()) | |||
4291 | EndAddress = StartAddress + InputEndOffset - InputOffset; | |||
4292 | ||||
4293 | if (StartAddress == PrevEndAddress) { | |||
4294 | OutputRanges.back().HighPC = | |||
4295 | std::max(OutputRanges.back().HighPC, EndAddress); | |||
4296 | } else { | |||
4297 | OutputRanges.emplace_back(StartAddress, | |||
4298 | std::max(StartAddress, EndAddress)); | |||
4299 | } | |||
4300 | PrevEndAddress = OutputRanges.back().HighPC; | |||
4301 | } | |||
4302 | ||||
4303 | InputOffset = BB->getEndOffset(); | |||
4304 | ++BBI; | |||
4305 | } while (InputOffset < InputEndOffset); | |||
4306 | } | |||
4307 | ||||
4308 | // Post-processing pass to sort and merge ranges. | |||
4309 | llvm::sort(OutputRanges); | |||
4310 | DebugAddressRangesVector MergedRanges; | |||
4311 | PrevEndAddress = 0; | |||
4312 | for (const DebugAddressRange &Range : OutputRanges) { | |||
4313 | if (Range.LowPC <= PrevEndAddress) { | |||
4314 | MergedRanges.back().HighPC = | |||
4315 | std::max(MergedRanges.back().HighPC, Range.HighPC); | |||
4316 | } else { | |||
4317 | MergedRanges.emplace_back(Range.LowPC, Range.HighPC); | |||
4318 | } | |||
4319 | PrevEndAddress = MergedRanges.back().HighPC; | |||
4320 | } | |||
4321 | ||||
4322 | return MergedRanges; | |||
4323 | } | |||
4324 | ||||
4325 | MCInst *BinaryFunction::getInstructionAtOffset(uint64_t Offset) { | |||
4326 | if (CurrentState == State::Disassembled) { | |||
4327 | auto II = Instructions.find(Offset); | |||
4328 | return (II == Instructions.end()) ? nullptr : &II->second; | |||
4329 | } else if (CurrentState == State::CFG) { | |||
4330 | BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset); | |||
4331 | if (!BB) | |||
4332 | return nullptr; | |||
4333 | ||||
4334 | for (MCInst &Inst : *BB) { | |||
4335 | constexpr uint32_t InvalidOffset = std::numeric_limits<uint32_t>::max(); | |||
4336 | if (Offset == BC.MIB->getOffsetWithDefault(Inst, InvalidOffset)) | |||
4337 | return &Inst; | |||
4338 | } | |||
4339 | ||||
4340 | if (MCInst *LastInstr = BB->getLastNonPseudoInstr()) { | |||
4341 | const uint32_t Size = | |||
4342 | BC.MIB->getAnnotationWithDefault<uint32_t>(*LastInstr, "Size"); | |||
4343 | if (BB->getEndOffset() - Offset == Size) | |||
4344 | return LastInstr; | |||
4345 | } | |||
4346 | ||||
4347 | return nullptr; | |||
4348 | } else { | |||
4349 | llvm_unreachable("invalid CFG state to use getInstructionAtOffset()")::llvm::llvm_unreachable_internal("invalid CFG state to use getInstructionAtOffset()" , "bolt/lib/Core/BinaryFunction.cpp", 4349); | |||
4350 | } | |||
4351 | } | |||
4352 | ||||
4353 | DebugLocationsVector BinaryFunction::translateInputToOutputLocationList( | |||
4354 | const DebugLocationsVector &InputLL) const { | |||
4355 | DebugLocationsVector OutputLL; | |||
4356 | ||||
4357 | if (isFolded()) | |||
4358 | return OutputLL; | |||
4359 | ||||
4360 | // If the function hasn't changed - there's nothing to update. | |||
4361 | if (!isEmitted()) | |||
4362 | return InputLL; | |||
4363 | ||||
4364 | uint64_t PrevEndAddress = 0; | |||
4365 | SmallVectorImpl<uint8_t> *PrevExpr = nullptr; | |||
4366 | for (const DebugLocationEntry &Entry : InputLL) { | |||
4367 | const uint64_t Start = Entry.LowPC; | |||
4368 | const uint64_t End = Entry.HighPC; | |||
4369 | if (!containsAddress(Start)) { | |||
4370 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4371 | "for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4372 | << *this << " : [0x" << Twine::utohexstr(Start)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4373 | << ", 0x" << Twine::utohexstr(End) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false); | |||
4374 | continue; | |||
4375 | } | |||
4376 | uint64_t InputOffset = Start - getAddress(); | |||
4377 | const uint64_t InputEndOffset = std::min(End - getAddress(), getSize()); | |||
4378 | auto BBI = llvm::upper_bound(BasicBlockOffsets, | |||
4379 | BasicBlockOffset(InputOffset, nullptr), | |||
4380 | CompareBasicBlockOffsets()); | |||
4381 | --BBI; | |||
4382 | do { | |||
4383 | const BinaryBasicBlock *BB = BBI->second; | |||
4384 | if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) { | |||
4385 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4386 | "for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4387 | << *this << " : [0x" << Twine::utohexstr(Start)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false) | |||
4388 | << ", 0x" << Twine::utohexstr(End) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected " "for " << *this << " : [0x" << Twine::utohexstr (Start) << ", 0x" << Twine::utohexstr(End) << "]\n"; } } while (false); | |||
4389 | PrevEndAddress = 0; | |||
4390 | break; | |||
4391 | } | |||
4392 | ||||
4393 | // Skip the range if the block was deleted. | |||
4394 | if (const uint64_t OutputStart = BB->getOutputAddressRange().first) { | |||
4395 | const uint64_t StartAddress = | |||
4396 | OutputStart + InputOffset - BB->getOffset(); | |||
4397 | uint64_t EndAddress = BB->getOutputAddressRange().second; | |||
4398 | if (InputEndOffset < BB->getEndOffset()) | |||
4399 | EndAddress = StartAddress + InputEndOffset - InputOffset; | |||
4400 | ||||
4401 | if (StartAddress == PrevEndAddress && Entry.Expr == *PrevExpr) { | |||
4402 | OutputLL.back().HighPC = std::max(OutputLL.back().HighPC, EndAddress); | |||
4403 | } else { | |||
4404 | OutputLL.emplace_back(DebugLocationEntry{ | |||
4405 | StartAddress, std::max(StartAddress, EndAddress), Entry.Expr}); | |||
4406 | } | |||
4407 | PrevEndAddress = OutputLL.back().HighPC; | |||
4408 | PrevExpr = &OutputLL.back().Expr; | |||
4409 | } | |||
4410 | ||||
4411 | ++BBI; | |||
4412 | InputOffset = BB->getEndOffset(); | |||
4413 | } while (InputOffset < InputEndOffset); | |||
4414 | } | |||
4415 | ||||
4416 | // Sort and merge adjacent entries with identical location. | |||
4417 | llvm::stable_sort( | |||
4418 | OutputLL, [](const DebugLocationEntry &A, const DebugLocationEntry &B) { | |||
4419 | return A.LowPC < B.LowPC; | |||
4420 | }); | |||
4421 | DebugLocationsVector MergedLL; | |||
4422 | PrevEndAddress = 0; | |||
4423 | PrevExpr = nullptr; | |||
4424 | for (const DebugLocationEntry &Entry : OutputLL) { | |||
4425 | if (Entry.LowPC <= PrevEndAddress && *PrevExpr == Entry.Expr) { | |||
4426 | MergedLL.back().HighPC = std::max(Entry.HighPC, MergedLL.back().HighPC); | |||
4427 | } else { | |||
4428 | const uint64_t Begin = std::max(Entry.LowPC, PrevEndAddress); | |||
4429 | const uint64_t End = std::max(Begin, Entry.HighPC); | |||
4430 | MergedLL.emplace_back(DebugLocationEntry{Begin, End, Entry.Expr}); | |||
4431 | } | |||
4432 | PrevEndAddress = MergedLL.back().HighPC; | |||
4433 | PrevExpr = &MergedLL.back().Expr; | |||
4434 | } | |||
4435 | ||||
4436 | return MergedLL; | |||
4437 | } | |||
4438 | ||||
4439 | void BinaryFunction::printLoopInfo(raw_ostream &OS) const { | |||
4440 | if (!opts::shouldPrint(*this)) | |||
4441 | return; | |||
4442 | ||||
4443 | OS << "Loop Info for Function \"" << *this << "\""; | |||
4444 | if (hasValidProfile()) | |||
4445 | OS << " (count: " << getExecutionCount() << ")"; | |||
4446 | OS << "\n"; | |||
4447 | ||||
4448 | std::stack<BinaryLoop *> St; | |||
4449 | for (BinaryLoop *L : *BLI) | |||
4450 | St.push(L); | |||
4451 | while (!St.empty()) { | |||
4452 | BinaryLoop *L = St.top(); | |||
4453 | St.pop(); | |||
4454 | ||||
4455 | for (BinaryLoop *Inner : *L) | |||
4456 | St.push(Inner); | |||
4457 | ||||
4458 | if (!hasValidProfile()) | |||
4459 | continue; | |||
4460 | ||||
4461 | OS << (L->getLoopDepth() > 1 ? "Nested" : "Outer") | |||
4462 | << " loop header: " << L->getHeader()->getName(); | |||
4463 | OS << "\n"; | |||
4464 | OS << "Loop basic blocks: "; | |||
4465 | ListSeparator LS; | |||
4466 | for (BinaryBasicBlock *BB : L->blocks()) | |||
4467 | OS << LS << BB->getName(); | |||
4468 | OS << "\n"; | |||
4469 | if (hasValidProfile()) { | |||
4470 | OS << "Total back edge count: " << L->TotalBackEdgeCount << "\n"; | |||
4471 | OS << "Loop entry count: " << L->EntryCount << "\n"; | |||
4472 | OS << "Loop exit count: " << L->ExitCount << "\n"; | |||
4473 | if (L->EntryCount > 0) { | |||
4474 | OS << "Average iters per entry: " | |||
4475 | << format("%.4lf", (double)L->TotalBackEdgeCount / L->EntryCount) | |||
4476 | << "\n"; | |||
4477 | } | |||
4478 | } | |||
4479 | OS << "----\n"; | |||
4480 | } | |||
4481 | ||||
4482 | OS << "Total number of loops: " << BLI->TotalLoops << "\n"; | |||
4483 | OS << "Number of outer loops: " << BLI->OuterLoops << "\n"; | |||
4484 | OS << "Maximum nested loop depth: " << BLI->MaximumDepth << "\n\n"; | |||
4485 | } | |||
4486 | ||||
4487 | bool BinaryFunction::isAArch64Veneer() const { | |||
4488 | if (empty() || hasIslandsInfo()) | |||
4489 | return false; | |||
4490 | ||||
4491 | BinaryBasicBlock &BB = **BasicBlocks.begin(); | |||
4492 | for (MCInst &Inst : BB) | |||
4493 | if (!BC.MIB->hasAnnotation(Inst, "AArch64Veneer")) | |||
4494 | return false; | |||
4495 | ||||
4496 | for (auto I = BasicBlocks.begin() + 1, E = BasicBlocks.end(); I != E; ++I) { | |||
4497 | for (MCInst &Inst : **I) | |||
4498 | if (!BC.MIB->isNoop(Inst)) | |||
4499 | return false; | |||
4500 | } | |||
4501 | ||||
4502 | return true; | |||
4503 | } | |||
4504 | ||||
4505 | void BinaryFunction::addRelocation(uint64_t Address, MCSymbol *Symbol, | |||
4506 | uint64_t RelType, uint64_t Addend, | |||
4507 | uint64_t Value) { | |||
4508 | assert(Address >= getAddress() && Address < getAddress() + getMaxSize() &&(static_cast <bool> (Address >= getAddress() && Address < getAddress() + getMaxSize() && "address is outside of the function" ) ? void (0) : __assert_fail ("Address >= getAddress() && Address < getAddress() + getMaxSize() && \"address is outside of the function\"" , "bolt/lib/Core/BinaryFunction.cpp", 4509, __extension__ __PRETTY_FUNCTION__ )) | |||
4509 | "address is outside of the function")(static_cast <bool> (Address >= getAddress() && Address < getAddress() + getMaxSize() && "address is outside of the function" ) ? void (0) : __assert_fail ("Address >= getAddress() && Address < getAddress() + getMaxSize() && \"address is outside of the function\"" , "bolt/lib/Core/BinaryFunction.cpp", 4509, __extension__ __PRETTY_FUNCTION__ )); | |||
4510 | uint64_t Offset = Address - getAddress(); | |||
4511 | LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addRelocation in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: addRelocation in " << formatv("{0}@{1:x} against {2}\n", this, Offset, Symbol-> getName()); } } while (false) | |||
4512 | << formatv("{0}@{1:x} against {2}\n", this, Offset,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: addRelocation in " << formatv("{0}@{1:x} against {2}\n", this, Offset, Symbol-> getName()); } } while (false) | |||
4513 | Symbol->getName()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("bolt")) { dbgs() << "BOLT-DEBUG: addRelocation in " << formatv("{0}@{1:x} against {2}\n", this, Offset, Symbol-> getName()); } } while (false); | |||
4514 | bool IsCI = BC.isAArch64() && isInConstantIsland(Address); | |||
4515 | std::map<uint64_t, Relocation> &Rels = | |||
4516 | IsCI ? Islands->Relocations : Relocations; | |||
4517 | if (BC.MIB->shouldRecordCodeRelocation(RelType)) | |||
4518 | Rels[Offset] = Relocation{Offset, Symbol, RelType, Addend, Value}; | |||
4519 | } | |||
4520 | ||||
4521 | } // namespace bolt | |||
4522 | } // namespace llvm |