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