[WPD] Allow load/save bitcoded index when running opt -wholeprogramdevirt

[evgeny777]

Summary

Depends on D73091

[evgeny777]

Removed WPD resolution from source index asm file.

[tejohnson]

One issue with taking combined indexes in testing is the handling of module paths when there are locals (won't be hit by the included test which doesn't contain any). E.g. in WPD if we try to promote when the target is a local function, we attempt to get its promoted global name:

// If target is a local function and we are exporting it by
// devirtualizing a call in another module, we need to record the
// promoted name.
Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
    TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));

Since the modulePath (hardcoded in the test .ll files) won't be found in the index's module path table we'll get an assert in getModulePath. Until this is solved (e.g. possibly via a regex replacement scheme specified by an option that is applied to the module paths in the index, either during assembly or when reading in the bitcode), I'm reluctant to add facilities to consume combined indexes for testing.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

121–122

Option summary needs update.

127–129

Ditto (and in particular the format being dependent on the suffix).

[evgeny777]

One issue with taking combined indexes in testing is the handling of module paths when there are locals (won't be hit by the included test which doesn't contain any). E.g. in WPD if we try to promote when the target is a local function, we attempt to get its promoted global name:

Honestly, I don't understand how we can step on this. The piece of code you've shown is from DevirtIndex::trySingleImplDevirt. There is no way opt -wholeprogramdevirt can call it, because it uses DevirtModule::trySingleImplDevirt and the latter doesn't have to deal with internal virtual functions, because they're promoted by ThinLTOBitcodeWriter (in order to export declarations to regular LTO module).

[evgeny777]

Addressed

[tejohnson]

In D73094#1833931, @evgeny777 wrote:

One issue with taking combined indexes in testing is the handling of module paths when there are locals (won't be hit by the included test which doesn't contain any). E.g. in WPD if we try to promote when the target is a local function, we attempt to get its promoted global name:

Honestly, I don't understand how we can step on this. The piece of code you've shown is from DevirtIndex::trySingleImplDevirt. There is no way opt -wholeprogramdevirt can call it, because it uses DevirtModule::trySingleImplDevirt and the latter doesn't have to deal with internal virtual functions, because they're promoted by ThinLTOBitcodeWriter (in order to export declarations to regular LTO module).

Looks like there may not be an issue at this moment. I have a vague concern that this could result in unexpected failures/issues. The other place where we check the modulePath in WPD is in AddCalls, which is also invoked by DevirtModule. However, it is used to determine whether the target function needs exporting, and this return value is ignored when this is called from DevirtModule, because as you note any promotion should already have been done. Not sure if that should previously have asserted a false return value, which would have fired incorrectly if the testing code used a bitcode with a local function. Actually, we won't even call AddCalls in that case, because it is guarded by a non-null return value from ExportSummary->getValueInfo(TheFn->getGUID())), which will be null if TheFn is a local in a testing environment, and therefore no edges will be added to the summary in that case, which is ok if we aren't testing for that.

Would it be worthwhile to add some checking in somewhere that there are no locals in the index read by opt?

[evgeny777]

Would it be worthwhile to add some checking in somewhere that there are no locals in the index read by opt?

Probably we can assert on !isLocalLinkage(FS->linkage()) when analyzing ExportSummary in DevirtModule::run. Another option is to check presence of regular LTO module in combined index when reading summary.

[tejohnson]

In D73094#1834139, @evgeny777 wrote:

Would it be worthwhile to add some checking in somewhere that there are no locals in the index read by opt?

Probably we can assert on !isLocalLinkage(FS->linkage()) when analyzing ExportSummary in DevirtModule::run.

You can't just always assert that during WPD though, only those locals used by the importing ThinLTO module are promoted when splitting. See promoteInternals() in ThinLTOBitcodeWriter.cpp. So it might be better to do any checking in opt itself, after reading the index, essentially to enforce that we cannot guarantee that any locals are handled as expected in this testing mode.

Another option is to check presence of regular LTO module in combined index when reading summary.

This sounds like a good idea too.

[evgeny777]

Added check for regular LTO module in combined summary

So it might be better to do any checking in opt itself, after reading the index, essentially to enforce that we cannot guarantee that any locals are handled as expected in this testing mode

After some experiments this seems useless to me. Given combined summary I can try identifying local virtual functions using this approach:

1. Call ModuleSummaryIndex::collectDefinedFunctionsForModule("[Regular LTO]", ...)
2. Given GUID of virtual function locate all summaries across all modules
3. Check that neither of those summaries has local linkage

But what's the point? Even if I find such summary this most likely means that either ThinLTOBitcodeWriter is broken or index is intentionally modified.

[tejohnson]

lgtm with a couple requests for comments.

In D73094#1836360, @evgeny777 wrote:

Added check for regular LTO module in combined summary

So it might be better to do any checking in opt itself, after reading the index, essentially to enforce that we cannot guarantee that any locals are handled as expected in this testing mode

After some experiments this seems useless to me. Given combined summary I can try identifying local virtual functions using this approach:

1. Call ModuleSummaryIndex::collectDefinedFunctionsForModule("[Regular LTO]", ...)
2. Given GUID of virtual function locate all summaries across all modules
3. Check that neither of those summaries has local linkage

But what's the point? Even if I find such summary this most likely means that either ThinLTOBitcodeWriter is broken or index is intentionally modified.

I can't create a scenario where we could run into an issue currently, if this combined index is only used for WPD exporting, with a properly split and promoted module. My concern is more that in the future someone may try to synthesize a combined index in assembly that has an issue, or due to code changes we could end up trying to look for the GUID of a local that didn't originally need promotion in this code. I was originally envisioning some more simpler minded checking, that simply required there to be no locals in the summary whatsoever, until we can properly handle them by fixing up the module paths when testing, e.g. via an option providing a regex replacement scheme on the module paths when assembling.

But since the risk in this particular usage of a combined index seems very low to non-existent at the moment, please go ahead but add a comment somewhere, maybe where we are reading the index, that we assume that any values that WPD cares about will have been properly promoted to global scope.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

747

Comment as to why.

llvm/include/llvm/IR/ModuleSummaryIndex.h

public:
 
   // Current version for the module summary in bitcode files.
   // The BitcodeSummaryVersion should be bumped whenever we introduce changes
   // in the way some record are interpreted, like flags for instance.
   // Note that incrementing this may require changes in both BitcodeReader.cpp
   // and BitcodeWriter.cpp.
   static constexpr uint64_t BitcodeSummaryVersion = 8;
 
+  // Regular LTO module name for ASM writer
+  static constexpr const char *getRegularLTOModuleName() {
+    return "[Regular LTO]";
+  }
+
   bool haveGVs() const { return HaveGVs; }
 
   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
   gvsummary_iterator end() { return GlobalValueMap.end(); }
   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
   size_t size() const { return GlobalValueMap.size(); }
 

llvm/lib/IR/AsmWriter.cpp

void AssemblyWriter::printModuleSummaryIndex() {
   assert(TheIndex);
   Machine.initializeIndexIfNeeded();
 
   Out << "\n";
 
   // Print module path entries. To print in order, add paths to a vector
   // indexed by module slot.
   std::vector<std::pair<std::string, ModuleHash>> moduleVec;
-  std::string RegularLTOModuleName = "[Regular LTO]";
+  std::string RegularLTOModuleName =
+      ModuleSummaryIndex::getRegularLTOModuleName();
   moduleVec.resize(TheIndex->modulePaths().size());
   for (auto &ModPath : TheIndex->modulePaths())
     moduleVec[Machine.getModulePathSlot(ModPath.first())] = std::make_pair(
         // A module id of -1 is a special entry for a regular LTO module created
         // during the thin link.
         ModPath.second.first == -1u ? RegularLTOModuleName
                                     : (std::string)ModPath.first(),
         ModPath.second.second);

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/TypeMetadataUtils.h"
+#include "llvm/Bitcode/BitcodeReader.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSummaryIndexYAML.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 #include "llvm/PassSupport.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/Utils/Evaluator.h"
 #include <algorithm>
 #include <cstddef>
cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
                clEnumValN(PassSummaryAction::Import, "import",
                           "Import typeid resolutions from summary and globals"),
                clEnumValN(PassSummaryAction::Export, "export",
                           "Export typeid resolutions to summary and globals")),
     cl::Hidden);
 
 static cl::opt<std::string> ClReadSummary(
     "wholeprogramdevirt-read-summary",
-    cl::desc("Read summary from given YAML file before running pass"),
+    cl::desc(
+        "Read summary from given bitcode or YAML file before running pass"),
     cl::Hidden);
 
 static cl::opt<std::string> ClWriteSummary(
     "wholeprogramdevirt-write-summary",
-    cl::desc("Write summary to given YAML file after running pass"),
+    cl::desc("Write summary to given bitcode or YAML file after running pass. "
+             "Output file format is deduced from extension: *.bc means writing "
+             "bitcode, otherwise YAML"),
     cl::Hidden);
 
 static cl::opt<unsigned>
     ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
                 cl::init(10), cl::ZeroOrMore,
                 cl::desc("Maximum number of call targets per "
                          "call site to enable branch funnels"));
 
for (auto &SlotSummary : T.second) {
           WPDRes->second.SingleImplName,
           Summary.getModuleHash(S->modulePath()));
     }
   }
 }
 
 } // end namespace llvm
 
+static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) {
+  // Check that summary index contains regular LTO module
+  const auto &ModPaths = Summary->modulePaths();
+  if (ModPaths.find(ModuleSummaryIndex::getRegularLTOModuleName()) ==
+      ModPaths.end())
+    return createStringError(
+        errc::invalid_argument,
+        "combined summary should contain Regular LTO module");
+  return ErrorSuccess();
+}
+
 bool DevirtModule::runForTesting(
     Module &M, function_ref<AAResults &(Function &)> AARGetter,
     function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
     function_ref<DominatorTree &(Function &)> LookupDomTree) {
-  ModuleSummaryIndex Summary(/*HaveGVs=*/false);
+  std::unique_ptr<ModuleSummaryIndex> Summary =
+      std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false);
 
   // Handle the command-line summary arguments. This code is for testing
   // purposes only, so we handle errors directly.
   if (!ClReadSummary.empty()) {
     ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
                           ": ");
     auto ReadSummaryFile =
         ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
-
+    if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =
+            getModuleSummaryIndex(*ReadSummaryFile)) {
+      Summary = std::move(*SummaryOrErr);
+      ExitOnErr(checkCombinedSummaryForTesting(Summary.get()));
+    } else {
+      // Try YAML if we've failed with bitcode.
+      consumeError(SummaryOrErr.takeError());
       yaml::Input In(ReadSummaryFile->getBuffer());
-    In >> Summary;
+      In >> *Summary;
       ExitOnErr(errorCodeToError(In.error()));
     }
+  }
 
   bool Changed =
-      DevirtModule(
-          M, AARGetter, OREGetter, LookupDomTree,
-          ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
-          ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
+      DevirtModule(M, AARGetter, OREGetter, LookupDomTree,
+                   ClSummaryAction == PassSummaryAction::Export ? Summary.get()
+                                                                : nullptr,
+                   ClSummaryAction == PassSummaryAction::Import ? Summary.get()
+                                                                : nullptr)
           .run();
 
   if (!ClWriteSummary.empty()) {
     ExitOnError ExitOnErr(
         "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
     std::error_code EC;
+    if (StringRef(ClWriteSummary).endswith(".bc")) {
+      raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_None);
+      ExitOnErr(errorCodeToError(EC));
+      WriteIndexToFile(*Summary, OS);
+    } else {
       raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_Text);
       ExitOnErr(errorCodeToError(EC));
-
       yaml::Output Out(OS);
-    Out << Summary;
+      Out << *Summary;
+    }
   }
 
   return Changed;
 }
 
 void DevirtModule::buildTypeIdentifierMap(
     std::vector<VTableBits> &Bits,
     DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {

llvm/test/Transforms/WholeProgramDevirt/Inputs/devirt-bad-index.ll

+; ModuleID = '/tmp/devirt-index.bc'
+source_filename = "/tmp/devirt-index.bc"
+
+^0 = module: (path: "/tmp/main.bc", hash: (3499594384, 1671013073, 3271036935, 1830411232, 59290952))

llvm/test/Transforms/WholeProgramDevirt/Inputs/devirt-single-impl2-index.ll

+; ModuleID = '/tmp/devirt-index.bc'
+source_filename = "/tmp/devirt-index.bc"
+
+^0 = module: (path: "/tmp/main.bc", hash: (3499594384, 1671013073, 3271036935, 1830411232, 59290952))
+^1 = module: (path: "/tmp/foo.bc", hash: (1981453201, 1990260332, 4054522231, 886164300, 2116061388))
+^2 = module: (path: "/tmp/bar.bc", hash: (1315792037, 3870713320, 284974409, 169291533, 3565750560))
+^3 = module: (path: "[Regular LTO]", hash: (0, 0, 0, 0, 0))
+^4 = gv: (guid: 7004155349499253778, summaries: (variable: (module: ^2, flags: (linkage: linkonce_odr, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), varFlags: (readonly: 0, writeonly: 0, constant: 1))))
+^5 = gv: (guid: 7112837063505133550, summaries: (variable: (module: ^2, flags: (linkage: linkonce_odr, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), varFlags: (readonly: 0, writeonly: 0, constant: 1), refs: (^4))))
+^6 = gv: (guid: 12105754951942688208, summaries: (variable: (module: ^3, flags: (linkage: linkonce_odr, notEligibleToImport: 1, live: 1, dsoLocal: 1, canAutoHide: 1), varFlags: (readonly: 0, writeonly: 0, constant: 1), refs: (^5, ^7))))
+^7 = gv: (guid: 13351721993301222997, summaries: (function: (module: ^2, flags: (linkage: linkonce_odr, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 1), insts: 1), function: (module: ^3, flags: (linkage: available_externally, notEligibleToImport: 1, live: 1, dsoLocal: 1, canAutoHide: 0), insts: 1)))
+^8 = gv: (guid: 15822663052811949562, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), insts: 2, calls: ((callee: ^10)))))
+^9 = gv: (guid: 16692224328168775211, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), insts: 9, typeIdInfo: (typeTestAssumeConstVCalls: ((vFuncId: (guid: 7004155349499253778, offset: 0)))))))
+^10 = gv: (guid: 17377440600225628772, summaries: (function: (module: ^2, flags: (linkage: external, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), insts: 9, calls: ((callee: ^9)), refs: (^6))))

llvm/test/Transforms/WholeProgramDevirt/devirt-single-impl2.ll

+; Check that we can run WPD export using opt -wholeprogramdevirt while
+; loading/saving index from/to bitcode
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-as %p/Inputs/devirt-single-impl2-index.ll -o %t.index.bc
+; RUN: opt %s -S -wholeprogramdevirt -wholeprogramdevirt-read-summary=%t.index.bc \
+; RUN:     -wholeprogramdevirt-summary-action=export \
+; RUN:     -wholeprogramdevirt-write-summary=%t2.index.bc -o /dev/null
+; RUN: llvm-dis %t2.index.bc -o - | FileCheck %s
+
+; Check couple of bad summary indexes
+; RUN: llvm-as %p/Inputs/devirt-bad-index.ll -o %t-bad.index.bc
+; RUN: not opt %s -S -wholeprogramdevirt -wholeprogramdevirt-read-summary=%t-bad1.index.bc \
+; RUN:     -wholeprogramdevirt-summary-action=export -o /dev/null 2>&1 | FileCheck %s --check-prefix=MISSING-MODULE
+
+; Check single impl devirtulation in summary
+; CHECK: typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: unsat, sizeM1BitWidth: 0), wpdResolutions: ((offset: 0, wpdRes: (kind: singleImpl, singleImplName: "_ZNK1A1fEv"))))) ; guid
+
+; MISSING-MODULE: combined summary should contain Regular LTO module
+
+source_filename = "ld-temp.o"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+
+$_ZTV1A = comdat any
+
+@_ZTV1A = weak_odr hidden unnamed_addr constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* bitcast ({ i8*, i8* }* @_ZTI1A to i8*), i8* bitcast (i32 (%struct.A*)* @_ZNK1A1fEv to i8*)] }, comdat, align 8, !type !0, !type !1
+@_ZTI1A = external hidden constant { i8*, i8* }, align 8
+define available_externally hidden i32 @_ZNK1A1fEv(%struct.A* %this) unnamed_addr align 2 {
+entry:
+  ret i32 3
+}
+
+!llvm.ident = !{!2}
+!llvm.module.flags = !{!3, !4, !5, !6}
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTSM1AKFivE.virtual"}
+!2 = !{!"clang version 10.0.0 (trunk 373596)"}
+!3 = !{i32 1, !"wchar_size", i32 4}
+!4 = !{i32 1, !"EnableSplitLTOUnit", i32 1}
+!5 = !{i32 1, !"ThinLTO", i32 0}
+!6 = !{i32 1, !"LTOPostLink", i32 1}