Hello,
On Thu, 4 Apr 2024, Richard Biener wrote:
> I have reworded the comment before the all-to-all conflict recording
> since it seemed to be confusing and missing the point - but maybe I
> am also missing something here.
The point of the comment was to explain how this differs from building a
conflict graph for named objects without indirect accesses, i.e. how e.g.
a conflict graph for register allocation is done. There conflicts are
added at the points where objects are defined (between that def and all
currently live objects), and _only_ there. I.e. not at CFG merge points
and not at uses. So something like so:
foreach INSN in block backwards:
foreach DEF in INSN:
foreach O in active:
add_conflict (DEF, O);
remove (DEF from active);
That's for the more usual backwards direction, but it would be similar
for forward one. The point is that this is the only place where conflicts
are added, not at CFG splits/merges.
The above relies on being able to see all places where the objects are
written. With indirect accesses that's not the case anymore:
ptr = cond : &foo : &bar; // MENTION foo, bar
*ptr = 42; // no DEF of a named object
escape (ptr);
CLOBBER (foo)
CLOBBER (bar)
We somewhere need to record the conflict between foo and bar.
Conservatively we did so at the first real instruction of a block. As
minor optimization we also start a block in a mode where we just record
mentions, and switch to also recording conflicts at the first real insn.
(An empty block, or just PHIs do not cause conflicts in themself)
This need for an N-to-N conflict generation at some point is the major
difference between building the conflict graph for named vs.
potentionally indirect objects, and the comment tried to explain that
from the perspective of someone familiar with conflict graph building
in regalloc :-)
Where exactly these N-to-N conflicts are generated doesn't matter so much,
as long as everything is there. The current way was the most obvious one.
The observation that these N-to-N conflicts only need to be done on the
commonly disjoint sets of the inputs (which is trivially empty for a
single predecessor) is correct, i.e. only doing it with more than a single
predecessor makes sense. This requires adding the N-to-Ns always even in
mostly emtpy blocks, for the danger of that being missed in the successor
block, as you are doing.
So, fine with me, also with the changed comment if you think it explains
stuff better :)
Ciao,
Michael.
>
> Nevertheless for the testcase in the PR the compile-time spend in
> add_scope_conflicts at -O1 drops from previously 67s (39%) to 10s (9%).
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, OK for trunk?
>
> Thanks,
> Richard.
>
> PR middle-end/114579
> * cfgexpand.cc (add_scope_conflicts_1): Record all-to-all
> conflicts only when there's a CFG merge but for all CFG merges.
> ---
> gcc/cfgexpand.cc | 46 +++++++++++++++++++++++++++++++++-------------
> 1 file changed, 33 insertions(+), 13 deletions(-)
>
> diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc
> index eef565eddb5..fa48a4c633f 100644
> --- a/gcc/cfgexpand.cc
> +++ b/gcc/cfgexpand.cc
> @@ -640,21 +640,26 @@ add_scope_conflicts_1 (basic_block bb, bitmap work,
> bool for_conflict)
> {
> if (for_conflict && visit == visit_op)
> {
> - /* If this is the first real instruction in this BB we need
> - to add conflicts for everything live at this point now.
> - Unlike classical liveness for named objects we can't
> - rely on seeing a def/use of the names we're interested in.
> - There might merely be indirect loads/stores. We'd not add any
> - conflicts for such partitions. */
> + /* When we are inheriting live variables from our predecessors
> + through a CFG merge we might not see an actual mention of
> + the variables to record the approprate conflict as defs/uses
> + might be through indirect stores/loads. For this reason
> + we have to make sure each live variable conflicts with
> + each other. When there's just a single predecessor the
> + set of conflicts is already up-to-date.
> + We perform this delayed at the first real instruction to
> + allow clobbers starting this block to remove variables from
> + the set of live variables. */
> bitmap_iterator bi;
> unsigned i;
> - EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
> - {
> - class stack_var *a = &stack_vars[i];
> - if (!a->conflicts)
> - a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack);
> - bitmap_ior_into (a->conflicts, work);
> - }
> + if (EDGE_COUNT (bb->preds) > 1)
> + EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
> + {
> + class stack_var *a = &stack_vars[i];
> + if (!a->conflicts)
> + a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack);
> + bitmap_ior_into (a->conflicts, work);
> + }
> visit = visit_conflict;
> }
> walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit);
> @@ -662,6 +667,21 @@ add_scope_conflicts_1 (basic_block bb, bitmap work, bool
> for_conflict)
> add_scope_conflicts_2 (USE_FROM_PTR (use_p), work, visit);
> }
> }
> +
> + /* When there was no real instruction but there's a CFG merge we need
> + to add the conflicts now. */
> + if (for_conflict && visit == visit_op && EDGE_COUNT (bb->preds) > 1)
> + {
> + bitmap_iterator bi;
> + unsigned i;
> + EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
> + {
> + class stack_var *a = &stack_vars[i];
> + if (!a->conflicts)
> + a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack);
> + bitmap_ior_into (a->conflicts, work);
> + }
> + }
> }
>
> /* Generate stack partition conflicts between all partitions that are
>
