Page MenuHomePhabricator

Use Propeller ID instead of MBB IDs.
Needs ReviewPublic

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



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.


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

  • These IDs are captured and dumped into a specially created section named “bb_addr_map” and is created just before the AsmPrinter pass which writes out object files. This also ensures that we have a mapping that is close to assembly.
  • Annotation works by taking a virtual address of an instruction and looking up the bb_addr_map to find the MBB ID 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 ID 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 MBB IDs do not provide a one-to-one correspondence throughout the lifetime of Machine IR, due to their volatility. Profile annotation using MBB IDs is restricted to be fixed point; only valid at the exact point where it was dumped.
  • Further, the object code can only be dumped before AsmPrinter and cannot be dumped at an arbitrary point in the Machine IR pass pipeline. Hence, MBB IDs are not suitable and we need something else.

We propose using unique incremental Propeller IDs for basic blocks instead of MBB IDs. These IDs are assigned upon the creation of machine basic blocks. We modify MachineFunction::CreateMachineBasicBlock to assign the Propeller ID to every newly created basic block. It assigns MachineFunction::NextPropellerID to the Propeller 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 NextPropellerID variable is scoped to MachineFunction, interleaving of codegen for different functions won't cause any inconistencies.

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

Unit TestsFailed

620 msx64 debian > BOLT.AArch64::r_aarch64_prelxx.s
Script: -- : 'RUN: at line 11'; /usr/bin/clang --target=x86_64-linux -fuse-ld=lld -Wl,--unresolved-symbols=ignore-all --target=aarch64-pc-linux -nostartfiles -nostdlib -ffreestanding -nostartfiles -nostdlib /var/lib/buildkite-agent/builds/llvm-project/bolt/test/AArch64/r_aarch64_prelxx.s -o /var/lib/buildkite-agent/builds/llvm-project/build/tools/bolt/test/AArch64/Output/r_aarch64_prelxx.s.tmp.exe -mlittle-endian -Wl,-q -Wl,-z,max-page-size=4
60 msx64 debian > LLVM-Unit.CodeGen/_/CodeGenTests/10::55
Script(shard): -- GTEST_OUTPUT=json:/var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests-LLVM-Unit-1321390-10-55.json GTEST_SHUFFLE=0 GTEST_TOTAL_SHARDS=55 GTEST_SHARD_INDEX=10 /var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests
100 msx64 debian > LLVM-Unit.CodeGen/_/CodeGenTests/17::55
Script(shard): -- GTEST_OUTPUT=json:/var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests-LLVM-Unit-1321390-17-55.json GTEST_SHUFFLE=0 GTEST_TOTAL_SHARDS=55 GTEST_SHARD_INDEX=17 /var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests
90 msx64 debian > LLVM-Unit.CodeGen/_/CodeGenTests/18::55
Script(shard): -- GTEST_OUTPUT=json:/var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests-LLVM-Unit-1321390-18-55.json GTEST_SHUFFLE=0 GTEST_TOTAL_SHARDS=55 GTEST_SHARD_INDEX=18 /var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests
150 msx64 debian > LLVM-Unit.CodeGen/_/CodeGenTests/2::55
Script(shard): -- GTEST_OUTPUT=json:/var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests-LLVM-Unit-1321390-2-55.json GTEST_SHUFFLE=0 GTEST_TOTAL_SHARDS=55 GTEST_SHARD_INDEX=2 /var/lib/buildkite-agent/builds/llvm-project/build/unittests/CodeGen/./CodeGenTests
View Full Test Results (20 Failed)

Event Timeline

rahmanl created this revision.Apr 19 2021, 7:26 PM
rahmanl updated this revision to Diff 338689.Apr 19 2021, 7:38 PM


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?

Herald added a project: Restricted Project. · View Herald TranscriptAug 4 2022, 11:25 AM