[InstCombine] Signed saturation patterns
[llvm-core.git] / lib / Transforms / IPO / ThinLTOBitcodeWriter.cpp
blob690b5e8bf49ee688a547efafca563f1c151b79ba
1 //===- ThinLTOBitcodeWriter.cpp - Bitcode writing pass for ThinLTO --------===//
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 //===----------------------------------------------------------------------===//
9 #include "llvm/Transforms/IPO/ThinLTOBitcodeWriter.h"
10 #include "llvm/Analysis/BasicAliasAnalysis.h"
11 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
12 #include "llvm/Analysis/ProfileSummaryInfo.h"
13 #include "llvm/Analysis/TypeMetadataUtils.h"
14 #include "llvm/Bitcode/BitcodeWriter.h"
15 #include "llvm/IR/Constants.h"
16 #include "llvm/IR/DebugInfo.h"
17 #include "llvm/IR/Intrinsics.h"
18 #include "llvm/IR/Module.h"
19 #include "llvm/IR/PassManager.h"
20 #include "llvm/Object/ModuleSymbolTable.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/IPO/FunctionImport.h"
27 #include "llvm/Transforms/IPO/LowerTypeTests.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include "llvm/Transforms/Utils/ModuleUtils.h"
30 using namespace llvm;
32 namespace {
34 // Promote each local-linkage entity defined by ExportM and used by ImportM by
35 // changing visibility and appending the given ModuleId.
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;
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;
56 std::string NewName = (Name + ModuleId).str();
58 if (const auto *C = ExportGV.getComdat())
59 if (C->getName() == Name)
60 RenamedComdats.try_emplace(C, ExportM.getOrInsertComdat(NewName));
62 ExportGV.setName(NewName);
63 ExportGV.setLinkage(GlobalValue::ExternalLinkage);
64 ExportGV.setVisibility(GlobalValue::HiddenVisibility);
66 if (ImportGV) {
67 ImportGV->setName(NewName);
68 ImportGV->setVisibility(GlobalValue::HiddenVisibility);
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);
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.
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.
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();
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);
99 CI->setArgOperand(ArgNo,
100 MetadataAsValue::get(M.getContext(), GlobalMD));
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);
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);
120 for (GlobalObject &GO : M.global_objects()) {
121 SmallVector<MDNode *, 1> MDs;
122 GO.getMetadata(LLVMContext::MD_type, MDs);
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;
131 GO.addMetadata(
132 LLVMContext::MD_type,
133 *MDNode::get(M.getContext(), {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;) {
145 Function &F = *I++;
146 if (F.isDeclaration() && F.use_empty()) {
147 F.eraseFromParent();
148 continue;
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;
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();
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;
174 static void
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);
182 for (GlobalValue *GV : V)
183 if (!convertToDeclaration(*GV))
184 GV->eraseFromParent();
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);
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.
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);
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);
217 return;
220 promoteTypeIds(M, ModuleId);
222 // Returns whether a global or its associated global has attached type
223 // metadata. The former may participate in CFI or whole-program
224 // devirtualization, so they need to appear in the merged module instead of
225 // the thin LTO module. Similarly, globals that are associated with globals
226 // with type metadata need to appear in the merged module because they will
227 // reference the global's section directly.
228 auto HasTypeMetadata = [](const GlobalObject *GO) {
229 if (MDNode *MD = GO->getMetadata(LLVMContext::MD_associated))
230 if (auto *AssocVM = dyn_cast_or_null<ValueAsMetadata>(MD->getOperand(0)))
231 if (auto *AssocGO = dyn_cast<GlobalObject>(AssocVM->getValue()))
232 if (AssocGO->hasMetadata(LLVMContext::MD_type))
233 return true;
234 return GO->hasMetadata(LLVMContext::MD_type);
237 // Collect the set of virtual functions that are eligible for virtual constant
238 // propagation. Each eligible function must not access memory, must return
239 // an integer of width <=64 bits, must take at least one argument, must not
240 // use its first argument (assumed to be "this") and all arguments other than
241 // the first one must be of <=64 bit integer type.
243 // Note that we test whether this copy of the function is readnone, rather
244 // than testing function attributes, which must hold for any copy of the
245 // function, even a less optimized version substituted at link time. This is
246 // sound because the virtual constant propagation optimizations effectively
247 // inline all implementations of the virtual function into each call site,
248 // rather than using function attributes to perform local optimization.
249 DenseSet<const Function *> EligibleVirtualFns;
250 // If any member of a comdat lives in MergedM, put all members of that
251 // comdat in MergedM to keep the comdat together.
252 DenseSet<const Comdat *> MergedMComdats;
253 for (GlobalVariable &GV : M.globals())
254 if (HasTypeMetadata(&GV)) {
255 if (const auto *C = GV.getComdat())
256 MergedMComdats.insert(C);
257 forEachVirtualFunction(GV.getInitializer(), [&](Function *F) {
258 auto *RT = dyn_cast<IntegerType>(F->getReturnType());
259 if (!RT || RT->getBitWidth() > 64 || F->arg_empty() ||
260 !F->arg_begin()->use_empty())
261 return;
262 for (auto &Arg : make_range(std::next(F->arg_begin()), F->arg_end())) {
263 auto *ArgT = dyn_cast<IntegerType>(Arg.getType());
264 if (!ArgT || ArgT->getBitWidth() > 64)
265 return;
267 if (!F->isDeclaration() &&
268 computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
269 EligibleVirtualFns.insert(F);
273 ValueToValueMapTy VMap;
274 std::unique_ptr<Module> MergedM(
275 CloneModule(M, VMap, [&](const GlobalValue *GV) -> bool {
276 if (const auto *C = GV->getComdat())
277 if (MergedMComdats.count(C))
278 return true;
279 if (auto *F = dyn_cast<Function>(GV))
280 return EligibleVirtualFns.count(F);
281 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
282 return HasTypeMetadata(GVar);
283 return false;
284 }));
285 StripDebugInfo(*MergedM);
286 MergedM->setModuleInlineAsm("");
288 for (Function &F : *MergedM)
289 if (!F.isDeclaration()) {
290 // Reset the linkage of all functions eligible for virtual constant
291 // propagation. The canonical definitions live in the thin LTO module so
292 // that they can be imported.
293 F.setLinkage(GlobalValue::AvailableExternallyLinkage);
294 F.setComdat(nullptr);
297 SetVector<GlobalValue *> CfiFunctions;
298 for (auto &F : M)
299 if ((!F.hasLocalLinkage() || F.hasAddressTaken()) && HasTypeMetadata(&F))
300 CfiFunctions.insert(&F);
302 // Remove all globals with type metadata, globals with comdats that live in
303 // MergedM, and aliases pointing to such globals from the thin LTO module.
304 filterModule(&M, [&](const GlobalValue *GV) {
305 if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
306 if (HasTypeMetadata(GVar))
307 return false;
308 if (const auto *C = GV->getComdat())
309 if (MergedMComdats.count(C))
310 return false;
311 return true;
314 promoteInternals(*MergedM, M, ModuleId, CfiFunctions);
315 promoteInternals(M, *MergedM, ModuleId, CfiFunctions);
317 auto &Ctx = MergedM->getContext();
318 SmallVector<MDNode *, 8> CfiFunctionMDs;
319 for (auto V : CfiFunctions) {
320 Function &F = *cast<Function>(V);
321 SmallVector<MDNode *, 2> Types;
322 F.getMetadata(LLVMContext::MD_type, Types);
324 SmallVector<Metadata *, 4> Elts;
325 Elts.push_back(MDString::get(Ctx, F.getName()));
326 CfiFunctionLinkage Linkage;
327 if (lowertypetests::isJumpTableCanonical(&F))
328 Linkage = CFL_Definition;
329 else if (F.hasExternalWeakLinkage())
330 Linkage = CFL_WeakDeclaration;
331 else
332 Linkage = CFL_Declaration;
333 Elts.push_back(ConstantAsMetadata::get(
334 llvm::ConstantInt::get(Type::getInt8Ty(Ctx), Linkage)));
335 for (auto Type : Types)
336 Elts.push_back(Type);
337 CfiFunctionMDs.push_back(MDTuple::get(Ctx, Elts));
340 if(!CfiFunctionMDs.empty()) {
341 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("cfi.functions");
342 for (auto MD : CfiFunctionMDs)
343 NMD->addOperand(MD);
346 SmallVector<MDNode *, 8> FunctionAliases;
347 for (auto &A : M.aliases()) {
348 if (!isa<Function>(A.getAliasee()))
349 continue;
351 auto *F = cast<Function>(A.getAliasee());
353 Metadata *Elts[] = {
354 MDString::get(Ctx, A.getName()),
355 MDString::get(Ctx, F->getName()),
356 ConstantAsMetadata::get(
357 ConstantInt::get(Type::getInt8Ty(Ctx), A.getVisibility())),
358 ConstantAsMetadata::get(
359 ConstantInt::get(Type::getInt8Ty(Ctx), A.isWeakForLinker())),
362 FunctionAliases.push_back(MDTuple::get(Ctx, Elts));
365 if (!FunctionAliases.empty()) {
366 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("aliases");
367 for (auto MD : FunctionAliases)
368 NMD->addOperand(MD);
371 SmallVector<MDNode *, 8> Symvers;
372 ModuleSymbolTable::CollectAsmSymvers(M, [&](StringRef Name, StringRef Alias) {
373 Function *F = M.getFunction(Name);
374 if (!F || F->use_empty())
375 return;
377 Symvers.push_back(MDTuple::get(
378 Ctx, {MDString::get(Ctx, Name), MDString::get(Ctx, Alias)}));
381 if (!Symvers.empty()) {
382 NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("symvers");
383 for (auto MD : Symvers)
384 NMD->addOperand(MD);
387 simplifyExternals(*MergedM);
389 // FIXME: Try to re-use BSI and PFI from the original module here.
390 ProfileSummaryInfo PSI(M);
391 ModuleSummaryIndex Index = buildModuleSummaryIndex(M, nullptr, &PSI);
393 // Mark the merged module as requiring full LTO. We still want an index for
394 // it though, so that it can participate in summary-based dead stripping.
395 MergedM->addModuleFlag(Module::Error, "ThinLTO", uint32_t(0));
396 ModuleSummaryIndex MergedMIndex =
397 buildModuleSummaryIndex(*MergedM, nullptr, &PSI);
399 SmallVector<char, 0> Buffer;
401 BitcodeWriter W(Buffer);
402 // Save the module hash produced for the full bitcode, which will
403 // be used in the backends, and use that in the minimized bitcode
404 // produced for the full link.
405 ModuleHash ModHash = {{0}};
406 W.writeModule(M, /*ShouldPreserveUseListOrder=*/false, &Index,
407 /*GenerateHash=*/true, &ModHash);
408 W.writeModule(*MergedM, /*ShouldPreserveUseListOrder=*/false, &MergedMIndex);
409 W.writeSymtab();
410 W.writeStrtab();
411 OS << Buffer;
413 // If a minimized bitcode module was requested for the thin link, only
414 // the information that is needed by thin link will be written in the
415 // given OS (the merged module will be written as usual).
416 if (ThinLinkOS) {
417 Buffer.clear();
418 BitcodeWriter W2(Buffer);
419 StripDebugInfo(M);
420 W2.writeThinLinkBitcode(M, Index, ModHash);
421 W2.writeModule(*MergedM, /*ShouldPreserveUseListOrder=*/false,
422 &MergedMIndex);
423 W2.writeSymtab();
424 W2.writeStrtab();
425 *ThinLinkOS << Buffer;
429 // Check if the LTO Unit splitting has been enabled.
430 bool enableSplitLTOUnit(Module &M) {
431 bool EnableSplitLTOUnit = false;
432 if (auto *MD = mdconst::extract_or_null<ConstantInt>(
433 M.getModuleFlag("EnableSplitLTOUnit")))
434 EnableSplitLTOUnit = MD->getZExtValue();
435 return EnableSplitLTOUnit;
438 // Returns whether this module needs to be split because it uses type metadata.
439 bool hasTypeMetadata(Module &M) {
440 for (auto &GO : M.global_objects()) {
441 if (GO.hasMetadata(LLVMContext::MD_type))
442 return true;
444 return false;
447 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
448 function_ref<AAResults &(Function &)> AARGetter,
449 Module &M, const ModuleSummaryIndex *Index) {
450 std::unique_ptr<ModuleSummaryIndex> NewIndex = nullptr;
451 // See if this module has any type metadata. If so, we try to split it
452 // or at least promote type ids to enable WPD.
453 if (hasTypeMetadata(M)) {
454 if (enableSplitLTOUnit(M))
455 return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
456 // Promote type ids as needed for index-based WPD.
457 std::string ModuleId = getUniqueModuleId(&M);
458 if (!ModuleId.empty()) {
459 promoteTypeIds(M, ModuleId);
460 // Need to rebuild the index so that it contains type metadata
461 // for the newly promoted type ids.
462 // FIXME: Probably should not bother building the index at all
463 // in the caller of writeThinLTOBitcode (which does so via the
464 // ModuleSummaryIndexAnalysis pass), since we have to rebuild it
465 // anyway whenever there is type metadata (here or in
466 // splitAndWriteThinLTOBitcode). Just always build it once via the
467 // buildModuleSummaryIndex when Module(s) are ready.
468 ProfileSummaryInfo PSI(M);
469 NewIndex = std::make_unique<ModuleSummaryIndex>(
470 buildModuleSummaryIndex(M, nullptr, &PSI));
471 Index = NewIndex.get();
475 // Write it out as an unsplit ThinLTO module.
477 // Save the module hash produced for the full bitcode, which will
478 // be used in the backends, and use that in the minimized bitcode
479 // produced for the full link.
480 ModuleHash ModHash = {{0}};
481 WriteBitcodeToFile(M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
482 /*GenerateHash=*/true, &ModHash);
483 // If a minimized bitcode module was requested for the thin link, only
484 // the information that is needed by thin link will be written in the
485 // given OS.
486 if (ThinLinkOS && Index)
487 WriteThinLinkBitcodeToFile(M, *ThinLinkOS, *Index, ModHash);
490 class WriteThinLTOBitcode : public ModulePass {
491 raw_ostream &OS; // raw_ostream to print on
492 // The output stream on which to emit a minimized module for use
493 // just in the thin link, if requested.
494 raw_ostream *ThinLinkOS;
496 public:
497 static char ID; // Pass identification, replacement for typeid
498 WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()), ThinLinkOS(nullptr) {
499 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
502 explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
503 : ModulePass(ID), OS(o), ThinLinkOS(ThinLinkOS) {
504 initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
507 StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
509 bool runOnModule(Module &M) override {
510 const ModuleSummaryIndex *Index =
511 &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
512 writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
513 return true;
515 void getAnalysisUsage(AnalysisUsage &AU) const override {
516 AU.setPreservesAll();
517 AU.addRequired<AssumptionCacheTracker>();
518 AU.addRequired<ModuleSummaryIndexWrapperPass>();
519 AU.addRequired<TargetLibraryInfoWrapperPass>();
522 } // anonymous namespace
524 char WriteThinLTOBitcode::ID = 0;
525 INITIALIZE_PASS_BEGIN(WriteThinLTOBitcode, "write-thinlto-bitcode",
526 "Write ThinLTO Bitcode", false, true)
527 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
528 INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass)
529 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
530 INITIALIZE_PASS_END(WriteThinLTOBitcode, "write-thinlto-bitcode",
531 "Write ThinLTO Bitcode", false, true)
533 ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str,
534 raw_ostream *ThinLinkOS) {
535 return new WriteThinLTOBitcode(Str, ThinLinkOS);
538 PreservedAnalyses
539 llvm::ThinLTOBitcodeWriterPass::run(Module &M, ModuleAnalysisManager &AM) {
540 FunctionAnalysisManager &FAM =
541 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
542 writeThinLTOBitcode(OS, ThinLinkOS,
543 [&FAM](Function &F) -> AAResults & {
544 return FAM.getResult<AAManager>(F);
546 M, &AM.getResult<ModuleSummaryIndexAnalysis>(M));
547 return PreservedAnalyses::all();