contrib/llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

   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/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"
  28 using namespace llvm;
  29
  30 namespace {
  31
  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())
  39       continue;
  40
  41     auto Name = ExportGV.getName();
  42     GlobalValue *ImportGV = nullptr;
  43     if (!PromoteExtra.count(&ExportGV)) {
  44       ImportGV = ImportM.getNamedValue(Name);
  45       if (!ImportGV)
  46         continue;
  47       ImportGV->removeDeadConstantUsers();
  48       if (ImportGV->use_empty()) {
  49         ImportGV->eraseFromParent();
  50         continue;
  51       }
  52     }
  53
  54     std::string NewName = (Name + ModuleId).str();
  55
  56     if (const auto *C = ExportGV.getComdat())
  57       if (C->getName() == Name)
  58         RenamedComdats.try_emplace(C, ExportM.getOrInsertComdat(NewName));
  59
  60     ExportGV.setName(NewName);
  61     ExportGV.setLinkage(GlobalValue::ExternalLinkage);
  62     ExportGV.setVisibility(GlobalValue::HiddenVisibility);
  63
  64     if (ImportGV) {
  65       ImportGV->setName(NewName);
  66       ImportGV->setVisibility(GlobalValue::HiddenVisibility);
  67     }
  68   }
  69
  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);
  76       }
  77 }
  78
  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.
  81 //
  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) {
  87     Metadata *MD =
  88         cast<MetadataAsValue>(CI->getArgOperand(ArgNo))->getMetadata();
  89
  90     if (isa<MDNode>(MD) && cast<MDNode>(MD)->isDistinct()) {
  91       Metadata *&GlobalMD = LocalToGlobal[MD];
  92       if (!GlobalMD) {
  93         std::string NewName =
  94             (to_string(LocalToGlobal.size()) + ModuleId).str();
  95         GlobalMD = MDString::get(M.getContext(), NewName);
  96       }
  97
  98       CI->setArgOperand(ArgNo,
  99                         MetadataAsValue::get(M.getContext(), GlobalMD));
 100     }
 101   };
 102
 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);
 108     }
 109   }
 110
 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);
 116     }
 117   }
 118
 119   for (GlobalObject &GO : M.global_objects()) {
 120     SmallVector<MDNode *, 1> MDs;
 121     GO.getMetadata(LLVMContext::MD_type, MDs);
 122
 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);
 128         continue;
 129       }
 130       GO.addMetadata(
 131           LLVMContext::MD_type,
 132           *MDNode::get(M.getContext(),
 133                        ArrayRef<Metadata *>{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.
 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, "", &M);
 158     NewF->setVisibility(F.getVisibility());
 159     NewF->takeName(&F);
 160     F.replaceAllUsesWith(ConstantExpr::getBitCast(NewF, F.getType()));
 161     F.eraseFromParent();
 162   }
 163
 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();
 168       continue;
 169     }
 170   }
 171 }
 172
 173 void filterModule(
 174     Module *M, function_ref<bool(const GlobalValue *)> ShouldKeepDefinition) {
 175   for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end();
 176        I != E;) {
 177     GlobalAlias *GA = &*I++;
 178     if (ShouldKeepDefinition(GA))
 179       continue;
 180
 181     GlobalObject *GO;
 182     if (GA->getValueType()->isFunctionTy())
 183       GO = Function::Create(cast<FunctionType>(GA->getValueType()),
 184                             GlobalValue::ExternalLinkage, "", M);
 185     else
 186       GO = new GlobalVariable(
 187           *M, GA->getValueType(), false, GlobalValue::ExternalLinkage,
 188           nullptr, "", nullptr,
 189           GA->getThreadLocalMode(), GA->getType()->getAddressSpace());
 190     GO->takeName(GA);
 191     GA->replaceAllUsesWith(GO);
 192     GA->eraseFromParent();
 193   }
 194
 195   for (Function &F : *M) {
 196     if (ShouldKeepDefinition(&F))
 197       continue;
 198
 199     F.deleteBody();
 200     F.setComdat(nullptr);
 201     F.clearMetadata();
 202   }
 203
 204   for (GlobalVariable &GV : M->globals()) {
 205     if (ShouldKeepDefinition(&GV))
 206       continue;
 207
 208     GV.setInitializer(nullptr);
 209     GV.setLinkage(GlobalValue::ExternalLinkage);
 210     GV.setComdat(nullptr);
 211     GV.clearMetadata();
 212   }
 213 }
 214
 215 void forEachVirtualFunction(Constant *C, function_ref<void(Function *)> Fn) {
 216   if (auto *F = dyn_cast<Function>(C))
 217     return Fn(F);
 218   if (isa<GlobalValue>(C))
 219     return;
 220   for (Value *Op : C->operands())
 221     forEachVirtualFunction(cast<Constant>(Op), Fn);
 222 }
 223
 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);
 235     if (ThinLinkOS)
 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);
 239     return;
 240   }
 241
 242   promoteTypeIds(M, ModuleId);
 243
 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);
 250     return !MDs.empty();
 251   };
 252
 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.
 258   //
 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())
 277           return;
 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)
 281             return;
 282         }
 283         if (!F->isDeclaration() &&
 284             computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
 285           EligibleVirtualFns.insert(F);
 286       });
 287     }
 288
 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))
 294             return true;
 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);
 299         return false;
 300       }));
 301   StripDebugInfo(*MergedM);
 302
 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);
 310     }
 311
 312   SetVector<GlobalValue *> CfiFunctions;
 313   for (auto &F : M)
 314     if ((!F.hasLocalLinkage() || F.hasAddressTaken()) && HasTypeMetadata(&F))
 315       CfiFunctions.insert(&F);
 316
 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))
 322         return false;
 323     if (const auto *C = GV->getComdat())
 324       if (MergedMComdats.count(C))
 325         return false;
 326     return true;
 327   });
 328
 329   promoteInternals(*MergedM, M, ModuleId, CfiFunctions);
 330   promoteInternals(M, *MergedM, ModuleId, CfiFunctions);
 331
 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);
 337
 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;
 346     else
 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));
 353   }
 354
 355   if(!CfiFunctionMDs.empty()) {
 356     NamedMDNode *NMD = MergedM->getOrInsertNamedMetadata("cfi.functions");
 357     for (auto MD : CfiFunctionMDs)
 358       NMD->addOperand(MD);
 359   }
 360
 361   simplifyExternals(*MergedM);
 362
 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);
 366
 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);
 372
 373   SmallVector<char, 0> Buffer;
 374
 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,
 383                 &MergedMIndex);
 384   W.writeSymtab();
 385   W.writeStrtab();
 386   OS << Buffer;
 387
 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).
 391   if (ThinLinkOS) {
 392     Buffer.clear();
 393     BitcodeWriter W2(Buffer);
 394     StripDebugInfo(M);
 395     W2.writeThinLinkBitcode(&M, Index, ModHash);
 396     W2.writeModule(MergedM.get(), /*ShouldPreserveUseListOrder=*/false,
 397                    &MergedMIndex);
 398     W2.writeSymtab();
 399     W2.writeStrtab();
 400     *ThinLinkOS << Buffer;
 401   }
 402 }
 403
 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);
 409     if (!MDs.empty())
 410       return true;
 411   }
 412
 413   return false;
 414 }
 415
 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);
 422
 423   // Otherwise we can just write it out as a regular module.
 424
 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
 433   // given OS.
 434   if (ThinLinkOS && Index)
 435     WriteThinLinkBitcodeToFile(&M, *ThinLinkOS, *Index, ModHash);
 436 }
 437
 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;
 443
 444 public:
 445   static char ID; // Pass identification, replacement for typeid
 446   WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()), ThinLinkOS(nullptr) {
 447     initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
 448   }
 449
 450   explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
 451       : ModulePass(ID), OS(o), ThinLinkOS(ThinLinkOS) {
 452     initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
 453   }
 454
 455   StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
 456
 457   bool runOnModule(Module &M) override {
 458     const ModuleSummaryIndex *Index =
 459         &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
 460     writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
 461     return true;
 462   }
 463   void getAnalysisUsage(AnalysisUsage &AU) const override {
 464     AU.setPreservesAll();
 465     AU.addRequired<AssumptionCacheTracker>();
 466     AU.addRequired<ModuleSummaryIndexWrapperPass>();
 467     AU.addRequired<TargetLibraryInfoWrapperPass>();
 468   }
 469 };
 470 } // anonymous namespace
 471
 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)
 480
 481 ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str,
 482                                                 raw_ostream *ThinLinkOS) {
 483   return new WriteThinLTOBitcode(Str, ThinLinkOS);
 484 }
 485
 486 PreservedAnalyses
 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);
 493                       },
 494                       M, &AM.getResult<ModuleSummaryIndexAnalysis>(M));
 495   return PreservedAnalyses::all();
 496 }