[ThinLTO] Support for reference graph in per-module and combined summary.

[tejohnson]

Summary

This patch adds support for including a full reference graph including
call graph edges and other GV references in the summary.

The reference graph edges can be used to make importing decisions
without materializing any source modules, can be used in the plugin
to make file staging decisions for distributed build systems, and is
expected to have other uses.

The call graph edges are recorded in each function summary in the
bitcode via a list of <CalleeValueIds, StaticCount> tuples when no PGO
data exists, or <CalleeValueId, StaticCount, ProfileCount> pairs when
there is PGO, where the ValueId can be mapped to the function GUID via
the ValueSymbolTable. In the function index in memory, the call graph
edges reference the target via the CalleeGUID instead of the
CalleeValueId.

The reference graph edges are recorded in each summary record with a
list of referenced value IDs, which can be mapped to value GUID via the
ValueSymbolTable.

Addtionally, a new summary record type is added to record references
from global variable initializers. A number of bitcode records and data
structures have been renamed to reflect the newly expanded scope of the
summary beyond functions. More cleanup will follow.

Measurements on 483.xalancbmk show the following increases in object and
combined index sizes:

• Overall .o bitcode increase is 1.34% without PGO and 1.54% with PGO
• The combined index increase is 116% without PGO and 120% with PGO
• The aggregate size of the .o bitcode and combined index together increased 3.22% without PGO and 3.39% with PGO (the combined index size increase is large taken alone, but its size is still on the same order of magnitude as the larger .o files).

[davidxl]

include/llvm/Bitcode/LLVMBitCodes.h

192–209

A side note -- it might be useful to reserve some bits for general function attributes such as 'address-taken' etc.

include/llvm/IR/FunctionInfo.h

148

Without profile data, it might be useful to record the number of static callsites from a function to the callee. This can help compiler backend to make better global decisions later (e.g. better inlining and enable more function GC).

362

Is this member really needed? The helper is not intended to own the summary.

lib/Bitcode/Reader/BitcodeReader.cpp

5765

Is it better to introduce a symbolic name for the start index instead of hardcoded 3?

lib/Bitcode/Writer/BitcodeWriter.cpp

2511

Should this be called 'getBlockProfileCount' ? This utiltiy method belongs to include/llvm/ProfileData/ProfileCommon.h.

2867–2869

Should the type be SmallVector<uint64_t, 64> ? GUID is 64 bit type.

[davidxl]

+eraman This patch defines scaledCount() method which should probably be in ProfileCommon.h. There is a similar method in your inliner patch which can be moved there too.

[tejohnson]

include/llvm/Bitcode/LLVMBitCodes.h

192–209

What is the advantage of saving bits now? The format is still highly in flux anyway, and once it is nailed down eventually we would need to use some kind of version id to specify the change regardless of whether it was using saved bits or not.

include/llvm/IR/FunctionInfo.h

148

I could do that by overloading the count field to hold the static number of callsites. Alternatively, for statically-generated profile information is it useful to record the block frequency sums or something like that?

362

The helper does own the function summary temporarily. We create it when the function summary section is read, then later transfer ownership to the index when the VST is read. The reason why I need to keep a non-owning pointer to the summary is that later on after all VST entries are read from the combined index I need to set up the call graph edges in the combined index, and for that I need to keep the association here between the function summary and the CallGraphEdgeValueIdList.

lib/Bitcode/Reader/BitcodeReader.cpp

5765

I can do that. There's a lot of hardcoded start indices just like this in the file already, but I agree a symbolic name would be clearer.

lib/Bitcode/Writer/BitcodeWriter.cpp

2511

Good idea. Will rename and move.

2867–2869

Good point, it should be uint64_t, but for a different reason. We aren't writing the GUID, but rather a value id which is unsigned. But we are writing the profile count when we have profile data, which is uint64_t. Fixing it here and when writing the combined summary.

[davidxl]

include/llvm/Bitcode/LLVMBitCodes.h

192–209

ok.

include/llvm/IR/FunctionInfo.h

148

Regarding static # of callsites -- another way is to build a multi-graph -- basically do not collapse all edges from one caller to the same callee. How much space do we save there?

If we want to save space, there is a better way to do this -- we can build a graph with edges from module to the callee. Such a module->function edge contains the following information :
{ Aggregate call count, max call count, static # of sites }

It is probably not useful to record static block frequency.

362

owns it temporarily in what sense? Does it have a chance to de-allocate it?

[davidxl]

include/llvm/IR/FunctionInfo.h

148

My suggestion regarding using module->function edge can not replace the aggregate function->function call edge here -- but it can be emitted as additional information to track static callsite info -- but that is independent of what this patch does.

[tejohnson]

include/llvm/IR/FunctionInfo.h

148

Right, we still want the function->function edges for better precision. Will consider module->function edges at a later point.

I will need to do some measurements to see what the overhead is of not collapsing the edges within each function. But if we simply add a static callsite count (possibly both with and without PGO), I think that may be sufficient.

362

It passes ownership to the function index in memory when the corresponding VST entry is created. After all the VST entries are created, it uses the saved (non-owned) pointer to create the call graph edges in the function index in memory (need to wait until all the VST entries are parsed as we need to know all the value id and GUIDs). See FunctionIndexBitcodeReader::parseValueSymbolTable (note the function return is in the EndBlock case in the switch statement, not at the bottom of the routine).

The other alternative would be to keep a mapping there from the FunctionSummaryIOHelper object to the corresponding FunctionSummary pointer (created when we parse the corresponding VST entry and transfer the ownership of the unique_ptr to the function index). I think that is probably cleaner and more straightforward. Will make that change.

As an aside, I just noticed that the ValueIdToCallGraphGUIDMap is only used in this routine, I will move it to function local instead of being on the FunctionIndexBitcodeReader class.

[davidxl]

include/llvm/IR/FunctionInfo.h

362

Right -- if the IO helper class only conditionally pass the ownership to functionIndex in some cases, the unique pointer is needed. However if it is intended to be always passed to another object, the helper just need to keep a naked pointer to the summary as it does not really own it.

[tejohnson]

include/llvm/IR/FunctionInfo.h

362

In the BitcodeWriter it stays owned by the helper. In the BitcodeReader ownership is always transferred to the in-memory function index. Even in the latter case, I think creating a unique_ptr immediately, rather than creating a naked pointer and only creating a unique_ptr when the VST is read, is cleaner as it makes the current ownership clear and avoids malloc.

[tejohnson]

Address most of davidxl's comments (except keeping track of total static
count of call edges, that is still TODO).

[mehdi_amini]

I have a concerned about the "Only inter-module calls are recorded" part. This prevents to perform accurate pure summary-based importing decision (that I'm planning on doing).
Have you measured the impact of representing the full call-graph in the summary?

[tejohnson]

In D17212#360805, @joker.eph wrote:

I have a concerned about the "Only inter-module calls are recorded" part. This prevents to perform accurate pure summary-based importing decision (that I'm planning on doing).
Have you measured the impact of representing the full call-graph in the summary?

Good point, I forgot that would be needed if we want to make summary-only importing decisions. Let me add the intra-module edges and measure the added overhead.

[tejohnson]

In D17212#360841, @tejohnson wrote:

In D17212#360805, @joker.eph wrote:

I have a concerned about the "Only inter-module calls are recorded" part. This prevents to perform accurate pure summary-based importing decision (that I'm planning on doing).
Have you measured the impact of representing the full call-graph in the summary?

Good point, I forgot that would be needed if we want to make summary-only importing decisions. Let me add the intra-module edges and measure the added overhead.

For 483.xalancbmk, adding in the intra-module calls adds ~4% to the combined index size (so 26-27% over no callgraph) with and without PGO. This seems reasonable. Will update the patch to include those.

[tejohnson]

• Include intra-module calls.

[eraman]

include/llvm/ProfileData/ProfileCommon.h

194

Why not just do
ScaledCount = EntryCount * BlockFreq / EntryFreq using APInt<128>, take the lower 64 bits if the result fitx within uint64_t and use UINT64_MAX otheerwise?

[mehdi_amini]

I skimmed through and it sounds good to me, please see a few comments below.

[mehdi_amini]

include/llvm/Bitcode/LLVMBitCodes.h

192–210

Side note: we will need to nail the format in the coming weeks/months somehow, or have a plan for backward compatibility (auto upgrade...).

197

It is a bit annoying to have to manually overload for every "optional" data. It may also lead to a combinatory explosion if there were many. Unfortunately the only alternative in the current bitcode format is to have function summary stored as block instead of record...

include/llvm/IR/FunctionInfo.h

148

Without profile data, it might be useful to record the number of static callsites from a function to the callee. This can help compiler backend to make better global decisions later (e.g. better inlining and enable more function GC).

Can you elaborate how would you use this information and how it would help inlining and GC?

374

I think we usually prefix takeXXX and not getXXX when ownership is transferred.

[tejohnson]

Responses to Mehdi's comments.

include/llvm/Bitcode/LLVMBitCodes.h

192–210

Agreed, although I think we are still in the heavy churn tuning phase.

197

Actually my first implementation of this used a single record id. What I did was add a bit to indicate whether there was any profile data, so that the reader knew how to interpret the array data at the end (as either a list of just callee ids, or <callee id, count> pairs). I think I used the size of the record to deduce whether there was any call information. I decided to switch to explicitly encoding this information in the record id because it seemed cleaner and more consistent, and also removed a bit from each record (the profile flag). This reduces the size for large .o bitcode files and for the combined index, although the size for small .o bitcode files is a bit larger due to the 2 extra abbrev ids.

I could probably go back to using the size to deduce the presence or absence of call information, and reduce this to 2 per summary type. WDYT?

include/llvm/IR/FunctionInfo.h

148

I think what David was alluding to was similar to what I was describing on IRC yesterday - if you know you have a single static callsite via the summary, you can give the same inline cost benefit currently given for internal(ized) single-callsite functions. Then if it is inlined, hopefully the original out-of-line function can be eliminated via linker GC.

To do this, the combined index creation step would need to aggregate the # static callsites to each function and put that into the callee function's combined summary.

374

Ok, will fix.

[tejohnson]

Response to eraman's comment.

include/llvm/ProfileData/ProfileCommon.h

194

I looked at APInt briefly when I was thinking about how to do this, but was concerned that it was going to be inefficient in the common case. However, it looks like that isn't the case as it has a fast path. Will change this to use it.

Note I actually stole this code from RAGreedy::initializeCSRCost() (which could probably be refactored to use this new method once it goes in).

[mehdi_amini]

include/llvm/IR/FunctionInfo.h

367

Why this?
If needed, replace with FunctionSummaryIOHelper() = default;

[tejohnson]

include/llvm/IR/FunctionInfo.h

367

This was leftover from when I had a member variable that was being passed in and initialized in the constructor. Removing this now.

[tejohnson]

• Address comments by eraman and jokereph.

[tejohnson]

Add static callsite count to summary callgraph edges.
For 483.xalancbmk this increases the size of the combined index
by another 3.5%.

[mehdi_amini]

include/llvm/IR/FunctionInfo.h

156

Missing const variant.

[tejohnson]

include/llvm/IR/FunctionInfo.h

156

Adding that now.

[tejohnson]

• Add const variant of FunctionSummary::edges

[mehdi_amini]

How could we integrate accesses to global variable as part of this?
It turns out that to be able to benefit from the linker information on what symbol is exported during the import, this is a must.

[tejohnson]

In D17212#362864, @joker.eph wrote:

How could we integrate accesses to global variable as part of this?
It turns out that to be able to benefit from the linker information on what symbol is exported during the import, this is a must.

Well without it you still can see which function symbols will be exported, just not the variables, so you are running with less info and I guess need to assume that all static variables will be exposed and promote them. To refine that behavior for variables, yes, we'd need additional info in the summary.

(For davidxl or anyone else who didn't see the IRC conversation, Mehdi is looking at doing pure summary-based importing decisions in the linker step, then giving this info to the ThinLTO backends to avoid promotion of local values that aren't exported. For a distributed build if we wanted to do it this way the importing decisions would all be made in the plugin step, then would need to be serialized out for the distributed backends to check.)

Two possibilities depending on the fidelity of the info you think you need:

1. One possibility is to just put a flag in the function summary if it accesses *any* local variables, and adjust the importing threshold accordingly. Then in the ThinLTO backend for the exporting module you need to check which of your own functions are on the import list, and which local variables they access, and promote accordingly.

2. If it will be really beneficial to note exactly which local variables are accessed by which function, we'll need to broaden the edges list to include accesses to variables (I assume you only care about local variables here). E.g. the per-module summary edge list for a function would need to include value ids for any local variables referenced by that function (not sure that the other parts of the triple, the static and profile counts, are needed for that). Then in the combined VST we need to include entries for GUIDs of things that don't have a function summary, but are referenced by these edges. When accessing a function summary edge list for a candidate function to import, you could then see the GUID of any local variables accessed. You wouldn't know them by name, but if for example you wanted a heuristic like "if >=N hot import candidate functions from module M access a local variable with GUID G, go ahead and import those and let G be promoted by the backend (which like in approach #1 needs to check which local variables are accessed by any functions on an import list)".

Obviously 1) is easier and cheaper space-wise. What are your thoughts?

[davidxl]

Is there a need to mark it? Does the following work?

1. using summary call graph to do importing decision
2. for any function that is imported by another module, mark it as

'exported'

3. When processing the exporting module, check any exported function and

promote any statics it references.

David

[tejohnson]

In D17212#362994, @davidxl wrote:

Is there a need to mark it? Does the following work?

1. using summary call graph to do importing decision
2. for any function that is imported by another module, mark it as

'exported'

3. When processing the exporting module, check any exported function and

promote any statics it references.

David

That does work for correctness, but Mehdi was proposing that functions accessing local values need to meet a higher importing threshold so that we don't cause too many promotions due to over-eager importing.

In terms of serializing the info out for doing any of this with a distributed build, we could do it via an "exported" bit in the combined summary though.

[mehdi_amini]

lib/Bitcode/Reader/BitcodeReader.cpp

5524

Shouldn't this be ValueIdToCallGraphGUIDMap[ValueID] = Function::getGUID(FunctionGlobalId); ?

[tejohnson]

lib/Bitcode/Reader/BitcodeReader.cpp

5524

Good catch! Yes, it should be. The VST_CODE_ENTRY case does not need to invoke getGlobalIdentifier since those are externally-defined functions (and so not possibly local).

But looking at the other places here where we set up this map I realized that the VST_CODE_COMBINED_FNENTRY case was wrong - we already have the GUID and there is no ValueName in that record. I have a fix for both coming up shortly.

[tejohnson]

• Fix ValueIdToCallGraphGUIDMap entries.

[tejohnson]

Update patch to include full reference graph.

Some notable changes from prior patch:

• include non-call reference edges in summary records
• introduce summary entries for global variable initializations
• add the VSTOFFSET record to the combined index bitcode file, and use it when reading both the per-module and combined indices to parse the VST before the summary section (analogous to how it is used when parsing normal bitcode to parse the VST before the function blocks), which reduces the amount of bookkeeping required to associate the VST entry with the value ids used in the summary section.

Bitcode name changes:

• add a new FS_*_GLOBALVAR_INIT_REFS records to hold ref graph edges from global variable inits to referenced global vars.
• changed the VST_CODE_COMBINED_FNENTRY name to VST_CODE_COMBINED_GVDEFENTRY to reflect the broadened scope (can correspond to either a function or variable def and associated summary).
• changed FUNCTION_SUMMARY_BLOCK_ID to GLOBALVAL_SUMMARY_BLOCK_ID to reflect additional scope

Data structure and related naming changes:

• Added a new GlobalValueSummary type which holds summary info common to both the function and globalvar summaries.
• Made the existing FunctionSummary record a derived class of the new GlobalValueSummary.
• Added a new derived GlobalVarSummary class of GlobalValueSummary.
• Renamed FunctionInfo* -> GlobalValueInfo*
• Renamed FunctionSummary -> GlobalValueSummary or just Summary as appropriate
• Misc other variable and method renamings to reflect above changes.

TODO:

• Rename FunctionInfoIndex to something more broad (ModuleIndex?) (ditto for related classes like FunctionInfoIndexBitcodeReader).
• Move getGUID and getGlobalIdentifier from Function to GlobalValue class.
• Some lingering FunctionSummary references that need to be updated to GlobalValueSummary or just Summary.

I will work on the TODO items now but wanted to get this patch out for review,
testing by Mehdi, and feedback.

Note that some of these changes (many of the renames, can be committed first
as NFC changes).

[mehdi_amini]

LGTM overall. Still some comments/questions below.

Thanks for the good work!

include/llvm/IR/FunctionInfo.h

92

Can't/shouldn't be protected?

109

why to be written to...?

150

I think the usual terminology in LLVM is "PGO" (I had to google FDO)
(same below)

155

F?

Also again the "to be written to" seems off to me.

209

Can't you have a single ctor?

GlobalValueInfo(uint64_t Offset = 0, std::unique_ptr<GlobalValueSummary> Summary = nullptr)

lib/Bitcode/Reader/BitcodeReader.cpp

416

I guess more renaming could have been done here right?
(I really don't mind, but since you cared to rename many places below...)

445

doc

5884

Mmmmm....

5886

Mmmmm (bis)....

lib/Bitcode/Writer/BitcodeWriter.cpp

849–853

I'd write it:

if (M->getValueSymbolTable().empty())
  return 0;
return WriteValueSymbolTableForwardDecl(Stream);

2346

Why is it no longer valid?

2475–2507

Mind adding a one line comment?

2488

Guarantee on the recursion depth?

2578

if(CS) could be hoisted out of the loop.

2590

You depend on the order of the calls.
If an instruction first add a call to a function, but later on will reference it, you won't remove it from RefEdges.

This may be intended and you want to have an accurate count of ref + calls and here you're trying to filter calls out of refedges. However a call instruction could legitimately refer the function (a call passing a function pointer as an argument for instance)

2592

?

2616

?

2992

Isn't the opposite that the code is doing?

[mehdi_amini]

Another question: you reported measurements in the description, is it up to date with the new patch?

[tejohnson]

In D17212#369588, @joker.eph wrote:

Another question: you reported measurements in the description, is it up to date with the new patch?

Not yet, need to update that. The size of the thinlto.bc combined index went up quite a bit percentage wise with the ref graph, especially once I corrected it to recursively look for references, and added in the global variable init refs. Here are the new stats, only have non-PGO so far, will collect PGO as well and update the summary (once I make a fix described below to add linkage types to variables):

For 483.xalancbmk (non-PGO):
Total .o (bitcode) size: +1.24%
Combined .thinlto.bc size: +120%
Aggregate .o + .thinlto.bc size: +3.16%

I gave the last number because the size of the combined index .thinlto.bc file is on the same order of magnitude as the largest individual .o bitcode files, so the increase should be taken in that context.

include/llvm/IR/FunctionInfo.h

92

Good point, will make protected.

109

Good catch, this was leftover from the prior patch when it was part of a bitcode writer helper, didn't updated it up after moving here. Will fix.

150

Will fix...bummer that every compiler I have worked on seems to use a different term! PGO/FDO/PBO...bah.

155

Same issue as above, stale comment, will update.

209

Yes, will fix.

lib/Bitcode/Reader/BitcodeReader.cpp

416

Yep, this was part of the TODO list in this patch update. Working on that now. Specifically, I'm changing FunctionIndex* and FunctionInfoIndex* to ModuleSummaryIndex*. I left this for a follow-on update because already the renaming was pretty extensive, and this particular change bleeds into some of the interfaces and variable/field names used in other parts of the compiler (clang etc).

445

Will do.

5884

Oops. In my haste to get the renaming done and send this out, forgot that I planned to add a linkage type to the global var init records. Will add now.

5886

Ditto.

lib/Bitcode/Writer/BitcodeWriter.cpp

849–853

Good idea, will fix.

2346

Good catch. I think this got removed when I was using a different data structure here for awhile, and I missed it when restoring the old approach. Will add back.

2475–2507

Will do.

2488

Beyond the Visited set check earlier? What would you like to see?

2578

Yes, missed this when I cleaned things up from when I was initially looking for non-call references inside this loop.

2590

I don't think the order of calls matters? The reference list is populated once outside of this loop.

On your second point, that is true that this will cause a function both called and referenced in another way to only be recorded as called by this function. Is it important to list both types of references? I was thinking that it was important for importing needs to distinguish the functions being called from the other non-call references, but that essentially the combination of the two are the full reference set of the function. If I should put it in both places, I will need to figure out how to distinguish the two types of function references in findRefEdges.

2592

More cruft left from when I was looking for non-call refs in this loop, will remove

2616

Incomplete cleanup of debugging output, will remove.

2992

Yes, good catch. I think what I initially wanted was to record them this way, but the issue is that the alias doesn't have a separate summary, which is why we are grabbing the aliasee summary here. Will update the comment.

[mehdi_amini]

lib/Bitcode/Reader/BitcodeReader.cpp

416

Fine with me.

lib/Bitcode/Writer/BitcodeWriter.cpp

849–853

Re-reading it, the variable had the nice property of having a name, making it very clear what is returned.
If you adopt the above suggested change, I would add a one line comment along the line of // return the VSTOffsetPlaceholder if we have a VST

2488

I was not worried on non-termination or corretness, but depth that would explode the stack.

It was late and I couldn't think clearly enough to find the answer myself. I just got a coffee so I should be able to answer myself now ;)

-> For every instruction you will pull transitively all the operands until you reach a global (or something already seen). i.e. this is a DFS search on the SSA graph.
If I'm correct, a worklist would probably be appropriate here.

2578

Re-reading, I'm not even sure what this loop on the operand is doing at all!
Wouldn't the code do exactly the same if you just remove the loop and turn the test into if (CS)`

2590

I pointed what I saw as an inconsistency, but I may misunderstand totally what you're trying to do here.

So I will assume in the following that:

• RefEdges contains the global values referenced by the current function
• CallGraphEdges contains the list of Functions called by the current function

Do we agree that we should have either of these properties:

1. A function that is part of CallGraphEdges should *not* be present in RefEdges even if it is referenced in another way than a call
2. A function that is part of CallGraphEdges should *also* be present in RefEdges *if it is referenced* in another way than a call

What I read from your code right now is:

3. A function that is part of CallGraphEdges *may or may not* be present in RefEdges *if it is referenced* in another way than a call.

[tejohnson]

lib/Bitcode/Writer/BitcodeWriter.cpp

849–853

Will do.

2488

I wouldn't have thought that an instruction would be large enough to cause stack explosion. But I have no issue with changing this to a worklist iteration instead.

2578

Right, this loop is bogus!

2590

Yep, I was distracted by the bogus loop above, we are collecting this per instruction so there is an ordering issue, and we are getting #3 which is undesirable.

I think the way to fix this is to check for the callsite first, then pass in some info from the callsite to findRefEdges so that the callsite reference is itself ignored. I.e. pass in either the callee GV and skip it to get #1, or pass in the Use to get #2.

I saw David's follow-on that he thinks #2 is best. I can try that.

[mehdi_amini]

lib/Bitcode/Writer/BitcodeWriter.cpp

2488

I may misunderstand, but it seems to me that the depth is not the width of a single instruction, but potentially on the order of the number of instructions in the Function.
If I'm wrong and you're bounded somehow by the number of operands, then recursion is fine with me.

[tejohnson]

lib/Bitcode/Writer/BitcodeWriter.cpp

2488

If you are right then this needs to change beyond moving to a worklist, as I only intended to capture the references within a single instruction or variable def.

The two entry points to this routine are in WriteFunction, where we pass in an Instruction as the User, and in WriteModuleLevelReferences, where we pass in a GlobalVariable (and I had confirmed that the operands of a variable are its initializer). We recursively walk the given User's operands(). I wouldn't have thought that we could jump from a given Instruction to other instructions in the function this way?

[tejohnson]

lib/Bitcode/Writer/BitcodeWriter.cpp

2590

Actually it turns out to be pretty simple, we only need to pass in the callee GV to findRefEdges to exclude it (because you can't have both a call and a non-call reference to a function in the same instruction, at least I couldn't find a way!).

For xalancbmk this fix actually reduced the combined index and .o sizes a bit. It turns out that with the old flow we were inadvertently including intrinsics (which were ignored in the call graph edge list) in the reference list.

In the new version of the patch I will upload shortly I've included a new test that checks for both issues (ensuring a function is in both the call list and ref list if it is accessed both ways by the function, and ignoring intrinsics).

[tejohnson]

• Address Mehdi's review comments.

[tejohnson]

Fixes to findRefEdges discussed in review and IRC

Two main changes to findRefEdges:

1. Use worklist iteration instead of recursion

The reason is that when we invoke with an Instruction, it will iterate
into other instructions in the function when it encounters a use of
a local variable defined in another instruction. Ultimately we are
analyzing all instructions in the function, and we prevent duplicate
work by sharing the Visited set across all instructions in the function.
However, using a worklist approach is more efficient for large functions
where with recursion we may end up recursing many times (using much
stack).

2. More accurate detection and skipping of callsite references

The prior solution would miss the non-call reference to foo in the
following case:
foo((void *)foo);
since we were skipping all GVs that matched the callee GV.

Additionally, as noted in 1) we may traverse through local variables
defined on other instructions. Those other instructions may be calls
which return a value. We want to make sure we don't count calls in other
instructions encountered this way as non-call refs. Depending on the
order of traversal (e.g. a use on a phi encountered before the call
instruction), we can't count on the call being in the visited set.

Finally, doing the checking for callsites here avoids the need for
WriteFunction to special case call instructions, which has its own set
of issues. For example, one solution considered was for call
instructions to invoke findRefEdges on each of its data_ops(). This
means findRefEdges would need to distinguish between a GV user that was
passed in being either a reference (if it was a call instruction
operand) or a global variable for which we want to analyze initializers
(i.e. called from WriteModuleLevelReferences).

Finally, enhanced the new test quite a bit to check for the various
cases I encountered when fixing findRefEdges.

[mehdi_amini]

LGTM.
Thanks! I think we reached the point of "good enough". I feel this review was productive :)

[tejohnson]

In D17212#372070, @joker.eph wrote:

LGTM.
Thanks! I think we reached the point of "good enough". I feel this review was productive :)

Great, thanks for the reviews! Agreed, the final state is much more complete and accurate.

Will update the title and summary along with updated stats before I commit.

[tejohnson]

This is the same as what was reviewed, except for 2 small changes that can be post-commit reviewed:

Mehdi: A bad interaction between my changes and your libLTO interfaces committed this week (which merges into the first index when creating the combined index, instead of creating a new combined index and merging everything into it). See removeEmptySummaryEntries() and its callsite for the detailed explanation of what I needed to do since I am now parsing the VST first and need to do some eager creation of index entries that was being cleaned up as we merged the indexes.

Easwaran: Updated getBlockProfileCount as per our conversation this morning to do the multiplication before the integer divide in order to avoid inaccuracies due to truncation.

include/llvm/Bitcode/LLVMBitCodes.h

enum BlockIDs {
   METADATA_BLOCK_ID,
   METADATA_ATTACHMENT_ID,
 
   TYPE_BLOCK_ID_NEW,
 
   USELIST_BLOCK_ID,
 
   MODULE_STRTAB_BLOCK_ID,
-  FUNCTION_SUMMARY_BLOCK_ID,
+  GLOBALVAL_SUMMARY_BLOCK_ID,
 
   OPERAND_BUNDLE_TAGS_BLOCK_ID,
 
   METADATA_KIND_BLOCK_ID
 };
 
 /// Identification block contains a string that describes the producer details,
 /// and an epoch that defines the auto-upgrade capability.
enum TypeSymtabCodes {
     TST_CODE_ENTRY = 1     // TST_ENTRY: [typeid, namechar x N]
   };
 
   // Value symbol table codes.
   enum ValueSymtabCodes {
     VST_CODE_ENTRY   = 1,   // VST_ENTRY: [valueid, namechar x N]
     VST_CODE_BBENTRY = 2,   // VST_BBENTRY: [bbid, namechar x N]
     VST_CODE_FNENTRY = 3,   // VST_FNENTRY: [valueid, offset, namechar x N]
-    // VST_COMBINED_FNENTRY: [funcsumoffset, funcguid]
-    VST_CODE_COMBINED_FNENTRY = 4
+    // VST_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid]
+    VST_CODE_COMBINED_GVDEFENTRY = 4,
+    // VST_COMBINED_ENTRY: [valueid, refguid]
+    VST_CODE_COMBINED_ENTRY = 5
   };
 
   // The module path symbol table only has one code (MST_CODE_ENTRY).
   enum ModulePathSymtabCodes {
     MST_CODE_ENTRY   = 1,  // MST_ENTRY: [modid, namechar x N]
   };
 
   // The function summary section uses different codes in the per-module
   // and combined index cases.
   enum FunctionSummarySymtabCodes {
-    FS_CODE_PERMODULE_ENTRY = 1,  // FS_ENTRY: [valueid, linkage, instcount]
-    FS_CODE_COMBINED_ENTRY  = 2,  // FS_ENTRY: [modid, linkage, instcount]
+    // PERMODULE: [valueid, linkage, instcount, numrefs, numrefs x valueid,
+    //             n x (valueid, callsitecount)]
+    FS_PERMODULE = 1,
+    // PERMODULE_PROFILE: [valueid, linkage, instcount, numrefs,
+    //                     numrefs x valueid,
+    //                     n x (valueid, callsitecount, profilecount)]
+    FS_PERMODULE_PROFILE = 2,
+    // PERMODULE_GLOBALVAR_INIT_REFS: [valueid, linkage, n x valueid]
+    FS_PERMODULE_GLOBALVAR_INIT_REFS = 3,
+    // COMBINED: [modid, linkage, instcount, numrefs, numrefs x valueid,
+    //            n x (valueid, callsitecount)]
+    FS_COMBINED = 4,
+    // COMBINED_PROFILE: [modid, linkage, instcount, numrefs,
+    //                    numrefs x valueid,
+    //                    n x (valueid, callsitecount, profilecount)]
+    FS_COMBINED_PROFILE = 5,
+    // COMBINED_GLOBALVAR_INIT_REFS: [modid, linkage, n x valueid]
+    FS_COMBINED_GLOBALVAR_INIT_REFS = 6,
   };
 
   enum MetadataCodes {
     METADATA_STRING        = 1,   // MDSTRING:      [values]
     METADATA_VALUE         = 2,   // VALUE:         [type num, value num]
     METADATA_NODE          = 3,   // NODE:          [n x md num]
     METADATA_NAME          = 4,   // STRING:        [values]
     METADATA_DISTINCT_NODE = 5,   // DISTINCT_NODE: [n x md num]
     METADATA_KIND          = 6,   // [n x [id, name]]

include/llvm/Bitcode/ReaderWriter.h

namespace llvm {
   /// error, this returns "".
   std::string getBitcodeProducerString(MemoryBufferRef Buffer,
                                        LLVMContext &Context);
 
   /// Read the specified bitcode file, returning the module.
   ErrorOr<std::unique_ptr<Module>> parseBitcodeFile(MemoryBufferRef Buffer,
                                                     LLVMContext &Context);
 
-  /// Check if the given bitcode buffer contains a function summary block.
-  bool hasFunctionSummary(MemoryBufferRef Buffer,
+  /// Check if the given bitcode buffer contains a summary block.
+  bool hasGlobalValueSummary(MemoryBufferRef Buffer,
                              DiagnosticHandlerFunction DiagnosticHandler);
 
   /// Parse the specified bitcode buffer, returning the function info index.
   /// If IsLazy is true, parse the entire function summary into
   /// the index. Otherwise skip the function summary section, and only create
   /// an index object with a map from function name to function summary offset.
   /// The index is used to perform lazy function summary reading later.
   ErrorOr<std::unique_ptr<FunctionInfoIndex>>
   getFunctionInfoIndex(MemoryBufferRef Buffer,
namespace llvm {
   ///
   /// For streams where it matters, the given stream should be in "binary"
   /// mode.
   ///
   /// If \c ShouldPreserveUseListOrder, encode the use-list order for each \a
   /// Value in \c M.  These will be reconstructed exactly when \a M is
   /// deserialized.
   ///
-  /// If \c EmitFunctionSummary, emit the function summary index (currently
+  /// If \c EmitSummaryIndex, emit the module's summary index (currently
   /// for use in ThinLTO optimization).
   void WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                           bool ShouldPreserveUseListOrder = false,
-                          bool EmitFunctionSummary = false);
+                          bool EmitSummaryIndex = false);
 
-  /// Write the specified function summary index to the given raw output stream,
+  /// Write the specified module summary index to the given raw output stream,
   /// where it will be written in a new bitcode block. This is used when
   /// writing the combined index file for ThinLTO.
-  void WriteFunctionSummaryToFile(const FunctionInfoIndex &Index,
-                                  raw_ostream &Out);
+  void WriteIndexToFile(const FunctionInfoIndex &Index, raw_ostream &Out);
 
   /// isBitcodeWrapper - Return true if the given bytes are the magic bytes
   /// for an LLVM IR bitcode wrapper.
   ///
   inline bool isBitcodeWrapper(const unsigned char *BufPtr,
                                const unsigned char *BufEnd) {
     // See if you can find the hidden message in the magic bytes :-).
     // (Hint: it's a little-endian encoding.)

include/llvm/IR/FunctionInfo.h

 //===-- llvm/FunctionInfo.h - Function Info Index ---------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 /// @file
 /// FunctionInfo.h This file contains the declarations the classes that hold
-///  the function info index and summary.
+///  the module index and summary for function importing.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_FUNCTIONINFO_H
 #define LLVM_IR_FUNCTIONINFO_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
-/// \brief Function summary information to aid decisions and implementation of
-/// importing.
+/// \brief Class to accumulate and hold information about a callee.
+struct CalleeInfo {
+  /// The static number of callsites calling corresponding function.
+  unsigned CallsiteCount;
+  /// The cumulative profile count of calls to corresponding function
+  /// (if using PGO, otherwise 0).
+  uint64_t ProfileCount;
+  CalleeInfo() = default;
+  CalleeInfo(unsigned CallsiteCount, uint64_t ProfileCount)
+      : CallsiteCount(CallsiteCount), ProfileCount(ProfileCount) {}
+  CalleeInfo &operator+=(uint64_t RHSProfileCount) {
+    CallsiteCount++;
+    ProfileCount += RHSProfileCount;
+    return *this;
+  }
+};
+
+/// \brief Function and variable summary information to aid decisions and
+/// implementation of importing.
 ///
-/// This is a separate class from FunctionInfo to enable lazy reading of this
-/// function summary information from the combined index file during imporing.
-class FunctionSummary {
+/// This is a separate class from GlobalValueInfo to enable lazy reading of this
+/// summary information from the combined index file during imporing.
+class GlobalValueSummary {
+public:
+  /// \brief Sububclass discriminator (for dyn_cast<> et al.)
+  enum SummaryKind { FunctionKind, GlobalVarKind };
+
 private:
-  /// \brief Path of module containing function IR, used to locate module when
-  /// importing this function.
+  /// Kind of summary for use in dyn_cast<> et al.
+  SummaryKind Kind;
+
+  /// \brief Path of module IR containing value's definition, used to locate
+  /// module during importing.
   ///
-  /// This is only used during parsing of the combined function index, or when
+  /// This is only used during parsing of the combined index, or when
   /// parsing the per-module index for creation of the combined function index,
   /// not during writing of the per-module index which doesn't contain a
   /// module path string table.
   StringRef ModulePath;
 
-  /// \brief The linkage type of the associated function.
+  /// \brief The linkage type of the associated global value.
   ///
-  /// One use is to flag functions that have local linkage types and need to
+  /// One use is to flag values that have local linkage types and need to
   /// have module identifier appended before placing into the combined
-  /// index, to disambiguate from other functions with the same name.
+  /// index, to disambiguate from other values with the same name.
   /// In the future this will be used to update and optimize linkage
   /// types based on global summary-based analysis.
-  GlobalValue::LinkageTypes FunctionLinkage;
-
-  // The rest of the information is used to help decide whether importing
-  // is likely to be profitable.
-  // Other information will be added as the importing is tuned, such
-  // as hotness (when profile available), and other function characteristics.
+  GlobalValue::LinkageTypes Linkage;
 
-  /// Number of instructions (ignoring debug instructions, e.g.) computed
-  /// during the initial compile step when the function index is first built.
-  unsigned InstCount;
+  /// List of GUIDs 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<uint64_t> RefEdgeList;
+
+protected:
+  /// GlobalValueSummary constructor.
+  GlobalValueSummary(SummaryKind K, GlobalValue::LinkageTypes Linkage)
+      : Kind(K), Linkage(Linkage) {}
 
 public:
-  /// Construct a summary object from summary data expected for all
-  /// summary records.
-  FunctionSummary(unsigned NumInsts) : InstCount(NumInsts) {}
+  /// Which kind of summary subclass this is.
+  SummaryKind getSummaryKind() const { return Kind; }
 
   /// Set the path to the module containing this function, for use in
   /// the combined index.
   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
 
   /// Get the path to the module containing this function.
   StringRef modulePath() const { return ModulePath; }
 
-  /// Record linkage type.
-  void setFunctionLinkage(GlobalValue::LinkageTypes Linkage) {
-    FunctionLinkage = Linkage;
-  }
+  /// Return linkage type recorded for this global value.
+  GlobalValue::LinkageTypes linkage() const { return Linkage; }
+
+  /// Record a reference from this global value to the global value identified
+  /// by \p RefGUID.
+  void addRefEdge(uint64_t RefGUID) { RefEdgeList.push_back(RefGUID); }
+
+  /// Record a reference from this global value to each global value identified
+  /// in \p RefEdges.
+  void addRefEdges(DenseSet<unsigned> &RefEdges) {
+    for (auto &RI : RefEdges)
+      addRefEdge(RI);
+  }
+
+  /// Return the list of GUIDs referenced by this global value definition.
+  std::vector<uint64_t> &refs() { return RefEdgeList; }
+  const std::vector<uint64_t> &refs() const { return RefEdgeList; }
+};
+
+/// \brief Function summary information to aid decisions and implementation of
+/// importing.
+class FunctionSummary : public GlobalValueSummary {
+public:
+  /// <CalleeGUID, CalleeInfo> call edge pair.
+  typedef std::pair<uint64_t, CalleeInfo> EdgeTy;
 
-  /// Return linkage type recorded for this function.
-  GlobalValue::LinkageTypes getFunctionLinkage() const {
-    return FunctionLinkage;
+private:
+  /// Number of instructions (ignoring debug instructions, e.g.) computed
+  /// during the initial compile step when the function index is first built.
+  unsigned InstCount;
+
+  /// List of <CalleeGUID, CalleeInfo> call edge pairs from this function.
+  std::vector<EdgeTy> CallGraphEdgeList;
+
+public:
+  /// Summary constructors.
+  FunctionSummary(GlobalValue::LinkageTypes Linkage, unsigned NumInsts)
+      : GlobalValueSummary(FunctionKind, Linkage), InstCount(NumInsts) {}
+
+  /// 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(uint64_t CalleeGUID, CalleeInfo Info) {
+    CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info));
+  }
+
+  /// Record a call graph edge from this function to each function recorded
+  /// in \p CallGraphEdges.
+  void addCallGraphEdges(DenseMap<unsigned, CalleeInfo> &CallGraphEdges) {
+    for (auto &EI : CallGraphEdges)
+      addCallGraphEdge(EI.first, EI.second);
+  }
+
+  /// Return the list of <CalleeGUID, ProfileCount> pairs.
+  std::vector<EdgeTy> &edges() { return CallGraphEdgeList; }
+  const std::vector<EdgeTy> &edges() const { return CallGraphEdgeList; }
 };
 
-/// \brief Class to hold pointer to function summary and information required
-/// for parsing it.
+/// \brief Global variable summary information to aid decisions and
+/// implementation of importing.
 ///
-/// For the per-module index, this holds the bitcode offset
-/// of the corresponding function block. For the combined index,
-/// after parsing of the \a ValueSymbolTable, this initially
-/// holds the offset of the corresponding function summary bitcode
-/// record. After parsing the associated summary information from the summary
-/// block the \a FunctionSummary is populated and stored here.
-class FunctionInfo {
+/// 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(GlobalValue::LinkageTypes Linkage)
+      : GlobalValueSummary(GlobalVarKind, Linkage) {}
+
+  /// Check if this is a global variable summary.
+  static bool classof(const GlobalValueSummary *GVS) {
+    return GVS->getSummaryKind() == GlobalVarKind;
+  }
+};
+
+/// \brief Class to hold pointer to summary object and information required
+/// for parsing or writing it.
+class GlobalValueInfo {
 private:
-  /// Function summary information used to help make ThinLTO importing
-  /// decisions.
-  std::unique_ptr<FunctionSummary> Summary;
+  /// Summary information used to help make ThinLTO importing decisions.
+  std::unique_ptr<GlobalValueSummary> Summary;
 
-  /// \brief The bitcode offset corresponding to either the associated
-  /// function's function body record, or its function summary record,
+  /// \brief The bitcode offset corresponding to either an associated
+  /// function's function body record, or to an associated summary record,
   /// depending on whether this is a per-module or combined index.
   ///
   /// This bitcode offset is written to or read from the associated
-  /// \a ValueSymbolTable entry for the function.
-  /// For the per-module index this holds the bitcode offset of the
-  /// function's body record  within bitcode module block in its module,
-  /// which is used during lazy function parsing or ThinLTO importing.
+  /// \a ValueSymbolTable entry for a function.
+  /// For the per-module index this holds the bitcode offset of a
+  /// function's body record within bitcode module block in its module,
+  /// although this field is currently only used when writing the VST
+  /// (it is set to 0 and also unused when this is a global variable).
   /// For the combined index this holds the offset of the corresponding
-  /// function summary record, to enable associating the combined index
+  /// summary record, to enable associating the combined index
   /// VST records with the summary records.
   uint64_t BitcodeIndex;
 
 public:
-  /// Constructor used during parsing of VST entries.
-  FunctionInfo(uint64_t FuncOffset)
-      : Summary(nullptr), BitcodeIndex(FuncOffset) {}
-
-  /// Constructor used for per-module index bitcode writing.
-  FunctionInfo(uint64_t FuncOffset,
-               std::unique_ptr<FunctionSummary> FuncSummary)
-      : Summary(std::move(FuncSummary)), BitcodeIndex(FuncOffset) {}
-
-  /// Record the function summary information parsed out of the function
-  /// summary block during parsing or combined index creation.
-  void setFunctionSummary(std::unique_ptr<FunctionSummary> FuncSummary) {
-    Summary = std::move(FuncSummary);
+  GlobalValueInfo(uint64_t Offset = 0,
+                  std::unique_ptr<GlobalValueSummary> Summary = nullptr)
+      : Summary(std::move(Summary)), BitcodeIndex(Offset) {}
+
+  /// Record the summary information parsed out of the summary block during
+  /// parsing or combined index creation.
+  void setSummary(std::unique_ptr<GlobalValueSummary> GVSummary) {
+    Summary = std::move(GVSummary);
   }
 
-  /// Get the function summary recorded for this function.
-  FunctionSummary *functionSummary() const { return Summary.get(); }
+  /// Get the summary recorded for this global value.
+  GlobalValueSummary *summary() const { return Summary.get(); }
 
-  /// Get the bitcode index recorded for this function, depending on
-  /// the index type.
+  /// Get the bitcode index recorded for this value symbol table entry.
   uint64_t bitcodeIndex() const { return BitcodeIndex; }
 
-  /// Record the bitcode index for this function, depending on
-  /// the index type.
-  void setBitcodeIndex(uint64_t FuncOffset) { BitcodeIndex = FuncOffset; }
+  /// Set the bitcode index recorded for this value symbol table entry.
+  void setBitcodeIndex(uint64_t Offset) { BitcodeIndex = Offset; }
 };
 
-/// List of function info structures for a particular function name held
-/// in the FunctionMap. Requires a vector in the case of multiple
-/// COMDAT functions of the same name.
-typedef std::vector<std::unique_ptr<FunctionInfo>> FunctionInfoList;
+/// List of global value info structures for a particular value held
+/// in the GlobalValueMap. Requires a vector in the case of multiple
+/// COMDAT values of the same name.
+typedef std::vector<std::unique_ptr<GlobalValueInfo>> GlobalValueInfoList;
 
-/// Map from function GUID to corresponding function info structures.
+/// Map from global value GUID to corresponding info structures.
 /// Use a std::map rather than a DenseMap since it will likely incur
 /// less overhead, as the value type is not very small and the size
 /// of the map is unknown, resulting in inefficiencies due to repeated
 /// insertions and resizing.
-typedef std::map<uint64_t, FunctionInfoList> FunctionInfoMapTy;
+typedef std::map<uint64_t, GlobalValueInfoList> GlobalValueInfoMapTy;
 
-/// Type used for iterating through the function info map.
-typedef FunctionInfoMapTy::const_iterator const_funcinfo_iterator;
-typedef FunctionInfoMapTy::iterator funcinfo_iterator;
+/// Type used for iterating through the global value info map.
+typedef GlobalValueInfoMapTy::const_iterator const_globalvalueinfo_iterator;
+typedef GlobalValueInfoMapTy::iterator globalvalueinfo_iterator;
 
 /// String table to hold/own module path strings, which additionally holds the
 /// module ID assigned to each module during the plugin step. The StringMap
 /// makes a copy of and owns inserted strings.
 typedef StringMap<uint64_t> ModulePathStringTableTy;
 
-/// Class to hold module path string table and function map,
+/// Class to hold module path string table and global value map,
 /// and encapsulate methods for operating on them.
 class FunctionInfoIndex {
 private:
-  /// Map from function name to list of function information instances
-  /// for functions of that name (may be duplicates in the COMDAT case, e.g.).
-  FunctionInfoMapTy FunctionMap;
+  /// Map from value name to list of information instances for values of that
+  /// name (may be duplicates in the COMDAT case, e.g.).
+  GlobalValueInfoMapTy GlobalValueMap;
 
   /// Holds strings for combined index, mapping to the corresponding module ID.
   ModulePathStringTableTy ModulePathStringTable;
 
 public:
   FunctionInfoIndex() = default;
 
   // Disable the copy constructor and assignment operators, so
   // no unexpected copying/moving occurs.
   FunctionInfoIndex(const FunctionInfoIndex &) = delete;
   void operator=(const FunctionInfoIndex &) = delete;
 
-  funcinfo_iterator begin() { return FunctionMap.begin(); }
-  const_funcinfo_iterator begin() const { return FunctionMap.begin(); }
-  funcinfo_iterator end() { return FunctionMap.end(); }
-  const_funcinfo_iterator end() const { return FunctionMap.end(); }
+  globalvalueinfo_iterator begin() { return GlobalValueMap.begin(); }
+  const_globalvalueinfo_iterator begin() const {
+    return GlobalValueMap.begin();
+  }
+  globalvalueinfo_iterator end() { return GlobalValueMap.end(); }
+  const_globalvalueinfo_iterator end() const { return GlobalValueMap.end(); }
+
+  /// Get the list of global value info objects for a given value name.
+  const GlobalValueInfoList &getGlobalValueInfoList(StringRef FuncName) {
+    return GlobalValueMap[Function::getGUID(FuncName)];
+  }
 
-  /// Get the list of function info objects for a given function.
-  const FunctionInfoList &getFunctionInfoList(StringRef FuncName) {
-    return FunctionMap[Function::getGUID(FuncName)];
+  /// Get the list of global value info objects for a given value name.
+  const const_globalvalueinfo_iterator
+  findGlobalValueInfoList(StringRef ValueName) const {
+    return GlobalValueMap.find(Function::getGUID(ValueName));
   }
 
-  /// Get the list of function info objects for a given function.
-  const const_funcinfo_iterator findFunctionInfoList(StringRef FuncName) const {
-    return FunctionMap.find(Function::getGUID(FuncName));
+  /// Get the list of global value info objects for a given value GUID.
+  const const_globalvalueinfo_iterator
+  findGlobalValueInfoList(uint64_t ValueGUID) const {
+    return GlobalValueMap.find(ValueGUID);
   }
 
-  /// Add a function info for a function of the given name.
-  void addFunctionInfo(StringRef FuncName, std::unique_ptr<FunctionInfo> Info) {
-    FunctionMap[Function::getGUID(FuncName)].push_back(std::move(Info));
+  /// Add a global value info for a value of the given name.
+  void addGlobalValueInfo(StringRef ValueName,
+                          std::unique_ptr<GlobalValueInfo> Info) {
+    GlobalValueMap[Function::getGUID(ValueName)].push_back(std::move(Info));
   }
 
-  void addFunctionInfo(uint64_t FuncGUID, std::unique_ptr<FunctionInfo> Info) {
-    FunctionMap[FuncGUID].push_back(std::move(Info));
+  /// Add a global value info for a value of the given GUID.
+  void addGlobalValueInfo(uint64_t ValueGUID,
+                          std::unique_ptr<GlobalValueInfo> Info) {
+    GlobalValueMap[ValueGUID].push_back(std::move(Info));
   }
 
   /// Iterator to allow writer to walk through table during emission.
   iterator_range<StringMap<uint64_t>::const_iterator>
   modPathStringEntries() const {
     return llvm::make_range(ModulePathStringTable.begin(),
                             ModulePathStringTable.end());
   }
 
   /// Get the module ID recorded for the given module path.
   uint64_t getModuleId(const StringRef ModPath) const {
     return ModulePathStringTable.lookup(ModPath);
   }
 
-  /// Add the given per-module index into this function index/summary,
+  /// Add the given per-module index into this module index/summary,
   /// assigning it the given module ID. Each module merged in should have
   /// a unique ID, necessary for consistent renaming of promoted
   /// static (local) variables.
   void mergeFrom(std::unique_ptr<FunctionInfoIndex> Other,
                  uint64_t NextModuleId);
 
   /// Convenience method for creating a promoted global name
   /// for the given value name of a local, and its original module's ID.
public:
   /// to have exported functions.
   bool hasExportedFunctions(const Module &M) const {
     return ModulePathStringTable.count(M.getModuleIdentifier());
   }
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/Object/FunctionIndexObjectFile.h

public:
   static ErrorOr<MemoryBufferRef> findBitcodeInObject(const ObjectFile &Obj);
 
   /// \brief Finds and returns bitcode in the given memory buffer (which may
   /// be either a bitcode file or a native object file with embedded bitcode),
   /// or an error code if not found.
   static ErrorOr<MemoryBufferRef>
   findBitcodeInMemBuffer(MemoryBufferRef Object);
 
-  /// \brief Looks for function summary in the given memory buffer,
+  /// \brief Looks for summary sections in the given memory buffer,
   /// returns true if found, else false.
   static bool
-  hasFunctionSummaryInMemBuffer(MemoryBufferRef Object,
+  hasGlobalValueSummaryInMemBuffer(MemoryBufferRef Object,
                                    DiagnosticHandlerFunction DiagnosticHandler);
 
   /// \brief Parse function index in the given memory buffer.
   /// Return new FunctionIndexObjectFile instance containing parsed function
   /// summary/index.
   static ErrorOr<std::unique_ptr<FunctionIndexObjectFile>>
   create(MemoryBufferRef Object, DiagnosticHandlerFunction DiagnosticHandler,
          bool IsLazy = false);
 

include/llvm/ProfileData/ProfileCommon.h

 // This file contains data structures and functions common to both instrumented
 // and sample profiling.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PROFILEDATA_PROFILE_COMMON_H
 #define LLVM_PROFILEDATA_PROFILE_COMMON_H
 
+#include "llvm/ADT/APInt.h"
 #include <cstdint>
 #include <functional>
 #include <map>
 #include <vector>
 
 #include "llvm/Support/Casting.h"
 
 namespace llvm {

 }
 
 SummaryEntryVector &ProfileSummary::getDetailedSummary() {
   if (!DetailedSummaryCutoffs.empty() && DetailedSummary.empty())
     computeDetailedSummary();
   return DetailedSummary;
 }
 
+/// Helper to compute the profile count for a block, based on the
+/// ratio of its frequency to the entry block frequency, multiplied
+/// by the entry block count.
+inline uint64_t getBlockProfileCount(uint64_t BlockFreq, uint64_t EntryFreq,
+                                     uint64_t EntryCount) {
+  APInt ScaledCount(128, EntryCount);
+  APInt BlockFreqAPInt(128, BlockFreq);
+  APInt EntryFreqAPInt(128, EntryFreq);
+  ScaledCount *= BlockFreqAPInt.udiv(EntryFreqAPInt);
+  return ScaledCount.getLimitedValue();
+}
+
 } // end namespace llvm
 #endif

lib/Bitcode/Reader/BitcodeReader.cpp

private:
   std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
   std::error_code findFunctionInStream(
       Function *F,
       DenseMap<Function *, uint64_t>::iterator DeferredFunctionInfoIterator);
 };
 
 /// Class to manage reading and parsing function summary index bitcode
 /// files/sections.
 class FunctionIndexBitcodeReader {
   DiagnosticHandlerFunction DiagnosticHandler;
 
-  /// Eventually points to the function index built during parsing.
+  /// Eventually points to the module index built during parsing.
   FunctionInfoIndex *TheIndex = nullptr;
 
   std::unique_ptr<MemoryBuffer> Buffer;
   std::unique_ptr<BitstreamReader> StreamFile;
   BitstreamCursor Stream;
 
   /// \brief Used to indicate whether we are doing lazy parsing of summary data.
   ///
   /// If false, the summary section is fully parsed into the index during
   /// the initial parse. Otherwise, if true, the caller is expected to
   /// invoke \a readFunctionSummary for each summary needed, and the summary
   /// section is thus parsed lazily.
   bool IsLazy = false;
 
   /// Used to indicate whether caller only wants to check for the presence
-  /// of the function summary bitcode section. All blocks are skipped,
-  /// but the SeenFuncSummary boolean is set.
-  bool CheckFuncSummaryPresenceOnly = false;
+  /// of the global value summary bitcode section. All blocks are skipped,
+  /// but the SeenGlobalValSummary boolean is set.
+  bool CheckGlobalValSummaryPresenceOnly = false;
 
-  /// Indicates whether we have encountered a function summary section
-  /// yet during parsing, used when checking if file contains function
+  /// Indicates whether we have encountered a global value summary section
+  /// yet during parsing, used when checking if file contains global value
   /// summary section.
-  bool SeenFuncSummary = false;
+  bool SeenGlobalValSummary = false;
 
-  /// \brief Map populated during function summary section parsing, and
-  /// consumed during ValueSymbolTable parsing.
-  ///
-  /// Used to correlate summary records with VST entries. For the per-module
-  /// index this maps the ValueID to the parsed function summary, and
-  /// for the combined index this maps the summary record's bitcode
-  /// offset to the function summary (since in the combined index the
-  /// VST records do not hold value IDs but rather hold the function
-  /// summary record offset).
-  DenseMap<uint64_t, std::unique_ptr<FunctionSummary>> SummaryMap;
+  /// Indicates whether we have already parsed the VST, used for error checking.
+  bool SeenValueSymbolTable = false;
+
+  /// Set to the offset of the VST recorded in the MODULE_CODE_VSTOFFSET record.
+  /// Used to enable on-demand parsing of the VST.
+  uint64_t VSTOffset = 0;
+
+  // Map to save ValueId to GUID association that was recorded in the
+  // ValueSymbolTable. It is used after the VST is parsed to convert
+  // call graph edges read from the function summary from referencing
+  // callees by their ValueId to using the GUID instead, which is how
+  // they are recorded in the function index being built.
+  DenseMap<unsigned, uint64_t> ValueIdToCallGraphGUIDMap;
+
+  /// Map to save the association between summary offset in the VST to the
+  /// GlobalValueInfo object created when parsing it. Used to access the
+  /// info object when parsing the summary section.
+  DenseMap<uint64_t, GlobalValueInfo *> SummaryOffsetToInfoMap;
 
   /// Map populated during module path string table parsing, from the
   /// module ID to a string reference owned by the index's module
-  /// path string table, used to correlate with combined index function
+  /// path string table, used to correlate with combined index
   /// summary records.
   DenseMap<uint64_t, StringRef> ModuleIdMap;
 
   /// Original source file name recorded in a bitcode record.
   std::string SourceFileName;
 
 public:
   std::error_code error(BitcodeError E, const Twine &Message);
   std::error_code error(BitcodeError E);
   std::error_code error(const Twine &Message);
 
   FunctionIndexBitcodeReader(MemoryBuffer *Buffer,
                              DiagnosticHandlerFunction DiagnosticHandler,
                              bool IsLazy = false,
-                             bool CheckFuncSummaryPresenceOnly = false);
+                             bool CheckGlobalValSummaryPresenceOnly = false);
   FunctionIndexBitcodeReader(DiagnosticHandlerFunction DiagnosticHandler,
                              bool IsLazy = false,
-                             bool CheckFuncSummaryPresenceOnly = false);
+                             bool CheckGlobalValSummaryPresenceOnly = false);
   ~FunctionIndexBitcodeReader() { freeState(); }
 
   void freeState();
 
   void releaseBuffer();
 
-  /// Check if the parser has encountered a function summary section.
-  bool foundFuncSummary() { return SeenFuncSummary; }
+  /// Check if the parser has encountered a summary section.
+  bool foundGlobalValSummary() { return SeenGlobalValSummary; }
 
   /// \brief Main interface to parsing a bitcode buffer.
   /// \returns true if an error occurred.
   std::error_code parseSummaryIndexInto(std::unique_ptr<DataStreamer> Streamer,
                                         FunctionInfoIndex *I);
 
-  /// \brief Interface for parsing a function summary lazily.
+  /// \brief Interface for parsing a summary lazily.
   std::error_code parseFunctionSummary(std::unique_ptr<DataStreamer> Streamer,
                                        FunctionInfoIndex *I,
                                        size_t FunctionSummaryOffset);
 
 private:
   std::error_code parseModule();
-  std::error_code parseValueSymbolTable();
+  std::error_code parseValueSymbolTable(
+      uint64_t Offset,
+      DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap);
   std::error_code parseEntireSummary();
   std::error_code parseModuleStringTable();
   std::error_code initStream(std::unique_ptr<DataStreamer> Streamer);
   std::error_code initStreamFromBuffer();
   std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
+  uint64_t getGUIDFromValueId(unsigned ValueId);
+  GlobalValueInfo *getInfoFromSummaryOffset(uint64_t Offset);
 };
 } // end anonymous namespace
 
 BitcodeDiagnosticInfo::BitcodeDiagnosticInfo(std::error_code EC,
                                              DiagnosticSeverity Severity,
                                              const Twine &Msg)
     : DiagnosticInfo(DK_Bitcode, Severity), Msg(Msg), EC(EC) {}
 
if (GO->getComdat() == reinterpret_cast<Comdat *>(1)) {
         GO->setComdat(nullptr);
       else
         GO->setComdat(TheModule->getOrInsertComdat(V->getName()));
     }
   }
   return V;
 }
 
-/// Parse the value symbol table at either the current parsing location or
-/// at the given bit offset if provided.
-std::error_code BitcodeReader::parseValueSymbolTable(uint64_t Offset) {
-  uint64_t CurrentBit;
-  // Pass in the Offset to distinguish between calling for the module-level
-  // VST (where we want to jump to the VST offset) and the function-level
-  // VST (where we don't).
-  if (Offset > 0) {
-    // Save the current parsing location so we can jump back at the end
-    // of the VST read.
-    CurrentBit = Stream.GetCurrentBitNo();
-    Stream.JumpToBit(Offset * 32);
+/// Helper to note and return the current location, and jump to the given
+/// offset.
+static uint64_t jumpToValueSymbolTable(uint64_t Offset,
+                                       BitstreamCursor &Stream) {
+  uint64_t CurrentBit = Stream.GetCurrentBitNo();
 #ifndef NDEBUG
-    // Do some checking if we are in debug mode.
-    BitstreamEntry Entry = Stream.advance();
-    assert(Entry.Kind == BitstreamEntry::SubBlock);
-    assert(Entry.ID == bitc::VALUE_SYMTAB_BLOCK_ID);
 #else
-    // In NDEBUG mode ignore the output so we don't get an unused variable
-    // warning.
-    Stream.advance();
 #endif
-  }
+  return CurrentBit;
 
+/// Parse the value symbol table at either the current parsing location or
+/// at the given bit offset if provided.
+std::error_code BitcodeReader::parseValueSymbolTable(uint64_t Offset) {
+  uint64_t CurrentBit;
+  // Pass in the Offset to distinguish between calling for the module-level
+  // VST (where we want to jump to the VST offset) and the function-level
+  // VST (where we don't).
+  if (Offset > 0)
+    CurrentBit = jumpToValueSymbolTable(Offset, Stream);
+
   // Compute the delta between the bitcode indices in the VST (the word offset
   // to the word-aligned ENTER_SUBBLOCK for the function block, and that
   // expected by the lazy reader. The reader's EnterSubBlock expects to have
   // already read the ENTER_SUBBLOCK code (size getAbbrevIDWidth) and BlockID
   // (size BlockIDWidth). Note that we access the stream's AbbrevID width here
   // just before entering the VST subblock because: 1) the EnterSubBlock
   // changes the AbbrevID width; 2) the VST block is nested within the same
   // outer MODULE_BLOCK as the FUNCTION_BLOCKs and therefore have the same

 }
 
 std::error_code FunctionIndexBitcodeReader::error(BitcodeError E) {
   return ::error(DiagnosticHandler, make_error_code(E));
 }
 
 FunctionIndexBitcodeReader::FunctionIndexBitcodeReader(
     MemoryBuffer *Buffer, DiagnosticHandlerFunction DiagnosticHandler,
-    bool IsLazy, bool CheckFuncSummaryPresenceOnly)
+    bool IsLazy, bool CheckGlobalValSummaryPresenceOnly)
     : DiagnosticHandler(DiagnosticHandler), Buffer(Buffer), IsLazy(IsLazy),
-      CheckFuncSummaryPresenceOnly(CheckFuncSummaryPresenceOnly) {}
+      CheckGlobalValSummaryPresenceOnly(CheckGlobalValSummaryPresenceOnly) {}
 
 FunctionIndexBitcodeReader::FunctionIndexBitcodeReader(
     DiagnosticHandlerFunction DiagnosticHandler, bool IsLazy,
-    bool CheckFuncSummaryPresenceOnly)
+    bool CheckGlobalValSummaryPresenceOnly)
     : DiagnosticHandler(DiagnosticHandler), Buffer(nullptr), IsLazy(IsLazy),
-      CheckFuncSummaryPresenceOnly(CheckFuncSummaryPresenceOnly) {}
+      CheckGlobalValSummaryPresenceOnly(CheckGlobalValSummaryPresenceOnly) {}
 
 void FunctionIndexBitcodeReader::freeState() { Buffer = nullptr; }
 
 void FunctionIndexBitcodeReader::releaseBuffer() { Buffer.release(); }
 
-// Specialized value symbol table parser used when reading function index
+uint64_t FunctionIndexBitcodeReader::getGUIDFromValueId(unsigned ValueId) {
+  auto VGI = ValueIdToCallGraphGUIDMap.find(ValueId);
+  assert(VGI != ValueIdToCallGraphGUIDMap.end());
+  return VGI->second;
+}
+
+GlobalValueInfo *
+FunctionIndexBitcodeReader::getInfoFromSummaryOffset(uint64_t Offset) {
+  auto I = SummaryOffsetToInfoMap.find(Offset);
+  assert(I != SummaryOffsetToInfoMap.end());
+  return I->second;
+}
+
+// Specialized value symbol table parser used when reading module index
 // blocks where we don't actually create global values.
-// At the end of this routine the function index is populated with a map
-// from function name to FunctionInfo. The function info contains
-// the function block's bitcode offset as well as the offset into the
-// function summary section.
-std::error_code FunctionIndexBitcodeReader::parseValueSymbolTable() {
+// At the end of this routine the module index is populated with a map
+// from global value name to GlobalValueInfo. The global value info contains
+// the function block's bitcode offset (if applicable), or the offset into the
+// summary section for the combined index.
+std::error_code FunctionIndexBitcodeReader::parseValueSymbolTable(
+    uint64_t Offset,
+    DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap) {
+  assert(Offset > 0 && "Expected non-zero VST offset");
+  uint64_t CurrentBit = jumpToValueSymbolTable(Offset, Stream);
+
   if (Stream.EnterSubBlock(bitc::VALUE_SYMTAB_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   // Read all the records for this value table.
   SmallString<128> ValueName;
   while (1) {
     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
 
     switch (Entry.Kind) {
     case BitstreamEntry::SubBlock: // Handled for us already.
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
+      // Done parsing VST, jump back to wherever we came from.
+      Stream.JumpToBit(CurrentBit);
       return std::error_code();
     case BitstreamEntry::Record:
       // The interesting case.
       break;
     }
 
     // Read a record.
     Record.clear();
     switch (Stream.readRecord(Entry.ID, Record)) {
     default: // Default behavior: ignore (e.g. VST_CODE_BBENTRY records).
       break;
+    case bitc::VST_CODE_ENTRY: { // VST_CODE_ENTRY: [valueid, namechar x N]
+      if (convertToString(Record, 1, ValueName))
+        return error("Invalid record");
+      unsigned ValueID = Record[0];
+      std::unique_ptr<GlobalValueInfo> GlobalValInfo =
+          llvm::make_unique<GlobalValueInfo>();
+      assert(!SourceFileName.empty());
+      auto VLI = ValueIdToLinkageMap.find(ValueID);
+      assert(VLI != ValueIdToLinkageMap.end() &&
+             "No linkage found for VST entry?");
+      std::string GlobalId =
+          Function::getGlobalIdentifier(ValueName, VLI->second, SourceFileName);
+      TheIndex->addGlobalValueInfo(GlobalId, std::move(GlobalValInfo));
+      ValueIdToCallGraphGUIDMap[ValueID] = Function::getGUID(GlobalId);
+      ValueName.clear();
+      break;
+    }
     case bitc::VST_CODE_FNENTRY: {
       // VST_CODE_FNENTRY: [valueid, offset, namechar x N]
       if (convertToString(Record, 2, ValueName))
         return error("Invalid record");
       unsigned ValueID = Record[0];
       uint64_t FuncOffset = Record[1];
       assert(!IsLazy && "Lazy summary read only supported for combined index");
-      // Gracefully handle bitcode without a function summary section,
-      // which will simply not populate the index.
-      if (foundFuncSummary()) {
-        DenseMap<uint64_t, std::unique_ptr<FunctionSummary>>::iterator SMI =
-            SummaryMap.find(ValueID);
-        assert(SMI != SummaryMap.end() && "Summary info not found");
-        std::unique_ptr<FunctionInfo> FuncInfo =
-            llvm::make_unique<FunctionInfo>(FuncOffset);
-        FuncInfo->setFunctionSummary(std::move(SMI->second));
-        assert(!SourceFileName.empty());
-        std::string FunctionGlobalId = Function::getGlobalIdentifier(
-            ValueName, FuncInfo->functionSummary()->getFunctionLinkage(),
-            SourceFileName);
-        TheIndex->addFunctionInfo(FunctionGlobalId, std::move(FuncInfo));
-      }
+      std::unique_ptr<GlobalValueInfo> FuncInfo =
+          llvm::make_unique<GlobalValueInfo>(FuncOffset);
+      auto VLI = ValueIdToLinkageMap.find(ValueID);
+      assert(VLI != ValueIdToLinkageMap.end() &&
+             "No linkage found for VST entry?");
+      std::string FunctionGlobalId =
+          Function::getGlobalIdentifier(ValueName, VLI->second, SourceFileName);
+      TheIndex->addGlobalValueInfo(FunctionGlobalId, std::move(FuncInfo));
+      ValueIdToCallGraphGUIDMap[ValueID] = Function::getGUID(FunctionGlobalId);
 
       ValueName.clear();
       break;
     }
-    case bitc::VST_CODE_COMBINED_FNENTRY: {
-      // VST_CODE_COMBINED_FNENTRY: [offset, funcguid]
-      uint64_t FuncSummaryOffset = Record[0];
-      uint64_t FuncGUID = Record[1];
-      std::unique_ptr<FunctionInfo> FuncInfo =
-          llvm::make_unique<FunctionInfo>(FuncSummaryOffset);
-      if (foundFuncSummary() && !IsLazy) {
-        DenseMap<uint64_t, std::unique_ptr<FunctionSummary>>::iterator SMI =
-            SummaryMap.find(FuncSummaryOffset);
-        assert(SMI != SummaryMap.end() && "Summary info not found");
-        FuncInfo->setFunctionSummary(std::move(SMI->second));
-      }
-      TheIndex->addFunctionInfo(FuncGUID, std::move(FuncInfo));
-
-      ValueName.clear();
+    case bitc::VST_CODE_COMBINED_GVDEFENTRY: {
+      // VST_CODE_COMBINED_GVDEFENTRY: [valueid, offset, guid]
+      unsigned ValueID = Record[0];
+      uint64_t GlobalValSummaryOffset = Record[1];
+      uint64_t GlobalValGUID = Record[2];
+      std::unique_ptr<GlobalValueInfo> GlobalValInfo =
+          llvm::make_unique<GlobalValueInfo>(GlobalValSummaryOffset);
+      SummaryOffsetToInfoMap[GlobalValSummaryOffset] = GlobalValInfo.get();
+      TheIndex->addGlobalValueInfo(GlobalValGUID, std::move(GlobalValInfo));
+      ValueIdToCallGraphGUIDMap[ValueID] = GlobalValGUID;
+      break;
+    case bitc::VST_CODE_COMBINED_ENTRY: {
+      // VST_CODE_COMBINED_ENTRY: [valueid, refguid]
+      unsigned ValueID = Record[0];
+      uint64_t RefGUID = Record[1];
+      ValueIdToCallGraphGUIDMap[ValueID] = RefGUID;
       break;
     }
     }
   }
 }
 
-// Parse just the blocks needed for function index building out of the module.
-// At the end of this routine the function Index is populated with a map
-// from function name to FunctionInfo. The function info contains
-// either the parsed function summary information (when parsing summaries
-// eagerly), or just to the function summary record's offset
+// Parse just the blocks needed for building the index out of the module.
+// At the end of this routine the module Index is populated with a map
+// from global value name to GlobalValueInfo. The global value info contains
+// either the parsed summary information (when parsing summaries
+// eagerly), or just to the summary record's offset
 // if parsing lazily (IsLazy).
 std::error_code FunctionIndexBitcodeReader::parseModule() {
   if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
+  DenseMap<unsigned, GlobalValue::LinkageTypes> ValueIdToLinkageMap;
+  unsigned ValueId = 0;
 
-  // Read the function index for this module.
+  // Read the index for this module.
   while (1) {
     BitstreamEntry Entry = Stream.advance();
 
     switch (Entry.Kind) {
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
       return std::error_code();
 
     case BitstreamEntry::SubBlock:
-      if (CheckFuncSummaryPresenceOnly) {
-        if (Entry.ID == bitc::FUNCTION_SUMMARY_BLOCK_ID) {
-          SeenFuncSummary = true;
+      if (CheckGlobalValSummaryPresenceOnly) {
+        if (Entry.ID == bitc::GLOBALVAL_SUMMARY_BLOCK_ID) {
+          SeenGlobalValSummary = true;
           // No need to parse the rest since we found the summary.
           return std::error_code();
         }
         if (Stream.SkipBlock())
           return error("Invalid record");
         continue;
       }
       switch (Entry.ID) {
       default: // Skip unknown content.
         if (Stream.SkipBlock())
           return error("Invalid record");
         break;
       case bitc::BLOCKINFO_BLOCK_ID:
         // Need to parse these to get abbrev ids (e.g. for VST)
         if (Stream.ReadBlockInfoBlock())
           return error("Malformed block");
         break;
       case bitc::VALUE_SYMTAB_BLOCK_ID:
-        if (std::error_code EC = parseValueSymbolTable())
-          return EC;
+        // Should have been parsed earlier via VSTOffset, unless there
+        // is no summary section.
+        assert(((SeenValueSymbolTable && VSTOffset > 0) ||
+                !SeenGlobalValSummary) &&
+               "Expected early VST parse via VSTOffset record");
+        if (Stream.SkipBlock())
+          return error("Invalid record");
         break;
-      case bitc::FUNCTION_SUMMARY_BLOCK_ID:
-        SeenFuncSummary = true;
+      case bitc::GLOBALVAL_SUMMARY_BLOCK_ID:
+        assert(VSTOffset > 0 && "Expected non-zero VST offset");
+        assert(!SeenValueSymbolTable &&
+               "Already read VST when parsing summary block?");
+        if (std::error_code EC =
+                parseValueSymbolTable(VSTOffset, ValueIdToLinkageMap))
+          return EC;
+        SeenValueSymbolTable = true;
+        SeenGlobalValSummary = true;
         if (IsLazy) {
           // Lazy parsing of summary info, skip it.
           if (Stream.SkipBlock())
             return error("Invalid record");
         } else if (std::error_code EC = parseEntireSummary())
           return EC;
         break;
       case bitc::MODULE_STRTAB_BLOCK_ID:
         if (std::error_code EC = parseModuleStringTable())
           return EC;
         break;
       }
       continue;
 
     case BitstreamEntry::Record:
-      // Once we find the single record of interest, skip the rest.
-      if (!SourceFileName.empty())
+      // Once we find the last record of interest, skip the rest.
+      if (VSTOffset > 0)
         Stream.skipRecord(Entry.ID);
       else {
         Record.clear();
         auto BitCode = Stream.readRecord(Entry.ID, Record);
         switch (BitCode) {
         default:
           break; // Default behavior, ignore unknown content.
         /// MODULE_CODE_SOURCE_FILENAME: [namechar x N]
-        case bitc::MODULE_CODE_SOURCE_FILENAME:
+        case bitc::MODULE_CODE_SOURCE_FILENAME: {
           SmallString<128> ValueName;
           if (convertToString(Record, 0, ValueName))
             return error("Invalid record");
           SourceFileName = ValueName.c_str();
           break;
         }
+        /// MODULE_CODE_VSTOFFSET: [offset]
+        case bitc::MODULE_CODE_VSTOFFSET:
+          if (Record.size() < 1)
+            return error("Invalid record");
+          VSTOffset = Record[0];
+          break;
+        // GLOBALVAR: [pointer type, isconst, initid,
+        //             linkage, alignment, section, visibility, threadlocal,
+        //             unnamed_addr, externally_initialized, dllstorageclass,
+        //             comdat]
+        case bitc::MODULE_CODE_GLOBALVAR: {
+          if (Record.size() < 6)
+            return error("Invalid record");
+          uint64_t RawLinkage = Record[3];
+          GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage);
+          ValueIdToLinkageMap[ValueId++] = Linkage;
+          break;
+        }
+        // FUNCTION:  [type, callingconv, isproto, linkage, paramattr,
+        //             alignment, section, visibility, gc, unnamed_addr,
+        //             prologuedata, dllstorageclass, comdat, prefixdata]
+        case bitc::MODULE_CODE_FUNCTION: {
+          if (Record.size() < 8)
+            return error("Invalid record");
+          uint64_t RawLinkage = Record[3];
+          GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage);
+          ValueIdToLinkageMap[ValueId++] = Linkage;
+          break;
+        }
+        // ALIAS: [alias type, addrspace, aliasee val#, linkage, visibility,
+        // dllstorageclass]
+        case bitc::MODULE_CODE_ALIAS: {
+          if (Record.size() < 6)
+            return error("Invalid record");
+          uint64_t RawLinkage = Record[3];
+          GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage);
+          ValueIdToLinkageMap[ValueId++] = Linkage;
+          break;
+        }
+        }
       }
       continue;
     }
   }
 }
 
-// Eagerly parse the entire function summary block (i.e. for all functions
-// in the index). This populates the FunctionSummary objects in
-// the index.
+// Eagerly parse the entire summary block. This populates the GlobalValueSummary
+// objects in the index.
 std::error_code FunctionIndexBitcodeReader::parseEntireSummary() {
-  if (Stream.EnterSubBlock(bitc::FUNCTION_SUMMARY_BLOCK_ID))
+  if (Stream.EnterSubBlock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   while (1) {
     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
 
     switch (Entry.Kind) {
while (1) {
     // is a per-module index or a combined index file. In the per-module
     // case the records contain the associated value's ID for correlation
     // with VST entries. In the combined index the correlation is done
     // via the bitcode offset of the summary records (which were saved
     // in the combined index VST entries). The records also contain
     // information used for ThinLTO renaming and importing.
     Record.clear();
     uint64_t CurRecordBit = Stream.GetCurrentBitNo();
-    switch (Stream.readRecord(Entry.ID, Record)) {
+    auto BitCode = Stream.readRecord(Entry.ID, Record);
+    switch (BitCode) {
     default: // Default behavior: ignore.
       break;
-    // FS_PERMODULE_ENTRY: [valueid, linkage, instcount]
-    case bitc::FS_CODE_PERMODULE_ENTRY: {
+    // FS_PERMODULE: [valueid, linkage, instcount, numrefs, numrefs x valueid,
+    //                n x (valueid, callsitecount)]
+    // FS_PERMODULE_PROFILE: [valueid, linkage, instcount, numrefs,
+    //                        numrefs x valueid,
+    //                        n x (valueid, callsitecount, profilecount)]
+    case bitc::FS_PERMODULE:
+    case bitc::FS_PERMODULE_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t RawLinkage = Record[1];
       unsigned InstCount = Record[2];
-      std::unique_ptr<FunctionSummary> FS =
-          llvm::make_unique<FunctionSummary>(InstCount);
-      FS->setFunctionLinkage(getDecodedLinkage(RawLinkage));
+      unsigned NumRefs = Record[3];
+      std::unique_ptr<FunctionSummary> FS = llvm::make_unique<FunctionSummary>(
+          getDecodedLinkage(RawLinkage), 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(Buffer->getBufferIdentifier(), 0));
-      SummaryMap[ValueID] = std::move(FS);
+      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];
+        uint64_t RefGUID = getGUIDFromValueId(RefValueId);
+        FS->addRefEdge(RefGUID);
+      }
+      bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE);
+      for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E;
+           ++I) {
+        unsigned CalleeValueId = Record[I];
+        unsigned CallsiteCount = Record[++I];
+        uint64_t ProfileCount = HasProfile ? Record[++I] : 0;
+        uint64_t CalleeGUID = getGUIDFromValueId(CalleeValueId);
+        FS->addCallGraphEdge(CalleeGUID,
+                             CalleeInfo(CallsiteCount, ProfileCount));
+      }
+      uint64_t GUID = getGUIDFromValueId(ValueID);
+      auto InfoList = TheIndex->findGlobalValueInfoList(GUID);
+      assert(InfoList != TheIndex->end() &&
+             "Expected VST parse to create GlobalValueInfo entry");
+      assert(InfoList->second.size() == 1 &&
+             "Expected a single GlobalValueInfo per GUID in module");
+      auto &Info = InfoList->second[0];
+      assert(!Info->summary() && "Expected a single summary per VST entry");
+      Info->setSummary(std::move(FS));
       break;
     }
-    // FS_COMBINED_ENTRY: [modid, linkage, instcount]
-    case bitc::FS_CODE_COMBINED_ENTRY: {
+    // FS_PERMODULE_GLOBALVAR_INIT_REFS: [valueid, linkage, n x valueid]
+    case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: {
+      unsigned ValueID = Record[0];
+      uint64_t RawLinkage = Record[1];
+      std::unique_ptr<GlobalVarSummary> FS =
+          llvm::make_unique<GlobalVarSummary>(getDecodedLinkage(RawLinkage));
+      FS->setModulePath(
+          TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0));
+      for (unsigned I = 2, E = Record.size(); I != E; ++I) {
+        unsigned RefValueId = Record[I];
+        uint64_t RefGUID = getGUIDFromValueId(RefValueId);
+        FS->addRefEdge(RefGUID);
+      }
+      uint64_t GUID = getGUIDFromValueId(ValueID);
+      auto InfoList = TheIndex->findGlobalValueInfoList(GUID);
+      assert(InfoList != TheIndex->end() &&
+             "Expected VST parse to create GlobalValueInfo entry");
+      assert(InfoList->second.size() == 1 &&
+             "Expected a single GlobalValueInfo per GUID in module");
+      auto &Info = InfoList->second[0];
+      assert(!Info->summary() && "Expected a single summary per VST entry");
+      Info->setSummary(std::move(FS));
+      break;
+    }
+    // FS_COMBINED: [modid, linkage, instcount, numrefs, numrefs x valueid,
+    //               n x (valueid, callsitecount)]
+    // FS_COMBINED_PROFILE: [modid, linkage, instcount, numrefs,
+    //                       numrefs x valueid,
+    //                       n x (valueid, callsitecount, profilecount)]
+    case bitc::FS_COMBINED:
+    case bitc::FS_COMBINED_PROFILE: {
       uint64_t ModuleId = Record[0];
       uint64_t RawLinkage = Record[1];
       unsigned InstCount = Record[2];
-      std::unique_ptr<FunctionSummary> FS =
-          llvm::make_unique<FunctionSummary>(InstCount);
-      FS->setFunctionLinkage(getDecodedLinkage(RawLinkage));
+      unsigned NumRefs = Record[3];
+      std::unique_ptr<FunctionSummary> FS = llvm::make_unique<FunctionSummary>(
+          getDecodedLinkage(RawLinkage), InstCount);
+      FS->setModulePath(ModuleIdMap[ModuleId]);
+      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];
+        uint64_t RefGUID = getGUIDFromValueId(RefValueId);
+        FS->addRefEdge(RefGUID);
+      }
+      bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
+      for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E;
+           ++I) {
+        unsigned CalleeValueId = Record[I];
+        unsigned CallsiteCount = Record[++I];
+        uint64_t ProfileCount = HasProfile ? Record[++I] : 0;
+        uint64_t CalleeGUID = getGUIDFromValueId(CalleeValueId);
+        FS->addCallGraphEdge(CalleeGUID,
+                             CalleeInfo(CallsiteCount, ProfileCount));
+      }
+      auto *Info = getInfoFromSummaryOffset(CurRecordBit);
+      assert(!Info->summary() && "Expected a single summary per VST entry");
+      Info->setSummary(std::move(FS));
+      break;
+    }
+    // FS_COMBINED_GLOBALVAR_INIT_REFS: [modid, linkage, n x valueid]
+    case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS: {
+      uint64_t ModuleId = Record[0];
+      uint64_t RawLinkage = Record[1];
+      std::unique_ptr<GlobalVarSummary> FS =
+          llvm::make_unique<GlobalVarSummary>(getDecodedLinkage(RawLinkage));
       FS->setModulePath(ModuleIdMap[ModuleId]);
-      SummaryMap[CurRecordBit] = std::move(FS);
+      for (unsigned I = 2, E = Record.size(); I != E; ++I) {
+        unsigned RefValueId = Record[I];
+        uint64_t RefGUID = getGUIDFromValueId(RefValueId);
+        FS->addRefEdge(RefGUID);
+      }
+      auto *Info = getInfoFromSummaryOffset(CurRecordBit);
+      assert(!Info->summary() && "Expected a single summary per VST entry");
+      Info->setSummary(std::move(FS));
       break;
     }
     }
   }
   llvm_unreachable("Exit infinite loop");
 }
 
 // Parse the  module string table block into the Index.
 // This populates the ModulePathStringTable map in the index.
 std::error_code FunctionIndexBitcodeReader::parseModuleStringTable() {
   if (Stream.EnterSubBlock(bitc::MODULE_STRTAB_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   SmallString<128> ModulePath;
   while (1) {
     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
 
     switch (Entry.Kind) {
     case BitstreamEntry::SubBlock: // Handled for us already.
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
       return std::error_code();
     case BitstreamEntry::Record:
       // The interesting case.
       break;
     }
 
     Record.clear();
case BitstreamEntry::Record:
     // The expected case.
     break;
   }
 
   // TODO: Read a record. This interface will be completed when ThinLTO
   // importing is added so that it can be tested.
   SmallVector<uint64_t, 64> Record;
   switch (Stream.readRecord(Entry.ID, Record)) {
-  case bitc::FS_CODE_COMBINED_ENTRY:
+  case bitc::FS_COMBINED:
+  case bitc::FS_COMBINED_PROFILE:
+  case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS:
   default:
     return error("Invalid record");
   }
 
   return std::error_code();
 }
 
 std::error_code
llvm::getFunctionInfoIndex(MemoryBufferRef Buffer,
 
   if (std::error_code EC = R.parseSummaryIndexInto(nullptr, Index.get()))
     return cleanupOnError(EC);
 
   Buf.release(); // The FunctionIndexBitcodeReader owns it now.
   return std::move(Index);
 }
 
-// Check if the given bitcode buffer contains a function summary block.
-bool llvm::hasFunctionSummary(MemoryBufferRef Buffer,
+// Check if the given bitcode buffer contains a global value summary block.
+bool llvm::hasGlobalValueSummary(MemoryBufferRef Buffer,
                                  DiagnosticHandlerFunction DiagnosticHandler) {
   std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
   FunctionIndexBitcodeReader R(Buf.get(), DiagnosticHandler, false, true);
 
   auto cleanupOnError = [&](std::error_code EC) {
     R.releaseBuffer(); // Never take ownership on error.
     return false;
   };
 
   if (std::error_code EC = R.parseSummaryIndexInto(nullptr, nullptr))
     return cleanupOnError(EC);
 
   Buf.release(); // The FunctionIndexBitcodeReader owns it now.
-  return R.foundFuncSummary();
+  return R.foundGlobalValSummary();
 }
 
 // This method supports lazy reading of function summary data from the combined
 // index during ThinLTO function importing. When reading the combined index
 // file, getFunctionInfoIndex is first invoked with IsLazy=true.
 // Then this method is called for each function considered for importing,
 // to parse the summary information for the given function name into
 // the index.
 std::error_code llvm::readFunctionSummary(
     MemoryBufferRef Buffer, DiagnosticHandlerFunction DiagnosticHandler,
     StringRef FunctionName, std::unique_ptr<FunctionInfoIndex> Index) {
   std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
   FunctionIndexBitcodeReader R(Buf.get(), DiagnosticHandler);
 
   auto cleanupOnError = [&](std::error_code EC) {
     R.releaseBuffer(); // Never take ownership on error.
     return EC;
   };
 
   // Lookup the given function name in the FunctionMap, which may
   // contain a list of function infos in the case of a COMDAT. Walk through
   // and parse each function summary info at the function summary offset
   // recorded when parsing the value symbol table.
-  for (const auto &FI : Index->getFunctionInfoList(FunctionName)) {
+  for (const auto &FI : Index->getGlobalValueInfoList(FunctionName)) {
     size_t FunctionSummaryOffset = FI->bitcodeIndex();
     if (std::error_code EC =
             R.parseFunctionSummary(nullptr, Index.get(), FunctionSummaryOffset))
       return cleanupOnError(EC);
   }
 
   Buf.release(); // The FunctionIndexBitcodeReader owns it now.
   return std::error_code();
 }

lib/Bitcode/Writer/BitcodeWriter.cpp

 //===--- Bitcode/Writer/BitcodeWriter.cpp - Bitcode Writer ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Bitcode writer implementation.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Bitcode/ReaderWriter.h"
 #include "ValueEnumerator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Bitcode/BitstreamWriter.h"
 #include "llvm/Bitcode/LLVMBitCodes.h"
+#include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/UseListOrder.h"
 #include "llvm/IR/ValueSymbolTable.h"
+#include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cctype>
 #include <map>
 using namespace llvm;
for (const Comdat *C : VE.getComdats()) {
     Stream.EmitRecord(bitc::MODULE_CODE_COMDAT, Vals, /*AbbrevToUse=*/0);
     Vals.clear();
   }
 }
 
 /// Write a record that will eventually hold the word offset of the
 /// module-level VST. For now the offset is 0, which will be backpatched
 /// after the real VST is written. Returns the bit offset to backpatch.
-static uint64_t WriteValueSymbolTableForwardDecl(const ValueSymbolTable &VST,
-                                                 BitstreamWriter &Stream) {
-  if (VST.empty())
-    return 0;
-
+static uint64_t WriteValueSymbolTableForwardDecl(BitstreamWriter &Stream) {
   // Write a placeholder value in for the offset of the real VST,
   // which is written after the function blocks so that it can include
   // the offset of each function. The placeholder offset will be
   // updated when the real VST is written.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_VSTOFFSET));
   // Blocks are 32-bit aligned, so we can use a 32-bit word offset to
   // hold the real VST offset. Must use fixed instead of VBR as we don't
// Emit the module's source file name.
     for (const auto P : M->getSourceFileName())
       Vals.push_back((unsigned char)P);
 
     // Emit the finished record.
     Stream.EmitRecord(bitc::MODULE_CODE_SOURCE_FILENAME, Vals, FilenameAbbrev);
     Vals.clear();
   }
 
-  uint64_t VSTOffsetPlaceholder =
-      WriteValueSymbolTableForwardDecl(M->getValueSymbolTable(), Stream);
-  return VSTOffsetPlaceholder;
+  // If we have a VST, write the VSTOFFSET record placeholder and return
+  // its offset.
+  if (M->getValueSymbolTable().empty())
+    return 0;
+  return WriteValueSymbolTableForwardDecl(Stream);
 }
 
 static uint64_t GetOptimizationFlags(const Value *V) {
   uint64_t Flags = 0;
 
   if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(V)) {
     if (OBO->hasNoSignedWrap())
       Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP;

 /// Emit names for globals/functions etc. The VSTOffsetPlaceholder,
 /// BitcodeStartBit and FunctionIndex are only passed for the module-level
 /// VST, where we are including a function bitcode index and need to
 /// backpatch the VST forward declaration record.
 static void WriteValueSymbolTable(
     const ValueSymbolTable &VST, const ValueEnumerator &VE,
     BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0,
     uint64_t BitcodeStartBit = 0,
-    DenseMap<const Function *, std::unique_ptr<FunctionInfo>> *FunctionIndex =
-        nullptr) {
+    DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>>
+        *FunctionIndex = nullptr) {
   if (VST.empty()) {
     // WriteValueSymbolTableForwardDecl should have returned early as
     // well. Ensure this handling remains in sync by asserting that
     // the placeholder offset is not set.
     assert(VSTOffsetPlaceholder == 0);
     return;
   }
 
if (isa<BasicBlock>(Name.getValue())) {
       // Must be the module-level VST, where we pass in the Index and
       // have a VSTOffsetPlaceholder. The function-level VST should not
       // contain any Function symbols.
       assert(FunctionIndex);
       assert(VSTOffsetPlaceholder > 0);
 
       // Save the word offset of the function (from the start of the
       // actual bitcode written to the stream).
       assert(FunctionIndex->count(F) == 1);
       uint64_t BitcodeIndex =
           (*FunctionIndex)[F]->bitcodeIndex() - BitcodeStartBit;
       assert((BitcodeIndex & 31) == 0 && "function block not 32-bit aligned");
       NameVals.push_back(BitcodeIndex / 32);
 
       Code = bitc::VST_CODE_FNENTRY;
       AbbrevToUse = FnEntry8BitAbbrev;
       if (Bits == SE_Char6)
for (const ValueName &Name : VST) {
     Stream.EmitRecord(Code, NameVals, AbbrevToUse);
     NameVals.clear();
   }
   Stream.ExitBlock();
 }
 
 /// Emit function names and summary offsets for the combined index
 /// used by ThinLTO.
-static void WriteCombinedValueSymbolTable(const FunctionInfoIndex &Index,
-                                          BitstreamWriter &Stream) {
+static void
+WriteCombinedValueSymbolTable(const FunctionInfoIndex &Index,
+                              BitstreamWriter &Stream,
+                              std::map<uint64_t, unsigned> &GUIDToValueIdMap,
+                              uint64_t VSTOffsetPlaceholder) {
+  assert(VSTOffsetPlaceholder > 0 && "Expected non-zero VSTOffsetPlaceholder");
+  // Get the offset of the VST we are writing, and backpatch it into
+  // the VST forward declaration record.
+  uint64_t VSTOffset = Stream.GetCurrentBitNo();
+  assert((VSTOffset & 31) == 0 && "VST block not 32-bit aligned");
+  Stream.BackpatchWord(VSTOffsetPlaceholder, VSTOffset / 32);
+
   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
 
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
-  Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_FNENTRY));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcsumoffset
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcguid
-  unsigned FnEntryAbbrev = Stream.EmitAbbrev(Abbv);
+  Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_GVDEFENTRY));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // sumoffset
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // guid
+  unsigned DefEntryAbbrev = Stream.EmitAbbrev(Abbv);
+
+  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
+  unsigned EntryAbbrev = Stream.EmitAbbrev(Abbv);
 
   SmallVector<uint64_t, 64> NameVals;
 
   for (const auto &FII : Index) {
-    for (const auto &FI : FII.second) {
-      NameVals.push_back(FI->bitcodeIndex());
-
-      uint64_t FuncGUID = FII.first;
+    const auto &VMI = GUIDToValueIdMap.find(FuncGUID);
+    assert(VMI != GUIDToValueIdMap.end());
 
-      // VST_CODE_COMBINED_FNENTRY: [funcsumoffset, funcguid]
-      unsigned AbbrevToUse = FnEntryAbbrev;
-
+    for (const auto &FI : FII.second) {
+      // VST_CODE_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid]
+      NameVals.push_back(VMI->second);
+      NameVals.push_back(FI->bitcodeIndex());
       NameVals.push_back(FuncGUID);
 
       // Emit the finished record.
-      Stream.EmitRecord(bitc::VST_CODE_COMBINED_FNENTRY, NameVals, AbbrevToUse);
+      Stream.EmitRecord(bitc::VST_CODE_COMBINED_GVDEFENTRY, NameVals,
+                        DefEntryAbbrev);
       NameVals.clear();
     }
+    GUIDToValueIdMap.erase(VMI);
+  }
+  for (const auto &GVI : GUIDToValueIdMap) {
+    // VST_CODE_COMBINED_ENTRY: [valueid, refguid]
+    NameVals.push_back(GVI.second);
+    NameVals.push_back(GVI.first);
+
+    // Emit the finished record.
+    Stream.EmitRecord(bitc::VST_CODE_COMBINED_ENTRY, NameVals, EntryAbbrev);
+    NameVals.clear();
   }
   Stream.ExitBlock();
 }
 
 static void WriteUseList(ValueEnumerator &VE, UseListOrder &&Order,
                          BitstreamWriter &Stream) {
   assert(Order.Shuffle.size() >= 2 && "Shuffle too small");
   unsigned Code;
static void WriteUseListBlock(const Function *F, ValueEnumerator &VE,
   Stream.EnterSubblock(bitc::USELIST_BLOCK_ID, 3);
   while (hasMore()) {
     WriteUseList(VE, std::move(VE.UseListOrders.back()), Stream);
     VE.UseListOrders.pop_back();
   }
   Stream.ExitBlock();
 }
 
-/// \brief Save information for the given function into the function index.
-///
-/// At a minimum this saves the bitcode index of the function record that
-/// was just written. However, if we are emitting function summary information,
-/// for example for ThinLTO, then a \a FunctionSummary object is created
-/// to hold the provided summary information.
-static void SaveFunctionInfo(
-    const Function &F,
-    DenseMap<const Function *, std::unique_ptr<FunctionInfo>> &FunctionIndex,
-    unsigned NumInsts, uint64_t BitcodeIndex, bool EmitFunctionSummary) {
-  std::unique_ptr<FunctionSummary> FuncSummary;
-  if (EmitFunctionSummary) {
-    FuncSummary = llvm::make_unique<FunctionSummary>(NumInsts);
-    FuncSummary->setFunctionLinkage(F.getLinkage());
+// 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, const ValueEnumerator &VE,
+                         DenseSet<unsigned> &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)) {
+        // 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(VE.getValueID(Operand));
+        continue;
+      }
+      Worklist.push_back(Operand);
+    }
   }
-  FunctionIndex[&F] =
-      llvm::make_unique<FunctionInfo>(BitcodeIndex, std::move(FuncSummary));
 }
 
 /// Emit a function body to the module stream.
 static void WriteFunction(
-    const Function &F, ValueEnumerator &VE, BitstreamWriter &Stream,
-    DenseMap<const Function *, std::unique_ptr<FunctionInfo>> &FunctionIndex,
-    bool EmitFunctionSummary) {
+    const Function &F, const Module *M, ValueEnumerator &VE,
+    BitstreamWriter &Stream,
+    DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> &FunctionIndex,
+    bool EmitSummaryIndex) {
   // Save the bitcode index of the start of this function block for recording
   // in the VST.
   uint64_t BitcodeIndex = Stream.GetCurrentBitNo();
 
+  bool HasProfileData = F.getEntryCount().hasValue();
+  std::unique_ptr<BlockFrequencyInfo> BFI;
+  if (EmitSummaryIndex && HasProfileData) {
+    Function &Func = const_cast<Function &>(F);
+    LoopInfo LI{DominatorTree(Func)};
+    BranchProbabilityInfo BPI{Func, LI};
+    BFI = llvm::make_unique<BlockFrequencyInfo>(Func, BPI, LI);
+  }
+
   Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4);
   VE.incorporateFunction(F);
 
   SmallVector<unsigned, 64> Vals;
 
   // Emit the number of basic blocks, so the reader can create them ahead of
   // time.
   Vals.push_back(VE.getBasicBlocks().size());
static void WriteFunction(
 
   // Keep a running idea of what the instruction ID is.
   unsigned InstID = CstEnd;
 
   bool NeedsMetadataAttachment = F.hasMetadata();
 
   DILocation *LastDL = nullptr;
   unsigned NumInsts = 0;
+  // Map from callee ValueId to profile count. Used to accumulate profile
+  // counts for all static calls to a given callee.
+  DenseMap<unsigned, CalleeInfo> CallGraphEdges;
+  DenseSet<unsigned> RefEdges;
 
+  SmallPtrSet<const User *, 8> Visited;
   // Finally, emit all the instructions, in order.
   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
          I != E; ++I) {
       WriteInstruction(*I, InstID, VE, Stream, Vals);
 
       if (!isa<DbgInfoIntrinsic>(I))
         ++NumInsts;
 
       if (!I->getType()->isVoidTy())
         ++InstID;
 
+      if (EmitSummaryIndex) {
+        if (auto CS = ImmutableCallSite(&*I)) {
+          auto *CalledFunction = CS.getCalledFunction();
+          if (CalledFunction && CalledFunction->hasName() &&
+              !CalledFunction->isIntrinsic()) {
+            uint64_t ScaledCount = 0;
+            if (HasProfileData)
+              ScaledCount = getBlockProfileCount(
+                  BFI->getBlockFreq(&(*BB)).getFrequency(), BFI->getEntryFreq(),
+                  F.getEntryCount().getValue());
+            unsigned CalleeId = VE.getValueID(
+                M->getValueSymbolTable().lookup(CalledFunction->getName()));
+            CallGraphEdges[CalleeId] += ScaledCount;
+          }
+        }
+        findRefEdges(&*I, VE, RefEdges, Visited);
+      }
+
       // If the instruction has metadata, write a metadata attachment later.
       NeedsMetadataAttachment |= I->hasMetadataOtherThanDebugLoc();
 
       // If the instruction has a debug location, emit it.
       DILocation *DL = I->getDebugLoc();
       if (!DL)
         continue;
 
       if (DL == LastDL) {
         // Just repeat the same debug loc as last time.
         Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC_AGAIN, Vals);
         continue;
       }
 
       Vals.push_back(DL->getLine());
       Vals.push_back(DL->getColumn());
       Vals.push_back(VE.getMetadataOrNullID(DL->getScope()));
       Vals.push_back(VE.getMetadataOrNullID(DL->getInlinedAt()));
       Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC, Vals);
       Vals.clear();
 
       LastDL = DL;
     }
 
+  std::unique_ptr<FunctionSummary> FuncSummary;
+  if (EmitSummaryIndex) {
+    FuncSummary = llvm::make_unique<FunctionSummary>(F.getLinkage(), NumInsts);
+    FuncSummary->addCallGraphEdges(CallGraphEdges);
+    FuncSummary->addRefEdges(RefEdges);
+  }
+  FunctionIndex[&F] =
+      llvm::make_unique<GlobalValueInfo>(BitcodeIndex, std::move(FuncSummary));
+
   // Emit names for all the instructions etc.
   WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);
 
   if (NeedsMetadataAttachment)
     WriteMetadataAttachment(F, VE, Stream);
   if (VE.shouldPreserveUseListOrder())
     WriteUseListBlock(&F, VE, Stream);
   VE.purgeFunction();
   Stream.ExitBlock();
-
-  SaveFunctionInfo(F, FunctionIndex, NumInsts, BitcodeIndex,
-                   EmitFunctionSummary);
 }
 
 // Emit blockinfo, which defines the standard abbreviations etc.
 static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) {
   // We only want to emit block info records for blocks that have multiple
   // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK.
   // Other blocks can define their abbrevs inline.
   Stream.EnterBlockInfoBlock(2);
for (const StringMapEntry<uint64_t> &MPSE : I.modPathStringEntries()) {
     Stream.EmitRecord(bitc::MST_CODE_ENTRY, NameVals, AbbrevToUse);
     NameVals.clear();
   }
   Stream.ExitBlock();
 }
 
 // Helper to emit a single function summary record.
 static void WritePerModuleFunctionSummaryRecord(
-    SmallVector<unsigned, 64> &NameVals, FunctionSummary *FS, unsigned ValueID,
-    unsigned FSAbbrev, BitstreamWriter &Stream) {
+    SmallVector<uint64_t, 64> &NameVals, FunctionSummary *FS, unsigned ValueID,
+    unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev,
+    BitstreamWriter &Stream, const Function &F) {
   assert(FS);
   NameVals.push_back(ValueID);
-  NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage()));
+  NameVals.push_back(getEncodedLinkage(FS->linkage()));
   NameVals.push_back(FS->instCount());
+  NameVals.push_back(FS->refs().size());
+
+  for (auto &RI : FS->refs())
+    NameVals.push_back(RI);
+
+  bool HasProfileData = F.getEntryCount().hasValue();
+  for (auto &ECI : FS->edges()) {
+    NameVals.push_back(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 =
+      (HasProfileData ? bitc::FS_PERMODULE_PROFILE : bitc::FS_PERMODULE);
 
   // Emit the finished record.
-  Stream.EmitRecord(bitc::FS_CODE_PERMODULE_ENTRY, NameVals, FSAbbrev);
+  Stream.EmitRecord(Code, NameVals, FSAbbrev);
   NameVals.clear();
 }
 
-/// Emit the per-module function summary section alongside the rest of
+// Collect the global value references in the given variable's initializer,
+// and emit them in a summary record.
+static void WriteModuleLevelReferences(const GlobalVariable &V,
+                                       const ValueEnumerator &VE,
+                                       SmallVector<uint64_t, 64> &NameVals,
+                                       unsigned FSModRefsAbbrev,
+                                       BitstreamWriter &Stream) {
+  DenseSet<unsigned> RefEdges;
+  SmallPtrSet<const User *, 8> Visited;
+  findRefEdges(&V, VE, RefEdges, Visited);
+  unsigned RefCount = RefEdges.size();
+  if (RefCount) {
+    NameVals.push_back(VE.getValueID(&V));
+    NameVals.push_back(getEncodedLinkage(V.getLinkage()));
+    for (auto RefId : RefEdges) {
+      NameVals.push_back(RefId);
+    }
+    Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals,
+                      FSModRefsAbbrev);
+    NameVals.clear();
+  }
+}
+
+/// Emit the per-module summary section alongside the rest of
 /// the module's bitcode.
-static void WritePerModuleFunctionSummary(
-    DenseMap<const Function *, std::unique_ptr<FunctionInfo>> &FunctionIndex,
+static void WritePerModuleGlobalValueSummary(
+    DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> &FunctionIndex,
     const Module *M, const ValueEnumerator &VE, BitstreamWriter &Stream) {
-  Stream.EnterSubblock(bitc::FUNCTION_SUMMARY_BLOCK_ID, 3);
+  if (M->empty())
+    return;
 
-  // Abbrev for FS_CODE_PERMODULE_ENTRY.
+  Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3);
+
+  // Abbrev for FS_PERMODULE.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
-  Abbv->Add(BitCodeAbbrevOp(bitc::FS_CODE_PERMODULE_ENTRY));
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
-  unsigned FSAbbrev = Stream.EmitAbbrev(Abbv);
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
+  // numrefs x valueid, n x (valueid, callsitecount)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv);
 
-  SmallVector<unsigned, 64> NameVals;
+  // Abbrev for FS_PERMODULE_PROFILE.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_PROFILE));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
+  // numrefs x valueid, n x (valueid, callsitecount, profilecount)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv);
+
+  // Abbrev for FS_PERMODULE_GLOBALVAR_INIT_REFS.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));  // valueids
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv);
+
+  SmallVector<uint64_t, 64> NameVals;
   // Iterate over the list of functions instead of the FunctionIndex map to
   // ensure the ordering is stable.
   for (const Function &F : *M) {
     if (F.isDeclaration())
       continue;
     // Skip anonymous functions. We will emit a function summary for
     // any aliases below.
     if (!F.hasName())
       continue;
 
     assert(FunctionIndex.count(&F) == 1);
 
     WritePerModuleFunctionSummaryRecord(
-        NameVals, FunctionIndex[&F]->functionSummary(),
-        VE.getValueID(M->getValueSymbolTable().lookup(F.getName())), FSAbbrev,
-        Stream);
+        NameVals, dyn_cast<FunctionSummary>(FunctionIndex[&F]->summary()),
+        VE.getValueID(M->getValueSymbolTable().lookup(F.getName())),
+        FSCallsAbbrev, FSCallsProfileAbbrev, Stream, F);
   }
 
   for (const GlobalAlias &A : M->aliases()) {
     if (!A.getBaseObject())
       continue;
     const Function *F = dyn_cast<Function>(A.getBaseObject());
     if (!F || F->isDeclaration())
       continue;
 
     assert(FunctionIndex.count(F) == 1);
+    FunctionSummary *FS =
+        dyn_cast<FunctionSummary>(FunctionIndex[F]->summary());
+    // Add the alias to the reference list of aliasee function.
+    FS->addRefEdge(
+        VE.getValueID(M->getValueSymbolTable().lookup(A.getName())));
     WritePerModuleFunctionSummaryRecord(
-        NameVals, FunctionIndex[F]->functionSummary(),
-        VE.getValueID(M->getValueSymbolTable().lookup(A.getName())), FSAbbrev,
-        Stream);
+        NameVals, FS,
+        VE.getValueID(M->getValueSymbolTable().lookup(A.getName())),
+        FSCallsAbbrev, FSCallsProfileAbbrev, Stream, *F);
+  }
+
+  // Capture references from GlobalVariable initializers, which are outside
+  // of a function scope.
+  for (const GlobalVariable &G : M->globals())
+    WriteModuleLevelReferences(G, VE, NameVals, FSModRefsAbbrev, Stream);
+  for (const GlobalAlias &A : M->aliases()) {
+    const auto *GV = dyn_cast<GlobalVariable>(A.getBaseObject());
+    if (GV)
+      WriteModuleLevelReferences(*GV, VE, NameVals, FSModRefsAbbrev, Stream);
   }
 
   Stream.ExitBlock();
 }
 
 /// Emit the combined function summary section into the combined index
 /// file.
-static void WriteCombinedFunctionSummary(const FunctionInfoIndex &I,
-                                         BitstreamWriter &Stream) {
-  Stream.EnterSubblock(bitc::FUNCTION_SUMMARY_BLOCK_ID, 3);
+static void WriteCombinedGlobalValueSummary(
+    const FunctionInfoIndex &I, BitstreamWriter &Stream,
+    std::map<uint64_t, unsigned> &GUIDToValueIdMap, unsigned GlobalValueId) {
+  Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3);
 
-  // Abbrev for FS_CODE_COMBINED_ENTRY.
+  // Abbrev for FS_COMBINED.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
-  Abbv->Add(BitCodeAbbrevOp(bitc::FS_CODE_COMBINED_ENTRY));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount
-  unsigned FSAbbrev = Stream.EmitAbbrev(Abbv);
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
+  // numrefs x valueid, n x (valueid, callsitecount)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv);
 
-  SmallVector<unsigned, 64> NameVals;
+  // Abbrev for FS_COMBINED_PROFILE.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_PROFILE));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
+  // numrefs x valueid, n x (valueid, callsitecount, profilecount)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv);
+
+  // Abbrev for FS_COMBINED_GLOBALVAR_INIT_REFS.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));    // valueids
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv);
+
+  SmallVector<uint64_t, 64> NameVals;
   for (const auto &FII : I) {
     for (auto &FI : FII.second) {
-      FunctionSummary *FS = FI->functionSummary();
-      assert(FS);
+      GlobalValueSummary *S = FI->summary();
+      assert(S);
+
+      if (auto *VS = dyn_cast<GlobalVarSummary>(S)) {
+        assert(!VS->refs().empty() && "Expected at least one ref edge");
+        NameVals.push_back(I.getModuleId(VS->modulePath()));
+        NameVals.push_back(getEncodedLinkage(VS->linkage()));
+        for (auto &RI : VS->refs()) {
+          const auto &VMI = GUIDToValueIdMap.find(RI);
+          unsigned RefId;
+          // If this GUID doesn't have an entry, assign one.
+          if (VMI == GUIDToValueIdMap.end()) {
+            GUIDToValueIdMap[RI] = ++GlobalValueId;
+            RefId = GlobalValueId;
+          } else {
+            RefId = VMI->second;
+          }
+          NameVals.push_back(RefId);
+        }
+
+        // Record the starting offset of this summary entry for use
+        // in the VST entry. Add the current code size since the
+        // reader will invoke readRecord after the abbrev id read.
+        FI->setBitcodeIndex(Stream.GetCurrentBitNo() +
+                            Stream.GetAbbrevIDWidth());
+
+        // Emit the finished record.
+        Stream.EmitRecord(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS, NameVals,
+                          FSModRefsAbbrev);
+        NameVals.clear();
+        continue;
+      }
 
+      auto *FS = dyn_cast<FunctionSummary>(S);
+      assert(FS);
       NameVals.push_back(I.getModuleId(FS->modulePath()));
-      NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage()));
+      NameVals.push_back(getEncodedLinkage(FS->linkage()));
       NameVals.push_back(FS->instCount());
+      NameVals.push_back(FS->refs().size());
+
+      for (auto &RI : FS->refs()) {
+        const auto &VMI = GUIDToValueIdMap.find(RI);
+        unsigned RefId;
+        // If this GUID doesn't have an entry, assign one.
+        if (VMI == GUIDToValueIdMap.end()) {
+          GUIDToValueIdMap[RI] = ++GlobalValueId;
+          RefId = GlobalValueId;
+        } else {
+          RefId = VMI->second;
+        }
+        NameVals.push_back(RefId);
+      }
+
+      bool HasProfileData = false;
+      for (auto &EI : FS->edges()) {
+        HasProfileData |= EI.second.ProfileCount != 0;
+        if (HasProfileData)
+          break;
+      }
+
+      for (auto &EI : FS->edges()) {
+        const auto &VMI = GUIDToValueIdMap.find(EI.first);
+        // If this GUID doesn't have an entry, it doesn't have a function
+        // summary and we don't need to record any calls to it.
+        if (VMI == GUIDToValueIdMap.end())
+          continue;
+        NameVals.push_back(VMI->second);
+        assert(EI.second.CallsiteCount > 0 && "Expected at least one callsite");
+        NameVals.push_back(EI.second.CallsiteCount);
+        if (HasProfileData)
+          NameVals.push_back(EI.second.ProfileCount);
+      }
 
       // Record the starting offset of this summary entry for use
       // in the VST entry. Add the current code size since the
       // reader will invoke readRecord after the abbrev id read.
       FI->setBitcodeIndex(Stream.GetCurrentBitNo() + Stream.GetAbbrevIDWidth());
 
+      unsigned FSAbbrev =
+          (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
+      unsigned Code =
+          (HasProfileData ? bitc::FS_COMBINED_PROFILE : bitc::FS_COMBINED);
+
       // Emit the finished record.
-      Stream.EmitRecord(bitc::FS_CODE_COMBINED_ENTRY, NameVals, FSAbbrev);
+      Stream.EmitRecord(Code, NameVals, FSAbbrev);
       NameVals.clear();
     }
   }
 
   Stream.ExitBlock();
 }
 
 // Create the "IDENTIFICATION_BLOCK_ID" containing a single string with the
static void WriteIdentificationBlock(const Module *M, BitstreamWriter &Stream) {
   SmallVector<unsigned, 1> Vals = {bitc::BITCODE_CURRENT_EPOCH};
   Stream.EmitRecord(bitc::IDENTIFICATION_CODE_EPOCH, Vals, EpochAbbrev);
   Stream.ExitBlock();
 }
 
 /// WriteModule - Emit the specified module to the bitstream.
 static void WriteModule(const Module *M, BitstreamWriter &Stream,
                         bool ShouldPreserveUseListOrder,
-                        uint64_t BitcodeStartBit, bool EmitFunctionSummary) {
+                        uint64_t BitcodeStartBit, bool EmitSummaryIndex) {
   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 
   SmallVector<unsigned, 1> Vals;
   unsigned CurVersion = 1;
   Vals.push_back(CurVersion);
   Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
 
   // Analyze the module, enumerating globals, functions, etc.
static void WriteModule(const Module *M, BitstreamWriter &Stream,
 
   // Emit module-level use-lists.
   if (VE.shouldPreserveUseListOrder())
     WriteUseListBlock(nullptr, VE, Stream);
 
   WriteOperandBundleTags(M, Stream);
 
   // Emit function bodies.
-  DenseMap<const Function *, std::unique_ptr<FunctionInfo>> FunctionIndex;
+  DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> FunctionIndex;
   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F)
     if (!F->isDeclaration())
-      WriteFunction(*F, VE, Stream, FunctionIndex, EmitFunctionSummary);
+      WriteFunction(*F, M, VE, Stream, FunctionIndex, EmitSummaryIndex);
 
   // Need to write after the above call to WriteFunction which populates
   // the summary information in the index.
-  if (EmitFunctionSummary)
-    WritePerModuleFunctionSummary(FunctionIndex, M, VE, Stream);
+  if (EmitSummaryIndex)
+    WritePerModuleGlobalValueSummary(FunctionIndex, M, VE, Stream);
 
   WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream,
                         VSTOffsetPlaceholder, BitcodeStartBit, &FunctionIndex);
 
   Stream.ExitBlock();
 }
 
 /// EmitDarwinBCHeader - If generating a bc file on darwin, we have to emit a
static void WriteBitcodeHeader(BitstreamWriter &Stream) {
   Stream.Emit(0xE, 4);
   Stream.Emit(0xD, 4);
 }
 
 /// WriteBitcodeToFile - Write the specified module to the specified output
 /// stream.
 void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                               bool ShouldPreserveUseListOrder,
-                              bool EmitFunctionSummary) {
+                              bool EmitSummaryIndex) {
   SmallVector<char, 0> Buffer;
   Buffer.reserve(256*1024);
 
   // If this is darwin or another generic macho target, reserve space for the
   // header.
   Triple TT(M->getTargetTriple());
   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
     Buffer.insert(Buffer.begin(), BWH_HeaderSize, 0);
// Emit the module into the buffer.
 
     // Emit the file header.
     WriteBitcodeHeader(Stream);
 
     WriteIdentificationBlock(M, Stream);
 
     // Emit the module.
     WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit,
-                EmitFunctionSummary);
+                EmitSummaryIndex);
   }
 
   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
     EmitDarwinBCHeaderAndTrailer(Buffer, TT);
 
   // Write the generated bitstream to "Out".
   Out.write((char*)&Buffer.front(), Buffer.size());
 }
 
-// Write the specified function summary index to the given raw output stream,
+// Write the specified module summary index to the given raw output stream,
 // where it will be written in a new bitcode block. This is used when
 // writing the combined index file for ThinLTO.
-void llvm::WriteFunctionSummaryToFile(const FunctionInfoIndex &Index,
-                                      raw_ostream &Out) {
+void llvm::WriteIndexToFile(const FunctionInfoIndex &Index, raw_ostream &Out) {
   SmallVector<char, 0> Buffer;
   Buffer.reserve(256 * 1024);
 
   BitstreamWriter Stream(Buffer);
 
   // Emit the bitcode header.
   WriteBitcodeHeader(Stream);
 
   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 
   SmallVector<unsigned, 1> Vals;
   unsigned CurVersion = 1;
   Vals.push_back(CurVersion);
   Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
 
+  // If we have a VST, write the VSTOFFSET record placeholder and record
+  // its offset.
+  uint64_t VSTOffsetPlaceholder = WriteValueSymbolTableForwardDecl(Stream);
+
   // Write the module paths in the combined index.
   WriteModStrings(Index, Stream);
 
-  // Write the function summary combined index records.
-  WriteCombinedFunctionSummary(Index, Stream);
+  // Assign unique value ids to all functions in the index for use
+  // in writing out the call graph edges. Save the mapping from GUID
+  // to the new global value id to use when writing those edges, which
+  // are currently saved in the index in terms of GUID.
+  std::map<uint64_t, unsigned> GUIDToValueIdMap;
+  unsigned GlobalValueId = 0;
+  for (auto &II : Index)
+    GUIDToValueIdMap[II.first] = ++GlobalValueId;
+
+  // Write the summary combined index records.
+  WriteCombinedGlobalValueSummary(Index, Stream, GUIDToValueIdMap,
+                                  GlobalValueId);
 
   // Need a special VST writer for the combined index (we don't have a
   // real VST and real values when this is invoked).
-  WriteCombinedValueSymbolTable(Index, Stream);
+  WriteCombinedValueSymbolTable(Index, Stream, GUIDToValueIdMap,
+                                VSTOffsetPlaceholder);
 
   Stream.ExitBlock();
 
   Out.write((char *)&Buffer.front(), Buffer.size());
 }

lib/Bitcode/Writer/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = BitWriter
 parent = Bitcode
-required_libraries = Core Support
+required_libraries = Analysis Core Support

lib/IR/FunctionInfo.cpp

 //===-- FunctionInfo.cpp - Function Info Index ----------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements the function info index and summary classes for the
+// This file implements the module index and summary classes for the
 // IR library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/FunctionInfo.h"
 #include "llvm/ADT/StringMap.h"
 using namespace llvm;
 
-// Create the combined function index/summary from multiple
+// Create the combined module index/summary from multiple
 // per-module instances.
 void FunctionInfoIndex::mergeFrom(std::unique_ptr<FunctionInfoIndex> Other,
                                   uint64_t NextModuleId) {
 
   StringRef ModPath;
-  for (auto &OtherFuncInfoLists : *Other) {
-    uint64_t FuncGUID = OtherFuncInfoLists.first;
-    FunctionInfoList &List = OtherFuncInfoLists.second;
+  for (auto &OtherGlobalValInfoLists : *Other) {
+    uint64_t ValueGUID = OtherGlobalValInfoLists.first;
+    GlobalValueInfoList &List = OtherGlobalValInfoLists.second;
 
-    // Assert that the func info list only has one entry, since we shouldn't
+    // Assert that the value info list only has one entry, since we shouldn't
     // have duplicate names within a single per-module index.
     assert(List.size() == 1);
-    std::unique_ptr<FunctionInfo> Info = std::move(List.front());
+    std::unique_ptr<GlobalValueInfo> Info = std::move(List.front());
 
-    // Skip if there was no function summary section.
-    if (!Info->functionSummary())
+    // Skip if there was no summary section.
+    if (!Info->summary())
       continue;
 
     // Add the module path string ref for this module if we haven't already
     // saved a reference to it.
     if (ModPath.empty())
-      ModPath =
-          addModulePath(Info->functionSummary()->modulePath(), NextModuleId);
+      ModPath = addModulePath(Info->summary()->modulePath(), NextModuleId);
     else
-      assert(ModPath == Info->functionSummary()->modulePath() &&
+      assert(ModPath == Info->summary()->modulePath() &&
              "Each module in the combined map should have a unique ID");
 
     // Note the module path string ref was copied above and is still owned by
     // the original per-module index. Reset it to the new module path
     // string reference owned by the combined index.
-    Info->functionSummary()->setModulePath(ModPath);
+    Info->summary()->setModulePath(ModPath);
 
-    // Add new function info to existing list. There may be duplicates when
-    // combining FunctionMap entries, due to COMDAT functions. Any local
-    // functions were given unique global IDs.
-    addFunctionInfo(FuncGUID, std::move(Info));
+    // Add new value info to existing list. There may be duplicates when
+    // combining GlobalValueMap entries, due to COMDAT values. Any local
+    // values were given unique global IDs.
+    addGlobalValueInfo(ValueGUID, std::move(Info));
   }
 }

lib/Object/FunctionIndexObjectFile.cpp

if (!ObjFile)
       return ObjFile.getError();
     return findBitcodeInObject(*ObjFile->get());
   }
   default:
     return object_error::invalid_file_type;
   }
 }
 
-// Looks for function index in the given memory buffer.
+// Looks for module summary index in the given memory buffer.
 // returns true if found, else false.
-bool FunctionIndexObjectFile::hasFunctionSummaryInMemBuffer(
+bool FunctionIndexObjectFile::hasGlobalValueSummaryInMemBuffer(
     MemoryBufferRef Object, DiagnosticHandlerFunction DiagnosticHandler) {
   ErrorOr<MemoryBufferRef> BCOrErr = findBitcodeInMemBuffer(Object);
   if (!BCOrErr)
     return false;
 
-  return hasFunctionSummary(BCOrErr.get(), DiagnosticHandler);
+  return hasGlobalValueSummary(BCOrErr.get(), DiagnosticHandler);
 }
 
 // Parse function index in the given memory buffer.
 // Return new FunctionIndexObjectFile instance containing parsed
 // function summary/index.
 ErrorOr<std::unique_ptr<FunctionIndexObjectFile>>
 FunctionIndexObjectFile::create(MemoryBufferRef Object,
                                 DiagnosticHandlerFunction DiagnosticHandler,

lib/Transforms/IPO/FunctionImport.cpp

while (!Worklist.empty()) {
     StringRef CalledFunctionName;
     unsigned Threshold;
     std::tie(CalledFunctionName, Threshold) = Worklist.pop_back_val();
     DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Process import for "
                  << CalledFunctionName << " with Threshold " << Threshold
                  << "\n");
 
     // Try to get a summary for this function call.
-    auto InfoList = Index.findFunctionInfoList(CalledFunctionName);
+    auto InfoList = Index.findGlobalValueInfoList(CalledFunctionName);
     if (InfoList == Index.end()) {
       DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": No summary for "
                    << CalledFunctionName << " Ignoring.\n");
       continue;
     }
     assert(!InfoList->second.empty() && "No summary, error at import?");
 
     // Comdat can have multiple entries, FIXME: what do we do with them?
     auto &Info = InfoList->second[0];
     assert(Info && "Nullptr in list, error importing summaries?\n");
 
-    auto *Summary = Info->functionSummary();
+    auto *Summary = dyn_cast<FunctionSummary>(Info->summary());
     if (!Summary) {
       // FIXME: in case we are lazyloading summaries, we can do it now.
       DEBUG(dbgs() << DestModule.getModuleIdentifier()
                    << ": Missing summary for  " << CalledFunctionName
                    << ", error at import?\n");
       llvm_unreachable("Missing summary");
     }
 

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

+; ModuleID = 'thinlto-function-summary-callgraph2.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 void @func() #0 !prof !2 {
+entry:
+    ret void
+}
+
+!2 = !{!"function_entry_count", i64 1}

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

+; ModuleID = 'thinlto-function-summary-callgraph2.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 void @func() #0 {
+entry:
+    ret void
+}
+

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

+; RUN: llvm-as -function-summary %s -o %t.o
+; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+; RUN: llvm-as -function-summary %p/Inputs/thinlto-function-summary-callgraph.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:       <GLOBALVAL_SUMMARY_BLOCK
+; See if the call to func is registered, using the expected value id,
+; callsite count and profile count
+; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=1 op5=1 op6=1/>
+; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+; CHECK-NEXT:  <VALUE_SYMTAB
+; CHECK-NEXT:    <FNENTRY {{.*}} record string = 'main'
+; External function func should have entry with value id 1
+; CHECK-NEXT:    <ENTRY {{.*}} op0=1 {{.*}} record string = 'func'
+; CHECK-NEXT:  </VALUE_SYMTAB>
+
+; COMBINED:       <GLOBALVAL_SUMMARY_BLOCK
+; COMBINED-NEXT:    <COMBINED
+; See if the call to func is registered, using the expected value id,
+; callsite count and profile count
+; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op4=1 op5=1 op6=1/>
+; COMBINED-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+; COMBINED-NEXT:  <VALUE_SYMTAB
+; Entry for function func should have entry with value id 1
+; COMBINED-NEXT:    <COMBINED_GVDEFENTRY {{.*}} op0=1 {{.*}} op2=7289175272376759421/>
+; COMBINED-NEXT:    <COMBINED_GVDEFENTRY
+; COMBINED-NEXT:  </VALUE_SYMTAB>
+
+; 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 !prof !2 {
+entry:
+    call void (...) @func()
+    ret i32 0
+}
+
+declare void @func(...) #1
+
+!2 = !{!"function_entry_count", i64 1}

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

+; RUN: llvm-as -function-summary %s -o %t.o
+; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+; RUN: llvm-as -function-summary %p/Inputs/thinlto-function-summary-callgraph.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:       <GLOBALVAL_SUMMARY_BLOCK
+; See if the call to func is registered, using the expected value id and
+; callsite count
+; CHECK-NEXT:    <PERMODULE {{.*}} op4=1 op5=1/>
+; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+; CHECK-NEXT:  <VALUE_SYMTAB
+; CHECK-NEXT:    <FNENTRY {{.*}} record string = 'main'
+; External function func should have entry with value id 1
+; CHECK-NEXT:    <ENTRY {{.*}} op0=1 {{.*}} record string = 'func'
+; CHECK-NEXT:  </VALUE_SYMTAB>
+
+; COMBINED:       <GLOBALVAL_SUMMARY_BLOCK
+; COMBINED-NEXT:    <COMBINED
+; See if the call to func is registered, using the expected value id and
+; callsite count
+; COMBINED-NEXT:    <COMBINED {{.*}} op4=1 op5=1/>
+; COMBINED-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+; COMBINED-NEXT:  <VALUE_SYMTAB
+; Entry for function func should have entry with value id 1
+; COMBINED-NEXT:    <COMBINED_GVDEFENTRY {{.*}} op0=1 {{.*}} op2=7289175272376759421/>
+; COMBINED-NEXT:    <COMBINED_GVDEFENTRY
+; COMBINED-NEXT:  </VALUE_SYMTAB>
+
+; 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 {
+entry:
+    call void (...) @func()
+    ret i32 0
+}
+
+declare void @func(...) #1

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

+; RUN: llvm-as -function-summary %s -o %t.o
+; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+
+; See if the calls and other references are recorded properly using the
+; expected value id and other information as appropriate (callsite cout
+; for calls). Use different linkage types for the various test cases to
+; distinguish the test cases here (op1 contains the linkage type).
+; Note that op3 contains the # non-call references.
+; This also ensures that we didn't include a call or reference to intrinsic
+; llvm.ctpop.i8.
+; CHECK:       <GLOBALVAL_SUMMARY_BLOCK
+; Function main contains call to func, as well as address reference to func:
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[MAINID:[0-9]+]] op1=0 {{.*}} op3=1 op4=[[FUNCID:[0-9]+]] op5=[[FUNCID]] op6=1/>
+; Function W contains a call to func3 as well as a reference to globalvar:
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[WID:[0-9]+]] op1=17 {{.*}} op3=1 op4=[[GLOBALVARID:[0-9]+]] op5=[[FUNC3ID:[0-9]+]] op6=1/>
+; Function X contains call to foo, as well as address reference to foo
+; which is in the same instruction as the call:
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[XID:[0-9]+]] op1=12 {{.*}} op3=1 op4=[[FOOID:[0-9]+]] op5=[[FOOID]] op6=1/>
+; Function Y contains call to func2, and ensures we don't incorrectly add
+; a reference to it when reached while earlier analyzing the phi using its
+; return value:
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[YID:[0-9]+]] op1=9 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]] op5=1/>
+; Function Z contains call to func2, and ensures we don't incorrectly add
+; a reference to it when reached while analyzing subsequent use of its return
+; value:
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[ZID:[0-9]+]] op1=19 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]] op5=1/>
+; Variable bar initialization contains address reference to func:
+; CHECK-DAG:    <PERMODULE_GLOBALVAR_INIT_REFS {{.*}} op0=[[BARID:[0-9]+]] op1=0 op2=[[FUNCID]]/>
+; CHECK:  </GLOBALVAL_SUMMARY_BLOCK>
+
+; CHECK-NEXT:  <VALUE_SYMTAB
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[BARID]] {{.*}} record string = 'bar'
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[FUNCID]] {{.*}} record string = 'func'
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[FOOID]] {{.*}} record string = 'foo'
+; CHECK-DAG:    <FNENTRY {{.*}} op0=[[MAINID]] {{.*}} record string = 'main'
+; CHECK-DAG:    <FNENTRY {{.*}} op0=[[WID]] {{.*}} record string = 'W'
+; CHECK-DAG:    <FNENTRY {{.*}} op0=[[XID]] {{.*}} record string = 'X'
+; CHECK-DAG:    <FNENTRY {{.*}} op0=[[YID]] {{.*}} record string = 'Y'
+; CHECK-DAG:    <FNENTRY {{.*}} op0=[[ZID]] {{.*}} record string = 'Z'
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[FUNC2ID]] {{.*}} record string = 'func2'
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[FUNC3ID]] {{.*}} record string = 'func3'
+; CHECK-DAG:    <ENTRY {{.*}} op0=[[GLOBALVARID]] {{.*}} record string = 'globalvar'
+; CHECK:  </VALUE_SYMTAB>
+
+; ModuleID = 'thinlto-function-summary-refgraph.ll'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@bar = global void (...)* bitcast (void ()* @func to void (...)*), align 8
+
+@globalvar = global i32 0, align 4
+
+declare void @func() #0
+declare i32 @func2(...) #1
+declare void @foo(i8* %F) #0
+declare i32 @func3(i32* dereferenceable(4)) #2
+
+; Function Attrs: nounwind uwtable
+define weak_odr void @W() #0 {
+entry:
+  %call = tail call i32 @func3(i32* nonnull dereferenceable(4) @globalvar)
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define available_externally void @X() #0 {
+entry:
+  call void @foo(i8* bitcast (void (i8*)* @foo to i8*))
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define private i32 @Y(i32 %i) #0 {
+entry:
+  %cmp3 = icmp slt i32 %i, 10
+  br i1 %cmp3, label %while.body.preheader, label %while.end
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  %j.05 = phi i32 [ %add, %while.body ], [ 0, %while.body.preheader ]
+  %i.addr.04 = phi i32 [ %inc, %while.body ], [ %i, %while.body.preheader ]
+  %inc = add nsw i32 %i.addr.04, 1
+  %call = tail call i32 (...) @func2() #2
+  %add = add nsw i32 %call, %j.05
+  %exitcond = icmp eq i32 %inc, 10
+  br i1 %exitcond, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:                               ; preds = %while.body
+  %add.lcssa = phi i32 [ %add, %while.body ]
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  %j.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %while.end.loopexit ]
+  ret i32 %j.0.lcssa
+}
+
+; Function Attrs: nounwind uwtable
+define linkonce_odr i32 @Z() #0 {
+entry:
+  %call = tail call i32 (...) @func2() #2
+  ret i32 %call
+}
+
+declare i8 @llvm.ctpop.i8(i8)
+
+; Function Attrs: nounwind uwtable
+define i32 @main() #0 {
+entry:
+  %retval = alloca i32, align 4
+  %foo = alloca void (...)*, align 8
+  store i32 0, i32* %retval, align 4
+  store void (...)* bitcast (void ()* @func to void (...)*), void (...)** %foo, align 8
+  %0 = load void (...)*, void (...)** %foo, align 8
+  call void (...) %0()
+  call void @func()
+  call i8  @llvm.ctpop.i8( i8 10 )
+  ret i32 0
+}

test/Bitcode/thinlto-function-summary.ll

 ; RUN: llvm-as -function-summary < %s | llvm-bcanalyzer -dump | FileCheck %s -check-prefix=BC
 ; Check for function summary block/records.
 
 ; Check the value ids in the function summary entries against the
 ; same in the ValueSumbolTable, to ensure the ordering is stable.
 ; Also check the linkage field on the summary entries.
-; BC: <FUNCTION_SUMMARY_BLOCK
-; BC-NEXT: <PERMODULE_ENTRY {{.*}} op0=1 op1=0
-; BC-NEXT: <PERMODULE_ENTRY {{.*}} op0=2 op1=0
-; BC-NEXT: <PERMODULE_ENTRY {{.*}} op0=4 op1=3
-; BC-NEXT: </FUNCTION_SUMMARY_BLOCK
+; BC: <GLOBALVAL_SUMMARY_BLOCK
+; BC-NEXT: <PERMODULE {{.*}} op0=1 op1=0
+; BC-NEXT: <PERMODULE {{.*}} op0=2 op1=0
+; BC-NEXT: <PERMODULE {{.*}} op0=4 op1=3
+; BC-NEXT: </GLOBALVAL_SUMMARY_BLOCK
 ; BC-NEXT: <VALUE_SYMTAB
 ; BC-NEXT: <FNENTRY {{.*}} op0=1 {{.*}}> record string = 'foo'
 ; BC-NEXT: <FNENTRY {{.*}} op0=2 {{.*}}> record string = 'bar'
 ; BC-NEXT: <FNENTRY {{.*}} op0=4 {{.*}}> record string = 'f'
 
 ; RUN: llvm-as -function-summary < %s | llvm-dis | FileCheck %s
 ; Check that this round-trips correctly.
 

test/Bitcode/thinlto-summary-linkage-types.ll

 ; Check the linkage types in both the per-module and combined summaries.
 ; RUN: llvm-as -function-summary %s -o %t.o
 ; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
 ; RUN: llvm-lto -thinlto -o %t2 %t.o
 ; RUN: llvm-bcanalyzer -dump %t2.thinlto.bc | FileCheck %s --check-prefix=COMBINED
 
 define private void @private()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=9
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=9
+; CHECK: <PERMODULE {{.*}} op1=9
+; COMBINED-DAG: <COMBINED {{.*}} op1=9
 {
   ret void
 }
 
 define internal void @internal()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=3
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=3
+; CHECK: <PERMODULE {{.*}} op1=3
+; COMBINED-DAG: <COMBINED {{.*}} op1=3
 {
   ret void
 }
 
 define available_externally void @available_externally()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=12
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=12
+; CHECK: <PERMODULE {{.*}} op1=12
+; COMBINED-DAG: <COMBINED {{.*}} op1=12
 {
   ret void
 }
 
 define linkonce void @linkonce()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=18
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=18
+; CHECK: <PERMODULE {{.*}} op1=18
+; COMBINED-DAG: <COMBINED {{.*}} op1=18
 {
   ret void
 }
 
 define weak void @weak()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=16
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=16
+; CHECK: <PERMODULE {{.*}} op1=16
+; COMBINED-DAG: <COMBINED {{.*}} op1=16
 {
   ret void
 }
 
 define linkonce_odr void @linkonce_odr()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=19
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=19
+; CHECK: <PERMODULE {{.*}} op1=19
+; COMBINED-DAG: <COMBINED {{.*}} op1=19
 {
   ret void
 }
 
 define weak_odr void @weak_odr()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=17
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=17
+; CHECK: <PERMODULE {{.*}} op1=17
+; COMBINED-DAG: <COMBINED {{.*}} op1=17
 {
   ret void
 }
 
 define external void @external()
-; CHECK: <PERMODULE_ENTRY {{.*}} op1=0
-; COMBINED-DAG: <COMBINED_ENTRY {{.*}} op1=0
+; CHECK: <PERMODULE {{.*}} op1=0
+; COMBINED-DAG: <COMBINED {{.*}} op1=0
 {
   ret void
 }

test/tools/gold/X86/thinlto.ll

 
 ; NM: T f
 ; NM2: T {{f|g}}
 
 ; COMBINED: <MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: </MODULE_STRTAB_BLOCK
-; COMBINED-NEXT: <FUNCTION_SUMMARY_BLOCK
-; COMBINED-NEXT: <COMBINED_ENTRY
-; COMBINED-NEXT: <COMBINED_ENTRY
-; COMBINED-NEXT: </FUNCTION_SUMMARY_BLOCK
+; COMBINED-NEXT: <GLOBALVAL_SUMMARY_BLOCK
+; COMBINED-NEXT: <COMBINED
+; COMBINED-NEXT: <COMBINED
+; COMBINED-NEXT: </GLOBALVAL_SUMMARY_BLOCK
 ; COMBINED-NEXT: <VALUE_SYMTAB
-; Check that the format is: op0=offset, op1=funcguid, where funcguid is
-; the lower 64 bits of the function name MD5.
-; COMBINED-NEXT: <COMBINED_FNENTRY abbrevid={{[0-9]+}} op0={{[0-9]+}} op1={{-3706093650706652785|-5300342847281564238}}
-; COMBINED-NEXT: <COMBINED_FNENTRY abbrevid={{[0-9]+}} op0={{[0-9]+}} op1={{-3706093650706652785|-5300342847281564238}}
+; Check that the format is: op0=valueid, op1=offset, op2=funcguid,
+; where funcguid is the lower 64 bits of the function name MD5.
+; COMBINED-NEXT: <COMBINED_GVDEFENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{[0-9]+}} op2={{-3706093650706652785|-5300342847281564238}}
+; COMBINED-NEXT: <COMBINED_GVDEFENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{[0-9]+}} op2={{-3706093650706652785|-5300342847281564238}}
 ; COMBINED-NEXT: </VALUE_SYMTAB
 
 declare void @g(...)
 
 define void @f() {
 entry:
   call void (...) @g()
   ret void
 }

test/tools/llvm-lto/thinlto.ll

 ; Test combined function index generation for ThinLTO via llvm-lto.
 ; RUN: llvm-as -function-summary %s -o %t.o
 ; RUN: llvm-as -function-summary %p/Inputs/thinlto.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
 ; RUN: not test -e %t3
 
 ; COMBINED: <MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: </MODULE_STRTAB_BLOCK
-; COMBINED-NEXT: <FUNCTION_SUMMARY_BLOCK
-; COMBINED-NEXT: <COMBINED_ENTRY
-; COMBINED-NEXT: <COMBINED_ENTRY
-; COMBINED-NEXT: </FUNCTION_SUMMARY_BLOCK
+; COMBINED-NEXT: <GLOBALVAL_SUMMARY_BLOCK
+; COMBINED-NEXT: <COMBINED
+; COMBINED-NEXT: <COMBINED
+; COMBINED-NEXT: </GLOBALVAL_SUMMARY_BLOCK
 ; COMBINED-NEXT: <VALUE_SYMTAB
-; Check that the format is: op0=offset, op1=funcguid, where funcguid is
-; the lower 64 bits of the function name MD5.
-; COMBINED-NEXT: <COMBINED_FNENTRY abbrevid={{[0-9]+}} op0={{[0-9]+}} op1={{-3706093650706652785|-5300342847281564238}}
-; COMBINED-NEXT: <COMBINED_FNENTRY abbrevid={{[0-9]+}} op0={{[0-9]+}} op1={{-3706093650706652785|-5300342847281564238}}
+; Check that the format is: op0=valueid, op1=offset, op2=funcguid,
+; where funcguid is the lower 64 bits of the function name MD5.
+; COMBINED-NEXT: <COMBINED_GVDEFENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{[0-9]+}} op2={{-3706093650706652785|-5300342847281564238}}
+; COMBINED-NEXT: <COMBINED_GVDEFENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{[0-9]+}} op2={{-3706093650706652785|-5300342847281564238}}
 ; COMBINED-NEXT: </VALUE_SYMTAB
 
 define void @f() {
 entry:
   ret void
 }

tools/gold/gold-plugin.cpp

 getFunctionIndexForFile(claimed_file &F, ld_plugin_input_file &Info) {
   const void *View = getSymbolsAndView(F);
 
   MemoryBufferRef BufferRef(StringRef((const char *)View, Info.filesize),
                             Info.name);
 
   // Don't bother trying to build an index if there is no summary information
   // in this bitcode file.
-  if (!object::FunctionIndexObjectFile::hasFunctionSummaryInMemBuffer(
+  if (!object::FunctionIndexObjectFile::hasGlobalValueSummaryInMemBuffer(
           BufferRef, diagnosticHandler))
     return std::unique_ptr<FunctionInfoIndex>(nullptr);
 
   ErrorOr<std::unique_ptr<object::FunctionIndexObjectFile>> ObjOrErr =
       object::FunctionIndexObjectFile::create(BufferRef, diagnosticHandler);
 
   if (std::error_code EC = ObjOrErr.getError())
     message(LDPL_FATAL, "Could not read function index bitcode from file : %s",
if (options::thinlto) {
     }
 
     std::error_code EC;
     raw_fd_ostream OS(output_name + ".thinlto.bc", EC,
                       sys::fs::OpenFlags::F_None);
     if (EC)
       message(LDPL_FATAL, "Unable to open %s.thinlto.bc for writing: %s",
               output_name.data(), EC.message().c_str());
-    WriteFunctionSummaryToFile(CombinedIndex, OS);
+    WriteIndexToFile(CombinedIndex, OS);
     OS.close();
 
     if (options::thinlto_index_only) {
       cleanup_hook();
       exit(0);
     }
 
     thinLTOBackends(ApiFile, CombinedIndex);

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

static const char *GetBlockName(unsigned BlockID,
   case bitc::FUNCTION_BLOCK_ID:        return "FUNCTION_BLOCK";
   case bitc::IDENTIFICATION_BLOCK_ID:
     return "IDENTIFICATION_BLOCK_ID";
   case bitc::VALUE_SYMTAB_BLOCK_ID:    return "VALUE_SYMTAB";
   case bitc::METADATA_BLOCK_ID:        return "METADATA_BLOCK";
   case bitc::METADATA_KIND_BLOCK_ID:   return "METADATA_KIND_BLOCK";
   case bitc::METADATA_ATTACHMENT_ID:   return "METADATA_ATTACHMENT_BLOCK";
   case bitc::USELIST_BLOCK_ID:         return "USELIST_BLOCK_ID";
-  case bitc::FUNCTION_SUMMARY_BLOCK_ID:
-                                       return "FUNCTION_SUMMARY_BLOCK";
+  case bitc::GLOBALVAL_SUMMARY_BLOCK_ID:
+    return "GLOBALVAL_SUMMARY_BLOCK";
   case bitc::MODULE_STRTAB_BLOCK_ID:   return "MODULE_STRTAB_BLOCK";
   }
 }
 
 /// GetCodeName - Return a symbolic code name if known, otherwise return
 /// null.
 static const char *GetCodeName(unsigned CodeID, unsigned BlockID,
                                const BitstreamReader &StreamFile,
default: return nullptr;
       STRINGIFY_CODE(FUNC_CODE, INST_GEP)
     }
   case bitc::VALUE_SYMTAB_BLOCK_ID:
     switch (CodeID) {
     default: return nullptr;
     STRINGIFY_CODE(VST_CODE, ENTRY)
     STRINGIFY_CODE(VST_CODE, BBENTRY)
     STRINGIFY_CODE(VST_CODE, FNENTRY)
-    STRINGIFY_CODE(VST_CODE, COMBINED_FNENTRY)
+    STRINGIFY_CODE(VST_CODE, COMBINED_GVDEFENTRY)
+    STRINGIFY_CODE(VST_CODE, COMBINED_ENTRY)
     }
   case bitc::MODULE_STRTAB_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(MST_CODE, ENTRY)
     }
-  case bitc::FUNCTION_SUMMARY_BLOCK_ID:
+  case bitc::GLOBALVAL_SUMMARY_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
-      STRINGIFY_CODE(FS_CODE, PERMODULE_ENTRY)
-      STRINGIFY_CODE(FS_CODE, COMBINED_ENTRY)
+      STRINGIFY_CODE(FS, PERMODULE)
+      STRINGIFY_CODE(FS, PERMODULE_PROFILE)
+      STRINGIFY_CODE(FS, PERMODULE_GLOBALVAR_INIT_REFS)
+      STRINGIFY_CODE(FS, COMBINED)
+      STRINGIFY_CODE(FS, COMBINED_PROFILE)
+      STRINGIFY_CODE(FS, COMBINED_GLOBALVAR_INIT_REFS)
     }
   case bitc::METADATA_ATTACHMENT_ID:
     switch(CodeID) {
     default:return nullptr;
       STRINGIFY_CODE(METADATA, ATTACHMENT)
     }
   case bitc::METADATA_BLOCK_ID:
     switch(CodeID) {

tools/llvm-lto/llvm-lto.cpp

if (!Index)
       continue;
     CombinedIndex.mergeFrom(std::move(Index), ++NextModuleId);
   }
   std::error_code EC;
   assert(!OutputFilename.empty());
   raw_fd_ostream OS(OutputFilename + ".thinlto.bc", EC,
                     sys::fs::OpenFlags::F_None);
   error(EC, "error opening the file '" + OutputFilename + ".thinlto.bc'");
-  WriteFunctionSummaryToFile(CombinedIndex, OS);
+  WriteIndexToFile(CombinedIndex, OS);
   OS.close();
 }
 
 int main(int argc, char **argv) {
   // Print a stack trace if we signal out.
   sys::PrintStackTraceOnErrorSignal();
   PrettyStackTraceProgram X(argc, argv);