| Message ID | 20231122111415.815147-4-maxim.kuvyrkov@linaro.org |
|---|---|
| State | New |
| Headers | show |
| Series | Avoid exponential behavior in scheduler and better logging | expand |
Dear RTL maintainers, Gently ping. This patch adds a couple of new functions to lists.cc, which then are used to simplify logic in the scheduler. OK to merge? On Wed, 22 Nov 2023 at 15:14, Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org> wrote: > This patch simplifies logic behind deps_join(), which will be > important for the upcoming improvements of sched-deps.cc logging. > > The only functional change is that when deps_join() is called with > empty state for the 2nd argument, it will not reverse INSN_ and > EXPR_LISTs in the 1st argument. Before this patch the lists were > reversed due to use of concat_*_LIST(). Now, with copy_*_LIST() > used for this case, the lists will remain in the original order. > > gcc/ChangeLog: > > * lists.cc (copy_EXPR_LIST, concat_EXPR_LIST): New functions. > * rtl.h (copy_EXPR_LIST, concat_EXPR_LIST): Declare. > * sched-rgn.cc (concat_insn_list, concat_expr_list): New helpers. > (concat_insn_mem_list): Simplify. > (deps_join): Update > --- > gcc/lists.cc | 30 +++++++++++++++++++++++++++- > gcc/rtl.h | 4 +++- > gcc/sched-rgn.cc | 51 +++++++++++++++++++++++++++--------------------- > 3 files changed, 61 insertions(+), 24 deletions(-) > > diff --git a/gcc/lists.cc b/gcc/lists.cc > index 2cdf37ad533..83e7bf32176 100644 > --- a/gcc/lists.cc > +++ b/gcc/lists.cc > @@ -160,6 +160,24 @@ free_INSN_LIST_list (rtx_insn_list **listp) > free_list ((rtx *)listp, &unused_insn_list); > } > > +/* Make a copy of the EXPR_LIST list LINK and return it. */ > +rtx_expr_list * > +copy_EXPR_LIST (rtx_expr_list *link) > +{ > + rtx_expr_list *new_queue; > + rtx_expr_list **pqueue = &new_queue; > + > + for (; link; link = link->next ()) > + { > + rtx x = link->element (); > + rtx_expr_list *newlink = alloc_EXPR_LIST (REG_NOTE_KIND (link), x, > NULL); > + *pqueue = newlink; > + pqueue = (rtx_expr_list **)&XEXP (newlink, 1); > + } > + *pqueue = NULL; > + return new_queue; > +} > + > /* Make a copy of the INSN_LIST list LINK and return it. */ > rtx_insn_list * > copy_INSN_LIST (rtx_insn_list *link) > @@ -178,12 +196,22 @@ copy_INSN_LIST (rtx_insn_list *link) > return new_queue; > } > > +/* Duplicate the EXPR_LIST elements of COPY and prepend them to OLD. */ > +rtx_expr_list * > +concat_EXPR_LIST (rtx_expr_list *copy, rtx_expr_list *old) > +{ > + rtx_expr_list *new_rtx = old; > + for (; copy; copy = copy->next ()) > + new_rtx = alloc_EXPR_LIST (REG_NOTE_KIND (copy), copy->element (), > new_rtx); > + return new_rtx; > +} > + > /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */ > rtx_insn_list * > concat_INSN_LIST (rtx_insn_list *copy, rtx_insn_list *old) > { > rtx_insn_list *new_rtx = old; > - for (; copy ; copy = copy->next ()) > + for (; copy; copy = copy->next ()) > { > new_rtx = alloc_INSN_LIST (copy->insn (), new_rtx); > PUT_REG_NOTE_KIND (new_rtx, REG_NOTE_KIND (copy)); > diff --git a/gcc/rtl.h b/gcc/rtl.h > index e4b6cc0dbb5..7e952d7cbeb 100644 > --- a/gcc/rtl.h > +++ b/gcc/rtl.h > @@ -3764,10 +3764,12 @@ extern void free_EXPR_LIST_list (rtx_expr_list **); > extern void free_INSN_LIST_list (rtx_insn_list **); > extern void free_EXPR_LIST_node (rtx); > extern void free_INSN_LIST_node (rtx); > +extern rtx_expr_list *alloc_EXPR_LIST (int, rtx, rtx); > extern rtx_insn_list *alloc_INSN_LIST (rtx, rtx); > +extern rtx_expr_list *copy_EXPR_LIST (rtx_expr_list *); > extern rtx_insn_list *copy_INSN_LIST (rtx_insn_list *); > +extern rtx_expr_list *concat_EXPR_LIST (rtx_expr_list *, rtx_expr_list *); > extern rtx_insn_list *concat_INSN_LIST (rtx_insn_list *, rtx_insn_list *); > -extern rtx_expr_list *alloc_EXPR_LIST (int, rtx, rtx); > extern void remove_free_INSN_LIST_elem (rtx_insn *, rtx_insn_list **); > extern rtx remove_list_elem (rtx, rtx *); > extern rtx_insn *remove_free_INSN_LIST_node (rtx_insn_list **); > diff --git a/gcc/sched-rgn.cc b/gcc/sched-rgn.cc > index e5964f54ead..da3ec0458ff 100644 > --- a/gcc/sched-rgn.cc > +++ b/gcc/sched-rgn.cc > @@ -2585,25 +2585,32 @@ add_branch_dependences (rtx_insn *head, rtx_insn > *tail) > > static class deps_desc *bb_deps; > > +/* Return a new insn_list with all the elements from the two input > lists. */ > +static rtx_insn_list * > +concat_insn_list (rtx_insn_list *copy, rtx_insn_list *old) > +{ > + if (!old) > + return copy_INSN_LIST (copy); > + return concat_INSN_LIST (copy, old); > +} > + > +/* Return a new expr_list with all the elements from the two input > lists. */ > +static rtx_expr_list * > +concat_expr_list (rtx_expr_list *copy, rtx_expr_list *old) > +{ > + if (!old) > + return copy_EXPR_LIST (copy); > + return concat_EXPR_LIST (copy, old); > +} > + > static void > concat_insn_mem_list (rtx_insn_list *copy_insns, > rtx_expr_list *copy_mems, > rtx_insn_list **old_insns_p, > rtx_expr_list **old_mems_p) > { > - rtx_insn_list *new_insns = *old_insns_p; > - rtx_expr_list *new_mems = *old_mems_p; > - > - while (copy_insns) > - { > - new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns); > - new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), > new_mems); > - copy_insns = copy_insns->next (); > - copy_mems = copy_mems->next (); > - } > - > - *old_insns_p = new_insns; > - *old_mems_p = new_mems; > + *old_insns_p = concat_insn_list (copy_insns, *old_insns_p); > + *old_mems_p = concat_expr_list (copy_mems, *old_mems_p); > } > > /* Join PRED_DEPS to the SUCC_DEPS. */ > @@ -2619,11 +2626,11 @@ deps_join (class deps_desc *succ_deps, class > deps_desc *pred_deps) > struct deps_reg *pred_rl = &pred_deps->reg_last[reg]; > struct deps_reg *succ_rl = &succ_deps->reg_last[reg]; > > - succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses); > - succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets); > + succ_rl->uses = concat_insn_list (pred_rl->uses, succ_rl->uses); > + succ_rl->sets = concat_insn_list (pred_rl->sets, succ_rl->sets); > succ_rl->implicit_sets > - = concat_INSN_LIST (pred_rl->implicit_sets, > succ_rl->implicit_sets); > - succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers, > + = concat_insn_list (pred_rl->implicit_sets, > succ_rl->implicit_sets); > + succ_rl->clobbers = concat_insn_list (pred_rl->clobbers, > succ_rl->clobbers); > succ_rl->uses_length += pred_rl->uses_length; > succ_rl->clobbers_length += pred_rl->clobbers_length; > @@ -2641,10 +2648,10 @@ deps_join (class deps_desc *succ_deps, class > deps_desc *pred_deps) > &succ_deps->pending_write_mems); > > succ_deps->pending_jump_insns > - = concat_INSN_LIST (pred_deps->pending_jump_insns, > + = concat_insn_list (pred_deps->pending_jump_insns, > succ_deps->pending_jump_insns); > succ_deps->last_pending_memory_flush > - = concat_INSN_LIST (pred_deps->last_pending_memory_flush, > + = concat_insn_list (pred_deps->last_pending_memory_flush, > succ_deps->last_pending_memory_flush); > > succ_deps->pending_read_list_length += > pred_deps->pending_read_list_length; > @@ -2653,17 +2660,17 @@ deps_join (class deps_desc *succ_deps, class > deps_desc *pred_deps) > > /* last_function_call is inherited by successor. */ > succ_deps->last_function_call > - = concat_INSN_LIST (pred_deps->last_function_call, > + = concat_insn_list (pred_deps->last_function_call, > succ_deps->last_function_call); > > /* last_function_call_may_noreturn is inherited by successor. */ > succ_deps->last_function_call_may_noreturn > - = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn, > + = concat_insn_list (pred_deps->last_function_call_may_noreturn, > succ_deps->last_function_call_may_noreturn); > > /* sched_before_next_call is inherited by successor. */ > succ_deps->sched_before_next_call > - = concat_INSN_LIST (pred_deps->sched_before_next_call, > + = concat_insn_list (pred_deps->sched_before_next_call, > succ_deps->sched_before_next_call); > } > > -- > 2.34.1 > >
diff --git a/gcc/lists.cc b/gcc/lists.cc index 2cdf37ad533..83e7bf32176 100644 --- a/gcc/lists.cc +++ b/gcc/lists.cc @@ -160,6 +160,24 @@ free_INSN_LIST_list (rtx_insn_list **listp) free_list ((rtx *)listp, &unused_insn_list); } +/* Make a copy of the EXPR_LIST list LINK and return it. */ +rtx_expr_list * +copy_EXPR_LIST (rtx_expr_list *link) +{ + rtx_expr_list *new_queue; + rtx_expr_list **pqueue = &new_queue; + + for (; link; link = link->next ()) + { + rtx x = link->element (); + rtx_expr_list *newlink = alloc_EXPR_LIST (REG_NOTE_KIND (link), x, NULL); + *pqueue = newlink; + pqueue = (rtx_expr_list **)&XEXP (newlink, 1); + } + *pqueue = NULL; + return new_queue; +} + /* Make a copy of the INSN_LIST list LINK and return it. */ rtx_insn_list * copy_INSN_LIST (rtx_insn_list *link) @@ -178,12 +196,22 @@ copy_INSN_LIST (rtx_insn_list *link) return new_queue; } +/* Duplicate the EXPR_LIST elements of COPY and prepend them to OLD. */ +rtx_expr_list * +concat_EXPR_LIST (rtx_expr_list *copy, rtx_expr_list *old) +{ + rtx_expr_list *new_rtx = old; + for (; copy; copy = copy->next ()) + new_rtx = alloc_EXPR_LIST (REG_NOTE_KIND (copy), copy->element (), new_rtx); + return new_rtx; +} + /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */ rtx_insn_list * concat_INSN_LIST (rtx_insn_list *copy, rtx_insn_list *old) { rtx_insn_list *new_rtx = old; - for (; copy ; copy = copy->next ()) + for (; copy; copy = copy->next ()) { new_rtx = alloc_INSN_LIST (copy->insn (), new_rtx); PUT_REG_NOTE_KIND (new_rtx, REG_NOTE_KIND (copy)); diff --git a/gcc/rtl.h b/gcc/rtl.h index e4b6cc0dbb5..7e952d7cbeb 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -3764,10 +3764,12 @@ extern void free_EXPR_LIST_list (rtx_expr_list **); extern void free_INSN_LIST_list (rtx_insn_list **); extern void free_EXPR_LIST_node (rtx); extern void free_INSN_LIST_node (rtx); +extern rtx_expr_list *alloc_EXPR_LIST (int, rtx, rtx); extern rtx_insn_list *alloc_INSN_LIST (rtx, rtx); +extern rtx_expr_list *copy_EXPR_LIST (rtx_expr_list *); extern rtx_insn_list *copy_INSN_LIST (rtx_insn_list *); +extern rtx_expr_list *concat_EXPR_LIST (rtx_expr_list *, rtx_expr_list *); extern rtx_insn_list *concat_INSN_LIST (rtx_insn_list *, rtx_insn_list *); -extern rtx_expr_list *alloc_EXPR_LIST (int, rtx, rtx); extern void remove_free_INSN_LIST_elem (rtx_insn *, rtx_insn_list **); extern rtx remove_list_elem (rtx, rtx *); extern rtx_insn *remove_free_INSN_LIST_node (rtx_insn_list **); diff --git a/gcc/sched-rgn.cc b/gcc/sched-rgn.cc index e5964f54ead..da3ec0458ff 100644 --- a/gcc/sched-rgn.cc +++ b/gcc/sched-rgn.cc @@ -2585,25 +2585,32 @@ add_branch_dependences (rtx_insn *head, rtx_insn *tail) static class deps_desc *bb_deps; +/* Return a new insn_list with all the elements from the two input lists. */ +static rtx_insn_list * +concat_insn_list (rtx_insn_list *copy, rtx_insn_list *old) +{ + if (!old) + return copy_INSN_LIST (copy); + return concat_INSN_LIST (copy, old); +} + +/* Return a new expr_list with all the elements from the two input lists. */ +static rtx_expr_list * +concat_expr_list (rtx_expr_list *copy, rtx_expr_list *old) +{ + if (!old) + return copy_EXPR_LIST (copy); + return concat_EXPR_LIST (copy, old); +} + static void concat_insn_mem_list (rtx_insn_list *copy_insns, rtx_expr_list *copy_mems, rtx_insn_list **old_insns_p, rtx_expr_list **old_mems_p) { - rtx_insn_list *new_insns = *old_insns_p; - rtx_expr_list *new_mems = *old_mems_p; - - while (copy_insns) - { - new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns); - new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems); - copy_insns = copy_insns->next (); - copy_mems = copy_mems->next (); - } - - *old_insns_p = new_insns; - *old_mems_p = new_mems; + *old_insns_p = concat_insn_list (copy_insns, *old_insns_p); + *old_mems_p = concat_expr_list (copy_mems, *old_mems_p); } /* Join PRED_DEPS to the SUCC_DEPS. */ @@ -2619,11 +2626,11 @@ deps_join (class deps_desc *succ_deps, class deps_desc *pred_deps) struct deps_reg *pred_rl = &pred_deps->reg_last[reg]; struct deps_reg *succ_rl = &succ_deps->reg_last[reg]; - succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses); - succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets); + succ_rl->uses = concat_insn_list (pred_rl->uses, succ_rl->uses); + succ_rl->sets = concat_insn_list (pred_rl->sets, succ_rl->sets); succ_rl->implicit_sets - = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets); - succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers, + = concat_insn_list (pred_rl->implicit_sets, succ_rl->implicit_sets); + succ_rl->clobbers = concat_insn_list (pred_rl->clobbers, succ_rl->clobbers); succ_rl->uses_length += pred_rl->uses_length; succ_rl->clobbers_length += pred_rl->clobbers_length; @@ -2641,10 +2648,10 @@ deps_join (class deps_desc *succ_deps, class deps_desc *pred_deps) &succ_deps->pending_write_mems); succ_deps->pending_jump_insns - = concat_INSN_LIST (pred_deps->pending_jump_insns, + = concat_insn_list (pred_deps->pending_jump_insns, succ_deps->pending_jump_insns); succ_deps->last_pending_memory_flush - = concat_INSN_LIST (pred_deps->last_pending_memory_flush, + = concat_insn_list (pred_deps->last_pending_memory_flush, succ_deps->last_pending_memory_flush); succ_deps->pending_read_list_length += pred_deps->pending_read_list_length; @@ -2653,17 +2660,17 @@ deps_join (class deps_desc *succ_deps, class deps_desc *pred_deps) /* last_function_call is inherited by successor. */ succ_deps->last_function_call - = concat_INSN_LIST (pred_deps->last_function_call, + = concat_insn_list (pred_deps->last_function_call, succ_deps->last_function_call); /* last_function_call_may_noreturn is inherited by successor. */ succ_deps->last_function_call_may_noreturn - = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn, + = concat_insn_list (pred_deps->last_function_call_may_noreturn, succ_deps->last_function_call_may_noreturn); /* sched_before_next_call is inherited by successor. */ succ_deps->sched_before_next_call - = concat_INSN_LIST (pred_deps->sched_before_next_call, + = concat_insn_list (pred_deps->sched_before_next_call, succ_deps->sched_before_next_call); }