| 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/thin and non-LTO |
| 28 | // pipelines: |
| 29 | // |
| 30 | // During regular LTO, the pass determines the best optimization for each |
| 31 | // virtual call and applies the resolutions directly to virtual calls that are |
| 32 | // eligible for virtual call optimization (i.e. calls that use either of the |
| 33 | // llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics). |
| 34 | // |
| 35 | // During hybrid Regular/ThinLTO, the pass operates in two phases: |
| 36 | // - Export phase: this is run during the thin link over a single merged module |
| 37 | // that contains all vtables with !type metadata that participate in the link. |
| 38 | // The pass computes a resolution for each virtual call and stores it in the |
| 39 | // type identifier summary. |
| 40 | // - Import phase: this is run during the thin backends over the individual |
| 41 | // modules. The pass applies the resolutions previously computed during the |
| 42 | // import phase to each eligible virtual call. |
| 43 | // |
| 44 | // During ThinLTO, the pass operates in two phases: |
| 45 | // - Export phase: this is run during the thin link over the index which |
| 46 | // contains a summary of all vtables with !type metadata that participate in |
| 47 | // the link. It computes a resolution for each virtual call and stores it in |
| 48 | // the type identifier summary. Only single implementation devirtualization |
| 49 | // is supported. |
| 50 | // - Import phase: (same as with hybrid case above). |
| 51 | // |
| 52 | // During Speculative devirtualization mode -not restricted to LTO-: |
| 53 | // - The pass applies speculative devirtualization without requiring any type of |
| 54 | // visibility. |
| 55 | // - Skips other features like virtual constant propagation, uniform return |
| 56 | // value optimization, unique return value optimization and branch funnels as |
| 57 | // they need LTO. |
| 58 | // - This mode is enabled via 'devirtualize-speculatively' flag. |
| 59 | // |
| 60 | //===----------------------------------------------------------------------===// |
| 61 | |
| 62 | #include "llvm/Transforms/IPO/WholeProgramDevirt.h" |
| 63 | #include "llvm/ADT/ArrayRef.h" |
| 64 | #include "llvm/ADT/DenseMap.h" |
| 65 | #include "llvm/ADT/DenseMapInfo.h" |
| 66 | #include "llvm/ADT/DenseSet.h" |
| 67 | #include "llvm/ADT/MapVector.h" |
| 68 | #include "llvm/ADT/SmallPtrSet.h" |
| 69 | #include "llvm/ADT/SmallVector.h" |
| 70 | #include "llvm/ADT/Statistic.h" |
| 71 | #include "llvm/Analysis/AssumptionCache.h" |
| 72 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
| 73 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
| 74 | #include "llvm/Analysis/ModuleSummaryAnalysis.h" |
| 75 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
| 76 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
| 77 | #include "llvm/Analysis/TypeMetadataUtils.h" |
| 78 | #include "llvm/Bitcode/BitcodeReader.h" |
| 79 | #include "llvm/Bitcode/BitcodeWriter.h" |
| 80 | #include "llvm/IR/Constants.h" |
| 81 | #include "llvm/IR/DataLayout.h" |
| 82 | #include "llvm/IR/DebugLoc.h" |
| 83 | #include "llvm/IR/DerivedTypes.h" |
| 84 | #include "llvm/IR/DiagnosticInfo.h" |
| 85 | #include "llvm/IR/Dominators.h" |
| 86 | #include "llvm/IR/Function.h" |
| 87 | #include "llvm/IR/GlobalAlias.h" |
| 88 | #include "llvm/IR/GlobalVariable.h" |
| 89 | #include "llvm/IR/IRBuilder.h" |
| 90 | #include "llvm/IR/InstrTypes.h" |
| 91 | #include "llvm/IR/Instruction.h" |
| 92 | #include "llvm/IR/Instructions.h" |
| 93 | #include "llvm/IR/Intrinsics.h" |
| 94 | #include "llvm/IR/LLVMContext.h" |
| 95 | #include "llvm/IR/MDBuilder.h" |
| 96 | #include "llvm/IR/Metadata.h" |
| 97 | #include "llvm/IR/Module.h" |
| 98 | #include "llvm/IR/ModuleSummaryIndexYAML.h" |
| 99 | #include "llvm/IR/PassManager.h" |
| 100 | #include "llvm/IR/ProfDataUtils.h" |
| 101 | #include "llvm/Support/Casting.h" |
| 102 | #include "llvm/Support/CommandLine.h" |
| 103 | #include "llvm/Support/DebugCounter.h" |
| 104 | #include "llvm/Support/Errc.h" |
| 105 | #include "llvm/Support/Error.h" |
| 106 | #include "llvm/Support/FileSystem.h" |
| 107 | #include "llvm/Support/GlobPattern.h" |
| 108 | #include "llvm/Support/TimeProfiler.h" |
| 109 | #include "llvm/TargetParser/Triple.h" |
| 110 | #include "llvm/Transforms/IPO.h" |
| 111 | #include "llvm/Transforms/IPO/FunctionAttrs.h" |
| 112 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| 113 | #include "llvm/Transforms/Utils/CallPromotionUtils.h" |
| 114 | #include "llvm/Transforms/Utils/Evaluator.h" |
| 115 | #include <algorithm> |
| 116 | #include <cmath> |
| 117 | #include <cstddef> |
| 118 | #include <map> |
| 119 | #include <set> |
| 120 | #include <string> |
| 121 | |
| 122 | using namespace llvm; |
| 123 | using namespace wholeprogramdevirt; |
| 124 | |
| 125 | #define DEBUG_TYPE "wholeprogramdevirt" |
| 126 | |
| 127 | STATISTIC(NumDevirtTargets, "Number of whole program devirtualization targets"); |
| 128 | STATISTIC(NumSingleImpl, "Number of single implementation devirtualizations"); |
| 129 | STATISTIC(NumBranchFunnel, "Number of branch funnels"); |
| 130 | STATISTIC(NumUniformRetVal, "Number of uniform return value optimizations"); |
| 131 | STATISTIC(NumUniqueRetVal, "Number of unique return value optimizations"); |
| 132 | STATISTIC(NumVirtConstProp1Bit, |
| 133 | "Number of 1 bit virtual constant propagations"); |
| 134 | STATISTIC(NumVirtConstProp, "Number of virtual constant propagations"); |
| 135 | DEBUG_COUNTER(CallsToDevirt, "calls-to-devirt", |
| 136 | "Controls how many calls should be devirtualized."); |
| 137 | |
| 138 | namespace llvm { |
| 139 | |
| 140 | static cl::opt<PassSummaryAction> ClSummaryAction( |
| 141 | "wholeprogramdevirt-summary-action", |
| 142 | cl::desc("What to do with the summary when running this pass"), |
| 143 | cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), |
| 144 | clEnumValN(PassSummaryAction::Import, "import", |
| 145 | "Import typeid resolutions from summary and globals"), |
| 146 | clEnumValN(PassSummaryAction::Export, "export", |
| 147 | "Export typeid resolutions to summary and globals")), |
| 148 | cl::Hidden); |
| 149 | |
| 150 | static cl::opt<std::string> ClReadSummary( |
| 151 | "wholeprogramdevirt-read-summary", |
| 152 | cl::desc( |
| 153 | "Read summary from given bitcode or YAML file before running pass"), |
| 154 | cl::Hidden); |
| 155 | |
| 156 | static cl::opt<std::string> ClWriteSummary( |
| 157 | "wholeprogramdevirt-write-summary", |
| 158 | cl::desc("Write summary to given bitcode or YAML file after running pass. " |
| 159 | "Output file format is deduced from extension: *.bc means writing " |
| 160 | "bitcode, otherwise YAML"), |
| 161 | cl::Hidden); |
| 162 | |
| 163 | // TODO: This option eventually should support any public visibility vtables |
| 164 | // with/out LTO. |
| 165 | static cl::opt<bool> ClDevirtualizeSpeculatively( |
| 166 | "devirtualize-speculatively", |
| 167 | cl::desc("Enable speculative devirtualization optimization"), |
| 168 | cl::init(Val: false)); |
| 169 | |
| 170 | static cl::opt<unsigned> |
| 171 | ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden, |
| 172 | cl::init(Val: 10), |
| 173 | cl::desc("Maximum number of call targets per " |
| 174 | "call site to enable branch funnels")); |
| 175 | |
| 176 | static cl::opt<bool> |
| 177 | PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden, |
| 178 | cl::desc("Print index-based devirtualization messages")); |
| 179 | |
| 180 | /// Provide a way to force enable whole program visibility in tests. |
| 181 | /// This is needed to support legacy tests that don't contain |
| 182 | /// !vcall_visibility metadata (the mere presense of type tests |
| 183 | /// previously implied hidden visibility). |
| 184 | static cl::opt<bool> |
| 185 | WholeProgramVisibility("whole-program-visibility", cl::Hidden, |
| 186 | cl::desc("Enable whole program visibility")); |
| 187 | |
| 188 | /// Provide a way to force disable whole program for debugging or workarounds, |
| 189 | /// when enabled via the linker. |
| 190 | static cl::opt<bool> DisableWholeProgramVisibility( |
| 191 | "disable-whole-program-visibility", cl::Hidden, |
| 192 | cl::desc("Disable whole program visibility (overrides enabling options)")); |
| 193 | |
| 194 | /// Provide way to prevent certain function from being devirtualized |
| 195 | static cl::list<std::string> |
| 196 | SkipFunctionNames("wholeprogramdevirt-skip", |
| 197 | cl::desc("Prevent function(s) from being devirtualized"), |
| 198 | cl::Hidden, cl::CommaSeparated); |
| 199 | |
| 200 | } // end namespace llvm |
| 201 | |
| 202 | /// With Clang, a pure virtual class's deleting destructor is emitted as a |
| 203 | /// `llvm.trap` intrinsic followed by an unreachable IR instruction. In the |
| 204 | /// context of whole program devirtualization, the deleting destructor of a pure |
| 205 | /// virtual class won't be invoked by the source code so safe to skip as a |
| 206 | /// devirtualize target. |
| 207 | /// |
| 208 | /// However, not all unreachable functions are safe to skip. In some cases, the |
| 209 | /// program intends to run such functions and terminate, for instance, a unit |
| 210 | /// test may run a death test. A non-test program might (or allowed to) invoke |
| 211 | /// such functions to report failures (whether/when it's a good practice or not |
| 212 | /// is a different topic). |
| 213 | /// |
| 214 | /// This option is enabled to keep an unreachable function as a possible |
| 215 | /// devirtualize target to conservatively keep the program behavior. |
| 216 | /// |
| 217 | /// TODO: Make a pure virtual class's deleting destructor precisely identifiable |
| 218 | /// in Clang's codegen for more devirtualization in LLVM. |
| 219 | static cl::opt<bool> WholeProgramDevirtKeepUnreachableFunction( |
| 220 | "wholeprogramdevirt-keep-unreachable-function", |
| 221 | cl::desc("Regard unreachable functions as possible devirtualize targets."), |
| 222 | cl::Hidden, cl::init(Val: true)); |
| 223 | |
| 224 | /// Mechanism to add runtime checking of devirtualization decisions, optionally |
| 225 | /// trapping or falling back to indirect call on any that are not correct. |
| 226 | /// Trapping mode is useful for debugging undefined behavior leading to failures |
| 227 | /// with WPD. Fallback mode is useful for ensuring safety when whole program |
| 228 | /// visibility may be compromised. |
| 229 | enum WPDCheckMode { None, Trap, Fallback }; |
| 230 | static cl::opt<WPDCheckMode> DevirtCheckMode( |
| 231 | "wholeprogramdevirt-check", cl::Hidden, |
| 232 | cl::desc("Type of checking for incorrect devirtualizations"), |
| 233 | cl::values(clEnumValN(WPDCheckMode::None, "none", "No checking"), |
| 234 | clEnumValN(WPDCheckMode::Trap, "trap", "Trap when incorrect"), |
| 235 | clEnumValN(WPDCheckMode::Fallback, "fallback", |
| 236 | "Fallback to indirect when incorrect"))); |
| 237 | |
| 238 | namespace { |
| 239 | struct PatternList { |
| 240 | std::vector<GlobPattern> Patterns; |
| 241 | template <class T> void init(const T &StringList) { |
| 242 | for (const auto &S : StringList) |
| 243 | if (Expected<GlobPattern> Pat = GlobPattern::create(Pat: S)) |
| 244 | Patterns.push_back(x: std::move(*Pat)); |
| 245 | } |
| 246 | bool match(StringRef S) { |
| 247 | for (const GlobPattern &P : Patterns) |
| 248 | if (P.match(S)) |
| 249 | return true; |
| 250 | return false; |
| 251 | } |
| 252 | }; |
| 253 | } // namespace |
| 254 | |
| 255 | // Find the minimum offset that we may store a value of size Size bits at. If |
| 256 | // IsAfter is set, look for an offset before the object, otherwise look for an |
| 257 | // offset after the object. |
| 258 | uint64_t |
| 259 | wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets, |
| 260 | bool IsAfter, uint64_t Size) { |
| 261 | // Find a minimum offset taking into account only vtable sizes. |
| 262 | uint64_t MinByte = 0; |
| 263 | for (const VirtualCallTarget &Target : Targets) { |
| 264 | if (IsAfter) |
| 265 | MinByte = std::max(a: MinByte, b: Target.minAfterBytes()); |
| 266 | else |
| 267 | MinByte = std::max(a: MinByte, b: Target.minBeforeBytes()); |
| 268 | } |
| 269 | |
| 270 | // Build a vector of arrays of bytes covering, for each target, a slice of the |
| 271 | // used region (see AccumBitVector::BytesUsed in |
| 272 | // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively, |
| 273 | // this aligns the used regions to start at MinByte. |
| 274 | // |
| 275 | // In this example, A, B and C are vtables, # is a byte already allocated for |
| 276 | // a virtual function pointer, AAAA... (etc.) are the used regions for the |
| 277 | // vtables and Offset(X) is the value computed for the Offset variable below |
| 278 | // for X. |
| 279 | // |
| 280 | // Offset(A) |
| 281 | // | | |
| 282 | // |MinByte |
| 283 | // A: ################AAAAAAAA|AAAAAAAA |
| 284 | // B: ########BBBBBBBBBBBBBBBB|BBBB |
| 285 | // C: ########################|CCCCCCCCCCCCCCCC |
| 286 | // | Offset(B) | |
| 287 | // |
| 288 | // This code produces the slices of A, B and C that appear after the divider |
| 289 | // at MinByte. |
| 290 | std::vector<ArrayRef<uint8_t>> Used; |
| 291 | for (const VirtualCallTarget &Target : Targets) { |
| 292 | ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed |
| 293 | : Target.TM->Bits->Before.BytesUsed; |
| 294 | uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes() |
| 295 | : MinByte - Target.minBeforeBytes(); |
| 296 | |
| 297 | // Disregard used regions that are smaller than Offset. These are |
| 298 | // effectively all-free regions that do not need to be checked. |
| 299 | if (VTUsed.size() > Offset) |
| 300 | Used.push_back(x: VTUsed.slice(N: Offset)); |
| 301 | } |
| 302 | |
| 303 | if (Size == 1) { |
| 304 | // Find a free bit in each member of Used. |
| 305 | for (unsigned I = 0;; ++I) { |
| 306 | uint8_t BitsUsed = 0; |
| 307 | for (auto &&B : Used) |
| 308 | if (I < B.size()) |
| 309 | BitsUsed |= B[I]; |
| 310 | if (BitsUsed != 0xff) |
| 311 | return (MinByte + I) * 8 + llvm::countr_zero(Val: uint8_t(~BitsUsed)); |
| 312 | } |
| 313 | } else { |
| 314 | // Find a free (Size/8) byte region in each member of Used. |
| 315 | // FIXME: see if alignment helps. |
| 316 | for (unsigned I = 0;; ++I) { |
| 317 | for (auto &&B : Used) { |
| 318 | unsigned Byte = 0; |
| 319 | while ((I + Byte) < B.size() && Byte < (Size / 8)) { |
| 320 | if (B[I + Byte]) |
| 321 | goto NextI; |
| 322 | ++Byte; |
| 323 | } |
| 324 | } |
| 325 | // Rounding up ensures the constant is always stored at address we |
| 326 | // can directly load from without misalignment. |
| 327 | return alignTo(Value: (MinByte + I) * 8, Align: Size); |
| 328 | NextI:; |
| 329 | } |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | void wholeprogramdevirt::setBeforeReturnValues( |
| 334 | MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore, |
| 335 | unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { |
| 336 | if (BitWidth == 1) |
| 337 | OffsetByte = -(AllocBefore / 8 + 1); |
| 338 | else |
| 339 | OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8); |
| 340 | OffsetBit = AllocBefore % 8; |
| 341 | |
| 342 | for (VirtualCallTarget &Target : Targets) { |
| 343 | if (BitWidth == 1) |
| 344 | Target.setBeforeBit(AllocBefore); |
| 345 | else |
| 346 | Target.setBeforeBytes(Pos: AllocBefore, Size: (BitWidth + 7) / 8); |
| 347 | } |
| 348 | } |
| 349 | |
| 350 | void wholeprogramdevirt::setAfterReturnValues( |
| 351 | MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter, |
| 352 | unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { |
| 353 | if (BitWidth == 1) |
| 354 | OffsetByte = AllocAfter / 8; |
| 355 | else |
| 356 | OffsetByte = (AllocAfter + 7) / 8; |
| 357 | OffsetBit = AllocAfter % 8; |
| 358 | |
| 359 | for (VirtualCallTarget &Target : Targets) { |
| 360 | if (BitWidth == 1) |
| 361 | Target.setAfterBit(AllocAfter); |
| 362 | else |
| 363 | Target.setAfterBytes(Pos: AllocAfter, Size: (BitWidth + 7) / 8); |
| 364 | } |
| 365 | } |
| 366 | |
| 367 | VirtualCallTarget::VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM) |
| 368 | : Fn(Fn), TM(TM), |
| 369 | IsBigEndian(Fn->getDataLayout().isBigEndian()), |
| 370 | WasDevirt(false) {} |
| 371 | |
| 372 | namespace { |
| 373 | |
| 374 | // A slot in a set of virtual tables. The TypeID identifies the set of virtual |
| 375 | // tables, and the ByteOffset is the offset in bytes from the address point to |
| 376 | // the virtual function pointer. |
| 377 | struct VTableSlot { |
| 378 | Metadata *TypeID; |
| 379 | uint64_t ByteOffset; |
| 380 | }; |
| 381 | |
| 382 | } // end anonymous namespace |
| 383 | |
| 384 | template <> struct llvm::DenseMapInfo<VTableSlot> { |
| 385 | static unsigned getHashValue(const VTableSlot &I) { |
| 386 | return DenseMapInfo<Metadata *>::getHashValue(PtrVal: I.TypeID) ^ |
| 387 | DenseMapInfo<uint64_t>::getHashValue(Val: I.ByteOffset); |
| 388 | } |
| 389 | static bool isEqual(const VTableSlot &LHS, |
| 390 | const VTableSlot &RHS) { |
| 391 | return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset; |
| 392 | } |
| 393 | }; |
| 394 | |
| 395 | template <> struct llvm::DenseMapInfo<VTableSlotSummary> { |
| 396 | static unsigned getHashValue(const VTableSlotSummary &I) { |
| 397 | return DenseMapInfo<StringRef>::getHashValue(Val: I.TypeID) ^ |
| 398 | DenseMapInfo<uint64_t>::getHashValue(Val: I.ByteOffset); |
| 399 | } |
| 400 | static bool isEqual(const VTableSlotSummary &LHS, |
| 401 | const VTableSlotSummary &RHS) { |
| 402 | return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset; |
| 403 | } |
| 404 | }; |
| 405 | |
| 406 | // Returns true if the function must be unreachable based on ValueInfo. |
| 407 | // |
| 408 | // In particular, identifies a function as unreachable in the following |
| 409 | // conditions |
| 410 | // 1) All summaries are live. |
| 411 | // 2) All function summaries indicate it's unreachable |
| 412 | // 3) There is no non-function with the same GUID (which is rare) |
| 413 | static bool mustBeUnreachableFunction(ValueInfo TheFnVI) { |
| 414 | if (WholeProgramDevirtKeepUnreachableFunction) |
| 415 | return false; |
| 416 | |
| 417 | if ((!TheFnVI) || TheFnVI.getSummaryList().empty()) { |
| 418 | // Returns false if ValueInfo is absent, or the summary list is empty |
| 419 | // (e.g., function declarations). |
| 420 | return false; |
| 421 | } |
| 422 | |
| 423 | for (const auto &Summary : TheFnVI.getSummaryList()) { |
| 424 | // Conservatively returns false if any non-live functions are seen. |
| 425 | // In general either all summaries should be live or all should be dead. |
| 426 | if (!Summary->isLive()) |
| 427 | return false; |
| 428 | if (auto *FS = dyn_cast<FunctionSummary>(Val: Summary->getBaseObject())) { |
| 429 | if (!FS->fflags().MustBeUnreachable) |
| 430 | return false; |
| 431 | } |
| 432 | // Be conservative if a non-function has the same GUID (which is rare). |
| 433 | else |
| 434 | return false; |
| 435 | } |
| 436 | // All function summaries are live and all of them agree that the function is |
| 437 | // unreachble. |
| 438 | return true; |
| 439 | } |
| 440 | |
| 441 | namespace { |
| 442 | // A virtual call site. VTable is the loaded virtual table pointer, and CS is |
| 443 | // the indirect virtual call. |
| 444 | struct VirtualCallSite { |
| 445 | Value *VTable = nullptr; |
| 446 | CallBase &CB; |
| 447 | |
| 448 | // If non-null, this field points to the associated unsafe use count stored in |
| 449 | // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description |
| 450 | // of that field for details. |
| 451 | unsigned *NumUnsafeUses = nullptr; |
| 452 | |
| 453 | void |
| 454 | emitRemark(const StringRef OptName, const StringRef TargetName, |
| 455 | function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter) { |
| 456 | Function *F = CB.getCaller(); |
| 457 | DebugLoc DLoc = CB.getDebugLoc(); |
| 458 | BasicBlock *Block = CB.getParent(); |
| 459 | |
| 460 | using namespace ore; |
| 461 | OREGetter(*F).emit(OptDiag: OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block) |
| 462 | << NV("Optimization", OptName) |
| 463 | << ": devirtualized a call to " |
| 464 | << NV("FunctionName", TargetName)); |
| 465 | } |
| 466 | |
| 467 | void replaceAndErase( |
| 468 | const StringRef OptName, const StringRef TargetName, bool RemarksEnabled, |
| 469 | function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter, |
| 470 | Value *New) { |
| 471 | if (RemarksEnabled) |
| 472 | emitRemark(OptName, TargetName, OREGetter); |
| 473 | CB.replaceAllUsesWith(V: New); |
| 474 | if (auto *II = dyn_cast<InvokeInst>(Val: &CB)) { |
| 475 | UncondBrInst::Create(Target: II->getNormalDest(), InsertBefore: CB.getIterator()); |
| 476 | II->getUnwindDest()->removePredecessor(Pred: II->getParent()); |
| 477 | } |
| 478 | CB.eraseFromParent(); |
| 479 | // This use is no longer unsafe. |
| 480 | if (NumUnsafeUses) |
| 481 | --*NumUnsafeUses; |
| 482 | } |
| 483 | }; |
| 484 | |
| 485 | // Call site information collected for a specific VTableSlot and possibly a list |
| 486 | // of constant integer arguments. The grouping by arguments is handled by the |
| 487 | // VTableSlotInfo class. |
| 488 | struct CallSiteInfo { |
| 489 | /// The set of call sites for this slot. Used during regular LTO and the |
| 490 | /// import phase of ThinLTO (as well as the export phase of ThinLTO for any |
| 491 | /// call sites that appear in the merged module itself); in each of these |
| 492 | /// cases we are directly operating on the call sites at the IR level. |
| 493 | std::vector<VirtualCallSite> CallSites; |
| 494 | |
| 495 | /// Whether all call sites represented by this CallSiteInfo, including those |
| 496 | /// in summaries, have been devirtualized. This starts off as true because a |
| 497 | /// default constructed CallSiteInfo represents no call sites. |
| 498 | /// |
| 499 | /// If at the end of the pass there are still undevirtualized calls, we will |
| 500 | /// need to add a use of llvm.type.test to each of the function summaries in |
| 501 | /// the vector. |
| 502 | bool AllCallSitesDevirted = true; |
| 503 | |
| 504 | // These fields are used during the export phase of ThinLTO and reflect |
| 505 | // information collected from function summaries. |
| 506 | |
| 507 | /// CFI-specific: a vector containing the list of function summaries that use |
| 508 | /// the llvm.type.checked.load intrinsic and therefore will require |
| 509 | /// resolutions for llvm.type.test in order to implement CFI checks if |
| 510 | /// devirtualization was unsuccessful. |
| 511 | std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers; |
| 512 | |
| 513 | /// A vector containing the list of function summaries that use |
| 514 | /// assume(llvm.type.test). |
| 515 | std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers; |
| 516 | |
| 517 | bool isExported() const { |
| 518 | return !SummaryTypeCheckedLoadUsers.empty() || |
| 519 | !SummaryTypeTestAssumeUsers.empty(); |
| 520 | } |
| 521 | |
| 522 | void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) { |
| 523 | SummaryTypeCheckedLoadUsers.push_back(x: FS); |
| 524 | AllCallSitesDevirted = false; |
| 525 | } |
| 526 | |
| 527 | void addSummaryTypeTestAssumeUser(FunctionSummary *FS) { |
| 528 | SummaryTypeTestAssumeUsers.push_back(x: FS); |
| 529 | AllCallSitesDevirted = false; |
| 530 | } |
| 531 | |
| 532 | void markDevirt() { AllCallSitesDevirted = true; } |
| 533 | }; |
| 534 | |
| 535 | // Call site information collected for a specific VTableSlot. |
| 536 | struct VTableSlotInfo { |
| 537 | // The set of call sites which do not have all constant integer arguments |
| 538 | // (excluding "this"). |
| 539 | CallSiteInfo CSInfo; |
| 540 | |
| 541 | // The set of call sites with all constant integer arguments (excluding |
| 542 | // "this"), grouped by argument list. |
| 543 | std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo; |
| 544 | |
| 545 | void addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses); |
| 546 | |
| 547 | private: |
| 548 | CallSiteInfo &findCallSiteInfo(CallBase &CB); |
| 549 | }; |
| 550 | |
| 551 | CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) { |
| 552 | std::vector<uint64_t> Args; |
| 553 | auto *CBType = dyn_cast<IntegerType>(Val: CB.getType()); |
| 554 | if (!CBType || CBType->getBitWidth() > 64 || CB.arg_empty()) |
| 555 | return CSInfo; |
| 556 | for (auto &&Arg : drop_begin(RangeOrContainer: CB.args())) { |
| 557 | auto *CI = dyn_cast<ConstantInt>(Val&: Arg); |
| 558 | if (!CI || CI->getBitWidth() > 64) |
| 559 | return CSInfo; |
| 560 | Args.push_back(x: CI->getZExtValue()); |
| 561 | } |
| 562 | return ConstCSInfo[Args]; |
| 563 | } |
| 564 | |
| 565 | void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB, |
| 566 | unsigned *NumUnsafeUses) { |
| 567 | auto &CSI = findCallSiteInfo(CB); |
| 568 | CSI.AllCallSitesDevirted = false; |
| 569 | CSI.CallSites.push_back(x: {.VTable: VTable, .CB: CB, .NumUnsafeUses: NumUnsafeUses}); |
| 570 | } |
| 571 | |
| 572 | struct DevirtModule { |
| 573 | Module &M; |
| 574 | ModuleAnalysisManager &MAM; |
| 575 | FunctionAnalysisManager &FAM; |
| 576 | |
| 577 | ModuleSummaryIndex *const ExportSummary; |
| 578 | const ModuleSummaryIndex *const ImportSummary; |
| 579 | |
| 580 | IntegerType *const Int8Ty; |
| 581 | PointerType *const Int8PtrTy; |
| 582 | IntegerType *const Int32Ty; |
| 583 | IntegerType *const Int64Ty; |
| 584 | IntegerType *const IntPtrTy; |
| 585 | /// Sizeless array type, used for imported vtables. This provides a signal |
| 586 | /// to analyzers that these imports may alias, as they do for example |
| 587 | /// when multiple unique return values occur in the same vtable. |
| 588 | ArrayType *const Int8Arr0Ty; |
| 589 | |
| 590 | const bool RemarksEnabled; |
| 591 | std::function<OptimizationRemarkEmitter &(Function &)> OREGetter; |
| 592 | MapVector<VTableSlot, VTableSlotInfo> CallSlots; |
| 593 | |
| 594 | // Calls that have already been optimized. We may add a call to multiple |
| 595 | // VTableSlotInfos if vtable loads are coalesced and need to make sure not to |
| 596 | // optimize a call more than once. |
| 597 | SmallPtrSet<CallBase *, 8> OptimizedCalls; |
| 598 | |
| 599 | // Store calls that had their ptrauth bundle removed. They are to be deleted |
| 600 | // at the end of the optimization. |
| 601 | SmallVector<CallBase *, 8> CallsWithPtrAuthBundleRemoved; |
| 602 | |
| 603 | // This map keeps track of the number of "unsafe" uses of a loaded function |
| 604 | // pointer. The key is the associated llvm.type.test intrinsic call generated |
| 605 | // by this pass. An unsafe use is one that calls the loaded function pointer |
| 606 | // directly. Every time we eliminate an unsafe use (for example, by |
| 607 | // devirtualizing it or by applying virtual constant propagation), we |
| 608 | // decrement the value stored in this map. If a value reaches zero, we can |
| 609 | // eliminate the type check by RAUWing the associated llvm.type.test call with |
| 610 | // true. |
| 611 | std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest; |
| 612 | PatternList FunctionsToSkip; |
| 613 | |
| 614 | const bool DevirtSpeculatively; |
| 615 | DevirtModule(Module &M, ModuleAnalysisManager &MAM, |
| 616 | ModuleSummaryIndex *ExportSummary, |
| 617 | const ModuleSummaryIndex *ImportSummary, |
| 618 | bool DevirtSpeculatively) |
| 619 | : M(M), MAM(MAM), |
| 620 | FAM(MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager()), |
| 621 | ExportSummary(ExportSummary), ImportSummary(ImportSummary), |
| 622 | Int8Ty(Type::getInt8Ty(C&: M.getContext())), |
| 623 | Int8PtrTy(PointerType::getUnqual(C&: M.getContext())), |
| 624 | Int32Ty(Type::getInt32Ty(C&: M.getContext())), |
| 625 | Int64Ty(Type::getInt64Ty(C&: M.getContext())), |
| 626 | IntPtrTy(M.getDataLayout().getIntPtrType(C&: M.getContext(), AddressSpace: 0)), |
| 627 | Int8Arr0Ty(ArrayType::get(ElementType: Type::getInt8Ty(C&: M.getContext()), NumElements: 0)), |
| 628 | RemarksEnabled(areRemarksEnabled()), |
| 629 | OREGetter([&](Function &F) -> OptimizationRemarkEmitter & { |
| 630 | return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F); |
| 631 | }), |
| 632 | DevirtSpeculatively(DevirtSpeculatively) { |
| 633 | assert(!(ExportSummary && ImportSummary)); |
| 634 | FunctionsToSkip.init(StringList: SkipFunctionNames); |
| 635 | } |
| 636 | |
| 637 | bool areRemarksEnabled(); |
| 638 | |
| 639 | void |
| 640 | scanTypeTestUsers(Function *TypeTestFunc, |
| 641 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap); |
| 642 | void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc); |
| 643 | |
| 644 | void buildTypeIdentifierMap( |
| 645 | std::vector<VTableBits> &Bits, |
| 646 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap); |
| 647 | |
| 648 | bool |
| 649 | tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot, |
| 650 | const std::set<TypeMemberInfo> &TypeMemberInfos, |
| 651 | uint64_t ByteOffset, |
| 652 | ModuleSummaryIndex *ExportSummary); |
| 653 | |
| 654 | void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn, |
| 655 | bool &IsExported); |
| 656 | bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary, |
| 657 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 658 | VTableSlotInfo &SlotInfo, |
| 659 | WholeProgramDevirtResolution *Res); |
| 660 | |
| 661 | void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Function &JT, |
| 662 | bool &IsExported); |
| 663 | void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 664 | VTableSlotInfo &SlotInfo, |
| 665 | WholeProgramDevirtResolution *Res, VTableSlot Slot); |
| 666 | |
| 667 | bool tryEvaluateFunctionsWithArgs( |
| 668 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 669 | ArrayRef<uint64_t> Args); |
| 670 | |
| 671 | void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, |
| 672 | uint64_t TheRetVal); |
| 673 | bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 674 | CallSiteInfo &CSInfo, |
| 675 | WholeProgramDevirtResolution::ByArg *Res); |
| 676 | |
| 677 | // Returns the global symbol name that is used to export information about the |
| 678 | // given vtable slot and list of arguments. |
| 679 | std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 680 | StringRef Name); |
| 681 | |
| 682 | bool shouldExportConstantsAsAbsoluteSymbols(); |
| 683 | |
| 684 | // This function is called during the export phase to create a symbol |
| 685 | // definition containing information about the given vtable slot and list of |
| 686 | // arguments. |
| 687 | void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, |
| 688 | Constant *C); |
| 689 | void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, |
| 690 | uint32_t Const, uint32_t &Storage); |
| 691 | |
| 692 | // This function is called during the import phase to create a reference to |
| 693 | // the symbol definition created during the export phase. |
| 694 | Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 695 | StringRef Name); |
| 696 | Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 697 | StringRef Name, IntegerType *IntTy, |
| 698 | uint32_t Storage); |
| 699 | |
| 700 | Constant *getMemberAddr(const TypeMemberInfo *M); |
| 701 | |
| 702 | void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne, |
| 703 | Constant *UniqueMemberAddr); |
| 704 | bool tryUniqueRetValOpt(unsigned BitWidth, |
| 705 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 706 | CallSiteInfo &CSInfo, |
| 707 | WholeProgramDevirtResolution::ByArg *Res, |
| 708 | VTableSlot Slot, ArrayRef<uint64_t> Args); |
| 709 | |
| 710 | void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName, |
| 711 | Constant *Byte, Constant *Bit); |
| 712 | bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 713 | VTableSlotInfo &SlotInfo, |
| 714 | WholeProgramDevirtResolution *Res, VTableSlot Slot); |
| 715 | |
| 716 | void rebuildGlobal(VTableBits &B); |
| 717 | |
| 718 | // Apply the summary resolution for Slot to all virtual calls in SlotInfo. |
| 719 | void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo); |
| 720 | |
| 721 | // If we were able to eliminate all unsafe uses for a type checked load, |
| 722 | // eliminate the associated type tests by replacing them with true. |
| 723 | void removeRedundantTypeTests(); |
| 724 | |
| 725 | bool run(); |
| 726 | |
| 727 | // Look up the corresponding ValueInfo entry of `TheFn` in `ExportSummary`. |
| 728 | // |
| 729 | // Caller guarantees that `ExportSummary` is not nullptr. |
| 730 | static ValueInfo lookUpFunctionValueInfo(Function *TheFn, |
| 731 | ModuleSummaryIndex *ExportSummary); |
| 732 | |
| 733 | // Returns true if the function definition must be unreachable. |
| 734 | // |
| 735 | // Note if this helper function returns true, `F` is guaranteed |
| 736 | // to be unreachable; if it returns false, `F` might still |
| 737 | // be unreachable but not covered by this helper function. |
| 738 | // |
| 739 | // Implementation-wise, if function definition is present, IR is analyzed; if |
| 740 | // not, look up function flags from ExportSummary as a fallback. |
| 741 | static bool mustBeUnreachableFunction(Function *const F, |
| 742 | ModuleSummaryIndex *ExportSummary); |
| 743 | |
| 744 | // Lower the module using the action and summary passed as command line |
| 745 | // arguments. For testing purposes only. |
| 746 | static bool runForTesting(Module &M, ModuleAnalysisManager &MAM, |
| 747 | bool DevirtSpeculatively); |
| 748 | }; |
| 749 | |
| 750 | struct DevirtIndex { |
| 751 | ModuleSummaryIndex &ExportSummary; |
| 752 | // The set in which to record GUIDs exported from their module by |
| 753 | // devirtualization, used by client to ensure they are not internalized. |
| 754 | std::set<GlobalValue::GUID> &ExportedGUIDs; |
| 755 | // A map in which to record the information necessary to locate the WPD |
| 756 | // resolution for local targets in case they are exported by cross module |
| 757 | // importing. |
| 758 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap; |
| 759 | // We have hardcoded the promoted and renamed function name in the WPD |
| 760 | // summary, so we need to ensure that they will be renamed. Note this and |
| 761 | // that adding the current names to this set ensures we continue to rename |
| 762 | // them. |
| 763 | DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr; |
| 764 | |
| 765 | MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots; |
| 766 | |
| 767 | PatternList FunctionsToSkip; |
| 768 | |
| 769 | DevirtIndex( |
| 770 | ModuleSummaryIndex &ExportSummary, |
| 771 | std::set<GlobalValue::GUID> &ExportedGUIDs, |
| 772 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap, |
| 773 | DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr) |
| 774 | : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs), |
| 775 | LocalWPDTargetsMap(LocalWPDTargetsMap), |
| 776 | ExternallyVisibleSymbolNamesPtr(ExternallyVisibleSymbolNamesPtr) { |
| 777 | FunctionsToSkip.init(StringList: SkipFunctionNames); |
| 778 | } |
| 779 | |
| 780 | bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot, |
| 781 | const TypeIdCompatibleVtableInfo TIdInfo, |
| 782 | uint64_t ByteOffset); |
| 783 | |
| 784 | bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot, |
| 785 | VTableSlotSummary &SlotSummary, |
| 786 | VTableSlotInfo &SlotInfo, |
| 787 | WholeProgramDevirtResolution *Res, |
| 788 | std::set<ValueInfo> &DevirtTargets); |
| 789 | |
| 790 | void run(); |
| 791 | }; |
| 792 | } // end anonymous namespace |
| 793 | |
| 794 | PreservedAnalyses WholeProgramDevirtPass::run(Module &M, |
| 795 | ModuleAnalysisManager &MAM) { |
| 796 | if (UseCommandLine) { |
| 797 | if (!DevirtModule::runForTesting(M, MAM, DevirtSpeculatively: ClDevirtualizeSpeculatively)) |
| 798 | return PreservedAnalyses::all(); |
| 799 | return PreservedAnalyses::none(); |
| 800 | } |
| 801 | |
| 802 | std::optional<ModuleSummaryIndex> Index; |
| 803 | if (!ExportSummary && !ImportSummary && DevirtSpeculatively) { |
| 804 | // Build the ExportSummary from the module. |
| 805 | assert(!ExportSummary && |
| 806 | "ExportSummary is expected to be empty in non-LTO mode"); |
| 807 | ProfileSummaryInfo PSI(M); |
| 808 | Index.emplace(args: buildModuleSummaryIndex(M, GetBFICallback: nullptr, PSI: &PSI)); |
| 809 | ExportSummary = Index.has_value() ? &Index.value() : nullptr; |
| 810 | } |
| 811 | if (!DevirtModule(M, MAM, ExportSummary, ImportSummary, DevirtSpeculatively) |
| 812 | .run()) |
| 813 | return PreservedAnalyses::all(); |
| 814 | return PreservedAnalyses::none(); |
| 815 | } |
| 816 | |
| 817 | // Enable whole program visibility if enabled by client (e.g. linker) or |
| 818 | // internal option, and not force disabled. |
| 819 | bool llvm::hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) { |
| 820 | return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) && |
| 821 | !DisableWholeProgramVisibility; |
| 822 | } |
| 823 | |
| 824 | static bool |
| 825 | typeIDVisibleToRegularObj(StringRef TypeID, |
| 826 | function_ref<bool(StringRef)> IsVisibleToRegularObj) { |
| 827 | // TypeID for member function pointer type is an internal construct |
| 828 | // and won't exist in IsVisibleToRegularObj. The full TypeID |
| 829 | // will be present and participate in invalidation. |
| 830 | if (TypeID.ends_with(Suffix: ".virtual")) |
| 831 | return false; |
| 832 | |
| 833 | // TypeID that doesn't start with Itanium mangling (_ZTS) will be |
| 834 | // non-externally visible types which cannot interact with |
| 835 | // external native files. See CodeGenModule::CreateMetadataIdentifierImpl. |
| 836 | if (!TypeID.consume_front(Prefix: "_ZTS")) |
| 837 | return false; |
| 838 | |
| 839 | // TypeID is keyed off the type name symbol (_ZTS). However, the native |
| 840 | // object may not contain this symbol if it does not contain a key |
| 841 | // function for the base type and thus only contains a reference to the |
| 842 | // type info (_ZTI). To catch this case we query using the type info |
| 843 | // symbol corresponding to the TypeID. |
| 844 | std::string TypeInfo = ("_ZTI"+ TypeID).str(); |
| 845 | return IsVisibleToRegularObj(TypeInfo); |
| 846 | } |
| 847 | |
| 848 | static bool |
| 849 | skipUpdateDueToValidation(GlobalVariable &GV, |
| 850 | function_ref<bool(StringRef)> IsVisibleToRegularObj) { |
| 851 | SmallVector<MDNode *, 2> Types; |
| 852 | GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types); |
| 853 | |
| 854 | for (auto *Type : Types) |
| 855 | if (auto *TypeID = dyn_cast<MDString>(Val: Type->getOperand(I: 1).get())) |
| 856 | return typeIDVisibleToRegularObj(TypeID: TypeID->getString(), |
| 857 | IsVisibleToRegularObj); |
| 858 | |
| 859 | return false; |
| 860 | } |
| 861 | |
| 862 | /// If whole program visibility asserted, then upgrade all public vcall |
| 863 | /// visibility metadata on vtable definitions to linkage unit visibility in |
| 864 | /// Module IR (for regular or hybrid LTO). |
| 865 | void llvm::updateVCallVisibilityInModule( |
| 866 | Module &M, bool WholeProgramVisibilityEnabledInLTO, |
| 867 | const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, |
| 868 | bool ValidateAllVtablesHaveTypeInfos, |
| 869 | function_ref<bool(StringRef)> IsVisibleToRegularObj) { |
| 870 | if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) |
| 871 | return; |
| 872 | |
| 873 | for (GlobalVariable &GV : M.globals()) { |
| 874 | // Add linkage unit visibility to any variable with type metadata, which are |
| 875 | // the vtable definitions. We won't have an existing vcall_visibility |
| 876 | // metadata on vtable definitions with public visibility. |
| 877 | if (GV.hasMetadata(KindID: LLVMContext::MD_type) && |
| 878 | GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic && |
| 879 | // Don't upgrade the visibility for symbols exported to the dynamic |
| 880 | // linker, as we have no information on their eventual use. |
| 881 | !DynamicExportSymbols.count(V: GV.getGUID()) && |
| 882 | // With validation enabled, we want to exclude symbols visible to |
| 883 | // regular objects. Local symbols will be in this group due to the |
| 884 | // current implementation but those with VCallVisibilityTranslationUnit |
| 885 | // will have already been marked in clang so are unaffected. |
| 886 | !(ValidateAllVtablesHaveTypeInfos && |
| 887 | skipUpdateDueToValidation(GV, IsVisibleToRegularObj))) |
| 888 | GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit); |
| 889 | } |
| 890 | } |
| 891 | |
| 892 | void llvm::updatePublicTypeTestCalls(Module &M, |
| 893 | bool WholeProgramVisibilityEnabledInLTO) { |
| 894 | llvm::TimeTraceScope timeScope("Update public type test calls"); |
| 895 | Function *PublicTypeTestFunc = |
| 896 | Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test); |
| 897 | if (!PublicTypeTestFunc) |
| 898 | return; |
| 899 | if (hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) { |
| 900 | Function *TypeTestFunc = |
| 901 | Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::type_test); |
| 902 | for (Use &U : make_early_inc_range(Range: PublicTypeTestFunc->uses())) { |
| 903 | auto *CI = cast<CallInst>(Val: U.getUser()); |
| 904 | auto *NewCI = CallInst::Create( |
| 905 | Func: TypeTestFunc, Args: {CI->getArgOperand(i: 0), CI->getArgOperand(i: 1)}, Bundles: {}, NameStr: "", |
| 906 | InsertBefore: CI->getIterator()); |
| 907 | CI->replaceAllUsesWith(V: NewCI); |
| 908 | CI->eraseFromParent(); |
| 909 | } |
| 910 | } else { |
| 911 | // TODO: Don't replace public type tests when speculative devirtualization |
| 912 | // gets enabled in LTO mode. |
| 913 | auto *True = ConstantInt::getTrue(Context&: M.getContext()); |
| 914 | for (Use &U : make_early_inc_range(Range: PublicTypeTestFunc->uses())) { |
| 915 | auto *CI = cast<CallInst>(Val: U.getUser()); |
| 916 | CI->replaceAllUsesWith(V: True); |
| 917 | CI->eraseFromParent(); |
| 918 | } |
| 919 | } |
| 920 | } |
| 921 | |
| 922 | /// Based on typeID string, get all associated vtable GUIDS that are |
| 923 | /// visible to regular objects. |
| 924 | void llvm::getVisibleToRegularObjVtableGUIDs( |
| 925 | ModuleSummaryIndex &Index, |
| 926 | DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols, |
| 927 | function_ref<bool(StringRef)> IsVisibleToRegularObj) { |
| 928 | for (const auto &TypeID : Index.typeIdCompatibleVtableMap()) { |
| 929 | if (typeIDVisibleToRegularObj(TypeID: TypeID.first, IsVisibleToRegularObj)) |
| 930 | for (const TypeIdOffsetVtableInfo &P : TypeID.second) |
| 931 | VisibleToRegularObjSymbols.insert(V: P.VTableVI.getGUID()); |
| 932 | } |
| 933 | } |
| 934 | |
| 935 | /// If whole program visibility asserted, then upgrade all public vcall |
| 936 | /// visibility metadata on vtable definition summaries to linkage unit |
| 937 | /// visibility in Module summary index (for ThinLTO). |
| 938 | void llvm::updateVCallVisibilityInIndex( |
| 939 | ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, |
| 940 | const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, |
| 941 | const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols) { |
| 942 | if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) |
| 943 | return; |
| 944 | for (auto &P : Index) { |
| 945 | // Don't upgrade the visibility for symbols exported to the dynamic |
| 946 | // linker, as we have no information on their eventual use. |
| 947 | if (DynamicExportSymbols.count(V: P.first)) |
| 948 | continue; |
| 949 | // With validation enabled, we want to exclude symbols visible to regular |
| 950 | // objects. Local symbols will be in this group due to the current |
| 951 | // implementation but those with VCallVisibilityTranslationUnit will have |
| 952 | // already been marked in clang so are unaffected. |
| 953 | if (VisibleToRegularObjSymbols.count(V: P.first)) |
| 954 | continue; |
| 955 | for (auto &S : P.second.getSummaryList()) { |
| 956 | auto *GVar = dyn_cast<GlobalVarSummary>(Val: S.get()); |
| 957 | if (!GVar || |
| 958 | GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic) |
| 959 | continue; |
| 960 | GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit); |
| 961 | } |
| 962 | } |
| 963 | } |
| 964 | |
| 965 | void llvm::runWholeProgramDevirtOnIndex( |
| 966 | ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs, |
| 967 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap, |
| 968 | DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr) { |
| 969 | DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap, |
| 970 | ExternallyVisibleSymbolNamesPtr) |
| 971 | .run(); |
| 972 | } |
| 973 | |
| 974 | void llvm::updateIndexWPDForExports( |
| 975 | ModuleSummaryIndex &Summary, |
| 976 | function_ref<bool(StringRef, ValueInfo)> IsExported, |
| 977 | std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap, |
| 978 | DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr) { |
| 979 | for (auto &T : LocalWPDTargetsMap) { |
| 980 | auto &VI = T.first; |
| 981 | // This was enforced earlier during trySingleImplDevirt. |
| 982 | assert(VI.getSummaryList().size() == 1 && |
| 983 | "Devirt of local target has more than one copy"); |
| 984 | auto &S = VI.getSummaryList()[0]; |
| 985 | if (!IsExported(S->modulePath(), VI)) |
| 986 | continue; |
| 987 | |
| 988 | // It's been exported by a cross module import. |
| 989 | for (auto &SlotSummary : T.second) { |
| 990 | auto *TIdSum = Summary.getTypeIdSummary(TypeId: SlotSummary.TypeID); |
| 991 | assert(TIdSum); |
| 992 | auto WPDRes = TIdSum->WPDRes.find(x: SlotSummary.ByteOffset); |
| 993 | assert(WPDRes != TIdSum->WPDRes.end()); |
| 994 | if (ExternallyVisibleSymbolNamesPtr) |
| 995 | ExternallyVisibleSymbolNamesPtr->insert(V: WPDRes->second.SingleImplName); |
| 996 | WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal( |
| 997 | Name: WPDRes->second.SingleImplName, |
| 998 | ModHash: Summary.getModuleHash(ModPath: S->modulePath())); |
| 999 | } |
| 1000 | } |
| 1001 | } |
| 1002 | |
| 1003 | static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) { |
| 1004 | // Check that summary index contains regular LTO module when performing |
| 1005 | // export to prevent occasional use of index from pure ThinLTO compilation |
| 1006 | // (-fno-split-lto-module). This kind of summary index is passed to |
| 1007 | // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting. |
| 1008 | const auto &ModPaths = Summary->modulePaths(); |
| 1009 | if (ClSummaryAction != PassSummaryAction::Import && |
| 1010 | !ModPaths.contains(Key: ModuleSummaryIndex::getRegularLTOModuleName())) |
| 1011 | return createStringError( |
| 1012 | EC: errc::invalid_argument, |
| 1013 | S: "combined summary should contain Regular LTO module"); |
| 1014 | return ErrorSuccess(); |
| 1015 | } |
| 1016 | |
| 1017 | bool DevirtModule::runForTesting(Module &M, ModuleAnalysisManager &MAM, |
| 1018 | bool DevirtSpeculatively) { |
| 1019 | std::unique_ptr<ModuleSummaryIndex> Summary = |
| 1020 | std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/args: false); |
| 1021 | |
| 1022 | // Handle the command-line summary arguments. This code is for testing |
| 1023 | // purposes only, so we handle errors directly. |
| 1024 | if (!ClReadSummary.empty()) { |
| 1025 | ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: "+ ClReadSummary + |
| 1026 | ": "); |
| 1027 | auto ReadSummaryFile = |
| 1028 | ExitOnErr(errorOrToExpected(EO: MemoryBuffer::getFile(Filename: ClReadSummary))); |
| 1029 | if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr = |
| 1030 | getModuleSummaryIndex(Buffer: *ReadSummaryFile)) { |
| 1031 | Summary = std::move(*SummaryOrErr); |
| 1032 | ExitOnErr(checkCombinedSummaryForTesting(Summary: Summary.get())); |
| 1033 | } else { |
| 1034 | // Try YAML if we've failed with bitcode. |
| 1035 | consumeError(Err: SummaryOrErr.takeError()); |
| 1036 | yaml::Input In(ReadSummaryFile->getBuffer()); |
| 1037 | In >> *Summary; |
| 1038 | ExitOnErr(errorCodeToError(EC: In.error())); |
| 1039 | } |
| 1040 | } |
| 1041 | |
| 1042 | bool Changed = |
| 1043 | DevirtModule(M, MAM, |
| 1044 | ClSummaryAction == PassSummaryAction::Export ? Summary.get() |
| 1045 | : nullptr, |
| 1046 | ClSummaryAction == PassSummaryAction::Import ? Summary.get() |
| 1047 | : nullptr, |
| 1048 | DevirtSpeculatively) |
| 1049 | .run(); |
| 1050 | |
| 1051 | if (!ClWriteSummary.empty()) { |
| 1052 | ExitOnError ExitOnErr( |
| 1053 | "-wholeprogramdevirt-write-summary: "+ ClWriteSummary + ": "); |
| 1054 | std::error_code EC; |
| 1055 | if (StringRef(ClWriteSummary).ends_with(Suffix: ".bc")) { |
| 1056 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_None); |
| 1057 | ExitOnErr(errorCodeToError(EC)); |
| 1058 | writeIndexToFile(Index: *Summary, Out&: OS); |
| 1059 | } else { |
| 1060 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF); |
| 1061 | ExitOnErr(errorCodeToError(EC)); |
| 1062 | yaml::Output Out(OS); |
| 1063 | Out << *Summary; |
| 1064 | } |
| 1065 | } |
| 1066 | |
| 1067 | return Changed; |
| 1068 | } |
| 1069 | |
| 1070 | void DevirtModule::buildTypeIdentifierMap( |
| 1071 | std::vector<VTableBits> &Bits, |
| 1072 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { |
| 1073 | DenseMap<GlobalVariable *, VTableBits *> GVToBits; |
| 1074 | Bits.reserve(n: M.global_size()); |
| 1075 | SmallVector<MDNode *, 2> Types; |
| 1076 | for (GlobalVariable &GV : M.globals()) { |
| 1077 | Types.clear(); |
| 1078 | GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types); |
| 1079 | if (GV.isDeclaration() || Types.empty()) |
| 1080 | continue; |
| 1081 | |
| 1082 | VTableBits *&BitsPtr = GVToBits[&GV]; |
| 1083 | if (!BitsPtr) { |
| 1084 | Bits.emplace_back(); |
| 1085 | Bits.back().GV = &GV; |
| 1086 | Bits.back().ObjectSize = |
| 1087 | M.getDataLayout().getTypeAllocSize(Ty: GV.getInitializer()->getType()); |
| 1088 | BitsPtr = &Bits.back(); |
| 1089 | } |
| 1090 | |
| 1091 | for (MDNode *Type : Types) { |
| 1092 | auto *TypeID = Type->getOperand(I: 1).get(); |
| 1093 | |
| 1094 | uint64_t Offset = |
| 1095 | cast<ConstantInt>( |
| 1096 | Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue()) |
| 1097 | ->getZExtValue(); |
| 1098 | |
| 1099 | TypeIdMap[TypeID].insert(x: {.Bits: BitsPtr, .Offset: Offset}); |
| 1100 | } |
| 1101 | } |
| 1102 | } |
| 1103 | |
| 1104 | bool DevirtModule::tryFindVirtualCallTargets( |
| 1105 | std::vector<VirtualCallTarget> &TargetsForSlot, |
| 1106 | const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset, |
| 1107 | ModuleSummaryIndex *ExportSummary) { |
| 1108 | for (const TypeMemberInfo &TM : TypeMemberInfos) { |
| 1109 | if (!TM.Bits->GV->isConstant()) |
| 1110 | return false; |
| 1111 | |
| 1112 | // Without DevirtSpeculatively, we cannot perform whole program |
| 1113 | // devirtualization analysis on a vtable with public LTO visibility. |
| 1114 | if (!DevirtSpeculatively && TM.Bits->GV->getVCallVisibility() == |
| 1115 | GlobalObject::VCallVisibilityPublic) |
| 1116 | return false; |
| 1117 | |
| 1118 | Function *Fn = nullptr; |
| 1119 | Constant *C = nullptr; |
| 1120 | std::tie(args&: Fn, args&: C) = |
| 1121 | getFunctionAtVTableOffset(GV: TM.Bits->GV, Offset: TM.Offset + ByteOffset, M); |
| 1122 | |
| 1123 | if (!Fn) |
| 1124 | return false; |
| 1125 | |
| 1126 | if (FunctionsToSkip.match(S: Fn->getName())) |
| 1127 | return false; |
| 1128 | |
| 1129 | // We can disregard __cxa_pure_virtual as a possible call target, as |
| 1130 | // calls to pure virtuals are UB. |
| 1131 | if (Fn->getName() == "__cxa_pure_virtual") |
| 1132 | continue; |
| 1133 | |
| 1134 | // In most cases empty functions will be overridden by the |
| 1135 | // implementation of the derived class, so we can skip them. |
| 1136 | if (DevirtSpeculatively && Fn->getReturnType()->isVoidTy() && |
| 1137 | Fn->getInstructionCount() <= 1) |
| 1138 | continue; |
| 1139 | |
| 1140 | // We can disregard unreachable functions as possible call targets, as |
| 1141 | // unreachable functions shouldn't be called. |
| 1142 | if (mustBeUnreachableFunction(F: Fn, ExportSummary)) |
| 1143 | continue; |
| 1144 | |
| 1145 | // Save the symbol used in the vtable to use as the devirtualization |
| 1146 | // target. |
| 1147 | auto *GV = dyn_cast<GlobalValue>(Val: C); |
| 1148 | assert(GV); |
| 1149 | if (auto *GA = dyn_cast<GlobalAlias>(Val: GV)) |
| 1150 | if (!GA->isInterposable() && !GA->getAliaseeObject()->isInterposable()) |
| 1151 | GV = GA->getAliaseeObject(); |
| 1152 | TargetsForSlot.push_back(x: {GV, &TM}); |
| 1153 | } |
| 1154 | |
| 1155 | // Give up if we couldn't find any targets. |
| 1156 | return !TargetsForSlot.empty(); |
| 1157 | } |
| 1158 | |
| 1159 | bool DevirtIndex::tryFindVirtualCallTargets( |
| 1160 | std::vector<ValueInfo> &TargetsForSlot, |
| 1161 | const TypeIdCompatibleVtableInfo TIdInfo, uint64_t ByteOffset) { |
| 1162 | for (const TypeIdOffsetVtableInfo &P : TIdInfo) { |
| 1163 | // Find a representative copy of the vtable initializer. |
| 1164 | // We can have multiple available_externally, linkonce_odr and weak_odr |
| 1165 | // vtable initializers. We can also have multiple external vtable |
| 1166 | // initializers in the case of comdats, which we cannot check here. |
| 1167 | // The linker should give an error in this case. |
| 1168 | // |
| 1169 | // Also, handle the case of same-named local Vtables with the same path |
| 1170 | // and therefore the same GUID. This can happen if there isn't enough |
| 1171 | // distinguishing path when compiling the source file. In that case we |
| 1172 | // conservatively return false early. |
| 1173 | if (P.VTableVI.hasLocal() && P.VTableVI.getSummaryList().size() > 1) |
| 1174 | return false; |
| 1175 | const GlobalVarSummary *VS = nullptr; |
| 1176 | for (const auto &S : P.VTableVI.getSummaryList()) { |
| 1177 | auto *CurVS = cast<GlobalVarSummary>(Val: S->getBaseObject()); |
| 1178 | if (!CurVS->vTableFuncs().empty() || |
| 1179 | // Previously clang did not attach the necessary type metadata to |
| 1180 | // available_externally vtables, in which case there would not |
| 1181 | // be any vtable functions listed in the summary and we need |
| 1182 | // to treat this case conservatively (in case the bitcode is old). |
| 1183 | // However, we will also not have any vtable functions in the |
| 1184 | // case of a pure virtual base class. In that case we do want |
| 1185 | // to set VS to avoid treating it conservatively. |
| 1186 | !GlobalValue::isAvailableExternallyLinkage(Linkage: S->linkage())) { |
| 1187 | VS = CurVS; |
| 1188 | // We cannot perform whole program devirtualization analysis on a vtable |
| 1189 | // with public LTO visibility. |
| 1190 | if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic) |
| 1191 | return false; |
| 1192 | break; |
| 1193 | } |
| 1194 | } |
| 1195 | // There will be no VS if all copies are available_externally having no |
| 1196 | // type metadata. In that case we can't safely perform WPD. |
| 1197 | if (!VS) |
| 1198 | return false; |
| 1199 | if (!VS->isLive()) |
| 1200 | continue; |
| 1201 | for (auto VTP : VS->vTableFuncs()) { |
| 1202 | if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset) |
| 1203 | continue; |
| 1204 | |
| 1205 | if (mustBeUnreachableFunction(TheFnVI: VTP.FuncVI)) |
| 1206 | continue; |
| 1207 | |
| 1208 | TargetsForSlot.push_back(x: VTP.FuncVI); |
| 1209 | } |
| 1210 | } |
| 1211 | |
| 1212 | // Give up if we couldn't find any targets. |
| 1213 | return !TargetsForSlot.empty(); |
| 1214 | } |
| 1215 | |
| 1216 | void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo, |
| 1217 | Constant *TheFn, bool &IsExported) { |
| 1218 | // Don't devirtualize function if we're told to skip it |
| 1219 | // in -wholeprogramdevirt-skip. |
| 1220 | if (FunctionsToSkip.match(S: TheFn->stripPointerCasts()->getName())) |
| 1221 | return; |
| 1222 | auto Apply = [&](CallSiteInfo &CSInfo) { |
| 1223 | for (auto &&VCallSite : CSInfo.CallSites) { |
| 1224 | if (!OptimizedCalls.insert(Ptr: &VCallSite.CB).second) |
| 1225 | continue; |
| 1226 | |
| 1227 | // Stop when the number of devirted calls reaches the cutoff. |
| 1228 | if (!DebugCounter::shouldExecute(Counter&: CallsToDevirt)) |
| 1229 | continue; |
| 1230 | |
| 1231 | if (RemarksEnabled) |
| 1232 | VCallSite.emitRemark(OptName: "single-impl", |
| 1233 | TargetName: TheFn->stripPointerCasts()->getName(), OREGetter); |
| 1234 | NumSingleImpl++; |
| 1235 | auto &CB = VCallSite.CB; |
| 1236 | assert(!CB.getCalledFunction() && "devirtualizing direct call?"); |
| 1237 | IRBuilder<> Builder(&CB); |
| 1238 | Value *Callee = |
| 1239 | Builder.CreateBitCast(V: TheFn, DestTy: CB.getCalledOperand()->getType()); |
| 1240 | |
| 1241 | // If trap checking is enabled, add support to compare the virtual |
| 1242 | // function pointer to the devirtualized target. In case of a mismatch, |
| 1243 | // perform a debug trap. |
| 1244 | if (DevirtCheckMode == WPDCheckMode::Trap) { |
| 1245 | auto *Cond = Builder.CreateICmpNE(LHS: CB.getCalledOperand(), RHS: Callee); |
| 1246 | Instruction *ThenTerm = SplitBlockAndInsertIfThen( |
| 1247 | Cond, SplitBefore: &CB, /*Unreachable=*/false, |
| 1248 | BranchWeights: MDBuilder(M.getContext()).createUnlikelyBranchWeights()); |
| 1249 | Builder.SetInsertPoint(ThenTerm); |
| 1250 | Function *TrapFn = |
| 1251 | Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::debugtrap); |
| 1252 | auto *CallTrap = Builder.CreateCall(Callee: TrapFn); |
| 1253 | CallTrap->setDebugLoc(CB.getDebugLoc()); |
| 1254 | } |
| 1255 | |
| 1256 | // If fallback checking or speculative devirtualization are enabled, |
| 1257 | // add support to compare the virtual function pointer to the |
| 1258 | // devirtualized target. In case of a mismatch, fall back to indirect |
| 1259 | // call. |
| 1260 | if (DevirtCheckMode == WPDCheckMode::Fallback || DevirtSpeculatively) { |
| 1261 | MDNode *Weights = MDBuilder(M.getContext()).createLikelyBranchWeights(); |
| 1262 | // Version the indirect call site. If the called value is equal to the |
| 1263 | // given callee, 'NewInst' will be executed, otherwise the original call |
| 1264 | // site will be executed. |
| 1265 | CallBase &NewInst = versionCallSite(CB, Callee, BranchWeights: Weights); |
| 1266 | NewInst.setCalledOperand(Callee); |
| 1267 | // Since the new call site is direct, we must clear metadata that |
| 1268 | // is only appropriate for indirect calls. This includes !prof and |
| 1269 | // !callees metadata. |
| 1270 | NewInst.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr); |
| 1271 | NewInst.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr); |
| 1272 | // Additionally, we should remove them from the fallback indirect call, |
| 1273 | // so that we don't attempt to perform indirect call promotion later. |
| 1274 | CB.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr); |
| 1275 | CB.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr); |
| 1276 | } |
| 1277 | |
| 1278 | // In either trapping or non-checking mode, devirtualize original call. |
| 1279 | else { |
| 1280 | // Devirtualize unconditionally. |
| 1281 | CB.setCalledOperand(Callee); |
| 1282 | // Since the call site is now direct, we must clear metadata that |
| 1283 | // is only appropriate for indirect calls. This includes !prof and |
| 1284 | // !callees metadata. |
| 1285 | CB.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr); |
| 1286 | CB.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr); |
| 1287 | if (CB.getCalledOperand() && |
| 1288 | CB.getOperandBundle(ID: LLVMContext::OB_ptrauth)) { |
| 1289 | auto *NewCS = CallBase::removeOperandBundle( |
| 1290 | CB: &CB, ID: LLVMContext::OB_ptrauth, InsertPt: CB.getIterator()); |
| 1291 | CB.replaceAllUsesWith(V: NewCS); |
| 1292 | // Schedule for deletion at the end of pass run. |
| 1293 | CallsWithPtrAuthBundleRemoved.push_back(Elt: &CB); |
| 1294 | } |
| 1295 | } |
| 1296 | |
| 1297 | // This use is no longer unsafe. |
| 1298 | if (VCallSite.NumUnsafeUses) |
| 1299 | --*VCallSite.NumUnsafeUses; |
| 1300 | } |
| 1301 | if (CSInfo.isExported()) |
| 1302 | IsExported = true; |
| 1303 | CSInfo.markDevirt(); |
| 1304 | }; |
| 1305 | Apply(SlotInfo.CSInfo); |
| 1306 | for (auto &P : SlotInfo.ConstCSInfo) |
| 1307 | Apply(P.second); |
| 1308 | } |
| 1309 | |
| 1310 | static bool addCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) { |
| 1311 | // We can't add calls if we haven't seen a definition |
| 1312 | if (Callee.getSummaryList().empty()) |
| 1313 | return false; |
| 1314 | |
| 1315 | // Insert calls into the summary index so that the devirtualized targets |
| 1316 | // are eligible for import. |
| 1317 | // FIXME: Annotate type tests with hotness. For now, mark these as hot |
| 1318 | // to better ensure we have the opportunity to inline them. |
| 1319 | bool IsExported = false; |
| 1320 | auto &S = Callee.getSummaryList()[0]; |
| 1321 | CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* HasTailCall = */ false); |
| 1322 | auto AddCalls = [&](CallSiteInfo &CSInfo) { |
| 1323 | for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) { |
| 1324 | FS->addCall(E: {Callee, CI}); |
| 1325 | IsExported |= S->modulePath() != FS->modulePath(); |
| 1326 | } |
| 1327 | for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) { |
| 1328 | FS->addCall(E: {Callee, CI}); |
| 1329 | IsExported |= S->modulePath() != FS->modulePath(); |
| 1330 | } |
| 1331 | }; |
| 1332 | AddCalls(SlotInfo.CSInfo); |
| 1333 | for (auto &P : SlotInfo.ConstCSInfo) |
| 1334 | AddCalls(P.second); |
| 1335 | return IsExported; |
| 1336 | } |
| 1337 | |
| 1338 | bool DevirtModule::trySingleImplDevirt( |
| 1339 | ModuleSummaryIndex *ExportSummary, |
| 1340 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, |
| 1341 | WholeProgramDevirtResolution *Res) { |
| 1342 | // See if the program contains a single implementation of this virtual |
| 1343 | // function. |
| 1344 | auto *TheFn = TargetsForSlot[0].Fn; |
| 1345 | for (auto &&Target : TargetsForSlot) |
| 1346 | if (TheFn != Target.Fn) |
| 1347 | return false; |
| 1348 | |
| 1349 | // If so, update each call site to call that implementation directly. |
| 1350 | if (RemarksEnabled || AreStatisticsEnabled()) |
| 1351 | TargetsForSlot[0].WasDevirt = true; |
| 1352 | |
| 1353 | bool IsExported = false; |
| 1354 | applySingleImplDevirt(SlotInfo, TheFn, IsExported); |
| 1355 | if (!IsExported) |
| 1356 | return false; |
| 1357 | |
| 1358 | // If the only implementation has local linkage, we must promote to external |
| 1359 | // to make it visible to thin LTO objects. We can only get here during the |
| 1360 | // ThinLTO export phase. |
| 1361 | if (TheFn->hasLocalLinkage()) { |
| 1362 | std::string NewName = (TheFn->getName() + ".llvm.merged").str(); |
| 1363 | |
| 1364 | // Since we are renaming the function, any comdats with the same name must |
| 1365 | // also be renamed. This is required when targeting COFF, as the comdat name |
| 1366 | // must match one of the names of the symbols in the comdat. |
| 1367 | if (Comdat *C = TheFn->getComdat()) { |
| 1368 | if (C->getName() == TheFn->getName()) { |
| 1369 | Comdat *NewC = M.getOrInsertComdat(Name: NewName); |
| 1370 | NewC->setSelectionKind(C->getSelectionKind()); |
| 1371 | for (GlobalObject &GO : M.global_objects()) |
| 1372 | if (GO.getComdat() == C) |
| 1373 | GO.setComdat(NewC); |
| 1374 | } |
| 1375 | } |
| 1376 | |
| 1377 | TheFn->setLinkage(GlobalValue::ExternalLinkage); |
| 1378 | TheFn->setVisibility(GlobalValue::HiddenVisibility); |
| 1379 | TheFn->setName(NewName); |
| 1380 | } |
| 1381 | if (ValueInfo TheFnVI = ExportSummary->getValueInfo(GUID: TheFn->getGUID())) |
| 1382 | // Any needed promotion of 'TheFn' has already been done during |
| 1383 | // LTO unit split, so we can ignore return value of AddCalls. |
| 1384 | addCalls(SlotInfo, Callee: TheFnVI); |
| 1385 | |
| 1386 | Res->TheKind = WholeProgramDevirtResolution::SingleImpl; |
| 1387 | Res->SingleImplName = std::string(TheFn->getName()); |
| 1388 | |
| 1389 | return true; |
| 1390 | } |
| 1391 | |
| 1392 | bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot, |
| 1393 | VTableSlotSummary &SlotSummary, |
| 1394 | VTableSlotInfo &SlotInfo, |
| 1395 | WholeProgramDevirtResolution *Res, |
| 1396 | std::set<ValueInfo> &DevirtTargets) { |
| 1397 | // See if the program contains a single implementation of this virtual |
| 1398 | // function. |
| 1399 | auto TheFn = TargetsForSlot[0]; |
| 1400 | for (auto &&Target : TargetsForSlot) |
| 1401 | if (TheFn != Target) |
| 1402 | return false; |
| 1403 | |
| 1404 | // Don't devirtualize if we don't have target definition. |
| 1405 | auto Size = TheFn.getSummaryList().size(); |
| 1406 | if (!Size) |
| 1407 | return false; |
| 1408 | |
| 1409 | // Don't devirtualize function if we're told to skip it |
| 1410 | // in -wholeprogramdevirt-skip. |
| 1411 | if (FunctionsToSkip.match(S: TheFn.name())) |
| 1412 | return false; |
| 1413 | |
| 1414 | // If the summary list contains multiple summaries where at least one is |
| 1415 | // a local, give up, as we won't know which (possibly promoted) name to use. |
| 1416 | if (TheFn.hasLocal() && Size > 1) |
| 1417 | return false; |
| 1418 | |
| 1419 | // Collect functions devirtualized at least for one call site for stats. |
| 1420 | if (PrintSummaryDevirt || AreStatisticsEnabled()) |
| 1421 | DevirtTargets.insert(x: TheFn); |
| 1422 | |
| 1423 | auto &S = TheFn.getSummaryList()[0]; |
| 1424 | bool IsExported = addCalls(SlotInfo, Callee: TheFn); |
| 1425 | if (IsExported) |
| 1426 | ExportedGUIDs.insert(x: TheFn.getGUID()); |
| 1427 | |
| 1428 | // Record in summary for use in devirtualization during the ThinLTO import |
| 1429 | // step. |
| 1430 | Res->TheKind = WholeProgramDevirtResolution::SingleImpl; |
| 1431 | if (GlobalValue::isLocalLinkage(Linkage: S->linkage())) { |
| 1432 | if (IsExported) { |
| 1433 | // If target is a local function and we are exporting it by |
| 1434 | // devirtualizing a call in another module, we need to record the |
| 1435 | // promoted name. |
| 1436 | if (ExternallyVisibleSymbolNamesPtr) |
| 1437 | ExternallyVisibleSymbolNamesPtr->insert(V: TheFn.name()); |
| 1438 | Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal( |
| 1439 | Name: TheFn.name(), ModHash: ExportSummary.getModuleHash(ModPath: S->modulePath())); |
| 1440 | } else { |
| 1441 | LocalWPDTargetsMap[TheFn].push_back(x: SlotSummary); |
| 1442 | Res->SingleImplName = std::string(TheFn.name()); |
| 1443 | } |
| 1444 | } else |
| 1445 | Res->SingleImplName = std::string(TheFn.name()); |
| 1446 | |
| 1447 | // Name will be empty if this thin link driven off of serialized combined |
| 1448 | // index (e.g. llvm-lto). However, WPD is not supported/invoked for the |
| 1449 | // legacy LTO API anyway. |
| 1450 | assert(!Res->SingleImplName.empty()); |
| 1451 | |
| 1452 | return true; |
| 1453 | } |
| 1454 | |
| 1455 | void DevirtModule::tryICallBranchFunnel( |
| 1456 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, |
| 1457 | WholeProgramDevirtResolution *Res, VTableSlot Slot) { |
| 1458 | Triple T(M.getTargetTriple()); |
| 1459 | if (T.getArch() != Triple::x86_64) |
| 1460 | return; |
| 1461 | |
| 1462 | if (TargetsForSlot.size() > ClThreshold) |
| 1463 | return; |
| 1464 | |
| 1465 | bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted; |
| 1466 | if (!HasNonDevirt) |
| 1467 | for (auto &P : SlotInfo.ConstCSInfo) |
| 1468 | if (!P.second.AllCallSitesDevirted) { |
| 1469 | HasNonDevirt = true; |
| 1470 | break; |
| 1471 | } |
| 1472 | |
| 1473 | if (!HasNonDevirt) |
| 1474 | return; |
| 1475 | |
| 1476 | // If any GV is AvailableExternally, not to generate branch.funnel. |
| 1477 | // NOTE: It is to avoid crash in LowerTypeTest. |
| 1478 | // If the branch.funnel is generated, because GV.isDeclarationForLinker(), |
| 1479 | // in LowerTypeTestsModule::lower(), its GlobalTypeMember would NOT |
| 1480 | // be saved in GlobalTypeMembers[&GV]. Then crash happens in |
| 1481 | // buildBitSetsFromDisjointSet due to GlobalTypeMembers[&GV] is NULL. |
| 1482 | // Even doing experiment to save it in GlobalTypeMembers[&GV] and |
| 1483 | // making GlobalTypeMembers[&GV] be not NULL, crash could avoid from |
| 1484 | // buildBitSetsFromDisjointSet. But still report_fatal_error in Verifier |
| 1485 | // or SelectionDAGBuilder later, because operands linkage type consistency |
| 1486 | // check of icall.branch.funnel can not pass. |
| 1487 | for (auto &T : TargetsForSlot) { |
| 1488 | if (T.TM->Bits->GV->hasAvailableExternallyLinkage()) |
| 1489 | return; |
| 1490 | } |
| 1491 | |
| 1492 | FunctionType *FT = |
| 1493 | FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), Params: {Int8PtrTy}, isVarArg: true); |
| 1494 | Function *JT; |
| 1495 | if (isa<MDString>(Val: Slot.TypeID)) { |
| 1496 | JT = Function::Create(Ty: FT, Linkage: Function::ExternalLinkage, |
| 1497 | AddrSpace: M.getDataLayout().getProgramAddressSpace(), |
| 1498 | N: getGlobalName(Slot, Args: {}, Name: "branch_funnel"), M: &M); |
| 1499 | JT->setVisibility(GlobalValue::HiddenVisibility); |
| 1500 | } else { |
| 1501 | JT = Function::Create(Ty: FT, Linkage: Function::InternalLinkage, |
| 1502 | AddrSpace: M.getDataLayout().getProgramAddressSpace(), |
| 1503 | N: "branch_funnel", M: &M); |
| 1504 | } |
| 1505 | JT->addParamAttr(ArgNo: 0, Kind: Attribute::Nest); |
| 1506 | |
| 1507 | std::vector<Value *> JTArgs; |
| 1508 | JTArgs.push_back(x: JT->arg_begin()); |
| 1509 | for (auto &T : TargetsForSlot) { |
| 1510 | JTArgs.push_back(x: getMemberAddr(M: T.TM)); |
| 1511 | JTArgs.push_back(x: T.Fn); |
| 1512 | } |
| 1513 | |
| 1514 | BasicBlock *BB = BasicBlock::Create(Context&: M.getContext(), Name: "", Parent: JT, InsertBefore: nullptr); |
| 1515 | Function *Intr = Intrinsic::getOrInsertDeclaration( |
| 1516 | M: &M, id: llvm::Intrinsic::icall_branch_funnel, OverloadTys: {}); |
| 1517 | |
| 1518 | auto *CI = CallInst::Create(Func: Intr, Args: JTArgs, NameStr: "", InsertBefore: BB); |
| 1519 | CI->setTailCallKind(CallInst::TCK_MustTail); |
| 1520 | ReturnInst::Create(C&: M.getContext(), retVal: nullptr, InsertBefore: BB); |
| 1521 | |
| 1522 | bool IsExported = false; |
| 1523 | applyICallBranchFunnel(SlotInfo, JT&: *JT, IsExported); |
| 1524 | if (IsExported) |
| 1525 | Res->TheKind = WholeProgramDevirtResolution::BranchFunnel; |
| 1526 | |
| 1527 | if (!JT->getEntryCount().has_value()) { |
| 1528 | // FIXME: we could pass through thinlto the necessary information. |
| 1529 | setExplicitlyUnknownFunctionEntryCount(F&: *JT, DEBUG_TYPE); |
| 1530 | } |
| 1531 | } |
| 1532 | |
| 1533 | void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo, |
| 1534 | Function &JT, bool &IsExported) { |
| 1535 | DenseMap<Function *, double> FunctionEntryCounts; |
| 1536 | auto Apply = [&](CallSiteInfo &CSInfo) { |
| 1537 | if (CSInfo.isExported()) |
| 1538 | IsExported = true; |
| 1539 | if (CSInfo.AllCallSitesDevirted) |
| 1540 | return; |
| 1541 | |
| 1542 | std::map<CallBase *, CallBase *> CallBases; |
| 1543 | for (auto &&VCallSite : CSInfo.CallSites) { |
| 1544 | CallBase &CB = VCallSite.CB; |
| 1545 | |
| 1546 | if (CallBases.find(x: &CB) != CallBases.end()) { |
| 1547 | // When finding devirtualizable calls, it's possible to find the same |
| 1548 | // vtable passed to multiple llvm.type.test or llvm.type.checked.load |
| 1549 | // calls, which can cause duplicate call sites to be recorded in |
| 1550 | // [Const]CallSites. If we've already found one of these |
| 1551 | // call instances, just ignore it. It will be replaced later. |
| 1552 | continue; |
| 1553 | } |
| 1554 | |
| 1555 | // Jump tables are only profitable if the retpoline mitigation is enabled. |
| 1556 | Attribute FSAttr = CB.getCaller()->getFnAttribute(Kind: "target-features"); |
| 1557 | if (!FSAttr.isValid() || |
| 1558 | !FSAttr.getValueAsString().contains(Other: "+retpoline")) |
| 1559 | continue; |
| 1560 | |
| 1561 | NumBranchFunnel++; |
| 1562 | if (RemarksEnabled) |
| 1563 | VCallSite.emitRemark(OptName: "branch-funnel", TargetName: JT.getName(), OREGetter); |
| 1564 | |
| 1565 | // Pass the address of the vtable in the nest register, which is r10 on |
| 1566 | // x86_64. |
| 1567 | std::vector<Type *> NewArgs; |
| 1568 | NewArgs.push_back(x: Int8PtrTy); |
| 1569 | append_range(C&: NewArgs, R: CB.getFunctionType()->params()); |
| 1570 | FunctionType *NewFT = |
| 1571 | FunctionType::get(Result: CB.getFunctionType()->getReturnType(), Params: NewArgs, |
| 1572 | isVarArg: CB.getFunctionType()->isVarArg()); |
| 1573 | IRBuilder<> IRB(&CB); |
| 1574 | std::vector<Value *> Args; |
| 1575 | Args.push_back(x: VCallSite.VTable); |
| 1576 | llvm::append_range(C&: Args, R: CB.args()); |
| 1577 | |
| 1578 | CallBase *NewCS = nullptr; |
| 1579 | if (!JT.isDeclaration()) { |
| 1580 | // Accumulate the call frequencies of the original call site, and use |
| 1581 | // that as total entry count for the funnel function. |
| 1582 | auto &F = *CB.getCaller(); |
| 1583 | auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F); |
| 1584 | auto EC = BFI.getBlockFreq(BB: &F.getEntryBlock()); |
| 1585 | auto CC = F.getEntryCount(); |
| 1586 | double CallCount = 0.0; |
| 1587 | if (EC.getFrequency() != 0 && CC && *CC != 0) { |
| 1588 | double CallFreq = |
| 1589 | static_cast<double>( |
| 1590 | BFI.getBlockFreq(BB: CB.getParent()).getFrequency()) / |
| 1591 | EC.getFrequency(); |
| 1592 | CallCount = CallFreq * *CC; |
| 1593 | } |
| 1594 | FunctionEntryCounts[&JT] += CallCount; |
| 1595 | } |
| 1596 | if (isa<CallInst>(Val: CB)) |
| 1597 | NewCS = IRB.CreateCall(FTy: NewFT, Callee: &JT, Args); |
| 1598 | else |
| 1599 | NewCS = |
| 1600 | IRB.CreateInvoke(Ty: NewFT, Callee: &JT, NormalDest: cast<InvokeInst>(Val&: CB).getNormalDest(), |
| 1601 | UnwindDest: cast<InvokeInst>(Val&: CB).getUnwindDest(), Args); |
| 1602 | NewCS->setCallingConv(CB.getCallingConv()); |
| 1603 | |
| 1604 | AttributeList Attrs = CB.getAttributes(); |
| 1605 | std::vector<AttributeSet> NewArgAttrs; |
| 1606 | NewArgAttrs.push_back(x: AttributeSet::get( |
| 1607 | C&: M.getContext(), Attrs: ArrayRef<Attribute>{Attribute::get( |
| 1608 | Context&: M.getContext(), Kind: Attribute::Nest)})); |
| 1609 | for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I) |
| 1610 | NewArgAttrs.push_back(x: Attrs.getParamAttrs(ArgNo: I)); |
| 1611 | NewCS->setAttributes( |
| 1612 | AttributeList::get(C&: M.getContext(), FnAttrs: Attrs.getFnAttrs(), |
| 1613 | RetAttrs: Attrs.getRetAttrs(), ArgAttrs: NewArgAttrs)); |
| 1614 | |
| 1615 | CallBases[&CB] = NewCS; |
| 1616 | |
| 1617 | // This use is no longer unsafe. |
| 1618 | if (VCallSite.NumUnsafeUses) |
| 1619 | --*VCallSite.NumUnsafeUses; |
| 1620 | } |
| 1621 | // Don't mark as devirtualized because there may be callers compiled without |
| 1622 | // retpoline mitigation, which would mean that they are lowered to |
| 1623 | // llvm.type.test and therefore require an llvm.type.test resolution for the |
| 1624 | // type identifier. |
| 1625 | |
| 1626 | for (auto &[Old, New] : CallBases) { |
| 1627 | Old->replaceAllUsesWith(V: New); |
| 1628 | Old->eraseFromParent(); |
| 1629 | } |
| 1630 | }; |
| 1631 | Apply(SlotInfo.CSInfo); |
| 1632 | for (auto &P : SlotInfo.ConstCSInfo) |
| 1633 | Apply(P.second); |
| 1634 | for (auto &[F, C] : FunctionEntryCounts) { |
| 1635 | assert(!F->getEntryCount() && |
| 1636 | "Unexpected entry count for funnel that was freshly synthesized"); |
| 1637 | F->setEntryCount(Count: static_cast<uint64_t>(std::round(x: C))); |
| 1638 | } |
| 1639 | } |
| 1640 | |
| 1641 | bool DevirtModule::tryEvaluateFunctionsWithArgs( |
| 1642 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 1643 | ArrayRef<uint64_t> Args) { |
| 1644 | // Evaluate each function and store the result in each target's RetVal |
| 1645 | // field. |
| 1646 | for (VirtualCallTarget &Target : TargetsForSlot) { |
| 1647 | // TODO: Skip for now if the vtable symbol was an alias to a function, |
| 1648 | // need to evaluate whether it would be correct to analyze the aliasee |
| 1649 | // function for this optimization. |
| 1650 | auto *Fn = dyn_cast<Function>(Val: Target.Fn); |
| 1651 | if (!Fn) |
| 1652 | return false; |
| 1653 | |
| 1654 | if (Fn->arg_size() != Args.size() + 1) |
| 1655 | return false; |
| 1656 | |
| 1657 | Evaluator Eval(M.getDataLayout(), nullptr); |
| 1658 | SmallVector<Constant *, 2> EvalArgs; |
| 1659 | EvalArgs.push_back( |
| 1660 | Elt: Constant::getNullValue(Ty: Fn->getFunctionType()->getParamType(i: 0))); |
| 1661 | for (unsigned I = 0; I != Args.size(); ++I) { |
| 1662 | auto *ArgTy = |
| 1663 | dyn_cast<IntegerType>(Val: Fn->getFunctionType()->getParamType(i: I + 1)); |
| 1664 | if (!ArgTy) |
| 1665 | return false; |
| 1666 | EvalArgs.push_back(Elt: ConstantInt::get(Ty: ArgTy, V: Args[I])); |
| 1667 | } |
| 1668 | |
| 1669 | Constant *RetVal; |
| 1670 | if (!Eval.EvaluateFunction(F: Fn, RetVal, ActualArgs: EvalArgs) || |
| 1671 | !isa<ConstantInt>(Val: RetVal)) |
| 1672 | return false; |
| 1673 | Target.RetVal = cast<ConstantInt>(Val: RetVal)->getZExtValue(); |
| 1674 | } |
| 1675 | return true; |
| 1676 | } |
| 1677 | |
| 1678 | void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, |
| 1679 | uint64_t TheRetVal) { |
| 1680 | for (auto Call : CSInfo.CallSites) { |
| 1681 | if (!OptimizedCalls.insert(Ptr: &Call.CB).second) |
| 1682 | continue; |
| 1683 | NumUniformRetVal++; |
| 1684 | Call.replaceAndErase( |
| 1685 | OptName: "uniform-ret-val", TargetName: FnName, RemarksEnabled, OREGetter, |
| 1686 | New: ConstantInt::get(Ty: cast<IntegerType>(Val: Call.CB.getType()), V: TheRetVal)); |
| 1687 | } |
| 1688 | CSInfo.markDevirt(); |
| 1689 | } |
| 1690 | |
| 1691 | bool DevirtModule::tryUniformRetValOpt( |
| 1692 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo, |
| 1693 | WholeProgramDevirtResolution::ByArg *Res) { |
| 1694 | // Uniform return value optimization. If all functions return the same |
| 1695 | // constant, replace all calls with that constant. |
| 1696 | uint64_t TheRetVal = TargetsForSlot[0].RetVal; |
| 1697 | for (const VirtualCallTarget &Target : TargetsForSlot) |
| 1698 | if (Target.RetVal != TheRetVal) |
| 1699 | return false; |
| 1700 | |
| 1701 | if (CSInfo.isExported()) { |
| 1702 | Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal; |
| 1703 | Res->Info = TheRetVal; |
| 1704 | } |
| 1705 | |
| 1706 | applyUniformRetValOpt(CSInfo, FnName: TargetsForSlot[0].Fn->getName(), TheRetVal); |
| 1707 | if (RemarksEnabled || AreStatisticsEnabled()) |
| 1708 | for (auto &&Target : TargetsForSlot) |
| 1709 | Target.WasDevirt = true; |
| 1710 | return true; |
| 1711 | } |
| 1712 | |
| 1713 | std::string DevirtModule::getGlobalName(VTableSlot Slot, |
| 1714 | ArrayRef<uint64_t> Args, |
| 1715 | StringRef Name) { |
| 1716 | std::string FullName = "__typeid_"; |
| 1717 | raw_string_ostream OS(FullName); |
| 1718 | OS << cast<MDString>(Val: Slot.TypeID)->getString() << '_' << Slot.ByteOffset; |
| 1719 | for (uint64_t Arg : Args) |
| 1720 | OS << '_' << Arg; |
| 1721 | OS << '_' << Name; |
| 1722 | return FullName; |
| 1723 | } |
| 1724 | |
| 1725 | bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() { |
| 1726 | Triple T(M.getTargetTriple()); |
| 1727 | return T.isX86() && T.getObjectFormat() == Triple::ELF; |
| 1728 | } |
| 1729 | |
| 1730 | void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 1731 | StringRef Name, Constant *C) { |
| 1732 | GlobalAlias *GA = GlobalAlias::create(Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::ExternalLinkage, |
| 1733 | Name: getGlobalName(Slot, Args, Name), Aliasee: C, Parent: &M); |
| 1734 | GA->setVisibility(GlobalValue::HiddenVisibility); |
| 1735 | } |
| 1736 | |
| 1737 | void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 1738 | StringRef Name, uint32_t Const, |
| 1739 | uint32_t &Storage) { |
| 1740 | if (shouldExportConstantsAsAbsoluteSymbols()) { |
| 1741 | exportGlobal( |
| 1742 | Slot, Args, Name, |
| 1743 | C: ConstantExpr::getIntToPtr(C: ConstantInt::get(Ty: Int32Ty, V: Const), Ty: Int8PtrTy)); |
| 1744 | return; |
| 1745 | } |
| 1746 | |
| 1747 | Storage = Const; |
| 1748 | } |
| 1749 | |
| 1750 | Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 1751 | StringRef Name) { |
| 1752 | GlobalVariable *GV = |
| 1753 | M.getOrInsertGlobal(Name: getGlobalName(Slot, Args, Name), Ty: Int8Arr0Ty); |
| 1754 | GV->setVisibility(GlobalValue::HiddenVisibility); |
| 1755 | return GV; |
| 1756 | } |
| 1757 | |
| 1758 | Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, |
| 1759 | StringRef Name, IntegerType *IntTy, |
| 1760 | uint32_t Storage) { |
| 1761 | if (!shouldExportConstantsAsAbsoluteSymbols()) |
| 1762 | return ConstantInt::get(Ty: IntTy, V: Storage); |
| 1763 | |
| 1764 | Constant *C = importGlobal(Slot, Args, Name); |
| 1765 | auto *GV = cast<GlobalVariable>(Val: C->stripPointerCasts()); |
| 1766 | C = ConstantExpr::getPtrToInt(C, Ty: IntTy); |
| 1767 | |
| 1768 | // We only need to set metadata if the global is newly created, in which |
| 1769 | // case it would not have hidden visibility. |
| 1770 | if (GV->hasMetadata(KindID: LLVMContext::MD_absolute_symbol)) |
| 1771 | return C; |
| 1772 | |
| 1773 | auto SetAbsRange = [&](uint64_t Min, uint64_t Max) { |
| 1774 | auto *MinC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Min)); |
| 1775 | auto *MaxC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Max)); |
| 1776 | GV->setMetadata(KindID: LLVMContext::MD_absolute_symbol, |
| 1777 | Node: MDNode::get(Context&: M.getContext(), MDs: {MinC, MaxC})); |
| 1778 | }; |
| 1779 | unsigned AbsWidth = IntTy->getBitWidth(); |
| 1780 | if (AbsWidth == IntPtrTy->getBitWidth()) { |
| 1781 | uint64_t AllOnes = IntTy->getBitMask(); |
| 1782 | SetAbsRange(AllOnes, AllOnes); // Full set. |
| 1783 | } else { |
| 1784 | SetAbsRange(0, 1ull << AbsWidth); |
| 1785 | } |
| 1786 | return C; |
| 1787 | } |
| 1788 | |
| 1789 | void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, |
| 1790 | bool IsOne, |
| 1791 | Constant *UniqueMemberAddr) { |
| 1792 | for (auto &&Call : CSInfo.CallSites) { |
| 1793 | if (!OptimizedCalls.insert(Ptr: &Call.CB).second) |
| 1794 | continue; |
| 1795 | IRBuilder<> B(&Call.CB); |
| 1796 | Value *Cmp = |
| 1797 | B.CreateICmp(P: IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, LHS: Call.VTable, |
| 1798 | RHS: B.CreateBitCast(V: UniqueMemberAddr, DestTy: Call.VTable->getType())); |
| 1799 | Cmp = B.CreateZExt(V: Cmp, DestTy: Call.CB.getType()); |
| 1800 | NumUniqueRetVal++; |
| 1801 | Call.replaceAndErase(OptName: "unique-ret-val", TargetName: FnName, RemarksEnabled, OREGetter, |
| 1802 | New: Cmp); |
| 1803 | } |
| 1804 | CSInfo.markDevirt(); |
| 1805 | } |
| 1806 | |
| 1807 | Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) { |
| 1808 | return ConstantExpr::getPtrAdd(Ptr: M->Bits->GV, |
| 1809 | Offset: ConstantInt::get(Ty: Int64Ty, V: M->Offset)); |
| 1810 | } |
| 1811 | |
| 1812 | bool DevirtModule::tryUniqueRetValOpt( |
| 1813 | unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot, |
| 1814 | CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res, |
| 1815 | VTableSlot Slot, ArrayRef<uint64_t> Args) { |
| 1816 | // IsOne controls whether we look for a 0 or a 1. |
| 1817 | auto tryUniqueRetValOptFor = [&](bool IsOne) { |
| 1818 | const TypeMemberInfo *UniqueMember = nullptr; |
| 1819 | for (const VirtualCallTarget &Target : TargetsForSlot) { |
| 1820 | if (Target.RetVal == (IsOne ? 1 : 0)) { |
| 1821 | if (UniqueMember) |
| 1822 | return false; |
| 1823 | UniqueMember = Target.TM; |
| 1824 | } |
| 1825 | } |
| 1826 | |
| 1827 | // We should have found a unique member or bailed out by now. We already |
| 1828 | // checked for a uniform return value in tryUniformRetValOpt. |
| 1829 | assert(UniqueMember); |
| 1830 | |
| 1831 | Constant *UniqueMemberAddr = getMemberAddr(M: UniqueMember); |
| 1832 | if (CSInfo.isExported()) { |
| 1833 | Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal; |
| 1834 | Res->Info = IsOne; |
| 1835 | |
| 1836 | exportGlobal(Slot, Args, Name: "unique_member", C: UniqueMemberAddr); |
| 1837 | } |
| 1838 | |
| 1839 | // Replace each call with the comparison. |
| 1840 | applyUniqueRetValOpt(CSInfo, FnName: TargetsForSlot[0].Fn->getName(), IsOne, |
| 1841 | UniqueMemberAddr); |
| 1842 | |
| 1843 | // Update devirtualization statistics for targets. |
| 1844 | if (RemarksEnabled || AreStatisticsEnabled()) |
| 1845 | for (auto &&Target : TargetsForSlot) |
| 1846 | Target.WasDevirt = true; |
| 1847 | |
| 1848 | return true; |
| 1849 | }; |
| 1850 | |
| 1851 | if (BitWidth == 1) { |
| 1852 | if (tryUniqueRetValOptFor(true)) |
| 1853 | return true; |
| 1854 | if (tryUniqueRetValOptFor(false)) |
| 1855 | return true; |
| 1856 | } |
| 1857 | return false; |
| 1858 | } |
| 1859 | |
| 1860 | void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName, |
| 1861 | Constant *Byte, Constant *Bit) { |
| 1862 | for (auto Call : CSInfo.CallSites) { |
| 1863 | if (!OptimizedCalls.insert(Ptr: &Call.CB).second) |
| 1864 | continue; |
| 1865 | auto *RetType = cast<IntegerType>(Val: Call.CB.getType()); |
| 1866 | IRBuilder<> B(&Call.CB); |
| 1867 | Value *Addr = B.CreatePtrAdd(Ptr: Call.VTable, Offset: Byte); |
| 1868 | if (RetType->getBitWidth() == 1) { |
| 1869 | Value *Bits = B.CreateLoad(Ty: Int8Ty, Ptr: Addr); |
| 1870 | Value *BitsAndBit = B.CreateAnd(LHS: Bits, RHS: Bit); |
| 1871 | auto IsBitSet = B.CreateICmpNE(LHS: BitsAndBit, RHS: ConstantInt::get(Ty: Int8Ty, V: 0)); |
| 1872 | NumVirtConstProp1Bit++; |
| 1873 | Call.replaceAndErase(OptName: "virtual-const-prop-1-bit", TargetName: FnName, RemarksEnabled, |
| 1874 | OREGetter, New: IsBitSet); |
| 1875 | } else { |
| 1876 | Value *Val = B.CreateLoad(Ty: RetType, Ptr: Addr); |
| 1877 | NumVirtConstProp++; |
| 1878 | Call.replaceAndErase(OptName: "virtual-const-prop", TargetName: FnName, RemarksEnabled, |
| 1879 | OREGetter, New: Val); |
| 1880 | } |
| 1881 | } |
| 1882 | CSInfo.markDevirt(); |
| 1883 | } |
| 1884 | |
| 1885 | bool DevirtModule::tryVirtualConstProp( |
| 1886 | MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, |
| 1887 | WholeProgramDevirtResolution *Res, VTableSlot Slot) { |
| 1888 | // TODO: Skip for now if the vtable symbol was an alias to a function, |
| 1889 | // need to evaluate whether it would be correct to analyze the aliasee |
| 1890 | // function for this optimization. |
| 1891 | auto *Fn = dyn_cast<Function>(Val: TargetsForSlot[0].Fn); |
| 1892 | if (!Fn) |
| 1893 | return false; |
| 1894 | // This only works if the function returns an integer. |
| 1895 | auto *RetType = dyn_cast<IntegerType>(Val: Fn->getReturnType()); |
| 1896 | if (!RetType) |
| 1897 | return false; |
| 1898 | unsigned BitWidth = RetType->getBitWidth(); |
| 1899 | |
| 1900 | // TODO: Since we can evaluated these constants at compile-time, we can save |
| 1901 | // some space by calculating the smallest range of values that all these |
| 1902 | // constants can fit in, then only allocate enough space to fit those values. |
| 1903 | // At each callsite, we can get the original type by doing a sign/zero |
| 1904 | // extension. For example, if we would store an i64, but we can see that all |
| 1905 | // the values fit into an i16, then we can store an i16 before/after the |
| 1906 | // vtable and at each callsite do a s/zext. |
| 1907 | if (BitWidth > 64) |
| 1908 | return false; |
| 1909 | |
| 1910 | Align TypeAlignment = M.getDataLayout().getABIIntegerTypeAlignment(BitWidth); |
| 1911 | |
| 1912 | // Make sure that each function is defined, does not access memory, takes at |
| 1913 | // least one argument, does not use its first argument (which we assume is |
| 1914 | // 'this'), and has the same return type. |
| 1915 | // |
| 1916 | // Note that we test whether this copy of the function is readnone, rather |
| 1917 | // than testing function attributes, which must hold for any copy of the |
| 1918 | // function, even a less optimized version substituted at link time. This is |
| 1919 | // sound because the virtual constant propagation optimizations effectively |
| 1920 | // inline all implementations of the virtual function into each call site, |
| 1921 | // rather than using function attributes to perform local optimization. |
| 1922 | for (VirtualCallTarget &Target : TargetsForSlot) { |
| 1923 | // TODO: Skip for now if the vtable symbol was an alias to a function, |
| 1924 | // need to evaluate whether it would be correct to analyze the aliasee |
| 1925 | // function for this optimization. |
| 1926 | auto *Fn = dyn_cast<Function>(Val: Target.Fn); |
| 1927 | if (!Fn) |
| 1928 | return false; |
| 1929 | |
| 1930 | if (Fn->isDeclaration() || Fn->isInterposable() || |
| 1931 | !computeFunctionBodyMemoryAccess(F&: *Fn, AAR&: FAM.getResult<AAManager>(IR&: *Fn)) |
| 1932 | .doesNotAccessMemory() || |
| 1933 | Fn->arg_empty() || !Fn->arg_begin()->use_empty() || |
| 1934 | Fn->getReturnType() != RetType) |
| 1935 | return false; |
| 1936 | |
| 1937 | // This only works if the integer size is at most the alignment of the |
| 1938 | // vtable. If the table is underaligned, then we can't guarantee that the |
| 1939 | // constant will always be aligned to the integer type alignment. For |
| 1940 | // example, if the table is `align 1`, we can never guarantee that an i32 |
| 1941 | // stored before/after the vtable is 32-bit aligned without changing the |
| 1942 | // alignment of the new global. |
| 1943 | GlobalVariable *GV = Target.TM->Bits->GV; |
| 1944 | Align TableAlignment = M.getDataLayout().getValueOrABITypeAlignment( |
| 1945 | Alignment: GV->getAlign(), Ty: GV->getValueType()); |
| 1946 | if (TypeAlignment > TableAlignment) |
| 1947 | return false; |
| 1948 | } |
| 1949 | |
| 1950 | for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) { |
| 1951 | if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, Args: CSByConstantArg.first)) |
| 1952 | continue; |
| 1953 | |
| 1954 | WholeProgramDevirtResolution::ByArg *ResByArg = nullptr; |
| 1955 | if (Res) |
| 1956 | ResByArg = &Res->ResByArg[CSByConstantArg.first]; |
| 1957 | |
| 1958 | if (tryUniformRetValOpt(TargetsForSlot, CSInfo&: CSByConstantArg.second, Res: ResByArg)) |
| 1959 | continue; |
| 1960 | |
| 1961 | if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSInfo&: CSByConstantArg.second, |
| 1962 | Res: ResByArg, Slot, Args: CSByConstantArg.first)) |
| 1963 | continue; |
| 1964 | |
| 1965 | // Find an allocation offset in bits in all vtables associated with the |
| 1966 | // type. |
| 1967 | // TODO: If there would be "holes" in the vtable that were added by |
| 1968 | // padding, we could place i1s there to reduce any extra padding that |
| 1969 | // would be introduced by the i1s. |
| 1970 | uint64_t AllocBefore = |
| 1971 | findLowestOffset(Targets: TargetsForSlot, /*IsAfter=*/false, Size: BitWidth); |
| 1972 | uint64_t AllocAfter = |
| 1973 | findLowestOffset(Targets: TargetsForSlot, /*IsAfter=*/true, Size: BitWidth); |
| 1974 | |
| 1975 | // Calculate the total amount of padding needed to store a value at both |
| 1976 | // ends of the object. |
| 1977 | uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0; |
| 1978 | for (auto &&Target : TargetsForSlot) { |
| 1979 | TotalPaddingBefore += std::max<int64_t>( |
| 1980 | a: (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, b: 0); |
| 1981 | TotalPaddingAfter += std::max<int64_t>( |
| 1982 | a: (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, b: 0); |
| 1983 | } |
| 1984 | |
| 1985 | // If the amount of padding is too large, give up. |
| 1986 | // FIXME: do something smarter here. |
| 1987 | if (std::min(a: TotalPaddingBefore, b: TotalPaddingAfter) > 128) |
| 1988 | continue; |
| 1989 | |
| 1990 | // Calculate the offset to the value as a (possibly negative) byte offset |
| 1991 | // and (if applicable) a bit offset, and store the values in the targets. |
| 1992 | int64_t OffsetByte; |
| 1993 | uint64_t OffsetBit; |
| 1994 | if (TotalPaddingBefore <= TotalPaddingAfter) |
| 1995 | setBeforeReturnValues(Targets: TargetsForSlot, AllocBefore, BitWidth, OffsetByte, |
| 1996 | OffsetBit); |
| 1997 | else |
| 1998 | setAfterReturnValues(Targets: TargetsForSlot, AllocAfter, BitWidth, OffsetByte, |
| 1999 | OffsetBit); |
| 2000 | |
| 2001 | // In an earlier check we forbade constant propagation from operating on |
| 2002 | // tables whose alignment is less than the alignment needed for loading |
| 2003 | // the constant. Thus, the address we take the offset from will always be |
| 2004 | // aligned to at least this integer alignment. Now, we need to ensure that |
| 2005 | // the offset is also aligned to this integer alignment to ensure we always |
| 2006 | // have an aligned load. |
| 2007 | assert(OffsetByte % TypeAlignment.value() == 0); |
| 2008 | |
| 2009 | if (RemarksEnabled || AreStatisticsEnabled()) |
| 2010 | for (auto &&Target : TargetsForSlot) |
| 2011 | Target.WasDevirt = true; |
| 2012 | |
| 2013 | |
| 2014 | if (CSByConstantArg.second.isExported()) { |
| 2015 | ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp; |
| 2016 | ResByArg->Byte = OffsetByte; |
| 2017 | exportConstant(Slot, Args: CSByConstantArg.first, Name: "bit", Const: 1ULL << OffsetBit, |
| 2018 | Storage&: ResByArg->Bit); |
| 2019 | } |
| 2020 | |
| 2021 | // Rewrite each call to a load from OffsetByte/OffsetBit. |
| 2022 | Constant *ByteConst = ConstantInt::getSigned(Ty: Int32Ty, V: OffsetByte); |
| 2023 | Constant *BitConst = ConstantInt::get(Ty: Int8Ty, V: 1ULL << OffsetBit); |
| 2024 | applyVirtualConstProp(CSInfo&: CSByConstantArg.second, |
| 2025 | FnName: TargetsForSlot[0].Fn->getName(), Byte: ByteConst, Bit: BitConst); |
| 2026 | } |
| 2027 | return true; |
| 2028 | } |
| 2029 | |
| 2030 | void DevirtModule::rebuildGlobal(VTableBits &B) { |
| 2031 | if (B.Before.Bytes.empty() && B.After.Bytes.empty()) |
| 2032 | return; |
| 2033 | |
| 2034 | // Align the before byte array to the global's minimum alignment so that we |
| 2035 | // don't break any alignment requirements on the global. |
| 2036 | Align Alignment = M.getDataLayout().getValueOrABITypeAlignment( |
| 2037 | Alignment: B.GV->getAlign(), Ty: B.GV->getValueType()); |
| 2038 | B.Before.Bytes.resize(new_size: alignTo(Size: B.Before.Bytes.size(), A: Alignment)); |
| 2039 | |
| 2040 | // Before was stored in reverse order; flip it now. |
| 2041 | for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I) |
| 2042 | std::swap(a&: B.Before.Bytes[I], b&: B.Before.Bytes[Size - 1 - I]); |
| 2043 | |
| 2044 | // Build an anonymous global containing the before bytes, followed by the |
| 2045 | // original initializer, followed by the after bytes. |
| 2046 | auto *NewInit = ConstantStruct::getAnon( |
| 2047 | V: {ConstantDataArray::get(Context&: M.getContext(), Elts&: B.Before.Bytes), |
| 2048 | B.GV->getInitializer(), |
| 2049 | ConstantDataArray::get(Context&: M.getContext(), Elts&: B.After.Bytes)}); |
| 2050 | auto *NewGV = |
| 2051 | new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(), |
| 2052 | GlobalVariable::PrivateLinkage, NewInit, "", B.GV); |
| 2053 | NewGV->setSection(B.GV->getSection()); |
| 2054 | NewGV->setComdat(B.GV->getComdat()); |
| 2055 | NewGV->setAlignment(B.GV->getAlign()); |
| 2056 | |
| 2057 | // Copy the original vtable's metadata to the anonymous global, adjusting |
| 2058 | // offsets as required. |
| 2059 | NewGV->copyMetadata(Src: B.GV, Offset: B.Before.Bytes.size()); |
| 2060 | |
| 2061 | // Build an alias named after the original global, pointing at the second |
| 2062 | // element (the original initializer). |
| 2063 | auto *Alias = GlobalAlias::create( |
| 2064 | Ty: B.GV->getInitializer()->getType(), AddressSpace: 0, Linkage: B.GV->getLinkage(), Name: "", |
| 2065 | Aliasee: ConstantExpr::getGetElementPtr( |
| 2066 | DL: M.getDataLayout(), Ty: NewInit->getType(), C: NewGV, |
| 2067 | IdxList: {ConstantInt::get(Ty: Int32Ty, V: 0), ConstantInt::get(Ty: Int32Ty, V: 1)}, |
| 2068 | NW: GEPNoWrapFlags::inBounds()), |
| 2069 | Parent: &M); |
| 2070 | Alias->setVisibility(B.GV->getVisibility()); |
| 2071 | Alias->takeName(V: B.GV); |
| 2072 | |
| 2073 | B.GV->replaceAllUsesWith(V: Alias); |
| 2074 | B.GV->eraseFromParent(); |
| 2075 | } |
| 2076 | |
| 2077 | bool DevirtModule::areRemarksEnabled() { |
| 2078 | const auto &FL = M.getFunctionList(); |
| 2079 | for (const Function &Fn : FL) { |
| 2080 | if (Fn.empty()) |
| 2081 | continue; |
| 2082 | auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &Fn.front()); |
| 2083 | return DI.isEnabled(); |
| 2084 | } |
| 2085 | return false; |
| 2086 | } |
| 2087 | |
| 2088 | /// Find assumes whose conditions depend on this type test through phi or select |
| 2089 | /// nodes. SimplifyCFG can produce these patterns by merging type test + assume |
| 2090 | /// sequences from different predecessors. |
| 2091 | static void |
| 2092 | findAssumesThroughMergesForTypeTest(SmallVectorImpl<CallInst *> &Assumes, |
| 2093 | CallInst &TypeTest, |
| 2094 | SmallPtrSetImpl<Value *> &VisitedMerges) { |
| 2095 | SmallVector<Value *, 4> Worklist; |
| 2096 | #ifndef NDEBUG |
| 2097 | SmallPtrSet<CallInst *, 4> DirectAssumes(Assumes.begin(), Assumes.end()); |
| 2098 | #endif |
| 2099 | |
| 2100 | auto GetMergeUser = [](User *U, Value *V) -> Value * { |
| 2101 | if (isa<PHINode>(Val: U)) |
| 2102 | return U; |
| 2103 | if (auto *Select = dyn_cast<SelectInst>(Val: U); |
| 2104 | Select && (Select->getTrueValue() == V || Select->getFalseValue() == V)) |
| 2105 | return Select; |
| 2106 | return nullptr; |
| 2107 | }; |
| 2108 | |
| 2109 | // Direct assume users were already collected by |
| 2110 | // findDevirtualizableCallsForTypeTest. Start from merge users so this search |
| 2111 | // finds only assumptions that depend on the type test through merges. |
| 2112 | for (User *U : TypeTest.users()) |
| 2113 | if (Value *Merge = GetMergeUser(U, &TypeTest)) |
| 2114 | Worklist.push_back(Elt: Merge); |
| 2115 | |
| 2116 | while (!Worklist.empty()) { |
| 2117 | Value *V = Worklist.pop_back_val(); |
| 2118 | if (!VisitedMerges.insert(Ptr: V).second) |
| 2119 | continue; |
| 2120 | |
| 2121 | for (User *U : V->users()) { |
| 2122 | if (auto *Assume = dyn_cast<AssumeInst>(Val: U)) { |
| 2123 | if (Assume->getArgOperand(i: 0) == V) { |
| 2124 | assert(!DirectAssumes.contains(Assume) && |
| 2125 | "assume must not be both direct and merged"); |
| 2126 | Assumes.push_back(Elt: Assume); |
| 2127 | } |
| 2128 | continue; |
| 2129 | } |
| 2130 | |
| 2131 | if (Value *Merge = GetMergeUser(U, V)) |
| 2132 | Worklist.push_back(Elt: Merge); |
| 2133 | } |
| 2134 | } |
| 2135 | } |
| 2136 | |
| 2137 | void DevirtModule::scanTypeTestUsers( |
| 2138 | Function *TypeTestFunc, |
| 2139 | DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { |
| 2140 | // Cleanup removes every assume reachable through a merge, so each merge only |
| 2141 | // needs to be processed once even if multiple unresolved type tests reach it. |
| 2142 | SmallPtrSet<Value *, 8> VisitedMerges; |
| 2143 | |
| 2144 | // Find all virtual calls via a virtual table pointer %p under an assumption |
| 2145 | // of the form llvm.assume(llvm.type.test(%p, %md)) or |
| 2146 | // llvm.assume(llvm.public.type.test(%p, %md)). |
| 2147 | // This indicates that %p points to a member of the type identifier %md. |
| 2148 | // Group calls by (type ID, offset) pair (effectively the identity of the |
| 2149 | // virtual function) and store to CallSlots. |
| 2150 | for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc->uses())) { |
| 2151 | auto *CI = dyn_cast<CallInst>(Val: U.getUser()); |
| 2152 | if (!CI) |
| 2153 | continue; |
| 2154 | // Search for virtual calls based on %p and add them to DevirtCalls. |
| 2155 | SmallVector<DevirtCallSite, 1> DevirtCalls; |
| 2156 | SmallVector<CallInst *, 1> Assumes; |
| 2157 | auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: *CI->getFunction()); |
| 2158 | findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT); |
| 2159 | |
| 2160 | Metadata *TypeId = |
| 2161 | cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1))->getMetadata(); |
| 2162 | // If we found any, add them to CallSlots. |
| 2163 | if (!Assumes.empty()) { |
| 2164 | Value *Ptr = CI->getArgOperand(i: 0)->stripPointerCasts(); |
| 2165 | for (DevirtCallSite Call : DevirtCalls) |
| 2166 | CallSlots[{.TypeID: TypeId, .ByteOffset: Call.Offset}].addCallSite(VTable: Ptr, CB&: Call.CB, NumUnsafeUses: nullptr); |
| 2167 | } |
| 2168 | |
| 2169 | auto RemoveTypeTestAssumes = [&]() { |
| 2170 | // A merge of type test results does not imply that any individual type |
| 2171 | // test can be assumed, so don't use these assumes to identify |
| 2172 | // devirtualizable calls. They still need to be removed when type |
| 2173 | // information is missing for any value contributing to the merge. |
| 2174 | findAssumesThroughMergesForTypeTest(Assumes, TypeTest&: *CI, VisitedMerges); |
| 2175 | |
| 2176 | // We no longer need the assumes or the type test. |
| 2177 | for (auto *Assume : Assumes) |
| 2178 | Assume->eraseFromParent(); |
| 2179 | // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we |
| 2180 | // may use the vtable argument later. |
| 2181 | if (CI->use_empty()) |
| 2182 | CI->eraseFromParent(); |
| 2183 | }; |
| 2184 | |
| 2185 | // At this point we could remove all type test assume sequences, as they |
| 2186 | // were originally inserted for WPD. However, we can keep these in the |
| 2187 | // code stream for later analysis (e.g. to help drive more efficient ICP |
| 2188 | // sequences). They will eventually be removed by a second LowerTypeTests |
| 2189 | // invocation that cleans them up. In order to do this correctly, the first |
| 2190 | // LowerTypeTests invocation needs to know that they have "Unknown" type |
| 2191 | // test resolution, so that they aren't treated as Unsat and lowered to |
| 2192 | // False, which will break any uses on assumes. Below we remove any type |
| 2193 | // test assumes that will not be treated as Unknown by LTT. |
| 2194 | |
| 2195 | // The type test assumes will be treated by LTT as Unsat if the type id is |
| 2196 | // not used on a global (in which case it has no entry in the TypeIdMap). |
| 2197 | if (!TypeIdMap.count(Val: TypeId)) |
| 2198 | RemoveTypeTestAssumes(); |
| 2199 | |
| 2200 | // For ThinLTO importing, we need to remove the type test assumes if this is |
| 2201 | // an MDString type id without a corresponding TypeIdSummary. Any |
| 2202 | // non-MDString type ids are ignored and treated as Unknown by LTT, so their |
| 2203 | // type test assumes can be kept. If the MDString type id is missing a |
| 2204 | // TypeIdSummary (e.g. because there was no use on a vcall, preventing the |
| 2205 | // exporting phase of WPD from analyzing it), then it would be treated as |
| 2206 | // Unsat by LTT and we need to remove its type test assumes here. If not |
| 2207 | // used on a vcall we don't need them for later optimization use in any |
| 2208 | // case. |
| 2209 | else if (ImportSummary && isa<MDString>(Val: TypeId)) { |
| 2210 | const TypeIdSummary *TidSummary = |
| 2211 | ImportSummary->getTypeIdSummary(TypeId: cast<MDString>(Val: TypeId)->getString()); |
| 2212 | if (!TidSummary) |
| 2213 | RemoveTypeTestAssumes(); |
| 2214 | else |
| 2215 | // If one was created it should not be Unsat, because if we reached here |
| 2216 | // the type id was used on a global. |
| 2217 | assert(TidSummary->TTRes.TheKind != TypeTestResolution::Unsat); |
| 2218 | } |
| 2219 | } |
| 2220 | } |
| 2221 | |
| 2222 | void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) { |
| 2223 | Function *TypeTestFunc = |
| 2224 | Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::type_test); |
| 2225 | |
| 2226 | for (Use &U : llvm::make_early_inc_range(Range: TypeCheckedLoadFunc->uses())) { |
| 2227 | auto *CI = dyn_cast<CallInst>(Val: U.getUser()); |
| 2228 | if (!CI) |
| 2229 | continue; |
| 2230 | |
| 2231 | Value *Ptr = CI->getArgOperand(i: 0); |
| 2232 | Value *Offset = CI->getArgOperand(i: 1); |
| 2233 | Value *TypeIdValue = CI->getArgOperand(i: 2); |
| 2234 | Metadata *TypeId = cast<MetadataAsValue>(Val: TypeIdValue)->getMetadata(); |
| 2235 | |
| 2236 | SmallVector<DevirtCallSite, 1> DevirtCalls; |
| 2237 | SmallVector<Instruction *, 1> LoadedPtrs; |
| 2238 | SmallVector<Instruction *, 1> Preds; |
| 2239 | bool HasNonCallUses = false; |
| 2240 | auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: *CI->getFunction()); |
| 2241 | findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds, |
| 2242 | HasNonCallUses, CI, DT); |
| 2243 | |
| 2244 | // Start by generating "pessimistic" code that explicitly loads the function |
| 2245 | // pointer from the vtable and performs the type check. If possible, we will |
| 2246 | // eliminate the load and the type check later. |
| 2247 | |
| 2248 | // If possible, only generate the load at the point where it is used. |
| 2249 | // This helps avoid unnecessary spills. |
| 2250 | IRBuilder<> LoadB( |
| 2251 | (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI); |
| 2252 | |
| 2253 | Value *LoadedValue = nullptr; |
| 2254 | if (TypeCheckedLoadFunc->getIntrinsicID() == |
| 2255 | Intrinsic::type_checked_load_relative) { |
| 2256 | Function *LoadRelFunc = Intrinsic::getOrInsertDeclaration( |
| 2257 | M: &M, id: Intrinsic::load_relative, OverloadTys: {Int32Ty}); |
| 2258 | LoadedValue = LoadB.CreateCall(Callee: LoadRelFunc, Args: {Ptr, Offset}); |
| 2259 | } else { |
| 2260 | Value *GEP = LoadB.CreatePtrAdd(Ptr, Offset); |
| 2261 | LoadedValue = LoadB.CreateLoad(Ty: Int8PtrTy, Ptr: GEP); |
| 2262 | } |
| 2263 | |
| 2264 | for (Instruction *LoadedPtr : LoadedPtrs) { |
| 2265 | LoadedPtr->replaceAllUsesWith(V: LoadedValue); |
| 2266 | LoadedPtr->eraseFromParent(); |
| 2267 | } |
| 2268 | |
| 2269 | // Likewise for the type test. |
| 2270 | IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI); |
| 2271 | CallInst *TypeTestCall = CallB.CreateCall(Callee: TypeTestFunc, Args: {Ptr, TypeIdValue}); |
| 2272 | |
| 2273 | for (Instruction *Pred : Preds) { |
| 2274 | Pred->replaceAllUsesWith(V: TypeTestCall); |
| 2275 | Pred->eraseFromParent(); |
| 2276 | } |
| 2277 | |
| 2278 | // We have already erased any extractvalue instructions that refer to the |
| 2279 | // intrinsic call, but the intrinsic may have other non-extractvalue uses |
| 2280 | // (although this is unlikely). In that case, explicitly build a pair and |
| 2281 | // RAUW it. |
| 2282 | if (!CI->use_empty()) { |
| 2283 | Value *Pair = PoisonValue::get(T: CI->getType()); |
| 2284 | IRBuilder<> B(CI); |
| 2285 | Pair = B.CreateInsertValue(Agg: Pair, Val: LoadedValue, Idxs: {0}); |
| 2286 | Pair = B.CreateInsertValue(Agg: Pair, Val: TypeTestCall, Idxs: {1}); |
| 2287 | CI->replaceAllUsesWith(V: Pair); |
| 2288 | } |
| 2289 | |
| 2290 | // The number of unsafe uses is initially the number of uses. |
| 2291 | auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall]; |
| 2292 | NumUnsafeUses = DevirtCalls.size(); |
| 2293 | |
| 2294 | // If the function pointer has a non-call user, we cannot eliminate the type |
| 2295 | // check, as one of those users may eventually call the pointer. Increment |
| 2296 | // the unsafe use count to make sure it cannot reach zero. |
| 2297 | if (HasNonCallUses) |
| 2298 | ++NumUnsafeUses; |
| 2299 | for (DevirtCallSite Call : DevirtCalls) { |
| 2300 | CallSlots[{.TypeID: TypeId, .ByteOffset: Call.Offset}].addCallSite(VTable: Ptr, CB&: Call.CB, |
| 2301 | NumUnsafeUses: &NumUnsafeUses); |
| 2302 | } |
| 2303 | |
| 2304 | CI->eraseFromParent(); |
| 2305 | } |
| 2306 | } |
| 2307 | |
| 2308 | void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) { |
| 2309 | auto *TypeId = dyn_cast<MDString>(Val: Slot.TypeID); |
| 2310 | if (!TypeId) |
| 2311 | return; |
| 2312 | const TypeIdSummary *TidSummary = |
| 2313 | ImportSummary->getTypeIdSummary(TypeId: TypeId->getString()); |
| 2314 | if (!TidSummary) |
| 2315 | return; |
| 2316 | auto ResI = TidSummary->WPDRes.find(x: Slot.ByteOffset); |
| 2317 | if (ResI == TidSummary->WPDRes.end()) |
| 2318 | return; |
| 2319 | const WholeProgramDevirtResolution &Res = ResI->second; |
| 2320 | |
| 2321 | if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) { |
| 2322 | assert(!Res.SingleImplName.empty()); |
| 2323 | // The type of the function in the declaration is irrelevant because every |
| 2324 | // call site will cast it to the correct type. |
| 2325 | Value *SingleImplVal = |
| 2326 | M.getOrInsertFunction(Name: Res.SingleImplName, |
| 2327 | RetTy: Type::getVoidTy(C&: M.getContext())) |
| 2328 | .getCallee(); |
| 2329 | if (auto *A = dyn_cast<GlobalAlias>(Val: SingleImplVal->stripPointerCasts())) |
| 2330 | if (!A->isInterposable() && !A->getAliaseeObject()->isInterposable()) |
| 2331 | SingleImplVal = A->getAliaseeObject(); |
| 2332 | Constant *SingleImpl = cast<Constant>(Val: SingleImplVal); |
| 2333 | |
| 2334 | // This is the import phase so we should not be exporting anything. |
| 2335 | bool IsExported = false; |
| 2336 | applySingleImplDevirt(SlotInfo, TheFn: SingleImpl, IsExported); |
| 2337 | assert(!IsExported); |
| 2338 | } |
| 2339 | |
| 2340 | for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) { |
| 2341 | auto I = Res.ResByArg.find(x: CSByConstantArg.first); |
| 2342 | if (I == Res.ResByArg.end()) |
| 2343 | continue; |
| 2344 | auto &ResByArg = I->second; |
| 2345 | // FIXME: We should figure out what to do about the "function name" argument |
| 2346 | // to the apply* functions, as the function names are unavailable during the |
| 2347 | // importing phase. For now we just pass the empty string. This does not |
| 2348 | // impact correctness because the function names are just used for remarks. |
| 2349 | switch (ResByArg.TheKind) { |
| 2350 | case WholeProgramDevirtResolution::ByArg::UniformRetVal: |
| 2351 | applyUniformRetValOpt(CSInfo&: CSByConstantArg.second, FnName: "", TheRetVal: ResByArg.Info); |
| 2352 | break; |
| 2353 | case WholeProgramDevirtResolution::ByArg::UniqueRetVal: { |
| 2354 | Constant *UniqueMemberAddr = |
| 2355 | importGlobal(Slot, Args: CSByConstantArg.first, Name: "unique_member"); |
| 2356 | applyUniqueRetValOpt(CSInfo&: CSByConstantArg.second, FnName: "", IsOne: ResByArg.Info, |
| 2357 | UniqueMemberAddr); |
| 2358 | break; |
| 2359 | } |
| 2360 | case WholeProgramDevirtResolution::ByArg::VirtualConstProp: { |
| 2361 | Constant *Byte = ConstantInt::get(Ty: Int32Ty, V: ResByArg.Byte); |
| 2362 | Constant *Bit = importConstant(Slot, Args: CSByConstantArg.first, Name: "bit", IntTy: Int8Ty, |
| 2363 | Storage: ResByArg.Bit); |
| 2364 | applyVirtualConstProp(CSInfo&: CSByConstantArg.second, FnName: "", Byte, Bit); |
| 2365 | break; |
| 2366 | } |
| 2367 | default: |
| 2368 | break; |
| 2369 | } |
| 2370 | } |
| 2371 | |
| 2372 | if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) { |
| 2373 | // The type of the function is irrelevant, because it's bitcast at calls |
| 2374 | // anyhow. |
| 2375 | auto *JT = cast<Function>( |
| 2376 | Val: M.getOrInsertFunction(Name: getGlobalName(Slot, Args: {}, Name: "branch_funnel"), |
| 2377 | RetTy: Type::getVoidTy(C&: M.getContext())) |
| 2378 | .getCallee()); |
| 2379 | bool IsExported = false; |
| 2380 | applyICallBranchFunnel(SlotInfo, JT&: *JT, IsExported); |
| 2381 | assert(!IsExported); |
| 2382 | } |
| 2383 | } |
| 2384 | |
| 2385 | void DevirtModule::removeRedundantTypeTests() { |
| 2386 | auto *True = ConstantInt::getTrue(Context&: M.getContext()); |
| 2387 | for (auto &&U : NumUnsafeUsesForTypeTest) { |
| 2388 | if (U.second == 0) { |
| 2389 | U.first->replaceAllUsesWith(V: True); |
| 2390 | U.first->eraseFromParent(); |
| 2391 | } |
| 2392 | } |
| 2393 | } |
| 2394 | |
| 2395 | ValueInfo |
| 2396 | DevirtModule::lookUpFunctionValueInfo(Function *TheFn, |
| 2397 | ModuleSummaryIndex *ExportSummary) { |
| 2398 | assert((ExportSummary != nullptr) && |
| 2399 | "Caller guarantees ExportSummary is not nullptr"); |
| 2400 | |
| 2401 | const auto TheFnGUID = TheFn->getGUID(); |
| 2402 | const auto TheFnGUIDWithExportedName = |
| 2403 | GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: TheFn->getName()); |
| 2404 | // Look up ValueInfo with the GUID in the current linkage. |
| 2405 | ValueInfo TheFnVI = ExportSummary->getValueInfo(GUID: TheFnGUID); |
| 2406 | // If no entry is found and GUID is different from GUID computed using |
| 2407 | // exported name, look up ValueInfo with the exported name unconditionally. |
| 2408 | // This is a fallback. |
| 2409 | // |
| 2410 | // The reason to have a fallback: |
| 2411 | // 1. LTO could enable global value internalization via |
| 2412 | // `enable-lto-internalization`. |
| 2413 | // 2. The GUID in ExportedSummary is computed using exported name. |
| 2414 | if ((!TheFnVI) && (TheFnGUID != TheFnGUIDWithExportedName)) { |
| 2415 | TheFnVI = ExportSummary->getValueInfo(GUID: TheFnGUIDWithExportedName); |
| 2416 | } |
| 2417 | return TheFnVI; |
| 2418 | } |
| 2419 | |
| 2420 | bool DevirtModule::mustBeUnreachableFunction( |
| 2421 | Function *const F, ModuleSummaryIndex *ExportSummary) { |
| 2422 | if (WholeProgramDevirtKeepUnreachableFunction) |
| 2423 | return false; |
| 2424 | // First, learn unreachability by analyzing function IR. |
| 2425 | if (!F->isDeclaration()) { |
| 2426 | // A function must be unreachable if its entry block ends with an |
| 2427 | // 'unreachable'. |
| 2428 | return isa<UnreachableInst>(Val: F->getEntryBlock().getTerminator()); |
| 2429 | } |
| 2430 | // Learn unreachability from ExportSummary if ExportSummary is present. |
| 2431 | return ExportSummary && |
| 2432 | ::mustBeUnreachableFunction( |
| 2433 | TheFnVI: DevirtModule::lookUpFunctionValueInfo(TheFn: F, ExportSummary)); |
| 2434 | } |
| 2435 | |
| 2436 | bool DevirtModule::run() { |
| 2437 | // If only some of the modules were split, we cannot correctly perform |
| 2438 | // this transformation. We already checked for the presense of type tests |
| 2439 | // with partially split modules during the thin link, and would have emitted |
| 2440 | // an error if any were found, so here we can simply return. |
| 2441 | if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) || |
| 2442 | (ImportSummary && ImportSummary->partiallySplitLTOUnits())) |
| 2443 | return false; |
| 2444 | |
| 2445 | Function *PublicTypeTestFunc = nullptr; |
| 2446 | // If we are in speculative devirtualization mode, we can work on the public |
| 2447 | // type test intrinsics. |
| 2448 | if (DevirtSpeculatively) |
| 2449 | PublicTypeTestFunc = |
| 2450 | Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test); |
| 2451 | Function *TypeTestFunc = |
| 2452 | Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test); |
| 2453 | Function *TypeCheckedLoadFunc = |
| 2454 | Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_checked_load); |
| 2455 | Function *TypeCheckedLoadRelativeFunc = Intrinsic::getDeclarationIfExists( |
| 2456 | M: &M, id: Intrinsic::type_checked_load_relative); |
| 2457 | Function *AssumeFunc = |
| 2458 | Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::assume); |
| 2459 | |
| 2460 | // Normally if there are no users of the devirtualization intrinsics in the |
| 2461 | // module, this pass has nothing to do. But if we are exporting, we also need |
| 2462 | // to handle any users that appear only in the function summaries. |
| 2463 | if (!ExportSummary && |
| 2464 | (((!PublicTypeTestFunc || PublicTypeTestFunc->use_empty()) && |
| 2465 | (!TypeTestFunc || TypeTestFunc->use_empty())) || |
| 2466 | !AssumeFunc || AssumeFunc->use_empty()) && |
| 2467 | (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()) && |
| 2468 | (!TypeCheckedLoadRelativeFunc || |
| 2469 | TypeCheckedLoadRelativeFunc->use_empty())) |
| 2470 | return false; |
| 2471 | |
| 2472 | // Rebuild type metadata into a map for easy lookup. |
| 2473 | std::vector<VTableBits> Bits; |
| 2474 | DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap; |
| 2475 | buildTypeIdentifierMap(Bits, TypeIdMap); |
| 2476 | |
| 2477 | if (PublicTypeTestFunc && AssumeFunc) |
| 2478 | scanTypeTestUsers(TypeTestFunc: PublicTypeTestFunc, TypeIdMap); |
| 2479 | |
| 2480 | if (TypeTestFunc && AssumeFunc) |
| 2481 | scanTypeTestUsers(TypeTestFunc, TypeIdMap); |
| 2482 | |
| 2483 | if (TypeCheckedLoadFunc) |
| 2484 | scanTypeCheckedLoadUsers(TypeCheckedLoadFunc); |
| 2485 | |
| 2486 | if (TypeCheckedLoadRelativeFunc) |
| 2487 | scanTypeCheckedLoadUsers(TypeCheckedLoadFunc: TypeCheckedLoadRelativeFunc); |
| 2488 | |
| 2489 | if (ImportSummary) { |
| 2490 | for (auto &S : CallSlots) |
| 2491 | importResolution(Slot: S.first, SlotInfo&: S.second); |
| 2492 | |
| 2493 | removeRedundantTypeTests(); |
| 2494 | |
| 2495 | // We have lowered or deleted the type intrinsics, so we will no longer have |
| 2496 | // enough information to reason about the liveness of virtual function |
| 2497 | // pointers in GlobalDCE. |
| 2498 | for (GlobalVariable &GV : M.globals()) |
| 2499 | GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility); |
| 2500 | |
| 2501 | // The rest of the code is only necessary when exporting or during regular |
| 2502 | // LTO, so we are done. |
| 2503 | return true; |
| 2504 | } |
| 2505 | |
| 2506 | if (TypeIdMap.empty()) |
| 2507 | return true; |
| 2508 | |
| 2509 | // Collect information from summary about which calls to try to devirtualize. |
| 2510 | if (ExportSummary) { |
| 2511 | DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID; |
| 2512 | for (auto &P : TypeIdMap) { |
| 2513 | if (auto *TypeId = dyn_cast<MDString>(Val: P.first)) |
| 2514 | MetadataByGUID[GlobalValue::getGUIDAssumingExternalLinkage( |
| 2515 | GlobalName: TypeId->getString())] |
| 2516 | .push_back(NewVal: TypeId); |
| 2517 | } |
| 2518 | |
| 2519 | for (auto &P : *ExportSummary) { |
| 2520 | for (auto &S : P.second.getSummaryList()) { |
| 2521 | auto *FS = dyn_cast<FunctionSummary>(Val: S.get()); |
| 2522 | if (!FS) |
| 2523 | continue; |
| 2524 | // FIXME: Only add live functions. |
| 2525 | for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) { |
| 2526 | for (Metadata *MD : MetadataByGUID[VF.GUID]) { |
| 2527 | CallSlots[{.TypeID: MD, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS); |
| 2528 | } |
| 2529 | } |
| 2530 | for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) { |
| 2531 | for (Metadata *MD : MetadataByGUID[VF.GUID]) { |
| 2532 | CallSlots[{.TypeID: MD, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS); |
| 2533 | } |
| 2534 | } |
| 2535 | for (const FunctionSummary::ConstVCall &VC : |
| 2536 | FS->type_test_assume_const_vcalls()) { |
| 2537 | for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) { |
| 2538 | CallSlots[{.TypeID: MD, .ByteOffset: VC.VFunc.Offset}] |
| 2539 | .ConstCSInfo[VC.Args] |
| 2540 | .addSummaryTypeTestAssumeUser(FS); |
| 2541 | } |
| 2542 | } |
| 2543 | for (const FunctionSummary::ConstVCall &VC : |
| 2544 | FS->type_checked_load_const_vcalls()) { |
| 2545 | for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) { |
| 2546 | CallSlots[{.TypeID: MD, .ByteOffset: VC.VFunc.Offset}] |
| 2547 | .ConstCSInfo[VC.Args] |
| 2548 | .addSummaryTypeCheckedLoadUser(FS); |
| 2549 | } |
| 2550 | } |
| 2551 | } |
| 2552 | } |
| 2553 | } |
| 2554 | |
| 2555 | // For each (type, offset) pair: |
| 2556 | bool DidVirtualConstProp = false; |
| 2557 | std::map<std::string, GlobalValue *> DevirtTargets; |
| 2558 | for (auto &S : CallSlots) { |
| 2559 | // Search each of the members of the type identifier for the virtual |
| 2560 | // function implementation at offset S.first.ByteOffset, and add to |
| 2561 | // TargetsForSlot. |
| 2562 | std::vector<VirtualCallTarget> TargetsForSlot; |
| 2563 | WholeProgramDevirtResolution *Res = nullptr; |
| 2564 | const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[S.first.TypeID]; |
| 2565 | if (ExportSummary && isa<MDString>(Val: S.first.TypeID) && |
| 2566 | TypeMemberInfos.size()) |
| 2567 | // For any type id used on a global's type metadata, create the type id |
| 2568 | // summary resolution regardless of whether we can devirtualize, so that |
| 2569 | // lower type tests knows the type id is not Unsat. If it was not used on |
| 2570 | // a global's type metadata, the TypeIdMap entry set will be empty, and |
| 2571 | // we don't want to create an entry (with the default Unknown type |
| 2572 | // resolution), which can prevent detection of the Unsat. |
| 2573 | Res = &ExportSummary |
| 2574 | ->getOrInsertTypeIdSummary( |
| 2575 | TypeId: cast<MDString>(Val: S.first.TypeID)->getString()) |
| 2576 | .WPDRes[S.first.ByteOffset]; |
| 2577 | if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos, |
| 2578 | ByteOffset: S.first.ByteOffset, ExportSummary)) { |
| 2579 | bool SingleImplDevirt = |
| 2580 | trySingleImplDevirt(ExportSummary, TargetsForSlot, SlotInfo&: S.second, Res); |
| 2581 | // Out of speculative devirtualization mode, Try to apply virtual constant |
| 2582 | // propagation or branch funneling. |
| 2583 | // TODO: This should eventually be enabled for non-public type tests. |
| 2584 | if (!SingleImplDevirt && !DevirtSpeculatively) { |
| 2585 | DidVirtualConstProp |= |
| 2586 | tryVirtualConstProp(TargetsForSlot, SlotInfo&: S.second, Res, Slot: S.first); |
| 2587 | |
| 2588 | tryICallBranchFunnel(TargetsForSlot, SlotInfo&: S.second, Res, Slot: S.first); |
| 2589 | } |
| 2590 | |
| 2591 | // Collect functions devirtualized at least for one call site for stats. |
| 2592 | if (RemarksEnabled || AreStatisticsEnabled()) |
| 2593 | for (const auto &T : TargetsForSlot) |
| 2594 | if (T.WasDevirt) |
| 2595 | DevirtTargets[std::string(T.Fn->getName())] = T.Fn; |
| 2596 | } |
| 2597 | |
| 2598 | // CFI-specific: if we are exporting and any llvm.type.checked.load |
| 2599 | // intrinsics were *not* devirtualized, we need to add the resulting |
| 2600 | // llvm.type.test intrinsics to the function summaries so that the |
| 2601 | // LowerTypeTests pass will export them. |
| 2602 | if (ExportSummary && isa<MDString>(Val: S.first.TypeID)) { |
| 2603 | auto GUID = GlobalValue::getGUIDAssumingExternalLinkage( |
| 2604 | GlobalName: cast<MDString>(Val: S.first.TypeID)->getString()); |
| 2605 | auto AddTypeTestsForTypeCheckedLoads = [&](CallSiteInfo &CSI) { |
| 2606 | if (!CSI.AllCallSitesDevirted) |
| 2607 | for (auto *FS : CSI.SummaryTypeCheckedLoadUsers) |
| 2608 | FS->addTypeTest(Guid: GUID); |
| 2609 | }; |
| 2610 | AddTypeTestsForTypeCheckedLoads(S.second.CSInfo); |
| 2611 | for (auto &CCS : S.second.ConstCSInfo) |
| 2612 | AddTypeTestsForTypeCheckedLoads(CCS.second); |
| 2613 | } |
| 2614 | } |
| 2615 | |
| 2616 | if (RemarksEnabled) { |
| 2617 | // Generate remarks for each devirtualized function. |
| 2618 | for (const auto &DT : DevirtTargets) { |
| 2619 | GlobalValue *GV = DT.second; |
| 2620 | auto *F = dyn_cast<Function>(Val: GV); |
| 2621 | if (!F) { |
| 2622 | auto *A = dyn_cast<GlobalAlias>(Val: GV); |
| 2623 | assert(A && isa<Function>(A->getAliasee())); |
| 2624 | F = dyn_cast<Function>(Val: A->getAliasee()); |
| 2625 | assert(F); |
| 2626 | } |
| 2627 | |
| 2628 | using namespace ore; |
| 2629 | OREGetter(*F).emit(OptDiag: OptimizationRemark(DEBUG_TYPE, "Devirtualized", F) |
| 2630 | << "devirtualized "<< NV( "FunctionName", DT.first)); |
| 2631 | } |
| 2632 | } |
| 2633 | |
| 2634 | NumDevirtTargets += DevirtTargets.size(); |
| 2635 | |
| 2636 | removeRedundantTypeTests(); |
| 2637 | |
| 2638 | // Rebuild each global we touched as part of virtual constant propagation to |
| 2639 | // include the before and after bytes. |
| 2640 | if (DidVirtualConstProp) |
| 2641 | for (VTableBits &B : Bits) |
| 2642 | rebuildGlobal(B); |
| 2643 | |
| 2644 | // We have lowered or deleted the type intrinsics, so we will no longer have |
| 2645 | // enough information to reason about the liveness of virtual function |
| 2646 | // pointers in GlobalDCE. |
| 2647 | for (GlobalVariable &GV : M.globals()) |
| 2648 | GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility); |
| 2649 | |
| 2650 | for (auto *CI : CallsWithPtrAuthBundleRemoved) |
| 2651 | CI->eraseFromParent(); |
| 2652 | |
| 2653 | return true; |
| 2654 | } |
| 2655 | |
| 2656 | void DevirtIndex::run() { |
| 2657 | if (ExportSummary.typeIdCompatibleVtableMap().empty()) |
| 2658 | return; |
| 2659 | |
| 2660 | // Assert that we haven't made any changes that would affect the hasLocal() |
| 2661 | // flag on the GUID summary info. |
| 2662 | assert(!ExportSummary.withInternalizeAndPromote() && |
| 2663 | "Expect index-based WPD to run before internalization and promotion"); |
| 2664 | |
| 2665 | DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID; |
| 2666 | for (const auto &P : ExportSummary.typeIdCompatibleVtableMap()) { |
| 2667 | NameByGUID[GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: P.first)].push_back( |
| 2668 | x: P.first); |
| 2669 | // Create the type id summary resolution regardlness of whether we can |
| 2670 | // devirtualize, so that lower type tests knows the type id is used on |
| 2671 | // a global and not Unsat. We do this here rather than in the loop over the |
| 2672 | // CallSlots, since that handling will only see type tests that directly |
| 2673 | // feed assumes, and we would miss any that aren't currently handled by WPD |
| 2674 | // (such as type tests that feed assumes via phis). |
| 2675 | ExportSummary.getOrInsertTypeIdSummary(TypeId: P.first); |
| 2676 | } |
| 2677 | |
| 2678 | // Collect information from summary about which calls to try to devirtualize. |
| 2679 | for (auto &P : ExportSummary) { |
| 2680 | for (auto &S : P.second.getSummaryList()) { |
| 2681 | auto *FS = dyn_cast<FunctionSummary>(Val: S.get()); |
| 2682 | if (!FS) |
| 2683 | continue; |
| 2684 | // FIXME: Only add live functions. |
| 2685 | for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) { |
| 2686 | for (StringRef Name : NameByGUID[VF.GUID]) { |
| 2687 | CallSlots[{.TypeID: Name, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS); |
| 2688 | } |
| 2689 | } |
| 2690 | for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) { |
| 2691 | for (StringRef Name : NameByGUID[VF.GUID]) { |
| 2692 | CallSlots[{.TypeID: Name, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS); |
| 2693 | } |
| 2694 | } |
| 2695 | for (const FunctionSummary::ConstVCall &VC : |
| 2696 | FS->type_test_assume_const_vcalls()) { |
| 2697 | for (StringRef Name : NameByGUID[VC.VFunc.GUID]) { |
| 2698 | CallSlots[{.TypeID: Name, .ByteOffset: VC.VFunc.Offset}] |
| 2699 | .ConstCSInfo[VC.Args] |
| 2700 | .addSummaryTypeTestAssumeUser(FS); |
| 2701 | } |
| 2702 | } |
| 2703 | for (const FunctionSummary::ConstVCall &VC : |
| 2704 | FS->type_checked_load_const_vcalls()) { |
| 2705 | for (StringRef Name : NameByGUID[VC.VFunc.GUID]) { |
| 2706 | CallSlots[{.TypeID: Name, .ByteOffset: VC.VFunc.Offset}] |
| 2707 | .ConstCSInfo[VC.Args] |
| 2708 | .addSummaryTypeCheckedLoadUser(FS); |
| 2709 | } |
| 2710 | } |
| 2711 | } |
| 2712 | } |
| 2713 | |
| 2714 | std::set<ValueInfo> DevirtTargets; |
| 2715 | // For each (type, offset) pair: |
| 2716 | for (auto &S : CallSlots) { |
| 2717 | // Search each of the members of the type identifier for the virtual |
| 2718 | // function implementation at offset S.first.ByteOffset, and add to |
| 2719 | // TargetsForSlot. |
| 2720 | std::vector<ValueInfo> TargetsForSlot; |
| 2721 | auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(TypeId: S.first.TypeID); |
| 2722 | assert(TidSummary); |
| 2723 | // The type id summary would have been created while building the NameByGUID |
| 2724 | // map earlier. |
| 2725 | WholeProgramDevirtResolution *Res = |
| 2726 | &ExportSummary.getTypeIdSummary(TypeId: S.first.TypeID) |
| 2727 | ->WPDRes[S.first.ByteOffset]; |
| 2728 | if (tryFindVirtualCallTargets(TargetsForSlot, TIdInfo: *TidSummary, |
| 2729 | ByteOffset: S.first.ByteOffset)) { |
| 2730 | |
| 2731 | if (!trySingleImplDevirt(TargetsForSlot, SlotSummary&: S.first, SlotInfo&: S.second, Res, |
| 2732 | DevirtTargets)) |
| 2733 | continue; |
| 2734 | } |
| 2735 | } |
| 2736 | |
| 2737 | // Optionally have the thin link print message for each devirtualized |
| 2738 | // function. |
| 2739 | if (PrintSummaryDevirt) |
| 2740 | for (const auto &DT : DevirtTargets) |
| 2741 | errs() << "Devirtualized call to "<< DT << "\n"; |
| 2742 | |
| 2743 | NumDevirtTargets += DevirtTargets.size(); |
| 2744 | } |
| 2745 |
Generated on 2026-Oct-10 from project llvm_projects revision b1dd93c6a
Powered by 
Code Browser 2.1
Generator usage only permitted with license.