IR: Eliminate non-determinism in the module summary analysis.

[pcc]

Summary

Also make the summary ref and call graph vectors immutable. This means
a smaller API surface and fewer places to audit for non-determinism.

[mehdi_amini]

llvm/include/llvm/IR/ModuleSummaryIndex.h

45 ↗

(On Diff #81833)

The comment is outdated: IndirectCalls in per-module index are GUID-based.

175 ↗

(On Diff #81833)

I didn't know about OwningArrayRef, interesting.
What is the advantage over a const std::vector ?

180 ↗

(On Diff #81833)

It seems to me that this is causing memory allocation and copy that could be avoided: because Refs is an ArrayRef we're allocating and copying into RefEdgeList. However looking at call site, if Refs comes from makeRefList we just created a vector there. If it comes from findRefEdges we just created a SetVector.

In both cases it looks like we could take and store a std::vector that would be moved in.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

92 ↗

(On Diff #81833)

Fusing these looks much more sane!

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

4798 ↗

(On Diff #81833)

Ret.reserve( Record.size());

4806 ↗

(On Diff #81833)

Ret.reserve( Record.size());

[tejohnson]

This looks like a good cleanup. One minor suggestion below. I see Mehdi just responded with a couple of suggestions, so will hold off on accepting for now.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

138 ↗

(On Diff #81833)

CalleeId doesn't seem like the best name anymore. Just "Callee"?

[pcc]

• Address review comments

llvm/include/llvm/IR/ModuleSummaryIndex.h

175 ↗

(On Diff #81833)

I guess it saves us a pointer as well as the additional space reserved by the std::vector, since the size is fixed. I haven't measured how important this is in practice, though.

180 ↗

(On Diff #81833)

I guess there's one way that saves copies and another that saves memory. In the absence of evidence pointing one way or the other, I'd be inclined to go with the slightly simpler approach, i.e. the one I took.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

138 ↗

(On Diff #81833)

I folded it into the only use.

[mehdi_amini]

llvm/include/llvm/IR/ModuleSummaryIndex.h

175 ↗

(On Diff #81833)

Oh makes sense! There is no "capacity" so you save a pointer (2 instead of 3).

180 ↗

(On Diff #81833)

It is not clear to me why you think that "not simply using std::vector everywhere" is simpler though?

This means hitting the heap a lot without good reason (that I perceive right now), which we traditionally avoid as much as possible I believe (reusing SmallVector across records in the BitcodeReader for example). Because of that it does not seem "one way or another to me": adding this extra malloc/free/copy sequence for saving a pointer should be motivated.

(And I just saved 8B for this structure in D27970, if memory was a concern we would have started with this)

[pcc]

llvm/include/llvm/IR/ModuleSummaryIndex.h

180 ↗

(On Diff #81833)

It is not clear to me why you think that "not simply using std::vector everywhere" is simpler though?

To avoid the copy we'd need to add a way to move the std::vector out of MapVector/SetVector. Not a big deal but it would make the interface for those classes a little more complicated.

This means hitting the heap a lot without good reason (that I perceive right now), which we traditionally avoid as much as possible I believe (reusing SmallVector across records in the BitcodeReader for example). Because of that it does not seem "one way or another to me": adding this extra malloc/free/copy sequence for saving a pointer should be motivated.

I'd say that copying the vector is the "default position" as it wouldn't require more API surface in MapVector/SetVector. It's also the status quo as we were effectively copying the data structure in using add*Edges before.

And while we're copying the vector we might as well use a slightly better data structure here.

But I can see how using OwningArrayRef here could be seen as taking a position on whether the memory savings are worth it, which I don't (see also other thread), so I guess I don't have a problem with moving the vector.

[pcc]

• Micro optimize our memory allocations

[mehdi_amini]

LGTM. Thanks.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

176 ↗

(On Diff #82132)

takeVector()?

llvm/trunk/include/llvm/ADT/MapVector.h

class MapVector {
   VectorType Vector;
 
 public:
   typedef typename VectorType::iterator iterator;
   typedef typename VectorType::const_iterator const_iterator;
   typedef typename VectorType::reverse_iterator reverse_iterator;
   typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
 
-  ArrayRef<value_type> getArrayRef() const { return Vector; }
+  /// Clear the MapVector and return the underlying vector.
+  VectorType takeVector() {
+    Map.clear();
+    return std::move(Vector);
+  }
 
   size_type size() const { return Vector.size(); }
 
   iterator begin() { return Vector.begin(); }
   const_iterator begin() const { return Vector.begin(); }
   iterator end() { return Vector.end(); }
   const_iterator end() const { return Vector.end(); }
 

llvm/trunk/include/llvm/ADT/SetVector.h

public:
   /// \brief Initialize a SetVector with a range of elements
   template<typename It>
   SetVector(It Start, It End) {
     insert(Start, End);
   }
 
   ArrayRef<T> getArrayRef() const { return vector_; }
 
+  /// Clear the SetVector and return the underlying vector.
+  Vector takeVector() {
+    set_.clear();
+    return std::move(vector_);
+  }
+
   /// \brief Determine if the SetVector is empty or not.
   bool empty() const {
     return vector_.empty();
   }
 
   /// \brief Determine the number of elements in the SetVector.
   size_type size() const {
     return vector_.size();

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

struct CalleeInfo {
   CalleeInfo() = default;
   explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
 
   void updateHotness(const HotnessType OtherHotness) {
     Hotness = std::max(Hotness, OtherHotness);
   }
 };
 
-/// Struct to hold value either by GUID or Value*, depending on whether this
-/// is a combined or per-module index, respectively.
+/// Struct to hold value either by GUID or GlobalValue*. Values in combined
+/// indexes as well as indirect calls are GUIDs, all others are GlobalValues.
 struct ValueInfo {
   /// The value representation used in this instance.
   enum ValueInfoKind {
     VI_GUID,
     VI_Value,
   };
 
   /// Union of the two possible value types.
   union ValueUnion {
     GlobalValue::GUID Id;
-    const Value *V;
+    const GlobalValue *GV;
     ValueUnion(GlobalValue::GUID Id) : Id(Id) {}
-    ValueUnion(const Value *V) : V(V) {}
+    ValueUnion(const GlobalValue *GV) : GV(GV) {}
   };
 
   /// The value being represented.
   ValueUnion TheValue;
   /// The value representation.
   ValueInfoKind Kind;
   /// Constructor for a GUID value
   ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {}
-  /// Constructor for a Value* value
-  ValueInfo(const Value *V) : TheValue(V), Kind(VI_Value) {}
+  /// Constructor for a GlobalValue* value
+  ValueInfo(const GlobalValue *V) : TheValue(V), Kind(VI_Value) {}
   /// Accessor for GUID value
   GlobalValue::GUID getGUID() const {
     assert(Kind == VI_GUID && "Not a GUID type");
     return TheValue.Id;
   }
-  /// Accessor for Value* value
-  const Value *getValue() const {
+  /// Accessor for GlobalValue* value
+  const GlobalValue *getValue() const {
     assert(Kind == VI_Value && "Not a Value type");
-    return TheValue.V;
+    return TheValue.GV;
   }
   bool isGUID() const { return Kind == VI_GUID; }
 };
 
+template <> struct DenseMapInfo<ValueInfo> {
+  static inline ValueInfo getEmptyKey() { return ValueInfo((GlobalValue *)-1); }
+  static inline ValueInfo getTombstoneKey() {
+    return ValueInfo((GlobalValue *)-2);
+  }
+  static bool isEqual(ValueInfo L, ValueInfo R) {
+    if (L.isGUID() != R.isGUID())
+      return false;
+    return L.isGUID() ? (L.getGUID() == R.getGUID())
+                      : (L.getValue() == R.getValue());
+  }
+  static unsigned getHashValue(ValueInfo I) {
+    return I.isGUID() ? I.getGUID() : (uintptr_t)I.getValue();
+  }
+};
+
 /// \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 };
 
   /// Group flags (Linkage, noRename, isOptSize, etc.) as a bitfield.
private:
   /// List of values referenced by this global value's definition
   /// (either by the initializer of a global variable, or referenced
   /// from within a function). This does not include functions called, which
   /// are listed in the derived FunctionSummary object.
   std::vector<ValueInfo> RefEdgeList;
 
 protected:
   /// GlobalValueSummary constructor.
-  GlobalValueSummary(SummaryKind K, GVFlags Flags) : Kind(K), Flags(Flags) {}
+  GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
+      : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {}
 
 public:
   virtual ~GlobalValueSummary() = default;
 
   /// Returns the hash of the original name, it is identical to the GUID for
   /// externally visible symbols, but not for local ones.
   GlobalValue::GUID getOriginalName() { return OriginalName; }
 
public:
   }
 
   /// Flag that this global value possibly references another value that
   /// can't be renamed.
   void setHasInlineAsmMaybeReferencingInternal() {
     Flags.HasInlineAsmMaybeReferencingInternal = true;
   }
 
-  /// Record a reference from this global value to the global value identified
-  /// by \p RefGUID.
-  void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); }
-
-  /// Record a reference from this global value to the global value identified
-  /// by \p RefV.
-  void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); }
-
-  /// Record a reference from this global value to each global value identified
-  /// in \p RefEdges.
-  void addRefEdges(DenseSet<const Value *> &RefEdges) {
-    for (auto &RI : RefEdges)
-      addRefEdge(RI);
-  }
-
   /// Return the list of values referenced by this global value definition.
-  std::vector<ValueInfo> &refs() { return RefEdgeList; }
-  const std::vector<ValueInfo> &refs() const { return RefEdgeList; }
+  ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
 };
 
 /// \brief Alias summary information.
 class AliasSummary : public GlobalValueSummary {
   GlobalValueSummary *AliaseeSummary;
 
 public:
   /// Summary constructors.
-  AliasSummary(GVFlags Flags) : GlobalValueSummary(AliasKind, Flags) {}
+  AliasSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
+      : GlobalValueSummary(AliasKind, Flags, std::move(Refs)) {}
 
   /// Check if this is an alias summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == AliasKind;
   }
 
   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
 
private:
   /// during the initial compile step when the summary index is first built.
   unsigned InstCount;
 
   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
   std::vector<EdgeTy> CallGraphEdgeList;
 
 public:
   /// Summary constructors.
-  FunctionSummary(GVFlags Flags, unsigned NumInsts)
-      : GlobalValueSummary(FunctionKind, Flags), InstCount(NumInsts) {}
+  FunctionSummary(GVFlags Flags, unsigned NumInsts, std::vector<ValueInfo> Refs,
+                  std::vector<EdgeTy> CGEdges)
+      : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
+        InstCount(NumInsts), CallGraphEdgeList(std::move(CGEdges)) {}
 
   /// Check if this is a function summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == FunctionKind;
   }
 
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
-  /// 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
-  /// in \p CallGraphEdges.
-  void addCallGraphEdges(DenseMap<const Value *, CalleeInfo> &CallGraphEdges) {
-    for (auto &EI : CallGraphEdges)
-      addCallGraphEdge(EI.first, EI.second);
-  }
-
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
-  std::vector<EdgeTy> &calls() { return CallGraphEdgeList; }
-  const std::vector<EdgeTy> &calls() const { return CallGraphEdgeList; }
+  ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 };
 
 /// \brief Global variable summary information to aid decisions and
 /// implementation of importing.
 ///
 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
 /// but is a placeholder as additional info may be added to the summary
 /// for variables.
 class GlobalVarSummary : public GlobalValueSummary {
 
 public:
   /// Summary constructors.
-  GlobalVarSummary(GVFlags Flags) : GlobalValueSummary(GlobalVarKind, Flags) {}
+  GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
+      : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
 
   /// Check if this is a global variable summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == GlobalVarKind;
   }
 };
 
 /// 160 bits SHA1

llvm/trunk/lib/Analysis/ModuleSummaryAnalysis.cpp

 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass builds a ModuleSummaryIndex object for the module, to be written
 // to bitcode or LLVM assembly.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Triple.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/Analysis/ProfileSummaryInfo.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/Object/IRObjectFile.h"
 #include "llvm/Pass.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "module-summary-analysis"
 
 // Walk through the operands of a given User via worklist iteration and populate
 // the set of GlobalValue references encountered. Invoked either on an
 // Instruction or a GlobalVariable (which walks its initializer).
-static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges,
+static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges,
                          SmallPtrSet<const User *, 8> &Visited) {
   SmallVector<const User *, 32> Worklist;
   Worklist.push_back(CurUser);
 
   while (!Worklist.empty()) {
     const User *U = Worklist.pop_back_val();
 
     if (!Visited.insert(U).second)
       continue;
 
     ImmutableCallSite CS(U);
 
     for (const auto &OI : U->operands()) {
       const User *Operand = dyn_cast<User>(OI);
       if (!Operand)
         continue;
       if (isa<BlockAddress>(Operand))
         continue;
-      if (isa<GlobalValue>(Operand)) {
+      if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
         // We have a reference to a global value. This should be added to
         // the reference set unless it is a callee. Callees are handled
         // specially by WriteFunction and are added to a separate list.
         if (!(CS && CS.isCallee(&OI)))
-          RefEdges.insert(Operand);
+          RefEdges.insert(GV);
         continue;
       }
       Worklist.push_back(Operand);
     }
   }
 }
 
 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
                                    bool HasLocalsInUsed) {
   // Summary not currently supported for anonymous functions, they should
   // have been named.
   assert(F.hasName());
 
   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;
+  MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
+  SetVector<ValueInfo> RefEdges;
   ICallPromotionAnalysis ICallAnalysis;
 
   bool HasInlineAsmMaybeReferencingInternal = false;
   SmallPtrSet<const User *, 8> Visited;
   for (const BasicBlock &BB : F)
     for (const Instruction &I : BB) {
       if (isa<DbgInfoIntrinsic>(I))
         continue;
for (const Instruction &I : BB) {
       // Check if this is a direct call to a known function.
       if (CalledFunction) {
         // Skip intrinsics.
         if (CalledFunction->isIntrinsic())
           continue;
         // We should have named any anonymous globals
         assert(CalledFunction->hasName());
         auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
+        auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
+                                   : CalleeInfo::HotnessType::Unknown;
+
         // Use the original CalledValue, in case it was an alias. We want
         // to record the call edge to the alias in that case. Eventually
         // an alias summary will be created to associate the alias and
         // aliasee.
-        auto *CalleeId =
-            M.getValueSymbolTable().lookup(CalledValue->getName());
-
-        auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
-                                   : CalleeInfo::HotnessType::Unknown;
-        CallGraphEdges[CalleeId].updateHotness(Hotness);
+        CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
       } else {
         // Skip inline assembly calls.
         if (CI && CI->isInlineAsm())
           continue;
         // Skip direct calls.
         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
           continue;
 
         uint32_t NumVals, NumCandidates;
         uint64_t TotalCount;
         auto CandidateProfileData =
             ICallAnalysis.getPromotionCandidatesForInstruction(
                 &I, NumVals, TotalCount, NumCandidates);
         for (auto &Candidate : CandidateProfileData)
-          IndirectCallEdges[Candidate.Value].updateHotness(
+          CallGraphEdges[Candidate.Value].updateHotness(
               getHotness(Candidate.Count, PSI));
       }
     }
 
   GlobalValueSummary::GVFlags Flags(F);
-  std::unique_ptr<FunctionSummary> FuncSummary =
-      llvm::make_unique<FunctionSummary>(Flags, NumInsts);
-  FuncSummary->addCallGraphEdges(CallGraphEdges);
-  FuncSummary->addCallGraphEdges(IndirectCallEdges);
-  FuncSummary->addRefEdges(RefEdges);
+  auto FuncSummary = llvm::make_unique<FunctionSummary>(
+      Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector());
   if (HasInlineAsmMaybeReferencingInternal)
     FuncSummary->setHasInlineAsmMaybeReferencingInternal();
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 static void computeVariableSummary(ModuleSummaryIndex &Index,
                                    const GlobalVariable &V) {
-  DenseSet<const Value *> RefEdges;
+  SetVector<ValueInfo> RefEdges;
   SmallPtrSet<const User *, 8> Visited;
   findRefEdges(&V, RefEdges, Visited);
   GlobalValueSummary::GVFlags Flags(V);
-  std::unique_ptr<GlobalVarSummary> GVarSummary =
-      llvm::make_unique<GlobalVarSummary>(Flags);
-  GVarSummary->addRefEdges(RefEdges);
+  auto GVarSummary =
+      llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
 }
 
 static void computeAliasSummary(ModuleSummaryIndex &Index,
                                 const GlobalAlias &A) {
   GlobalValueSummary::GVFlags Flags(A);
-  std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags);
+  auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
   auto *Aliasee = A.getBaseObject();
   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
   AS->setAliasee(AliaseeSummary);
   Index.addGlobalValueSummary(A.getName(), std::move(AS));
 }
 
 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
ModuleSymbolTable::CollectAsmSymbols(
           GlobalValueSummary::GVFlags GVFlags(
               GlobalValue::InternalLinkage,
               /* NoRename */ true,
               /* HasInlineAsmMaybeReferencingInternal */ false,
               /* IsNotViableToInline */ true);
           // Create the appropriate summary type.
           if (isa<Function>(GV)) {
             std::unique_ptr<FunctionSummary> Summary =
-                llvm::make_unique<FunctionSummary>(GVFlags, 0);
+                llvm::make_unique<FunctionSummary>(
+                    GVFlags, 0, ArrayRef<ValueInfo>{},
+                    ArrayRef<FunctionSummary::EdgeTy>{});
             Summary->setNoRename();
             Index.addGlobalValueSummary(Name, std::move(Summary));
           } else {
             std::unique_ptr<GlobalVarSummary> Summary =
-                llvm::make_unique<GlobalVarSummary>(GVFlags);
+                llvm::make_unique<GlobalVarSummary>(GVFlags,
+                                                    ArrayRef<ValueInfo>{});
             Summary->setNoRename();
             Index.addGlobalValueSummary(Name, std::move(Summary));
           }
         });
   }
 
   return Index;
 }

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

ModuleSummaryIndexBitcodeReader(
       BitstreamCursor Stream, ModuleSummaryIndex &TheIndex);
 
   Error parseModule(StringRef ModulePath);
 
 private:
   Error parseValueSymbolTable(
       uint64_t Offset,
       DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap);
+  std::vector<ValueInfo> makeRefList(ArrayRef<uint64_t> Record);
+  std::vector<FunctionSummary::EdgeTy> makeCallList(ArrayRef<uint64_t> Record,
+                                                    bool IsOldProfileFormat,
+                                                    bool HasProfile);
   Error parseEntireSummary(StringRef ModulePath);
   Error parseModuleStringTable();
-  std::pair<GlobalValue::GUID, GlobalValue::GUID>
 
+  std::pair<GlobalValue::GUID, GlobalValue::GUID>
   getGUIDFromValueId(unsigned ValueId);
-  std::pair<GlobalValue::GUID, CalleeInfo::HotnessType>
-  readCallGraphEdge(const SmallVector<uint64_t, 64> &Record, unsigned int &I,
-                    bool IsOldProfileFormat, bool HasProfile);
 };
 
 } // end anonymous namespace
 
 std::error_code llvm::errorToErrorCodeAndEmitErrors(LLVMContext &Ctx,
                                                     Error Err) {
   if (Err) {
     std::error_code EC;
case BitstreamEntry::Record: {
         }
         }
       }
       continue;
     }
   }
 }
 
+std::vector<ValueInfo>
+ModuleSummaryIndexBitcodeReader::makeRefList(ArrayRef<uint64_t> Record) {
+  std::vector<ValueInfo> Ret;
+  Ret.reserve(Record.size());
+  for (uint64_t RefValueId : Record)
+    Ret.push_back(getGUIDFromValueId(RefValueId).first);
+  return Ret;
+}
+
+std::vector<FunctionSummary::EdgeTy> ModuleSummaryIndexBitcodeReader::makeCallList(
+    ArrayRef<uint64_t> Record, bool IsOldProfileFormat, bool HasProfile) {
+  std::vector<FunctionSummary::EdgeTy> Ret;
+  Ret.reserve(Record.size());
+  for (unsigned I = 0, E = Record.size(); I != E; ++I) {
+    CalleeInfo::HotnessType Hotness = CalleeInfo::HotnessType::Unknown;
+    GlobalValue::GUID CalleeGUID = getGUIDFromValueId(Record[I]).first;
+    if (IsOldProfileFormat) {
+      I += 1; // Skip old callsitecount field
+      if (HasProfile)
+        I += 1; // Skip old profilecount field
+    } else if (HasProfile)
+      Hotness = static_cast<CalleeInfo::HotnessType>(Record[++I]);
+    Ret.push_back(FunctionSummary::EdgeTy{CalleeGUID, CalleeInfo{Hotness}});
+  }
+  return Ret;
+}
+
 // Eagerly parse the entire summary block. This populates the GlobalValueSummary
 // objects in the index.
 Error ModuleSummaryIndexBitcodeReader::parseEntireSummary(
     StringRef ModulePath) {
   if (Stream.EnterSubBlock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID))
     return error("Invalid record");
   SmallVector<uint64_t, 64> Record;
 
while (true) {
     //                        n x (valueid, hotness)]
     case bitc::FS_PERMODULE:
     case bitc::FS_PERMODULE_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       unsigned InstCount = Record[2];
       unsigned NumRefs = Record[3];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<FunctionSummary> FS =
-          llvm::make_unique<FunctionSummary>(Flags, InstCount);
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
-      FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first());
       static int RefListStartIndex = 4;
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
-      for (unsigned I = 4, E = CallGraphEdgeStartIndex; I != E; ++I) {
-        unsigned RefValueId = Record[I];
-        GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first;
-        FS->addRefEdge(RefGUID);
-      }
+      std::vector<ValueInfo> Refs = makeRefList(
+          ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE);
-      for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E;
-           ++I) {
-        CalleeInfo::HotnessType Hotness;
-        GlobalValue::GUID CalleeGUID;
-        std::tie(CalleeGUID, Hotness) =
-            readCallGraphEdge(Record, I, IsOldProfileFormat, HasProfile);
-        FS->addCallGraphEdge(CalleeGUID, CalleeInfo(Hotness));
-      }
+      std::vector<FunctionSummary::EdgeTy> Calls = makeCallList(
+          ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
+          IsOldProfileFormat, HasProfile);
+      auto FS = llvm::make_unique<FunctionSummary>(
+          Flags, InstCount, std::move(Refs), std::move(Calls));
       auto GUID = getGUIDFromValueId(ValueID);
+      FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first());
       FS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
       break;
     }
     // FS_ALIAS: [valueid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_PERMODULE entries, as
     // they expect all aliasee summaries to be available.
     case bitc::FS_ALIAS: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       unsigned AliaseeID = Record[2];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags);
+      auto AS =
+          llvm::make_unique<AliasSummary>(Flags, std::vector<ValueInfo>{});
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
       AS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first());
 
       GlobalValue::GUID AliaseeGUID = getGUIDFromValueId(AliaseeID).first;
       auto *AliaseeSummary = TheIndex.getGlobalValueSummary(AliaseeGUID);
       if (!AliaseeSummary)
         return error("Alias expects aliasee summary to be parsed");
       AS->setAliasee(AliaseeSummary);
 
       auto GUID = getGUIDFromValueId(ValueID);
       AS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(AS));
       break;
     }
     // FS_PERMODULE_GLOBALVAR_INIT_REFS: [valueid, flags, n x valueid]
     case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<GlobalVarSummary> FS =
-          llvm::make_unique<GlobalVarSummary>(Flags);
+      std::vector<ValueInfo> Refs =
+          makeRefList(ArrayRef<uint64_t>(Record).slice(2));
+      auto FS = llvm::make_unique<GlobalVarSummary>(Flags, std::move(Refs));
       FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first());
-      for (unsigned I = 2, E = Record.size(); I != E; ++I) {
-        unsigned RefValueId = Record[I];
-        GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first;
-        FS->addRefEdge(RefGUID);
-      }
       auto GUID = getGUIDFromValueId(ValueID);
       FS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
       break;
     }
     // FS_COMBINED: [valueid, modid, flags, instcount, numrefs,
     //               numrefs x valueid, n x (valueid)]
     // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, numrefs,
     //                       numrefs x valueid, n x (valueid, hotness)]
     case bitc::FS_COMBINED:
     case bitc::FS_COMBINED_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       unsigned InstCount = Record[3];
       unsigned NumRefs = Record[4];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<FunctionSummary> FS =
-          llvm::make_unique<FunctionSummary>(Flags, InstCount);
-      LastSeenSummary = FS.get();
-      FS->setModulePath(ModuleIdMap[ModuleId]);
       static int RefListStartIndex = 5;
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
-      for (unsigned I = RefListStartIndex, E = CallGraphEdgeStartIndex; I != E;
-           ++I) {
-        unsigned RefValueId = Record[I];
-        GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first;
-        FS->addRefEdge(RefGUID);
-      }
+      std::vector<ValueInfo> Refs = makeRefList(
+          ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
-      for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E;
-           ++I) {
-        CalleeInfo::HotnessType Hotness;
-        GlobalValue::GUID CalleeGUID;
-        std::tie(CalleeGUID, Hotness) =
-            readCallGraphEdge(Record, I, IsOldProfileFormat, HasProfile);
-        FS->addCallGraphEdge(CalleeGUID, CalleeInfo(Hotness));
-      }
+      std::vector<FunctionSummary::EdgeTy> Edges = makeCallList(
+          ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
+          IsOldProfileFormat, HasProfile);
       GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
+      auto FS = llvm::make_unique<FunctionSummary>(
+          Flags, InstCount, std::move(Refs), std::move(Edges));
+      LastSeenSummary = FS.get();
+      FS->setModulePath(ModuleIdMap[ModuleId]);
       TheIndex.addGlobalValueSummary(GUID, std::move(FS));
       Combined = true;
       break;
     }
     // FS_COMBINED_ALIAS: [valueid, modid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_COMBINED entries, as
     // they expect all aliasee summaries to be available.
     case bitc::FS_COMBINED_ALIAS: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       unsigned AliaseeValueId = Record[3];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags);
+      auto AS = llvm::make_unique<AliasSummary>(Flags, std::vector<ValueInfo>{});
       LastSeenSummary = AS.get();
       AS->setModulePath(ModuleIdMap[ModuleId]);
 
       auto AliaseeGUID = getGUIDFromValueId(AliaseeValueId).first;
       auto AliaseeInModule =
           TheIndex.findSummaryInModule(AliaseeGUID, AS->modulePath());
       if (!AliaseeInModule)
         return error("Alias expects aliasee summary to be parsed");
       AS->setAliasee(AliaseeInModule);
 
       GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
       TheIndex.addGlobalValueSummary(GUID, std::move(AS));
       Combined = true;
       break;
     }
     // FS_COMBINED_GLOBALVAR_INIT_REFS: [valueid, modid, flags, n x valueid]
     case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      std::unique_ptr<GlobalVarSummary> FS =
-          llvm::make_unique<GlobalVarSummary>(Flags);
+      std::vector<ValueInfo> Refs =
+          makeRefList(ArrayRef<uint64_t>(Record).slice(3));
+      auto FS = llvm::make_unique<GlobalVarSummary>(Flags, std::move(Refs));
       LastSeenSummary = FS.get();
       FS->setModulePath(ModuleIdMap[ModuleId]);
-      for (unsigned I = 3, E = Record.size(); I != E; ++I) {
-        unsigned RefValueId = Record[I];
-        GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first;
-        FS->addRefEdge(RefGUID);
-      }
       GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
       TheIndex.addGlobalValueSummary(GUID, std::move(FS));
       Combined = true;
       break;
     }
     // FS_COMBINED_ORIGINAL_NAME: [original_name]
     case bitc::FS_COMBINED_ORIGINAL_NAME: {
       uint64_t OriginalName = Record[0];
       if (!LastSeenSummary)
         return error("Name attachment that does not follow a combined record");
       LastSeenSummary->setOriginalName(OriginalName);
       // Reset the LastSeenSummary
       LastSeenSummary = nullptr;
     }
     }
   }
   llvm_unreachable("Exit infinite loop");
 }
 
-std::pair<GlobalValue::GUID, CalleeInfo::HotnessType>
-ModuleSummaryIndexBitcodeReader::readCallGraphEdge(
-    const SmallVector<uint64_t, 64> &Record, unsigned int &I,
-    const bool IsOldProfileFormat, const bool HasProfile) {
-
-  auto Hotness = CalleeInfo::HotnessType::Unknown;
-  unsigned CalleeValueId = Record[I];
-  GlobalValue::GUID CalleeGUID = getGUIDFromValueId(CalleeValueId).first;
-  if (IsOldProfileFormat) {
-    I += 1; // Skip old callsitecount field
-    if (HasProfile)
-      I += 1; // Skip old profilecount field
-  } else if (HasProfile)
-    Hotness = static_cast<CalleeInfo::HotnessType>(Record[++I]);
-  return {CalleeGUID, Hotness};
-}
-
 // Parse the  module string table block into the Index.
 // This populates the ModulePathStringTable map in the index.
 Error ModuleSummaryIndexBitcodeReader::parseModuleStringTable() {
   if (Stream.EnterSubBlock(bitc::MODULE_STRTAB_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 

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

void ModuleBitcodeWriter::writePerModuleFunctionSummaryRecord(
     const Function &F) {
   NameVals.push_back(ValueID);
 
   FunctionSummary *FS = cast<FunctionSummary>(Summary);
   NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
   NameVals.push_back(FS->instCount());
   NameVals.push_back(FS->refs().size());
 
-  unsigned SizeBeforeRefs = NameVals.size();
   for (auto &RI : FS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
-  // 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 getValueId(L.first) < getValueId(R.first);
-            });
   bool HasProfileData = F.getEntryCount().hasValue();
-  for (auto &ECI : Calls) {
+  for (auto &ECI : FS->calls()) {
     NameVals.push_back(getValueId(ECI.first));
     if (HasProfileData)
       NameVals.push_back(static_cast<uint8_t>(ECI.second.Hotness));
   }
 
   unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
   unsigned Code =
       (HasProfileData ? bitc::FS_PERMODULE_PROFILE : bitc::FS_PERMODULE);

llvm/trunk/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll

 ; Test to check the callgraph in summary when there is PGO
 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
 ; RUN: opt -module-summary %p/Inputs/thinlto-function-summary-callgraph-profile-summary.ll -o %t2.o
 ; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o
 ; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
 
 
 ; CHECK-LABEL:       <GLOBALVAL_SUMMARY_BLOCK
 ; CHECK-NEXT:    <VERSION
 ; See if the call to func is registered, using the expected callsite count
 ; and profile count, with value id matching the subsequent value symbol table.
-; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=[[HOT1:.*]] op5=3 op6=[[HOT2:.*]] op7=3 op8=[[HOT3:.*]] op9=3 op10=[[COLD:.*]] op11=1 op12=[[NONE1:.*]] op13=2 op14=[[NONE2:.*]] op15=2 op16=[[NONE3:.*]] op17=2/>
+; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=[[HOT1:.*]] op5=3 op6=[[COLD:.*]] op7=1 op8=[[HOT2:.*]] op9=3 op10=[[NONE1:.*]] op11=2 op12=[[HOT3:.*]] op13=3 op14=[[NONE2:.*]] op15=2 op16=[[NONE3:.*]] op17=2/>
 ; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; CHECK-LABEL:  <VALUE_SYMTAB
 ; CHECK-NEXT:       <FNENTRY {{.*}} record string = 'hot_function
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE1]] {{.*}} record string = 'none1'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[COLD]] {{.*}} record string = 'cold'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE2]] {{.*}} record string = 'none2'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE3]] {{.*}} record string = 'none3'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT1]] {{.*}} record string = 'hot1'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT2]] {{.*}} record string = 'hot2'
 ; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT3]] {{.*}} record string = 'hot3'
 ; CHECK-LABEL:  </VALUE_SYMTAB>
 
 ; COMBINED:       <GLOBALVAL_SUMMARY_BLOCK
 ; COMBINED-NEXT:    <VERSION
 ; COMBINED-NEXT:    <COMBINED abbrevid=
 ; COMBINED-NEXT:    <COMBINED abbrevid=
 ; COMBINED-NEXT:    <COMBINED abbrevid=
 ; COMBINED-NEXT:    <COMBINED abbrevid=
 ; COMBINED-NEXT:    <COMBINED abbrevid=
 ; COMBINED-NEXT:    <COMBINED abbrevid=
-; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op5=[[HOT1:.*]] op6=3 op7=[[HOT2:.*]] op8=3 op9=[[HOT3:.*]] op10=3 op11=[[COLD:.*]] op12=1 op13=[[NONE1:.*]] op14=2 op15=[[NONE2:.*]] op16=2 op17=[[NONE3:.*]] op18=2/>
+; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op5=[[HOT1:.*]] op6=3 op7=[[COLD:.*]] op8=1 op9=[[HOT2:.*]] op10=3 op11=[[NONE1:.*]] op12=2 op13=[[HOT3:.*]] op14=3 op15=[[NONE2:.*]] op16=2 op17=[[NONE3:.*]] op18=2/>
 ; COMBINED_NEXT:    <COMBINED abbrevid=
 ; COMBINED_NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 
 
 ; ModuleID = 'thinlto-function-summary-callgraph.ll'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"