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 // This pass prepares a module containing type metadata for ThinLTO by splitting
  11 // it into regular and thin LTO parts if possible, and writing both parts to
  12 // a multi-module bitcode file. Modules that do not contain type metadata are
  13 // written unmodified as a single module.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/BasicAliasAnalysis.h"
  18 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
  19 #include "llvm/Analysis/ProfileSummaryInfo.h"
  20 #include "llvm/Analysis/TypeMetadataUtils.h"
  21 #include "llvm/Bitcode/BitcodeWriter.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DebugInfo.h"
  24 #include "llvm/IR/Intrinsics.h"
  25 #include "llvm/IR/Module.h"
  26 #include "llvm/IR/PassManager.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Support/FileSystem.h"
  29 #include "llvm/Support/ScopedPrinter.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include "llvm/Transforms/IPO.h"
  32 #include "llvm/Transforms/IPO/FunctionAttrs.h"
  33 #include "llvm/Transforms/Utils/Cloning.h"
  34 #include "llvm/Transforms/Utils/ModuleUtils.h"
  35 using namespace llvm;
  36
  37 namespace {
  38
  39 // Promote each local-linkage entity defined by ExportM and used by ImportM by
  40 // changing visibility and appending the given ModuleId.
  41 void promoteInternals(Module &ExportM, Module &ImportM, StringRef ModuleId) {
  42   DenseMap<const Comdat *, Comdat *> RenamedComdats;
  43   for (auto &ExportGV : ExportM.global_values()) {
  44     if (!ExportGV.hasLocalLinkage())
  45       continue;
  46
  47     auto Name = ExportGV.getName();
  48     GlobalValue *ImportGV = ImportM.getNamedValue(Name);
  49     if (!ImportGV || ImportGV->use_empty())
  50       continue;
  51
  52     std::string NewName = (Name + ModuleId).str();
  53
  54     if (const auto *C = ExportGV.getComdat())
  55       if (C->getName() == Name)
  56         RenamedComdats.try_emplace(C, ExportM.getOrInsertComdat(NewName));
  57
  58     ExportGV.setName(NewName);
  59     ExportGV.setLinkage(GlobalValue::ExternalLinkage);
  60     ExportGV.setVisibility(GlobalValue::HiddenVisibility);
  61
  62     ImportGV->setName(NewName);
  63     ImportGV->setVisibility(GlobalValue::HiddenVisibility);
  64   }
  65
  66   if (!RenamedComdats.empty())
  67     for (auto &GO : ExportM.global_objects())
  68       if (auto *C = GO.getComdat()) {
  69         auto Replacement = RenamedComdats.find(C);
  70         if (Replacement != RenamedComdats.end())
  71           GO.setComdat(Replacement->second);
  72       }
  73 }
  74
  75 // Promote all internal (i.e. distinct) type ids used by the module by replacing
  76 // them with external type ids formed using the module id.
  77 //
  78 // Note that this needs to be done before we clone the module because each clone
  79 // will receive its own set of distinct metadata nodes.
  80 void promoteTypeIds(Module &M, StringRef ModuleId) {
  81   DenseMap<Metadata *, Metadata *> LocalToGlobal;
  82   auto ExternalizeTypeId = [&](CallInst *CI, unsigned ArgNo) {
  83     Metadata *MD =
  84         cast<MetadataAsValue>(CI->getArgOperand(ArgNo))->getMetadata();
  85
  86     if (isa<MDNode>(MD) && cast<MDNode>(MD)->isDistinct()) {
  87       Metadata *&GlobalMD = LocalToGlobal[MD];
  88       if (!GlobalMD) {
  89         std::string NewName =
  90             (to_string(LocalToGlobal.size()) + ModuleId).str();
  91         GlobalMD = MDString::get(M.getContext(), NewName);
  92       }
  93
  94       CI->setArgOperand(ArgNo,
  95                         MetadataAsValue::get(M.getContext(), GlobalMD));
  96     }
  97   };
  98
  99   if (Function *TypeTestFunc =
 100           M.getFunction(Intrinsic::getName(Intrinsic::type_test))) {
 101     for (const Use &U : TypeTestFunc->uses()) {
 102       auto CI = cast<CallInst>(U.getUser());
 103       ExternalizeTypeId(CI, 1);
 104     }
 105   }
 106
 107   if (Function *TypeCheckedLoadFunc =
 108           M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load))) {
 109     for (const Use &U : TypeCheckedLoadFunc->uses()) {
 110       auto CI = cast<CallInst>(U.getUser());
 111       ExternalizeTypeId(CI, 2);
 112     }
 113   }
 114
 115   for (GlobalObject &GO : M.global_objects()) {
 116     SmallVector<MDNode *, 1> MDs;
 117     GO.getMetadata(LLVMContext::MD_type, MDs);
 118
 119     GO.eraseMetadata(LLVMContext::MD_type);
 120     for (auto MD : MDs) {
 121       auto I = LocalToGlobal.find(MD->getOperand(1));
 122       if (I == LocalToGlobal.end()) {
 123         GO.addMetadata(LLVMContext::MD_type, *MD);
 124         continue;
 125       }
 126       GO.addMetadata(
 127           LLVMContext::MD_type,
 128           *MDNode::get(M.getContext(),
 129                        ArrayRef<Metadata *>{MD->getOperand(0), I->second}));
 130     }
 131   }
 132 }
 133
 134 // Drop unused globals, and drop type information from function declarations.
 135 // FIXME: If we made functions typeless then there would be no need to do this.
 136 void simplifyExternals(Module &M) {
 137   FunctionType *EmptyFT =
 138       FunctionType::get(Type::getVoidTy(M.getContext()), false);
 139
 140   for (auto I = M.begin(), E = M.end(); I != E;) {
 141     Function &F = *I++;
 142     if (F.isDeclaration() && F.use_empty()) {
 143       F.eraseFromParent();
 144       continue;
 145     }
 146
 147     if (!F.isDeclaration() || F.getFunctionType() == EmptyFT)
 148       continue;
 149
 150     Function *NewF =
 151         Function::Create(EmptyFT, GlobalValue::ExternalLinkage, "", &M);
 152     NewF->setVisibility(F.getVisibility());
 153     NewF->takeName(&F);
 154     F.replaceAllUsesWith(ConstantExpr::getBitCast(NewF, F.getType()));
 155     F.eraseFromParent();
 156   }
 157
 158   for (auto I = M.global_begin(), E = M.global_end(); I != E;) {
 159     GlobalVariable &GV = *I++;
 160     if (GV.isDeclaration() && GV.use_empty()) {
 161       GV.eraseFromParent();
 162       continue;
 163     }
 164   }
 165 }
 166
 167 void filterModule(
 168     Module *M, function_ref<bool(const GlobalValue *)> ShouldKeepDefinition) {
 169   for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end();
 170        I != E;) {
 171     GlobalAlias *GA = &*I++;
 172     if (ShouldKeepDefinition(GA))
 173       continue;
 174
 175     GlobalObject *GO;
 176     if (GA->getValueType()->isFunctionTy())
 177       GO = Function::Create(cast<FunctionType>(GA->getValueType()),
 178                             GlobalValue::ExternalLinkage, "", M);
 179     else
 180       GO = new GlobalVariable(
 181           *M, GA->getValueType(), false, GlobalValue::ExternalLinkage,
 182           nullptr, "", nullptr,
 183           GA->getThreadLocalMode(), GA->getType()->getAddressSpace());
 184     GO->takeName(GA);
 185     GA->replaceAllUsesWith(GO);
 186     GA->eraseFromParent();
 187   }
 188
 189   for (Function &F : *M) {
 190     if (ShouldKeepDefinition(&F))
 191       continue;
 192
 193     F.deleteBody();
 194     F.setComdat(nullptr);
 195     F.clearMetadata();
 196   }
 197
 198   for (GlobalVariable &GV : M->globals()) {
 199     if (ShouldKeepDefinition(&GV))
 200       continue;
 201
 202     GV.setInitializer(nullptr);
 203     GV.setLinkage(GlobalValue::ExternalLinkage);
 204     GV.setComdat(nullptr);
 205     GV.clearMetadata();
 206   }
 207 }
 208
 209 void forEachVirtualFunction(Constant *C, function_ref<void(Function *)> Fn) {
 210   if (auto *F = dyn_cast<Function>(C))
 211     return Fn(F);
 212   if (isa<GlobalValue>(C))
 213     return;
 214   for (Value *Op : C->operands())
 215     forEachVirtualFunction(cast<Constant>(Op), Fn);
 216 }
 217
 218 // If it's possible to split M into regular and thin LTO parts, do so and write
 219 // a multi-module bitcode file with the two parts to OS. Otherwise, write only a
 220 // regular LTO bitcode file to OS.
 221 void splitAndWriteThinLTOBitcode(
 222     raw_ostream &OS, raw_ostream *ThinLinkOS,
 223     function_ref<AAResults &(Function &)> AARGetter, Module &M) {
 224   std::string ModuleId = getUniqueModuleId(&M);
 225   if (ModuleId.empty()) {
 226     // We couldn't generate a module ID for this module, just write it out as a
 227     // regular LTO module.
 228     WriteBitcodeToFile(&M, OS);
 229     if (ThinLinkOS)
 230       // We don't have a ThinLTO part, but still write the module to the
 231       // ThinLinkOS if requested so that the expected output file is produced.
 232       WriteBitcodeToFile(&M, *ThinLinkOS);
 233     return;
 234   }
 235
 236   promoteTypeIds(M, ModuleId);
 237
 238   // Returns whether a global has attached type metadata. Such globals may
 239   // participate in CFI or whole-program devirtualization, so they need to
 240   // appear in the merged module instead of the thin LTO module.
 241   auto HasTypeMetadata = [&](const GlobalObject *GO) {
 242     SmallVector<MDNode *, 1> MDs;
 243     GO->getMetadata(LLVMContext::MD_type, MDs);
 244     return !MDs.empty();
 245   };
 246
 247   // Collect the set of virtual functions that are eligible for virtual constant
 248   // propagation. Each eligible function must not access memory, must return
 249   // an integer of width <=64 bits, must take at least one argument, must not
 250   // use its first argument (assumed to be "this") and all arguments other than
 251   // the first one must be of <=64 bit integer type.
 252   //
 253   // Note that we test whether this copy of the function is readnone, rather
 254   // than testing function attributes, which must hold for any copy of the
 255   // function, even a less optimized version substituted at link time. This is
 256   // sound because the virtual constant propagation optimizations effectively
 257   // inline all implementations of the virtual function into each call site,
 258   // rather than using function attributes to perform local optimization.
 259   std::set<const Function *> EligibleVirtualFns;
 260   // If any member of a comdat lives in MergedM, put all members of that
 261   // comdat in MergedM to keep the comdat together.
 262   DenseSet<const Comdat *> MergedMComdats;
 263   for (GlobalVariable &GV : M.globals())
 264     if (HasTypeMetadata(&GV)) {
 265       if (const auto *C = GV.getComdat())
 266         MergedMComdats.insert(C);
 267       forEachVirtualFunction(GV.getInitializer(), [&](Function *F) {
 268         auto *RT = dyn_cast<IntegerType>(F->getReturnType());
 269         if (!RT || RT->getBitWidth() > 64 || F->arg_empty() ||
 270             !F->arg_begin()->use_empty())
 271           return;
 272         for (auto &Arg : make_range(std::next(F->arg_begin()), F->arg_end())) {
 273           auto *ArgT = dyn_cast<IntegerType>(Arg.getType());
 274           if (!ArgT || ArgT->getBitWidth() > 64)
 275             return;
 276         }
 277         if (computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
 278           EligibleVirtualFns.insert(F);
 279       });
 280     }
 281
 282   ValueToValueMapTy VMap;
 283   std::unique_ptr<Module> MergedM(
 284       CloneModule(&M, VMap, [&](const GlobalValue *GV) -> bool {
 285         if (const auto *C = GV->getComdat())
 286           if (MergedMComdats.count(C))
 287             return true;
 288         if (auto *F = dyn_cast<Function>(GV))
 289           return EligibleVirtualFns.count(F);
 290         if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
 291           return HasTypeMetadata(GVar);
 292         return false;
 293       }));
 294   StripDebugInfo(*MergedM);
 295
 296   for (Function &F : *MergedM)
 297     if (!F.isDeclaration()) {
 298       // Reset the linkage of all functions eligible for virtual constant
 299       // propagation. The canonical definitions live in the thin LTO module so
 300       // that they can be imported.
 301       F.setLinkage(GlobalValue::AvailableExternallyLinkage);
 302       F.setComdat(nullptr);
 303     }
 304
 305   // Remove all globals with type metadata, globals with comdats that live in
 306   // MergedM, and aliases pointing to such globals from the thin LTO module.
 307   filterModule(&M, [&](const GlobalValue *GV) {
 308     if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
 309       if (HasTypeMetadata(GVar))
 310         return false;
 311     if (const auto *C = GV->getComdat())
 312       if (MergedMComdats.count(C))
 313         return false;
 314     return true;
 315   });
 316
 317   promoteInternals(*MergedM, M, ModuleId);
 318   promoteInternals(M, *MergedM, ModuleId);
 319
 320   simplifyExternals(*MergedM);
 321
 322
 323   // FIXME: Try to re-use BSI and PFI from the original module here.
 324   ProfileSummaryInfo PSI(M);
 325   ModuleSummaryIndex Index = buildModuleSummaryIndex(M, nullptr, &PSI);
 326
 327   SmallVector<char, 0> Buffer;
 328
 329   BitcodeWriter W(Buffer);
 330   // Save the module hash produced for the full bitcode, which will
 331   // be used in the backends, and use that in the minimized bitcode
 332   // produced for the full link.
 333   ModuleHash ModHash = {{0}};
 334   W.writeModule(&M, /*ShouldPreserveUseListOrder=*/false, &Index,
 335                 /*GenerateHash=*/true, &ModHash);
 336   W.writeModule(MergedM.get());
 337   W.writeStrtab();
 338   OS << Buffer;
 339
 340   // If a minimized bitcode module was requested for the thin link,
 341   // strip the debug info (the merged module was already stripped above)
 342   // and write it to the given OS.
 343   if (ThinLinkOS) {
 344     Buffer.clear();
 345     BitcodeWriter W2(Buffer);
 346     StripDebugInfo(M);
 347     W2.writeModule(&M, /*ShouldPreserveUseListOrder=*/false, &Index,
 348                    /*GenerateHash=*/false, &ModHash);
 349     W2.writeModule(MergedM.get());
 350     W2.writeStrtab();
 351     *ThinLinkOS << Buffer;
 352   }
 353 }
 354
 355 // Returns whether this module needs to be split because it uses type metadata.
 356 bool requiresSplit(Module &M) {
 357   SmallVector<MDNode *, 1> MDs;
 358   for (auto &GO : M.global_objects()) {
 359     GO.getMetadata(LLVMContext::MD_type, MDs);
 360     if (!MDs.empty())
 361       return true;
 362   }
 363
 364   return false;
 365 }
 366
 367 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
 368                          function_ref<AAResults &(Function &)> AARGetter,
 369                          Module &M, const ModuleSummaryIndex *Index) {
 370   // See if this module has any type metadata. If so, we need to split it.
 371   if (requiresSplit(M))
 372     return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
 373
 374   // Otherwise we can just write it out as a regular module.
 375
 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   WriteBitcodeToFile(&M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
 381                      /*GenerateHash=*/true, &ModHash);
 382   // If a minimized bitcode module was requested for the thin link,
 383   // strip the debug info and write it to the given OS.
 384   if (ThinLinkOS) {
 385     StripDebugInfo(M);
 386     WriteBitcodeToFile(&M, *ThinLinkOS, /*ShouldPreserveUseListOrder=*/false,
 387                        Index,
 388                        /*GenerateHash=*/false, &ModHash);
 389   }
 390 }
 391
 392 class WriteThinLTOBitcode : public ModulePass {
 393   raw_ostream &OS; // raw_ostream to print on
 394   // The output stream on which to emit a minimized module for use
 395   // just in the thin link, if requested.
 396   raw_ostream *ThinLinkOS;
 397
 398 public:
 399   static char ID; // Pass identification, replacement for typeid
 400   WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()), ThinLinkOS(nullptr) {
 401     initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
 402   }
 403
 404   explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
 405       : ModulePass(ID), OS(o), ThinLinkOS(ThinLinkOS) {
 406     initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
 407   }
 408
 409   StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
 410
 411   bool runOnModule(Module &M) override {
 412     const ModuleSummaryIndex *Index =
 413         &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
 414     writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
 415     return true;
 416   }
 417   void getAnalysisUsage(AnalysisUsage &AU) const override {
 418     AU.setPreservesAll();
 419     AU.addRequired<AssumptionCacheTracker>();
 420     AU.addRequired<ModuleSummaryIndexWrapperPass>();
 421     AU.addRequired<TargetLibraryInfoWrapperPass>();
 422   }
 423 };
 424 } // anonymous namespace
 425
 426 char WriteThinLTOBitcode::ID = 0;
 427 INITIALIZE_PASS_BEGIN(WriteThinLTOBitcode, "write-thinlto-bitcode",
 428                       "Write ThinLTO Bitcode", false, true)
 429 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 430 INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass)
 431 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 432 INITIALIZE_PASS_END(WriteThinLTOBitcode, "write-thinlto-bitcode",
 433                     "Write ThinLTO Bitcode", false, true)
 434
 435 ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str,
 436                                                 raw_ostream *ThinLinkOS) {
 437   return new WriteThinLTOBitcode(Str, ThinLinkOS);
 438 }