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