This is an archive of the discontinued LLVM Phabricator instance.

Function bitcode index in Value Symbol Table and lazy reading support
ClosedPublic

Authored by tejohnson on Sep 1 2015, 10:53 AM.

Details

Summary

Support for including the function bitcode indices in the Value Symbol
Table. This requires writing the VST after the function blocks, which in
turn requires a new VST forward declaration record encoding the offset of
the full VST (which is backpatched to contain the offset after the VST
is written).

This patch also enables the lazy function reader to use the new function
indices out of the VST. This support will be used by ThinLTO as well, which
will be in a follow on patch. Backwards compatibility with older bitcode
files is maintained.

A new test is also included.

The bitcode format (used for the lazy reader as well as the upcoming
ThinLTO patches) came out of discussions with Duncan and others and is
described here:
https://drive.google.com/file/d/0B036uwnWM6RWdnBLakxmeDdOeXc/view

Diff Detail

Repository
rL LLVM

Event Timeline

tejohnson updated this revision to Diff 33710.Sep 1 2015, 10:53 AM
tejohnson retitled this revision from to Function bitcode index in Value Symbol Table and lazy reading support.
tejohnson updated this object.
tejohnson added a subscriber: llvm-commits.
mehdi_amini edited edge metadata.Sep 1 2015, 3:48 PM

Hi Teresa,

Thanks for this patch, it looks good to me overall.
Please find some comments inline.

Also does it change the behavior of the LazyReader?
I don't know it enough to know if the fact that you are populating DeferredFunctionInfo using the module VST means it no longer needs to visit all the blocks. I'd expect llvm-extract to be constant time now, independently of the number of functions in the module.

Best,

Mehdi

include/llvm/Bitcode/BitstreamReader.h
237 ↗(On Diff #33710)

This is identical to getAbbrevIDWidth() two lines above, do you really need to alias it?

include/llvm/Bitcode/BitstreamWriter.h
126 ↗(On Diff #33710)

(Note: this shift/insert seems ok to me but I am not certain about if it is endian independent)

129 ↗(On Diff #33710)

It looks like the BackpatchWord change is independent, can it be in a separate commit?

521 ↗(On Diff #33710)

It seems this is not needed for this patch? I don't see any use of getOrCreateBlockInfo in the diff?

lib/Bitcode/Reader/BitcodeReader.cpp
1589 ↗(On Diff #33710)

I believe usually function argument are using the base class SmallVectorImpl<uint64_t> to avoid specializing on the size. The size is only relevant when you allocate it.

1693 ↗(On Diff #33710)

Minor comment: You can avoid the extra dyn_cast.

GlobalObject *GO;
// If this is an alias, need to get the actual Function object
// it aliases, in order to set up the DeferredFunctionInfo entry below.
auto *GA = dyn_cast<GlobalAlias>(V);
if (GA)
  GO = GA->getBaseObject();
else
  GO = dyn_cast<GlobalObject>(V);
assert(GO);
2987 ↗(On Diff #33710)

kudos for the comments everywhere! :)

3301 ↗(On Diff #33710)

Is Record.size() > 1 a valid possibility here?

4744 ↗(On Diff #33710)

Not sure from the comment: is there a possibility for the assert to fire on old format bitcode? LLVM is supposed to always be able to read old bitcode.

lib/Bitcode/Writer/BitcodeWriter.cpp
599 ↗(On Diff #33710)

Could be directly:

SmallVector<unsigned, 2> Vals{llvm::bitc::MODULE_CODE_VSTOFFSET, 0};
Stream.EmitRecordWithAbbrev(VSTOffsetAbbrev, Rec);
2132 ↗(On Diff #33710)

What if there has been a placeholder emitted in this case?

2188 ↗(On Diff #33710)

Why did you need to change it to use an iterator?
I believe you can still use Name instead of SI to have getValue() below.

for (const ValueName &Name : VST) {
   Value &Val = Name.getValue();

(I may have missed a use-case).

2203 ↗(On Diff #33710)

(Minor comment: Same extra dyn_cast as previously)

In D12536#237772, @joker.eph wrote:

Hi Teresa,

Thanks for this patch, it looks good to me overall.
Please find some comments inline.

Thanks, responses inline.

Also does it change the behavior of the LazyReader?
I don't know it enough to know if the fact that you are populating DeferredFunctionInfo using the module VST means it no longer needs to visit all the blocks.

Previously the lazy reader needs to parse through all the function blocks to populate DeferredFunctionInfo: Each time a function block is encountered by a call to parseModule, it records the bitcode offset (via BitcodeReader::rememberAndSkipFunctionBody) and stops parsing. Then whenever a function is materialized, it invokes BitcodeReader::findFunctionInStream, and if the DeferredFunctionInfo entry isn't found, parseModule is resumed from where it left off (and again records and skips the next function block and stops). findFunctionInStream will repeat this process until the function to be materialized is found. In the end, all the function blocks up through the last one materialized need to be walked through once to populate the full DeferredFunctionInfo (although their contents are skipped so it should be fairly fast).

With my patch, because the DeferredFunctionInfo is populated from the VST when we encounter the first function block, we can avoid this walk and stop parsing the module. I have an assert in findFunctionInStream that it should always find an entry for a function when the VSTOffset is not 0 - so essentially parseModule is never called from here to walk through the function blocks.

I'd expect llvm-extract to be constant time now, independently of the number of functions in the module.

Yes, that would be the case with this change.

Thanks,
Teresa

Best,

Mehdi

include/llvm/Bitcode/BitstreamReader.h
237 ↗(On Diff #33710)

I will remove this and switch to using getAbbrevIDWidth.

I originally didn't use the same name since I thought abbrev ids was a specific use case. But looking at the LLVM Bitcode File Format doc online I see that it does refer to this number as the abbrev id width, and block IDs are also referred to as (possibly builtin) abbrev IDs.

Will change the corresponding interface I added to the BitstreamWriter to getAbbrevIDWidth to be consistent.

include/llvm/Bitcode/BitstreamWriter.h
126 ↗(On Diff #33710)

It should be - this mirrors the way the CurValue is set in Emit() via shifting.

129 ↗(On Diff #33710)

It is only needed because of the new use case of being called to backpatch the VSTOffset, which is the first time a non-word aligned location is backpatched. But it is independent in that it could presumably be used in other contexts in the future. If you feel this is better as a separate commit I can split it out and commit it first.

521 ↗(On Diff #33710)

This was leftover from something else I tried and apparently forgot to clean up. Will move the public back down where it was.

lib/Bitcode/Reader/BitcodeReader.cpp
1589 ↗(On Diff #33710)

Got it, will change.

1693 ↗(On Diff #33710)

Good idea, will do.

2987 ↗(On Diff #33710)

Thanks!

3301 ↗(On Diff #33710)

Not in the current record design. It will only contain one record with a 32-bit word offset.

4744 ↗(On Diff #33710)

Right, I left in the support for the old bitcode. This comment is meant to ensure that if we fall into the old format handling (no DeferredFunctionInfo entry that was pre-populated) that we indeed have the old format (in which case there should not have been a VSTOFFSET record in the bitcode). So the assert will not fire with the old format. Will clarify this in the comment.

lib/Bitcode/Writer/BitcodeWriter.cpp
599 ↗(On Diff #33710)

True, hadn't seen that usage before but it looks like that would work. Will change.

2132 ↗(On Diff #33710)

WriteValueSymbolTableForwardDecl has the same early return, so there won't be one. Will add an assert here to ensure that VSTOffsetPlaceholder is 0 so that the two routines are forced to stay in sync on that.

2188 ↗(On Diff #33710)

Ah, looks like this loop was just rangified a few weeks back, and my merge went back to the old code since I was using the earlier code when I first implemented this handling. Will fix.

2203 ↗(On Diff #33710)

Will fix.

New patch being uploaded. A few additional notes below.

lib/Bitcode/Reader/BitcodeReader.cpp
1693 ↗(On Diff #33710)

Actually, did something similar but optimized for the common case where it isn't an alias: It does the dyn_cast to GlobalObject, and only does the dyn_cast to GlobalAlias if GO is null.

lib/Bitcode/Writer/BitcodeWriter.cpp
2203 ↗(On Diff #33710)

Ditto here - dyn_cast to Function, if null, do the alias check.

tejohnson updated this revision to Diff 33820.Sep 2 2015, 10:02 AM
tejohnson edited edge metadata.

Update per Mehdi's review comments.

Ping.

Please let me know if you have any other comments or if it looks ready to go in.

Thanks,
Teresa

This revision was automatically updated to reflect the committed changes.