1 //===- ThinLTOBitcodeWriter.cpp - Bitcode writing pass for ThinLTO --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
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/Object/ModuleSymbolTable.h"
22 #include "llvm/Pass.h"
23 #include "llvm/Support/ScopedPrinter.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/Transforms/IPO.h"
26 #include "llvm/Transforms/IPO/FunctionAttrs.h"
27 #include "llvm/Transforms/IPO/FunctionImport.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include "llvm/Transforms/Utils/ModuleUtils.h"
30 using namespace llvm;
31
32 namespace {
33
34 // Promote each local-linkage entity defined by ExportM and used by ImportM by
35 // changing visibility and appending the given ModuleId.
promoteInternals(Module & ExportM,Module & ImportM,StringRef ModuleId,SetVector<GlobalValue * > & PromoteExtra)36 void promoteInternals(Module &ExportM, Module &ImportM, StringRef ModuleId,
37 SetVector<GlobalValue *> &PromoteExtra) {
38 DenseMap<const Comdat *, Comdat *> RenamedComdats;
39 for (auto &ExportGV : ExportM.global_values()) {
40 if (!ExportGV.hasLocalLinkage())
41 continue;
42
43 auto Name = ExportGV.getName();
44 GlobalValue *ImportGV = nullptr;
45 if (!PromoteExtra.count(&ExportGV)) {
46 ImportGV = ImportM.getNamedValue(Name);
47 if (!ImportGV)
48 continue;
49 ImportGV->removeDeadConstantUsers();
50 if (ImportGV->use_empty()) {
51 ImportGV->eraseFromParent();
52 continue;
53 }
54 }
55
56 std::string NewName = (Name + ModuleId).str();
57
58 if (const auto *C = ExportGV.getComdat())
59 if (C->getName() == Name)
60 RenamedComdats.try_emplace(C, ExportM.getOrInsertComdat(NewName));
61
62 ExportGV.setName(NewName);
63 ExportGV.setLinkage(GlobalValue::ExternalLinkage);
64 ExportGV.setVisibility(GlobalValue::HiddenVisibility);
65
66 if (ImportGV) {
67 ImportGV->setName(NewName);
68 ImportGV->setVisibility(GlobalValue::HiddenVisibility);
69 }
70 }
71
72 if (!RenamedComdats.empty())
73 for (auto &GO : ExportM.global_objects())
74 if (auto *C = GO.getComdat()) {
75 auto Replacement = RenamedComdats.find(C);
76 if (Replacement != RenamedComdats.end())
77 GO.setComdat(Replacement->second);
78 }
79 }
80
81 // Promote all internal (i.e. distinct) type ids used by the module by replacing
82 // them with external type ids formed using the module id.
83 //
84 // Note that this needs to be done before we clone the module because each clone
85 // will receive its own set of distinct metadata nodes.
promoteTypeIds(Module & M,StringRef ModuleId)86 void promoteTypeIds(Module &M, StringRef ModuleId) {
87 DenseMap<Metadata *, Metadata *> LocalToGlobal;
88 auto ExternalizeTypeId = [&](CallInst *CI, unsigned ArgNo) {
89 Metadata *MD =
90 cast<MetadataAsValue>(CI->getArgOperand(ArgNo))->getMetadata();
91
92 if (isa<MDNode>(MD) && cast<MDNode>(MD)->isDistinct()) {
93 Metadata *&GlobalMD = LocalToGlobal[MD];
94 if (!GlobalMD) {
95 std::string NewName = (Twine(LocalToGlobal.size()) + ModuleId).str();
96 GlobalMD = MDString::get(M.getContext(), NewName);
97 }
98
99 CI->setArgOperand(ArgNo,
100 MetadataAsValue::get(M.getContext(), GlobalMD));
101 }
102 };
103
104 if (Function *TypeTestFunc =
105 M.getFunction(Intrinsic::getName(Intrinsic::type_test))) {
106 for (const Use &U : TypeTestFunc->uses()) {
107 auto CI = cast<CallInst>(U.getUser());
108 ExternalizeTypeId(CI, 1);
109 }
110 }
111
112 if (Function *TypeCheckedLoadFunc =
113 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load))) {
114 for (const Use &U : TypeCheckedLoadFunc->uses()) {
115 auto CI = cast<CallInst>(U.getUser());
116 ExternalizeTypeId(CI, 2);
117 }
118 }
119
120 for (GlobalObject &GO : M.global_objects()) {
121 SmallVector<MDNode *, 1> MDs;
122 GO.getMetadata(LLVMContext::MD_type, MDs);
123
124 GO.eraseMetadata(LLVMContext::MD_type);
125 for (auto MD : MDs) {
126 auto I = LocalToGlobal.find(MD->getOperand(1));
127 if (I == LocalToGlobal.end()) {
128 GO.addMetadata(LLVMContext::MD_type, *MD);
129 continue;
130 }
131 GO.addMetadata(
132 LLVMContext::MD_type,
133 *MDNode::get(M.getContext(), {MD->getOperand(0), I->second}));
134 }
135 }
136 }
137
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.
simplifyExternals(Module & M)140 void simplifyExternals(Module &M) {
141 FunctionType *EmptyFT =
142 FunctionType::get(Type::getVoidTy(M.getContext()), false);
143
144 for (auto I = M.begin(), E = M.end(); I != E;) {
145 Function &F = *I++;
146 if (F.isDeclaration() && F.use_empty()) {
147 F.eraseFromParent();
148 continue;
149 }
150
151 if (!F.isDeclaration() || F.getFunctionType() == EmptyFT ||
152 // Changing the type of an intrinsic may invalidate the IR.
153 F.getName().startswith("llvm."))
154 continue;
155
156 Function *NewF =
157 Function::Create(EmptyFT, GlobalValue::ExternalLinkage,
158 F.getAddressSpace(), "", &M);
159 NewF->setVisibility(F.getVisibility());
160 NewF->takeName(&F);
161 F.replaceAllUsesWith(ConstantExpr::getBitCast(NewF, F.getType()));
162 F.eraseFromParent();
163 }
164
165 for (auto I = M.global_begin(), E = M.global_end(); I != E;) {
166 GlobalVariable &GV = *I++;
167 if (GV.isDeclaration() && GV.use_empty()) {
168 GV.eraseFromParent();
169 continue;
170 }
171 }
172 }
173
174 static void
filterModule(Module * M,function_ref<bool (const GlobalValue *)> ShouldKeepDefinition)175 filterModule(Module *M,
176 function_ref<bool(const GlobalValue *)> ShouldKeepDefinition) {
177 std::vector<GlobalValue *> V;
178 for (GlobalValue &GV : M->global_values())
179 if (!ShouldKeepDefinition(&GV))
180 V.push_back(&GV);
181
182 for (GlobalValue *GV : V)
183 if (!convertToDeclaration(*GV))
184 GV->eraseFromParent();
185 }
186
forEachVirtualFunction(Constant * C,function_ref<void (Function *)> Fn)187 void forEachVirtualFunction(Constant *C, function_ref<void(Function *)> Fn) {
188 if (auto *F = dyn_cast<Function>(C))
189 return Fn(F);
190 if (isa<GlobalValue>(C))
191 return;
192 for (Value *Op : C->operands())
193 forEachVirtualFunction(cast<Constant>(Op), Fn);
194 }
195
196 // If it's possible to split M into regular and thin LTO parts, do so and write
197 // a multi-module bitcode file with the two parts to OS. Otherwise, write only a
198 // regular LTO bitcode file to OS.
splitAndWriteThinLTOBitcode(raw_ostream & OS,raw_ostream * ThinLinkOS,function_ref<AAResults & (Function &)> AARGetter,Module & M)199 void splitAndWriteThinLTOBitcode(
200 raw_ostream &OS, raw_ostream *ThinLinkOS,
201 function_ref<AAResults &(Function &)> AARGetter, Module &M) {
202 std::string ModuleId = getUniqueModuleId(&M);
203 if (ModuleId.empty()) {
204 // We couldn't generate a module ID for this module, write it out as a
205 // regular LTO module with an index for summary-based dead stripping.
206 ProfileSummaryInfo PSI(M);
207 M.addModuleFlag(Module::Error, "ThinLTO", uint32_t(0));
208 ModuleSummaryIndex Index = buildModuleSummaryIndex(M, nullptr, &PSI);
209 WriteBitcodeToFile(M, OS, /*ShouldPreserveUseListOrder=*/false, &Index);
210
211 if (ThinLinkOS)
212 // We don't have a ThinLTO part, but still write the module to the
213 // ThinLinkOS if requested so that the expected output file is produced.
214 WriteBitcodeToFile(M, *ThinLinkOS, /*ShouldPreserveUseListOrder=*/false,
215 &Index);
216
217 return;
218 }
219
220 promoteTypeIds(M, ModuleId);
221
222 // Returns whether a global has attached type metadata. Such globals may
223 // participate in CFI or whole-program devirtualization, so they need to
224 // appear in the merged module instead of the thin LTO module.
225 auto HasTypeMetadata = [](const GlobalObject *GO) {
226 return GO->hasMetadata(LLVMContext::MD_type);
227 };
228
229 // Collect the set of virtual functions that are eligible for virtual constant
230 // propagation. Each eligible function must not access memory, must return
231 // an integer of width <=64 bits, must take at least one argument, must not
232 // use its first argument (assumed to be "this") and all arguments other than
233 // the first one must be of <=64 bit integer type.
234 //
235 // Note that we test whether this copy of the function is readnone, rather
236 // than testing function attributes, which must hold for any copy of the
237 // function, even a less optimized version substituted at link time. This is
238 // sound because the virtual constant propagation optimizations effectively
239 // inline all implementations of the virtual function into each call site,
240 // rather than using function attributes to perform local optimization.
241 DenseSet<const Function *> EligibleVirtualFns;
242 // If any member of a comdat lives in MergedM, put all members of that
243 // comdat in MergedM to keep the comdat together.
244 DenseSet<const Comdat *> MergedMComdats;
245 for (GlobalVariable &GV : M.globals())
246 if (HasTypeMetadata(&GV)) {
247 if (const auto *C = GV.getComdat())
248 MergedMComdats.insert(C);
249 forEachVirtualFunction(GV.getInitializer(), [&](Function *F) {
250 auto *RT = dyn_cast<IntegerType>(F->getReturnType());
251 if (!RT || RT->getBitWidth() > 64 || F->arg_empty() ||
252 !F->arg_begin()->use_empty())
253 return;
254 for (auto &Arg : make_range(std::next(F->arg_begin()), F->arg_end())) {
255 auto *ArgT = dyn_cast<IntegerType>(Arg.getType());
256 if (!ArgT || ArgT->getBitWidth() > 64)
257 return;
258 }
259 if (!F->isDeclaration() &&
260 computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
261 EligibleVirtualFns.insert(F);
262 });
263 }
264
265 ValueToValueMapTy VMap;
266 std::unique_ptr<Module> MergedM(
267 CloneModule(M, VMap, [&](const GlobalValue *GV) -> bool {
268 if (const auto *C = GV->getComdat())
269 if (MergedMComdats.count(C))
270 return true;
271 if (auto *F = dyn_cast<Function>(GV))
272 return EligibleVirtualFns.count(F);
273 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
274 return HasTypeMetadata(GVar);
275 return false;
276 }));
277 StripDebugInfo(*MergedM);
278 MergedM->setModuleInlineAsm("");
279
280 for (Function &F : *MergedM)
281 if (!F.isDeclaration()) {
282 // Reset the linkage of all functions eligible for virtual constant
283 // propagation. The canonical definitions live in the thin LTO module so
284 // that they can be imported.
285 F.setLinkage(GlobalValue::AvailableExternallyLinkage);
286 F.setComdat(nullptr);
287 }
288
289 SetVector<GlobalValue *> CfiFunctions;
290 for (auto &F : M)
291 if ((!F.hasLocalLinkage() || F.hasAddressTaken()) && HasTypeMetadata(&F))
292 CfiFunctions.insert(&F);
293
294 // Remove all globals with type metadata, globals with comdats that live in
295 // MergedM, and aliases pointing to such globals from the thin LTO module.
296 filterModule(&M, [&](const GlobalValue *GV) {
297 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
298 if (HasTypeMetadata(GVar))
299 return false;
300 if (const auto *C = GV->getComdat())
301 if (MergedMComdats.count(C))
302 return false;
303 return true;
304 });
305
306 promoteInternals(*MergedM, M, ModuleId, CfiFunctions);
307 promoteInternals(M, *MergedM, ModuleId, CfiFunctions);
308
309 auto &Ctx = MergedM->getContext();
310 SmallVector<MDNode *, 8> CfiFunctionMDs;
311 for (auto V : CfiFunctions) {
312 Function &F = *cast<Function>(V);
313 SmallVector<MDNode *, 2> Types;
314 F.getMetadata(LLVMContext::MD_type, Types);
315
316 SmallVector<Metadata *, 4> Elts;
317 Elts.push_back(MDString::get(Ctx, F.getName()));
318 CfiFunctionLinkage Linkage;
319 if (!F.isDeclarationForLinker())
320 Linkage = CFL_Definition;
321 else if (F.isWeakForLinker())
322 Linkage = CFL_WeakDeclaration;
323 else
324 Linkage = CFL_Declaration;
325 Elts.push_back(ConstantAsMetadata::get(
326 llvm::ConstantInt::get(Type::getInt8Ty(Ctx), Linkage)));
327 for (auto Type : Types)
328 Elts.push_back(Type);
329 CfiFunctionMDs.push_back(MDTuple::get(Ctx, Elts));
330 }
331
332 if(!CfiFunctionMDs.empty()) {
333 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("cfi.functions");
334 for (auto MD : CfiFunctionMDs)
335 NMD->addOperand(MD);
336 }
337
338 SmallVector<MDNode *, 8> FunctionAliases;
339 for (auto &A : M.aliases()) {
340 if (!isa<Function>(A.getAliasee()))
341 continue;
342
343 auto *F = cast<Function>(A.getAliasee());
344
345 Metadata *Elts[] = {
346 MDString::get(Ctx, A.getName()),
347 MDString::get(Ctx, F->getName()),
348 ConstantAsMetadata::get(
349 ConstantInt::get(Type::getInt8Ty(Ctx), A.getVisibility())),
350 ConstantAsMetadata::get(
351 ConstantInt::get(Type::getInt8Ty(Ctx), A.isWeakForLinker())),
352 };
353
354 FunctionAliases.push_back(MDTuple::get(Ctx, Elts));
355 }
356
357 if (!FunctionAliases.empty()) {
358 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("aliases");
359 for (auto MD : FunctionAliases)
360 NMD->addOperand(MD);
361 }
362
363 SmallVector<MDNode *, 8> Symvers;
364 ModuleSymbolTable::CollectAsmSymvers(M, [&](StringRef Name, StringRef Alias) {
365 Function *F = M.getFunction(Name);
366 if (!F || F->use_empty())
367 return;
368
369 Symvers.push_back(MDTuple::get(
370 Ctx, {MDString::get(Ctx, Name), MDString::get(Ctx, Alias)}));
371 });
372
373 if (!Symvers.empty()) {
374 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("symvers");
375 for (auto MD : Symvers)
376 NMD->addOperand(MD);
377 }
378
379 simplifyExternals(*MergedM);
380
381 // FIXME: Try to re-use BSI and PFI from the original module here.
382 ProfileSummaryInfo PSI(M);
383 ModuleSummaryIndex Index = buildModuleSummaryIndex(M, nullptr, &PSI);
384
385 // Mark the merged module as requiring full LTO. We still want an index for
386 // it though, so that it can participate in summary-based dead stripping.
387 MergedM->addModuleFlag(Module::Error, "ThinLTO", uint32_t(0));
388 ModuleSummaryIndex MergedMIndex =
389 buildModuleSummaryIndex(*MergedM, nullptr, &PSI);
390
391 SmallVector<char, 0> Buffer;
392
393 BitcodeWriter W(Buffer);
394 // Save the module hash produced for the full bitcode, which will
395 // be used in the backends, and use that in the minimized bitcode
396 // produced for the full link.
397 ModuleHash ModHash = {{0}};
398 W.writeModule(M, /*ShouldPreserveUseListOrder=*/false, &Index,
399 /*GenerateHash=*/true, &ModHash);
400 W.writeModule(*MergedM, /*ShouldPreserveUseListOrder=*/false, &MergedMIndex);
401 W.writeSymtab();
402 W.writeStrtab();
403 OS << Buffer;
404
405 // If a minimized bitcode module was requested for the thin link, only
406 // the information that is needed by thin link will be written in the
407 // given OS (the merged module will be written as usual).
408 if (ThinLinkOS) {
409 Buffer.clear();
410 BitcodeWriter W2(Buffer);
411 StripDebugInfo(M);
412 W2.writeThinLinkBitcode(M, Index, ModHash);
413 W2.writeModule(*MergedM, /*ShouldPreserveUseListOrder=*/false,
414 &MergedMIndex);
415 W2.writeSymtab();
416 W2.writeStrtab();
417 *ThinLinkOS << Buffer;
418 }
419 }
420
421 // Returns whether this module needs to be split because splitting is
422 // enabled and it uses type metadata.
requiresSplit(Module & M)423 bool requiresSplit(Module &M) {
424 // First check if the LTO Unit splitting has been enabled.
425 bool EnableSplitLTOUnit = false;
426 if (auto *MD = mdconst::extract_or_null<ConstantInt>(
427 M.getModuleFlag("EnableSplitLTOUnit")))
428 EnableSplitLTOUnit = MD->getZExtValue();
429 if (!EnableSplitLTOUnit)
430 return false;
431
432 // Module only needs to be split if it contains type metadata.
433 for (auto &GO : M.global_objects()) {
434 if (GO.hasMetadata(LLVMContext::MD_type))
435 return true;
436 }
437
438 return false;
439 }
440
writeThinLTOBitcode(raw_ostream & OS,raw_ostream * ThinLinkOS,function_ref<AAResults & (Function &)> AARGetter,Module & M,const ModuleSummaryIndex * Index)441 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
442 function_ref<AAResults &(Function &)> AARGetter,
443 Module &M, const ModuleSummaryIndex *Index) {
444 // Split module if splitting is enabled and it contains any type metadata.
445 if (requiresSplit(M))
446 return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
447
448 // Otherwise we can just write it out as a regular module.
449
450 // Save the module hash produced for the full bitcode, which will
451 // be used in the backends, and use that in the minimized bitcode
452 // produced for the full link.
453 ModuleHash ModHash = {{0}};
454 WriteBitcodeToFile(M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
455 /*GenerateHash=*/true, &ModHash);
456 // If a minimized bitcode module was requested for the thin link, only
457 // the information that is needed by thin link will be written in the
458 // given OS.
459 if (ThinLinkOS && Index)
460 WriteThinLinkBitcodeToFile(M, *ThinLinkOS, *Index, ModHash);
461 }
462
463 class WriteThinLTOBitcode : public ModulePass {
464 raw_ostream &OS; // raw_ostream to print on
465 // The output stream on which to emit a minimized module for use
466 // just in the thin link, if requested.
467 raw_ostream *ThinLinkOS;
468
469 public:
470 static char ID; // Pass identification, replacement for typeid
WriteThinLTOBitcode()471 WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()), ThinLinkOS(nullptr) {
472 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
473 }
474
WriteThinLTOBitcode(raw_ostream & o,raw_ostream * ThinLinkOS)475 explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
476 : ModulePass(ID), OS(o), ThinLinkOS(ThinLinkOS) {
477 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
478 }
479
getPassName() const480 StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
481
runOnModule(Module & M)482 bool runOnModule(Module &M) override {
483 const ModuleSummaryIndex *Index =
484 &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
485 writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
486 return true;
487 }
getAnalysisUsage(AnalysisUsage & AU) const488 void getAnalysisUsage(AnalysisUsage &AU) const override {
489 AU.setPreservesAll();
490 AU.addRequired<AssumptionCacheTracker>();
491 AU.addRequired<ModuleSummaryIndexWrapperPass>();
492 AU.addRequired<TargetLibraryInfoWrapperPass>();
493 }
494 };
495 } // anonymous namespace
496
497 char WriteThinLTOBitcode::ID = 0;
498 INITIALIZE_PASS_BEGIN(WriteThinLTOBitcode, "write-thinlto-bitcode",
499 "Write ThinLTO Bitcode", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)500 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
501 INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass)
502 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
503 INITIALIZE_PASS_END(WriteThinLTOBitcode, "write-thinlto-bitcode",
504 "Write ThinLTO Bitcode", false, true)
505
506 ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str,
507 raw_ostream *ThinLinkOS) {
508 return new WriteThinLTOBitcode(Str, ThinLinkOS);
509 }
510
511 PreservedAnalyses
run(Module & M,ModuleAnalysisManager & AM)512 llvm::ThinLTOBitcodeWriterPass::run(Module &M, ModuleAnalysisManager &AM) {
513 FunctionAnalysisManager &FAM =
514 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
515 writeThinLTOBitcode(OS, ThinLinkOS,
516 [&FAM](Function &F) -> AAResults & {
517 return FAM.getResult<AAManager>(F);
518 },
519 M, &AM.getResult<ModuleSummaryIndexAnalysis>(M));
520 return PreservedAnalyses::all();
521 }
522