[ThinLTO] Compute synthetic function entry count

[eraman]

Summary

This patch computes the synthetic function entry count on the whole
program callgraph (based on module summary) and writes the entry counts
to the summary. After function importing, this count gets attached to
the IR as metadata. Since it adds a new field to the summary, this bumps
up the version.

[tejohnson]

Sorry for the lateness of the review! Comments/questions below.

include/llvm/IR/ModuleSummaryIndex.h

457

Need to document that this is only populated by the Thin Link (and unused by per-module summaries).

1094

For consistency it would be nice to have the above two lines match the same code in child_begin (same with child*_end). I.e.

FunctionSummary *F =
    cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());

lib/Bitcode/Reader/BitcodeReader.cpp

5145

Update message (maybe change to a range rather than a list, since we now have quite a few valid versions).

5248

document constant 0 param (here and in other constructor calls). I.e. "/*Entry Count=*/0"

lib/Bitcode/Writer/BitcodeWriter.cpp

3747

We read this value out of the 5th index unconditionally (or at least when the version is high enough) in BitcodeReader.cpp. Won't it cause an issue on the reader side if we only emit this (and adjust where the ref count is emitted) conditionally?

Regardless, suggest asserting in the writer here and in writePerModuleFunctionSummaryRecord when you expect the FS->entryCount() to be 0.

lib/Transforms/IPO/FunctionImport.cpp

121

why off by default?

672

Some comments about what the algorithm does would be nice.

680

Can this be moved down into the if statement body? It isn't used outside of it.

690

ditto.

694

can this overflow?
Also, why only set the entry count on the first copy? Shouldn't we propagate into all copies?

901

Probably shouldn't do this during importing - setting on the functions already in the dest module isn't really related to importing anyway. Also, if done from the caller (i.e. see thinBackend(), we have a ready map of GUID->Summary, DefinedGlobals). Using that is much more efficient that looking up in the full Index hash map.

994

Remove?

[eraman]

Address Teresa's comments and rebase.

lib/Bitcode/Writer/BitcodeWriter.cpp

3747

Indeed this is a bug. I have changed it to write unconditionally. I don't quite follow the second part of your comment regarding the assert.

lib/Transforms/IPO/FunctionImport.cpp

121

I would like to enable this in the inliner, do some tuning and then turn this on by default. If you strongly prefer this to be default now, I will do so.

672

I haven't explained the algorithm here because it is done in SyntheticCountUtils that works on any callgraph. I have tried to add some comments. Let me know if you want any specific details.

694

Yes, this could overflow. I have changed it to a SaturatingAdd.

This should have been set to all copies. I have modified this as well as initialization counts.

901

thinBackend has the DefinedGlobalsMap, but not the other callers to this function. Could you suggest what is the best way to do this on all callers?

[eraman]

Ping

[tejohnson]

Sorry for the delay.

include/llvm/IR/ModuleSummaryIndex.h

436

Document '0' parameter like you did elsewhere.

lib/Analysis/ModuleSummaryAnalysis.cpp

440–441

Document '0' parameter like you did elsewhere.

lib/Bitcode/Writer/BitcodeWriter.cpp

3747

Nevermind the comment about the assert, looking again, I don't think it makes much sense.

lib/Transforms/IPO/FunctionImport.cpp

121

Ok

123

Nit - does this need to be split into 2 lines? It looks like it would fit on one 80 col line.

656

Nit: reads better without the "of" (i.e. just "All successors are the ...").

699

Nit: comment needs a fix, i.e. should "takes of" be "takes on"?

901

You only need to invoke this functionality from two places:

1. The new LTO API (thinBackend) - tested via llvm-lto2
2. The old C LTO API (ThinLTOCodeGenerator.cpp) - tested via llvm-lto

Both of these already have the DefinedGlobals map, because they invoke other Thin Link optimizations that require it. I.e. search for callers of thinLTOInternalizeModule, which is passed this map. And just add a call to this functionality, split out into a similar type of function, that takes the map. You'll note that for testing purposes, the old C API has the ability to call the thin link optimizations independent of the other optimizations, i.e. see ThinLTOCodeGenerator::internalize, and you may want to do something similar too (for testing via llvm-lto).

942

Similarly, this handling can be moved into renameModuleForThinLTO, called further below here, which already does some index-based updates for each imported global. See the start of processGlobalForThinLTO, which does:
ValueInfo VI = ImportIndex.getValueInfo(GV.getGUID());

and the ValueInfo has a pointer to the summary entry. You can have it get the ValueInfo once and share it with your update, which can be done in that method.

You may want to add an interface to the ValueInfo to get the summary entry given a ModulePath (Name), since it only has an interface to return the list of summary entries currently.

[eraman]

Sorry for this very long delay in following up.

lib/Transforms/IPO/FunctionImport.cpp

699

I think I intended "takes care of"

901

The test I wrote (function_entry_count.ll) runs opt to do function importing. The entry point is from FunctionImportLegacyPass::runOnModule. Is this something that I don't need to support (and rewrite the test appropriately)?

[eraman]

lib/Transforms/IPO/FunctionImport.cpp

901

Based on our offline chat, I changed the test not to use opt (and use llvm-lto2 instead) and I am able to move this code as you've suggested.

942

I am not sure what is the good way to guard the change with enable-import-entry-count flag. I don't like the idea of referencing the flag from a utils file, but the alternative is to pass the value through the callchain starting from renameModuleForThinLTO, which has other callers. Do you have any suggestions?

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

942

Perhaps do the updates on both the imported functions and the defined functions (what you were doing above) in renameModuleForThinLTO (it's called on the original module and again below for the imported symbols). Then you cover both my comments (since it's called outside importing for the orig module's defined symbols). In that case the EnableImportEntryCount flag can be completely moved into the utils source file.

[eraman]

lib/Transforms/IPO/FunctionImport.cpp

942

I have moved the updates to processGlobalForThinLTO. I am not sure if I am doing the right thing comparing ModulePath() with M.getModuleIdentifier().

[eraman]

Rebase and address Teresa's comments.

[tejohnson]

lib/Analysis/ModuleSummaryAnalysis.cpp

434

nit: s/InsCount/InstCount/
Thanks for adding the documentation for these existing parameters too!

lib/LTO/LTO.cpp

1142

Add brief comment about what this does.

lib/LTO/ThinLTOCodeGenerator.cpp

203 ↗

(On Diff #176166)

I don't see this new parameter getting used anywhere. I think it might be leftover from your earlier approach (along with the other changes to this file)?

941 ↗

(On Diff #176166)

Add a call to your new analysis above here so it is supported with the old LTO API as well. Then you can augment your new test with an llvm-lto invocation as well.

lib/Transforms/IPO/FunctionImport.cpp

671

I assume that eventually we would want to gate this based on whether we have FDO or not - how will that work?

675

What is a fake/invalid edge in the index?

[eraman]

I have to bump up the index version to 6 after rebasing and fix a few failing test cases.

lib/LTO/ThinLTOCodeGenerator.cpp

203 ↗

(On Diff #176166)

Yes, this is leftover from earlier iterations

lib/Transforms/IPO/FunctionImport.cpp

671

I think eventually we want this to work even when profile data is available by filling in the synthesized count for only those functions which do not have an entry count (a hybrid mode). What I have done now is to gate this on -enable-import-entry-count. To avoid declaring this as extern, I have moved the computeSyntheticCount to FunctionImportUtils.cpp (where the flag is defined) and bail out if the flag is false.

675

These are the edges from the fake root node to all nodes without parent (see calculateCallGraphRoot). But there is no need to handle them separately (and the FIXME should be removed). The Edge.second.RelBlockFreq will be 0 and hence this lambda will return 0 for the fake edges which is the right thing to do.

[eraman]

Address Teresa's comments, rebase and fix test failures after rebasing.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

671

It doesn't belong in FunctionImportUtils.cpp, which is operating on IR in the backends. It belongs somewhere in lib/LTO since this is done during the LTO/thin link portion of the compile. Historically we have put some of these facilities in FunctionImport.cpp even when they aren't directly related to importing (e.g. computeDeadSymbols), but it probably makes sense for them to move to a separate file under lib/LTO/ that can be shared by both the new and old LTO APIs. Maybe best to just create that new file now for your new code (in which case we can move computeDeadSymbols there as a follow on). Not sure the best name, maybe something like SummaryBasedOptimizations.cpp ? Open to better names...

Regarding avoiding that option being extern, 2 possibilities come to mind:

• Does an entry count of 0 in the summary mean that synthetic counts weren't created? If so, can you gate on that.

Or probably more robust:

• Consider adding a flag to the index (see withGlobalValueDeadStripping).

675

Ok sounds good - I noticed that the FIXME is still there though.

[eraman]

lib/Transforms/IPO/FunctionImport.cpp

671

I have create a new SummaryBasedOptimizations.cpp and moved the code there. I have also added a flag to Index to indicate whether synthetic counts are computed.

[eraman]

Address review comments

[tejohnson]

LGTM with 1 minor comment nit below, and also can you please add a test like test/Bitcode/thinlto-deadstrip-flag.ll to test for the new flag directly?

include/llvm/IR/ModuleSummaryIndex.h

744

s/propagatin/propagation/

[eraman]

Add a test case to check for synthetic entry counts and rebase.

[eraman]

Add a test case to check for HasSyntheticEntryCounts flag.

include/llvm/IR/ModuleSummaryIndex.h

public:
   /// Create an empty FunctionSummary (with specified call edges).
   /// Used to represent external nodes and the dummy root node.
   static FunctionSummary
   makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
     return FunctionSummary(
         FunctionSummary::GVFlags(
             GlobalValue::LinkageTypes::AvailableExternallyLinkage,
             /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
-        0, FunctionSummary::FFlags{}, std::vector<ValueInfo>(),
+        0, FunctionSummary::FFlags{}, 0, std::vector<ValueInfo>(),
         std::move(Edges), std::vector<GlobalValue::GUID>(),
         std::vector<FunctionSummary::VFuncId>(),
         std::vector<FunctionSummary::VFuncId>(),
         std::vector<FunctionSummary::ConstVCall>(),
         std::vector<FunctionSummary::ConstVCall>());
   }
 
   /// A dummy node to reference external functions that aren't in the index
   static FunctionSummary ExternalNode;
 
 private:
   /// Number of instructions (ignoring debug instructions, e.g.) computed
   /// during the initial compile step when the summary index is first built.
   unsigned InstCount;
 
   /// Function attribute flags. Used to track if a function accesses memory,
   /// recurses or aliases.
   FFlags FunFlags;
 
+  /// The synthesized entry count of the function.
+  uint64_t EntryCount = 0;
+
   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
   std::vector<EdgeTy> CallGraphEdgeList;
 
   /// All type identifier related information. Because these fields are
   /// relatively uncommon we only allocate space for them if necessary.
   struct TypeIdInfo {
     /// List of type identifiers used by this function in llvm.type.test
     /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs.
struct TypeIdInfo {
     std::vector<ConstVCall> TypeTestAssumeConstVCalls,
         TypeCheckedLoadConstVCalls;
   };
 
   std::unique_ptr<TypeIdInfo> TIdInfo;
 
 public:
   FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
-                  std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
+                  uint64_t EntryCount, std::vector<ValueInfo> Refs,
+                  std::vector<EdgeTy> CGEdges,
                   std::vector<GlobalValue::GUID> TypeTests,
                   std::vector<VFuncId> TypeTestAssumeVCalls,
                   std::vector<VFuncId> TypeCheckedLoadVCalls,
                   std::vector<ConstVCall> TypeTestAssumeConstVCalls,
                   std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
-        InstCount(NumInsts), FunFlags(FunFlags),
+        InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
         CallGraphEdgeList(std::move(CGEdges)) {
     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
         !TypeCheckedLoadConstVCalls.empty())
       TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
           std::move(TypeTests), std::move(TypeTestAssumeVCalls),
           std::move(TypeCheckedLoadVCalls),
           std::move(TypeTestAssumeConstVCalls),
           std::move(TypeCheckedLoadConstVCalls)});
   }
 
   /// Check if this is a function summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == FunctionKind;
   }
 
   /// Get function attribute flags.
   FFlags &fflags() { return FunFlags; }
 
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
+  /// Get the synthetic entry count for this function.
+  uint64_t entryCount() const { return EntryCount; }
+
+  /// Set the synthetic entry count for this function.
+  void setEntryCount(uint64_t EC) { EntryCount = EC; }
+
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 
   /// Returns the list of type identifiers used by this function in
   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
   /// represented as GUIDs.
   ArrayRef<GlobalValue::GUID> type_tests() const {
     if (TIdInfo)
private:
   /// GUIDs, it will be mapped to 0.
   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
 
   /// Indicates that summary-based GlobalValue GC has run, and values with
   /// GVFlags::Live==false are really dead. Otherwise, all values must be
   /// considered live.
   bool WithGlobalValueDeadStripping = false;
 
   /// Indicates that distributed backend should skip compilation of the
   /// module. Flag is suppose to be set by distributed ThinLTO indexing
   /// when it detected that the module is not needed during the final
   /// linking. As result distributed backend should just output a minimal
   /// valid object file.
   bool SkipModuleByDistributedBackend = false;
 
   /// If true then we're performing analysis of IR module, filling summary
   /// accordingly. The value of 'false' means we're reading summary from
public:
 
   /// Print out strongly connected components for debugging.
   void dumpSCCs(raw_ostream &OS);
 };
 
 /// GraphTraits definition to build SCC for the index
 template <> struct GraphTraits<ValueInfo> {
   typedef ValueInfo NodeRef;
+  using EdgeRef = FunctionSummary::EdgeTy &;
 
   static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
     return P.first;
   }
   using ChildIteratorType =
       mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
                       decltype(&valueInfoFromEdge)>;
 
+  using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
+
   static NodeRef getEntryNode(ValueInfo V) { return V; }
 
   static ChildIteratorType child_begin(NodeRef N) {
     if (!N.getSummaryList().size()) // handle external function
       return ChildIteratorType(
           FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
           &valueInfoFromEdge);
     FunctionSummary *F =
         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
     return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
   }
 
   static ChildIteratorType child_end(NodeRef N) {
     if (!N.getSummaryList().size()) // handle external function
       return ChildIteratorType(
           FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
           &valueInfoFromEdge);
     FunctionSummary *F =
         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
     return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
   }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    if (!N.getSummaryList().size()) // handle external function
+      return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
+
+    auto *S = N.getSummaryList().front().get()->getBaseObject();
+    FunctionSummary *F = cast<FunctionSummary>(S);
+    return F->CallGraphEdgeList.begin();
+  }
+
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) {
+    if (!N.getSummaryList().size()) // handle external function
+      return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
+
+    auto *S = N.getSummaryList().front().get()->getBaseObject();
+    FunctionSummary *F = cast<FunctionSummary>(S);
+    return F->CallGraphEdgeList.end();
+  }
+
+  static NodeRef edge_dest(EdgeRef E) { return E.first; }
 };
 
 template <>
 struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
   static NodeRef getEntryNode(ModuleSummaryIndex *I) {
     std::unique_ptr<GlobalValueSummary> Root =
         make_unique<FunctionSummary>(I->calculateCallGraphRoot());
     GlobalValueSummaryInfo G(I->isPerformingAnalysis());

include/llvm/IR/ModuleSummaryIndexYAML.h

static void inputOne(IO &io, StringRef Key, GlobalValueSummaryMapTy &V) {
     }
     auto P = V.emplace(KeyInt, /*IsAnalysis=*/false);
     auto &Elem = (*P.first).second;
     for (auto &FSum : FSums) {
       Elem.SummaryList.push_back(llvm::make_unique<FunctionSummary>(
           GlobalValueSummary::GVFlags(
               static_cast<GlobalValue::LinkageTypes>(FSum.Linkage),
               FSum.NotEligibleToImport, FSum.Live, FSum.IsLocal),
-          0, FunctionSummary::FFlags{}, ArrayRef<ValueInfo>{},
+          0, FunctionSummary::FFlags{}, 0, ArrayRef<ValueInfo>{},
           ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests),
           std::move(FSum.TypeTestAssumeVCalls),
           std::move(FSum.TypeCheckedLoadVCalls),
           std::move(FSum.TypeTestAssumeConstVCalls),
           std::move(FSum.TypeCheckedLoadConstVCalls)));
     }
   }
   static void output(IO &io, GlobalValueSummaryMapTy &V) {

include/llvm/Transforms/IPO/FunctionImport.h

void computeDeadSymbols(
     ModuleSummaryIndex &Index,
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
     function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing);
 
 /// Converts value \p GV to declaration, or replaces with a declaration if
 /// it is an alias. Returns true if converted, false if replaced.
 bool convertToDeclaration(GlobalValue &GV);
 
+/// Compute synthetic function entry counts.
+void computeSyntheticCounts(ModuleSummaryIndex &Index);
+
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 //
 /// This includes summaries from that module (in case any global summary based
 /// optimizations were recorded) and from any definitions in other modules that
 /// should be imported.
 //
 /// \p ModuleToSummariesForIndex will be populated with the needed summaries

lib/Analysis/ModuleSummaryAnalysis.cpp

GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
                                     /* Live = */ false, F.isDSOLocal());
   FunctionSummary::FFlags FunFlags{
       F.hasFnAttribute(Attribute::ReadNone),
       F.hasFnAttribute(Attribute::ReadOnly),
       F.hasFnAttribute(Attribute::NoRecurse),
       F.returnDoesNotAlias(),
   };
   auto FuncSummary = llvm::make_unique<FunctionSummary>(
-      Flags, NumInsts, FunFlags, RefEdges.takeVector(),
+      Flags, NumInsts, FunFlags, 0, RefEdges.takeVector(),
       CallGraphEdges.takeVector(), TypeTests.takeVector(),
       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
       TypeTestAssumeConstVCalls.takeVector(),
       TypeCheckedLoadConstVCalls.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
ModuleSymbolTable::CollectAsmSymbols(
                                               /* NotEligibleToImport = */ true,
                                               /* Live = */ true,
                                               /* Local */ GV->isDSOLocal());
           CantBePromoted.insert(GlobalValue::getGUID(Name));
           // Create the appropriate summary type.
           if (Function *F = dyn_cast<Function>(GV)) {
             std::unique_ptr<FunctionSummary> Summary =
                 llvm::make_unique<FunctionSummary>(
                     GVFlags, 0,
                     FunctionSummary::FFlags{
                         F->hasFnAttribute(Attribute::ReadNone),
                         F->hasFnAttribute(Attribute::ReadOnly),
                         F->hasFnAttribute(Attribute::NoRecurse),
                         F->returnDoesNotAlias()},
-                    ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
+                    0, ArrayRef<ValueInfo>{},
+                    ArrayRef<FunctionSummary::EdgeTy>{},
                     ArrayRef<GlobalValue::GUID>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::ConstVCall>{},
                     ArrayRef<FunctionSummary::ConstVCall>{});
             Index.addGlobalValueSummary(Name, std::move(Summary));
           } else {
             std::unique_ptr<GlobalVarSummary> Summary =

lib/Analysis/SyntheticCountsUtils.cpp

 //===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines utilities for propagating synthetic counts.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/SyntheticCountsUtils.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SCCIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/ModuleSummaryIndex.h"
 
 using namespace llvm;
 
 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
 template <typename CallGraphType>
 void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
     const SccTy &SCC, GetRelBBFreqTy GetRelBBFreq, GetCountTy GetCount,
     AddCountTy AddCount) {
 
-  SmallPtrSet<NodeRef, 8> SCCNodes;
+  DenseSet<NodeRef> SCCNodes;
   SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
 
   for (auto &Node : SCC)
     SCCNodes.insert(Node);
 
   // Partition the edges coming out of the SCC into those whose destination is
   // in the SCC and the rest.
   for (const auto &Node : SCCNodes) {
void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
   // The callgraph-scc needs to be visited in top-down order for propagation.
   // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
   // and call propagateFromSCC.
   for (auto &SCC : reverse(SCCs))
     propagateFromSCC(SCC, GetRelBBFreq, GetCount, AddCount);
 }
 
 template class llvm::SyntheticCountsUtils<const CallGraph *>;
+template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;

lib/Bitcode/Reader/BitcodeReader.cpp

// Parse version
     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
     if (Entry.Kind != BitstreamEntry::Record)
       return error("Invalid Summary Block: record for version expected");
     if (Stream.readRecord(Entry.ID, Record) != bitc::FS_VERSION)
       return error("Invalid Summary Block: version expected");
   }
   const uint64_t Version = Record[0];
   const bool IsOldProfileFormat = Version == 1;
-  if (Version < 1 || Version > 4)
+  if (Version < 1 || Version > 5)
     return error("Invalid summary version " + Twine(Version) +
                  ", 1, 2, 3 or 4 expected");
   Record.clear();
 
   // Keep around the last seen summary to be used when we see an optional
   // "OriginalName" attachement.
   GlobalValueSummary *LastSeenSummary = nullptr;
   GlobalValue::GUID LastSeenGUID = 0;
 
   // We can expect to see any number of type ID information records before
case bitc::FS_PERMODULE_PROFILE: {
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE);
       bool HasRelBF = (BitCode == bitc::FS_PERMODULE_RELBF);
       std::vector<FunctionSummary::EdgeTy> Calls = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile, HasRelBF);
       auto FS = llvm::make_unique<FunctionSummary>(
-          Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
+          Flags, InstCount, getDecodedFFlags(RawFunFlags), 0, std::move(Refs),
           std::move(Calls), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
while (true) {
     //                       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];
       uint64_t RawFunFlags = 0;
+      uint64_t EntryCount = 0;
       unsigned NumRefs = Record[4];
       int RefListStartIndex = 5;
 
       if (Version >= 4) {
         RawFunFlags = Record[4];
-        NumRefs = Record[5];
         RefListStartIndex = 6;
+        if (Version >= 5 && BitCode == bitc::FS_COMBINED) {
+          EntryCount = Record[5];
+          RefListStartIndex = 7;
+        }
+        NumRefs = Record[RefListStartIndex - 1];
       }
 
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
       std::vector<FunctionSummary::EdgeTy> Edges = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile, false);
       ValueInfo VI = getValueInfoFromValueId(ValueID).first;
       auto FS = llvm::make_unique<FunctionSummary>(
-          Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
-          std::move(Edges), std::move(PendingTypeTests),
+          Flags, InstCount, getDecodedFFlags(RawFunFlags), EntryCount,
+          std::move(Refs), std::move(Edges), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();

lib/Bitcode/Writer/BitcodeWriter.cpp

void ModuleBitcodeWriterBase::writeModuleLevelReferences(
   Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals,
                     FSModRefsAbbrev);
   NameVals.clear();
 }
 
 // Current version for the summary.
 // This is bumped whenever we introduce changes in the way some record are
 // interpreted, like flags for instance.
-static const uint64_t INDEX_VERSION = 4;
+static const uint64_t INDEX_VERSION = 5;
 
 /// Emit the per-module summary section alongside the rest of
 /// the module's bitcode.
 void ModuleBitcodeWriterBase::writePerModuleGlobalValueSummary() {
   // By default we compile with ThinLTO if the module has a summary, but the
   // client can request full LTO with a module flag.
   bool IsThinLTO = true;
   if (auto *MD =
void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
   // Abbrev for FS_COMBINED.
   auto Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // fflags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // entrycount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   // numrefs x valueid, n x (valueid)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSCallsAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
   // Abbrev for FS_COMBINED_PROFILE.
   Abbv = std::make_shared<BitCodeAbbrev>();
forEachSummary([&](GVInfo I, bool IsAliasee) {
     auto *FS = cast<FunctionSummary>(S);
     writeFunctionTypeMetadataRecords(Stream, FS);
 
     NameVals.push_back(*ValueId);
     NameVals.push_back(Index.getModuleId(FS->modulePath()));
     NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
     NameVals.push_back(FS->instCount());
     NameVals.push_back(getEncodedFFlags(FS->fflags()));
+
+    bool HasProfileData = false;
+    for (auto &EI : FS->calls()) {
+      HasProfileData |=
+          EI.second.getHotness() != CalleeInfo::HotnessType::Unknown;
+      if (HasProfileData)
+        break;
+    }
+
+    int CountIndex = 5;
+    if (!HasProfileData) {
+      CountIndex = 6;
+      NameVals.push_back(FS->entryCount());
+    }
+
     // Fill in below
     NameVals.push_back(0);
 
     unsigned Count = 0;
     for (auto &RI : FS->refs()) {
       auto RefValueId = getValueId(RI.getGUID());
       if (!RefValueId)
         continue;
       NameVals.push_back(*RefValueId);
       Count++;
     }
-    NameVals[5] = Count;
-
-    bool HasProfileData = false;
-    for (auto &EI : FS->calls()) {
-      HasProfileData |=
-          EI.second.getHotness() != CalleeInfo::HotnessType::Unknown;
-      if (HasProfileData)
-        break;
-    }
+    NameVals[CountIndex] = Count;
 
     for (auto &EI : FS->calls()) {
       // If this GUID doesn't have a value id, it doesn't have a function
       // summary and we don't need to record any calls to it.
       GlobalValue::GUID GUID = EI.first.getGUID();
       auto CallValueId = getValueId(GUID);
       if (!CallValueId) {
         // For SamplePGO, the indirect call targets for local functions will

lib/LTO/LTO.cpp

Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache) {
   // uses that couldn't be promoted/renamed on export). This is so
   // InProcessThinBackend::start can still launch a backend thread, which
   // is passed the map of summaries for the module, without any special
   // handling for this case.
   for (auto &Mod : ThinLTO.ModuleMap)
     if (!ModuleToDefinedGVSummaries.count(Mod.first))
       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
 
+  computeSyntheticCounts(ThinLTO.CombinedIndex);
+
   StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
       ThinLTO.ModuleMap.size());
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
   if (DumpThinCGSCCs)
     ThinLTO.CombinedIndex.dumpSCCs(outs());

lib/Transforms/IPO/FunctionImport.cpp

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/Analysis/SyntheticCountsUtils.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/IR/AutoUpgrade.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"

 #if !defined(NDEBUG)
                                   true /*Enabled with asserts.*/
 #else
                                   false
 #endif
                                   ),
     cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'"));
 
+static cl::opt<bool> EnableImportEntryCount(
+    "enable-import-entry-count", cl::init(false), cl::Hidden,
+    cl::desc("Attach 'synthetic_entry_count' metadata after "
+             "importing"));
+
 /// Summary file to use for function importing when using -function-import from
 /// the command line.
 static cl::opt<std::string>
     SummaryFile("summary-file",
                 cl::desc("The summary file to use for function importing."));
 
 /// Used when testing importing from distributed indexes via opt
 // -function-import.
 static cl::opt<bool>
     ImportAllIndex("import-all-index",
                    cl::desc("Import all external functions in index."));
 
+extern cl::opt<int> InitialSyntheticCount;
+
 // Load lazily a module from \p FileName in \p Context.
 static std::unique_ptr<Module> loadFile(const std::string &FileName,
                                         LLVMContext &Context) {
   SMDiagnostic Err;
   DEBUG(dbgs() << "Loading '" << FileName << "'\n");
   // Metadata isn't loaded until functions are imported, to minimize
   // the memory overhead.
   std::unique_ptr<Module> Result =
void llvm::computeDeadSymbols(
 
   unsigned DeadSymbols = Index.size() - LiveSymbols;
   DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
                << " symbols Dead \n");
   NumDeadSymbols += DeadSymbols;
   NumLiveSymbols += LiveSymbols;
 }
 
+static void initializeCounts(ModuleSummaryIndex &Index) {
+  auto Root = Index.calculateCallGraphRoot();
+  // Root is a fake node. All successors of are the actual roots of the
+  // callgraph.
+  // FIXME: This initializes the entry counts of only the root nodes. This makes
+  // sense when compiling a binary with ThinLTO, but for libraries any of the
+  // non-root nodes could be called from outside.
+  for (auto &C : Root.calls()) {
+    FunctionSummary *F = nullptr;
+    auto &V = C.first;
+    if (V.getSummaryList().size()) {
+      auto S = V.getSummaryList().front().get()->getBaseObject();
+      F = cast<FunctionSummary>(S);
+      F->setEntryCount(InitialSyntheticCount);
+    }
+  }
+}
+
+void llvm::computeSyntheticCounts(ModuleSummaryIndex &Index) {
+  using Scaled64 = ScaledNumber<uint64_t>;
+  initializeCounts(Index);
+  auto GetCallSiteRelFreq = [](FunctionSummary::EdgeTy &Edge) {
+    // FIXME: Handle fake/invalid edges?
+    return Scaled64(Edge.second.RelBlockFreq, -CalleeInfo::ScaleShift);
+  };
+  auto GetEntryCount = [](ValueInfo V) {
+    FunctionSummary *F = nullptr;
+    if (V.getSummaryList().size()) {
+      auto S = V.getSummaryList().front().get()->getBaseObject();
+      F = cast<FunctionSummary>(S);
+      return F->entryCount();
+    } else {
+      return UINT64_C(0);
+    }
+  };
+  auto AddToEntryCount = [](ValueInfo V, uint64_t New) {
+    FunctionSummary *F = nullptr;
+    if (V.getSummaryList().size()) {
+      auto S = V.getSummaryList().front().get()->getBaseObject();
+      F = cast<FunctionSummary>(S);
+      F->setEntryCount(F->entryCount() + New);
+    }
+  };
+
+  SyntheticCountsUtils<ModuleSummaryIndex *>::propagate(
+      &Index, GetCallSiteRelFreq, GetEntryCount, AddToEntryCount);
+}
+
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 void llvm::gatherImportedSummariesForModule(
     StringRef ModulePath,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     const FunctionImporter::ImportMapTy &ImportList,
     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
   // Include all summaries from the importing module.

 // index.
 Expected<bool> FunctionImporter::importFunctions(
     Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
   DEBUG(dbgs() << "Starting import for Module "
                << DestModule.getModuleIdentifier() << "\n");
   unsigned ImportedCount = 0, ImportedGVCount = 0;
 
   IRMover Mover(DestModule);
+  for (auto &F : DestModule) {
+    FunctionSummary *FS =
+        dyn_cast_or_null<FunctionSummary>(Index.findSummaryInModule(
+            F.getGUID(), DestModule.getModuleIdentifier()));
+    if (FS && !F.isDeclaration() && EnableImportEntryCount)
+      F.setEntryCount(
+          Function::ProfileCount(FS->entryCount(), Function::PCT_Synthetic));
+  }
   // Do the actual import of functions now, one Module at a time
   std::set<StringRef> ModuleNameOrderedList;
   for (auto &FunctionsToImportPerModule : ImportList) {
     ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
   }
   for (auto &Name : ModuleNameOrderedList) {
     // Get the module for the import
     const auto &FunctionsToImportPerModule = ImportList.find(Name);
for (Function &F : *SrcModule) {
       auto GUID = F.getGUID();
       auto Import = ImportGUIDs.count(GUID);
       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function " << GUID
                    << " " << F.getName() << " from "
                    << SrcModule->getSourceFileName() << "\n");
       if (Import) {
         if (Error Err = F.materialize())
           return std::move(Err);
+        auto *Summary = Index.findSummaryInModule(GUID, Name);
+        FunctionSummary *FS =
+            dyn_cast<FunctionSummary>(Summary->getBaseObject());
+        if (FS && !F.isDeclaration() && EnableImportEntryCount) {
+          F.setEntryCount(Function::ProfileCount(FS->entryCount(),
+                                                 Function::PCT_Synthetic));
+        }
         if (EnableImportMetadata) {
           // Add 'thinlto_src_module' metadata for statistics and debugging.
           F.setMetadata(
               "thinlto_src_module",
               MDNode::get(DestModule.getContext(),
                           {MDString::get(DestModule.getContext(),
                                          SrcModule->getSourceFileName())}));
         }
for (GlobalAlias &GA : SrcModule->aliases()) {
         // Import alias as a copy of its aliasee.
         GlobalObject *Base = GA.getBaseObject();
         if (Error Err = Base->materialize())
           return std::move(Err);
         auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
         DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
               << " " << Base->getName() << " from "
               << SrcModule->getSourceFileName() << "\n");
+        /*
+        auto *Summary = Index.findSummaryInModule(GUID, Name);
+        FunctionSummary *FS =
+        dyn_cast<FunctionSummary>(Summary->getBaseObject()); if (FS) {
+          Fn->setEntryCount(Function::ProfileCount(FS->entryCount(),
+        Function::PCT_Synthetic));
+        }
+        */
         if (EnableImportMetadata) {
           // Add 'thinlto_src_module' metadata for statistics and debugging.
           Fn->setMetadata(
               "thinlto_src_module",
               MDNode::get(DestModule.getContext(),
                           {MDString::get(DestModule.getContext(),
                                          SrcModule->getSourceFileName())}));
         }

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

 
 using namespace llvm;
 using Scaled64 = ScaledNumber<uint64_t>;
 using ProfileCount = Function::ProfileCount;
 
 #define DEBUG_TYPE "synthetic-counts-propagation"
 
 /// Initial synthetic count assigned to functions.
-static cl::opt<int>
+cl::opt<int>
     InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
                           cl::ZeroOrMore,
                           cl::desc("Initial value of synthetic entry count."));
 
 /// Initial synthetic count assigned to inline functions.
 static cl::opt<int> InlineSyntheticCount(
     "inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore,
     cl::desc("Initial synthetic entry count for inline functions."));

test/Bitcode/summary_version.ll

 ; Check summary versioning
 ; RUN: opt  -module-summary  %s -o - | llvm-bcanalyzer -dump | FileCheck %s
 
 ; CHECK: <GLOBALVAL_SUMMARY_BLOCK
-; CHECK: <VERSION op0=4/>
+; CHECK: <VERSION op0=5/>
 
 
 
 ; Need a function for the summary to be populated.
 define void @foo() {
     ret void
 }

test/Bitcode/thinlto-alias.ll

 
 ; COMBINED:       <GLOBALVAL_SUMMARY_BLOCK
 ; COMBINED-NEXT:    <VERSION
 ; COMBINED-NEXT:    <FLAGS
 ; See if the call to analias is registered, using the expected value id.
 ; COMBINED-NEXT:    <VALUE_GUID op0=[[ALIASID:[0-9]+]] op1=-5751648690987223394/>
 ; COMBINED-NEXT:    <VALUE_GUID
 ; COMBINED-NEXT:    <VALUE_GUID op0=[[ALIASEEID:[0-9]+]] op1=-1039159065113703048/>
-; COMBINED-NEXT:    <COMBINED {{.*}} op6=[[ALIASID]]/>
+; COMBINED-NEXT:    <COMBINED {{.*}} op7=[[ALIASID]]/>
 ; COMBINED-NEXT:    <COMBINED {{.*}}
 ; COMBINED-NEXT:    <COMBINED_ALIAS  {{.*}} op3=[[ALIASEEID]]
 ; 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"
 
 ; Function Attrs: nounwind uwtable
 define i32 @main() {
 entry:
     call void (...) @analias()
     ret i32 0
 }
 
 declare void @analias(...)

test/Bitcode/thinlto-function-summary-callgraph.ll

 ; COMBINED-NEXT:    <VERSION
 ; COMBINED-NEXT:    <FLAGS
 ; Only 2 VALUE_GUID since reference to undefinedglob should not be included in
 ; combined index.
 ; COMBINED-NEXT:    <VALUE_GUID op0=[[FUNCID:[0-9]+]] op1=7289175272376759421/>
 ; COMBINED-NEXT:    <VALUE_GUID
 ; COMBINED-NEXT:    <COMBINED
 ; See if the call to func is registered.
-; COMBINED-NEXT:    <COMBINED {{.*}} op6=[[FUNCID]]/>
+; COMBINED-NEXT:    <COMBINED {{.*}} op7=[[FUNCID]]/>
 ; 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"
 
 ; Function Attrs: nounwind uwtable
 define i32 @main() #0 {

test/ThinLTO/X86/Inputs/function_entry_count.ll

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

test/ThinLTO/X86/function_entry_count.ll

+; RUN: opt -thinlto-bc %s -write-relbf-to-summary -thin-link-bitcode-file=%t1.thinlink.bc -o %t1.bc
+; RUN: opt -thinlto-bc %p/Inputs/function_entry_count.ll -write-relbf-to-summary -thin-link-bitcode-file=%t2.thinlink.bc -o %t2.bc
+
+; First perform the thin link on the normal bitcode file.
+; RUN: llvm-lto2 run %t1.bc %t2.bc -o %t.o -save-temps -enable-import-entry-count \
+; RUN:     -thinlto-distributed-indexes \
+; RUN:     -r=%t1.bc,g, \
+; RUN:     -r=%t1.bc,f,px \
+; RUN:     -r=%t1.bc,h,px \
+; RUN:     -r=%t2.bc,h, \
+; RUN:     -r=%t2.bc,g,px
+; RUN: opt -function-import -import-all-index -enable-import-metadata -summary-file %t1.bc.thinlto.bc %t1.bc -o %t1.out -enable-import-entry-count 
+; RUN: llvm-dis -o - %t1.out | FileCheck %s
+
+; CHECK: define void @h() !prof ![[PROF2:[0-9]+]]
+; CHECK: define void @f(i32 %n) !prof ![[PROF1:[0-9]+]]
+; CHECK: define available_externally void @g() !prof ![[PROF2]]
+; CHECK-DAG: ![[PROF1]] = !{!"synthetic_function_entry_count", i64 10}
+; CHECK-DAG: ![[PROF2]] = !{!"synthetic_function_entry_count", i64 198}
+
+target triple = "x86_64-unknown-linux-gnu"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+declare void @g();
+
+define void @h() {
+  ret void
+}
+
+define void @f(i32 %n) {
+entry:
+  %cmp = icmp slt i32 %n, 1
+  br i1 %cmp, label %exit, label %loop
+loop:
+  %n1 = phi i32 [%n, %entry], [%n2, %loop]
+  call void  @g()
+  %n2 = sub i32 %n1, 1
+  %cmp2 = icmp slt i32 %n, 1
+  br i1 %cmp2, label %exit, label %loop
+exit:
+  ret void
+}