| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/IPO/LowerTypeTests.cpp |
| Warning: | line 1555, column 11 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LowerTypeTests.cpp - type metadata lowering pass -------------------===// | |||
| 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 lowers type metadata and calls to the llvm.type.test intrinsic. | |||
| 10 | // It also ensures that globals are properly laid out for the | |||
| 11 | // llvm.icall.branch.funnel intrinsic. | |||
| 12 | // See http://llvm.org/docs/TypeMetadata.html for more information. | |||
| 13 | // | |||
| 14 | //===----------------------------------------------------------------------===// | |||
| 15 | ||||
| 16 | #include "llvm/Transforms/IPO/LowerTypeTests.h" | |||
| 17 | #include "llvm/ADT/APInt.h" | |||
| 18 | #include "llvm/ADT/ArrayRef.h" | |||
| 19 | #include "llvm/ADT/DenseMap.h" | |||
| 20 | #include "llvm/ADT/EquivalenceClasses.h" | |||
| 21 | #include "llvm/ADT/PointerUnion.h" | |||
| 22 | #include "llvm/ADT/SetVector.h" | |||
| 23 | #include "llvm/ADT/SmallVector.h" | |||
| 24 | #include "llvm/ADT/Statistic.h" | |||
| 25 | #include "llvm/ADT/StringRef.h" | |||
| 26 | #include "llvm/ADT/TinyPtrVector.h" | |||
| 27 | #include "llvm/ADT/Triple.h" | |||
| 28 | #include "llvm/Analysis/TypeMetadataUtils.h" | |||
| 29 | #include "llvm/Analysis/ValueTracking.h" | |||
| 30 | #include "llvm/IR/Attributes.h" | |||
| 31 | #include "llvm/IR/BasicBlock.h" | |||
| 32 | #include "llvm/IR/Constant.h" | |||
| 33 | #include "llvm/IR/Constants.h" | |||
| 34 | #include "llvm/IR/DataLayout.h" | |||
| 35 | #include "llvm/IR/DerivedTypes.h" | |||
| 36 | #include "llvm/IR/Function.h" | |||
| 37 | #include "llvm/IR/GlobalAlias.h" | |||
| 38 | #include "llvm/IR/GlobalObject.h" | |||
| 39 | #include "llvm/IR/GlobalValue.h" | |||
| 40 | #include "llvm/IR/GlobalVariable.h" | |||
| 41 | #include "llvm/IR/IRBuilder.h" | |||
| 42 | #include "llvm/IR/InlineAsm.h" | |||
| 43 | #include "llvm/IR/Instruction.h" | |||
| 44 | #include "llvm/IR/Instructions.h" | |||
| 45 | #include "llvm/IR/Intrinsics.h" | |||
| 46 | #include "llvm/IR/LLVMContext.h" | |||
| 47 | #include "llvm/IR/Metadata.h" | |||
| 48 | #include "llvm/IR/Module.h" | |||
| 49 | #include "llvm/IR/ModuleSummaryIndex.h" | |||
| 50 | #include "llvm/IR/ModuleSummaryIndexYAML.h" | |||
| 51 | #include "llvm/IR/Operator.h" | |||
| 52 | #include "llvm/IR/PassManager.h" | |||
| 53 | #include "llvm/IR/Type.h" | |||
| 54 | #include "llvm/IR/Use.h" | |||
| 55 | #include "llvm/IR/User.h" | |||
| 56 | #include "llvm/IR/Value.h" | |||
| 57 | #include "llvm/InitializePasses.h" | |||
| 58 | #include "llvm/Pass.h" | |||
| 59 | #include "llvm/Support/Allocator.h" | |||
| 60 | #include "llvm/Support/Casting.h" | |||
| 61 | #include "llvm/Support/CommandLine.h" | |||
| 62 | #include "llvm/Support/Debug.h" | |||
| 63 | #include "llvm/Support/Error.h" | |||
| 64 | #include "llvm/Support/ErrorHandling.h" | |||
| 65 | #include "llvm/Support/FileSystem.h" | |||
| 66 | #include "llvm/Support/MathExtras.h" | |||
| 67 | #include "llvm/Support/MemoryBuffer.h" | |||
| 68 | #include "llvm/Support/TrailingObjects.h" | |||
| 69 | #include "llvm/Support/YAMLTraits.h" | |||
| 70 | #include "llvm/Support/raw_ostream.h" | |||
| 71 | #include "llvm/Transforms/IPO.h" | |||
| 72 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
| 73 | #include "llvm/Transforms/Utils/ModuleUtils.h" | |||
| 74 | #include <algorithm> | |||
| 75 | #include <cassert> | |||
| 76 | #include <cstdint> | |||
| 77 | #include <memory> | |||
| 78 | #include <set> | |||
| 79 | #include <string> | |||
| 80 | #include <system_error> | |||
| 81 | #include <utility> | |||
| 82 | #include <vector> | |||
| 83 | ||||
| 84 | using namespace llvm; | |||
| 85 | using namespace lowertypetests; | |||
| 86 | ||||
| 87 | #define DEBUG_TYPE"lowertypetests" "lowertypetests" | |||
| 88 | ||||
| 89 | STATISTIC(ByteArraySizeBits, "Byte array size in bits")static llvm::Statistic ByteArraySizeBits = {"lowertypetests", "ByteArraySizeBits", "Byte array size in bits"}; | |||
| 90 | STATISTIC(ByteArraySizeBytes, "Byte array size in bytes")static llvm::Statistic ByteArraySizeBytes = {"lowertypetests" , "ByteArraySizeBytes", "Byte array size in bytes"}; | |||
| 91 | STATISTIC(NumByteArraysCreated, "Number of byte arrays created")static llvm::Statistic NumByteArraysCreated = {"lowertypetests" , "NumByteArraysCreated", "Number of byte arrays created"}; | |||
| 92 | STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered")static llvm::Statistic NumTypeTestCallsLowered = {"lowertypetests" , "NumTypeTestCallsLowered", "Number of type test calls lowered" }; | |||
| 93 | STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers")static llvm::Statistic NumTypeIdDisjointSets = {"lowertypetests" , "NumTypeIdDisjointSets", "Number of disjoint sets of type identifiers" }; | |||
| 94 | ||||
| 95 | static cl::opt<bool> AvoidReuse( | |||
| 96 | "lowertypetests-avoid-reuse", | |||
| 97 | cl::desc("Try to avoid reuse of byte array addresses using aliases"), | |||
| 98 | cl::Hidden, cl::init(true)); | |||
| 99 | ||||
| 100 | static cl::opt<PassSummaryAction> ClSummaryAction( | |||
| 101 | "lowertypetests-summary-action", | |||
| 102 | cl::desc("What to do with the summary when running this pass"), | |||
| 103 | cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing")llvm::cl::OptionEnumValue { "none", int(PassSummaryAction::None ), "Do nothing" }, | |||
| 104 | clEnumValN(PassSummaryAction::Import, "import",llvm::cl::OptionEnumValue { "import", int(PassSummaryAction:: Import), "Import typeid resolutions from summary and globals" } | |||
| 105 | "Import typeid resolutions from summary and globals")llvm::cl::OptionEnumValue { "import", int(PassSummaryAction:: Import), "Import typeid resolutions from summary and globals" }, | |||
| 106 | clEnumValN(PassSummaryAction::Export, "export",llvm::cl::OptionEnumValue { "export", int(PassSummaryAction:: Export), "Export typeid resolutions to summary and globals" } | |||
| 107 | "Export typeid resolutions to summary and globals")llvm::cl::OptionEnumValue { "export", int(PassSummaryAction:: Export), "Export typeid resolutions to summary and globals" }), | |||
| 108 | cl::Hidden); | |||
| 109 | ||||
| 110 | static cl::opt<std::string> ClReadSummary( | |||
| 111 | "lowertypetests-read-summary", | |||
| 112 | cl::desc("Read summary from given YAML file before running pass"), | |||
| 113 | cl::Hidden); | |||
| 114 | ||||
| 115 | static cl::opt<std::string> ClWriteSummary( | |||
| 116 | "lowertypetests-write-summary", | |||
| 117 | cl::desc("Write summary to given YAML file after running pass"), | |||
| 118 | cl::Hidden); | |||
| 119 | ||||
| 120 | static cl::opt<bool> | |||
| 121 | ClDropTypeTests("lowertypetests-drop-type-tests", | |||
| 122 | cl::desc("Simply drop type test assume sequences"), | |||
| 123 | cl::Hidden, cl::init(false)); | |||
| 124 | ||||
| 125 | bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const { | |||
| 126 | if (Offset < ByteOffset) | |||
| 127 | return false; | |||
| 128 | ||||
| 129 | if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0) | |||
| 130 | return false; | |||
| 131 | ||||
| 132 | uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2; | |||
| 133 | if (BitOffset >= BitSize) | |||
| 134 | return false; | |||
| 135 | ||||
| 136 | return Bits.count(BitOffset); | |||
| 137 | } | |||
| 138 | ||||
| 139 | void BitSetInfo::print(raw_ostream &OS) const { | |||
| 140 | OS << "offset " << ByteOffset << " size " << BitSize << " align " | |||
| 141 | << (1 << AlignLog2); | |||
| 142 | ||||
| 143 | if (isAllOnes()) { | |||
| 144 | OS << " all-ones\n"; | |||
| 145 | return; | |||
| 146 | } | |||
| 147 | ||||
| 148 | OS << " { "; | |||
| 149 | for (uint64_t B : Bits) | |||
| 150 | OS << B << ' '; | |||
| 151 | OS << "}\n"; | |||
| 152 | } | |||
| 153 | ||||
| 154 | BitSetInfo BitSetBuilder::build() { | |||
| 155 | if (Min > Max) | |||
| 156 | Min = 0; | |||
| 157 | ||||
| 158 | // Normalize each offset against the minimum observed offset, and compute | |||
| 159 | // the bitwise OR of each of the offsets. The number of trailing zeros | |||
| 160 | // in the mask gives us the log2 of the alignment of all offsets, which | |||
| 161 | // allows us to compress the bitset by only storing one bit per aligned | |||
| 162 | // address. | |||
| 163 | uint64_t Mask = 0; | |||
| 164 | for (uint64_t &Offset : Offsets) { | |||
| 165 | Offset -= Min; | |||
| 166 | Mask |= Offset; | |||
| 167 | } | |||
| 168 | ||||
| 169 | BitSetInfo BSI; | |||
| 170 | BSI.ByteOffset = Min; | |||
| 171 | ||||
| 172 | BSI.AlignLog2 = 0; | |||
| 173 | if (Mask != 0) | |||
| 174 | BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined); | |||
| 175 | ||||
| 176 | // Build the compressed bitset while normalizing the offsets against the | |||
| 177 | // computed alignment. | |||
| 178 | BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1; | |||
| 179 | for (uint64_t Offset : Offsets) { | |||
| 180 | Offset >>= BSI.AlignLog2; | |||
| 181 | BSI.Bits.insert(Offset); | |||
| 182 | } | |||
| 183 | ||||
| 184 | return BSI; | |||
| 185 | } | |||
| 186 | ||||
| 187 | void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) { | |||
| 188 | // Create a new fragment to hold the layout for F. | |||
| 189 | Fragments.emplace_back(); | |||
| 190 | std::vector<uint64_t> &Fragment = Fragments.back(); | |||
| 191 | uint64_t FragmentIndex = Fragments.size() - 1; | |||
| 192 | ||||
| 193 | for (auto ObjIndex : F) { | |||
| 194 | uint64_t OldFragmentIndex = FragmentMap[ObjIndex]; | |||
| 195 | if (OldFragmentIndex == 0) { | |||
| 196 | // We haven't seen this object index before, so just add it to the current | |||
| 197 | // fragment. | |||
| 198 | Fragment.push_back(ObjIndex); | |||
| 199 | } else { | |||
| 200 | // This index belongs to an existing fragment. Copy the elements of the | |||
| 201 | // old fragment into this one and clear the old fragment. We don't update | |||
| 202 | // the fragment map just yet, this ensures that any further references to | |||
| 203 | // indices from the old fragment in this fragment do not insert any more | |||
| 204 | // indices. | |||
| 205 | std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex]; | |||
| 206 | llvm::append_range(Fragment, OldFragment); | |||
| 207 | OldFragment.clear(); | |||
| 208 | } | |||
| 209 | } | |||
| 210 | ||||
| 211 | // Update the fragment map to point our object indices to this fragment. | |||
| 212 | for (uint64_t ObjIndex : Fragment) | |||
| 213 | FragmentMap[ObjIndex] = FragmentIndex; | |||
| 214 | } | |||
| 215 | ||||
| 216 | void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits, | |||
| 217 | uint64_t BitSize, uint64_t &AllocByteOffset, | |||
| 218 | uint8_t &AllocMask) { | |||
| 219 | // Find the smallest current allocation. | |||
| 220 | unsigned Bit = 0; | |||
| 221 | for (unsigned I = 1; I != BitsPerByte; ++I) | |||
| 222 | if (BitAllocs[I] < BitAllocs[Bit]) | |||
| 223 | Bit = I; | |||
| 224 | ||||
| 225 | AllocByteOffset = BitAllocs[Bit]; | |||
| 226 | ||||
| 227 | // Add our size to it. | |||
| 228 | unsigned ReqSize = AllocByteOffset + BitSize; | |||
| 229 | BitAllocs[Bit] = ReqSize; | |||
| 230 | if (Bytes.size() < ReqSize) | |||
| 231 | Bytes.resize(ReqSize); | |||
| 232 | ||||
| 233 | // Set our bits. | |||
| 234 | AllocMask = 1 << Bit; | |||
| 235 | for (uint64_t B : Bits) | |||
| 236 | Bytes[AllocByteOffset + B] |= AllocMask; | |||
| 237 | } | |||
| 238 | ||||
| 239 | bool lowertypetests::isJumpTableCanonical(Function *F) { | |||
| 240 | if (F->isDeclarationForLinker()) | |||
| 241 | return false; | |||
| 242 | auto *CI = mdconst::extract_or_null<ConstantInt>( | |||
| 243 | F->getParent()->getModuleFlag("CFI Canonical Jump Tables")); | |||
| 244 | if (!CI || CI->getZExtValue() != 0) | |||
| 245 | return true; | |||
| 246 | return F->hasFnAttribute("cfi-canonical-jump-table"); | |||
| 247 | } | |||
| 248 | ||||
| 249 | namespace { | |||
| 250 | ||||
| 251 | struct ByteArrayInfo { | |||
| 252 | std::set<uint64_t> Bits; | |||
| 253 | uint64_t BitSize; | |||
| 254 | GlobalVariable *ByteArray; | |||
| 255 | GlobalVariable *MaskGlobal; | |||
| 256 | uint8_t *MaskPtr = nullptr; | |||
| 257 | }; | |||
| 258 | ||||
| 259 | /// A POD-like structure that we use to store a global reference together with | |||
| 260 | /// its metadata types. In this pass we frequently need to query the set of | |||
| 261 | /// metadata types referenced by a global, which at the IR level is an expensive | |||
| 262 | /// operation involving a map lookup; this data structure helps to reduce the | |||
| 263 | /// number of times we need to do this lookup. | |||
| 264 | class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> { | |||
| 265 | friend TrailingObjects; | |||
| 266 | ||||
| 267 | GlobalObject *GO; | |||
| 268 | size_t NTypes; | |||
| 269 | ||||
| 270 | // For functions: true if the jump table is canonical. This essentially means | |||
| 271 | // whether the canonical address (i.e. the symbol table entry) of the function | |||
| 272 | // is provided by the local jump table. This is normally the same as whether | |||
| 273 | // the function is defined locally, but if canonical jump tables are disabled | |||
| 274 | // by the user then the jump table never provides a canonical definition. | |||
| 275 | bool IsJumpTableCanonical; | |||
| 276 | ||||
| 277 | // For functions: true if this function is either defined or used in a thinlto | |||
| 278 | // module and its jumptable entry needs to be exported to thinlto backends. | |||
| 279 | bool IsExported; | |||
| 280 | ||||
| 281 | size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; } | |||
| 282 | ||||
| 283 | public: | |||
| 284 | static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO, | |||
| 285 | bool IsJumpTableCanonical, bool IsExported, | |||
| 286 | ArrayRef<MDNode *> Types) { | |||
| 287 | auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate( | |||
| 288 | totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember))); | |||
| 289 | GTM->GO = GO; | |||
| 290 | GTM->NTypes = Types.size(); | |||
| 291 | GTM->IsJumpTableCanonical = IsJumpTableCanonical; | |||
| 292 | GTM->IsExported = IsExported; | |||
| 293 | std::uninitialized_copy(Types.begin(), Types.end(), | |||
| 294 | GTM->getTrailingObjects<MDNode *>()); | |||
| 295 | return GTM; | |||
| 296 | } | |||
| 297 | ||||
| 298 | GlobalObject *getGlobal() const { | |||
| 299 | return GO; | |||
| 300 | } | |||
| 301 | ||||
| 302 | bool isJumpTableCanonical() const { | |||
| 303 | return IsJumpTableCanonical; | |||
| 304 | } | |||
| 305 | ||||
| 306 | bool isExported() const { | |||
| 307 | return IsExported; | |||
| 308 | } | |||
| 309 | ||||
| 310 | ArrayRef<MDNode *> types() const { | |||
| 311 | return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes); | |||
| 312 | } | |||
| 313 | }; | |||
| 314 | ||||
| 315 | struct ICallBranchFunnel final | |||
| 316 | : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> { | |||
| 317 | static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI, | |||
| 318 | ArrayRef<GlobalTypeMember *> Targets, | |||
| 319 | unsigned UniqueId) { | |||
| 320 | auto *Call = static_cast<ICallBranchFunnel *>( | |||
| 321 | Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()), | |||
| 322 | alignof(ICallBranchFunnel))); | |||
| 323 | Call->CI = CI; | |||
| 324 | Call->UniqueId = UniqueId; | |||
| 325 | Call->NTargets = Targets.size(); | |||
| 326 | std::uninitialized_copy(Targets.begin(), Targets.end(), | |||
| 327 | Call->getTrailingObjects<GlobalTypeMember *>()); | |||
| 328 | return Call; | |||
| 329 | } | |||
| 330 | ||||
| 331 | CallInst *CI; | |||
| 332 | ArrayRef<GlobalTypeMember *> targets() const { | |||
| 333 | return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets); | |||
| 334 | } | |||
| 335 | ||||
| 336 | unsigned UniqueId; | |||
| 337 | ||||
| 338 | private: | |||
| 339 | size_t NTargets; | |||
| 340 | }; | |||
| 341 | ||||
| 342 | struct ScopedSaveAliaseesAndUsed { | |||
| 343 | Module &M; | |||
| 344 | SmallVector<GlobalValue *, 4> Used, CompilerUsed; | |||
| 345 | std::vector<std::pair<GlobalIndirectSymbol *, Function *>> FunctionAliases; | |||
| 346 | ||||
| 347 | ScopedSaveAliaseesAndUsed(Module &M) : M(M) { | |||
| 348 | // The users of this class want to replace all function references except | |||
| 349 | // for aliases and llvm.used/llvm.compiler.used with references to a jump | |||
| 350 | // table. We avoid replacing aliases in order to avoid introducing a double | |||
| 351 | // indirection (or an alias pointing to a declaration in ThinLTO mode), and | |||
| 352 | // we avoid replacing llvm.used/llvm.compiler.used because these global | |||
| 353 | // variables describe properties of the global, not the jump table (besides, | |||
| 354 | // offseted references to the jump table in llvm.used are invalid). | |||
| 355 | // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly | |||
| 356 | // indirect) users", so what we do is save the list of globals referenced by | |||
| 357 | // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW | |||
| 358 | // replace the aliasees and then set them back to their original values at | |||
| 359 | // the end. | |||
| 360 | if (GlobalVariable *GV = collectUsedGlobalVariables(M, Used, false)) | |||
| 361 | GV->eraseFromParent(); | |||
| 362 | if (GlobalVariable *GV = collectUsedGlobalVariables(M, CompilerUsed, true)) | |||
| 363 | GV->eraseFromParent(); | |||
| 364 | ||||
| 365 | for (auto &GIS : concat<GlobalIndirectSymbol>(M.aliases(), M.ifuncs())) { | |||
| 366 | // FIXME: This should look past all aliases not just interposable ones, | |||
| 367 | // see discussion on D65118. | |||
| 368 | if (auto *F = | |||
| 369 | dyn_cast<Function>(GIS.getIndirectSymbol()->stripPointerCasts())) | |||
| 370 | FunctionAliases.push_back({&GIS, F}); | |||
| 371 | } | |||
| 372 | } | |||
| 373 | ||||
| 374 | ~ScopedSaveAliaseesAndUsed() { | |||
| 375 | appendToUsed(M, Used); | |||
| 376 | appendToCompilerUsed(M, CompilerUsed); | |||
| 377 | ||||
| 378 | for (auto P : FunctionAliases) | |||
| 379 | P.first->setIndirectSymbol( | |||
| 380 | ConstantExpr::getBitCast(P.second, P.first->getType())); | |||
| 381 | } | |||
| 382 | }; | |||
| 383 | ||||
| 384 | class LowerTypeTestsModule { | |||
| 385 | Module &M; | |||
| 386 | ||||
| 387 | ModuleSummaryIndex *ExportSummary; | |||
| 388 | const ModuleSummaryIndex *ImportSummary; | |||
| 389 | // Set when the client has invoked this to simply drop all type test assume | |||
| 390 | // sequences. | |||
| 391 | bool DropTypeTests; | |||
| 392 | ||||
| 393 | Triple::ArchType Arch; | |||
| 394 | Triple::OSType OS; | |||
| 395 | Triple::ObjectFormatType ObjectFormat; | |||
| 396 | ||||
| 397 | IntegerType *Int1Ty = Type::getInt1Ty(M.getContext()); | |||
| 398 | IntegerType *Int8Ty = Type::getInt8Ty(M.getContext()); | |||
| 399 | PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext()); | |||
| 400 | ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0); | |||
| 401 | IntegerType *Int32Ty = Type::getInt32Ty(M.getContext()); | |||
| 402 | PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty); | |||
| 403 | IntegerType *Int64Ty = Type::getInt64Ty(M.getContext()); | |||
| 404 | IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0); | |||
| 405 | ||||
| 406 | // Indirect function call index assignment counter for WebAssembly | |||
| 407 | uint64_t IndirectIndex = 1; | |||
| 408 | ||||
| 409 | // Mapping from type identifiers to the call sites that test them, as well as | |||
| 410 | // whether the type identifier needs to be exported to ThinLTO backends as | |||
| 411 | // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId). | |||
| 412 | struct TypeIdUserInfo { | |||
| 413 | std::vector<CallInst *> CallSites; | |||
| 414 | bool IsExported = false; | |||
| 415 | }; | |||
| 416 | DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers; | |||
| 417 | ||||
| 418 | /// This structure describes how to lower type tests for a particular type | |||
| 419 | /// identifier. It is either built directly from the global analysis (during | |||
| 420 | /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type | |||
| 421 | /// identifier summaries and external symbol references (in ThinLTO backends). | |||
| 422 | struct TypeIdLowering { | |||
| 423 | TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat; | |||
| 424 | ||||
| 425 | /// All except Unsat: the start address within the combined global. | |||
| 426 | Constant *OffsetedGlobal; | |||
| 427 | ||||
| 428 | /// ByteArray, Inline, AllOnes: log2 of the required global alignment | |||
| 429 | /// relative to the start address. | |||
| 430 | Constant *AlignLog2; | |||
| 431 | ||||
| 432 | /// ByteArray, Inline, AllOnes: one less than the size of the memory region | |||
| 433 | /// covering members of this type identifier as a multiple of 2^AlignLog2. | |||
| 434 | Constant *SizeM1; | |||
| 435 | ||||
| 436 | /// ByteArray: the byte array to test the address against. | |||
| 437 | Constant *TheByteArray; | |||
| 438 | ||||
| 439 | /// ByteArray: the bit mask to apply to bytes loaded from the byte array. | |||
| 440 | Constant *BitMask; | |||
| 441 | ||||
| 442 | /// Inline: the bit mask to test the address against. | |||
| 443 | Constant *InlineBits; | |||
| 444 | }; | |||
| 445 | ||||
| 446 | std::vector<ByteArrayInfo> ByteArrayInfos; | |||
| 447 | ||||
| 448 | Function *WeakInitializerFn = nullptr; | |||
| 449 | ||||
| 450 | bool shouldExportConstantsAsAbsoluteSymbols(); | |||
| 451 | uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL); | |||
| 452 | TypeIdLowering importTypeId(StringRef TypeId); | |||
| 453 | void importTypeTest(CallInst *CI); | |||
| 454 | void importFunction(Function *F, bool isJumpTableCanonical, | |||
| 455 | std::vector<GlobalAlias *> &AliasesToErase); | |||
| 456 | ||||
| 457 | BitSetInfo | |||
| 458 | buildBitSet(Metadata *TypeId, | |||
| 459 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); | |||
| 460 | ByteArrayInfo *createByteArray(BitSetInfo &BSI); | |||
| 461 | void allocateByteArrays(); | |||
| 462 | Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL, | |||
| 463 | Value *BitOffset); | |||
| 464 | void lowerTypeTestCalls( | |||
| 465 | ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, | |||
| 466 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); | |||
| 467 | Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI, | |||
| 468 | const TypeIdLowering &TIL); | |||
| 469 | ||||
| 470 | void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds, | |||
| 471 | ArrayRef<GlobalTypeMember *> Globals); | |||
| 472 | unsigned getJumpTableEntrySize(); | |||
| 473 | Type *getJumpTableEntryType(); | |||
| 474 | void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS, | |||
| 475 | Triple::ArchType JumpTableArch, | |||
| 476 | SmallVectorImpl<Value *> &AsmArgs, Function *Dest); | |||
| 477 | void verifyTypeMDNode(GlobalObject *GO, MDNode *Type); | |||
| 478 | void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds, | |||
| 479 | ArrayRef<GlobalTypeMember *> Functions); | |||
| 480 | void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds, | |||
| 481 | ArrayRef<GlobalTypeMember *> Functions); | |||
| 482 | void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds, | |||
| 483 | ArrayRef<GlobalTypeMember *> Functions); | |||
| 484 | void | |||
| 485 | buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds, | |||
| 486 | ArrayRef<GlobalTypeMember *> Globals, | |||
| 487 | ArrayRef<ICallBranchFunnel *> ICallBranchFunnels); | |||
| 488 | ||||
| 489 | void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT, | |||
| 490 | bool IsJumpTableCanonical); | |||
| 491 | void moveInitializerToModuleConstructor(GlobalVariable *GV); | |||
| 492 | void findGlobalVariableUsersOf(Constant *C, | |||
| 493 | SmallSetVector<GlobalVariable *, 8> &Out); | |||
| 494 | ||||
| 495 | void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions); | |||
| 496 | ||||
| 497 | /// replaceCfiUses - Go through the uses list for this definition | |||
| 498 | /// and make each use point to "V" instead of "this" when the use is outside | |||
| 499 | /// the block. 'This's use list is expected to have at least one element. | |||
| 500 | /// Unlike replaceAllUsesWith this function skips blockaddr and direct call | |||
| 501 | /// uses. | |||
| 502 | void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical); | |||
| 503 | ||||
| 504 | /// replaceDirectCalls - Go through the uses list for this definition and | |||
| 505 | /// replace each use, which is a direct function call. | |||
| 506 | void replaceDirectCalls(Value *Old, Value *New); | |||
| 507 | ||||
| 508 | public: | |||
| 509 | LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary, | |||
| 510 | const ModuleSummaryIndex *ImportSummary, | |||
| 511 | bool DropTypeTests); | |||
| 512 | ||||
| 513 | bool lower(); | |||
| 514 | ||||
| 515 | // Lower the module using the action and summary passed as command line | |||
| 516 | // arguments. For testing purposes only. | |||
| 517 | static bool runForTesting(Module &M); | |||
| 518 | }; | |||
| 519 | ||||
| 520 | struct LowerTypeTests : public ModulePass { | |||
| 521 | static char ID; | |||
| 522 | ||||
| 523 | bool UseCommandLine = false; | |||
| 524 | ||||
| 525 | ModuleSummaryIndex *ExportSummary; | |||
| 526 | const ModuleSummaryIndex *ImportSummary; | |||
| 527 | bool DropTypeTests; | |||
| 528 | ||||
| 529 | LowerTypeTests() : ModulePass(ID), UseCommandLine(true) { | |||
| 530 | initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); | |||
| 531 | } | |||
| 532 | ||||
| 533 | LowerTypeTests(ModuleSummaryIndex *ExportSummary, | |||
| 534 | const ModuleSummaryIndex *ImportSummary, bool DropTypeTests) | |||
| 535 | : ModulePass(ID), ExportSummary(ExportSummary), | |||
| 536 | ImportSummary(ImportSummary), | |||
| 537 | DropTypeTests(DropTypeTests || ClDropTypeTests) { | |||
| 538 | initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); | |||
| 539 | } | |||
| 540 | ||||
| 541 | bool runOnModule(Module &M) override { | |||
| 542 | if (UseCommandLine) | |||
| 543 | return LowerTypeTestsModule::runForTesting(M); | |||
| 544 | return LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests) | |||
| 545 | .lower(); | |||
| 546 | } | |||
| 547 | }; | |||
| 548 | ||||
| 549 | } // end anonymous namespace | |||
| 550 | ||||
| 551 | char LowerTypeTests::ID = 0; | |||
| 552 | ||||
| 553 | INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,static void *initializeLowerTypeTestsPassOnce(PassRegistry & Registry) { PassInfo *PI = new PassInfo( "Lower type metadata" , "lowertypetests", &LowerTypeTests::ID, PassInfo::NormalCtor_t (callDefaultCtor<LowerTypeTests>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLowerTypeTestsPassFlag; void llvm::initializeLowerTypeTestsPass (PassRegistry &Registry) { llvm::call_once(InitializeLowerTypeTestsPassFlag , initializeLowerTypeTestsPassOnce, std::ref(Registry)); } | |||
| 554 | false)static void *initializeLowerTypeTestsPassOnce(PassRegistry & Registry) { PassInfo *PI = new PassInfo( "Lower type metadata" , "lowertypetests", &LowerTypeTests::ID, PassInfo::NormalCtor_t (callDefaultCtor<LowerTypeTests>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLowerTypeTestsPassFlag; void llvm::initializeLowerTypeTestsPass (PassRegistry &Registry) { llvm::call_once(InitializeLowerTypeTestsPassFlag , initializeLowerTypeTestsPassOnce, std::ref(Registry)); } | |||
| 555 | ||||
| 556 | ModulePass * | |||
| 557 | llvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, | |||
| 558 | const ModuleSummaryIndex *ImportSummary, | |||
| 559 | bool DropTypeTests) { | |||
| 560 | return new LowerTypeTests(ExportSummary, ImportSummary, DropTypeTests); | |||
| 561 | } | |||
| 562 | ||||
| 563 | /// Build a bit set for TypeId using the object layouts in | |||
| 564 | /// GlobalLayout. | |||
| 565 | BitSetInfo LowerTypeTestsModule::buildBitSet( | |||
| 566 | Metadata *TypeId, | |||
| 567 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { | |||
| 568 | BitSetBuilder BSB; | |||
| 569 | ||||
| 570 | // Compute the byte offset of each address associated with this type | |||
| 571 | // identifier. | |||
| 572 | for (auto &GlobalAndOffset : GlobalLayout) { | |||
| 573 | for (MDNode *Type : GlobalAndOffset.first->types()) { | |||
| 574 | if (Type->getOperand(1) != TypeId) | |||
| 575 | continue; | |||
| 576 | uint64_t Offset = | |||
| 577 | cast<ConstantInt>( | |||
| 578 | cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) | |||
| 579 | ->getZExtValue(); | |||
| 580 | BSB.addOffset(GlobalAndOffset.second + Offset); | |||
| 581 | } | |||
| 582 | } | |||
| 583 | ||||
| 584 | return BSB.build(); | |||
| 585 | } | |||
| 586 | ||||
| 587 | /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in | |||
| 588 | /// Bits. This pattern matches to the bt instruction on x86. | |||
| 589 | static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits, | |||
| 590 | Value *BitOffset) { | |||
| 591 | auto BitsType = cast<IntegerType>(Bits->getType()); | |||
| 592 | unsigned BitWidth = BitsType->getBitWidth(); | |||
| 593 | ||||
| 594 | BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType); | |||
| 595 | Value *BitIndex = | |||
| 596 | B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1)); | |||
| 597 | Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex); | |||
| 598 | Value *MaskedBits = B.CreateAnd(Bits, BitMask); | |||
| 599 | return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0)); | |||
| 600 | } | |||
| 601 | ||||
| 602 | ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) { | |||
| 603 | // Create globals to stand in for byte arrays and masks. These never actually | |||
| 604 | // get initialized, we RAUW and erase them later in allocateByteArrays() once | |||
| 605 | // we know the offset and mask to use. | |||
| 606 | auto ByteArrayGlobal = new GlobalVariable( | |||
| 607 | M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); | |||
| 608 | auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true, | |||
| 609 | GlobalValue::PrivateLinkage, nullptr); | |||
| 610 | ||||
| 611 | ByteArrayInfos.emplace_back(); | |||
| 612 | ByteArrayInfo *BAI = &ByteArrayInfos.back(); | |||
| 613 | ||||
| 614 | BAI->Bits = BSI.Bits; | |||
| 615 | BAI->BitSize = BSI.BitSize; | |||
| 616 | BAI->ByteArray = ByteArrayGlobal; | |||
| 617 | BAI->MaskGlobal = MaskGlobal; | |||
| 618 | return BAI; | |||
| 619 | } | |||
| 620 | ||||
| 621 | void LowerTypeTestsModule::allocateByteArrays() { | |||
| 622 | llvm::stable_sort(ByteArrayInfos, | |||
| 623 | [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) { | |||
| 624 | return BAI1.BitSize > BAI2.BitSize; | |||
| 625 | }); | |||
| 626 | ||||
| 627 | std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size()); | |||
| 628 | ||||
| 629 | ByteArrayBuilder BAB; | |||
| 630 | for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { | |||
| 631 | ByteArrayInfo *BAI = &ByteArrayInfos[I]; | |||
| 632 | ||||
| 633 | uint8_t Mask; | |||
| 634 | BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask); | |||
| 635 | ||||
| 636 | BAI->MaskGlobal->replaceAllUsesWith( | |||
| 637 | ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy)); | |||
| 638 | BAI->MaskGlobal->eraseFromParent(); | |||
| 639 | if (BAI->MaskPtr) | |||
| 640 | *BAI->MaskPtr = Mask; | |||
| 641 | } | |||
| 642 | ||||
| 643 | Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes); | |||
| 644 | auto ByteArray = | |||
| 645 | new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true, | |||
| 646 | GlobalValue::PrivateLinkage, ByteArrayConst); | |||
| 647 | ||||
| 648 | for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { | |||
| 649 | ByteArrayInfo *BAI = &ByteArrayInfos[I]; | |||
| 650 | ||||
| 651 | Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0), | |||
| 652 | ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])}; | |||
| 653 | Constant *GEP = ConstantExpr::getInBoundsGetElementPtr( | |||
| 654 | ByteArrayConst->getType(), ByteArray, Idxs); | |||
| 655 | ||||
| 656 | // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures | |||
| 657 | // that the pc-relative displacement is folded into the lea instead of the | |||
| 658 | // test instruction getting another displacement. | |||
| 659 | GlobalAlias *Alias = GlobalAlias::create( | |||
| 660 | Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M); | |||
| 661 | BAI->ByteArray->replaceAllUsesWith(Alias); | |||
| 662 | BAI->ByteArray->eraseFromParent(); | |||
| 663 | } | |||
| 664 | ||||
| 665 | ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] + | |||
| 666 | BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] + | |||
| 667 | BAB.BitAllocs[6] + BAB.BitAllocs[7]; | |||
| 668 | ByteArraySizeBytes = BAB.Bytes.size(); | |||
| 669 | } | |||
| 670 | ||||
| 671 | /// Build a test that bit BitOffset is set in the type identifier that was | |||
| 672 | /// lowered to TIL, which must be either an Inline or a ByteArray. | |||
| 673 | Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B, | |||
| 674 | const TypeIdLowering &TIL, | |||
| 675 | Value *BitOffset) { | |||
| 676 | if (TIL.TheKind == TypeTestResolution::Inline) { | |||
| 677 | // If the bit set is sufficiently small, we can avoid a load by bit testing | |||
| 678 | // a constant. | |||
| 679 | return createMaskedBitTest(B, TIL.InlineBits, BitOffset); | |||
| 680 | } else { | |||
| 681 | Constant *ByteArray = TIL.TheByteArray; | |||
| 682 | if (AvoidReuse && !ImportSummary) { | |||
| 683 | // Each use of the byte array uses a different alias. This makes the | |||
| 684 | // backend less likely to reuse previously computed byte array addresses, | |||
| 685 | // improving the security of the CFI mechanism based on this pass. | |||
| 686 | // This won't work when importing because TheByteArray is external. | |||
| 687 | ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage, | |||
| 688 | "bits_use", ByteArray, &M); | |||
| 689 | } | |||
| 690 | ||||
| 691 | Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset); | |||
| 692 | Value *Byte = B.CreateLoad(Int8Ty, ByteAddr); | |||
| 693 | ||||
| 694 | Value *ByteAndMask = | |||
| 695 | B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty)); | |||
| 696 | return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0)); | |||
| 697 | } | |||
| 698 | } | |||
| 699 | ||||
| 700 | static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL, | |||
| 701 | Value *V, uint64_t COffset) { | |||
| 702 | if (auto GV = dyn_cast<GlobalObject>(V)) { | |||
| 703 | SmallVector<MDNode *, 2> Types; | |||
| 704 | GV->getMetadata(LLVMContext::MD_type, Types); | |||
| 705 | for (MDNode *Type : Types) { | |||
| 706 | if (Type->getOperand(1) != TypeId) | |||
| 707 | continue; | |||
| 708 | uint64_t Offset = | |||
| 709 | cast<ConstantInt>( | |||
| 710 | cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) | |||
| 711 | ->getZExtValue(); | |||
| 712 | if (COffset == Offset) | |||
| 713 | return true; | |||
| 714 | } | |||
| 715 | return false; | |||
| 716 | } | |||
| 717 | ||||
| 718 | if (auto GEP = dyn_cast<GEPOperator>(V)) { | |||
| 719 | APInt APOffset(DL.getPointerSizeInBits(0), 0); | |||
| 720 | bool Result = GEP->accumulateConstantOffset(DL, APOffset); | |||
| 721 | if (!Result) | |||
| 722 | return false; | |||
| 723 | COffset += APOffset.getZExtValue(); | |||
| 724 | return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset); | |||
| 725 | } | |||
| 726 | ||||
| 727 | if (auto Op = dyn_cast<Operator>(V)) { | |||
| 728 | if (Op->getOpcode() == Instruction::BitCast) | |||
| 729 | return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset); | |||
| 730 | ||||
| 731 | if (Op->getOpcode() == Instruction::Select) | |||
| 732 | return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) && | |||
| 733 | isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset); | |||
| 734 | } | |||
| 735 | ||||
| 736 | return false; | |||
| 737 | } | |||
| 738 | ||||
| 739 | /// Lower a llvm.type.test call to its implementation. Returns the value to | |||
| 740 | /// replace the call with. | |||
| 741 | Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI, | |||
| 742 | const TypeIdLowering &TIL) { | |||
| 743 | // Delay lowering if the resolution is currently unknown. | |||
| 744 | if (TIL.TheKind == TypeTestResolution::Unknown) | |||
| 745 | return nullptr; | |||
| 746 | if (TIL.TheKind == TypeTestResolution::Unsat) | |||
| 747 | return ConstantInt::getFalse(M.getContext()); | |||
| 748 | ||||
| 749 | Value *Ptr = CI->getArgOperand(0); | |||
| 750 | const DataLayout &DL = M.getDataLayout(); | |||
| 751 | if (isKnownTypeIdMember(TypeId, DL, Ptr, 0)) | |||
| 752 | return ConstantInt::getTrue(M.getContext()); | |||
| 753 | ||||
| 754 | BasicBlock *InitialBB = CI->getParent(); | |||
| 755 | ||||
| 756 | IRBuilder<> B(CI); | |||
| 757 | ||||
| 758 | Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); | |||
| 759 | ||||
| 760 | Constant *OffsetedGlobalAsInt = | |||
| 761 | ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy); | |||
| 762 | if (TIL.TheKind == TypeTestResolution::Single) | |||
| 763 | return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt); | |||
| 764 | ||||
| 765 | Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt); | |||
| 766 | ||||
| 767 | // We need to check that the offset both falls within our range and is | |||
| 768 | // suitably aligned. We can check both properties at the same time by | |||
| 769 | // performing a right rotate by log2(alignment) followed by an integer | |||
| 770 | // comparison against the bitset size. The rotate will move the lower | |||
| 771 | // order bits that need to be zero into the higher order bits of the | |||
| 772 | // result, causing the comparison to fail if they are nonzero. The rotate | |||
| 773 | // also conveniently gives us a bit offset to use during the load from | |||
| 774 | // the bitset. | |||
| 775 | Value *OffsetSHR = | |||
| 776 | B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy)); | |||
| 777 | Value *OffsetSHL = B.CreateShl( | |||
| 778 | PtrOffset, ConstantExpr::getZExt( | |||
| 779 | ConstantExpr::getSub( | |||
| 780 | ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)), | |||
| 781 | TIL.AlignLog2), | |||
| 782 | IntPtrTy)); | |||
| 783 | Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL); | |||
| 784 | ||||
| 785 | Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1); | |||
| 786 | ||||
| 787 | // If the bit set is all ones, testing against it is unnecessary. | |||
| 788 | if (TIL.TheKind == TypeTestResolution::AllOnes) | |||
| 789 | return OffsetInRange; | |||
| 790 | ||||
| 791 | // See if the intrinsic is used in the following common pattern: | |||
| 792 | // br(llvm.type.test(...), thenbb, elsebb) | |||
| 793 | // where nothing happens between the type test and the br. | |||
| 794 | // If so, create slightly simpler IR. | |||
| 795 | if (CI->hasOneUse()) | |||
| 796 | if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin())) | |||
| 797 | if (CI->getNextNode() == Br) { | |||
| 798 | BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator()); | |||
| 799 | BasicBlock *Else = Br->getSuccessor(1); | |||
| 800 | BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange); | |||
| 801 | NewBr->setMetadata(LLVMContext::MD_prof, | |||
| 802 | Br->getMetadata(LLVMContext::MD_prof)); | |||
| 803 | ReplaceInstWithInst(InitialBB->getTerminator(), NewBr); | |||
| 804 | ||||
| 805 | // Update phis in Else resulting from InitialBB being split | |||
| 806 | for (auto &Phi : Else->phis()) | |||
| 807 | Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB); | |||
| 808 | ||||
| 809 | IRBuilder<> ThenB(CI); | |||
| 810 | return createBitSetTest(ThenB, TIL, BitOffset); | |||
| 811 | } | |||
| 812 | ||||
| 813 | IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false)); | |||
| 814 | ||||
| 815 | // Now that we know that the offset is in range and aligned, load the | |||
| 816 | // appropriate bit from the bitset. | |||
| 817 | Value *Bit = createBitSetTest(ThenB, TIL, BitOffset); | |||
| 818 | ||||
| 819 | // The value we want is 0 if we came directly from the initial block | |||
| 820 | // (having failed the range or alignment checks), or the loaded bit if | |||
| 821 | // we came from the block in which we loaded it. | |||
| 822 | B.SetInsertPoint(CI); | |||
| 823 | PHINode *P = B.CreatePHI(Int1Ty, 2); | |||
| 824 | P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB); | |||
| 825 | P->addIncoming(Bit, ThenB.GetInsertBlock()); | |||
| 826 | return P; | |||
| 827 | } | |||
| 828 | ||||
| 829 | /// Given a disjoint set of type identifiers and globals, lay out the globals, | |||
| 830 | /// build the bit sets and lower the llvm.type.test calls. | |||
| 831 | void LowerTypeTestsModule::buildBitSetsFromGlobalVariables( | |||
| 832 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) { | |||
| 833 | // Build a new global with the combined contents of the referenced globals. | |||
| 834 | // This global is a struct whose even-indexed elements contain the original | |||
| 835 | // contents of the referenced globals and whose odd-indexed elements contain | |||
| 836 | // any padding required to align the next element to the next power of 2 plus | |||
| 837 | // any additional padding required to meet its alignment requirements. | |||
| 838 | std::vector<Constant *> GlobalInits; | |||
| 839 | const DataLayout &DL = M.getDataLayout(); | |||
| 840 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; | |||
| 841 | Align MaxAlign; | |||
| 842 | uint64_t CurOffset = 0; | |||
| 843 | uint64_t DesiredPadding = 0; | |||
| 844 | for (GlobalTypeMember *G : Globals) { | |||
| 845 | auto *GV = cast<GlobalVariable>(G->getGlobal()); | |||
| 846 | Align Alignment = | |||
| 847 | DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType()); | |||
| 848 | MaxAlign = std::max(MaxAlign, Alignment); | |||
| 849 | uint64_t GVOffset = alignTo(CurOffset + DesiredPadding, Alignment); | |||
| 850 | GlobalLayout[G] = GVOffset; | |||
| 851 | if (GVOffset != 0) { | |||
| 852 | uint64_t Padding = GVOffset - CurOffset; | |||
| 853 | GlobalInits.push_back( | |||
| 854 | ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding))); | |||
| 855 | } | |||
| 856 | ||||
| 857 | GlobalInits.push_back(GV->getInitializer()); | |||
| 858 | uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType()); | |||
| 859 | CurOffset = GVOffset + InitSize; | |||
| 860 | ||||
| 861 | // Compute the amount of padding that we'd like for the next element. | |||
| 862 | DesiredPadding = NextPowerOf2(InitSize - 1) - InitSize; | |||
| 863 | ||||
| 864 | // Experiments of different caps with Chromium on both x64 and ARM64 | |||
| 865 | // have shown that the 32-byte cap generates the smallest binary on | |||
| 866 | // both platforms while different caps yield similar performance. | |||
| 867 | // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html) | |||
| 868 | if (DesiredPadding > 32) | |||
| 869 | DesiredPadding = alignTo(InitSize, 32) - InitSize; | |||
| 870 | } | |||
| 871 | ||||
| 872 | Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits); | |||
| 873 | auto *CombinedGlobal = | |||
| 874 | new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true, | |||
| 875 | GlobalValue::PrivateLinkage, NewInit); | |||
| 876 | CombinedGlobal->setAlignment(MaxAlign); | |||
| 877 | ||||
| 878 | StructType *NewTy = cast<StructType>(NewInit->getType()); | |||
| 879 | lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout); | |||
| 880 | ||||
| 881 | // Build aliases pointing to offsets into the combined global for each | |||
| 882 | // global from which we built the combined global, and replace references | |||
| 883 | // to the original globals with references to the aliases. | |||
| 884 | for (unsigned I = 0; I != Globals.size(); ++I) { | |||
| 885 | GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal()); | |||
| 886 | ||||
| 887 | // Multiply by 2 to account for padding elements. | |||
| 888 | Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), | |||
| 889 | ConstantInt::get(Int32Ty, I * 2)}; | |||
| 890 | Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( | |||
| 891 | NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs); | |||
| 892 | assert(GV->getType()->getAddressSpace() == 0)((void)0); | |||
| 893 | GlobalAlias *GAlias = | |||
| 894 | GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(), | |||
| 895 | "", CombinedGlobalElemPtr, &M); | |||
| 896 | GAlias->setVisibility(GV->getVisibility()); | |||
| 897 | GAlias->takeName(GV); | |||
| 898 | GV->replaceAllUsesWith(GAlias); | |||
| 899 | GV->eraseFromParent(); | |||
| 900 | } | |||
| 901 | } | |||
| 902 | ||||
| 903 | bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() { | |||
| 904 | return (Arch == Triple::x86 || Arch == Triple::x86_64) && | |||
| 905 | ObjectFormat == Triple::ELF; | |||
| 906 | } | |||
| 907 | ||||
| 908 | /// Export the given type identifier so that ThinLTO backends may import it. | |||
| 909 | /// Type identifiers are exported by adding coarse-grained information about how | |||
| 910 | /// to test the type identifier to the summary, and creating symbols in the | |||
| 911 | /// object file (aliases and absolute symbols) containing fine-grained | |||
| 912 | /// information about the type identifier. | |||
| 913 | /// | |||
| 914 | /// Returns a pointer to the location in which to store the bitmask, if | |||
| 915 | /// applicable. | |||
| 916 | uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId, | |||
| 917 | const TypeIdLowering &TIL) { | |||
| 918 | TypeTestResolution &TTRes = | |||
| 919 | ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes; | |||
| 920 | TTRes.TheKind = TIL.TheKind; | |||
| 921 | ||||
| 922 | auto ExportGlobal = [&](StringRef Name, Constant *C) { | |||
| 923 | GlobalAlias *GA = | |||
| 924 | GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage, | |||
| 925 | "__typeid_" + TypeId + "_" + Name, C, &M); | |||
| 926 | GA->setVisibility(GlobalValue::HiddenVisibility); | |||
| 927 | }; | |||
| 928 | ||||
| 929 | auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) { | |||
| 930 | if (shouldExportConstantsAsAbsoluteSymbols()) | |||
| 931 | ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy)); | |||
| 932 | else | |||
| 933 | Storage = cast<ConstantInt>(C)->getZExtValue(); | |||
| 934 | }; | |||
| 935 | ||||
| 936 | if (TIL.TheKind != TypeTestResolution::Unsat) | |||
| 937 | ExportGlobal("global_addr", TIL.OffsetedGlobal); | |||
| 938 | ||||
| 939 | if (TIL.TheKind == TypeTestResolution::ByteArray || | |||
| 940 | TIL.TheKind == TypeTestResolution::Inline || | |||
| 941 | TIL.TheKind == TypeTestResolution::AllOnes) { | |||
| 942 | ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2); | |||
| 943 | ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1); | |||
| 944 | ||||
| 945 | uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1; | |||
| 946 | if (TIL.TheKind == TypeTestResolution::Inline) | |||
| 947 | TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6; | |||
| 948 | else | |||
| 949 | TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32; | |||
| 950 | } | |||
| 951 | ||||
| 952 | if (TIL.TheKind == TypeTestResolution::ByteArray) { | |||
| 953 | ExportGlobal("byte_array", TIL.TheByteArray); | |||
| 954 | if (shouldExportConstantsAsAbsoluteSymbols()) | |||
| 955 | ExportGlobal("bit_mask", TIL.BitMask); | |||
| 956 | else | |||
| 957 | return &TTRes.BitMask; | |||
| 958 | } | |||
| 959 | ||||
| 960 | if (TIL.TheKind == TypeTestResolution::Inline) | |||
| 961 | ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits); | |||
| 962 | ||||
| 963 | return nullptr; | |||
| 964 | } | |||
| 965 | ||||
| 966 | LowerTypeTestsModule::TypeIdLowering | |||
| 967 | LowerTypeTestsModule::importTypeId(StringRef TypeId) { | |||
| 968 | const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId); | |||
| 969 | if (!TidSummary) | |||
| 970 | return {}; // Unsat: no globals match this type id. | |||
| 971 | const TypeTestResolution &TTRes = TidSummary->TTRes; | |||
| 972 | ||||
| 973 | TypeIdLowering TIL; | |||
| 974 | TIL.TheKind = TTRes.TheKind; | |||
| 975 | ||||
| 976 | auto ImportGlobal = [&](StringRef Name) { | |||
| 977 | // Give the global a type of length 0 so that it is not assumed not to alias | |||
| 978 | // with any other global. | |||
| 979 | Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(), | |||
| 980 | Int8Arr0Ty); | |||
| 981 | if (auto *GV = dyn_cast<GlobalVariable>(C)) | |||
| 982 | GV->setVisibility(GlobalValue::HiddenVisibility); | |||
| 983 | C = ConstantExpr::getBitCast(C, Int8PtrTy); | |||
| 984 | return C; | |||
| 985 | }; | |||
| 986 | ||||
| 987 | auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth, | |||
| 988 | Type *Ty) { | |||
| 989 | if (!shouldExportConstantsAsAbsoluteSymbols()) { | |||
| 990 | Constant *C = | |||
| 991 | ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const); | |||
| 992 | if (!isa<IntegerType>(Ty)) | |||
| 993 | C = ConstantExpr::getIntToPtr(C, Ty); | |||
| 994 | return C; | |||
| 995 | } | |||
| 996 | ||||
| 997 | Constant *C = ImportGlobal(Name); | |||
| 998 | auto *GV = cast<GlobalVariable>(C->stripPointerCasts()); | |||
| 999 | if (isa<IntegerType>(Ty)) | |||
| 1000 | C = ConstantExpr::getPtrToInt(C, Ty); | |||
| 1001 | if (GV->getMetadata(LLVMContext::MD_absolute_symbol)) | |||
| 1002 | return C; | |||
| 1003 | ||||
| 1004 | auto SetAbsRange = [&](uint64_t Min, uint64_t Max) { | |||
| 1005 | auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min)); | |||
| 1006 | auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max)); | |||
| 1007 | GV->setMetadata(LLVMContext::MD_absolute_symbol, | |||
| 1008 | MDNode::get(M.getContext(), {MinC, MaxC})); | |||
| 1009 | }; | |||
| 1010 | if (AbsWidth == IntPtrTy->getBitWidth()) | |||
| 1011 | SetAbsRange(~0ull, ~0ull); // Full set. | |||
| 1012 | else | |||
| 1013 | SetAbsRange(0, 1ull << AbsWidth); | |||
| 1014 | return C; | |||
| 1015 | }; | |||
| 1016 | ||||
| 1017 | if (TIL.TheKind != TypeTestResolution::Unsat) | |||
| 1018 | TIL.OffsetedGlobal = ImportGlobal("global_addr"); | |||
| 1019 | ||||
| 1020 | if (TIL.TheKind == TypeTestResolution::ByteArray || | |||
| 1021 | TIL.TheKind == TypeTestResolution::Inline || | |||
| 1022 | TIL.TheKind == TypeTestResolution::AllOnes) { | |||
| 1023 | TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty); | |||
| 1024 | TIL.SizeM1 = | |||
| 1025 | ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy); | |||
| 1026 | } | |||
| 1027 | ||||
| 1028 | if (TIL.TheKind == TypeTestResolution::ByteArray) { | |||
| 1029 | TIL.TheByteArray = ImportGlobal("byte_array"); | |||
| 1030 | TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy); | |||
| 1031 | } | |||
| 1032 | ||||
| 1033 | if (TIL.TheKind == TypeTestResolution::Inline) | |||
| 1034 | TIL.InlineBits = ImportConstant( | |||
| 1035 | "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth, | |||
| 1036 | TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty); | |||
| 1037 | ||||
| 1038 | return TIL; | |||
| 1039 | } | |||
| 1040 | ||||
| 1041 | void LowerTypeTestsModule::importTypeTest(CallInst *CI) { | |||
| 1042 | auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); | |||
| 1043 | if (!TypeIdMDVal) | |||
| 1044 | report_fatal_error("Second argument of llvm.type.test must be metadata"); | |||
| 1045 | ||||
| 1046 | auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata()); | |||
| 1047 | // If this is a local unpromoted type, which doesn't have a metadata string, | |||
| 1048 | // treat as Unknown and delay lowering, so that we can still utilize it for | |||
| 1049 | // later optimizations. | |||
| 1050 | if (!TypeIdStr) | |||
| 1051 | return; | |||
| 1052 | ||||
| 1053 | TypeIdLowering TIL = importTypeId(TypeIdStr->getString()); | |||
| 1054 | Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL); | |||
| 1055 | if (Lowered) { | |||
| 1056 | CI->replaceAllUsesWith(Lowered); | |||
| 1057 | CI->eraseFromParent(); | |||
| 1058 | } | |||
| 1059 | } | |||
| 1060 | ||||
| 1061 | // ThinLTO backend: the function F has a jump table entry; update this module | |||
| 1062 | // accordingly. isJumpTableCanonical describes the type of the jump table entry. | |||
| 1063 | void LowerTypeTestsModule::importFunction( | |||
| 1064 | Function *F, bool isJumpTableCanonical, | |||
| 1065 | std::vector<GlobalAlias *> &AliasesToErase) { | |||
| 1066 | assert(F->getType()->getAddressSpace() == 0)((void)0); | |||
| 1067 | ||||
| 1068 | GlobalValue::VisibilityTypes Visibility = F->getVisibility(); | |||
| 1069 | std::string Name = std::string(F->getName()); | |||
| 1070 | ||||
| 1071 | if (F->isDeclarationForLinker() && isJumpTableCanonical) { | |||
| 1072 | // Non-dso_local functions may be overriden at run time, | |||
| 1073 | // don't short curcuit them | |||
| 1074 | if (F->isDSOLocal()) { | |||
| 1075 | Function *RealF = Function::Create(F->getFunctionType(), | |||
| 1076 | GlobalValue::ExternalLinkage, | |||
| 1077 | F->getAddressSpace(), | |||
| 1078 | Name + ".cfi", &M); | |||
| 1079 | RealF->setVisibility(GlobalVariable::HiddenVisibility); | |||
| 1080 | replaceDirectCalls(F, RealF); | |||
| 1081 | } | |||
| 1082 | return; | |||
| 1083 | } | |||
| 1084 | ||||
| 1085 | Function *FDecl; | |||
| 1086 | if (!isJumpTableCanonical) { | |||
| 1087 | // Either a declaration of an external function or a reference to a locally | |||
| 1088 | // defined jump table. | |||
| 1089 | FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, | |||
| 1090 | F->getAddressSpace(), Name + ".cfi_jt", &M); | |||
| 1091 | FDecl->setVisibility(GlobalValue::HiddenVisibility); | |||
| 1092 | } else { | |||
| 1093 | F->setName(Name + ".cfi"); | |||
| 1094 | F->setLinkage(GlobalValue::ExternalLinkage); | |||
| 1095 | FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, | |||
| 1096 | F->getAddressSpace(), Name, &M); | |||
| 1097 | FDecl->setVisibility(Visibility); | |||
| 1098 | Visibility = GlobalValue::HiddenVisibility; | |||
| 1099 | ||||
| 1100 | // Delete aliases pointing to this function, they'll be re-created in the | |||
| 1101 | // merged output. Don't do it yet though because ScopedSaveAliaseesAndUsed | |||
| 1102 | // will want to reset the aliasees first. | |||
| 1103 | for (auto &U : F->uses()) { | |||
| 1104 | if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) { | |||
| 1105 | Function *AliasDecl = Function::Create( | |||
| 1106 | F->getFunctionType(), GlobalValue::ExternalLinkage, | |||
| 1107 | F->getAddressSpace(), "", &M); | |||
| 1108 | AliasDecl->takeName(A); | |||
| 1109 | A->replaceAllUsesWith(AliasDecl); | |||
| 1110 | AliasesToErase.push_back(A); | |||
| 1111 | } | |||
| 1112 | } | |||
| 1113 | } | |||
| 1114 | ||||
| 1115 | if (F->hasExternalWeakLinkage()) | |||
| 1116 | replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isJumpTableCanonical); | |||
| 1117 | else | |||
| 1118 | replaceCfiUses(F, FDecl, isJumpTableCanonical); | |||
| 1119 | ||||
| 1120 | // Set visibility late because it's used in replaceCfiUses() to determine | |||
| 1121 | // whether uses need to to be replaced. | |||
| 1122 | F->setVisibility(Visibility); | |||
| 1123 | } | |||
| 1124 | ||||
| 1125 | void LowerTypeTestsModule::lowerTypeTestCalls( | |||
| 1126 | ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, | |||
| 1127 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { | |||
| 1128 | CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy); | |||
| 1129 | ||||
| 1130 | // For each type identifier in this disjoint set... | |||
| 1131 | for (Metadata *TypeId : TypeIds) { | |||
| 1132 | // Build the bitset. | |||
| 1133 | BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout); | |||
| 1134 | LLVM_DEBUG({do { } while (false) | |||
| 1135 | if (auto MDS = dyn_cast<MDString>(TypeId))do { } while (false) | |||
| 1136 | dbgs() << MDS->getString() << ": ";do { } while (false) | |||
| 1137 | elsedo { } while (false) | |||
| 1138 | dbgs() << "<unnamed>: ";do { } while (false) | |||
| 1139 | BSI.print(dbgs());do { } while (false) | |||
| 1140 | })do { } while (false); | |||
| 1141 | ||||
| 1142 | ByteArrayInfo *BAI = nullptr; | |||
| 1143 | TypeIdLowering TIL; | |||
| 1144 | TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr( | |||
| 1145 | Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)), | |||
| 1146 | TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2); | |||
| 1147 | TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1); | |||
| 1148 | if (BSI.isAllOnes()) { | |||
| 1149 | TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single | |||
| 1150 | : TypeTestResolution::AllOnes; | |||
| 1151 | } else if (BSI.BitSize <= 64) { | |||
| 1152 | TIL.TheKind = TypeTestResolution::Inline; | |||
| 1153 | uint64_t InlineBits = 0; | |||
| 1154 | for (auto Bit : BSI.Bits) | |||
| 1155 | InlineBits |= uint64_t(1) << Bit; | |||
| 1156 | if (InlineBits == 0) | |||
| 1157 | TIL.TheKind = TypeTestResolution::Unsat; | |||
| 1158 | else | |||
| 1159 | TIL.InlineBits = ConstantInt::get( | |||
| 1160 | (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits); | |||
| 1161 | } else { | |||
| 1162 | TIL.TheKind = TypeTestResolution::ByteArray; | |||
| 1163 | ++NumByteArraysCreated; | |||
| 1164 | BAI = createByteArray(BSI); | |||
| 1165 | TIL.TheByteArray = BAI->ByteArray; | |||
| 1166 | TIL.BitMask = BAI->MaskGlobal; | |||
| 1167 | } | |||
| 1168 | ||||
| 1169 | TypeIdUserInfo &TIUI = TypeIdUsers[TypeId]; | |||
| 1170 | ||||
| 1171 | if (TIUI.IsExported) { | |||
| 1172 | uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL); | |||
| 1173 | if (BAI) | |||
| 1174 | BAI->MaskPtr = MaskPtr; | |||
| 1175 | } | |||
| 1176 | ||||
| 1177 | // Lower each call to llvm.type.test for this type identifier. | |||
| 1178 | for (CallInst *CI : TIUI.CallSites) { | |||
| 1179 | ++NumTypeTestCallsLowered; | |||
| 1180 | Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL); | |||
| 1181 | if (Lowered) { | |||
| 1182 | CI->replaceAllUsesWith(Lowered); | |||
| 1183 | CI->eraseFromParent(); | |||
| 1184 | } | |||
| 1185 | } | |||
| 1186 | } | |||
| 1187 | } | |||
| 1188 | ||||
| 1189 | void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) { | |||
| 1190 | if (Type->getNumOperands() != 2) | |||
| 1191 | report_fatal_error("All operands of type metadata must have 2 elements"); | |||
| 1192 | ||||
| 1193 | if (GO->isThreadLocal()) | |||
| 1194 | report_fatal_error("Bit set element may not be thread-local"); | |||
| 1195 | if (isa<GlobalVariable>(GO) && GO->hasSection()) | |||
| 1196 | report_fatal_error( | |||
| 1197 | "A member of a type identifier may not have an explicit section"); | |||
| 1198 | ||||
| 1199 | // FIXME: We previously checked that global var member of a type identifier | |||
| 1200 | // must be a definition, but the IR linker may leave type metadata on | |||
| 1201 | // declarations. We should restore this check after fixing PR31759. | |||
| 1202 | ||||
| 1203 | auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0)); | |||
| 1204 | if (!OffsetConstMD) | |||
| 1205 | report_fatal_error("Type offset must be a constant"); | |||
| 1206 | auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue()); | |||
| 1207 | if (!OffsetInt) | |||
| 1208 | report_fatal_error("Type offset must be an integer constant"); | |||
| 1209 | } | |||
| 1210 | ||||
| 1211 | static const unsigned kX86JumpTableEntrySize = 8; | |||
| 1212 | static const unsigned kARMJumpTableEntrySize = 4; | |||
| 1213 | static const unsigned kARMBTIJumpTableEntrySize = 8; | |||
| 1214 | ||||
| 1215 | unsigned LowerTypeTestsModule::getJumpTableEntrySize() { | |||
| 1216 | switch (Arch) { | |||
| 1217 | case Triple::x86: | |||
| 1218 | case Triple::x86_64: | |||
| 1219 | return kX86JumpTableEntrySize; | |||
| 1220 | case Triple::arm: | |||
| 1221 | case Triple::thumb: | |||
| 1222 | return kARMJumpTableEntrySize; | |||
| 1223 | case Triple::aarch64: | |||
| 1224 | if (const auto *BTE = mdconst::extract_or_null<ConstantInt>( | |||
| 1225 | M.getModuleFlag("branch-target-enforcement"))) | |||
| 1226 | if (BTE->getZExtValue()) | |||
| 1227 | return kARMBTIJumpTableEntrySize; | |||
| 1228 | return kARMJumpTableEntrySize; | |||
| 1229 | default: | |||
| 1230 | report_fatal_error("Unsupported architecture for jump tables"); | |||
| 1231 | } | |||
| 1232 | } | |||
| 1233 | ||||
| 1234 | // Create a jump table entry for the target. This consists of an instruction | |||
| 1235 | // sequence containing a relative branch to Dest. Appends inline asm text, | |||
| 1236 | // constraints and arguments to AsmOS, ConstraintOS and AsmArgs. | |||
| 1237 | void LowerTypeTestsModule::createJumpTableEntry( | |||
| 1238 | raw_ostream &AsmOS, raw_ostream &ConstraintOS, | |||
| 1239 | Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs, | |||
| 1240 | Function *Dest) { | |||
| 1241 | unsigned ArgIndex = AsmArgs.size(); | |||
| 1242 | ||||
| 1243 | if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) { | |||
| 1244 | AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n"; | |||
| 1245 | AsmOS << "int3\nint3\nint3\n"; | |||
| 1246 | } else if (JumpTableArch == Triple::arm) { | |||
| 1247 | AsmOS << "b $" << ArgIndex << "\n"; | |||
| 1248 | } else if (JumpTableArch == Triple::aarch64) { | |||
| 1249 | if (const auto *BTE = mdconst::extract_or_null<ConstantInt>( | |||
| 1250 | Dest->getParent()->getModuleFlag("branch-target-enforcement"))) | |||
| 1251 | if (BTE->getZExtValue()) | |||
| 1252 | AsmOS << "bti c\n"; | |||
| 1253 | AsmOS << "b $" << ArgIndex << "\n"; | |||
| 1254 | } else if (JumpTableArch == Triple::thumb) { | |||
| 1255 | AsmOS << "b.w $" << ArgIndex << "\n"; | |||
| 1256 | } else { | |||
| 1257 | report_fatal_error("Unsupported architecture for jump tables"); | |||
| 1258 | } | |||
| 1259 | ||||
| 1260 | ConstraintOS << (ArgIndex > 0 ? ",s" : "s"); | |||
| 1261 | AsmArgs.push_back(Dest); | |||
| 1262 | } | |||
| 1263 | ||||
| 1264 | Type *LowerTypeTestsModule::getJumpTableEntryType() { | |||
| 1265 | return ArrayType::get(Int8Ty, getJumpTableEntrySize()); | |||
| 1266 | } | |||
| 1267 | ||||
| 1268 | /// Given a disjoint set of type identifiers and functions, build the bit sets | |||
| 1269 | /// and lower the llvm.type.test calls, architecture dependently. | |||
| 1270 | void LowerTypeTestsModule::buildBitSetsFromFunctions( | |||
| 1271 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { | |||
| 1272 | if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm || | |||
| 1273 | Arch == Triple::thumb || Arch == Triple::aarch64) | |||
| 1274 | buildBitSetsFromFunctionsNative(TypeIds, Functions); | |||
| 1275 | else if (Arch == Triple::wasm32 || Arch == Triple::wasm64) | |||
| 1276 | buildBitSetsFromFunctionsWASM(TypeIds, Functions); | |||
| 1277 | else | |||
| 1278 | report_fatal_error("Unsupported architecture for jump tables"); | |||
| 1279 | } | |||
| 1280 | ||||
| 1281 | void LowerTypeTestsModule::moveInitializerToModuleConstructor( | |||
| 1282 | GlobalVariable *GV) { | |||
| 1283 | if (WeakInitializerFn == nullptr) { | |||
| 1284 | WeakInitializerFn = Function::Create( | |||
| 1285 | FunctionType::get(Type::getVoidTy(M.getContext()), | |||
| 1286 | /* IsVarArg */ false), | |||
| 1287 | GlobalValue::InternalLinkage, | |||
| 1288 | M.getDataLayout().getProgramAddressSpace(), | |||
| 1289 | "__cfi_global_var_init", &M); | |||
| 1290 | BasicBlock *BB = | |||
| 1291 | BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn); | |||
| 1292 | ReturnInst::Create(M.getContext(), BB); | |||
| 1293 | WeakInitializerFn->setSection( | |||
| 1294 | ObjectFormat == Triple::MachO | |||
| 1295 | ? "__TEXT,__StaticInit,regular,pure_instructions" | |||
| 1296 | : ".text.startup"); | |||
| 1297 | // This code is equivalent to relocation application, and should run at the | |||
| 1298 | // earliest possible time (i.e. with the highest priority). | |||
| 1299 | appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0); | |||
| 1300 | } | |||
| 1301 | ||||
| 1302 | IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator()); | |||
| 1303 | GV->setConstant(false); | |||
| 1304 | IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlign()); | |||
| 1305 | GV->setInitializer(Constant::getNullValue(GV->getValueType())); | |||
| 1306 | } | |||
| 1307 | ||||
| 1308 | void LowerTypeTestsModule::findGlobalVariableUsersOf( | |||
| 1309 | Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) { | |||
| 1310 | for (auto *U : C->users()){ | |||
| 1311 | if (auto *GV = dyn_cast<GlobalVariable>(U)) | |||
| 1312 | Out.insert(GV); | |||
| 1313 | else if (auto *C2 = dyn_cast<Constant>(U)) | |||
| 1314 | findGlobalVariableUsersOf(C2, Out); | |||
| 1315 | } | |||
| 1316 | } | |||
| 1317 | ||||
| 1318 | // Replace all uses of F with (F ? JT : 0). | |||
| 1319 | void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr( | |||
| 1320 | Function *F, Constant *JT, bool IsJumpTableCanonical) { | |||
| 1321 | // The target expression can not appear in a constant initializer on most | |||
| 1322 | // (all?) targets. Switch to a runtime initializer. | |||
| 1323 | SmallSetVector<GlobalVariable *, 8> GlobalVarUsers; | |||
| 1324 | findGlobalVariableUsersOf(F, GlobalVarUsers); | |||
| 1325 | for (auto GV : GlobalVarUsers) | |||
| 1326 | moveInitializerToModuleConstructor(GV); | |||
| 1327 | ||||
| 1328 | // Can not RAUW F with an expression that uses F. Replace with a temporary | |||
| 1329 | // placeholder first. | |||
| 1330 | Function *PlaceholderFn = | |||
| 1331 | Function::Create(cast<FunctionType>(F->getValueType()), | |||
| 1332 | GlobalValue::ExternalWeakLinkage, | |||
| 1333 | F->getAddressSpace(), "", &M); | |||
| 1334 | replaceCfiUses(F, PlaceholderFn, IsJumpTableCanonical); | |||
| 1335 | ||||
| 1336 | Constant *Target = ConstantExpr::getSelect( | |||
| 1337 | ConstantExpr::getICmp(CmpInst::ICMP_NE, F, | |||
| 1338 | Constant::getNullValue(F->getType())), | |||
| 1339 | JT, Constant::getNullValue(F->getType())); | |||
| 1340 | PlaceholderFn->replaceAllUsesWith(Target); | |||
| 1341 | PlaceholderFn->eraseFromParent(); | |||
| 1342 | } | |||
| 1343 | ||||
| 1344 | static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) { | |||
| 1345 | Attribute TFAttr = F->getFnAttribute("target-features"); | |||
| 1346 | if (TFAttr.isValid()) { | |||
| 1347 | SmallVector<StringRef, 6> Features; | |||
| 1348 | TFAttr.getValueAsString().split(Features, ','); | |||
| 1349 | for (StringRef Feature : Features) { | |||
| 1350 | if (Feature == "-thumb-mode") | |||
| 1351 | return false; | |||
| 1352 | else if (Feature == "+thumb-mode") | |||
| 1353 | return true; | |||
| 1354 | } | |||
| 1355 | } | |||
| 1356 | ||||
| 1357 | return ModuleArch == Triple::thumb; | |||
| 1358 | } | |||
| 1359 | ||||
| 1360 | // Each jump table must be either ARM or Thumb as a whole for the bit-test math | |||
| 1361 | // to work. Pick one that matches the majority of members to minimize interop | |||
| 1362 | // veneers inserted by the linker. | |||
| 1363 | static Triple::ArchType | |||
| 1364 | selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions, | |||
| 1365 | Triple::ArchType ModuleArch) { | |||
| 1366 | if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb) | |||
| 1367 | return ModuleArch; | |||
| 1368 | ||||
| 1369 | unsigned ArmCount = 0, ThumbCount = 0; | |||
| 1370 | for (const auto GTM : Functions) { | |||
| 1371 | if (!GTM->isJumpTableCanonical()) { | |||
| 1372 | // PLT stubs are always ARM. | |||
| 1373 | // FIXME: This is the wrong heuristic for non-canonical jump tables. | |||
| 1374 | ++ArmCount; | |||
| 1375 | continue; | |||
| 1376 | } | |||
| 1377 | ||||
| 1378 | Function *F = cast<Function>(GTM->getGlobal()); | |||
| 1379 | ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount); | |||
| 1380 | } | |||
| 1381 | ||||
| 1382 | return ArmCount > ThumbCount ? Triple::arm : Triple::thumb; | |||
| 1383 | } | |||
| 1384 | ||||
| 1385 | void LowerTypeTestsModule::createJumpTable( | |||
| 1386 | Function *F, ArrayRef<GlobalTypeMember *> Functions) { | |||
| 1387 | std::string AsmStr, ConstraintStr; | |||
| 1388 | raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr); | |||
| 1389 | SmallVector<Value *, 16> AsmArgs; | |||
| 1390 | AsmArgs.reserve(Functions.size() * 2); | |||
| 1391 | ||||
| 1392 | Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch); | |||
| 1393 | ||||
| 1394 | for (unsigned I = 0; I != Functions.size(); ++I) | |||
| 1395 | createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs, | |||
| 1396 | cast<Function>(Functions[I]->getGlobal())); | |||
| 1397 | ||||
| 1398 | // Align the whole table by entry size. | |||
| 1399 | F->setAlignment(Align(getJumpTableEntrySize())); | |||
| 1400 | // Skip prologue. | |||
| 1401 | // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3. | |||
| 1402 | // Luckily, this function does not get any prologue even without the | |||
| 1403 | // attribute. | |||
| 1404 | if (OS != Triple::Win32) | |||
| 1405 | F->addFnAttr(Attribute::Naked); | |||
| 1406 | if (JumpTableArch == Triple::arm) | |||
| 1407 | F->addFnAttr("target-features", "-thumb-mode"); | |||
| 1408 | if (JumpTableArch == Triple::thumb) { | |||
| 1409 | F->addFnAttr("target-features", "+thumb-mode"); | |||
| 1410 | // Thumb jump table assembly needs Thumb2. The following attribute is added | |||
| 1411 | // by Clang for -march=armv7. | |||
| 1412 | F->addFnAttr("target-cpu", "cortex-a8"); | |||
| 1413 | } | |||
| 1414 | if (JumpTableArch == Triple::aarch64) { | |||
| 1415 | F->addFnAttr("branch-target-enforcement", "false"); | |||
| 1416 | F->addFnAttr("sign-return-address", "none"); | |||
| 1417 | } | |||
| 1418 | // Make sure we don't emit .eh_frame for this function. | |||
| 1419 | F->addFnAttr(Attribute::NoUnwind); | |||
| 1420 | ||||
| 1421 | BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F); | |||
| 1422 | IRBuilder<> IRB(BB); | |||
| 1423 | ||||
| 1424 | SmallVector<Type *, 16> ArgTypes; | |||
| 1425 | ArgTypes.reserve(AsmArgs.size()); | |||
| 1426 | for (const auto &Arg : AsmArgs) | |||
| 1427 | ArgTypes.push_back(Arg->getType()); | |||
| 1428 | InlineAsm *JumpTableAsm = | |||
| 1429 | InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false), | |||
| 1430 | AsmOS.str(), ConstraintOS.str(), | |||
| 1431 | /*hasSideEffects=*/true); | |||
| 1432 | ||||
| 1433 | IRB.CreateCall(JumpTableAsm, AsmArgs); | |||
| 1434 | IRB.CreateUnreachable(); | |||
| 1435 | } | |||
| 1436 | ||||
| 1437 | /// Given a disjoint set of type identifiers and functions, build a jump table | |||
| 1438 | /// for the functions, build the bit sets and lower the llvm.type.test calls. | |||
| 1439 | void LowerTypeTestsModule::buildBitSetsFromFunctionsNative( | |||
| 1440 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { | |||
| 1441 | // Unlike the global bitset builder, the function bitset builder cannot | |||
| 1442 | // re-arrange functions in a particular order and base its calculations on the | |||
| 1443 | // layout of the functions' entry points, as we have no idea how large a | |||
| 1444 | // particular function will end up being (the size could even depend on what | |||
| 1445 | // this pass does!) Instead, we build a jump table, which is a block of code | |||
| 1446 | // consisting of one branch instruction for each of the functions in the bit | |||
| 1447 | // set that branches to the target function, and redirect any taken function | |||
| 1448 | // addresses to the corresponding jump table entry. In the object file's | |||
| 1449 | // symbol table, the symbols for the target functions also refer to the jump | |||
| 1450 | // table entries, so that addresses taken outside the module will pass any | |||
| 1451 | // verification done inside the module. | |||
| 1452 | // | |||
| 1453 | // In more concrete terms, suppose we have three functions f, g, h which are | |||
| 1454 | // of the same type, and a function foo that returns their addresses: | |||
| 1455 | // | |||
| 1456 | // f: | |||
| 1457 | // mov 0, %eax | |||
| 1458 | // ret | |||
| 1459 | // | |||
| 1460 | // g: | |||
| 1461 | // mov 1, %eax | |||
| 1462 | // ret | |||
| 1463 | // | |||
| 1464 | // h: | |||
| 1465 | // mov 2, %eax | |||
| 1466 | // ret | |||
| 1467 | // | |||
| 1468 | // foo: | |||
| 1469 | // mov f, %eax | |||
| 1470 | // mov g, %edx | |||
| 1471 | // mov h, %ecx | |||
| 1472 | // ret | |||
| 1473 | // | |||
| 1474 | // We output the jump table as module-level inline asm string. The end result | |||
| 1475 | // will (conceptually) look like this: | |||
| 1476 | // | |||
| 1477 | // f = .cfi.jumptable | |||
| 1478 | // g = .cfi.jumptable + 4 | |||
| 1479 | // h = .cfi.jumptable + 8 | |||
| 1480 | // .cfi.jumptable: | |||
| 1481 | // jmp f.cfi ; 5 bytes | |||
| 1482 | // int3 ; 1 byte | |||
| 1483 | // int3 ; 1 byte | |||
| 1484 | // int3 ; 1 byte | |||
| 1485 | // jmp g.cfi ; 5 bytes | |||
| 1486 | // int3 ; 1 byte | |||
| 1487 | // int3 ; 1 byte | |||
| 1488 | // int3 ; 1 byte | |||
| 1489 | // jmp h.cfi ; 5 bytes | |||
| 1490 | // int3 ; 1 byte | |||
| 1491 | // int3 ; 1 byte | |||
| 1492 | // int3 ; 1 byte | |||
| 1493 | // | |||
| 1494 | // f.cfi: | |||
| 1495 | // mov 0, %eax | |||
| 1496 | // ret | |||
| 1497 | // | |||
| 1498 | // g.cfi: | |||
| 1499 | // mov 1, %eax | |||
| 1500 | // ret | |||
| 1501 | // | |||
| 1502 | // h.cfi: | |||
| 1503 | // mov 2, %eax | |||
| 1504 | // ret | |||
| 1505 | // | |||
| 1506 | // foo: | |||
| 1507 | // mov f, %eax | |||
| 1508 | // mov g, %edx | |||
| 1509 | // mov h, %ecx | |||
| 1510 | // ret | |||
| 1511 | // | |||
| 1512 | // Because the addresses of f, g, h are evenly spaced at a power of 2, in the | |||
| 1513 | // normal case the check can be carried out using the same kind of simple | |||
| 1514 | // arithmetic that we normally use for globals. | |||
| 1515 | ||||
| 1516 | // FIXME: find a better way to represent the jumptable in the IR. | |||
| 1517 | assert(!Functions.empty())((void)0); | |||
| 1518 | ||||
| 1519 | // Build a simple layout based on the regular layout of jump tables. | |||
| 1520 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; | |||
| 1521 | unsigned EntrySize = getJumpTableEntrySize(); | |||
| 1522 | for (unsigned I = 0; I != Functions.size(); ++I) | |||
| 1523 | GlobalLayout[Functions[I]] = I * EntrySize; | |||
| 1524 | ||||
| 1525 | Function *JumpTableFn = | |||
| 1526 | Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()), | |||
| 1527 | /* IsVarArg */ false), | |||
| 1528 | GlobalValue::PrivateLinkage, | |||
| 1529 | M.getDataLayout().getProgramAddressSpace(), | |||
| 1530 | ".cfi.jumptable", &M); | |||
| 1531 | ArrayType *JumpTableType = | |||
| 1532 | ArrayType::get(getJumpTableEntryType(), Functions.size()); | |||
| 1533 | auto JumpTable = | |||
| 1534 | ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0)); | |||
| 1535 | ||||
| 1536 | lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout); | |||
| 1537 | ||||
| 1538 | { | |||
| 1539 | ScopedSaveAliaseesAndUsed S(M); | |||
| 1540 | ||||
| 1541 | // Build aliases pointing to offsets into the jump table, and replace | |||
| 1542 | // references to the original functions with references to the aliases. | |||
| 1543 | for (unsigned I = 0; I != Functions.size(); ++I) { | |||
| 1544 | Function *F = cast<Function>(Functions[I]->getGlobal()); | |||
| 1545 | bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical(); | |||
| 1546 | ||||
| 1547 | Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast( | |||
| 1548 | ConstantExpr::getInBoundsGetElementPtr( | |||
| 1549 | JumpTableType, JumpTable, | |||
| 1550 | ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0), | |||
| 1551 | ConstantInt::get(IntPtrTy, I)}), | |||
| 1552 | F->getType()); | |||
| 1553 | if (Functions[I]->isExported()) { | |||
| 1554 | if (IsJumpTableCanonical) { | |||
| 1555 | ExportSummary->cfiFunctionDefs().insert(std::string(F->getName())); | |||
| ||||
| 1556 | } else { | |||
| 1557 | GlobalAlias *JtAlias = GlobalAlias::create( | |||
| 1558 | F->getValueType(), 0, GlobalValue::ExternalLinkage, | |||
| 1559 | F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M); | |||
| 1560 | JtAlias->setVisibility(GlobalValue::HiddenVisibility); | |||
| 1561 | ExportSummary->cfiFunctionDecls().insert(std::string(F->getName())); | |||
| 1562 | } | |||
| 1563 | } | |||
| 1564 | if (!IsJumpTableCanonical) { | |||
| 1565 | if (F->hasExternalWeakLinkage()) | |||
| 1566 | replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr, | |||
| 1567 | IsJumpTableCanonical); | |||
| 1568 | else | |||
| 1569 | replaceCfiUses(F, CombinedGlobalElemPtr, IsJumpTableCanonical); | |||
| 1570 | } else { | |||
| 1571 | assert(F->getType()->getAddressSpace() == 0)((void)0); | |||
| 1572 | ||||
| 1573 | GlobalAlias *FAlias = | |||
| 1574 | GlobalAlias::create(F->getValueType(), 0, F->getLinkage(), "", | |||
| 1575 | CombinedGlobalElemPtr, &M); | |||
| 1576 | FAlias->setVisibility(F->getVisibility()); | |||
| 1577 | FAlias->takeName(F); | |||
| 1578 | if (FAlias->hasName()) | |||
| 1579 | F->setName(FAlias->getName() + ".cfi"); | |||
| 1580 | replaceCfiUses(F, FAlias, IsJumpTableCanonical); | |||
| 1581 | if (!F->hasLocalLinkage()) | |||
| 1582 | F->setVisibility(GlobalVariable::HiddenVisibility); | |||
| 1583 | } | |||
| 1584 | } | |||
| 1585 | } | |||
| 1586 | ||||
| 1587 | createJumpTable(JumpTableFn, Functions); | |||
| 1588 | } | |||
| 1589 | ||||
| 1590 | /// Assign a dummy layout using an incrementing counter, tag each function | |||
| 1591 | /// with its index represented as metadata, and lower each type test to an | |||
| 1592 | /// integer range comparison. During generation of the indirect function call | |||
| 1593 | /// table in the backend, it will assign the given indexes. | |||
| 1594 | /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet | |||
| 1595 | /// been finalized. | |||
| 1596 | void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM( | |||
| 1597 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { | |||
| 1598 | assert(!Functions.empty())((void)0); | |||
| 1599 | ||||
| 1600 | // Build consecutive monotonic integer ranges for each call target set | |||
| 1601 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; | |||
| 1602 | ||||
| 1603 | for (GlobalTypeMember *GTM : Functions) { | |||
| 1604 | Function *F = cast<Function>(GTM->getGlobal()); | |||
| 1605 | ||||
| 1606 | // Skip functions that are not address taken, to avoid bloating the table | |||
| 1607 | if (!F->hasAddressTaken()) | |||
| 1608 | continue; | |||
| 1609 | ||||
| 1610 | // Store metadata with the index for each function | |||
| 1611 | MDNode *MD = MDNode::get(F->getContext(), | |||
| 1612 | ArrayRef<Metadata *>(ConstantAsMetadata::get( | |||
| 1613 | ConstantInt::get(Int64Ty, IndirectIndex)))); | |||
| 1614 | F->setMetadata("wasm.index", MD); | |||
| 1615 | ||||
| 1616 | // Assign the counter value | |||
| 1617 | GlobalLayout[GTM] = IndirectIndex++; | |||
| 1618 | } | |||
| 1619 | ||||
| 1620 | // The indirect function table index space starts at zero, so pass a NULL | |||
| 1621 | // pointer as the subtracted "jump table" offset. | |||
| 1622 | lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy), | |||
| 1623 | GlobalLayout); | |||
| 1624 | } | |||
| 1625 | ||||
| 1626 | void LowerTypeTestsModule::buildBitSetsFromDisjointSet( | |||
| 1627 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals, | |||
| 1628 | ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) { | |||
| 1629 | DenseMap<Metadata *, uint64_t> TypeIdIndices; | |||
| 1630 | for (unsigned I = 0; I != TypeIds.size(); ++I) | |||
| 1631 | TypeIdIndices[TypeIds[I]] = I; | |||
| 1632 | ||||
| 1633 | // For each type identifier, build a set of indices that refer to members of | |||
| 1634 | // the type identifier. | |||
| 1635 | std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size()); | |||
| 1636 | unsigned GlobalIndex = 0; | |||
| 1637 | DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices; | |||
| 1638 | for (GlobalTypeMember *GTM : Globals) { | |||
| 1639 | for (MDNode *Type : GTM->types()) { | |||
| 1640 | // Type = { offset, type identifier } | |||
| 1641 | auto I = TypeIdIndices.find(Type->getOperand(1)); | |||
| 1642 | if (I != TypeIdIndices.end()) | |||
| 1643 | TypeMembers[I->second].insert(GlobalIndex); | |||
| 1644 | } | |||
| 1645 | GlobalIndices[GTM] = GlobalIndex; | |||
| 1646 | GlobalIndex++; | |||
| 1647 | } | |||
| 1648 | ||||
| 1649 | for (ICallBranchFunnel *JT : ICallBranchFunnels) { | |||
| 1650 | TypeMembers.emplace_back(); | |||
| 1651 | std::set<uint64_t> &TMSet = TypeMembers.back(); | |||
| 1652 | for (GlobalTypeMember *T : JT->targets()) | |||
| 1653 | TMSet.insert(GlobalIndices[T]); | |||
| 1654 | } | |||
| 1655 | ||||
| 1656 | // Order the sets of indices by size. The GlobalLayoutBuilder works best | |||
| 1657 | // when given small index sets first. | |||
| 1658 | llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1, | |||
| 1659 | const std::set<uint64_t> &O2) { | |||
| 1660 | return O1.size() < O2.size(); | |||
| 1661 | }); | |||
| 1662 | ||||
| 1663 | // Create a GlobalLayoutBuilder and provide it with index sets as layout | |||
| 1664 | // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as | |||
| 1665 | // close together as possible. | |||
| 1666 | GlobalLayoutBuilder GLB(Globals.size()); | |||
| 1667 | for (auto &&MemSet : TypeMembers) | |||
| 1668 | GLB.addFragment(MemSet); | |||
| 1669 | ||||
| 1670 | // Build a vector of globals with the computed layout. | |||
| 1671 | bool IsGlobalSet = | |||
| 1672 | Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal()); | |||
| 1673 | std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size()); | |||
| 1674 | auto OGTMI = OrderedGTMs.begin(); | |||
| 1675 | for (auto &&F : GLB.Fragments) { | |||
| 1676 | for (auto &&Offset : F) { | |||
| 1677 | if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal())) | |||
| 1678 | report_fatal_error("Type identifier may not contain both global " | |||
| 1679 | "variables and functions"); | |||
| 1680 | *OGTMI++ = Globals[Offset]; | |||
| 1681 | } | |||
| 1682 | } | |||
| 1683 | ||||
| 1684 | // Build the bitsets from this disjoint set. | |||
| 1685 | if (IsGlobalSet
| |||
| 1686 | buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs); | |||
| 1687 | else | |||
| 1688 | buildBitSetsFromFunctions(TypeIds, OrderedGTMs); | |||
| 1689 | } | |||
| 1690 | ||||
| 1691 | /// Lower all type tests in this module. | |||
| 1692 | LowerTypeTestsModule::LowerTypeTestsModule( | |||
| 1693 | Module &M, ModuleSummaryIndex *ExportSummary, | |||
| 1694 | const ModuleSummaryIndex *ImportSummary, bool DropTypeTests) | |||
| 1695 | : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary), | |||
| 1696 | DropTypeTests(DropTypeTests || ClDropTypeTests) { | |||
| 1697 | assert(!(ExportSummary && ImportSummary))((void)0); | |||
| 1698 | Triple TargetTriple(M.getTargetTriple()); | |||
| 1699 | Arch = TargetTriple.getArch(); | |||
| 1700 | OS = TargetTriple.getOS(); | |||
| 1701 | ObjectFormat = TargetTriple.getObjectFormat(); | |||
| 1702 | } | |||
| 1703 | ||||
| 1704 | bool LowerTypeTestsModule::runForTesting(Module &M) { | |||
| 1705 | ModuleSummaryIndex Summary(/*HaveGVs=*/false); | |||
| 1706 | ||||
| 1707 | // Handle the command-line summary arguments. This code is for testing | |||
| 1708 | // purposes only, so we handle errors directly. | |||
| 1709 | if (!ClReadSummary.empty()) { | |||
| 1710 | ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary + | |||
| 1711 | ": "); | |||
| 1712 | auto ReadSummaryFile = | |||
| 1713 | ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary))); | |||
| 1714 | ||||
| 1715 | yaml::Input In(ReadSummaryFile->getBuffer()); | |||
| 1716 | In >> Summary; | |||
| 1717 | ExitOnErr(errorCodeToError(In.error())); | |||
| 1718 | } | |||
| 1719 | ||||
| 1720 | bool Changed = | |||
| 1721 | LowerTypeTestsModule( | |||
| 1722 | M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr, | |||
| 1723 | ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr, | |||
| 1724 | /*DropTypeTests*/ false) | |||
| 1725 | .lower(); | |||
| 1726 | ||||
| 1727 | if (!ClWriteSummary.empty()) { | |||
| 1728 | ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary + | |||
| 1729 | ": "); | |||
| 1730 | std::error_code EC; | |||
| 1731 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF); | |||
| 1732 | ExitOnErr(errorCodeToError(EC)); | |||
| 1733 | ||||
| 1734 | yaml::Output Out(OS); | |||
| 1735 | Out << Summary; | |||
| 1736 | } | |||
| 1737 | ||||
| 1738 | return Changed; | |||
| 1739 | } | |||
| 1740 | ||||
| 1741 | static bool isDirectCall(Use& U) { | |||
| 1742 | auto *Usr = dyn_cast<CallInst>(U.getUser()); | |||
| 1743 | if (Usr) { | |||
| 1744 | auto *CB = dyn_cast<CallBase>(Usr); | |||
| 1745 | if (CB && CB->isCallee(&U)) | |||
| 1746 | return true; | |||
| 1747 | } | |||
| 1748 | return false; | |||
| 1749 | } | |||
| 1750 | ||||
| 1751 | void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New, | |||
| 1752 | bool IsJumpTableCanonical) { | |||
| 1753 | SmallSetVector<Constant *, 4> Constants; | |||
| 1754 | auto UI = Old->use_begin(), E = Old->use_end(); | |||
| 1755 | for (; UI != E;) { | |||
| 1756 | Use &U = *UI; | |||
| 1757 | ++UI; | |||
| 1758 | ||||
| 1759 | // Skip block addresses | |||
| 1760 | if (isa<BlockAddress>(U.getUser())) | |||
| 1761 | continue; | |||
| 1762 | ||||
| 1763 | // Skip direct calls to externally defined or non-dso_local functions | |||
| 1764 | if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical)) | |||
| 1765 | continue; | |||
| 1766 | ||||
| 1767 | // Must handle Constants specially, we cannot call replaceUsesOfWith on a | |||
| 1768 | // constant because they are uniqued. | |||
| 1769 | if (auto *C = dyn_cast<Constant>(U.getUser())) { | |||
| 1770 | if (!isa<GlobalValue>(C)) { | |||
| 1771 | // Save unique users to avoid processing operand replacement | |||
| 1772 | // more than once. | |||
| 1773 | Constants.insert(C); | |||
| 1774 | continue; | |||
| 1775 | } | |||
| 1776 | } | |||
| 1777 | ||||
| 1778 | U.set(New); | |||
| 1779 | } | |||
| 1780 | ||||
| 1781 | // Process operand replacement of saved constants. | |||
| 1782 | for (auto *C : Constants) | |||
| 1783 | C->handleOperandChange(Old, New); | |||
| 1784 | } | |||
| 1785 | ||||
| 1786 | void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) { | |||
| 1787 | Old->replaceUsesWithIf(New, [](Use &U) { return isDirectCall(U); }); | |||
| 1788 | } | |||
| 1789 | ||||
| 1790 | bool LowerTypeTestsModule::lower() { | |||
| 1791 | Function *TypeTestFunc = | |||
| 1792 | M.getFunction(Intrinsic::getName(Intrinsic::type_test)); | |||
| 1793 | ||||
| 1794 | if (DropTypeTests && TypeTestFunc) { | |||
| ||||
| 1795 | for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end(); | |||
| 1796 | UI != UE;) { | |||
| 1797 | auto *CI = cast<CallInst>((*UI++).getUser()); | |||
| 1798 | // Find and erase llvm.assume intrinsics for this llvm.type.test call. | |||
| 1799 | for (auto CIU = CI->use_begin(), CIUE = CI->use_end(); CIU != CIUE;) | |||
| 1800 | if (auto *Assume = dyn_cast<AssumeInst>((*CIU++).getUser())) | |||
| 1801 | Assume->eraseFromParent(); | |||
| 1802 | // If the assume was merged with another assume, we might have a use on a | |||
| 1803 | // phi (which will feed the assume). Simply replace the use on the phi | |||
| 1804 | // with "true" and leave the merged assume. | |||
| 1805 | if (!CI->use_empty()) { | |||
| 1806 | assert(all_of(CI->users(),((void)0) | |||
| 1807 | [](User *U) -> bool { return isa<PHINode>(U); }))((void)0); | |||
| 1808 | CI->replaceAllUsesWith(ConstantInt::getTrue(M.getContext())); | |||
| 1809 | } | |||
| 1810 | CI->eraseFromParent(); | |||
| 1811 | } | |||
| 1812 | ||||
| 1813 | // We have deleted the type intrinsics, so we no longer have enough | |||
| 1814 | // information to reason about the liveness of virtual function pointers | |||
| 1815 | // in GlobalDCE. | |||
| 1816 | for (GlobalVariable &GV : M.globals()) | |||
| 1817 | GV.eraseMetadata(LLVMContext::MD_vcall_visibility); | |||
| 1818 | ||||
| 1819 | return true; | |||
| 1820 | } | |||
| 1821 | ||||
| 1822 | // If only some of the modules were split, we cannot correctly perform | |||
| 1823 | // this transformation. We already checked for the presense of type tests | |||
| 1824 | // with partially split modules during the thin link, and would have emitted | |||
| 1825 | // an error if any were found, so here we can simply return. | |||
| 1826 | if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) || | |||
| 1827 | (ImportSummary && ImportSummary->partiallySplitLTOUnits())) | |||
| 1828 | return false; | |||
| 1829 | ||||
| 1830 | Function *ICallBranchFunnelFunc = | |||
| 1831 | M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel)); | |||
| 1832 | if ((!TypeTestFunc || TypeTestFunc->use_empty()) && | |||
| 1833 | (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) && | |||
| 1834 | !ExportSummary && !ImportSummary) | |||
| 1835 | return false; | |||
| 1836 | ||||
| 1837 | if (ImportSummary
| |||
| 1838 | if (TypeTestFunc) { | |||
| 1839 | for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end(); | |||
| 1840 | UI != UE;) { | |||
| 1841 | auto *CI = cast<CallInst>((*UI++).getUser()); | |||
| 1842 | importTypeTest(CI); | |||
| 1843 | } | |||
| 1844 | } | |||
| 1845 | ||||
| 1846 | if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty()) | |||
| 1847 | report_fatal_error( | |||
| 1848 | "unexpected call to llvm.icall.branch.funnel during import phase"); | |||
| 1849 | ||||
| 1850 | SmallVector<Function *, 8> Defs; | |||
| 1851 | SmallVector<Function *, 8> Decls; | |||
| 1852 | for (auto &F : M) { | |||
| 1853 | // CFI functions are either external, or promoted. A local function may | |||
| 1854 | // have the same name, but it's not the one we are looking for. | |||
| 1855 | if (F.hasLocalLinkage()) | |||
| 1856 | continue; | |||
| 1857 | if (ImportSummary->cfiFunctionDefs().count(std::string(F.getName()))) | |||
| 1858 | Defs.push_back(&F); | |||
| 1859 | else if (ImportSummary->cfiFunctionDecls().count( | |||
| 1860 | std::string(F.getName()))) | |||
| 1861 | Decls.push_back(&F); | |||
| 1862 | } | |||
| 1863 | ||||
| 1864 | std::vector<GlobalAlias *> AliasesToErase; | |||
| 1865 | { | |||
| 1866 | ScopedSaveAliaseesAndUsed S(M); | |||
| 1867 | for (auto F : Defs) | |||
| 1868 | importFunction(F, /*isJumpTableCanonical*/ true, AliasesToErase); | |||
| 1869 | for (auto F : Decls) | |||
| 1870 | importFunction(F, /*isJumpTableCanonical*/ false, AliasesToErase); | |||
| 1871 | } | |||
| 1872 | for (GlobalAlias *GA : AliasesToErase) | |||
| 1873 | GA->eraseFromParent(); | |||
| 1874 | ||||
| 1875 | return true; | |||
| 1876 | } | |||
| 1877 | ||||
| 1878 | // Equivalence class set containing type identifiers and the globals that | |||
| 1879 | // reference them. This is used to partition the set of type identifiers in | |||
| 1880 | // the module into disjoint sets. | |||
| 1881 | using GlobalClassesTy = EquivalenceClasses< | |||
| 1882 | PointerUnion<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>; | |||
| 1883 | GlobalClassesTy GlobalClasses; | |||
| 1884 | ||||
| 1885 | // Verify the type metadata and build a few data structures to let us | |||
| 1886 | // efficiently enumerate the type identifiers associated with a global: | |||
| 1887 | // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector | |||
| 1888 | // of associated type metadata) and a mapping from type identifiers to their | |||
| 1889 | // list of GlobalTypeMembers and last observed index in the list of globals. | |||
| 1890 | // The indices will be used later to deterministically order the list of type | |||
| 1891 | // identifiers. | |||
| 1892 | BumpPtrAllocator Alloc; | |||
| 1893 | struct TIInfo { | |||
| 1894 | unsigned UniqueId; | |||
| 1895 | std::vector<GlobalTypeMember *> RefGlobals; | |||
| 1896 | }; | |||
| 1897 | DenseMap<Metadata *, TIInfo> TypeIdInfo; | |||
| 1898 | unsigned CurUniqueId = 0; | |||
| 1899 | SmallVector<MDNode *, 2> Types; | |||
| 1900 | ||||
| 1901 | // Cross-DSO CFI emits jumptable entries for exported functions as well as | |||
| 1902 | // address taken functions in case they are address taken in other modules. | |||
| 1903 | const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr; | |||
| 1904 | ||||
| 1905 | struct ExportedFunctionInfo { | |||
| 1906 | CfiFunctionLinkage Linkage; | |||
| 1907 | MDNode *FuncMD; // {name, linkage, type[, type...]} | |||
| 1908 | }; | |||
| 1909 | DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions; | |||
| 1910 | if (ExportSummary
| |||
| 1911 | // A set of all functions that are address taken by a live global object. | |||
| 1912 | DenseSet<GlobalValue::GUID> AddressTaken; | |||
| 1913 | for (auto &I : *ExportSummary) | |||
| 1914 | for (auto &GVS : I.second.SummaryList) | |||
| 1915 | if (GVS->isLive()) | |||
| 1916 | for (auto &Ref : GVS->refs()) | |||
| 1917 | AddressTaken.insert(Ref.getGUID()); | |||
| 1918 | ||||
| 1919 | NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions"); | |||
| 1920 | if (CfiFunctionsMD) { | |||
| 1921 | for (auto FuncMD : CfiFunctionsMD->operands()) { | |||
| 1922 | assert(FuncMD->getNumOperands() >= 2)((void)0); | |||
| 1923 | StringRef FunctionName = | |||
| 1924 | cast<MDString>(FuncMD->getOperand(0))->getString(); | |||
| 1925 | CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>( | |||
| 1926 | cast<ConstantAsMetadata>(FuncMD->getOperand(1)) | |||
| 1927 | ->getValue() | |||
| 1928 | ->getUniqueInteger() | |||
| 1929 | .getZExtValue()); | |||
| 1930 | const GlobalValue::GUID GUID = GlobalValue::getGUID( | |||
| 1931 | GlobalValue::dropLLVMManglingEscape(FunctionName)); | |||
| 1932 | // Do not emit jumptable entries for functions that are not-live and | |||
| 1933 | // have no live references (and are not exported with cross-DSO CFI.) | |||
| 1934 | if (!ExportSummary->isGUIDLive(GUID)) | |||
| 1935 | continue; | |||
| 1936 | if (!AddressTaken.count(GUID)) { | |||
| 1937 | if (!CrossDsoCfi || Linkage != CFL_Definition) | |||
| 1938 | continue; | |||
| 1939 | ||||
| 1940 | bool Exported = false; | |||
| 1941 | if (auto VI = ExportSummary->getValueInfo(GUID)) | |||
| 1942 | for (auto &GVS : VI.getSummaryList()) | |||
| 1943 | if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage())) | |||
| 1944 | Exported = true; | |||
| 1945 | ||||
| 1946 | if (!Exported) | |||
| 1947 | continue; | |||
| 1948 | } | |||
| 1949 | auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}}); | |||
| 1950 | if (!P.second && P.first->second.Linkage != CFL_Definition) | |||
| 1951 | P.first->second = {Linkage, FuncMD}; | |||
| 1952 | } | |||
| 1953 | ||||
| 1954 | for (const auto &P : ExportedFunctions) { | |||
| 1955 | StringRef FunctionName = P.first; | |||
| 1956 | CfiFunctionLinkage Linkage = P.second.Linkage; | |||
| 1957 | MDNode *FuncMD = P.second.FuncMD; | |||
| 1958 | Function *F = M.getFunction(FunctionName); | |||
| 1959 | if (F && F->hasLocalLinkage()) { | |||
| 1960 | // Locally defined function that happens to have the same name as a | |||
| 1961 | // function defined in a ThinLTO module. Rename it to move it out of | |||
| 1962 | // the way of the external reference that we're about to create. | |||
| 1963 | // Note that setName will find a unique name for the function, so even | |||
| 1964 | // if there is an existing function with the suffix there won't be a | |||
| 1965 | // name collision. | |||
| 1966 | F->setName(F->getName() + ".1"); | |||
| 1967 | F = nullptr; | |||
| 1968 | } | |||
| 1969 | ||||
| 1970 | if (!F) | |||
| 1971 | F = Function::Create( | |||
| 1972 | FunctionType::get(Type::getVoidTy(M.getContext()), false), | |||
| 1973 | GlobalVariable::ExternalLinkage, | |||
| 1974 | M.getDataLayout().getProgramAddressSpace(), FunctionName, &M); | |||
| 1975 | ||||
| 1976 | // If the function is available_externally, remove its definition so | |||
| 1977 | // that it is handled the same way as a declaration. Later we will try | |||
| 1978 | // to create an alias using this function's linkage, which will fail if | |||
| 1979 | // the linkage is available_externally. This will also result in us | |||
| 1980 | // following the code path below to replace the type metadata. | |||
| 1981 | if (F->hasAvailableExternallyLinkage()) { | |||
| 1982 | F->setLinkage(GlobalValue::ExternalLinkage); | |||
| 1983 | F->deleteBody(); | |||
| 1984 | F->setComdat(nullptr); | |||
| 1985 | F->clearMetadata(); | |||
| 1986 | } | |||
| 1987 | ||||
| 1988 | // Update the linkage for extern_weak declarations when a definition | |||
| 1989 | // exists. | |||
| 1990 | if (Linkage == CFL_Definition && F->hasExternalWeakLinkage()) | |||
| 1991 | F->setLinkage(GlobalValue::ExternalLinkage); | |||
| 1992 | ||||
| 1993 | // If the function in the full LTO module is a declaration, replace its | |||
| 1994 | // type metadata with the type metadata we found in cfi.functions. That | |||
| 1995 | // metadata is presumed to be more accurate than the metadata attached | |||
| 1996 | // to the declaration. | |||
| 1997 | if (F->isDeclaration()) { | |||
| 1998 | if (Linkage == CFL_WeakDeclaration) | |||
| 1999 | F->setLinkage(GlobalValue::ExternalWeakLinkage); | |||
| 2000 | ||||
| 2001 | F->eraseMetadata(LLVMContext::MD_type); | |||
| 2002 | for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I) | |||
| 2003 | F->addMetadata(LLVMContext::MD_type, | |||
| 2004 | *cast<MDNode>(FuncMD->getOperand(I).get())); | |||
| 2005 | } | |||
| 2006 | } | |||
| 2007 | } | |||
| 2008 | } | |||
| 2009 | ||||
| 2010 | DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers; | |||
| 2011 | for (GlobalObject &GO : M.global_objects()) { | |||
| 2012 | if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker()) | |||
| 2013 | continue; | |||
| 2014 | ||||
| 2015 | Types.clear(); | |||
| 2016 | GO.getMetadata(LLVMContext::MD_type, Types); | |||
| 2017 | ||||
| 2018 | bool IsJumpTableCanonical = false; | |||
| 2019 | bool IsExported = false; | |||
| 2020 | if (Function *F = dyn_cast<Function>(&GO)) { | |||
| 2021 | IsJumpTableCanonical = isJumpTableCanonical(F); | |||
| 2022 | if (ExportedFunctions.count(F->getName())) { | |||
| 2023 | IsJumpTableCanonical |= | |||
| 2024 | ExportedFunctions[F->getName()].Linkage == CFL_Definition; | |||
| 2025 | IsExported = true; | |||
| 2026 | // TODO: The logic here checks only that the function is address taken, | |||
| 2027 | // not that the address takers are live. This can be updated to check | |||
| 2028 | // their liveness and emit fewer jumptable entries once monolithic LTO | |||
| 2029 | // builds also emit summaries. | |||
| 2030 | } else if (!F->hasAddressTaken()) { | |||
| 2031 | if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage()) | |||
| 2032 | continue; | |||
| 2033 | } | |||
| 2034 | } | |||
| 2035 | ||||
| 2036 | auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical, | |||
| 2037 | IsExported, Types); | |||
| 2038 | GlobalTypeMembers[&GO] = GTM; | |||
| 2039 | for (MDNode *Type : Types) { | |||
| 2040 | verifyTypeMDNode(&GO, Type); | |||
| 2041 | auto &Info = TypeIdInfo[Type->getOperand(1)]; | |||
| 2042 | Info.UniqueId = ++CurUniqueId; | |||
| 2043 | Info.RefGlobals.push_back(GTM); | |||
| 2044 | } | |||
| 2045 | } | |||
| 2046 | ||||
| 2047 | auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & { | |||
| 2048 | // Add the call site to the list of call sites for this type identifier. We | |||
| 2049 | // also use TypeIdUsers to keep track of whether we have seen this type | |||
| 2050 | // identifier before. If we have, we don't need to re-add the referenced | |||
| 2051 | // globals to the equivalence class. | |||
| 2052 | auto Ins = TypeIdUsers.insert({TypeId, {}}); | |||
| 2053 | if (Ins.second) { | |||
| 2054 | // Add the type identifier to the equivalence class. | |||
| 2055 | GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId); | |||
| 2056 | GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); | |||
| 2057 | ||||
| 2058 | // Add the referenced globals to the type identifier's equivalence class. | |||
| 2059 | for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals) | |||
| 2060 | CurSet = GlobalClasses.unionSets( | |||
| 2061 | CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM))); | |||
| 2062 | } | |||
| 2063 | ||||
| 2064 | return Ins.first->second; | |||
| 2065 | }; | |||
| 2066 | ||||
| 2067 | if (TypeTestFunc
| |||
| 2068 | for (const Use &U : TypeTestFunc->uses()) { | |||
| 2069 | auto CI = cast<CallInst>(U.getUser()); | |||
| 2070 | // If this type test is only used by llvm.assume instructions, it | |||
| 2071 | // was used for whole program devirtualization, and is being kept | |||
| 2072 | // for use by other optimization passes. We do not need or want to | |||
| 2073 | // lower it here. We also don't want to rewrite any associated globals | |||
| 2074 | // unnecessarily. These will be removed by a subsequent LTT invocation | |||
| 2075 | // with the DropTypeTests flag set. | |||
| 2076 | bool OnlyAssumeUses = !CI->use_empty(); | |||
| 2077 | for (const Use &CIU : CI->uses()) { | |||
| 2078 | if (isa<AssumeInst>(CIU.getUser())) | |||
| 2079 | continue; | |||
| 2080 | OnlyAssumeUses = false; | |||
| 2081 | break; | |||
| 2082 | } | |||
| 2083 | if (OnlyAssumeUses) | |||
| 2084 | continue; | |||
| 2085 | ||||
| 2086 | auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); | |||
| 2087 | if (!TypeIdMDVal) | |||
| 2088 | report_fatal_error("Second argument of llvm.type.test must be metadata"); | |||
| 2089 | auto TypeId = TypeIdMDVal->getMetadata(); | |||
| 2090 | AddTypeIdUse(TypeId).CallSites.push_back(CI); | |||
| 2091 | } | |||
| 2092 | } | |||
| 2093 | ||||
| 2094 | if (ICallBranchFunnelFunc) { | |||
| 2095 | for (const Use &U : ICallBranchFunnelFunc->uses()) { | |||
| 2096 | if (Arch != Triple::x86_64) | |||
| 2097 | report_fatal_error( | |||
| 2098 | "llvm.icall.branch.funnel not supported on this target"); | |||
| 2099 | ||||
| 2100 | auto CI = cast<CallInst>(U.getUser()); | |||
| 2101 | ||||
| 2102 | std::vector<GlobalTypeMember *> Targets; | |||
| 2103 | if (CI->getNumArgOperands() % 2 != 1) | |||
| 2104 | report_fatal_error("number of arguments should be odd"); | |||
| 2105 | ||||
| 2106 | GlobalClassesTy::member_iterator CurSet; | |||
| 2107 | for (unsigned I = 1; I != CI->getNumArgOperands(); I += 2) { | |||
| 2108 | int64_t Offset; | |||
| 2109 | auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset( | |||
| 2110 | CI->getOperand(I), Offset, M.getDataLayout())); | |||
| 2111 | if (!Base) | |||
| 2112 | report_fatal_error( | |||
| 2113 | "Expected branch funnel operand to be global value"); | |||
| 2114 | ||||
| 2115 | GlobalTypeMember *GTM = GlobalTypeMembers[Base]; | |||
| 2116 | Targets.push_back(GTM); | |||
| 2117 | GlobalClassesTy::member_iterator NewSet = | |||
| 2118 | GlobalClasses.findLeader(GlobalClasses.insert(GTM)); | |||
| 2119 | if (I == 1) | |||
| 2120 | CurSet = NewSet; | |||
| 2121 | else | |||
| 2122 | CurSet = GlobalClasses.unionSets(CurSet, NewSet); | |||
| 2123 | } | |||
| 2124 | ||||
| 2125 | GlobalClasses.unionSets( | |||
| 2126 | CurSet, GlobalClasses.findLeader( | |||
| 2127 | GlobalClasses.insert(ICallBranchFunnel::create( | |||
| 2128 | Alloc, CI, Targets, ++CurUniqueId)))); | |||
| 2129 | } | |||
| 2130 | } | |||
| 2131 | ||||
| 2132 | if (ExportSummary
| |||
| 2133 | DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID; | |||
| 2134 | for (auto &P : TypeIdInfo) { | |||
| 2135 | if (auto *TypeId = dyn_cast<MDString>(P.first)) | |||
| 2136 | MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back( | |||
| 2137 | TypeId); | |||
| 2138 | } | |||
| 2139 | ||||
| 2140 | for (auto &P : *ExportSummary) { | |||
| 2141 | for (auto &S : P.second.SummaryList) { | |||
| 2142 | if (!ExportSummary->isGlobalValueLive(S.get())) | |||
| 2143 | continue; | |||
| 2144 | if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject())) | |||
| 2145 | for (GlobalValue::GUID G : FS->type_tests()) | |||
| 2146 | for (Metadata *MD : MetadataByGUID[G]) | |||
| 2147 | AddTypeIdUse(MD).IsExported = true; | |||
| 2148 | } | |||
| 2149 | } | |||
| 2150 | } | |||
| 2151 | ||||
| 2152 | if (GlobalClasses.empty()) | |||
| 2153 | return false; | |||
| 2154 | ||||
| 2155 | // Build a list of disjoint sets ordered by their maximum global index for | |||
| 2156 | // determinism. | |||
| 2157 | std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets; | |||
| 2158 | for (GlobalClassesTy::iterator I = GlobalClasses.begin(), | |||
| 2159 | E = GlobalClasses.end(); | |||
| 2160 | I != E; ++I) { | |||
| 2161 | if (!I->isLeader()) | |||
| 2162 | continue; | |||
| 2163 | ++NumTypeIdDisjointSets; | |||
| 2164 | ||||
| 2165 | unsigned MaxUniqueId = 0; | |||
| 2166 | for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); | |||
| 2167 | MI != GlobalClasses.member_end(); ++MI) { | |||
| 2168 | if (auto *MD = MI->dyn_cast<Metadata *>()) | |||
| 2169 | MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId); | |||
| 2170 | else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>()) | |||
| 2171 | MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId); | |||
| 2172 | } | |||
| 2173 | Sets.emplace_back(I, MaxUniqueId); | |||
| 2174 | } | |||
| 2175 | llvm::sort(Sets, | |||
| 2176 | [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1, | |||
| 2177 | const std::pair<GlobalClassesTy::iterator, unsigned> &S2) { | |||
| 2178 | return S1.second < S2.second; | |||
| 2179 | }); | |||
| 2180 | ||||
| 2181 | // For each disjoint set we found... | |||
| 2182 | for (const auto &S : Sets) { | |||
| 2183 | // Build the list of type identifiers in this disjoint set. | |||
| 2184 | std::vector<Metadata *> TypeIds; | |||
| 2185 | std::vector<GlobalTypeMember *> Globals; | |||
| 2186 | std::vector<ICallBranchFunnel *> ICallBranchFunnels; | |||
| 2187 | for (GlobalClassesTy::member_iterator MI = | |||
| 2188 | GlobalClasses.member_begin(S.first); | |||
| 2189 | MI != GlobalClasses.member_end(); ++MI) { | |||
| 2190 | if (MI->is<Metadata *>()) | |||
| 2191 | TypeIds.push_back(MI->get<Metadata *>()); | |||
| 2192 | else if (MI->is<GlobalTypeMember *>()) | |||
| 2193 | Globals.push_back(MI->get<GlobalTypeMember *>()); | |||
| 2194 | else | |||
| 2195 | ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>()); | |||
| 2196 | } | |||
| 2197 | ||||
| 2198 | // Order type identifiers by unique ID for determinism. This ordering is | |||
| 2199 | // stable as there is a one-to-one mapping between metadata and unique IDs. | |||
| 2200 | llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) { | |||
| 2201 | return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId; | |||
| 2202 | }); | |||
| 2203 | ||||
| 2204 | // Same for the branch funnels. | |||
| 2205 | llvm::sort(ICallBranchFunnels, | |||
| 2206 | [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) { | |||
| 2207 | return F1->UniqueId < F2->UniqueId; | |||
| 2208 | }); | |||
| 2209 | ||||
| 2210 | // Build bitsets for this disjoint set. | |||
| 2211 | buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels); | |||
| 2212 | } | |||
| 2213 | ||||
| 2214 | allocateByteArrays(); | |||
| 2215 | ||||
| 2216 | // Parse alias data to replace stand-in function declarations for aliases | |||
| 2217 | // with an alias to the intended target. | |||
| 2218 | if (ExportSummary) { | |||
| 2219 | if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) { | |||
| 2220 | for (auto AliasMD : AliasesMD->operands()) { | |||
| 2221 | assert(AliasMD->getNumOperands() >= 4)((void)0); | |||
| 2222 | StringRef AliasName = | |||
| 2223 | cast<MDString>(AliasMD->getOperand(0))->getString(); | |||
| 2224 | StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString(); | |||
| 2225 | ||||
| 2226 | if (!ExportedFunctions.count(Aliasee) || | |||
| 2227 | ExportedFunctions[Aliasee].Linkage != CFL_Definition || | |||
| 2228 | !M.getNamedAlias(Aliasee)) | |||
| 2229 | continue; | |||
| 2230 | ||||
| 2231 | GlobalValue::VisibilityTypes Visibility = | |||
| 2232 | static_cast<GlobalValue::VisibilityTypes>( | |||
| 2233 | cast<ConstantAsMetadata>(AliasMD->getOperand(2)) | |||
| 2234 | ->getValue() | |||
| 2235 | ->getUniqueInteger() | |||
| 2236 | .getZExtValue()); | |||
| 2237 | bool Weak = | |||
| 2238 | static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3)) | |||
| 2239 | ->getValue() | |||
| 2240 | ->getUniqueInteger() | |||
| 2241 | .getZExtValue()); | |||
| 2242 | ||||
| 2243 | auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee)); | |||
| 2244 | Alias->setVisibility(Visibility); | |||
| 2245 | if (Weak) | |||
| 2246 | Alias->setLinkage(GlobalValue::WeakAnyLinkage); | |||
| 2247 | ||||
| 2248 | if (auto *F = M.getFunction(AliasName)) { | |||
| 2249 | Alias->takeName(F); | |||
| 2250 | F->replaceAllUsesWith(Alias); | |||
| 2251 | F->eraseFromParent(); | |||
| 2252 | } else { | |||
| 2253 | Alias->setName(AliasName); | |||
| 2254 | } | |||
| 2255 | } | |||
| 2256 | } | |||
| 2257 | } | |||
| 2258 | ||||
| 2259 | // Emit .symver directives for exported functions, if they exist. | |||
| 2260 | if (ExportSummary) { | |||
| 2261 | if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) { | |||
| 2262 | for (auto Symver : SymversMD->operands()) { | |||
| 2263 | assert(Symver->getNumOperands() >= 2)((void)0); | |||
| 2264 | StringRef SymbolName = | |||
| 2265 | cast<MDString>(Symver->getOperand(0))->getString(); | |||
| 2266 | StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString(); | |||
| 2267 | ||||
| 2268 | if (!ExportedFunctions.count(SymbolName)) | |||
| 2269 | continue; | |||
| 2270 | ||||
| 2271 | M.appendModuleInlineAsm( | |||
| 2272 | (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str()); | |||
| 2273 | } | |||
| 2274 | } | |||
| 2275 | } | |||
| 2276 | ||||
| 2277 | return true; | |||
| 2278 | } | |||
| 2279 | ||||
| 2280 | PreservedAnalyses LowerTypeTestsPass::run(Module &M, | |||
| 2281 | ModuleAnalysisManager &AM) { | |||
| 2282 | bool Changed; | |||
| 2283 | if (UseCommandLine) | |||
| 2284 | Changed = LowerTypeTestsModule::runForTesting(M); | |||
| 2285 | else | |||
| 2286 | Changed = | |||
| 2287 | LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests) | |||
| 2288 | .lower(); | |||
| 2289 | if (!Changed) | |||
| 2290 | return PreservedAnalyses::all(); | |||
| 2291 | return PreservedAnalyses::none(); | |||
| 2292 | } |