[RFC] Add auxiliary field for per-pass custom data to BasicBlock

[huangjd]

Background

In many optimization passes we need to compute per-basic block info and propagate it through the CFG, or need a numbering order for each basic block. Currently the common way is to use DenseMap<BasicBlock *, T>, managed by whatever pass that needs to per block data. This is not the most efficient (both speed and memory usage) way, especially when the function contains a large amount of basic blocks. Profiling result shows that for the entire compilation duration, operations involving DenseMap<BasicBlock *, T> can account for up to 12% of the time in total. A search for such usage in the entire LLVM project yields more than a hundred results, indicating its prevalence.

Design

There will be a new generic field added to BasicBlock class. The purpose of this field is to supply any auxiliary per-block info used by a compiler pass, rather than storing data inherently tied to the block itself (such as its attributes). Given this, it is the responsibility of each pass to maintain the validity of the field’s value for the duration of the pass, including any memory cleanup should it allocate data and store the pointer in this field. The field’s value is considered undefined outside of the pass’ run() function as it is not owned by the block. In the case a pass generates sub-passes, it is also responsible to save and restore the auxiliary field if necessary.

The reason that this field is not preserved across passes is that many transformation passes can create new basic blocks, and it would reduce modularity to require a pass to initialize a new basic block’s field where others were created by a previous pass.

Implementation Details and Impact

Assuming a standard Linux 64-bit system, currently the first member (ignoring base class) of BasicBlock is bool IsNewDbgInfoFormat (1-bit info, 1-byte aligned) followed by InstListType InstList (8-byte aligned). This leaves a 63-bit gap to fit any info. It is sufficient for assigning a numbering order to basic blocks with uint32_t, which is currently assumed in many places. It is also sufficient to store a 64-bit pointer to a dynamically allocated object, given the max_align_t alignment requirement, which means that the lowest bit is definitely unset, so it can share sapce with the flag IsNewDbgInfoFormat.

Since adding this field will not change the size of BasicBlock, there will not be any change to memory usage. Existing code that access IsNewDbgInfoFormat would likely to emit the same assembly test %al, $1 in x86-64 (and something similar in other CPU), so there’s no performance impact.

As for comparing the performance between using this auxiliary field and using any map data structure mapping basic block to data, loading a field from the block object itself is obviously much faster than performing a map lookup.

Example Use Cases

In Mem2Reg, basic blocks are assigned an ordering for deterministic behavior. It could be beneficial to have the basic block number stored in the auxiliary field rather than in a DenseMap<BasicBlock*, unsigned>.

[nikic]

This sounds reasonable to me. Note that the IsNewDbgInfoFormat field is temporary and will be removed soon (probably directly after LLVM 19 branches? cc @StephenTozer). But I also don’t thing that slightly increasing BasicBlock size for this is a problem either. Relative to other values, BasicBlocks make up a relative small fraction.

The main danger of having such a shared field is that multiple pieces of code try to use it at the same time. We should document that only passes should use this field, not analyses. As only one pass can operate on the function at the same time, this should be safe. (Note that this excludes using the field for DT, which is one of the hottest users of BB mappings. And indeed, we may have multiple DTs for one function at the same time.)

cc @aengelke who was going to propose adding a similar field to Instructions.

[StephenTozer]

That’s correct, although we don’t have a specific time in mind, IsNewDbgInfoFormat should hopefully be disappearing soon.

[aengelke]

@nikic

The main danger of having such a shared field is that multiple pieces of code try to use it at the same time.

This was also the main reason I didn’t yet move forward proposing an aux field for instructions – it’s downsides:

• It adds some implicit state that is likely to cause problems. While we could establish a rule that these fields are only usable by passes, helpers and analysis (InlineFunction, PromoteMemToReg, DomTree, etc.) would also substantially benefit – but giving each of them a “MayTrashAuxData” parameter isn’t a good solution in my opinion.
• Required initialization: unless “contains” queries are not required, each pass must iterate over all blocks and reset the aux field. (Likewise for instructions, if they had one.)
• Not possible to store two things at the same time.

I think a numbering approach get’s us most of the performance gains (but not all) at a much lower complexity: We assign a per-function-unique number to each block (insertion of a block just fetches next highest value from function and adds 1; we could renumber at some points, e.g. SimplifyCFG or other passes that remove a lot of blocks). So for a function with 4 blocks, these numbers could be 0,1,4,5 (after renumbering, of course, they’d be 0-3). Then these maps/sets can be replaced by a vector (conceptually, all blocks could also be referred to by their number). Initialization would also be faster (for large functions, malloc+memset is likely faster than linked list traversal). This would also nicely simplify DTs, because MachineBasicBlocks already have such a number.

Edit: we could also do the same with instructions, which already have a number (“Order”) field, which could be somewhat easily expanded to be a per-function-unique number.

[davidxl]

The aux field can be limited to hold temporary mapped data per-pass. Index can be used for more general purpose mapping, but it can get complicated as well - for instance holes will be created overtime without garbage collection and renumbering can mess up existing mapping data etc.

For reference, GCC’s basic block structure has both aux and index field. The aux field is used per-pass.

[huangjd]

I think just adding an numbering field for now could be beneficial to most of the passes. If a pass needs larger auxiliary data it can be placed into an array owned by the pass itself and accessed by the block’s number. This adds one more load but is still faster than a map lookup.

[vporpo]

@nikic

The main danger of having such a shared field is that multiple pieces of code try to use it at the same time.

To help mitigate the sharing issue we could use a locking scheme that will only allow you to access the field if you own the lock, and would crash if someone else tries to acquire a lock at the same time. We could use one of the bits for marking the BB as “locked”. The lock object could clear the bit once it goes out of scope.

[huangjd]

To help mitigate the sharing issue we could use a locking scheme that will only allow you to access the field if you own the lock, and would crash if someone else tries to acquire a lock at the same time. We could use one of the bits for marking the BB as “locked”. The lock object could clear the bit once it goes out of scope.

Using an atomic byte incurs a non-trivial cost, in this case it’s probably better to let each pass have it’s own BB to auxiliary data map.

However this won’t be an issue if the blocks are numbered, since concurrent passes are not modifying the CFG, they can use the block number as index into auxiliary data array independently managed by each pass.

[vporpo]

@huangjd

Using an atomic byte incurs a non-trivial cost, in this case it’s probably better to let each pass have it’s own BB to auxiliary data map.

I was thinking of a very lightweight API for accessing the field like: BB.set(<some field value>, Lock) that requires a lock-like object as an argument that you can only get through an API like: Lock = F.acquireBBFieldLock(). Trying to acquire the lock while some other piece of code has already acquired it would cause a crash, which would warn you that someone else is already using the field.

[nikic]

@aengelke

It adds some implicit state that is likely to cause problems. While we could establish a rule that these fields are only usable by passes, helpers and analysis (InlineFunction, PromoteMemToReg, DomTree, etc.) would also substantially benefit – but giving each of them a “MayTrashAuxData” parameter isn’t a good solution in my opinion.

I think @vporpo made a pretty good suggestion on how to make sure there are no clashes.

@aengelke

Required initialization: unless “contains” queries are not required, each pass must iterate over all blocks and reset the aux field. (Likewise for instructions, if they had one.)

We should initialize the aux value to a known sentinel (-1) and then require that passes restore to that value once they are done (@vporpo’s lock object could assert that in debug builds).

I think that for many key use cases, this will happen automatically, without the need for explicit initialization (or de-initialization). For example, consider Instruction worklist management in InstCombine. The aux value would store the index in the worklist, with the sentinel indicating its not in the worklist. At the end of the transform, the worklist is always empty, so all the aux values are back at the sentinel value. This is both very efficient. (For InstCombine in particular we’d probably want to also use negative numbers to represent the deferred worklist.)

If we only have an instruction numbering, then we’d need an extra indirection from instruction numbers to worklist numbers. We’d replace the existing DenseMap on pointers with a vector, which is of course a win, but it’s not as good as directly using worklist indices.

---

Another thing worth noting is that even if you limit yourself to providing an arbitrary numbering, use inside analysis passes would still be somewhat iffy. In particular, it is necessary to perform occasional renumberings to prevent the index space from becoming too sparse. Such a renumbering also has to update any analysis that makes use of the numbers. I guess you could have some kind of registration mechanism for this. Or know all analyses that use them.

[t0b1_fox]

@nikic

If we only have an instruction numbering, then we’d need an extra indirection from instruction numbers to worklist numbers. We’d replace the existing DenseMap on pointers with a vector, which is of course a win, but it’s not as good as directly using worklist indices.

However, if most (or a substantial part) of the performance penalty of DenseMap<BasicBlock *, T> comes from its use in analyses, then having a numbering that everything can use might be more beneficial overall even if there is a penalty for access (which probably? is going to be relatively low) and renumbering.

@huangjd do you have more fine-grained profiling data that could shed light on this?

[rOptimizer]

@aengelke

I think a numbering approach get’s us most of the performance gains (but not all) at a much lower complexity: We assign a per-function-unique number to each block (insertion of a block just fetches next highest value from function and adds 1

For MachineBasicBlock we have that already: MBB.getNumber()

[aengelke]

@nikic

I think that for many key use cases, this will happen automatically, without the need for explicit initialization (or de-initialization).

I’m not so sure about this. For example, storing the register during ISel, the value number in GVN, etc. – these either need initialization or de-initialization. I haven’t made a thorough study of all instruction/block maps, but I think worklists are more of the exception than the rule (although a pretty heavy exception). That said, I also don’t like the approach of fixed sentinels – this way, one pass might need to reset the field while the next pass doesn’t require it to be initialized.

@nikic

If we only have an instruction numbering, then we’d need an extra indirection from instruction numbers to worklist numbers.

We probably want both: a number and aux data. Two 32-bit fields nicely fit and don’t increase the size once the new-debug-info fields are gone.

@nikic

In particular, it is necessary to perform occasional renumberings to prevent the index space from becoming too sparse. Such a renumbering also has to update any analysis that makes use of the numbers.

For basic blocks: the only cases where a renumbering is beneficial is after substantial block removal, which very likely invalidates all other analyses anyway (e.g., SimplifyCFG). I.e., make renumber() a thing that passes can call, but if they do, they must return PreservedAnalyses::none().

For instructions: this is more difficult, many passes remove instructions. But many analyses wouldn’t benefit from instruction numbers (maybe MemorySSA? others like DemandedBits aren’t preserved), this is primarily relevant for passes. So I don’t actually see a problem there by saying that analyses can’t rely on numbers/aux data, and that non-pass helpers can use the numbering, but not modify aux data. We could lift this restriction if a particular need/benefit becomes emergent.

tl;dr: Add aux data and number. Analyses can rely on block numbers only. Helpers can rely on block/instruction numbers. Passes can additionally modify aux data; if they renumber blocks, they must invalidate all analyses; they can renumber instructions at any time.

@rOptimizer

For MachineBasicBlock we have that already: MBB.getNumber()

Yes, I know. I wanted to update GenericDomTree to use that, but it wasn’t that important anymore once I removed the MachineDominatorTree from the x86 -O0 pipeline entirely.

[huangjd]

Here is a flame graph of backend compilation a non-trivial source code (typically coming from a parser project), DenseMap operations takes 12% of time (total is 564s, so that is 68s). Note that most of the DenseMap usage on SampleProfLoader itself comes from map operations on dominator tree, not reading the sample profile, which only takes 0.2% time (~1s, see below). I assume having assigned number to blocks could also speed up DT computations.

[aengelke]

I started porting the DominatorTree to use block numbers (branch, c-t-t). Results look promising, even though there’s an extra dom tree construction and no IR block renumbering for dense vector usage right now.

Current state:

• BasicBlock got a number that is unique inside the function, but renumbering is not implemented yet. The number is only valid if the block resides inside a function.
• If GraphTraits<NodeT *> supports getNumber(), DomTreeBase will use this, otherwise it will create a ptr-to-number mapping. I implemented this for BasicBlock and MachineBasicBlock.
• When removing a block, it must be removed from the dominator tree before removing it from the function, so that getNumber() can be used to find the dom tree node. I had to change some code to delay removing blocks, I believe this is the cause of two EarlyIfCvt-related test failures.
• Not preserved analyses cause an extra dom tree construction in the back-end. Renumbering definitely needs a way to also update the dom tree.
• Three WebAssembly tests still fail for a non-obvious reason I wasn’t able to track down so far.

This was more difficult than I expected and there were some hard-to-track-down issues (e.g., dominates() is sometimes called with blocks of different functions, which now obviously can have shared numbers; ScalarEvolution::verify() queries the dom tree of deleted nodes – not fixed yet; and sometimes it’s just stupidity on my side e.g. by forgetting to adjust the move constructor, causing a random test failure that looked completely unrelated).

My plan forward:

• Fix EarlyIfCvt + WebAssembly tests
• Implement renumbering of IR block numbers (and split addition of IR block numbers out into a separate PR)
• Adjust Machine IR’s RenumberBlocks to update a MDT/MPDT so that we can preserve dom trees acress renumberings
• Add more unit tests, I found the tests to be not very thorough
• Clean up code and make PRs. I kept many changes as separate commits so that NFC refactorings can go in separately, also allows for easier revert if something breaks (very likely…)

Comments?

[nikic]

Sounds great Feel free to add me to any reviews.

@aengelke

dominates() is sometimes called with blocks of different functions

I don’t think this is intentionally supported. Can we add an assertion against this in IR/Dominators? (Presumably we can’t do it in GenericDomTree because we don’t have a getParent GraphTrait.)

[aengelke]

An update: some preparatory work has landed and my initial implementation is “pre-review done”. The following parts have not yet landed:

• [Support] Assert that DomTree nodes share parent by aengelke · Pull Request #101198 · llvm/llvm-project · GitHub – this last preparation is currently blocked by Polly.
• [Support] Store dominator tree nodes in a vector · llvm/llvm-project@d521774 · GitHub stores DomTreeNodes in a vector, enhances GraphTraits with additional, optional methods to get numbers, maximum number, and number epoch, and adds support for LLVM-IR.
• [CodeGen] Use optimized domtree for MachineFunction · llvm/llvm-project@0cd3deb · GitHub adds support for Machine IR. A few changes in the passes are required.
• https://github.com/llvm/llvm-project/commit/f76d11fa9ed7597dfbb2fdf0afd64a263c749a88 changes SemiNCA (domtree construction) to use a vector instead of a map when numbers are available. (I think there’s more optimization potential here, but the code is also quite complex.)

In total, these changes improve O3 compile times by ~1%.

Should I already open PRs for the other three patches to get reviews? If so, how? I have no experience with Graphite, spr, etc. and there’s no documentation in the contributor guide.

There’s also the not-yet-addressed point of when to renumber blocks. Right now, only MIR does renumbering. We still need to determine which passes tend to remove many blocks and see if renumbering helps performance/memory usage.

[nikic]

While waiting on polly, maybe put up a PR for the DT numbering support without actually implementing the getNumber() trait anywhere (apart from unit tests)? That should also give us an idea of what the overhead of going through the fallback is (which will still be used by mlir, clang, and bolt, so it can’t be too high, or we might need a different implementation approach).

[clattner]

I’m a bit behind on these threads, but it seems like folks are talking about adding an # for both the instruction list and the block list. If you’re interested in this, I’d suggest taking a look at the MLIR features exist here for inspiration. Check out mlir::Operation::isBeforeInBlock for example, which manipulates the operation order and check out where the numberings get invalidated.

I’d suggest biasing /against/ completely dense numbering - such information (particularly in an instruction list) can be invalidated too easily. Leaving some padding between objects can lead to simple insertions not having to do an O(n) recalculation.

-Chris

[clattner]

Separate from ID numbers, I’d also be careful about adding an “aux” field . Such a thing is appealing (and yes, precedented in GCC and other compilers) but can greatly impact composability of analysis and transformations, and it is too easy/appealing to leave state in these “aux” fields that lives across passes. One of the great benefits of the LLVM design is that passes are independent, and hacks creep in quickly when you make it too easy to implicitly maintain state across passes.

I understand that we want to improve densemap overhead, but instead of putting an “aux” field in, I’d suggest putting something simple and defined (e.g. object numbering) which can then be used to index into on-the-side arrays that are maintained by the passes. That way you get rid of the densemaps, but you have something principled that can live across passes and be updated by the core IR in a stable way.

-Chris