Hi,
I am trying to work on PR80155, which exposes a problem with code
hoisting and register pressure on a leading embedded benchmark for ARM
cortex-m7, where code-hoisting causes an extra register spill.

I have attached two test-cases which (hopefully) are representative of
the original test-case.
The first one (trans_dfa.c) is bigger and somewhat similar to the
original test-case and trans_dfa_2.c is hand-reduced version of
trans_dfa.c. There's 2 spills caused with trans_dfa.c
and one spill with trans_dfa_2.c due to lesser amount of cases.
The test-cases in the PR are probably not relevant.

Initially I thought the spill was happening because of "too many
hoistings" taking place in original test-case thus increasing the
register pressure, but it seems the spill is possibly caused because
expression gets hoisted out of a block that is on loop exit.

For example, the following hoistings take place with trans_dfa_2.c:

(1) Inserting expression in block 4 for code hoisting:
{mem_ref<0B>,tab_20(D)}@.MEM_45 (0005)

(2) Inserting expression in block 4 for code hoisting: {plus_expr,_4,1} (0006)

(3) Inserting expression in block 4 for code hoisting:
{pointer_plus_expr,s_33,1} (0023)

(4) Inserting expression in block 3 for code hoisting:
{pointer_plus_expr,s_33,1} (0023)

The issue seems to be hoisting of (*tab + 1) which consists of first
two hoistings in block 4
from blocks 5 and 9, which causes the extra spill. I verified that by
disabling hoisting into block 4,
which resulted in no extra spills.

I wonder if that's because the expression (*tab + 1) is getting
hoisted from blocks 5 and 9,
which are on loop exit ? So the expression that was previously
computed in a block on loop exit, gets hoisted outside that block
which possibly makes the allocator more defensive ? Similarly
disabling hoisting of expressions which appeared in blocks on loop
exit in original test-case prevented the extra spill. The other
hoistings didn't seem to matter.

If that's the case, would it make sense to add another constraint to
hoisting to not hoist expression if it appears in a block that is on
loop exit (exception is if block has only single successor), at-least
for targets like cortex-m7 where the effect of spill is more
pronounced ?

I tried to write an untested prototype patch (approach-8.diff) on
these lines, to refuse hoisting if an expression appears in block on
loop exit. The patch adds a new map pre_expr_block_d, that maps
pre_expr to the set of blocks (as a bitmap) it appears in and are on
loop exit, which is computed during compute_avail.
During do_hoist_insertion, it simply checks if the bitmap of blocks is
not empty.
It works for the attached test-cases and passes ssa-pre-*.c and
ssa-hoist-*.c tests.

Alternatively, we could restrict replacing expression by it's leader
in eliminate_dom_walker::before_dom_children if the expression appears
in a block on loop exit.
In principle this is more general than hoisting, but I have restricted
it to only hoisted expressions to avoid being overly conservative.
Similarly, this constrained could be made conditional, only for
targets like cortex-m7. I have attached a prototype patch based on
this approach (approach-9.diff). Although it works for attached
test-cases, unfortunately it ICE's with the original test-case in
tail-merge, I am working on that.

I am not sure though if either of these approaches are in the correct
direction and would
be grateful for suggestions on the issue!

Thanks,
Prathamesh