[ThinLTO] Perform profile-guided indirect call promotion

[tejohnson]

Summary

To enable profile-guided indirect call promotion in ThinLTO mode, we
simply add call graph edges for each profitable target from the profile
to the summaries, then the summary-guided importing will consider the
callee for importing as usual.

Also we need to enable the indirect call promotion pass creation in the
PassManagerBuilder when PerformThinLTO=true (we are in the ThinLTO
backend), so that the newly imported functions are considered for
promotion in the backends.

A couple of other changes:

• Refactored the profitability analysis out of the IC promotion pass and into lib/Analysis so that it can be accessed by the summary index builder.
• The IC promotion profiles refer to callees by GUID, which required adding GUIDs to the per-module VST in bitcode (and assigning them valueIds similar to how they are assigned valueIds in the combined index).

[tejohnson]

Ping

[davidxl]

Can you split the refactor code into a separate patch?

[tejohnson]

In D21932#478232, @davidxl wrote:

Can you split the refactor code into a separate patch?

I moved the refactoring into D22182.
(I haven't updated this to rebase it on top of that one yet, will try to do that later tonight)

[tejohnson]

Rebase on top of D22182.

[tejohnson]

Hmm, the rebase didn't quite work as expected - I still see the diffs that I moved to D22182. Will try to figure out later.

[tejohnson]

I think this should properly rebase on top of D22182.

[davidxl]

include/llvm/IR/ModuleSummaryIndex.h

265 ↗

(On Diff #63383)

This is a duplicate.

lib/Analysis/ModuleSummaryAnalysis.cpp

99 ↗

(On Diff #63383)

When getCalledValue() returns constant, should it be covered above (i.e., CalledFunction is not null)?

104 ↗

(On Diff #63383)

See the comment in the dependent patch -- the icall analysis needs to return set of targets also 'legal'.

lib/Bitcode/Writer/BitcodeWriter.cpp

151 ↗

(On Diff #63383)

Add one line comment before each 'for' -- kind of hard to read a loop deep nested without some background.

[mehdi_amini]

lib/Bitcode/Writer/BitcodeWriter.cpp

151 ↗

(On Diff #63383)

Alternatively, using explicit name for iterator variable can help.

lib/Transforms/IPO/PassManagerBuilder.cpp

366 ↗

(On Diff #63383)

Is this totally related to this patch or is it already an existing mistake? (I.e. could be committed separately?)

Also remove braces for the if block.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

265 ↗

(On Diff #63383)

No, this is new (the other one takes a map of Value* this takes a map of GUID

lib/Analysis/ModuleSummaryAnalysis.cpp

99 ↗

(On Diff #63383)

This was modeled on the checking in PGOIndirectCallSiteVisitor::visitCallSite, which checks if the value is constant after the early return when getCalledFunction() is not-null.

104 ↗

(On Diff #63383)

As noted there, we can't check legality in the refactored code since we don't have access to the called function yet.

lib/Bitcode/Writer/BitcodeWriter.cpp

151 ↗

(On Diff #63383)

Ok, add some comments or use a more explicit name.

lib/Transforms/IPO/PassManagerBuilder.cpp

366 ↗

(On Diff #63383)

It could be committed earlier but would be a no-op without the rest of this patch (unless we happened to import a function that was called directly but also happened to be called indirectly).

Will remove braces.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

366 ↗

(On Diff #63383)

I see, it also runs during the compile phase so it'll only apply to imported function here. That's fine as-is then.

[tejohnson]

• Add comments and variable names to nested for loop.

[mehdi_amini]

lib/Analysis/ModuleSummaryAnalysis.cpp

97 ↗

(On Diff #63701)

Add a one line comment for this code block?

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll

3–4 ↗

(On Diff #63701)

I'm not sure why you need this definition?

[mehdi_amini]

LGTM with the two comments I made previously.

[tejohnson]

In D21932#486256, @mehdi_amini wrote:

LGTM with the two comments I made previously.

Thanks. Somehow I completely missed the last set of comments you added!

lib/Analysis/ModuleSummaryAnalysis.cpp

97 ↗

(On Diff #63701)

Will do.

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll

3–4 ↗

(On Diff #63701)

You're right, this is unnecessary. Removed.

[tejohnson]

• Address latest comments.

[Prazek]

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

150

early exit here will reduce indentation

151–161

I think that you should use braces here. It will be more readable and it will be harder to make mistake modifying it.

295–297

I guess you could use .at() member here, so you won't have to check if it's there with assert.

2858–2862

This code seems a little suspicious because you clear the NameVals vector every time you push it.
You could just create new vector with thouse 2 values and move it to Stream.EmitRecord.

[tejohnson]

Thanks for the review. Responses below.

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

150

ok

151–161

I've always been asked to remove braces when not necessary, so I will leave this as-is unless other reviewers concur.

295–297

True, but for efficiency I prefer to keep the check only in the debug builds. I will add an assertion message though, which should be here.

2858–2862

The clear is needed before using it on the subsequent iteration. This is consistent with the rest of BitcodeWriter.cpp, that uses a single SmallVector per routine, clearing after each EmitRecord call.

I believe this is for efficiency (SmallVector is good for small numbers of vals, has efficient push/pop, but is larger and less efficient to allocate). According to http://llvm.org/docs/ProgrammersManual.html#vector:
"std::vector is well loved and respected. It is useful when SmallVector isn’t: when the size of the vector is often large"

[mehdi_amini]

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

151–161

Agree with Teresa: I believe the LLVM usual coding style is to not add braces unless ambiguity (if/else nested inside an if).
(I agree that it's harder to make a mistake by keeping braces all the time, but that's not the usual LLVM style)

2858–2862

Agree as well: this is a common pattern in LLVM.

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

GlobalValue::GUID getGUID() const {
     assert(Kind == VI_GUID && "Not a GUID type");
     return TheValue.Id;
   }
   /// Accessor for Value* value
   const Value *getValue() const {
     assert(Kind == VI_Value && "Not a Value type");
     return TheValue.V;
   }
+  bool isGUID() const { return Kind == VI_GUID; }
 };
 
 /// \brief Function and variable summary information to aid decisions and
 /// implementation of importing.
 class GlobalValueSummary {
 public:
   /// \brief Sububclass discriminator (for dyn_cast<> et al.)
   enum SummaryKind { AliasKind, FunctionKind, GlobalVarKind };
public:
 
   /// Record a call graph edge from this function to the function identified
   /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile
   /// count (across all calls from this function) or 0 if no PGO.
   void addCallGraphEdge(GlobalValue::GUID CalleeGUID, CalleeInfo Info) {
     CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info));
   }
 
+  /// Record a call graph edge from this function to each function GUID recorded
+  /// in \p CallGraphEdges.
+  void
+  addCallGraphEdges(DenseMap<GlobalValue::GUID, CalleeInfo> &CallGraphEdges) {
+    for (auto &EI : CallGraphEdges)
+      addCallGraphEdge(EI.first, EI.second);
+  }
+
   /// Record a call graph edge from this function to the function identified
   /// by \p CalleeV, with \p CalleeInfo including the cumulative profile
   /// count (across all calls from this function) or 0 if no PGO.
   void addCallGraphEdge(const Value *CalleeV, CalleeInfo Info) {
     CallGraphEdgeList.push_back(std::make_pair(CalleeV, Info));
   }
 
   /// Record a call graph edge from this function to each function recorded

llvm/trunk/lib/Analysis/ModuleSummaryAnalysis.cpp

 // to bitcode or LLVM assembly.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Pass.h"
 using namespace llvm;
void ModuleSummaryIndexBuilder::computeFunctionSummary(
   // be renamed.
   if (!F.hasName())
     return;
 
   unsigned NumInsts = 0;
   // Map from callee ValueId to profile count. Used to accumulate profile
   // counts for all static calls to a given callee.
   DenseMap<const Value *, CalleeInfo> CallGraphEdges;
+  DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges;
   DenseSet<const Value *> RefEdges;
+  ICallPromotionAnalysis ICallAnalysis;
 
   SmallPtrSet<const User *, 8> Visited;
   for (const BasicBlock &BB : F)
     for (const Instruction &I : BB) {
       if (!isa<DbgInfoIntrinsic>(I))
         ++NumInsts;
 
       if (auto CS = ImmutableCallSite(&I)) {
         auto *CalledFunction = CS.getCalledFunction();
-        if (CalledFunction && CalledFunction->hasName() &&
-            !CalledFunction->isIntrinsic()) {
+        // Check if this is a direct call to a known function.
+        if (CalledFunction) {
+          if (CalledFunction->hasName() && !CalledFunction->isIntrinsic()) {
             auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
             auto *CalleeId =
                 M->getValueSymbolTable().lookup(CalledFunction->getName());
             CallGraphEdges[CalleeId] +=
                 (ScaledCount ? ScaledCount.getValue() : 0);
           }
+        } else {
+          // Otherwise, check for an indirect call (call to a non-const value
+          // that isn't an inline assembly call).
+          const CallInst *CI = dyn_cast<CallInst>(&I);
+          if (CS.getCalledValue() && !isa<Constant>(CS.getCalledValue()) &&
+              !(CI && CI->isInlineAsm())) {
+            uint32_t NumVals, NumCandidates;
+            uint64_t TotalCount;
+            auto CandidateProfileData =
+                ICallAnalysis.getPromotionCandidatesForInstruction(
+                    &I, NumVals, TotalCount, NumCandidates);
+            for (auto &Candidate : CandidateProfileData)
+              IndirectCallEdges[Candidate.Value] += Candidate.Count;
+          }
+        }
       }
       findRefEdges(&I, RefEdges, Visited);
     }
 
   GlobalValueSummary::GVFlags Flags(F);
   std::unique_ptr<FunctionSummary> FuncSummary =
       llvm::make_unique<FunctionSummary>(Flags, NumInsts);
   FuncSummary->addCallGraphEdges(CallGraphEdges);
+  FuncSummary->addCallGraphEdges(IndirectCallEdges);
   FuncSummary->addRefEdges(RefEdges);
   Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 void ModuleSummaryIndexBuilder::computeVariableSummary(
     const GlobalVariable &V) {
   DenseSet<const Value *> RefEdges;
   SmallPtrSet<const User *, 8> Visited;

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

class ModuleBitcodeWriter : public BitcodeWriter {
   const ModuleSummaryIndex *Index;
 
   /// True if a module hash record should be written.
   bool GenerateHash;
 
   /// The start bit of the module block, for use in generating a module hash
   uint64_t BitcodeStartBit = 0;
 
+  /// Map that holds the correspondence between GUIDs in the summary index,
+  /// that came from indirect call profiles, and a value id generated by this
+  /// class to use in the VST and summary block records.
+  std::map<GlobalValue::GUID, unsigned> GUIDToValueIdMap;
+
+  /// Tracks the last value id recorded in the GUIDToValueMap.
+  unsigned GlobalValueId;
+
 public:
   /// Constructs a ModuleBitcodeWriter object for the given Module,
   /// writing to the provided \p Buffer.
   ModuleBitcodeWriter(const Module *M, SmallVectorImpl<char> &Buffer,
                       bool ShouldPreserveUseListOrder,
                       const ModuleSummaryIndex *Index, bool GenerateHash)
       : BitcodeWriter(Buffer), M(*M), VE(*M, ShouldPreserveUseListOrder),
         Index(Index), GenerateHash(GenerateHash) {
     // Save the start bit of the actual bitcode, in case there is space
     // saved at the start for the darwin header above. The reader stream
     // will start at the bitcode, and we need the offset of the VST
     // to line up.
     BitcodeStartBit = Stream.GetCurrentBitNo();
+
+    // Assign ValueIds to any callee values in the index that came from
+    // indirect call profiles and were recorded as a GUID not a Value*
+    // (which would have been assigned an ID by the ValueEnumerator).
+    // The starting ValueId is just after the number of values in the
+    // ValueEnumerator, so that they can be emitted in the VST.
+    GlobalValueId = VE.getValues().size();
+    if (Index)
+      for (const auto &GUIDSummaryLists : *Index)
+        // Examine all summaries for this GUID.
+        for (auto &Summary : GUIDSummaryLists.second)
+          if (auto FS = dyn_cast<FunctionSummary>(Summary.get()))
+            // For each call in the function summary, see if the call
+            // is to a GUID (which means it is for an indirect call,
+            // otherwise we would have a Value for it). If so, synthesize
+            // a value id.
+            for (auto &CallEdge : FS->calls())
+              if (CallEdge.first.isGUID())
+                assignValueId(CallEdge.first.getGUID());
   }
 
 private:
   /// Main entry point for writing a module to bitcode, invoked by
   /// BitcodeWriter::write() after it writes the header.
   void writeBlocks() override;
 
   /// Create the "IDENTIFICATION_BLOCK_ID" containing a single string with the
void writePerModuleFunctionSummaryRecord(SmallVector<uint64_t, 64> &NameVals,
                                            unsigned FSCallsAbbrev,
                                            unsigned FSCallsProfileAbbrev,
                                            const Function &F);
   void writeModuleLevelReferences(const GlobalVariable &V,
                                   SmallVector<uint64_t, 64> &NameVals,
                                   unsigned FSModRefsAbbrev);
   void writePerModuleGlobalValueSummary();
   void writeModuleHash(size_t BlockStartPos);
+
+  void assignValueId(GlobalValue::GUID ValGUID) {
+    GUIDToValueIdMap[ValGUID] = ++GlobalValueId;
+  }
+  unsigned getValueId(GlobalValue::GUID ValGUID) {
+    const auto &VMI = GUIDToValueIdMap.find(ValGUID);
+    assert(VMI != GUIDToValueIdMap.end());
+    return VMI->second;
+  }
+  // Helper to get the valueId for the type of value recorded in VI.
+  unsigned getValueId(ValueInfo VI) {
+    if (VI.isGUID())
+      return getValueId(VI.getGUID());
+    return VE.getValueID(VI.getValue());
+  }
+  std::map<GlobalValue::GUID, unsigned> &valueIds() { return GUIDToValueIdMap; }
 };
 
 /// Class to manage the bitcode writing for a combined index.
 class IndexBitcodeWriter : public BitcodeWriter {
   /// The combined index to write to bitcode.
   const ModuleSummaryIndex &Index;
 
   /// When writing a subset of the index for distributed backends, client
void ModuleBitcodeWriter::writeValueSymbolTable(
 
   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
 
   // For the module-level VST, add abbrev Ids for the VST_CODE_FNENTRY
   // records, which are not used in the per-function VSTs.
   unsigned FnEntry8BitAbbrev;
   unsigned FnEntry7BitAbbrev;
   unsigned FnEntry6BitAbbrev;
+  unsigned GUIDEntryAbbrev;
   if (IsModuleLevel && hasVSTOffsetPlaceholder()) {
     // 8-bit fixed-width VST_CODE_FNENTRY function strings.
     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // value id
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
if (IsModuleLevel && hasVSTOffsetPlaceholder()) {
     // 6-bit char6 VST_CODE_FNENTRY function strings.
     Abbv = new BitCodeAbbrev();
     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // value id
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
     FnEntry6BitAbbrev = Stream.EmitAbbrev(Abbv);
+
+    // FIXME: Change the name of this record as it is now used by
+    // the per-module index as well.
+    Abbv = new BitCodeAbbrev();
+    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_ENTRY));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // refguid
+    GUIDEntryAbbrev = Stream.EmitAbbrev(Abbv);
   }
 
   // FIXME: Set up the abbrev, we know how many values there are!
   // FIXME: We know if the type names can use 7-bit ascii.
-  SmallVector<unsigned, 64> NameVals;
+  SmallVector<uint64_t, 64> NameVals;
 
   for (const ValueName &Name : VST) {
     // Figure out the encoding to use for the name.
     StringEncoding Bits =
         getStringEncoding(Name.getKeyData(), Name.getKeyLength());
 
     unsigned AbbrevToUse = VST_ENTRY_8_ABBREV;
     NameVals.push_back(VE.getValueID(Name.getValue()));
for (const ValueName &Name : VST) {
 
     for (const auto P : Name.getKey())
       NameVals.push_back((unsigned char)P);
 
     // Emit the finished record.
     Stream.EmitRecord(Code, NameVals, AbbrevToUse);
     NameVals.clear();
   }
+  // Emit any GUID valueIDs created for indirect call edges into the
+  // module-level VST.
+  if (IsModuleLevel && hasVSTOffsetPlaceholder())
+    for (const auto &GI : valueIds()) {
+      NameVals.push_back(GI.second);
+      NameVals.push_back(GI.first);
+      Stream.EmitRecord(bitc::VST_CODE_COMBINED_ENTRY, NameVals,
+                        GUIDEntryAbbrev);
+      NameVals.clear();
+    }
   Stream.ExitBlock();
 }
 
 /// Emit function names and summary offsets for the combined index
 /// used by ThinLTO.
 void IndexBitcodeWriter::writeCombinedValueSymbolTable() {
   assert(hasVSTOffsetPlaceholder() && "Expected non-zero VSTOffsetPlaceholder");
   // Get the offset of the VST we are writing, and backpatch it into
void ModuleBitcodeWriter::writePerModuleFunctionSummaryRecord(
   // Sort the refs for determinism output, the vector returned by FS->refs() has
   // been initialized from a DenseSet.
   std::sort(NameVals.begin() + SizeBeforeRefs, NameVals.end());
 
   std::vector<FunctionSummary::EdgeTy> Calls = FS->calls();
   std::sort(Calls.begin(), Calls.end(),
             [this](const FunctionSummary::EdgeTy &L,
                    const FunctionSummary::EdgeTy &R) {
-              return VE.getValueID(L.first.getValue()) <
-                     VE.getValueID(R.first.getValue());
+              return getValueId(L.first) < getValueId(R.first);
             });
   bool HasProfileData = F.getEntryCount().hasValue();
   for (auto &ECI : Calls) {
-    NameVals.push_back(VE.getValueID(ECI.first.getValue()));
+    NameVals.push_back(getValueId(ECI.first));
     assert(ECI.second.CallsiteCount > 0 && "Expected at least one callsite");
     NameVals.push_back(ECI.second.CallsiteCount);
     if (HasProfileData)
       NameVals.push_back(ECI.second.ProfileCount);
   }
 
   unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
   unsigned Code =

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

if (!DisableUnitAtATime) {
     addExtensionsToPM(EP_Peephole, MPM);
     MPM.add(createCFGSimplificationPass()); // Clean up after IPCP & DAE
   }
 
   if (!PerformThinLTO) {
     /// PGO instrumentation is added during the compile phase for ThinLTO, do
     /// not run it a second time
     addPGOInstrPasses(MPM);
-    // Indirect call promotion that promotes intra-module targets only.
-    MPM.add(createPGOIndirectCallPromotionLegacyPass());
-  }
+  }
+
 
   if (EnableNonLTOGlobalsModRef)
     // We add a module alias analysis pass here. In part due to bugs in the
     // analysis infrastructure this "works" in that the analysis stays alive
     // for the entire SCC pass run below.
     MPM.add(createGlobalsAAWrapperPass());
 
   // Start of CallGraph SCC passes.

llvm/trunk/test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @a() {
+entry:
+  ret void
+}

llvm/trunk/test/Transforms/PGOProfile/thinlto_indirect_call_promotion.ll

+; Do setup work for all below tests: generate bitcode and combined index
+; RUN: opt -module-summary %s -o %t.bc
+; RUN: opt -module-summary %p/Inputs/thinlto_indirect_call_promotion.ll -o %t2.bc
+; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
+
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -o %t4.bc -print-imports 2>&1 | FileCheck %s --check-prefix=IMPORTS
+; IMPORTS: Import a
+
+; RUN: opt %t4.bc -pgo-icall-prom -S -icp-count-threshold=1 | FileCheck %s --check-prefix=ICALL-PROM
+; RUN: opt %t4.bc -pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=1 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
+; PASS-REMARK: Promote indirect call to a with count 1 out of 1
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@foo = external local_unnamed_addr global void ()*, align 8
+
+define i32 @main() local_unnamed_addr {
+entry:
+  %0 = load void ()*, void ()** @foo, align 8
+; ICALL-PROM:   br i1 %{{[0-9]+}}, label %if.true.direct_targ, label %if.false.orig_indirect, !prof [[BRANCH_WEIGHT:![0-9]+]]
+  tail call void %0(), !prof !1
+  ret i32 0
+}
+
+!1 = !{!"VP", i32 0, i64 1, i64 -6289574019528802036, i64 1}
+
+; Should not have a VP annotation on new indirect call (check before and after
+; branch_weights annotation).
+; ICALL-PROM-NOT: !"VP"
+; ICALL-PROM: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 1, i32 0}
+; ICALL-PROM-NOT: !"VP"