On Wed, 24 May 2023, Richard Sandiford wrote:
> When I wrote early-remat, the DF_FORWARD block order was a postorder
> of a reverse/backward walk (i.e. of the inverted cfg), rather than a
> reverse postorder of a forward walk. A postorder of a backward walk
> lacked the important property that dominators come before the blocks
> they dominate; instead it ensures that postdominators come after
> the blocks that they postdominate.
>
> The DF_BACKWARD block order was similarly a postorder of a forward
> walk. Since early-remat wanted a standard postorder and reverse
> postorder with normal dominator properties, it used the DF_BACKWARD
> order instead of the DF_FORWARD order.
>
> g:53dddbfeb213ac4ec39f fixed the DF orders so that DF_FORWARD was
> an RPO of a forward walk and so that DF_BACKWARD was an RPO of a
> backward walk. This meant that iterating backwards over the
> DF_BACKWARD order had the exact problem that the original DF_FORWARD
> order had, triggering a flurry of ICEs for SVE.
>
> This fixes the build with SVE enabled. It also fixes an ICE
> in g++.target/aarch64/sve/pr99766.C with normal builds. I've
> included the test from the PR as well, for extra coverage.
>
> Tested on aarch64-linux-gnu and aarch64_be-elf. OK to install?
OK.
Thanks,
Richard.
> Richard
>
>
> gcc/
> PR rtl-optimization/109940
> * early-remat.cc (postorder_index): Rename to...
> (rpo_index): ...this.
> (compare_candidates): Sort by decreasing rpo_index rather than
> increasing postorder_index.
> (early_remat::sort_candidates): Calculate the forward RPO from
> DF_FORWARD.
> (early_remat::local_phase): Follow forward RPO using DF_FORWARD,
> rather than DF_BACKWARD in reverse.
>
> gcc/testsuite/
> * gcc.dg/torture/pr109940.c: New test.
> ---
> gcc/early-remat.cc | 28 ++++++++++++-------------
> gcc/testsuite/gcc.dg/torture/pr109940.c | 18 ++++++++++++++++
> 2 files changed, 32 insertions(+), 14 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/torture/pr109940.c
>
> diff --git a/gcc/early-remat.cc b/gcc/early-remat.cc
> index b76771eaf0d..1ee63c73c1b 100644
> --- a/gcc/early-remat.cc
> +++ b/gcc/early-remat.cc
> @@ -1010,8 +1010,8 @@ early_remat::init_block_info (void)
> m_block_info.safe_grow_cleared (n_blocks, true);
> }
>
> -/* Maps basic block indices to their position in the post order. */
> -static unsigned int *postorder_index;
> +/* Maps basic block indices to their position in the forward RPO. */
> +static unsigned int *rpo_index;
>
> /* Order remat_candidates X_IN and Y_IN according to the cfg postorder. */
>
> @@ -1024,7 +1024,7 @@ compare_candidates (const void *x_in, const void *y_in)
> basic_block y_bb = BLOCK_FOR_INSN (y->insn);
> if (x_bb != y_bb)
> /* Make X and Y follow block postorder. */
> - return postorder_index[x_bb->index] - postorder_index[y_bb->index];
> + return rpo_index[y_bb->index] - rpo_index[x_bb->index];
>
> /* Make X and Y follow a backward traversal of the containing block. */
> return DF_INSN_LUID (y->insn) - DF_INSN_LUID (x->insn);
> @@ -1051,15 +1051,15 @@ early_remat::sort_candidates (void)
> /* Create a mapping from block numbers to their position in the
> postorder. */
> unsigned int n_blocks = last_basic_block_for_fn (m_fn);
> - int *postorder = df_get_postorder (DF_BACKWARD);
> - unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
> - postorder_index = new unsigned int[n_blocks];
> - for (unsigned int i = 0; i < postorder_len; ++i)
> - postorder_index[postorder[i]] = i;
> + int *rpo = df_get_postorder (DF_FORWARD);
> + unsigned int rpo_len = df_get_n_blocks (DF_FORWARD);
> + rpo_index = new unsigned int[n_blocks];
> + for (unsigned int i = 0; i < rpo_len; ++i)
> + rpo_index[rpo[i]] = i;
>
> m_candidates.qsort (compare_candidates);
>
> - delete[] postorder_index;
> + delete[] rpo_index;
> }
>
> /* Commit to the current candidate indices and initialize cross-references.
> */
> @@ -2097,11 +2097,11 @@ early_remat::local_phase (void)
> if (dump_file)
> fprintf (dump_file, "\n;; Local phase:\n");
>
> - int *postorder = df_get_postorder (DF_BACKWARD);
> - unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
> - for (unsigned int i = postorder_len; i-- > 0; )
> - if (postorder[i] >= NUM_FIXED_BLOCKS)
> - process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
> + int *rpo = df_get_postorder (DF_FORWARD);
> + unsigned int rpo_len = df_get_n_blocks (DF_FORWARD);
> + for (unsigned int i = 0; i < rpo_len; ++i)
> + if (rpo[i] >= NUM_FIXED_BLOCKS)
> + process_block (BASIC_BLOCK_FOR_FN (m_fn, rpo[i]));
> }
>
> /* Return true if available values survive across edge E. */
> diff --git a/gcc/testsuite/gcc.dg/torture/pr109940.c
> b/gcc/testsuite/gcc.dg/torture/pr109940.c
> new file mode 100644
> index 00000000000..23364708e86
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr109940.c
> @@ -0,0 +1,18 @@
> +/* { dg-additional-options "-march=armv9-a" { target aarch64*-*-* } } */
> +
> +int a;
> +int *b;
> +void
> +c (int *d) { *d = a; }
> +
> +int
> +e(int d, int f) {
> + if (d <= 1)
> + return 1;
> + int g = d / 2;
> + for (int h = 0; h < g; h++)
> + if (f == (long int)b > b[h])
> + c(&b[h]);
> + e(g, f);
> + e(g, f);
> +}
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)
