Skip to content

JIT: use reverse post-order (RPO) traversal for morph #93246

@AndyAyersMS

Description

@AndyAyersMS

Morph, like many JIT phases, visits all the blocks in a method by following the bbNext chain. There's a missed opportunity here to cheaply propagate some information from block to block.

For "forward" phases like morph it is often preferable to visit the blocks in reverse post-order (RPO). An RPO ensures that for most blocks all the predecessors of the block have been visited before the block itself.

Currently value numbering implements an RPO visit. It's also possible to create an RPO using fgDfsReversePostorder.

The initial goal of this work is to modify morph to rely on RPO, and then to enable a simple form of global assertion prop for Morph (aka "cross-block local assertion prop") that can push facts forward across block boundaries. #86822 has a prototype implementation. The main remaining challenges there are to make the RPO efficient and to properly handle cases where control flow is altered.

There will be extra TP cost from the RPO and from the assertion changes; the hope is that these are paid back by improved optimizations and that this entire change can be zero-cost.

Note for "backwards" phases post-order provides similar benefits (all successors likely visited before a block is visited).

cc @dotnet/jit-contrib

Metadata

Metadata

Assignees

Labels

User StoryA single user-facing feature. Can be grouped under an epic.area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI

Type

No type

Projects

Status

Done

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions