Integrated: 8279886: C1: Turn off SelectivePhiFunctions in presence of irreducible loops

[Igor Veresov]

On Mon, 28 Feb 2022 20:46:26 GMT, Igor Veresov <iveresov at openjdk.org> wrote:

> This change add irreducible loops detection to `BlockListBuilder::mark_loops()` - a loop marking routine necessary for the SSA conversion. Here is brief description of the algorithm (copy-pasted from the comments I left in the code).
> 
> The loop detection algorithm works as follows:
> 
> - We maintain the `_loop_map`, where for each block we have a bitmap indicating which loops contain this block.
> - The CFG is recursively traversed (depth-first) and if we detect a loop, we assign the loop a unique number that is stored in the bitmap associated with the loop header block. Until we return back through that loop header the bitmap contains only a single bit corresponding to the loop number.
> - The bit is then propagated for all the blocks in the loop after we exit them (post-order). There could be multiple bits of course in case of nested loops.
> - When we exit the loop header we remove that single bit and assign the real loop state for it.
> - Now, the tricky part here is how we detect irriducible loops. In the algorithm above the loop state bits are propagated to the predecessors. If we encounter an irreducible loop (a loop with multiple heads) we would see a node with some loop bit set that would then propagate back and be never cleared because we would never go back through the original loop header. Therefore if there are any irreducible loops the bits in the states for these loops are going to propagate back to the root.
> 
> Testing is clean: hs-tier{1-7}

This pull request has now been integrated.

Changeset: b629782b
Author:    Igor Veresov <iveresov at openjdk.org>
URL:       https://git.openjdk.java.net/jdk/commit/b629782b8d44e8aa8a99c6a3381663a6169aa1ad
Stats:     63 lines in 5 files changed: 27 ins; 7 del; 29 mod

8279886: C1: Turn off SelectivePhiFunctions in presence of irreducible loops

Reviewed-by: kvn, dlong

-------------

PR: https://git.openjdk.java.net/jdk/pull/7636