This is an archive of the discontinued LLVM Phabricator instance.

[Propeller] Use Fixed MBB ID instead of volatile MachineBasicBlock::Number.
ClosedPublic

Authored by rahmanl on Apr 19 2021, 7:26 PM.

Details

Summary

Let Propeller use specialized IDs for basic blocks, instead of MBB number.

This allows optimizations not just prior to asm-printer, but throughout the entire codegen.
This patch only implements the functionality under the new LLVM_BB_ADDR_MAP version, but the old version is still being used. A later patch will change the used version.

Background

Today Propeller uses machine basic block (MBB) numbers, which already exist, to map native assembly to machine IR. This is done as follows.

  • Basic block addresses are captured and dumped into the LLVM_BB_ADDR_MAP section just before the AsmPrinter pass which writes out object files. This ensures that we have a mapping that is close to assembly.
  • Profiling mapping works by taking a virtual address of an instruction and looking up the LLVM_BB_ADDR_MAP section to find the MBB number it corresponds to.
  • While this works well today, we need to do better when we scale Propeller to target other Machine IR optimizations like spill code optimization. Register allocation happens earlier in the Machine IR pipeline and we need an annotation mechanism that is valid at that point.
  • The current scheme will not work in this scenario because the MBB number of a particular basic block is not fixed and changes over the course of codegen (via renumbering, adding, and removing the basic blocks).
  • In other words, the volatile MBB numbers do not provide a one-to-one correspondence throughout the lifetime of Machine IR. Profile annotation using MBB numbers is restricted to a fixed point; only valid at the exact point where it was dumped.
  • Further, the object file can only be dumped before AsmPrinter and cannot be dumped at an arbitrary point in the Machine IR pass pipeline. Hence, MBB numbers are not suitable and we need something else.
Solution

We propose using fixed unique incremental MBB IDs for basic blocks instead of volatile MBB numbers. These IDs are assigned upon the creation of machine basic blocks. We modify MachineFunction::CreateMachineBasicBlock to assign the fixed ID to every newly created basic block. It assigns MachineFunction::NextMBBID to the MBB ID and then increments it, which ensures having unique IDs.

To ensure correct profile attribution, multiple equivalent compilations must generate the same Propeller IDs. This is guaranteed as long as the MachineFunction passes run in the same order. Since the NextBBID variable is scoped to MachineFunction, interleaving of codegen for different functions won't cause any inconsistencies.

The new encoding is generated under the new version number 2 and we keep backward-compatibility with older versions.

Impact on Size of the LLVM_BB_ADDR_MAP Section

Emitting the Propeller ID results in a 23% increase in the size of the LLVM_BB_ADDR_MAP section for the clang binary.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
rahmanl updated this revision to Diff 338689.Apr 19 2021, 7:38 PM

Refactoring.

rahmanl updated this revision to Diff 341389.Apr 28 2021, 7:51 PM
  • Fix tests.
rahmanl edited the summary of this revision. (Show Details)Apr 29 2021, 8:02 PM
rahmanl updated this revision to Diff 343803.May 7 2021, 8:06 PM
  • Fix tests.
  • Add support for MIR printing and parsing.
rahmanl published this revision for review.May 7 2021, 8:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 7 2021, 8:08 PM
rahmanl edited the summary of this revision. (Show Details)May 7 2021, 8:09 PM
rahmanl updated this revision to Diff 364921.Aug 6 2021, 7:22 PM

Fix clang-tidy warnings.

rahmanl updated this revision to Diff 364924.Aug 6 2021, 7:52 PM

Add comments/Variable renaming.

CodeGen isn't really my thing, so I can't really review that side of things. The dumping/yaml2obj etc changes all seem fine, assuming the proposal as a whole is acceptable.

One thought I had: I was (perhaps incorrectly) under the impression that Propeller is something external to LLVM. It seems a bit backwards to be referring to it by name throughout this change, via code comments and variable names etc. Would it make more sense to use simply "ID" or something like "FixedID" or similar?

llvm/include/llvm/CodeGen/MachineBasicBlock.h
165
llvm/lib/CodeGen/MIRParser/MIParser.cpp
667
Herald added a project: Restricted Project. · View Herald TranscriptAug 4 2022, 11:25 AM
rahmanl updated this revision to Diff 466135.Oct 7 2022, 11:26 AM
  • Change PropellerID to BBID.
rahmanl updated this revision to Diff 466137.Oct 7 2022, 11:28 AM
  • clang-format.
rahmanl edited the summary of this revision. (Show Details)Oct 7 2022, 11:31 AM
rahmanl retitled this revision from Use Propeller ID instead of MBB IDs. to [Propeller] Use Fixed MBB ID instead of volatile `MachineBasicBlock::Number`..
rahmanl retitled this revision from [Propeller] Use Fixed MBB ID instead of volatile `MachineBasicBlock::Number`. to [Propeller] Use Fixed MBB ID instead of volatile MachineBasicBlock::Number..
rahmanl edited the summary of this revision. (Show Details)
rahmanl updated this revision to Diff 466178.Oct 7 2022, 2:16 PM
rahmanl marked 2 inline comments as done.
  • clang-format.

@jhenderson Thanks for the early review. The patch is ready for review again.

rahmanl updated this revision to Diff 466567.Oct 10 2022, 11:24 AM
  • Fix test.
jhenderson added inline comments.Oct 11 2022, 1:25 AM
llvm/include/llvm/CodeGen/BasicBlockSectionsProfileReader.h
35 ↗(On Diff #466567)

Is this comment still accurate? (It might be, I don't know).

llvm/lib/CodeGen/BasicBlockSections.cpp
232

Nit: this is not the LLVM naming style convention. The old name (as was in the original diff, and changed in an intermediate commit somewhere) was correct style. Since you're modifying this area of code, let's fix it.

269–270
rahmanl updated this revision to Diff 467182.Oct 12 2022, 10:06 AM
rahmanl marked 3 inline comments as done.
  • Address comments.

No more comments from me, thanks.

No more comments from me, thanks.

I appreciate the review @jhenderson

llvm/lib/CodeGen/BasicBlockSections.cpp
269–270

Changed the comment as it doesn't hold anymore.

rahmanl updated this revision to Diff 479368.Dec 1 2022, 11:11 AM
  • report error instead of assertions if entry block is displaced.
rahmanl updated this revision to Diff 479369.Dec 1 2022, 11:13 AM
  • report error instead of assertions if entry block is displaced.
jhenderson added inline comments.Dec 2 2022, 12:46 AM
llvm/lib/CodeGen/BasicBlockSections.cpp
308–311

Why report_fatal_error here? If this case can be hit by proper user code, should the error by propagated up to the call site? If not, why not an assertion?

rahmanl updated this revision to Diff 479712.Dec 2 2022, 12:17 PM
  • Changed check back to assert.
  • Changed the emitted BB address map version back to 1.
rahmanl updated this revision to Diff 479713.Dec 2 2022, 12:17 PM

clang-format.

rahmanl updated this revision to Diff 479714.Dec 2 2022, 12:18 PM

clang-format.

rahmanl updated this revision to Diff 479715.Dec 2 2022, 12:19 PM
  • clang-format.

In order to stage this, I changed this to emit the old version. I will need to submit another patch once the llvm is integrated into our create_llvm_prof tooling.

llvm/lib/CodeGen/BasicBlockSections.cpp
308–311

This is a hard failure and is not expected to happen. I changed to report_fatal_error to suppress the unused variable warning, but now I know I can used [[maybe_unused]] to do this.

rahmanl updated this revision to Diff 479904.Dec 4 2022, 1:02 AM
  • Changed the emitted BB address map version back to 1.
rahmanl updated this revision to Diff 479905.Dec 4 2022, 1:20 AM
  • Changed the emitted BB address map version back to 1.
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added a reviewer: zuban32. · View Herald Transcript
Herald added a reviewer: rafauler. · View Herald Transcript
Herald added a reviewer: Amir. · View Herald Transcript
Herald added a reviewer: maksfb. · View Herald Transcript
Herald added a reviewer: dang. · View Herald Transcript
Herald added a reviewer: NoQ. · View Herald Transcript
Herald added a reviewer: ributzka. · View Herald Transcript
Herald added a reviewer: dcaballe. · View Herald Transcript
Herald added a reviewer: njames93. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
rahmanl updated this revision to Diff 479906.Dec 4 2022, 1:29 AM
  • Rebase.
rahmanl removed projects: Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project.
rahmanl removed subscribers: StephenFan, Michael137, jholewinski and 128 others.
Herald added a project: Restricted Project. · View Herald TranscriptDec 4 2022, 1:31 AM
rahmanl edited the summary of this revision. (Show Details)Dec 4 2022, 1:43 AM
jhenderson added inline comments.Dec 4 2022, 11:59 PM
llvm/lib/CodeGen/BasicBlockSections.cpp
379

The note is unnecessary, since you've stated the same at the start of the comment.

rahmanl updated this revision to Diff 480595.Dec 6 2022, 1:20 PM
rahmanl marked 2 inline comments as done.

Refactoring and changing data structures.

tmsriram added inline comments.Dec 6 2022, 1:34 PM
llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
1158

It is okay to maintain both versions for now but we should deprecate the old version after some time, say 6 months? Can we add "TODOs" on code that should be deleted when that happens?

llvm/lib/CodeGen/BasicBlockSections.cpp
232

Please fix this too.

281

Add a TODO here to replace this with getBBID() when version 1 is deprecated.

302

Why did you remove the 4 here?

379

Please explicitly state the different purpose here and identify the comment block that needs to be deleted.

391

extra line.

llvm/lib/CodeGen/MachineBasicBlock.cpp
1629

TODO to replace all uses of this function with getBBID() when deprecated.

llvm/lib/CodeGen/MachineFunction.cpp
418

Please add a comment here on why this is needed.

rahmanl updated this revision to Diff 480605.Dec 6 2022, 1:37 PM

Remove redundant new line.

rahmanl updated this revision to Diff 480606.Dec 6 2022, 1:38 PM

Remove unused include.

rahmanl updated this revision to Diff 480657.Dec 6 2022, 3:44 PM
rahmanl marked 8 inline comments as done.
  • Address comments.
tmsriram accepted this revision.Dec 6 2022, 3:59 PM

LGTM. Please make sure all reviewers have approved the patch.

I want to add that this is a strong motivation to make Propeller's profile conversion tool a part of LLVM. This would get rid of the need to maintain multiple versions.

llvm/lib/CodeGen/BasicBlockSections.cpp
232

Rename BBID and BBCI / make sure it adheres to naming style convention.

281

Please fix this too.

This revision is now accepted and ready to land.Dec 6 2022, 3:59 PM
rahmanl updated this revision to Diff 480685.Dec 6 2022, 4:33 PM
rahmanl marked 2 inline comments as done.
  • Final comments.

Thanks Sri.

llvm/lib/CodeGen/BasicBlockSections.cpp
232

I think they adhere to the naming convention. James's original comment was about bbClusterInfo.

281

Added a single TODO in MachineBasicBlock.h.

302

This vector is allocated based on number of the blocks in sortBasicBlocksAndUpdateBranches.

llvm/lib/CodeGen/MachineBasicBlock.cpp
1629

Added TODO in the header file.

This revision was landed with ongoing or failed builds.Dec 6 2022, 10:50 PM
This revision was automatically updated to reflect the committed changes.
hokein added a subscriber: hokein.Dec 7 2022, 4:36 AM

This patch seems to break a build for one of our targets, I will share more details with you internally.

ashay-github added a subscriber: ashay-github.EditedDec 12 2022, 12:01 PM

Hello! It seems this patch breaks tests on Windows builds. For instance, at my end, the test in llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml produces AddressOffset: 0x2 instead of the expected AddressOffset: 0x1. The same test in Linux completes successfully.

It's possible that because the Phabricator instance does not add -DLLVM_INCLUDE_TOOLS=ON to the CMake invocation, we failed to catch this issue in CI. I can reproduce the issue locally using the following CMake command on Windows: cmake -GNinja -Bbuild -DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=host -DLLVM_INCLUDE_TOOLS=ON llvm && ninja -C build check-llvm-tools.

Here is the list of tests that fail:

Failed Tests (6):
  LLVM :: tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml
  LLVM :: tools/llvm-readobj/ELF/bb-addr-map.test
  LLVM :: tools/obj2yaml/ELF/bb-addr-map.yaml
  LLVM :: tools/yaml2obj/ELF/bb-addr-map.yaml
  LLVM-Unit :: Object/./ObjectTests.exe/ELFObjectFileTest/InvalidDecodeBBAddrMap
  LLVM-Unit :: Object/./ObjectTests.exe/ELFObjectFileTest/ReadBBAddrMap

Forcing BBAddrMapVersion to 2 in MCContext.h does not resolve the issue. On the other hand, reverting this patch causes all tests to pass.

Is there a quick fix for the problem? If not, could you revert it please?

Just want to echo @ashay-github comments. This regression in Windows is holding up Torch-MLIR and IREE-Torch and SHARK downstream projects rolling on to the latest LLVM. Can we please revert or quickly fix? Thanks

@rahmanl would it be possible to address the windows failures or revert this commit while someone investigates?

I will start looking at this now. If I can't get a fix by tomorrow, we'll
revert the patch. Thanks.

I confirmed just now that the build failure seems to be a result of MSVC version differences. MSVC v14.29 (from Visual Studio 2019) which is used in the pre-merge checks here causes the tests to pass, but MSVC v14.33 (from Visual Studio 2022) causes test failures, which perhaps means that either the older compiler miscompiled LLVM or that there is a bug in the newer version of the compiler. It still seems worthwhile to revert this patch so that we unblock folks downstream, and in the meantime, find out the source of the bug.

Thanks for the investigation @ashay-github. This seems to be a complex bug, I am setting up a windows machine to be able to debug, but I appreciate your help.

Thanks for looking into this! Let me know if you have trouble reproducing the error.

Thanks for looking into this! Let me know if you have trouble reproducing the error.

@ashay-github I've been having some issues trying to build LLVM on windows. Getting access to Visual Studio 2022 seems to take a while. Would you please reproduce the error on Windows again and send me the verbose llvm-lit diff. Also, if you could please share the intermediate object file(s) for one test (created using yaml2obj) I appreciate it.

@rahmanl I've uploaded the console output and the output of the following commands here: https://file.io/rjyLym3SKpqx. Let me know if you have trouble accessing those files.

> build\bin\yaml2obj.exe --docnum=1 llvm\test\tools\yaml2obj\ELF\bb-addr-map.yaml -o out.obj
> build\bin\obj2yaml.exe out.obj > out.yaml
rahmanl reopened this revision.Jan 13 2023, 3:11 PM

@ashay-github Thank you for providing the intermediate files. Unfortunately, I wasn't able to diagnose the issue. I ran into issues when building LLVM on windows. I wanted to try this patch again, but avoid running the problematic tests on windows.

This revision is now accepted and ready to land.Jan 13 2023, 3:11 PM
rahmanl updated this revision to Diff 489138.Jan 13 2023, 3:12 PM
  • Avoid running failed tests on Windows.

Hi @rahmanl, thanks for the changes. I did check that the updated patch doesn't break Windows builds and tests.

This revision was landed with ongoing or failed builds.Jan 17 2023, 3:25 PM
This revision was automatically updated to reflect the committed changes.

Thanks for verifying @ashay-github .