File: | llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp |
Warning: | line 1025, column 10 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===// | |||
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 pass implements whole program optimization of virtual calls in cases | |||
10 | // where we know (via !type metadata) that the list of callees is fixed. This | |||
11 | // includes the following: | |||
12 | // - Single implementation devirtualization: if a virtual call has a single | |||
13 | // possible callee, replace all calls with a direct call to that callee. | |||
14 | // - Virtual constant propagation: if the virtual function's return type is an | |||
15 | // integer <=64 bits and all possible callees are readnone, for each class and | |||
16 | // each list of constant arguments: evaluate the function, store the return | |||
17 | // value alongside the virtual table, and rewrite each virtual call as a load | |||
18 | // from the virtual table. | |||
19 | // - Uniform return value optimization: if the conditions for virtual constant | |||
20 | // propagation hold and each function returns the same constant value, replace | |||
21 | // each virtual call with that constant. | |||
22 | // - Unique return value optimization for i1 return values: if the conditions | |||
23 | // for virtual constant propagation hold and a single vtable's function | |||
24 | // returns 0, or a single vtable's function returns 1, replace each virtual | |||
25 | // call with a comparison of the vptr against that vtable's address. | |||
26 | // | |||
27 | // This pass is intended to be used during the regular and thin LTO pipelines: | |||
28 | // | |||
29 | // During regular LTO, the pass determines the best optimization for each | |||
30 | // virtual call and applies the resolutions directly to virtual calls that are | |||
31 | // eligible for virtual call optimization (i.e. calls that use either of the | |||
32 | // llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics). | |||
33 | // | |||
34 | // During hybrid Regular/ThinLTO, the pass operates in two phases: | |||
35 | // - Export phase: this is run during the thin link over a single merged module | |||
36 | // that contains all vtables with !type metadata that participate in the link. | |||
37 | // The pass computes a resolution for each virtual call and stores it in the | |||
38 | // type identifier summary. | |||
39 | // - Import phase: this is run during the thin backends over the individual | |||
40 | // modules. The pass applies the resolutions previously computed during the | |||
41 | // import phase to each eligible virtual call. | |||
42 | // | |||
43 | // During ThinLTO, the pass operates in two phases: | |||
44 | // - Export phase: this is run during the thin link over the index which | |||
45 | // contains a summary of all vtables with !type metadata that participate in | |||
46 | // the link. It computes a resolution for each virtual call and stores it in | |||
47 | // the type identifier summary. Only single implementation devirtualization | |||
48 | // is supported. | |||
49 | // - Import phase: (same as with hybrid case above). | |||
50 | // | |||
51 | //===----------------------------------------------------------------------===// | |||
52 | ||||
53 | #include "llvm/Transforms/IPO/WholeProgramDevirt.h" | |||
54 | #include "llvm/ADT/ArrayRef.h" | |||
55 | #include "llvm/ADT/DenseMap.h" | |||
56 | #include "llvm/ADT/DenseMapInfo.h" | |||
57 | #include "llvm/ADT/DenseSet.h" | |||
58 | #include "llvm/ADT/MapVector.h" | |||
59 | #include "llvm/ADT/SmallVector.h" | |||
60 | #include "llvm/ADT/Triple.h" | |||
61 | #include "llvm/ADT/iterator_range.h" | |||
62 | #include "llvm/Analysis/AssumptionCache.h" | |||
63 | #include "llvm/Analysis/BasicAliasAnalysis.h" | |||
64 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |||
65 | #include "llvm/Analysis/TypeMetadataUtils.h" | |||
66 | #include "llvm/Bitcode/BitcodeReader.h" | |||
67 | #include "llvm/Bitcode/BitcodeWriter.h" | |||
68 | #include "llvm/IR/Constants.h" | |||
69 | #include "llvm/IR/DataLayout.h" | |||
70 | #include "llvm/IR/DebugLoc.h" | |||
71 | #include "llvm/IR/DerivedTypes.h" | |||
72 | #include "llvm/IR/Dominators.h" | |||
73 | #include "llvm/IR/Function.h" | |||
74 | #include "llvm/IR/GlobalAlias.h" | |||
75 | #include "llvm/IR/GlobalVariable.h" | |||
76 | #include "llvm/IR/IRBuilder.h" | |||
77 | #include "llvm/IR/InstrTypes.h" | |||
78 | #include "llvm/IR/Instruction.h" | |||
79 | #include "llvm/IR/Instructions.h" | |||
80 | #include "llvm/IR/Intrinsics.h" | |||
81 | #include "llvm/IR/LLVMContext.h" | |||
82 | #include "llvm/IR/Metadata.h" | |||
83 | #include "llvm/IR/Module.h" | |||
84 | #include "llvm/IR/ModuleSummaryIndexYAML.h" | |||
85 | #include "llvm/InitializePasses.h" | |||
86 | #include "llvm/Pass.h" | |||
87 | #include "llvm/PassRegistry.h" | |||
88 | #include "llvm/Support/Casting.h" | |||
89 | #include "llvm/Support/CommandLine.h" | |||
90 | #include "llvm/Support/Errc.h" | |||
91 | #include "llvm/Support/Error.h" | |||
92 | #include "llvm/Support/FileSystem.h" | |||
93 | #include "llvm/Support/GlobPattern.h" | |||
94 | #include "llvm/Support/MathExtras.h" | |||
95 | #include "llvm/Transforms/IPO.h" | |||
96 | #include "llvm/Transforms/IPO/FunctionAttrs.h" | |||
97 | #include "llvm/Transforms/Utils/Evaluator.h" | |||
98 | #include <algorithm> | |||
99 | #include <cstddef> | |||
100 | #include <map> | |||
101 | #include <set> | |||
102 | #include <string> | |||
103 | ||||
104 | using namespace llvm; | |||
105 | using namespace wholeprogramdevirt; | |||
106 | ||||
107 | #define DEBUG_TYPE"wholeprogramdevirt" "wholeprogramdevirt" | |||
108 | ||||
109 | static cl::opt<PassSummaryAction> ClSummaryAction( | |||
110 | "wholeprogramdevirt-summary-action", | |||
111 | cl::desc("What to do with the summary when running this pass"), | |||
112 | cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing")llvm::cl::OptionEnumValue { "none", int(PassSummaryAction::None ), "Do nothing" }, | |||
113 | clEnumValN(PassSummaryAction::Import, "import",llvm::cl::OptionEnumValue { "import", int(PassSummaryAction:: Import), "Import typeid resolutions from summary and globals" } | |||
114 | "Import typeid resolutions from summary and globals")llvm::cl::OptionEnumValue { "import", int(PassSummaryAction:: Import), "Import typeid resolutions from summary and globals" }, | |||
115 | clEnumValN(PassSummaryAction::Export, "export",llvm::cl::OptionEnumValue { "export", int(PassSummaryAction:: Export), "Export typeid resolutions to summary and globals" } | |||
116 | "Export typeid resolutions to summary and globals")llvm::cl::OptionEnumValue { "export", int(PassSummaryAction:: Export), "Export typeid resolutions to summary and globals" }), | |||
117 | cl::Hidden); | |||
118 | ||||
119 | static cl::opt<std::string> ClReadSummary( | |||
120 | "wholeprogramdevirt-read-summary", | |||
121 | cl::desc( | |||
122 | "Read summary from given bitcode or YAML file before running pass"), | |||
123 | cl::Hidden); | |||
124 | ||||
125 | static cl::opt<std::string> ClWriteSummary( | |||
126 | "wholeprogramdevirt-write-summary", | |||
127 | cl::desc("Write summary to given bitcode or YAML file after running pass. " | |||
128 | "Output file format is deduced from extension: *.bc means writing " | |||
129 | "bitcode, otherwise YAML"), | |||
130 | cl::Hidden); | |||
131 | ||||
132 | static cl::opt<unsigned> | |||
133 | ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden, | |||
134 | cl::init(10), cl::ZeroOrMore, | |||
135 | cl::desc("Maximum number of call targets per " | |||
136 | "call site to enable branch funnels")); | |||
137 | ||||
138 | static cl::opt<bool> | |||
139 | PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden, | |||
140 | cl::init(false), cl::ZeroOrMore, | |||
141 | cl::desc("Print index-based devirtualization messages")); | |||
142 | ||||
143 | /// Provide a way to force enable whole program visibility in tests. | |||
144 | /// This is needed to support legacy tests that don't contain | |||
145 | /// !vcall_visibility metadata (the mere presense of type tests | |||
146 | /// previously implied hidden visibility). | |||
147 | cl::opt<bool> | |||
148 | WholeProgramVisibility("whole-program-visibility", cl::init(false), | |||
149 | cl::Hidden, cl::ZeroOrMore, | |||
150 | cl::desc("Enable whole program visibility")); | |||
151 | ||||
152 | /// Provide a way to force disable whole program for debugging or workarounds, | |||
153 | /// when enabled via the linker. | |||
154 | cl::opt<bool> DisableWholeProgramVisibility( | |||
155 | "disable-whole-program-visibility", cl::init(false), cl::Hidden, | |||
156 | cl::ZeroOrMore, | |||
157 | cl::desc("Disable whole program visibility (overrides enabling options)")); | |||
158 | ||||
159 | /// Provide way to prevent certain function from being devirtualized | |||
160 | cl::list<std::string> | |||
161 | SkipFunctionNames("wholeprogramdevirt-skip", | |||
162 | cl::desc("Prevent function(s) from being devirtualized"), | |||
163 | cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated); | |||
164 | ||||
165 | namespace { | |||
166 | struct PatternList { | |||
167 | std::vector<GlobPattern> Patterns; | |||
168 | template <class T> void init(const T &StringList) { | |||
169 | for (const auto &S : StringList) | |||
170 | if (Expected<GlobPattern> Pat = GlobPattern::create(S)) | |||
171 | Patterns.push_back(std::move(*Pat)); | |||
172 | } | |||
173 | bool match(StringRef S) { | |||
174 | for (const GlobPattern &P : Patterns) | |||
175 | if (P.match(S)) | |||
176 | return true; | |||
177 | return false; | |||
178 | } | |||
179 | }; | |||
180 | } // namespace | |||
181 | ||||
182 | // Find the minimum offset that we may store a value of size Size bits at. If | |||
183 | // IsAfter is set, look for an offset before the object, otherwise look for an | |||
184 | // offset after the object. | |||
185 | uint64_t | |||
186 | wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets, | |||
187 | bool IsAfter, uint64_t Size) { | |||
188 | // Find a minimum offset taking into account only vtable sizes. | |||
189 | uint64_t MinByte = 0; | |||
190 | for (const VirtualCallTarget &Target : Targets) { | |||
191 | if (IsAfter) | |||
192 | MinByte = std::max(MinByte, Target.minAfterBytes()); | |||
193 | else | |||
194 | MinByte = std::max(MinByte, Target.minBeforeBytes()); | |||
195 | } | |||
196 | ||||
197 | // Build a vector of arrays of bytes covering, for each target, a slice of the | |||
198 | // used region (see AccumBitVector::BytesUsed in | |||
199 | // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively, | |||
200 | // this aligns the used regions to start at MinByte. | |||
201 | // | |||
202 | // In this example, A, B and C are vtables, # is a byte already allocated for | |||
203 | // a virtual function pointer, AAAA... (etc.) are the used regions for the | |||
204 | // vtables and Offset(X) is the value computed for the Offset variable below | |||
205 | // for X. | |||
206 | // | |||
207 | // Offset(A) | |||
208 | // | | | |||
209 | // |MinByte | |||
210 | // A: ################AAAAAAAA|AAAAAAAA | |||
211 | // B: ########BBBBBBBBBBBBBBBB|BBBB | |||
212 | // C: ########################|CCCCCCCCCCCCCCCC | |||
213 | // | Offset(B) | | |||
214 | // | |||
215 | // This code produces the slices of A, B and C that appear after the divider | |||
216 | // at MinByte. | |||
217 | std::vector<ArrayRef<uint8_t>> Used; | |||
218 | for (const VirtualCallTarget &Target : Targets) { | |||
219 | ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed | |||
220 | : Target.TM->Bits->Before.BytesUsed; | |||
221 | uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes() | |||
222 | : MinByte - Target.minBeforeBytes(); | |||
223 | ||||
224 | // Disregard used regions that are smaller than Offset. These are | |||
225 | // effectively all-free regions that do not need to be checked. | |||
226 | if (VTUsed.size() > Offset) | |||
227 | Used.push_back(VTUsed.slice(Offset)); | |||
228 | } | |||
229 | ||||
230 | if (Size == 1) { | |||
231 | // Find a free bit in each member of Used. | |||
232 | for (unsigned I = 0;; ++I) { | |||
233 | uint8_t BitsUsed = 0; | |||
234 | for (auto &&B : Used) | |||
235 | if (I < B.size()) | |||
236 | BitsUsed |= B[I]; | |||
237 | if (BitsUsed != 0xff) | |||
238 | return (MinByte + I) * 8 + | |||
239 | countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined); | |||
240 | } | |||
241 | } else { | |||
242 | // Find a free (Size/8) byte region in each member of Used. | |||
243 | // FIXME: see if alignment helps. | |||
244 | for (unsigned I = 0;; ++I) { | |||
245 | for (auto &&B : Used) { | |||
246 | unsigned Byte = 0; | |||
247 | while ((I + Byte) < B.size() && Byte < (Size / 8)) { | |||
248 | if (B[I + Byte]) | |||
249 | goto NextI; | |||
250 | ++Byte; | |||
251 | } | |||
252 | } | |||
253 | return (MinByte + I) * 8; | |||
254 | NextI:; | |||
255 | } | |||
256 | } | |||
257 | } | |||
258 | ||||
259 | void wholeprogramdevirt::setBeforeReturnValues( | |||
260 | MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore, | |||
261 | unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { | |||
262 | if (BitWidth == 1) | |||
263 | OffsetByte = -(AllocBefore / 8 + 1); | |||
264 | else | |||
265 | OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8); | |||
266 | OffsetBit = AllocBefore % 8; | |||
267 | ||||
268 | for (VirtualCallTarget &Target : Targets) { | |||
269 | if (BitWidth == 1) | |||
270 | Target.setBeforeBit(AllocBefore); | |||
271 | else | |||
272 | Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8); | |||
273 | } | |||
274 | } | |||
275 | ||||
276 | void wholeprogramdevirt::setAfterReturnValues( | |||
277 | MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter, | |||
278 | unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { | |||
279 | if (BitWidth == 1) | |||
280 | OffsetByte = AllocAfter / 8; | |||
281 | else | |||
282 | OffsetByte = (AllocAfter + 7) / 8; | |||
283 | OffsetBit = AllocAfter % 8; | |||
284 | ||||
285 | for (VirtualCallTarget &Target : Targets) { | |||
286 | if (BitWidth == 1) | |||
287 | Target.setAfterBit(AllocAfter); | |||
288 | else | |||
289 | Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8); | |||
290 | } | |||
291 | } | |||
292 | ||||
293 | VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM) | |||
294 | : Fn(Fn), TM(TM), | |||
295 | IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {} | |||
296 | ||||
297 | namespace { | |||
298 | ||||
299 | // A slot in a set of virtual tables. The TypeID identifies the set of virtual | |||
300 | // tables, and the ByteOffset is the offset in bytes from the address point to | |||
301 | // the virtual function pointer. | |||
302 | struct VTableSlot { | |||
303 | Metadata *TypeID; | |||
304 | uint64_t ByteOffset; | |||
305 | }; | |||
306 | ||||
307 | } // end anonymous namespace | |||
308 | ||||
309 | namespace llvm { | |||
310 | ||||
311 | template <> struct DenseMapInfo<VTableSlot> { | |||
312 | static VTableSlot getEmptyKey() { | |||
313 | return {DenseMapInfo<Metadata *>::getEmptyKey(), | |||
314 | DenseMapInfo<uint64_t>::getEmptyKey()}; | |||
315 | } | |||
316 | static VTableSlot getTombstoneKey() { | |||
317 | return {DenseMapInfo<Metadata *>::getTombstoneKey(), | |||
318 | DenseMapInfo<uint64_t>::getTombstoneKey()}; | |||
319 | } | |||
320 | static unsigned getHashValue(const VTableSlot &I) { | |||
321 | return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^ | |||
322 | DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset); | |||
323 | } | |||
324 | static bool isEqual(const VTableSlot &LHS, | |||
325 | const VTableSlot &RHS) { | |||
326 | return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset; | |||
327 | } | |||
328 | }; | |||
329 | ||||
330 | template <> struct DenseMapInfo<VTableSlotSummary> { | |||
331 | static VTableSlotSummary getEmptyKey() { | |||
332 | return {DenseMapInfo<StringRef>::getEmptyKey(), | |||
333 | DenseMapInfo<uint64_t>::getEmptyKey()}; | |||
334 | } | |||
335 | static VTableSlotSummary getTombstoneKey() { | |||
336 | return {DenseMapInfo<StringRef>::getTombstoneKey(), | |||
337 | DenseMapInfo<uint64_t>::getTombstoneKey()}; | |||
338 | } | |||
339 | static unsigned getHashValue(const VTableSlotSummary &I) { | |||
340 | return DenseMapInfo<StringRef>::getHashValue(I.TypeID) ^ | |||
341 | DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset); | |||
342 | } | |||
343 | static bool isEqual(const VTableSlotSummary &LHS, | |||
344 | const VTableSlotSummary &RHS) { | |||
345 | return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset; | |||
346 | } | |||
347 | }; | |||
348 | ||||
349 | } // end namespace llvm | |||
350 | ||||
351 | namespace { | |||
352 | ||||
353 | // A virtual call site. VTable is the loaded virtual table pointer, and CS is | |||
354 | // the indirect virtual call. | |||
355 | struct VirtualCallSite { | |||
356 | Value *VTable = nullptr; | |||
357 | CallBase &CB; | |||
358 | ||||
359 | // If non-null, this field points to the associated unsafe use count stored in | |||
360 | // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description | |||
361 | // of that field for details. | |||
362 | unsigned *NumUnsafeUses = nullptr; | |||
363 | ||||
364 | void | |||
365 | emitRemark(const StringRef OptName, const StringRef TargetName, | |||
366 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter) { | |||
367 | Function *F = CB.getCaller(); | |||
368 | DebugLoc DLoc = CB.getDebugLoc(); | |||
369 | BasicBlock *Block = CB.getParent(); | |||
370 | ||||
371 | using namespace ore; | |||
372 | OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", OptName, DLoc, Block) | |||
373 | << NV("Optimization", OptName) | |||
374 | << ": devirtualized a call to " | |||
375 | << NV("FunctionName", TargetName)); | |||
376 | } | |||
377 | ||||
378 | void replaceAndErase( | |||
379 | const StringRef OptName, const StringRef TargetName, bool RemarksEnabled, | |||
380 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter, | |||
381 | Value *New) { | |||
382 | if (RemarksEnabled) | |||
383 | emitRemark(OptName, TargetName, OREGetter); | |||
384 | CB.replaceAllUsesWith(New); | |||
385 | if (auto *II = dyn_cast<InvokeInst>(&CB)) { | |||
386 | BranchInst::Create(II->getNormalDest(), &CB); | |||
387 | II->getUnwindDest()->removePredecessor(II->getParent()); | |||
388 | } | |||
389 | CB.eraseFromParent(); | |||
390 | // This use is no longer unsafe. | |||
391 | if (NumUnsafeUses) | |||
392 | --*NumUnsafeUses; | |||
393 | } | |||
394 | }; | |||
395 | ||||
396 | // Call site information collected for a specific VTableSlot and possibly a list | |||
397 | // of constant integer arguments. The grouping by arguments is handled by the | |||
398 | // VTableSlotInfo class. | |||
399 | struct CallSiteInfo { | |||
400 | /// The set of call sites for this slot. Used during regular LTO and the | |||
401 | /// import phase of ThinLTO (as well as the export phase of ThinLTO for any | |||
402 | /// call sites that appear in the merged module itself); in each of these | |||
403 | /// cases we are directly operating on the call sites at the IR level. | |||
404 | std::vector<VirtualCallSite> CallSites; | |||
405 | ||||
406 | /// Whether all call sites represented by this CallSiteInfo, including those | |||
407 | /// in summaries, have been devirtualized. This starts off as true because a | |||
408 | /// default constructed CallSiteInfo represents no call sites. | |||
409 | bool AllCallSitesDevirted = true; | |||
410 | ||||
411 | // These fields are used during the export phase of ThinLTO and reflect | |||
412 | // information collected from function summaries. | |||
413 | ||||
414 | /// Whether any function summary contains an llvm.assume(llvm.type.test) for | |||
415 | /// this slot. | |||
416 | bool SummaryHasTypeTestAssumeUsers = false; | |||
417 | ||||
418 | /// CFI-specific: a vector containing the list of function summaries that use | |||
419 | /// the llvm.type.checked.load intrinsic and therefore will require | |||
420 | /// resolutions for llvm.type.test in order to implement CFI checks if | |||
421 | /// devirtualization was unsuccessful. If devirtualization was successful, the | |||
422 | /// pass will clear this vector by calling markDevirt(). If at the end of the | |||
423 | /// pass the vector is non-empty, we will need to add a use of llvm.type.test | |||
424 | /// to each of the function summaries in the vector. | |||
425 | std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers; | |||
426 | std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers; | |||
427 | ||||
428 | bool isExported() const { | |||
429 | return SummaryHasTypeTestAssumeUsers || | |||
430 | !SummaryTypeCheckedLoadUsers.empty(); | |||
431 | } | |||
432 | ||||
433 | void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) { | |||
434 | SummaryTypeCheckedLoadUsers.push_back(FS); | |||
435 | AllCallSitesDevirted = false; | |||
436 | } | |||
437 | ||||
438 | void addSummaryTypeTestAssumeUser(FunctionSummary *FS) { | |||
439 | SummaryTypeTestAssumeUsers.push_back(FS); | |||
440 | SummaryHasTypeTestAssumeUsers = true; | |||
441 | AllCallSitesDevirted = false; | |||
442 | } | |||
443 | ||||
444 | void markDevirt() { | |||
445 | AllCallSitesDevirted = true; | |||
446 | ||||
447 | // As explained in the comment for SummaryTypeCheckedLoadUsers. | |||
448 | SummaryTypeCheckedLoadUsers.clear(); | |||
449 | } | |||
450 | }; | |||
451 | ||||
452 | // Call site information collected for a specific VTableSlot. | |||
453 | struct VTableSlotInfo { | |||
454 | // The set of call sites which do not have all constant integer arguments | |||
455 | // (excluding "this"). | |||
456 | CallSiteInfo CSInfo; | |||
457 | ||||
458 | // The set of call sites with all constant integer arguments (excluding | |||
459 | // "this"), grouped by argument list. | |||
460 | std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo; | |||
461 | ||||
462 | void addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses); | |||
463 | ||||
464 | private: | |||
465 | CallSiteInfo &findCallSiteInfo(CallBase &CB); | |||
466 | }; | |||
467 | ||||
468 | CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) { | |||
469 | std::vector<uint64_t> Args; | |||
470 | auto *CBType = dyn_cast<IntegerType>(CB.getType()); | |||
471 | if (!CBType || CBType->getBitWidth() > 64 || CB.arg_empty()) | |||
472 | return CSInfo; | |||
473 | for (auto &&Arg : drop_begin(CB.args())) { | |||
474 | auto *CI = dyn_cast<ConstantInt>(Arg); | |||
475 | if (!CI || CI->getBitWidth() > 64) | |||
476 | return CSInfo; | |||
477 | Args.push_back(CI->getZExtValue()); | |||
478 | } | |||
479 | return ConstCSInfo[Args]; | |||
480 | } | |||
481 | ||||
482 | void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB, | |||
483 | unsigned *NumUnsafeUses) { | |||
484 | auto &CSI = findCallSiteInfo(CB); | |||
485 | CSI.AllCallSitesDevirted = false; | |||
486 | CSI.CallSites.push_back({VTable, CB, NumUnsafeUses}); | |||
487 | } | |||
488 | ||||
489 | struct DevirtModule { | |||
490 | Module &M; | |||
491 | function_ref<AAResults &(Function &)> AARGetter; | |||
492 | function_ref<DominatorTree &(Function &)> LookupDomTree; | |||
493 | ||||
494 | ModuleSummaryIndex *ExportSummary; | |||
495 | const ModuleSummaryIndex *ImportSummary; | |||
496 | ||||
497 | IntegerType *Int8Ty; | |||
498 | PointerType *Int8PtrTy; | |||
499 | IntegerType *Int32Ty; | |||
500 | IntegerType *Int64Ty; | |||
501 | IntegerType *IntPtrTy; | |||
502 | /// Sizeless array type, used for imported vtables. This provides a signal | |||
503 | /// to analyzers that these imports may alias, as they do for example | |||
504 | /// when multiple unique return values occur in the same vtable. | |||
505 | ArrayType *Int8Arr0Ty; | |||
506 | ||||
507 | bool RemarksEnabled; | |||
508 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter; | |||
509 | ||||
510 | MapVector<VTableSlot, VTableSlotInfo> CallSlots; | |||
511 | ||||
512 | // This map keeps track of the number of "unsafe" uses of a loaded function | |||
513 | // pointer. The key is the associated llvm.type.test intrinsic call generated | |||
514 | // by this pass. An unsafe use is one that calls the loaded function pointer | |||
515 | // directly. Every time we eliminate an unsafe use (for example, by | |||
516 | // devirtualizing it or by applying virtual constant propagation), we | |||
517 | // decrement the value stored in this map. If a value reaches zero, we can | |||
518 | // eliminate the type check by RAUWing the associated llvm.type.test call with | |||
519 | // true. | |||
520 | std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest; | |||
521 | PatternList FunctionsToSkip; | |||
522 | ||||
523 | DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter, | |||
524 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter, | |||
525 | function_ref<DominatorTree &(Function &)> LookupDomTree, | |||
526 | ModuleSummaryIndex *ExportSummary, | |||
527 | const ModuleSummaryIndex *ImportSummary) | |||
528 | : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree), | |||
529 | ExportSummary(ExportSummary), ImportSummary(ImportSummary), | |||
530 | Int8Ty(Type::getInt8Ty(M.getContext())), | |||
531 | Int8PtrTy(Type::getInt8PtrTy(M.getContext())), | |||
532 | Int32Ty(Type::getInt32Ty(M.getContext())), | |||
533 | Int64Ty(Type::getInt64Ty(M.getContext())), | |||
534 | IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)), | |||
535 | Int8Arr0Ty(ArrayType::get(Type::getInt8Ty(M.getContext()), 0)), | |||
536 | RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) { | |||
537 | assert(!(ExportSummary && ImportSummary))((!(ExportSummary && ImportSummary)) ? static_cast< void> (0) : __assert_fail ("!(ExportSummary && ImportSummary)" , "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 537, __PRETTY_FUNCTION__)); | |||
538 | FunctionsToSkip.init(SkipFunctionNames); | |||
539 | } | |||
540 | ||||
541 | bool areRemarksEnabled(); | |||
542 | ||||
543 | void | |||
544 | scanTypeTestUsers(Function *TypeTestFunc, | |||
545 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap); | |||
546 | void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc); | |||
547 | ||||
548 | void buildTypeIdentifierMap( | |||
549 | std::vector<VTableBits> &Bits, | |||
550 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap); | |||
551 | bool | |||
552 | tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot, | |||
553 | const std::set<TypeMemberInfo> &TypeMemberInfos, | |||
554 | uint64_t ByteOffset); | |||
555 | ||||
556 | void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn, | |||
557 | bool &IsExported); | |||
558 | bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary, | |||
559 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
560 | VTableSlotInfo &SlotInfo, | |||
561 | WholeProgramDevirtResolution *Res); | |||
562 | ||||
563 | void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT, | |||
564 | bool &IsExported); | |||
565 | void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
566 | VTableSlotInfo &SlotInfo, | |||
567 | WholeProgramDevirtResolution *Res, VTableSlot Slot); | |||
568 | ||||
569 | bool tryEvaluateFunctionsWithArgs( | |||
570 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
571 | ArrayRef<uint64_t> Args); | |||
572 | ||||
573 | void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, | |||
574 | uint64_t TheRetVal); | |||
575 | bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
576 | CallSiteInfo &CSInfo, | |||
577 | WholeProgramDevirtResolution::ByArg *Res); | |||
578 | ||||
579 | // Returns the global symbol name that is used to export information about the | |||
580 | // given vtable slot and list of arguments. | |||
581 | std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
582 | StringRef Name); | |||
583 | ||||
584 | bool shouldExportConstantsAsAbsoluteSymbols(); | |||
585 | ||||
586 | // This function is called during the export phase to create a symbol | |||
587 | // definition containing information about the given vtable slot and list of | |||
588 | // arguments. | |||
589 | void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, | |||
590 | Constant *C); | |||
591 | void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, | |||
592 | uint32_t Const, uint32_t &Storage); | |||
593 | ||||
594 | // This function is called during the import phase to create a reference to | |||
595 | // the symbol definition created during the export phase. | |||
596 | Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
597 | StringRef Name); | |||
598 | Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
599 | StringRef Name, IntegerType *IntTy, | |||
600 | uint32_t Storage); | |||
601 | ||||
602 | Constant *getMemberAddr(const TypeMemberInfo *M); | |||
603 | ||||
604 | void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne, | |||
605 | Constant *UniqueMemberAddr); | |||
606 | bool tryUniqueRetValOpt(unsigned BitWidth, | |||
607 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
608 | CallSiteInfo &CSInfo, | |||
609 | WholeProgramDevirtResolution::ByArg *Res, | |||
610 | VTableSlot Slot, ArrayRef<uint64_t> Args); | |||
611 | ||||
612 | void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName, | |||
613 | Constant *Byte, Constant *Bit); | |||
614 | bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
615 | VTableSlotInfo &SlotInfo, | |||
616 | WholeProgramDevirtResolution *Res, VTableSlot Slot); | |||
617 | ||||
618 | void rebuildGlobal(VTableBits &B); | |||
619 | ||||
620 | // Apply the summary resolution for Slot to all virtual calls in SlotInfo. | |||
621 | void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo); | |||
622 | ||||
623 | // If we were able to eliminate all unsafe uses for a type checked load, | |||
624 | // eliminate the associated type tests by replacing them with true. | |||
625 | void removeRedundantTypeTests(); | |||
626 | ||||
627 | bool run(); | |||
628 | ||||
629 | // Lower the module using the action and summary passed as command line | |||
630 | // arguments. For testing purposes only. | |||
631 | static bool | |||
632 | runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter, | |||
633 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter, | |||
634 | function_ref<DominatorTree &(Function &)> LookupDomTree); | |||
635 | }; | |||
636 | ||||
637 | struct DevirtIndex { | |||
638 | ModuleSummaryIndex &ExportSummary; | |||
639 | // The set in which to record GUIDs exported from their module by | |||
640 | // devirtualization, used by client to ensure they are not internalized. | |||
641 | std::set<GlobalValue::GUID> &ExportedGUIDs; | |||
642 | // A map in which to record the information necessary to locate the WPD | |||
643 | // resolution for local targets in case they are exported by cross module | |||
644 | // importing. | |||
645 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap; | |||
646 | ||||
647 | MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots; | |||
648 | ||||
649 | PatternList FunctionsToSkip; | |||
650 | ||||
651 | DevirtIndex( | |||
652 | ModuleSummaryIndex &ExportSummary, | |||
653 | std::set<GlobalValue::GUID> &ExportedGUIDs, | |||
654 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) | |||
655 | : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs), | |||
656 | LocalWPDTargetsMap(LocalWPDTargetsMap) { | |||
657 | FunctionsToSkip.init(SkipFunctionNames); | |||
658 | } | |||
659 | ||||
660 | bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot, | |||
661 | const TypeIdCompatibleVtableInfo TIdInfo, | |||
662 | uint64_t ByteOffset); | |||
663 | ||||
664 | bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot, | |||
665 | VTableSlotSummary &SlotSummary, | |||
666 | VTableSlotInfo &SlotInfo, | |||
667 | WholeProgramDevirtResolution *Res, | |||
668 | std::set<ValueInfo> &DevirtTargets); | |||
669 | ||||
670 | void run(); | |||
671 | }; | |||
672 | ||||
673 | struct WholeProgramDevirt : public ModulePass { | |||
674 | static char ID; | |||
675 | ||||
676 | bool UseCommandLine = false; | |||
677 | ||||
678 | ModuleSummaryIndex *ExportSummary = nullptr; | |||
679 | const ModuleSummaryIndex *ImportSummary = nullptr; | |||
680 | ||||
681 | WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) { | |||
682 | initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry()); | |||
683 | } | |||
684 | ||||
685 | WholeProgramDevirt(ModuleSummaryIndex *ExportSummary, | |||
686 | const ModuleSummaryIndex *ImportSummary) | |||
687 | : ModulePass(ID), ExportSummary(ExportSummary), | |||
688 | ImportSummary(ImportSummary) { | |||
689 | initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry()); | |||
690 | } | |||
691 | ||||
692 | bool runOnModule(Module &M) override { | |||
693 | if (skipModule(M)) | |||
694 | return false; | |||
695 | ||||
696 | // In the new pass manager, we can request the optimization | |||
697 | // remark emitter pass on a per-function-basis, which the | |||
698 | // OREGetter will do for us. | |||
699 | // In the old pass manager, this is harder, so we just build | |||
700 | // an optimization remark emitter on the fly, when we need it. | |||
701 | std::unique_ptr<OptimizationRemarkEmitter> ORE; | |||
702 | auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & { | |||
703 | ORE = std::make_unique<OptimizationRemarkEmitter>(F); | |||
704 | return *ORE; | |||
705 | }; | |||
706 | ||||
707 | auto LookupDomTree = [this](Function &F) -> DominatorTree & { | |||
708 | return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); | |||
709 | }; | |||
710 | ||||
711 | if (UseCommandLine) | |||
712 | return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter, | |||
713 | LookupDomTree); | |||
714 | ||||
715 | return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree, | |||
716 | ExportSummary, ImportSummary) | |||
717 | .run(); | |||
718 | } | |||
719 | ||||
720 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
721 | AU.addRequired<AssumptionCacheTracker>(); | |||
722 | AU.addRequired<TargetLibraryInfoWrapperPass>(); | |||
723 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
724 | } | |||
725 | }; | |||
726 | ||||
727 | } // end anonymous namespace | |||
728 | ||||
729 | INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",static void *initializeWholeProgramDevirtPassOnce(PassRegistry &Registry) { | |||
730 | "Whole program devirtualization", false, false)static void *initializeWholeProgramDevirtPassOnce(PassRegistry &Registry) { | |||
731 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
732 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry); | |||
733 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
734 | INITIALIZE_PASS_END(WholeProgramDevirt, "wholeprogramdevirt",PassInfo *PI = new PassInfo( "Whole program devirtualization" , "wholeprogramdevirt", &WholeProgramDevirt::ID, PassInfo ::NormalCtor_t(callDefaultCtor<WholeProgramDevirt>), false , false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeWholeProgramDevirtPassFlag; void llvm ::initializeWholeProgramDevirtPass(PassRegistry &Registry ) { llvm::call_once(InitializeWholeProgramDevirtPassFlag, initializeWholeProgramDevirtPassOnce , std::ref(Registry)); } | |||
735 | "Whole program devirtualization", false, false)PassInfo *PI = new PassInfo( "Whole program devirtualization" , "wholeprogramdevirt", &WholeProgramDevirt::ID, PassInfo ::NormalCtor_t(callDefaultCtor<WholeProgramDevirt>), false , false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeWholeProgramDevirtPassFlag; void llvm ::initializeWholeProgramDevirtPass(PassRegistry &Registry ) { llvm::call_once(InitializeWholeProgramDevirtPassFlag, initializeWholeProgramDevirtPassOnce , std::ref(Registry)); } | |||
736 | char WholeProgramDevirt::ID = 0; | |||
737 | ||||
738 | ModulePass * | |||
739 | llvm::createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, | |||
740 | const ModuleSummaryIndex *ImportSummary) { | |||
741 | return new WholeProgramDevirt(ExportSummary, ImportSummary); | |||
742 | } | |||
743 | ||||
744 | PreservedAnalyses WholeProgramDevirtPass::run(Module &M, | |||
745 | ModuleAnalysisManager &AM) { | |||
746 | auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); | |||
747 | auto AARGetter = [&](Function &F) -> AAResults & { | |||
748 | return FAM.getResult<AAManager>(F); | |||
749 | }; | |||
750 | auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & { | |||
751 | return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F); | |||
752 | }; | |||
753 | auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & { | |||
754 | return FAM.getResult<DominatorTreeAnalysis>(F); | |||
755 | }; | |||
756 | if (UseCommandLine) { | |||
757 | if (DevirtModule::runForTesting(M, AARGetter, OREGetter, LookupDomTree)) | |||
758 | return PreservedAnalyses::all(); | |||
759 | return PreservedAnalyses::none(); | |||
760 | } | |||
761 | if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary, | |||
762 | ImportSummary) | |||
763 | .run()) | |||
764 | return PreservedAnalyses::all(); | |||
765 | return PreservedAnalyses::none(); | |||
766 | } | |||
767 | ||||
768 | // Enable whole program visibility if enabled by client (e.g. linker) or | |||
769 | // internal option, and not force disabled. | |||
770 | static bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) { | |||
771 | return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) && | |||
772 | !DisableWholeProgramVisibility; | |||
773 | } | |||
774 | ||||
775 | namespace llvm { | |||
776 | ||||
777 | /// If whole program visibility asserted, then upgrade all public vcall | |||
778 | /// visibility metadata on vtable definitions to linkage unit visibility in | |||
779 | /// Module IR (for regular or hybrid LTO). | |||
780 | void updateVCallVisibilityInModule( | |||
781 | Module &M, bool WholeProgramVisibilityEnabledInLTO, | |||
782 | const DenseSet<GlobalValue::GUID> &DynamicExportSymbols) { | |||
783 | if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) | |||
784 | return; | |||
785 | for (GlobalVariable &GV : M.globals()) | |||
786 | // Add linkage unit visibility to any variable with type metadata, which are | |||
787 | // the vtable definitions. We won't have an existing vcall_visibility | |||
788 | // metadata on vtable definitions with public visibility. | |||
789 | if (GV.hasMetadata(LLVMContext::MD_type) && | |||
790 | GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic && | |||
791 | // Don't upgrade the visibility for symbols exported to the dynamic | |||
792 | // linker, as we have no information on their eventual use. | |||
793 | !DynamicExportSymbols.count(GV.getGUID())) | |||
794 | GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit); | |||
795 | } | |||
796 | ||||
797 | /// If whole program visibility asserted, then upgrade all public vcall | |||
798 | /// visibility metadata on vtable definition summaries to linkage unit | |||
799 | /// visibility in Module summary index (for ThinLTO). | |||
800 | void updateVCallVisibilityInIndex( | |||
801 | ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, | |||
802 | const DenseSet<GlobalValue::GUID> &DynamicExportSymbols) { | |||
803 | if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) | |||
804 | return; | |||
805 | for (auto &P : Index) { | |||
806 | for (auto &S : P.second.SummaryList) { | |||
807 | auto *GVar = dyn_cast<GlobalVarSummary>(S.get()); | |||
808 | if (!GVar || GVar->vTableFuncs().empty() || | |||
809 | GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic || | |||
810 | // Don't upgrade the visibility for symbols exported to the dynamic | |||
811 | // linker, as we have no information on their eventual use. | |||
812 | DynamicExportSymbols.count(P.first)) | |||
813 | continue; | |||
814 | GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit); | |||
815 | } | |||
816 | } | |||
817 | } | |||
818 | ||||
819 | void runWholeProgramDevirtOnIndex( | |||
820 | ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs, | |||
821 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) { | |||
822 | DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run(); | |||
| ||||
823 | } | |||
824 | ||||
825 | void updateIndexWPDForExports( | |||
826 | ModuleSummaryIndex &Summary, | |||
827 | function_ref<bool(StringRef, ValueInfo)> isExported, | |||
828 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) { | |||
829 | for (auto &T : LocalWPDTargetsMap) { | |||
830 | auto &VI = T.first; | |||
831 | // This was enforced earlier during trySingleImplDevirt. | |||
832 | assert(VI.getSummaryList().size() == 1 &&((VI.getSummaryList().size() == 1 && "Devirt of local target has more than one copy" ) ? static_cast<void> (0) : __assert_fail ("VI.getSummaryList().size() == 1 && \"Devirt of local target has more than one copy\"" , "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 833, __PRETTY_FUNCTION__)) | |||
833 | "Devirt of local target has more than one copy")((VI.getSummaryList().size() == 1 && "Devirt of local target has more than one copy" ) ? static_cast<void> (0) : __assert_fail ("VI.getSummaryList().size() == 1 && \"Devirt of local target has more than one copy\"" , "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 833, __PRETTY_FUNCTION__)); | |||
834 | auto &S = VI.getSummaryList()[0]; | |||
835 | if (!isExported(S->modulePath(), VI)) | |||
836 | continue; | |||
837 | ||||
838 | // It's been exported by a cross module import. | |||
839 | for (auto &SlotSummary : T.second) { | |||
840 | auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID); | |||
841 | assert(TIdSum)((TIdSum) ? static_cast<void> (0) : __assert_fail ("TIdSum" , "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 841, __PRETTY_FUNCTION__)); | |||
842 | auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset); | |||
843 | assert(WPDRes != TIdSum->WPDRes.end())((WPDRes != TIdSum->WPDRes.end()) ? static_cast<void> (0) : __assert_fail ("WPDRes != TIdSum->WPDRes.end()", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 843, __PRETTY_FUNCTION__)); | |||
844 | WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal( | |||
845 | WPDRes->second.SingleImplName, | |||
846 | Summary.getModuleHash(S->modulePath())); | |||
847 | } | |||
848 | } | |||
849 | } | |||
850 | ||||
851 | } // end namespace llvm | |||
852 | ||||
853 | static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) { | |||
854 | // Check that summary index contains regular LTO module when performing | |||
855 | // export to prevent occasional use of index from pure ThinLTO compilation | |||
856 | // (-fno-split-lto-module). This kind of summary index is passed to | |||
857 | // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting. | |||
858 | const auto &ModPaths = Summary->modulePaths(); | |||
859 | if (ClSummaryAction != PassSummaryAction::Import && | |||
860 | ModPaths.find(ModuleSummaryIndex::getRegularLTOModuleName()) == | |||
861 | ModPaths.end()) | |||
862 | return createStringError( | |||
863 | errc::invalid_argument, | |||
864 | "combined summary should contain Regular LTO module"); | |||
865 | return ErrorSuccess(); | |||
866 | } | |||
867 | ||||
868 | bool DevirtModule::runForTesting( | |||
869 | Module &M, function_ref<AAResults &(Function &)> AARGetter, | |||
870 | function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter, | |||
871 | function_ref<DominatorTree &(Function &)> LookupDomTree) { | |||
872 | std::unique_ptr<ModuleSummaryIndex> Summary = | |||
873 | std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false); | |||
874 | ||||
875 | // Handle the command-line summary arguments. This code is for testing | |||
876 | // purposes only, so we handle errors directly. | |||
877 | if (!ClReadSummary.empty()) { | |||
878 | ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary + | |||
879 | ": "); | |||
880 | auto ReadSummaryFile = | |||
881 | ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary))); | |||
882 | if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr = | |||
883 | getModuleSummaryIndex(*ReadSummaryFile)) { | |||
884 | Summary = std::move(*SummaryOrErr); | |||
885 | ExitOnErr(checkCombinedSummaryForTesting(Summary.get())); | |||
886 | } else { | |||
887 | // Try YAML if we've failed with bitcode. | |||
888 | consumeError(SummaryOrErr.takeError()); | |||
889 | yaml::Input In(ReadSummaryFile->getBuffer()); | |||
890 | In >> *Summary; | |||
891 | ExitOnErr(errorCodeToError(In.error())); | |||
892 | } | |||
893 | } | |||
894 | ||||
895 | bool Changed = | |||
896 | DevirtModule(M, AARGetter, OREGetter, LookupDomTree, | |||
897 | ClSummaryAction == PassSummaryAction::Export ? Summary.get() | |||
898 | : nullptr, | |||
899 | ClSummaryAction == PassSummaryAction::Import ? Summary.get() | |||
900 | : nullptr) | |||
901 | .run(); | |||
902 | ||||
903 | if (!ClWriteSummary.empty()) { | |||
904 | ExitOnError ExitOnErr( | |||
905 | "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": "); | |||
906 | std::error_code EC; | |||
907 | if (StringRef(ClWriteSummary).endswith(".bc")) { | |||
908 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_None); | |||
909 | ExitOnErr(errorCodeToError(EC)); | |||
910 | WriteIndexToFile(*Summary, OS); | |||
911 | } else { | |||
912 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_Text); | |||
913 | ExitOnErr(errorCodeToError(EC)); | |||
914 | yaml::Output Out(OS); | |||
915 | Out << *Summary; | |||
916 | } | |||
917 | } | |||
918 | ||||
919 | return Changed; | |||
920 | } | |||
921 | ||||
922 | void DevirtModule::buildTypeIdentifierMap( | |||
923 | std::vector<VTableBits> &Bits, | |||
924 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { | |||
925 | DenseMap<GlobalVariable *, VTableBits *> GVToBits; | |||
926 | Bits.reserve(M.getGlobalList().size()); | |||
927 | SmallVector<MDNode *, 2> Types; | |||
928 | for (GlobalVariable &GV : M.globals()) { | |||
929 | Types.clear(); | |||
930 | GV.getMetadata(LLVMContext::MD_type, Types); | |||
931 | if (GV.isDeclaration() || Types.empty()) | |||
932 | continue; | |||
933 | ||||
934 | VTableBits *&BitsPtr = GVToBits[&GV]; | |||
935 | if (!BitsPtr) { | |||
936 | Bits.emplace_back(); | |||
937 | Bits.back().GV = &GV; | |||
938 | Bits.back().ObjectSize = | |||
939 | M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType()); | |||
940 | BitsPtr = &Bits.back(); | |||
941 | } | |||
942 | ||||
943 | for (MDNode *Type : Types) { | |||
944 | auto TypeID = Type->getOperand(1).get(); | |||
945 | ||||
946 | uint64_t Offset = | |||
947 | cast<ConstantInt>( | |||
948 | cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) | |||
949 | ->getZExtValue(); | |||
950 | ||||
951 | TypeIdMap[TypeID].insert({BitsPtr, Offset}); | |||
952 | } | |||
953 | } | |||
954 | } | |||
955 | ||||
956 | bool DevirtModule::tryFindVirtualCallTargets( | |||
957 | std::vector<VirtualCallTarget> &TargetsForSlot, | |||
958 | const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) { | |||
959 | for (const TypeMemberInfo &TM : TypeMemberInfos) { | |||
960 | if (!TM.Bits->GV->isConstant()) | |||
961 | return false; | |||
962 | ||||
963 | // We cannot perform whole program devirtualization analysis on a vtable | |||
964 | // with public LTO visibility. | |||
965 | if (TM.Bits->GV->getVCallVisibility() == | |||
966 | GlobalObject::VCallVisibilityPublic) | |||
967 | return false; | |||
968 | ||||
969 | Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(), | |||
970 | TM.Offset + ByteOffset, M); | |||
971 | if (!Ptr) | |||
972 | return false; | |||
973 | ||||
974 | auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts()); | |||
975 | if (!Fn) | |||
976 | return false; | |||
977 | ||||
978 | if (FunctionsToSkip.match(Fn->getName())) | |||
979 | return false; | |||
980 | ||||
981 | // We can disregard __cxa_pure_virtual as a possible call target, as | |||
982 | // calls to pure virtuals are UB. | |||
983 | if (Fn->getName() == "__cxa_pure_virtual") | |||
984 | continue; | |||
985 | ||||
986 | TargetsForSlot.push_back({Fn, &TM}); | |||
987 | } | |||
988 | ||||
989 | // Give up if we couldn't find any targets. | |||
990 | return !TargetsForSlot.empty(); | |||
991 | } | |||
992 | ||||
993 | bool DevirtIndex::tryFindVirtualCallTargets( | |||
994 | std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo, | |||
995 | uint64_t ByteOffset) { | |||
996 | for (const TypeIdOffsetVtableInfo &P : TIdInfo) { | |||
997 | // Find the first non-available_externally linkage vtable initializer. | |||
998 | // We can have multiple available_externally, linkonce_odr and weak_odr | |||
999 | // vtable initializers, however we want to skip available_externally as they | |||
1000 | // do not have type metadata attached, and therefore the summary will not | |||
1001 | // contain any vtable functions. We can also have multiple external | |||
1002 | // vtable initializers in the case of comdats, which we cannot check here. | |||
1003 | // The linker should give an error in this case. | |||
1004 | // | |||
1005 | // Also, handle the case of same-named local Vtables with the same path | |||
1006 | // and therefore the same GUID. This can happen if there isn't enough | |||
1007 | // distinguishing path when compiling the source file. In that case we | |||
1008 | // conservatively return false early. | |||
1009 | const GlobalVarSummary *VS = nullptr; | |||
1010 | bool LocalFound = false; | |||
1011 | for (auto &S : P.VTableVI.getSummaryList()) { | |||
1012 | if (GlobalValue::isLocalLinkage(S->linkage())) { | |||
1013 | if (LocalFound) | |||
1014 | return false; | |||
1015 | LocalFound = true; | |||
1016 | } | |||
1017 | if (!GlobalValue::isAvailableExternallyLinkage(S->linkage())) { | |||
1018 | VS = cast<GlobalVarSummary>(S->getBaseObject()); | |||
1019 | // We cannot perform whole program devirtualization analysis on a vtable | |||
1020 | // with public LTO visibility. | |||
1021 | if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic) | |||
1022 | return false; | |||
1023 | } | |||
1024 | } | |||
1025 | if (!VS->isLive()) | |||
| ||||
1026 | continue; | |||
1027 | for (auto VTP : VS->vTableFuncs()) { | |||
1028 | if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset) | |||
1029 | continue; | |||
1030 | ||||
1031 | TargetsForSlot.push_back(VTP.FuncVI); | |||
1032 | } | |||
1033 | } | |||
1034 | ||||
1035 | // Give up if we couldn't find any targets. | |||
1036 | return !TargetsForSlot.empty(); | |||
1037 | } | |||
1038 | ||||
1039 | void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo, | |||
1040 | Constant *TheFn, bool &IsExported) { | |||
1041 | // Don't devirtualize function if we're told to skip it | |||
1042 | // in -wholeprogramdevirt-skip. | |||
1043 | if (FunctionsToSkip.match(TheFn->stripPointerCasts()->getName())) | |||
1044 | return; | |||
1045 | auto Apply = [&](CallSiteInfo &CSInfo) { | |||
1046 | for (auto &&VCallSite : CSInfo.CallSites) { | |||
1047 | if (RemarksEnabled) | |||
1048 | VCallSite.emitRemark("single-impl", | |||
1049 | TheFn->stripPointerCasts()->getName(), OREGetter); | |||
1050 | VCallSite.CB.setCalledOperand(ConstantExpr::getBitCast( | |||
1051 | TheFn, VCallSite.CB.getCalledOperand()->getType())); | |||
1052 | // This use is no longer unsafe. | |||
1053 | if (VCallSite.NumUnsafeUses) | |||
1054 | --*VCallSite.NumUnsafeUses; | |||
1055 | } | |||
1056 | if (CSInfo.isExported()) | |||
1057 | IsExported = true; | |||
1058 | CSInfo.markDevirt(); | |||
1059 | }; | |||
1060 | Apply(SlotInfo.CSInfo); | |||
1061 | for (auto &P : SlotInfo.ConstCSInfo) | |||
1062 | Apply(P.second); | |||
1063 | } | |||
1064 | ||||
1065 | static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) { | |||
1066 | // We can't add calls if we haven't seen a definition | |||
1067 | if (Callee.getSummaryList().empty()) | |||
1068 | return false; | |||
1069 | ||||
1070 | // Insert calls into the summary index so that the devirtualized targets | |||
1071 | // are eligible for import. | |||
1072 | // FIXME: Annotate type tests with hotness. For now, mark these as hot | |||
1073 | // to better ensure we have the opportunity to inline them. | |||
1074 | bool IsExported = false; | |||
1075 | auto &S = Callee.getSummaryList()[0]; | |||
1076 | CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0); | |||
1077 | auto AddCalls = [&](CallSiteInfo &CSInfo) { | |||
1078 | for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) { | |||
1079 | FS->addCall({Callee, CI}); | |||
1080 | IsExported |= S->modulePath() != FS->modulePath(); | |||
1081 | } | |||
1082 | for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) { | |||
1083 | FS->addCall({Callee, CI}); | |||
1084 | IsExported |= S->modulePath() != FS->modulePath(); | |||
1085 | } | |||
1086 | }; | |||
1087 | AddCalls(SlotInfo.CSInfo); | |||
1088 | for (auto &P : SlotInfo.ConstCSInfo) | |||
1089 | AddCalls(P.second); | |||
1090 | return IsExported; | |||
1091 | } | |||
1092 | ||||
1093 | bool DevirtModule::trySingleImplDevirt( | |||
1094 | ModuleSummaryIndex *ExportSummary, | |||
1095 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, | |||
1096 | WholeProgramDevirtResolution *Res) { | |||
1097 | // See if the program contains a single implementation of this virtual | |||
1098 | // function. | |||
1099 | Function *TheFn = TargetsForSlot[0].Fn; | |||
1100 | for (auto &&Target : TargetsForSlot) | |||
1101 | if (TheFn != Target.Fn) | |||
1102 | return false; | |||
1103 | ||||
1104 | // If so, update each call site to call that implementation directly. | |||
1105 | if (RemarksEnabled) | |||
1106 | TargetsForSlot[0].WasDevirt = true; | |||
1107 | ||||
1108 | bool IsExported = false; | |||
1109 | applySingleImplDevirt(SlotInfo, TheFn, IsExported); | |||
1110 | if (!IsExported) | |||
1111 | return false; | |||
1112 | ||||
1113 | // If the only implementation has local linkage, we must promote to external | |||
1114 | // to make it visible to thin LTO objects. We can only get here during the | |||
1115 | // ThinLTO export phase. | |||
1116 | if (TheFn->hasLocalLinkage()) { | |||
1117 | std::string NewName = (TheFn->getName() + "$merged").str(); | |||
1118 | ||||
1119 | // Since we are renaming the function, any comdats with the same name must | |||
1120 | // also be renamed. This is required when targeting COFF, as the comdat name | |||
1121 | // must match one of the names of the symbols in the comdat. | |||
1122 | if (Comdat *C = TheFn->getComdat()) { | |||
1123 | if (C->getName() == TheFn->getName()) { | |||
1124 | Comdat *NewC = M.getOrInsertComdat(NewName); | |||
1125 | NewC->setSelectionKind(C->getSelectionKind()); | |||
1126 | for (GlobalObject &GO : M.global_objects()) | |||
1127 | if (GO.getComdat() == C) | |||
1128 | GO.setComdat(NewC); | |||
1129 | } | |||
1130 | } | |||
1131 | ||||
1132 | TheFn->setLinkage(GlobalValue::ExternalLinkage); | |||
1133 | TheFn->setVisibility(GlobalValue::HiddenVisibility); | |||
1134 | TheFn->setName(NewName); | |||
1135 | } | |||
1136 | if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID())) | |||
1137 | // Any needed promotion of 'TheFn' has already been done during | |||
1138 | // LTO unit split, so we can ignore return value of AddCalls. | |||
1139 | AddCalls(SlotInfo, TheFnVI); | |||
1140 | ||||
1141 | Res->TheKind = WholeProgramDevirtResolution::SingleImpl; | |||
1142 | Res->SingleImplName = std::string(TheFn->getName()); | |||
1143 | ||||
1144 | return true; | |||
1145 | } | |||
1146 | ||||
1147 | bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot, | |||
1148 | VTableSlotSummary &SlotSummary, | |||
1149 | VTableSlotInfo &SlotInfo, | |||
1150 | WholeProgramDevirtResolution *Res, | |||
1151 | std::set<ValueInfo> &DevirtTargets) { | |||
1152 | // See if the program contains a single implementation of this virtual | |||
1153 | // function. | |||
1154 | auto TheFn = TargetsForSlot[0]; | |||
1155 | for (auto &&Target : TargetsForSlot) | |||
1156 | if (TheFn != Target) | |||
1157 | return false; | |||
1158 | ||||
1159 | // Don't devirtualize if we don't have target definition. | |||
1160 | auto Size = TheFn.getSummaryList().size(); | |||
1161 | if (!Size) | |||
1162 | return false; | |||
1163 | ||||
1164 | // Don't devirtualize function if we're told to skip it | |||
1165 | // in -wholeprogramdevirt-skip. | |||
1166 | if (FunctionsToSkip.match(TheFn.name())) | |||
1167 | return false; | |||
1168 | ||||
1169 | // If the summary list contains multiple summaries where at least one is | |||
1170 | // a local, give up, as we won't know which (possibly promoted) name to use. | |||
1171 | for (auto &S : TheFn.getSummaryList()) | |||
1172 | if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1) | |||
1173 | return false; | |||
1174 | ||||
1175 | // Collect functions devirtualized at least for one call site for stats. | |||
1176 | if (PrintSummaryDevirt) | |||
1177 | DevirtTargets.insert(TheFn); | |||
1178 | ||||
1179 | auto &S = TheFn.getSummaryList()[0]; | |||
1180 | bool IsExported = AddCalls(SlotInfo, TheFn); | |||
1181 | if (IsExported) | |||
1182 | ExportedGUIDs.insert(TheFn.getGUID()); | |||
1183 | ||||
1184 | // Record in summary for use in devirtualization during the ThinLTO import | |||
1185 | // step. | |||
1186 | Res->TheKind = WholeProgramDevirtResolution::SingleImpl; | |||
1187 | if (GlobalValue::isLocalLinkage(S->linkage())) { | |||
1188 | if (IsExported) | |||
1189 | // If target is a local function and we are exporting it by | |||
1190 | // devirtualizing a call in another module, we need to record the | |||
1191 | // promoted name. | |||
1192 | Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal( | |||
1193 | TheFn.name(), ExportSummary.getModuleHash(S->modulePath())); | |||
1194 | else { | |||
1195 | LocalWPDTargetsMap[TheFn].push_back(SlotSummary); | |||
1196 | Res->SingleImplName = std::string(TheFn.name()); | |||
1197 | } | |||
1198 | } else | |||
1199 | Res->SingleImplName = std::string(TheFn.name()); | |||
1200 | ||||
1201 | // Name will be empty if this thin link driven off of serialized combined | |||
1202 | // index (e.g. llvm-lto). However, WPD is not supported/invoked for the | |||
1203 | // legacy LTO API anyway. | |||
1204 | assert(!Res->SingleImplName.empty())((!Res->SingleImplName.empty()) ? static_cast<void> ( 0) : __assert_fail ("!Res->SingleImplName.empty()", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1204, __PRETTY_FUNCTION__)); | |||
1205 | ||||
1206 | return true; | |||
1207 | } | |||
1208 | ||||
1209 | void DevirtModule::tryICallBranchFunnel( | |||
1210 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, | |||
1211 | WholeProgramDevirtResolution *Res, VTableSlot Slot) { | |||
1212 | Triple T(M.getTargetTriple()); | |||
1213 | if (T.getArch() != Triple::x86_64) | |||
1214 | return; | |||
1215 | ||||
1216 | if (TargetsForSlot.size() > ClThreshold) | |||
1217 | return; | |||
1218 | ||||
1219 | bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted; | |||
1220 | if (!HasNonDevirt) | |||
1221 | for (auto &P : SlotInfo.ConstCSInfo) | |||
1222 | if (!P.second.AllCallSitesDevirted) { | |||
1223 | HasNonDevirt = true; | |||
1224 | break; | |||
1225 | } | |||
1226 | ||||
1227 | if (!HasNonDevirt) | |||
1228 | return; | |||
1229 | ||||
1230 | FunctionType *FT = | |||
1231 | FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true); | |||
1232 | Function *JT; | |||
1233 | if (isa<MDString>(Slot.TypeID)) { | |||
1234 | JT = Function::Create(FT, Function::ExternalLinkage, | |||
1235 | M.getDataLayout().getProgramAddressSpace(), | |||
1236 | getGlobalName(Slot, {}, "branch_funnel"), &M); | |||
1237 | JT->setVisibility(GlobalValue::HiddenVisibility); | |||
1238 | } else { | |||
1239 | JT = Function::Create(FT, Function::InternalLinkage, | |||
1240 | M.getDataLayout().getProgramAddressSpace(), | |||
1241 | "branch_funnel", &M); | |||
1242 | } | |||
1243 | JT->addAttribute(1, Attribute::Nest); | |||
1244 | ||||
1245 | std::vector<Value *> JTArgs; | |||
1246 | JTArgs.push_back(JT->arg_begin()); | |||
1247 | for (auto &T : TargetsForSlot) { | |||
1248 | JTArgs.push_back(getMemberAddr(T.TM)); | |||
1249 | JTArgs.push_back(T.Fn); | |||
1250 | } | |||
1251 | ||||
1252 | BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr); | |||
1253 | Function *Intr = | |||
1254 | Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {}); | |||
1255 | ||||
1256 | auto *CI = CallInst::Create(Intr, JTArgs, "", BB); | |||
1257 | CI->setTailCallKind(CallInst::TCK_MustTail); | |||
1258 | ReturnInst::Create(M.getContext(), nullptr, BB); | |||
1259 | ||||
1260 | bool IsExported = false; | |||
1261 | applyICallBranchFunnel(SlotInfo, JT, IsExported); | |||
1262 | if (IsExported) | |||
1263 | Res->TheKind = WholeProgramDevirtResolution::BranchFunnel; | |||
1264 | } | |||
1265 | ||||
1266 | void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo, | |||
1267 | Constant *JT, bool &IsExported) { | |||
1268 | auto Apply = [&](CallSiteInfo &CSInfo) { | |||
1269 | if (CSInfo.isExported()) | |||
1270 | IsExported = true; | |||
1271 | if (CSInfo.AllCallSitesDevirted) | |||
1272 | return; | |||
1273 | for (auto &&VCallSite : CSInfo.CallSites) { | |||
1274 | CallBase &CB = VCallSite.CB; | |||
1275 | ||||
1276 | // Jump tables are only profitable if the retpoline mitigation is enabled. | |||
1277 | Attribute FSAttr = CB.getCaller()->getFnAttribute("target-features"); | |||
1278 | if (!FSAttr.isValid() || | |||
1279 | !FSAttr.getValueAsString().contains("+retpoline")) | |||
1280 | continue; | |||
1281 | ||||
1282 | if (RemarksEnabled) | |||
1283 | VCallSite.emitRemark("branch-funnel", | |||
1284 | JT->stripPointerCasts()->getName(), OREGetter); | |||
1285 | ||||
1286 | // Pass the address of the vtable in the nest register, which is r10 on | |||
1287 | // x86_64. | |||
1288 | std::vector<Type *> NewArgs; | |||
1289 | NewArgs.push_back(Int8PtrTy); | |||
1290 | append_range(NewArgs, CB.getFunctionType()->params()); | |||
1291 | FunctionType *NewFT = | |||
1292 | FunctionType::get(CB.getFunctionType()->getReturnType(), NewArgs, | |||
1293 | CB.getFunctionType()->isVarArg()); | |||
1294 | PointerType *NewFTPtr = PointerType::getUnqual(NewFT); | |||
1295 | ||||
1296 | IRBuilder<> IRB(&CB); | |||
1297 | std::vector<Value *> Args; | |||
1298 | Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy)); | |||
1299 | llvm::append_range(Args, CB.args()); | |||
1300 | ||||
1301 | CallBase *NewCS = nullptr; | |||
1302 | if (isa<CallInst>(CB)) | |||
1303 | NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(JT, NewFTPtr), Args); | |||
1304 | else | |||
1305 | NewCS = IRB.CreateInvoke(NewFT, IRB.CreateBitCast(JT, NewFTPtr), | |||
1306 | cast<InvokeInst>(CB).getNormalDest(), | |||
1307 | cast<InvokeInst>(CB).getUnwindDest(), Args); | |||
1308 | NewCS->setCallingConv(CB.getCallingConv()); | |||
1309 | ||||
1310 | AttributeList Attrs = CB.getAttributes(); | |||
1311 | std::vector<AttributeSet> NewArgAttrs; | |||
1312 | NewArgAttrs.push_back(AttributeSet::get( | |||
1313 | M.getContext(), ArrayRef<Attribute>{Attribute::get( | |||
1314 | M.getContext(), Attribute::Nest)})); | |||
1315 | for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I) | |||
1316 | NewArgAttrs.push_back(Attrs.getParamAttributes(I)); | |||
1317 | NewCS->setAttributes( | |||
1318 | AttributeList::get(M.getContext(), Attrs.getFnAttributes(), | |||
1319 | Attrs.getRetAttributes(), NewArgAttrs)); | |||
1320 | ||||
1321 | CB.replaceAllUsesWith(NewCS); | |||
1322 | CB.eraseFromParent(); | |||
1323 | ||||
1324 | // This use is no longer unsafe. | |||
1325 | if (VCallSite.NumUnsafeUses) | |||
1326 | --*VCallSite.NumUnsafeUses; | |||
1327 | } | |||
1328 | // Don't mark as devirtualized because there may be callers compiled without | |||
1329 | // retpoline mitigation, which would mean that they are lowered to | |||
1330 | // llvm.type.test and therefore require an llvm.type.test resolution for the | |||
1331 | // type identifier. | |||
1332 | }; | |||
1333 | Apply(SlotInfo.CSInfo); | |||
1334 | for (auto &P : SlotInfo.ConstCSInfo) | |||
1335 | Apply(P.second); | |||
1336 | } | |||
1337 | ||||
1338 | bool DevirtModule::tryEvaluateFunctionsWithArgs( | |||
1339 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
1340 | ArrayRef<uint64_t> Args) { | |||
1341 | // Evaluate each function and store the result in each target's RetVal | |||
1342 | // field. | |||
1343 | for (VirtualCallTarget &Target : TargetsForSlot) { | |||
1344 | if (Target.Fn->arg_size() != Args.size() + 1) | |||
1345 | return false; | |||
1346 | ||||
1347 | Evaluator Eval(M.getDataLayout(), nullptr); | |||
1348 | SmallVector<Constant *, 2> EvalArgs; | |||
1349 | EvalArgs.push_back( | |||
1350 | Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0))); | |||
1351 | for (unsigned I = 0; I != Args.size(); ++I) { | |||
1352 | auto *ArgTy = dyn_cast<IntegerType>( | |||
1353 | Target.Fn->getFunctionType()->getParamType(I + 1)); | |||
1354 | if (!ArgTy) | |||
1355 | return false; | |||
1356 | EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I])); | |||
1357 | } | |||
1358 | ||||
1359 | Constant *RetVal; | |||
1360 | if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) || | |||
1361 | !isa<ConstantInt>(RetVal)) | |||
1362 | return false; | |||
1363 | Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue(); | |||
1364 | } | |||
1365 | return true; | |||
1366 | } | |||
1367 | ||||
1368 | void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, | |||
1369 | uint64_t TheRetVal) { | |||
1370 | for (auto Call : CSInfo.CallSites) | |||
1371 | Call.replaceAndErase( | |||
1372 | "uniform-ret-val", FnName, RemarksEnabled, OREGetter, | |||
1373 | ConstantInt::get(cast<IntegerType>(Call.CB.getType()), TheRetVal)); | |||
1374 | CSInfo.markDevirt(); | |||
1375 | } | |||
1376 | ||||
1377 | bool DevirtModule::tryUniformRetValOpt( | |||
1378 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo, | |||
1379 | WholeProgramDevirtResolution::ByArg *Res) { | |||
1380 | // Uniform return value optimization. If all functions return the same | |||
1381 | // constant, replace all calls with that constant. | |||
1382 | uint64_t TheRetVal = TargetsForSlot[0].RetVal; | |||
1383 | for (const VirtualCallTarget &Target : TargetsForSlot) | |||
1384 | if (Target.RetVal != TheRetVal) | |||
1385 | return false; | |||
1386 | ||||
1387 | if (CSInfo.isExported()) { | |||
1388 | Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal; | |||
1389 | Res->Info = TheRetVal; | |||
1390 | } | |||
1391 | ||||
1392 | applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal); | |||
1393 | if (RemarksEnabled) | |||
1394 | for (auto &&Target : TargetsForSlot) | |||
1395 | Target.WasDevirt = true; | |||
1396 | return true; | |||
1397 | } | |||
1398 | ||||
1399 | std::string DevirtModule::getGlobalName(VTableSlot Slot, | |||
1400 | ArrayRef<uint64_t> Args, | |||
1401 | StringRef Name) { | |||
1402 | std::string FullName = "__typeid_"; | |||
1403 | raw_string_ostream OS(FullName); | |||
1404 | OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset; | |||
1405 | for (uint64_t Arg : Args) | |||
1406 | OS << '_' << Arg; | |||
1407 | OS << '_' << Name; | |||
1408 | return OS.str(); | |||
1409 | } | |||
1410 | ||||
1411 | bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() { | |||
1412 | Triple T(M.getTargetTriple()); | |||
1413 | return T.isX86() && T.getObjectFormat() == Triple::ELF; | |||
1414 | } | |||
1415 | ||||
1416 | void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
1417 | StringRef Name, Constant *C) { | |||
1418 | GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage, | |||
1419 | getGlobalName(Slot, Args, Name), C, &M); | |||
1420 | GA->setVisibility(GlobalValue::HiddenVisibility); | |||
1421 | } | |||
1422 | ||||
1423 | void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
1424 | StringRef Name, uint32_t Const, | |||
1425 | uint32_t &Storage) { | |||
1426 | if (shouldExportConstantsAsAbsoluteSymbols()) { | |||
1427 | exportGlobal( | |||
1428 | Slot, Args, Name, | |||
1429 | ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy)); | |||
1430 | return; | |||
1431 | } | |||
1432 | ||||
1433 | Storage = Const; | |||
1434 | } | |||
1435 | ||||
1436 | Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
1437 | StringRef Name) { | |||
1438 | Constant *C = | |||
1439 | M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Arr0Ty); | |||
1440 | auto *GV = dyn_cast<GlobalVariable>(C); | |||
1441 | if (GV) | |||
1442 | GV->setVisibility(GlobalValue::HiddenVisibility); | |||
1443 | return C; | |||
1444 | } | |||
1445 | ||||
1446 | Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, | |||
1447 | StringRef Name, IntegerType *IntTy, | |||
1448 | uint32_t Storage) { | |||
1449 | if (!shouldExportConstantsAsAbsoluteSymbols()) | |||
1450 | return ConstantInt::get(IntTy, Storage); | |||
1451 | ||||
1452 | Constant *C = importGlobal(Slot, Args, Name); | |||
1453 | auto *GV = cast<GlobalVariable>(C->stripPointerCasts()); | |||
1454 | C = ConstantExpr::getPtrToInt(C, IntTy); | |||
1455 | ||||
1456 | // We only need to set metadata if the global is newly created, in which | |||
1457 | // case it would not have hidden visibility. | |||
1458 | if (GV->hasMetadata(LLVMContext::MD_absolute_symbol)) | |||
1459 | return C; | |||
1460 | ||||
1461 | auto SetAbsRange = [&](uint64_t Min, uint64_t Max) { | |||
1462 | auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min)); | |||
1463 | auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max)); | |||
1464 | GV->setMetadata(LLVMContext::MD_absolute_symbol, | |||
1465 | MDNode::get(M.getContext(), {MinC, MaxC})); | |||
1466 | }; | |||
1467 | unsigned AbsWidth = IntTy->getBitWidth(); | |||
1468 | if (AbsWidth == IntPtrTy->getBitWidth()) | |||
1469 | SetAbsRange(~0ull, ~0ull); // Full set. | |||
1470 | else | |||
1471 | SetAbsRange(0, 1ull << AbsWidth); | |||
1472 | return C; | |||
1473 | } | |||
1474 | ||||
1475 | void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, | |||
1476 | bool IsOne, | |||
1477 | Constant *UniqueMemberAddr) { | |||
1478 | for (auto &&Call : CSInfo.CallSites) { | |||
1479 | IRBuilder<> B(&Call.CB); | |||
1480 | Value *Cmp = | |||
1481 | B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, Call.VTable, | |||
1482 | B.CreateBitCast(UniqueMemberAddr, Call.VTable->getType())); | |||
1483 | Cmp = B.CreateZExt(Cmp, Call.CB.getType()); | |||
1484 | Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter, | |||
1485 | Cmp); | |||
1486 | } | |||
1487 | CSInfo.markDevirt(); | |||
1488 | } | |||
1489 | ||||
1490 | Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) { | |||
1491 | Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy); | |||
1492 | return ConstantExpr::getGetElementPtr(Int8Ty, C, | |||
1493 | ConstantInt::get(Int64Ty, M->Offset)); | |||
1494 | } | |||
1495 | ||||
1496 | bool DevirtModule::tryUniqueRetValOpt( | |||
1497 | unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot, | |||
1498 | CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res, | |||
1499 | VTableSlot Slot, ArrayRef<uint64_t> Args) { | |||
1500 | // IsOne controls whether we look for a 0 or a 1. | |||
1501 | auto tryUniqueRetValOptFor = [&](bool IsOne) { | |||
1502 | const TypeMemberInfo *UniqueMember = nullptr; | |||
1503 | for (const VirtualCallTarget &Target : TargetsForSlot) { | |||
1504 | if (Target.RetVal == (IsOne ? 1 : 0)) { | |||
1505 | if (UniqueMember) | |||
1506 | return false; | |||
1507 | UniqueMember = Target.TM; | |||
1508 | } | |||
1509 | } | |||
1510 | ||||
1511 | // We should have found a unique member or bailed out by now. We already | |||
1512 | // checked for a uniform return value in tryUniformRetValOpt. | |||
1513 | assert(UniqueMember)((UniqueMember) ? static_cast<void> (0) : __assert_fail ("UniqueMember", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1513, __PRETTY_FUNCTION__)); | |||
1514 | ||||
1515 | Constant *UniqueMemberAddr = getMemberAddr(UniqueMember); | |||
1516 | if (CSInfo.isExported()) { | |||
1517 | Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal; | |||
1518 | Res->Info = IsOne; | |||
1519 | ||||
1520 | exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr); | |||
1521 | } | |||
1522 | ||||
1523 | // Replace each call with the comparison. | |||
1524 | applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne, | |||
1525 | UniqueMemberAddr); | |||
1526 | ||||
1527 | // Update devirtualization statistics for targets. | |||
1528 | if (RemarksEnabled) | |||
1529 | for (auto &&Target : TargetsForSlot) | |||
1530 | Target.WasDevirt = true; | |||
1531 | ||||
1532 | return true; | |||
1533 | }; | |||
1534 | ||||
1535 | if (BitWidth == 1) { | |||
1536 | if (tryUniqueRetValOptFor(true)) | |||
1537 | return true; | |||
1538 | if (tryUniqueRetValOptFor(false)) | |||
1539 | return true; | |||
1540 | } | |||
1541 | return false; | |||
1542 | } | |||
1543 | ||||
1544 | void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName, | |||
1545 | Constant *Byte, Constant *Bit) { | |||
1546 | for (auto Call : CSInfo.CallSites) { | |||
1547 | auto *RetType = cast<IntegerType>(Call.CB.getType()); | |||
1548 | IRBuilder<> B(&Call.CB); | |||
1549 | Value *Addr = | |||
1550 | B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte); | |||
1551 | if (RetType->getBitWidth() == 1) { | |||
1552 | Value *Bits = B.CreateLoad(Int8Ty, Addr); | |||
1553 | Value *BitsAndBit = B.CreateAnd(Bits, Bit); | |||
1554 | auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0)); | |||
1555 | Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled, | |||
1556 | OREGetter, IsBitSet); | |||
1557 | } else { | |||
1558 | Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo()); | |||
1559 | Value *Val = B.CreateLoad(RetType, ValAddr); | |||
1560 | Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled, | |||
1561 | OREGetter, Val); | |||
1562 | } | |||
1563 | } | |||
1564 | CSInfo.markDevirt(); | |||
1565 | } | |||
1566 | ||||
1567 | bool DevirtModule::tryVirtualConstProp( | |||
1568 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, | |||
1569 | WholeProgramDevirtResolution *Res, VTableSlot Slot) { | |||
1570 | // This only works if the function returns an integer. | |||
1571 | auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType()); | |||
1572 | if (!RetType) | |||
1573 | return false; | |||
1574 | unsigned BitWidth = RetType->getBitWidth(); | |||
1575 | if (BitWidth > 64) | |||
1576 | return false; | |||
1577 | ||||
1578 | // Make sure that each function is defined, does not access memory, takes at | |||
1579 | // least one argument, does not use its first argument (which we assume is | |||
1580 | // 'this'), and has the same return type. | |||
1581 | // | |||
1582 | // Note that we test whether this copy of the function is readnone, rather | |||
1583 | // than testing function attributes, which must hold for any copy of the | |||
1584 | // function, even a less optimized version substituted at link time. This is | |||
1585 | // sound because the virtual constant propagation optimizations effectively | |||
1586 | // inline all implementations of the virtual function into each call site, | |||
1587 | // rather than using function attributes to perform local optimization. | |||
1588 | for (VirtualCallTarget &Target : TargetsForSlot) { | |||
1589 | if (Target.Fn->isDeclaration() || | |||
1590 | computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) != | |||
1591 | MAK_ReadNone || | |||
1592 | Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() || | |||
1593 | Target.Fn->getReturnType() != RetType) | |||
1594 | return false; | |||
1595 | } | |||
1596 | ||||
1597 | for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) { | |||
1598 | if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first)) | |||
1599 | continue; | |||
1600 | ||||
1601 | WholeProgramDevirtResolution::ByArg *ResByArg = nullptr; | |||
1602 | if (Res) | |||
1603 | ResByArg = &Res->ResByArg[CSByConstantArg.first]; | |||
1604 | ||||
1605 | if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg)) | |||
1606 | continue; | |||
1607 | ||||
1608 | if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second, | |||
1609 | ResByArg, Slot, CSByConstantArg.first)) | |||
1610 | continue; | |||
1611 | ||||
1612 | // Find an allocation offset in bits in all vtables associated with the | |||
1613 | // type. | |||
1614 | uint64_t AllocBefore = | |||
1615 | findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth); | |||
1616 | uint64_t AllocAfter = | |||
1617 | findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth); | |||
1618 | ||||
1619 | // Calculate the total amount of padding needed to store a value at both | |||
1620 | // ends of the object. | |||
1621 | uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0; | |||
1622 | for (auto &&Target : TargetsForSlot) { | |||
1623 | TotalPaddingBefore += std::max<int64_t>( | |||
1624 | (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0); | |||
1625 | TotalPaddingAfter += std::max<int64_t>( | |||
1626 | (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0); | |||
1627 | } | |||
1628 | ||||
1629 | // If the amount of padding is too large, give up. | |||
1630 | // FIXME: do something smarter here. | |||
1631 | if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128) | |||
1632 | continue; | |||
1633 | ||||
1634 | // Calculate the offset to the value as a (possibly negative) byte offset | |||
1635 | // and (if applicable) a bit offset, and store the values in the targets. | |||
1636 | int64_t OffsetByte; | |||
1637 | uint64_t OffsetBit; | |||
1638 | if (TotalPaddingBefore <= TotalPaddingAfter) | |||
1639 | setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte, | |||
1640 | OffsetBit); | |||
1641 | else | |||
1642 | setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte, | |||
1643 | OffsetBit); | |||
1644 | ||||
1645 | if (RemarksEnabled) | |||
1646 | for (auto &&Target : TargetsForSlot) | |||
1647 | Target.WasDevirt = true; | |||
1648 | ||||
1649 | ||||
1650 | if (CSByConstantArg.second.isExported()) { | |||
1651 | ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp; | |||
1652 | exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte, | |||
1653 | ResByArg->Byte); | |||
1654 | exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit, | |||
1655 | ResByArg->Bit); | |||
1656 | } | |||
1657 | ||||
1658 | // Rewrite each call to a load from OffsetByte/OffsetBit. | |||
1659 | Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte); | |||
1660 | Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit); | |||
1661 | applyVirtualConstProp(CSByConstantArg.second, | |||
1662 | TargetsForSlot[0].Fn->getName(), ByteConst, BitConst); | |||
1663 | } | |||
1664 | return true; | |||
1665 | } | |||
1666 | ||||
1667 | void DevirtModule::rebuildGlobal(VTableBits &B) { | |||
1668 | if (B.Before.Bytes.empty() && B.After.Bytes.empty()) | |||
1669 | return; | |||
1670 | ||||
1671 | // Align the before byte array to the global's minimum alignment so that we | |||
1672 | // don't break any alignment requirements on the global. | |||
1673 | Align Alignment = M.getDataLayout().getValueOrABITypeAlignment( | |||
1674 | B.GV->getAlign(), B.GV->getValueType()); | |||
1675 | B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment)); | |||
1676 | ||||
1677 | // Before was stored in reverse order; flip it now. | |||
1678 | for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I) | |||
1679 | std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]); | |||
1680 | ||||
1681 | // Build an anonymous global containing the before bytes, followed by the | |||
1682 | // original initializer, followed by the after bytes. | |||
1683 | auto NewInit = ConstantStruct::getAnon( | |||
1684 | {ConstantDataArray::get(M.getContext(), B.Before.Bytes), | |||
1685 | B.GV->getInitializer(), | |||
1686 | ConstantDataArray::get(M.getContext(), B.After.Bytes)}); | |||
1687 | auto NewGV = | |||
1688 | new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(), | |||
1689 | GlobalVariable::PrivateLinkage, NewInit, "", B.GV); | |||
1690 | NewGV->setSection(B.GV->getSection()); | |||
1691 | NewGV->setComdat(B.GV->getComdat()); | |||
1692 | NewGV->setAlignment(MaybeAlign(B.GV->getAlignment())); | |||
1693 | ||||
1694 | // Copy the original vtable's metadata to the anonymous global, adjusting | |||
1695 | // offsets as required. | |||
1696 | NewGV->copyMetadata(B.GV, B.Before.Bytes.size()); | |||
1697 | ||||
1698 | // Build an alias named after the original global, pointing at the second | |||
1699 | // element (the original initializer). | |||
1700 | auto Alias = GlobalAlias::create( | |||
1701 | B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "", | |||
1702 | ConstantExpr::getGetElementPtr( | |||
1703 | NewInit->getType(), NewGV, | |||
1704 | ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0), | |||
1705 | ConstantInt::get(Int32Ty, 1)}), | |||
1706 | &M); | |||
1707 | Alias->setVisibility(B.GV->getVisibility()); | |||
1708 | Alias->takeName(B.GV); | |||
1709 | ||||
1710 | B.GV->replaceAllUsesWith(Alias); | |||
1711 | B.GV->eraseFromParent(); | |||
1712 | } | |||
1713 | ||||
1714 | bool DevirtModule::areRemarksEnabled() { | |||
1715 | const auto &FL = M.getFunctionList(); | |||
1716 | for (const Function &Fn : FL) { | |||
1717 | const auto &BBL = Fn.getBasicBlockList(); | |||
1718 | if (BBL.empty()) | |||
1719 | continue; | |||
1720 | auto DI = OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "", DebugLoc(), &BBL.front()); | |||
1721 | return DI.isEnabled(); | |||
1722 | } | |||
1723 | return false; | |||
1724 | } | |||
1725 | ||||
1726 | void DevirtModule::scanTypeTestUsers( | |||
1727 | Function *TypeTestFunc, | |||
1728 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { | |||
1729 | // Find all virtual calls via a virtual table pointer %p under an assumption | |||
1730 | // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p | |||
1731 | // points to a member of the type identifier %md. Group calls by (type ID, | |||
1732 | // offset) pair (effectively the identity of the virtual function) and store | |||
1733 | // to CallSlots. | |||
1734 | for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end(); | |||
1735 | I != E;) { | |||
1736 | auto CI = dyn_cast<CallInst>(I->getUser()); | |||
1737 | ++I; | |||
1738 | if (!CI) | |||
1739 | continue; | |||
1740 | ||||
1741 | // Search for virtual calls based on %p and add them to DevirtCalls. | |||
1742 | SmallVector<DevirtCallSite, 1> DevirtCalls; | |||
1743 | SmallVector<CallInst *, 1> Assumes; | |||
1744 | auto &DT = LookupDomTree(*CI->getFunction()); | |||
1745 | findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT); | |||
1746 | ||||
1747 | Metadata *TypeId = | |||
1748 | cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata(); | |||
1749 | // If we found any, add them to CallSlots. | |||
1750 | if (!Assumes.empty()) { | |||
1751 | Value *Ptr = CI->getArgOperand(0)->stripPointerCasts(); | |||
1752 | for (DevirtCallSite Call : DevirtCalls) | |||
1753 | CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB, nullptr); | |||
1754 | } | |||
1755 | ||||
1756 | auto RemoveTypeTestAssumes = [&]() { | |||
1757 | // We no longer need the assumes or the type test. | |||
1758 | for (auto Assume : Assumes) | |||
1759 | Assume->eraseFromParent(); | |||
1760 | // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we | |||
1761 | // may use the vtable argument later. | |||
1762 | if (CI->use_empty()) | |||
1763 | CI->eraseFromParent(); | |||
1764 | }; | |||
1765 | ||||
1766 | // At this point we could remove all type test assume sequences, as they | |||
1767 | // were originally inserted for WPD. However, we can keep these in the | |||
1768 | // code stream for later analysis (e.g. to help drive more efficient ICP | |||
1769 | // sequences). They will eventually be removed by a second LowerTypeTests | |||
1770 | // invocation that cleans them up. In order to do this correctly, the first | |||
1771 | // LowerTypeTests invocation needs to know that they have "Unknown" type | |||
1772 | // test resolution, so that they aren't treated as Unsat and lowered to | |||
1773 | // False, which will break any uses on assumes. Below we remove any type | |||
1774 | // test assumes that will not be treated as Unknown by LTT. | |||
1775 | ||||
1776 | // The type test assumes will be treated by LTT as Unsat if the type id is | |||
1777 | // not used on a global (in which case it has no entry in the TypeIdMap). | |||
1778 | if (!TypeIdMap.count(TypeId)) | |||
1779 | RemoveTypeTestAssumes(); | |||
1780 | ||||
1781 | // For ThinLTO importing, we need to remove the type test assumes if this is | |||
1782 | // an MDString type id without a corresponding TypeIdSummary. Any | |||
1783 | // non-MDString type ids are ignored and treated as Unknown by LTT, so their | |||
1784 | // type test assumes can be kept. If the MDString type id is missing a | |||
1785 | // TypeIdSummary (e.g. because there was no use on a vcall, preventing the | |||
1786 | // exporting phase of WPD from analyzing it), then it would be treated as | |||
1787 | // Unsat by LTT and we need to remove its type test assumes here. If not | |||
1788 | // used on a vcall we don't need them for later optimization use in any | |||
1789 | // case. | |||
1790 | else if (ImportSummary && isa<MDString>(TypeId)) { | |||
1791 | const TypeIdSummary *TidSummary = | |||
1792 | ImportSummary->getTypeIdSummary(cast<MDString>(TypeId)->getString()); | |||
1793 | if (!TidSummary) | |||
1794 | RemoveTypeTestAssumes(); | |||
1795 | else | |||
1796 | // If one was created it should not be Unsat, because if we reached here | |||
1797 | // the type id was used on a global. | |||
1798 | assert(TidSummary->TTRes.TheKind != TypeTestResolution::Unsat)((TidSummary->TTRes.TheKind != TypeTestResolution::Unsat) ? static_cast<void> (0) : __assert_fail ("TidSummary->TTRes.TheKind != TypeTestResolution::Unsat" , "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1798, __PRETTY_FUNCTION__)); | |||
1799 | } | |||
1800 | } | |||
1801 | } | |||
1802 | ||||
1803 | void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) { | |||
1804 | Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test); | |||
1805 | ||||
1806 | for (auto I = TypeCheckedLoadFunc->use_begin(), | |||
1807 | E = TypeCheckedLoadFunc->use_end(); | |||
1808 | I != E;) { | |||
1809 | auto CI = dyn_cast<CallInst>(I->getUser()); | |||
1810 | ++I; | |||
1811 | if (!CI) | |||
1812 | continue; | |||
1813 | ||||
1814 | Value *Ptr = CI->getArgOperand(0); | |||
1815 | Value *Offset = CI->getArgOperand(1); | |||
1816 | Value *TypeIdValue = CI->getArgOperand(2); | |||
1817 | Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata(); | |||
1818 | ||||
1819 | SmallVector<DevirtCallSite, 1> DevirtCalls; | |||
1820 | SmallVector<Instruction *, 1> LoadedPtrs; | |||
1821 | SmallVector<Instruction *, 1> Preds; | |||
1822 | bool HasNonCallUses = false; | |||
1823 | auto &DT = LookupDomTree(*CI->getFunction()); | |||
1824 | findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds, | |||
1825 | HasNonCallUses, CI, DT); | |||
1826 | ||||
1827 | // Start by generating "pessimistic" code that explicitly loads the function | |||
1828 | // pointer from the vtable and performs the type check. If possible, we will | |||
1829 | // eliminate the load and the type check later. | |||
1830 | ||||
1831 | // If possible, only generate the load at the point where it is used. | |||
1832 | // This helps avoid unnecessary spills. | |||
1833 | IRBuilder<> LoadB( | |||
1834 | (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI); | |||
1835 | Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset); | |||
1836 | Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy)); | |||
1837 | Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr); | |||
1838 | ||||
1839 | for (Instruction *LoadedPtr : LoadedPtrs) { | |||
1840 | LoadedPtr->replaceAllUsesWith(LoadedValue); | |||
1841 | LoadedPtr->eraseFromParent(); | |||
1842 | } | |||
1843 | ||||
1844 | // Likewise for the type test. | |||
1845 | IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI); | |||
1846 | CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue}); | |||
1847 | ||||
1848 | for (Instruction *Pred : Preds) { | |||
1849 | Pred->replaceAllUsesWith(TypeTestCall); | |||
1850 | Pred->eraseFromParent(); | |||
1851 | } | |||
1852 | ||||
1853 | // We have already erased any extractvalue instructions that refer to the | |||
1854 | // intrinsic call, but the intrinsic may have other non-extractvalue uses | |||
1855 | // (although this is unlikely). In that case, explicitly build a pair and | |||
1856 | // RAUW it. | |||
1857 | if (!CI->use_empty()) { | |||
1858 | Value *Pair = UndefValue::get(CI->getType()); | |||
1859 | IRBuilder<> B(CI); | |||
1860 | Pair = B.CreateInsertValue(Pair, LoadedValue, {0}); | |||
1861 | Pair = B.CreateInsertValue(Pair, TypeTestCall, {1}); | |||
1862 | CI->replaceAllUsesWith(Pair); | |||
1863 | } | |||
1864 | ||||
1865 | // The number of unsafe uses is initially the number of uses. | |||
1866 | auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall]; | |||
1867 | NumUnsafeUses = DevirtCalls.size(); | |||
1868 | ||||
1869 | // If the function pointer has a non-call user, we cannot eliminate the type | |||
1870 | // check, as one of those users may eventually call the pointer. Increment | |||
1871 | // the unsafe use count to make sure it cannot reach zero. | |||
1872 | if (HasNonCallUses) | |||
1873 | ++NumUnsafeUses; | |||
1874 | for (DevirtCallSite Call : DevirtCalls) { | |||
1875 | CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB, | |||
1876 | &NumUnsafeUses); | |||
1877 | } | |||
1878 | ||||
1879 | CI->eraseFromParent(); | |||
1880 | } | |||
1881 | } | |||
1882 | ||||
1883 | void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) { | |||
1884 | auto *TypeId = dyn_cast<MDString>(Slot.TypeID); | |||
1885 | if (!TypeId) | |||
1886 | return; | |||
1887 | const TypeIdSummary *TidSummary = | |||
1888 | ImportSummary->getTypeIdSummary(TypeId->getString()); | |||
1889 | if (!TidSummary) | |||
1890 | return; | |||
1891 | auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset); | |||
1892 | if (ResI == TidSummary->WPDRes.end()) | |||
1893 | return; | |||
1894 | const WholeProgramDevirtResolution &Res = ResI->second; | |||
1895 | ||||
1896 | if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) { | |||
1897 | assert(!Res.SingleImplName.empty())((!Res.SingleImplName.empty()) ? static_cast<void> (0) : __assert_fail ("!Res.SingleImplName.empty()", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1897, __PRETTY_FUNCTION__)); | |||
1898 | // The type of the function in the declaration is irrelevant because every | |||
1899 | // call site will cast it to the correct type. | |||
1900 | Constant *SingleImpl = | |||
1901 | cast<Constant>(M.getOrInsertFunction(Res.SingleImplName, | |||
1902 | Type::getVoidTy(M.getContext())) | |||
1903 | .getCallee()); | |||
1904 | ||||
1905 | // This is the import phase so we should not be exporting anything. | |||
1906 | bool IsExported = false; | |||
1907 | applySingleImplDevirt(SlotInfo, SingleImpl, IsExported); | |||
1908 | assert(!IsExported)((!IsExported) ? static_cast<void> (0) : __assert_fail ( "!IsExported", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1908, __PRETTY_FUNCTION__)); | |||
1909 | } | |||
1910 | ||||
1911 | for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) { | |||
1912 | auto I = Res.ResByArg.find(CSByConstantArg.first); | |||
1913 | if (I == Res.ResByArg.end()) | |||
1914 | continue; | |||
1915 | auto &ResByArg = I->second; | |||
1916 | // FIXME: We should figure out what to do about the "function name" argument | |||
1917 | // to the apply* functions, as the function names are unavailable during the | |||
1918 | // importing phase. For now we just pass the empty string. This does not | |||
1919 | // impact correctness because the function names are just used for remarks. | |||
1920 | switch (ResByArg.TheKind) { | |||
1921 | case WholeProgramDevirtResolution::ByArg::UniformRetVal: | |||
1922 | applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info); | |||
1923 | break; | |||
1924 | case WholeProgramDevirtResolution::ByArg::UniqueRetVal: { | |||
1925 | Constant *UniqueMemberAddr = | |||
1926 | importGlobal(Slot, CSByConstantArg.first, "unique_member"); | |||
1927 | applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info, | |||
1928 | UniqueMemberAddr); | |||
1929 | break; | |||
1930 | } | |||
1931 | case WholeProgramDevirtResolution::ByArg::VirtualConstProp: { | |||
1932 | Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte", | |||
1933 | Int32Ty, ResByArg.Byte); | |||
1934 | Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty, | |||
1935 | ResByArg.Bit); | |||
1936 | applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit); | |||
1937 | break; | |||
1938 | } | |||
1939 | default: | |||
1940 | break; | |||
1941 | } | |||
1942 | } | |||
1943 | ||||
1944 | if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) { | |||
1945 | // The type of the function is irrelevant, because it's bitcast at calls | |||
1946 | // anyhow. | |||
1947 | Constant *JT = cast<Constant>( | |||
1948 | M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"), | |||
1949 | Type::getVoidTy(M.getContext())) | |||
1950 | .getCallee()); | |||
1951 | bool IsExported = false; | |||
1952 | applyICallBranchFunnel(SlotInfo, JT, IsExported); | |||
1953 | assert(!IsExported)((!IsExported) ? static_cast<void> (0) : __assert_fail ( "!IsExported", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 1953, __PRETTY_FUNCTION__)); | |||
1954 | } | |||
1955 | } | |||
1956 | ||||
1957 | void DevirtModule::removeRedundantTypeTests() { | |||
1958 | auto True = ConstantInt::getTrue(M.getContext()); | |||
1959 | for (auto &&U : NumUnsafeUsesForTypeTest) { | |||
1960 | if (U.second == 0) { | |||
1961 | U.first->replaceAllUsesWith(True); | |||
1962 | U.first->eraseFromParent(); | |||
1963 | } | |||
1964 | } | |||
1965 | } | |||
1966 | ||||
1967 | bool DevirtModule::run() { | |||
1968 | // If only some of the modules were split, we cannot correctly perform | |||
1969 | // this transformation. We already checked for the presense of type tests | |||
1970 | // with partially split modules during the thin link, and would have emitted | |||
1971 | // an error if any were found, so here we can simply return. | |||
1972 | if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) || | |||
1973 | (ImportSummary && ImportSummary->partiallySplitLTOUnits())) | |||
1974 | return false; | |||
1975 | ||||
1976 | Function *TypeTestFunc = | |||
1977 | M.getFunction(Intrinsic::getName(Intrinsic::type_test)); | |||
1978 | Function *TypeCheckedLoadFunc = | |||
1979 | M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load)); | |||
1980 | Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume)); | |||
1981 | ||||
1982 | // Normally if there are no users of the devirtualization intrinsics in the | |||
1983 | // module, this pass has nothing to do. But if we are exporting, we also need | |||
1984 | // to handle any users that appear only in the function summaries. | |||
1985 | if (!ExportSummary && | |||
1986 | (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc || | |||
1987 | AssumeFunc->use_empty()) && | |||
1988 | (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty())) | |||
1989 | return false; | |||
1990 | ||||
1991 | // Rebuild type metadata into a map for easy lookup. | |||
1992 | std::vector<VTableBits> Bits; | |||
1993 | DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap; | |||
1994 | buildTypeIdentifierMap(Bits, TypeIdMap); | |||
1995 | ||||
1996 | if (TypeTestFunc && AssumeFunc) | |||
1997 | scanTypeTestUsers(TypeTestFunc, TypeIdMap); | |||
1998 | ||||
1999 | if (TypeCheckedLoadFunc) | |||
2000 | scanTypeCheckedLoadUsers(TypeCheckedLoadFunc); | |||
2001 | ||||
2002 | if (ImportSummary) { | |||
2003 | for (auto &S : CallSlots) | |||
2004 | importResolution(S.first, S.second); | |||
2005 | ||||
2006 | removeRedundantTypeTests(); | |||
2007 | ||||
2008 | // We have lowered or deleted the type instrinsics, so we will no | |||
2009 | // longer have enough information to reason about the liveness of virtual | |||
2010 | // function pointers in GlobalDCE. | |||
2011 | for (GlobalVariable &GV : M.globals()) | |||
2012 | GV.eraseMetadata(LLVMContext::MD_vcall_visibility); | |||
2013 | ||||
2014 | // The rest of the code is only necessary when exporting or during regular | |||
2015 | // LTO, so we are done. | |||
2016 | return true; | |||
2017 | } | |||
2018 | ||||
2019 | if (TypeIdMap.empty()) | |||
2020 | return true; | |||
2021 | ||||
2022 | // Collect information from summary about which calls to try to devirtualize. | |||
2023 | if (ExportSummary) { | |||
2024 | DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID; | |||
2025 | for (auto &P : TypeIdMap) { | |||
2026 | if (auto *TypeId = dyn_cast<MDString>(P.first)) | |||
2027 | MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back( | |||
2028 | TypeId); | |||
2029 | } | |||
2030 | ||||
2031 | for (auto &P : *ExportSummary) { | |||
2032 | for (auto &S : P.second.SummaryList) { | |||
2033 | auto *FS = dyn_cast<FunctionSummary>(S.get()); | |||
2034 | if (!FS) | |||
2035 | continue; | |||
2036 | // FIXME: Only add live functions. | |||
2037 | for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) { | |||
2038 | for (Metadata *MD : MetadataByGUID[VF.GUID]) { | |||
2039 | CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS); | |||
2040 | } | |||
2041 | } | |||
2042 | for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) { | |||
2043 | for (Metadata *MD : MetadataByGUID[VF.GUID]) { | |||
2044 | CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS); | |||
2045 | } | |||
2046 | } | |||
2047 | for (const FunctionSummary::ConstVCall &VC : | |||
2048 | FS->type_test_assume_const_vcalls()) { | |||
2049 | for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) { | |||
2050 | CallSlots[{MD, VC.VFunc.Offset}] | |||
2051 | .ConstCSInfo[VC.Args] | |||
2052 | .addSummaryTypeTestAssumeUser(FS); | |||
2053 | } | |||
2054 | } | |||
2055 | for (const FunctionSummary::ConstVCall &VC : | |||
2056 | FS->type_checked_load_const_vcalls()) { | |||
2057 | for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) { | |||
2058 | CallSlots[{MD, VC.VFunc.Offset}] | |||
2059 | .ConstCSInfo[VC.Args] | |||
2060 | .addSummaryTypeCheckedLoadUser(FS); | |||
2061 | } | |||
2062 | } | |||
2063 | } | |||
2064 | } | |||
2065 | } | |||
2066 | ||||
2067 | // For each (type, offset) pair: | |||
2068 | bool DidVirtualConstProp = false; | |||
2069 | std::map<std::string, Function*> DevirtTargets; | |||
2070 | for (auto &S : CallSlots) { | |||
2071 | // Search each of the members of the type identifier for the virtual | |||
2072 | // function implementation at offset S.first.ByteOffset, and add to | |||
2073 | // TargetsForSlot. | |||
2074 | std::vector<VirtualCallTarget> TargetsForSlot; | |||
2075 | WholeProgramDevirtResolution *Res = nullptr; | |||
2076 | const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[S.first.TypeID]; | |||
2077 | if (ExportSummary && isa<MDString>(S.first.TypeID) && | |||
2078 | TypeMemberInfos.size()) | |||
2079 | // For any type id used on a global's type metadata, create the type id | |||
2080 | // summary resolution regardless of whether we can devirtualize, so that | |||
2081 | // lower type tests knows the type id is not Unsat. If it was not used on | |||
2082 | // a global's type metadata, the TypeIdMap entry set will be empty, and | |||
2083 | // we don't want to create an entry (with the default Unknown type | |||
2084 | // resolution), which can prevent detection of the Unsat. | |||
2085 | Res = &ExportSummary | |||
2086 | ->getOrInsertTypeIdSummary( | |||
2087 | cast<MDString>(S.first.TypeID)->getString()) | |||
2088 | .WPDRes[S.first.ByteOffset]; | |||
2089 | if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos, | |||
2090 | S.first.ByteOffset)) { | |||
2091 | ||||
2092 | if (!trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res)) { | |||
2093 | DidVirtualConstProp |= | |||
2094 | tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first); | |||
2095 | ||||
2096 | tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first); | |||
2097 | } | |||
2098 | ||||
2099 | // Collect functions devirtualized at least for one call site for stats. | |||
2100 | if (RemarksEnabled) | |||
2101 | for (const auto &T : TargetsForSlot) | |||
2102 | if (T.WasDevirt) | |||
2103 | DevirtTargets[std::string(T.Fn->getName())] = T.Fn; | |||
2104 | } | |||
2105 | ||||
2106 | // CFI-specific: if we are exporting and any llvm.type.checked.load | |||
2107 | // intrinsics were *not* devirtualized, we need to add the resulting | |||
2108 | // llvm.type.test intrinsics to the function summaries so that the | |||
2109 | // LowerTypeTests pass will export them. | |||
2110 | if (ExportSummary && isa<MDString>(S.first.TypeID)) { | |||
2111 | auto GUID = | |||
2112 | GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString()); | |||
2113 | for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers) | |||
2114 | FS->addTypeTest(GUID); | |||
2115 | for (auto &CCS : S.second.ConstCSInfo) | |||
2116 | for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers) | |||
2117 | FS->addTypeTest(GUID); | |||
2118 | } | |||
2119 | } | |||
2120 | ||||
2121 | if (RemarksEnabled) { | |||
2122 | // Generate remarks for each devirtualized function. | |||
2123 | for (const auto &DT : DevirtTargets) { | |||
2124 | Function *F = DT.second; | |||
2125 | ||||
2126 | using namespace ore; | |||
2127 | OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "Devirtualized", F) | |||
2128 | << "devirtualized " | |||
2129 | << NV("FunctionName", DT.first)); | |||
2130 | } | |||
2131 | } | |||
2132 | ||||
2133 | removeRedundantTypeTests(); | |||
2134 | ||||
2135 | // Rebuild each global we touched as part of virtual constant propagation to | |||
2136 | // include the before and after bytes. | |||
2137 | if (DidVirtualConstProp) | |||
2138 | for (VTableBits &B : Bits) | |||
2139 | rebuildGlobal(B); | |||
2140 | ||||
2141 | // We have lowered or deleted the type instrinsics, so we will no | |||
2142 | // longer have enough information to reason about the liveness of virtual | |||
2143 | // function pointers in GlobalDCE. | |||
2144 | for (GlobalVariable &GV : M.globals()) | |||
2145 | GV.eraseMetadata(LLVMContext::MD_vcall_visibility); | |||
2146 | ||||
2147 | return true; | |||
2148 | } | |||
2149 | ||||
2150 | void DevirtIndex::run() { | |||
2151 | if (ExportSummary.typeIdCompatibleVtableMap().empty()) | |||
2152 | return; | |||
2153 | ||||
2154 | DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID; | |||
2155 | for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) { | |||
2156 | NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first); | |||
2157 | } | |||
2158 | ||||
2159 | // Collect information from summary about which calls to try to devirtualize. | |||
2160 | for (auto &P : ExportSummary) { | |||
2161 | for (auto &S : P.second.SummaryList) { | |||
2162 | auto *FS = dyn_cast<FunctionSummary>(S.get()); | |||
2163 | if (!FS) | |||
2164 | continue; | |||
2165 | // FIXME: Only add live functions. | |||
2166 | for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) { | |||
2167 | for (StringRef Name : NameByGUID[VF.GUID]) { | |||
2168 | CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS); | |||
2169 | } | |||
2170 | } | |||
2171 | for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) { | |||
2172 | for (StringRef Name : NameByGUID[VF.GUID]) { | |||
2173 | CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS); | |||
2174 | } | |||
2175 | } | |||
2176 | for (const FunctionSummary::ConstVCall &VC : | |||
2177 | FS->type_test_assume_const_vcalls()) { | |||
2178 | for (StringRef Name : NameByGUID[VC.VFunc.GUID]) { | |||
2179 | CallSlots[{Name, VC.VFunc.Offset}] | |||
2180 | .ConstCSInfo[VC.Args] | |||
2181 | .addSummaryTypeTestAssumeUser(FS); | |||
2182 | } | |||
2183 | } | |||
2184 | for (const FunctionSummary::ConstVCall &VC : | |||
2185 | FS->type_checked_load_const_vcalls()) { | |||
2186 | for (StringRef Name : NameByGUID[VC.VFunc.GUID]) { | |||
2187 | CallSlots[{Name, VC.VFunc.Offset}] | |||
2188 | .ConstCSInfo[VC.Args] | |||
2189 | .addSummaryTypeCheckedLoadUser(FS); | |||
2190 | } | |||
2191 | } | |||
2192 | } | |||
2193 | } | |||
2194 | ||||
2195 | std::set<ValueInfo> DevirtTargets; | |||
2196 | // For each (type, offset) pair: | |||
2197 | for (auto &S : CallSlots) { | |||
2198 | // Search each of the members of the type identifier for the virtual | |||
2199 | // function implementation at offset S.first.ByteOffset, and add to | |||
2200 | // TargetsForSlot. | |||
2201 | std::vector<ValueInfo> TargetsForSlot; | |||
2202 | auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID); | |||
2203 | assert(TidSummary)((TidSummary) ? static_cast<void> (0) : __assert_fail ( "TidSummary", "/build/llvm-toolchain-snapshot-13~++20210216111115+df22133a8a40/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp" , 2203, __PRETTY_FUNCTION__)); | |||
2204 | // Create the type id summary resolution regardlness of whether we can | |||
2205 | // devirtualize, so that lower type tests knows the type id is used on | |||
2206 | // a global and not Unsat. | |||
2207 | WholeProgramDevirtResolution *Res = | |||
2208 | &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID) | |||
2209 | .WPDRes[S.first.ByteOffset]; | |||
2210 | if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary, | |||
2211 | S.first.ByteOffset)) { | |||
2212 | ||||
2213 | if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res, | |||
2214 | DevirtTargets)) | |||
2215 | continue; | |||
2216 | } | |||
2217 | } | |||
2218 | ||||
2219 | // Optionally have the thin link print message for each devirtualized | |||
2220 | // function. | |||
2221 | if (PrintSummaryDevirt) | |||
2222 | for (const auto &DT : DevirtTargets) | |||
2223 | errs() << "Devirtualized call to " << DT << "\n"; | |||
2224 | } |