1570584 - Cranelift: extend redundant fill removal to work on tree-shaped regions

Status: RESOLVED FIXED

(Core :: JavaScript: WebAssembly, enhancement, P2)

Description

[Julian Seward [:jseward]]

Bug 1564772 adds a late-stage pass that opportunistically removes redundant
fill instructions. Currently this operates only within individual Ebbs.
However, it is -- conceptually, at least -- simple to extend it to operate on
tree shaped regions of Ebbs, since the transformation is a single forward pass
that carries an environment along, and that environment is still valid at the
start of blocks that are the immediate successors of current one, provided
that they have no other successors. That should increase the number of
detectably redundant fills.

This bug therefore extends 1564772 to do that. As a side effect, the patch
(to come) contains a more-or-less independent part that partitions a CFG into
trees of Ebbs, without recursion and with minimal heap allocation. It might
be useful elsewhere in CL.

Doing this is also important because of ongoing work to remove Ebbs in favour
of classic basic blocks. That will reduce the average size of blocks and so
will reduce the effectiveness of block-level-only redundant-fill removal. The
size of tree shaped regions is expected to be invariant to that
transformation, and hence will avoid any such lossage.

Comment 1

[Julian Seward [:jseward]]

This landed as https://github.com/CraneStation/cranelift/pull/906/
git rev 164f91a1f473e582e18e48d056c51787d9a1c24d