This is an archive of the discontinued LLVM Phabricator instance.

[Propeller] Encode address offsets of basic blocks relative to the end of the previous basic blocks.
ClosedPublic

Authored by rahmanl on Mar 9 2022, 4:27 PM.

Details

Summary

This is a resurrection of D106421 with the change that it keeps backward-compatibility. This means decoding the previous version of LLVM_BB_ADDR_MAP will work. This is required as the profile mapping tool is not released with LLVM (AutoFDO). As suggested by @jhenderson we rename the original section type value to SHT_LLVM_BB_ADDR_MAP_V0 and assign a new value to the SHT_LLVM_BB_ADDR_MAP section type. The new encoding adds a version byte to each function entry to specify the encoding version for that function. This patch also adds a feature byte to be used with more flexibility in the future. An use-case example for the feature field is encoding multi-section functions more concisely using a different format.

Conceptually, the new encoding emits basic block offsets and sizes as label differences between each two consecutive basic block begin and end label. When decoding, offsets must be aggregated along with basic block sizes to calculate the final offsets of basic blocks relative to the function address.

This encoding uses smaller values compared to the existing one (offsets relative to function symbol).
Smaller values tend to occupy fewer bytes in ULEB128 encoding. As a result, we get about 17% total reduction in the size of the bb-address-map section (from about 11MB to 9MB for the clang PGO binary).
The extra two bytes (version and feature fields) incur a small 3% size overhead to the LLVM_BB_ADDR_MAP section size.

Diff Detail

Event Timeline

rahmanl created this revision.Mar 9 2022, 4:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 9 2022, 4:27 PM
rahmanl retitled this revision from Encode address offsets of basic blocks relative to the end of the previous basic blocks. to [Propeller] Encode address offsets of basic blocks relative to the end of the previous basic blocks..Mar 9 2022, 11:08 PM
rahmanl edited the summary of this revision. (Show Details)
rahmanl published this revision for review.Mar 10 2022, 12:04 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2022, 12:04 AM
rahmanl updated this revision to Diff 414287.Mar 10 2022, 12:26 AM

Cleanup unrelated changes.

rahmanl edited reviewers, added: tmsriram; removed: shenhan, jhenderson.Apr 11 2022, 4:00 PM

I think that Extensions.rst should be updated as well, including a description of the versioning scheme, the fact that the section name is now a semantically significant property, and a description of both the v0 and v1 formats.

rahmanl updated this revision to Diff 425871.Apr 28 2022, 11:54 AM

Update Extensions.rst.

rahmanl updated this revision to Diff 425872.Apr 28 2022, 11:56 AM

Remove empty lines.

rahmanl updated this revision to Diff 425903.Apr 28 2022, 2:14 PM

Add unit-tests for checking invalid bb-address-map version suffixes.

I think that Extensions.rst should be updated as well, including a description of the versioning scheme, the fact that the section name is now a semantically significant property, and a description of both the v0 and v1 formats.

Thanks for the note. Updated Extensions.rst.

Would you mind taking a look @jhenderson?

rahmanl updated this revision to Diff 429861.May 16 2022, 2:40 PM

Rebase again.

Has the spec for this been finalised anywhere? My main conceren is the use of section names to have semantic importance. ELF generally tries to avoid this, hence the use of section types, and it would be a shame to introduce this approach when there are other options. It would be far more preferable to include the version number in the section data somewhere, a bit like how most DWARF sections are encoded. I can think of one other possible way of doing this: change the section type value for version 1 and upwards, and rename the original value to something like SHT_LLVM_BB_ADDR_MAP_V0. Add the version field as the first N bytes (2 or 4 probably) of the new section type. Parsers understanding the old data structure only won't recognise the new section type as a recognised format. This is good because it doesn't mislead people by printing incorrect offsets (in addition to not needing to rely on the section name).

llvm/docs/Extensions.rst
404–415
432–452

Do we need a note saying that v0 BB Addr maps may not have the version suffix in the section name?

llvm/lib/Object/ELF.cpp
641

int seems like an odd type for Version. It probably should be some unsigned type?

jhenderson added inline comments.May 17 2022, 1:27 AM
llvm/lib/Object/ELF.cpp
644–648

Coding standards say to use lower-case for first letter of error messages.

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
75

For V1 output, I feel like it would be useful to have both the raw offset and the calculated offset printed. I'm not sure exactly what would be the best way of doing that though.

Has the spec for this been finalised anywhere? My main conceren is the use of section names to have semantic importance. ELF generally tries to avoid this, hence the use of section types, and it would be a shame to introduce this approach when there are other options. It would be far more preferable to include the version number in the section data somewhere, a bit like how most DWARF sections are encoded. I can think of one other possible way of doing this: change the section type value for version 1 and upwards, and rename the original value to something like SHT_LLVM_BB_ADDR_MAP_V0. Add the version field as the first N bytes (2 or 4 probably) of the new section type. Parsers understanding the old data structure only won't recognise the new section type as a recognised format. This is good because it doesn't mislead people by printing incorrect offsets (in addition to not needing to rely on the section name).

Thanks for the review. And apologies for my delayed followup.
We did consider several ideas for storing the version.

  1. Store it for each function: wasteful for object-file size
  2. Store it once in a different COMDAT section of the object file and have the linker merge them all: Would not work for mixing different versions.
  3. Store it outside the section as a weak symbol. (Similar to 2).
  4. Store it inside the section metadata: For example, we can suffix the section name with the version name and then have the LLVM_BB_ADDR_MAP reading code read sections of different versions.

We chose idea 4 mostly for convenience reasons.

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

One thing to consider is how DWARF debug sections are designed. Most DWARF sections have a format that is something akin to the following:

header consisting of:
  unit length - 32 or 64-bit number indicating the size of this input section
  version - uint16_t for the section's version
  other metadata as appropriate for the section type
actual section payload

The linker concatenates these together into a single output section. Consumers iterate over a section by inspecting the first header, using that to parse the immediate next payload and then, if the unit length doesn't mean the end of section has been reached, parses the next header and so on. In your case, you could have a single "header" (which might just consist of a length and version), followed by many functions that conform to that header. Consumers would just have to know how to iterate over them and then, if there are multiple versions, handle the corresponding payload accordingly. The linker would just concatenate together.

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

One thing to consider is how DWARF debug sections are designed. Most DWARF sections have a format that is something akin to the following:

header consisting of:
  unit length - 32 or 64-bit number indicating the size of this input section
  version - uint16_t for the section's version
  other metadata as appropriate for the section type
actual section payload

The linker concatenates these together into a single output section. Consumers iterate over a section by inspecting the first header, using that to parse the immediate next payload and then, if the unit length doesn't mean the end of section has been reached, parses the next header and so on. In your case, you could have a single "header" (which might just consist of a length and version), followed by many functions that conform to that header. Consumers would just have to know how to iterate over them and then, if there are multiple versions, handle the corresponding payload accordingly. The linker would just concatenate together.

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

Yes, that's what I'd expect. (It's worth noting that -function-sections imposes other overheads like the ELF section header, so a couple of bytes is comparatively small).

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

Yes, that's what I'd expect. (It's worth noting that -function-sections imposes other overheads like the ELF section header, so a couple of bytes is comparatively small).

Correct, but with the difference that the ELF section header won't be repeated many times in the final linked section, but the version number will.

rahmanl updated this revision to Diff 437461.Jun 16 2022, 12:32 AM
rahmanl marked 5 inline comments as done.

Encode the version number as a field of each function's LLVM_BB_ADDR_MAP entry instead of section names.

rahmanl edited the summary of this revision. (Show Details)Jun 16 2022, 1:24 AM
rahmanl edited the summary of this revision. (Show Details)Jun 16 2022, 11:22 AM
rahmanl updated this revision to Diff 437700.Jun 16 2022, 2:09 PM
  • Fix tests.
rahmanl added inline comments.Jun 16 2022, 2:10 PM
llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
75

I think we should only care about the final calculated offset for verification. The raw offset is just an encoding technicality and should not be given much semantic importance.

rahmanl updated this revision to Diff 437706.Jun 16 2022, 2:30 PM
  • clang-format.
jhenderson added inline comments.Jun 17 2022, 1:42 AM
llvm/docs/Extensions.rst
399

Does this need extending?

456

Nit: looks like this line has gained some trailing whitespace somehow.

llvm/lib/Object/ELF.cpp
670–673

Nit: no need for braces here.

llvm/test/CodeGen/X86/basic-block-sections-labels.ll
49–50

It would be good if these could have comments in the asm indicating what they represent (i.e. version and feature), for those not familiar with the format.

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
193

I wonder if it would be better to link against the same section? This would allow you to compare the differences more easily.

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
109

Typo

129–132

I actually think the Version field should be mandatory. It seems odd to pin the default to the oldest version, but we also shouldn't have it change when a new version is added as otherwise it'll cause existing YAML to change behaviour.

132

Nit: let's line things up.

181

Nit

llvm/tools/obj2yaml/elf2yaml.cpp
897

We probably should emit an error for unsupported versions. The file format may change in a future version such that the existing parsing will break in nasty ways. Same probably goes for llvm-readobj.

rahmanl updated this revision to Diff 438177.Jun 19 2022, 12:04 AM
rahmanl marked 10 inline comments as done.
  • Address comments
rahmanl added inline comments.Jun 19 2022, 12:04 AM
llvm/docs/Extensions.rst
399

I interpreted your comment as we should remove it. Did you mean we should add a separate extension for this?

llvm/lib/Object/ELF.cpp
670–673

Also removed braces elsewhere.

jhenderson added inline comments.Jun 20 2022, 1:30 AM
llvm/docs/Extensions.rst
399

I was referring to the underline, which didn't match the modified header length sorry for the confusion! I'm happy either way with having just the "normal" title, or both mentioned in the header.

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
61
87

This didn't occur to me until now, but it's unfortunate that we have to have duplicate check patterns and near-duplicate YAML to do the v0 comparison check. I believe we can avoid it as follows:

  1. Have an additional YAML file that just describes the section, with the Type (and potentially Version) field parameterised.
  2. Create two ELF objects from this YAML, one with each of the two section types, the newer type having an explicit Version 0.
  3. Run llvm-readobj twice, to dump each of them individually.
  4. Use the same check pattern for the pair of these invocations.

What do you think?

196

Ah, that's an unfortunate side-effect. I think we should aim to avoid it somehow. About the best idea I have for this is to use different struct types in the ELFYAML code for SHT_LLVM_BB_ADDR_MAP_V0 entries and those in SHT_LLVM_BB_ADDR_MAP sections. This also means you can't set Features when it doesn't make sense (which is a good thing).

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
131–133

Any particular reason you have a double space between the colon and value here and below?

rahmanl updated this revision to Diff 438764.Jun 21 2022, 11:00 AM
rahmanl marked 5 inline comments as done.
  • Use the same checks for SHT_LLVM_BB_ADDR_MAP (with version=0) and SHT_LLVM_BB_ADDR_MAP_V0.

Thanks for the review @jhenderson

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
196

The problem is I would have to add alternative structs for BBAddrMapSection and BBAddrMapEntry and also define new mapping functions and writeSectionContent (with mostly identical code) for the SHT_LLVM_BB_ADDR_MAP_V0 type. We should be able to fully deprecate SHT_LLVM_BB_ADDR_MAP_V0 in a few months. So maybe this test won't stay around for too long. Of course, future versions will still use the same SHT_LLVM_BB_ADDR_MAP section type and therefore, new YAML fields will be optional (even if they are required for the new versions). So we won't have a major issue. Can I keep it as is?

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
131–133

It should be 3 spaces because of NumBlocks being used sometime. Aligned the YAML keys in this test more carefully.

jhenderson added inline comments.Jun 23 2022, 12:44 AM
llvm/lib/Object/ELF.cpp
671–672

Test case?

Also, the type is "SHT_LLVM_BB_ADDR_MAP", so probably wants to include the SHT_ too, to match (and be consistent with other error messages)

llvm/test/CodeGen/X86/basic-block-sections-labels-functions-sections.ll
13

Should we instead be including the version etc bytes? (I don't mind, just trying to understand the thought process)

35

If you're adding the comment here, I'd also add it to the other cases above (plus it makes it more robust, since it reduces the chance of spurious matches)

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
196

Yeah, leave as-is. Thanks for the explanation.

213

Nit: double blank line.

221

Super Nit: here and throughout, --check-prefixes -> --check-prefix when there's only one prefix to check (optional though - if you prefer to leave as-is, that's fine).

249

Nit: spurious extra line?

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
131–133

FWIW, I only align within the individual block, so here, I'd align with only the single space, and then use 3 spaces where NumBlocks is present. I don't care really though, as long as the spacing doesn't get excessive (at which point it can make readability an issue).

llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml
79–81

Nit: these should line up.

133

Nit: this should line up.

139

Nit: for consistent formatting, add a blank line before the YAML.

rahmanl updated this revision to Diff 439530.Jun 23 2022, 2:04 PM
rahmanl marked 11 inline comments as done.
  • Cleanups.
rahmanl updated this revision to Diff 439533.Jun 23 2022, 2:11 PM
  • Cleanups.
llvm/test/CodeGen/X86/basic-block-sections-labels-functions-sections.ll
13

You're right. We can do that.

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
131–133

Thanks. Adopted your approach.

rahmanl updated this revision to Diff 439536.Jun 23 2022, 2:16 PM
  • Cleanups.
rahmanl updated this revision to Diff 439537.Jun 23 2022, 2:21 PM
  • Cleanups.
jhenderson added inline comments.Jun 23 2022, 11:24 PM
llvm/lib/Object/ELF.cpp
671–672

Looks like there's still no test case?

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
180

FWIW, there are still 2 spaces here, rather than just 1.

rahmanl updated this revision to Diff 439818.Jun 24 2022, 10:40 AM
rahmanl marked 2 inline comments as done.
  • Cleanups.
llvm/lib/Object/ELF.cpp
671–672

Sorry, my response wasn't sent: I can't add a test to exercise this because I can't make a valid Yaml with an unsupported version number (ELFEmitter.cpp returns error if I specify version> 1), but I also don't think it's a good idea to remove that error handling. What do you suggest?

jhenderson added inline comments.Jun 27 2022, 12:53 AM
llvm/lib/Object/ELF.cpp
671–672

Hmm, good point. What do you think about the following proposal:

  1. Emit a warning rather than an error with yaml2obj.
  2. In this case, treat it as the max supported version (i.e. 1) and generate data like that, except with a value 2 for the Version field.

YAML is really only used for testing, so emitting an error blocks us from testing the actual production code we want to test, which seems unfortunate!

The alternative approach would be to use assembly, right?

rahmanl updated this revision to Diff 440457.Jun 27 2022, 7:46 PM
rahmanl marked an inline comment as done.
  • Add a llvm-readobj unit test with unsupported versions.
llvm/lib/Object/ELF.cpp
671–672

Done. Thanks for the suggestion.

jhenderson accepted this revision.Jun 28 2022, 1:25 AM

Two nits, otherwise LGTM.

llvm/lib/ObjectYAML/ELFEmitter.cpp
1402

Nit: semi-colon rather than comma is probably more correct

llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml
135
This revision is now accepted and ready to land.Jun 28 2022, 1:25 AM
rahmanl updated this revision to Diff 440621.Jun 28 2022, 7:41 AM
rahmanl marked 2 inline comments as done.
  • Final nits.
This revision was landed with ongoing or failed builds.Jun 28 2022, 7:43 AM
This revision was automatically updated to reflect the committed changes.