[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

This is a duplicate.

lib/Analysis/ModuleSummaryAnalysis.cpp

99

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

104

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

lib/Bitcode/Writer/BitcodeWriter.cpp

151

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

Alternatively, using explicit name for iterator variable can help.

lib/Transforms/IPO/PassManagerBuilder.cpp

413

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

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

lib/Analysis/ModuleSummaryAnalysis.cpp

99

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

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

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

lib/Transforms/IPO/PassManagerBuilder.cpp

413

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

413

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

Add a one line comment for this code block?

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll

4–5

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

Will do.

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll

4–5

You're right, this is unnecessary. Removed.

[tejohnson]

• Address latest comments.

[Prazek]

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

150 ↗

(On Diff #64255)

early exit here will reduce indentation

151–161 ↗

(On Diff #64255)

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 ↗

(On Diff #64255)

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

2858–2862 ↗

(On Diff #64255)

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 ↗

(On Diff #64255)

ok

151–161 ↗

(On Diff #64255)

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

295–297 ↗

(On Diff #64255)

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 ↗

(On Diff #64255)

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 ↗

(On Diff #64255)

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 ↗

(On Diff #64255)

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

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

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;

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 =

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.

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
+}

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"