On Tue, May 13, 2025 at 12:47 AM Andrew Pinski <quic_apin...@quicinc.com> wrote:
>
> With some functions, there might be the case where every stack variable is a
> live at the end of a
> basic block. If that is the case then it is known that all stack variables
> will conflict with each
> other so there is no reason to go through figuring out what variables
> conflict with each other.
> Since we hold the live variables in a bitmap, we can just count the number of
> bits and compare it to
> the number of stack variables. Currently the bitmap is a linked-list of
> 128bits each, on average there
> is going to be less than 128 stack variables in a function so this is not
> adding much overhead to check.
>
> In the case of the testcase from PR 114480 with `-fstack-reuse=none`, this
> reduces `expand var` from 70s
> down to less than 1s.
It looks like a very narrow special case to me where handling it does
come at a cost
in compile-time and also code complexity. Do you have statistics on
wheter it is really
a narrow special-case, like, can you count the number of times this
hits during bootstrap
(for > 1 BB functions) compared to the times it does not hit? Aka
which % of time does
it help?
It might be more useful to have a degraded mode for when we approach O(n*n) we'd
give up on coalescing rather than just handling the very extreme case
of all-all conflicts?
Richard.
> Bootstrapped and tested on x86_64-linux-gnu.
>
> gcc/ChangeLog:
>
> * cfgexpand.cc (add_scope_conflicts): Return true if all variables are
> alive at the end of a basic block.
> (partition_stack_vars): Take a new argument, all_active. Return early
> if
> all_active is true after the qsort.
> (expand_used_vars): Update call to partition_stack_vars.
>
> Signed-off-by: Andrew Pinski <quic_apin...@quicinc.com>
> ---
> gcc/cfgexpand.cc | 46 ++++++++++++++++++++++++++++++++++++----------
> 1 file changed, 36 insertions(+), 10 deletions(-)
>
> diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc
> index 277ef659f30..e84f12a5e93 100644
> --- a/gcc/cfgexpand.cc
> +++ b/gcc/cfgexpand.cc
> @@ -941,21 +941,23 @@ add_scope_conflicts_1 (vars_ssa_cache &cache,
> basic_block bb, bitmap work, bool
> }
>
> /* Generate stack partition conflicts between all partitions that are
> - simultaneously live. */
> + simultaneously live. Returns true if it is known that every stack
> + vars will conflict with each other. */
>
> -static void
> +static bool
> add_scope_conflicts (void)
> {
> /* If there is only one variable, there is nothing to be done as
> there is only possible partition. */
> if (stack_vars_num == 1)
> - return;
> + return true;
>
> basic_block bb;
> bool changed;
> bitmap work = BITMAP_ALLOC (NULL);
> int *rpo;
> int n_bbs;
> + bool all_active = false;
>
> vars_ssa_cache cache;
>
> @@ -987,20 +989,41 @@ add_scope_conflicts (void)
> active = (bitmap)bb->aux;
> add_scope_conflicts_1 (cache, bb, work, false);
> if (bitmap_ior_into (active, work))
> - changed = true;
> + {
> + /* If all of the stack variables
> + are alive at the end at any of the basic blocks,
> + then we know all of them will conflict with each
> + other. */
> + unsigned numactive = bitmap_count_bits (active);
> + if (numactive == stack_vars_num)
> + {
> + all_active = true;
> + changed = false;
> + break;
> + }
> + changed = true;
> + }
> }
> }
>
> - FOR_EACH_BB_FN (bb, cfun)
> - add_scope_conflicts_1 (cache, bb, work, true);
> + if (!all_active)
> + {
> + FOR_EACH_BB_FN (bb, cfun)
> + add_scope_conflicts_1 (cache, bb, work, true);
> + }
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> - cache.dump (dump_file);
> + {
> + cache.dump (dump_file);
> + if (all_active)
> + fprintf (dump_file, "All stack variables conflict.\n");
> + }
>
> free (rpo);
> BITMAP_FREE (work);
> FOR_ALL_BB_FN (bb, cfun)
> BITMAP_FREE (bb->aux);
> + return all_active;
> }
>
> /* A subroutine of partition_stack_vars. A comparison function for qsort,
> @@ -1233,7 +1256,7 @@ union_stack_vars (unsigned a, unsigned b)
> */
>
> static void
> -partition_stack_vars (void)
> +partition_stack_vars (bool all_active)
> {
> unsigned si, sj, n = stack_vars_num;
>
> @@ -1246,6 +1269,9 @@ partition_stack_vars (void)
>
> qsort (stack_vars_sorted, n, sizeof (unsigned), stack_var_cmp);
>
> + if (all_active)
> + return;
> +
> for (si = 0; si < n; ++si)
> {
> unsigned i = stack_vars_sorted[si];
> @@ -2580,7 +2606,7 @@ expand_used_vars (bitmap forced_stack_vars)
> {
> bool has_addressable_vars = false;
>
> - add_scope_conflicts ();
> + bool all_active = add_scope_conflicts ();
>
> /* If stack protection is enabled, we don't share space between
> vulnerable data and non-vulnerable data. */
> @@ -2596,7 +2622,7 @@ expand_used_vars (bitmap forced_stack_vars)
>
> /* Now that we have collected all stack variables, and have computed a
> minimal interference graph, attempt to save some stack space. */
> - partition_stack_vars ();
> + partition_stack_vars (all_active);
> if (dump_file)
> dump_stack_var_partition ();
> }
> --
> 2.43.0
>
