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

[rahmanl]

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.

[rahmanl]

Refactoring.

[rahmanl]

• Fix tests.

[rahmanl]

• Fix tests.
• Add support for MIR printing and parsing.

[rahmanl]

Rebase.

[rahmanl]

Fix clang-tidy warnings.

[rahmanl]

Add comments/Variable renaming.

[jhenderson]

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

172

llvm/lib/CodeGen/MIRParser/MIParser.cpp

666

[rahmanl]

Rebase.

[rahmanl]

• Change PropellerID to BBID.

[rahmanl]

• clang-format.

[rahmanl]

• clang-format.

[rahmanl]

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

[rahmanl]

• Fix test.

[jhenderson]

llvm/include/llvm/CodeGen/BasicBlockSectionsProfileReader.h

34–35

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

llvm/lib/CodeGen/BasicBlockSections.cpp

189

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.

224–225

[rahmanl]

• Address comments.

[jhenderson]

No more comments from me, thanks.

[rahmanl]

In D100808#3854974, @jhenderson wrote:

No more comments from me, thanks.

I appreciate the review @jhenderson

llvm/lib/CodeGen/BasicBlockSections.cpp

224–225

Changed the comment as it doesn't hold anymore.

[rahmanl]

• report error instead of assertions if entry block is displaced.

[rahmanl]

• report error instead of assertions if entry block is displaced.

[jhenderson]

llvm/lib/CodeGen/BasicBlockSections.cpp

264–267

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]

• Changed check back to assert.
• Changed the emitted BB address map version back to 1.

[rahmanl]

clang-format.

[rahmanl]

clang-format.

[rahmanl]

• clang-format.

[rahmanl]

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

264–267

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]

• Changed the emitted BB address map version back to 1.

[rahmanl]

• Changed the emitted BB address map version back to 1.

[rahmanl]

• Rebase.

[jhenderson]

llvm/lib/CodeGen/BasicBlockSections.cpp

332

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

[rahmanl]

Refactoring and changing data structures.

[tmsriram]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1363

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

189

Please fix this too.

238

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

258

Why did you remove the 4 here?

332

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

350

extra line.

llvm/lib/CodeGen/MachineBasicBlock.cpp

1654

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

llvm/lib/CodeGen/MachineFunction.cpp

443

Please add a comment here on why this is needed.

[rahmanl]

Remove redundant new line.

[rahmanl]

Remove unused include.

[rahmanl]

• Address comments.

[tmsriram]

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

189

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

238

Please fix this too.

[rahmanl]

• Final comments.

[rahmanl]

Thanks Sri.

llvm/lib/CodeGen/BasicBlockSections.cpp

189

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

238

Added a single TODO in MachineBasicBlock.h.

258

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

llvm/lib/CodeGen/MachineBasicBlock.cpp

1654

Added TODO in the header file.

[hokein]

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

[ashay-github]

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?

[powderluv]

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

[stella.stamenova]

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

[rahmanl]

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

[ashay-github]

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.

[rahmanl]

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.

[ashay-github]

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

[rahmanl]

In D100808#3992722, @ashay-github wrote:

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.

[ashay-github]

@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]

@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.

[rahmanl]

• Avoid running failed tests on Windows.

[ashay-github]

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

[rahmanl]

Thanks for verifying @ashay-github .