1 //===- ThinLTOBitcodeWriter.cpp - Bitcode writing pass for ThinLTO --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Transforms/IPO/ThinLTOBitcodeWriter.h"
11 #include "llvm/Analysis/BasicAliasAnalysis.h"
12 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
13 #include "llvm/Analysis/ProfileSummaryInfo.h"
14 #include "llvm/Analysis/TypeMetadataUtils.h"
15 #include "llvm/Bitcode/BitcodeWriter.h"
16 #include "llvm/IR/Constants.h"
17 #include "llvm/IR/DebugInfo.h"
18 #include "llvm/IR/Intrinsics.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/IR/PassManager.h"
21 #include "llvm/Pass.h"
22 #include "llvm/Support/ScopedPrinter.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Transforms/IPO.h"
25 #include "llvm/Transforms/IPO/FunctionAttrs.h"
26 #include "llvm/Transforms/Utils/Cloning.h"
27 #include "llvm/Transforms/Utils/ModuleUtils.h"
32 // Promote each local-linkage entity defined by ExportM and used by ImportM by
33 // changing visibility and appending the given ModuleId.
34 void promoteInternals(Module &ExportM, Module &ImportM, StringRef ModuleId,
35 SetVector<GlobalValue *> &PromoteExtra) {
36 DenseMap<const Comdat *, Comdat *> RenamedComdats;
37 for (auto &ExportGV : ExportM.global_values()) {
38 if (!ExportGV.hasLocalLinkage())
41 auto Name = ExportGV.getName();
42 GlobalValue *ImportGV = nullptr;
43 if (!PromoteExtra.count(&ExportGV)) {
44 ImportGV = ImportM.getNamedValue(Name);
47 ImportGV->removeDeadConstantUsers();
48 if (ImportGV->use_empty()) {
49 ImportGV->eraseFromParent();
54 std::string NewName = (Name + ModuleId).str();
56 if (const auto *C = ExportGV.getComdat())
57 if (C->getName() == Name)
58 RenamedComdats.try_emplace(C, ExportM.getOrInsertComdat(NewName));
60 ExportGV.setName(NewName);
61 ExportGV.setLinkage(GlobalValue::ExternalLinkage);
62 ExportGV.setVisibility(GlobalValue::HiddenVisibility);
65 ImportGV->setName(NewName);
66 ImportGV->setVisibility(GlobalValue::HiddenVisibility);
70 if (!RenamedComdats.empty())
71 for (auto &GO : ExportM.global_objects())
72 if (auto *C = GO.getComdat()) {
73 auto Replacement = RenamedComdats.find(C);
74 if (Replacement != RenamedComdats.end())
75 GO.setComdat(Replacement->second);
79 // Promote all internal (i.e. distinct) type ids used by the module by replacing
80 // them with external type ids formed using the module id.
82 // Note that this needs to be done before we clone the module because each clone
83 // will receive its own set of distinct metadata nodes.
84 void promoteTypeIds(Module &M, StringRef ModuleId) {
85 DenseMap<Metadata *, Metadata *> LocalToGlobal;
86 auto ExternalizeTypeId = [&](CallInst *CI, unsigned ArgNo) {
88 cast<MetadataAsValue>(CI->getArgOperand(ArgNo))->getMetadata();
90 if (isa<MDNode>(MD) && cast<MDNode>(MD)->isDistinct()) {
91 Metadata *&GlobalMD = LocalToGlobal[MD];
94 (to_string(LocalToGlobal.size()) + ModuleId).str();
95 GlobalMD = MDString::get(M.getContext(), NewName);
98 CI->setArgOperand(ArgNo,
99 MetadataAsValue::get(M.getContext(), GlobalMD));
103 if (Function *TypeTestFunc =
104 M.getFunction(Intrinsic::getName(Intrinsic::type_test))) {
105 for (const Use &U : TypeTestFunc->uses()) {
106 auto CI = cast<CallInst>(U.getUser());
107 ExternalizeTypeId(CI, 1);
111 if (Function *TypeCheckedLoadFunc =
112 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load))) {
113 for (const Use &U : TypeCheckedLoadFunc->uses()) {
114 auto CI = cast<CallInst>(U.getUser());
115 ExternalizeTypeId(CI, 2);
119 for (GlobalObject &GO : M.global_objects()) {
120 SmallVector<MDNode *, 1> MDs;
121 GO.getMetadata(LLVMContext::MD_type, MDs);
123 GO.eraseMetadata(LLVMContext::MD_type);
124 for (auto MD : MDs) {
125 auto I = LocalToGlobal.find(MD->getOperand(1));
126 if (I == LocalToGlobal.end()) {
127 GO.addMetadata(LLVMContext::MD_type, *MD);
131 LLVMContext::MD_type,
132 *MDNode::get(M.getContext(),
133 ArrayRef<Metadata *>{MD->getOperand(0), I->second}));
138 // Drop unused globals, and drop type information from function declarations.
139 // FIXME: If we made functions typeless then there would be no need to do this.
140 void simplifyExternals(Module &M) {
141 FunctionType *EmptyFT =
142 FunctionType::get(Type::getVoidTy(M.getContext()), false);
144 for (auto I = M.begin(), E = M.end(); I != E;) {
146 if (F.isDeclaration() && F.use_empty()) {
151 if (!F.isDeclaration() || F.getFunctionType() == EmptyFT ||
152 // Changing the type of an intrinsic may invalidate the IR.
153 F.getName().startswith("llvm."))
157 Function::Create(EmptyFT, GlobalValue::ExternalLinkage, "", &M);
158 NewF->setVisibility(F.getVisibility());
160 F.replaceAllUsesWith(ConstantExpr::getBitCast(NewF, F.getType()));
164 for (auto I = M.global_begin(), E = M.global_end(); I != E;) {
165 GlobalVariable &GV = *I++;
166 if (GV.isDeclaration() && GV.use_empty()) {
167 GV.eraseFromParent();
174 Module *M, function_ref<bool(const GlobalValue *)> ShouldKeepDefinition) {
175 for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end();
177 GlobalAlias *GA = &*I++;
178 if (ShouldKeepDefinition(GA))
182 if (GA->getValueType()->isFunctionTy())
183 GO = Function::Create(cast<FunctionType>(GA->getValueType()),
184 GlobalValue::ExternalLinkage, "", M);
186 GO = new GlobalVariable(
187 *M, GA->getValueType(), false, GlobalValue::ExternalLinkage,
188 nullptr, "", nullptr,
189 GA->getThreadLocalMode(), GA->getType()->getAddressSpace());
191 GA->replaceAllUsesWith(GO);
192 GA->eraseFromParent();
195 for (Function &F : *M) {
196 if (ShouldKeepDefinition(&F))
200 F.setComdat(nullptr);
204 for (GlobalVariable &GV : M->globals()) {
205 if (ShouldKeepDefinition(&GV))
208 GV.setInitializer(nullptr);
209 GV.setLinkage(GlobalValue::ExternalLinkage);
210 GV.setComdat(nullptr);
215 void forEachVirtualFunction(Constant *C, function_ref<void(Function *)> Fn) {
216 if (auto *F = dyn_cast<Function>(C))
218 if (isa<GlobalValue>(C))
220 for (Value *Op : C->operands())
221 forEachVirtualFunction(cast<Constant>(Op), Fn);
224 // If it's possible to split M into regular and thin LTO parts, do so and write
225 // a multi-module bitcode file with the two parts to OS. Otherwise, write only a
226 // regular LTO bitcode file to OS.
227 void splitAndWriteThinLTOBitcode(
228 raw_ostream &OS, raw_ostream *ThinLinkOS,
229 function_ref<AAResults &(Function &)> AARGetter, Module &M) {
230 std::string ModuleId = getUniqueModuleId(&M);
231 if (ModuleId.empty()) {
232 // We couldn't generate a module ID for this module, just write it out as a
233 // regular LTO module.
234 WriteBitcodeToFile(&M, OS);
236 // We don't have a ThinLTO part, but still write the module to the
237 // ThinLinkOS if requested so that the expected output file is produced.
238 WriteBitcodeToFile(&M, *ThinLinkOS);
242 promoteTypeIds(M, ModuleId);
244 // Returns whether a global has attached type metadata. Such globals may
245 // participate in CFI or whole-program devirtualization, so they need to
246 // appear in the merged module instead of the thin LTO module.
247 auto HasTypeMetadata = [&](const GlobalObject *GO) {
248 SmallVector<MDNode *, 1> MDs;
249 GO->getMetadata(LLVMContext::MD_type, MDs);
253 // Collect the set of virtual functions that are eligible for virtual constant
254 // propagation. Each eligible function must not access memory, must return
255 // an integer of width <=64 bits, must take at least one argument, must not
256 // use its first argument (assumed to be "this") and all arguments other than
257 // the first one must be of <=64 bit integer type.
259 // Note that we test whether this copy of the function is readnone, rather
260 // than testing function attributes, which must hold for any copy of the
261 // function, even a less optimized version substituted at link time. This is
262 // sound because the virtual constant propagation optimizations effectively
263 // inline all implementations of the virtual function into each call site,
264 // rather than using function attributes to perform local optimization.
265 std::set<const Function *> EligibleVirtualFns;
266 // If any member of a comdat lives in MergedM, put all members of that
267 // comdat in MergedM to keep the comdat together.
268 DenseSet<const Comdat *> MergedMComdats;
269 for (GlobalVariable &GV : M.globals())
270 if (HasTypeMetadata(&GV)) {
271 if (const auto *C = GV.getComdat())
272 MergedMComdats.insert(C);
273 forEachVirtualFunction(GV.getInitializer(), [&](Function *F) {
274 auto *RT = dyn_cast<IntegerType>(F->getReturnType());
275 if (!RT || RT->getBitWidth() > 64 || F->arg_empty() ||
276 !F->arg_begin()->use_empty())
278 for (auto &Arg : make_range(std::next(F->arg_begin()), F->arg_end())) {
279 auto *ArgT = dyn_cast<IntegerType>(Arg.getType());
280 if (!ArgT || ArgT->getBitWidth() > 64)
283 if (!F->isDeclaration() &&
284 computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
285 EligibleVirtualFns.insert(F);
289 ValueToValueMapTy VMap;
290 std::unique_ptr<Module> MergedM(
291 CloneModule(&M, VMap, [&](const GlobalValue *GV) -> bool {
292 if (const auto *C = GV->getComdat())
293 if (MergedMComdats.count(C))
295 if (auto *F = dyn_cast<Function>(GV))
296 return EligibleVirtualFns.count(F);
297 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
298 return HasTypeMetadata(GVar);
301 StripDebugInfo(*MergedM);
303 for (Function &F : *MergedM)
304 if (!F.isDeclaration()) {
305 // Reset the linkage of all functions eligible for virtual constant
306 // propagation. The canonical definitions live in the thin LTO module so
307 // that they can be imported.
308 F.setLinkage(GlobalValue::AvailableExternallyLinkage);
309 F.setComdat(nullptr);
312 SetVector<GlobalValue *> CfiFunctions;
314 if ((!F.hasLocalLinkage() || F.hasAddressTaken()) && HasTypeMetadata(&F))
315 CfiFunctions.insert(&F);
317 // Remove all globals with type metadata, globals with comdats that live in
318 // MergedM, and aliases pointing to such globals from the thin LTO module.
319 filterModule(&M, [&](const GlobalValue *GV) {
320 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
321 if (HasTypeMetadata(GVar))
323 if (const auto *C = GV->getComdat())
324 if (MergedMComdats.count(C))
329 promoteInternals(*MergedM, M, ModuleId, CfiFunctions);
330 promoteInternals(M, *MergedM, ModuleId, CfiFunctions);
332 SmallVector<MDNode *, 8> CfiFunctionMDs;
333 for (auto V : CfiFunctions) {
334 Function &F = *cast<Function>(V);
335 SmallVector<MDNode *, 2> Types;
336 F.getMetadata(LLVMContext::MD_type, Types);
338 auto &Ctx = MergedM->getContext();
339 SmallVector<Metadata *, 4> Elts;
340 Elts.push_back(MDString::get(Ctx, F.getName()));
341 CfiFunctionLinkage Linkage;
342 if (!F.isDeclarationForLinker())
343 Linkage = CFL_Definition;
344 else if (F.isWeakForLinker())
345 Linkage = CFL_WeakDeclaration;
347 Linkage = CFL_Declaration;
348 Elts.push_back(ConstantAsMetadata::get(
349 llvm::ConstantInt::get(Type::getInt8Ty(Ctx), Linkage)));
350 for (auto Type : Types)
351 Elts.push_back(Type);
352 CfiFunctionMDs.push_back(MDTuple::get(Ctx, Elts));
355 if(!CfiFunctionMDs.empty()) {
356 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("cfi.functions");
357 for (auto MD : CfiFunctionMDs)
361 simplifyExternals(*MergedM);
363 // FIXME: Try to re-use BSI and PFI from the original module here.
364 ProfileSummaryInfo PSI(M);
365 ModuleSummaryIndex Index = buildModuleSummaryIndex(M, nullptr, &PSI);
367 // Mark the merged module as requiring full LTO. We still want an index for
368 // it though, so that it can participate in summary-based dead stripping.
369 MergedM->addModuleFlag(Module::Error, "ThinLTO", uint32_t(0));
370 ModuleSummaryIndex MergedMIndex =
371 buildModuleSummaryIndex(*MergedM, nullptr, &PSI);
373 SmallVector<char, 0> Buffer;
375 BitcodeWriter W(Buffer);
376 // Save the module hash produced for the full bitcode, which will
377 // be used in the backends, and use that in the minimized bitcode
378 // produced for the full link.
379 ModuleHash ModHash = {{0}};
380 W.writeModule(&M, /*ShouldPreserveUseListOrder=*/false, &Index,
381 /*GenerateHash=*/true, &ModHash);
382 W.writeModule(MergedM.get(), /*ShouldPreserveUseListOrder=*/false,
388 // If a minimized bitcode module was requested for the thin link, only
389 // the information that is needed by thin link will be written in the
390 // given OS (the merged module will be written as usual).
393 BitcodeWriter W2(Buffer);
395 W2.writeThinLinkBitcode(&M, Index, ModHash);
396 W2.writeModule(MergedM.get(), /*ShouldPreserveUseListOrder=*/false,
400 *ThinLinkOS << Buffer;
404 // Returns whether this module needs to be split because it uses type metadata.
405 bool requiresSplit(Module &M) {
406 SmallVector<MDNode *, 1> MDs;
407 for (auto &GO : M.global_objects()) {
408 GO.getMetadata(LLVMContext::MD_type, MDs);
416 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
417 function_ref<AAResults &(Function &)> AARGetter,
418 Module &M, const ModuleSummaryIndex *Index) {
419 // See if this module has any type metadata. If so, we need to split it.
420 if (requiresSplit(M))
421 return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
423 // Otherwise we can just write it out as a regular module.
425 // Save the module hash produced for the full bitcode, which will
426 // be used in the backends, and use that in the minimized bitcode
427 // produced for the full link.
428 ModuleHash ModHash = {{0}};
429 WriteBitcodeToFile(&M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
430 /*GenerateHash=*/true, &ModHash);
431 // If a minimized bitcode module was requested for the thin link, only
432 // the information that is needed by thin link will be written in the
434 if (ThinLinkOS && Index)
435 WriteThinLinkBitcodeToFile(&M, *ThinLinkOS, *Index, ModHash);
438 class WriteThinLTOBitcode : public ModulePass {
439 raw_ostream &OS; // raw_ostream to print on
440 // The output stream on which to emit a minimized module for use
441 // just in the thin link, if requested.
442 raw_ostream *ThinLinkOS;
445 static char ID; // Pass identification, replacement for typeid
446 WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()), ThinLinkOS(nullptr) {
447 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
450 explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
451 : ModulePass(ID), OS(o), ThinLinkOS(ThinLinkOS) {
452 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
455 StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
457 bool runOnModule(Module &M) override {
458 const ModuleSummaryIndex *Index =
459 &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
460 writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
463 void getAnalysisUsage(AnalysisUsage &AU) const override {
464 AU.setPreservesAll();
465 AU.addRequired<AssumptionCacheTracker>();
466 AU.addRequired<ModuleSummaryIndexWrapperPass>();
467 AU.addRequired<TargetLibraryInfoWrapperPass>();
470 } // anonymous namespace
472 char WriteThinLTOBitcode::ID = 0;
473 INITIALIZE_PASS_BEGIN(WriteThinLTOBitcode, "write-thinlto-bitcode",
474 "Write ThinLTO Bitcode", false, true)
475 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
476 INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass)
477 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
478 INITIALIZE_PASS_END(WriteThinLTOBitcode, "write-thinlto-bitcode",
479 "Write ThinLTO Bitcode", false, true)
481 ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str,
482 raw_ostream *ThinLinkOS) {
483 return new WriteThinLTOBitcode(Str, ThinLinkOS);
487 llvm::ThinLTOBitcodeWriterPass::run(Module &M, ModuleAnalysisManager &AM) {
488 FunctionAnalysisManager &FAM =
489 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
490 writeThinLTOBitcode(OS, ThinLinkOS,
491 [&FAM](Function &F) -> AAResults & {
492 return FAM.getResult<AAManager>(F);
494 M, &AM.getResult<ModuleSummaryIndexAnalysis>(M));
495 return PreservedAnalyses::all();