Re: [PATCH 6/6] loop-iv.c: make cond_list a vec

[Trevor Saunders]

On Mon, Jun 20, 2016 at 09:11:21PM +0100, Richard Sandiford wrote:
> tbsaunde+...@tbsaunde.org writes:
> > diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
> > index 57fb8c1..21c3180 100644
> > --- a/gcc/loop-iv.c
> > +++ b/gcc/loop-iv.c
> > @@ -1860,7 +1860,6 @@ simplify_using_initial_values (struct loop *loop, 
> > enum rtx_code op, rtx *expr)
> >  {
> >bool expression_valid;
> >rtx head, tail, last_valid_expr;
> > -  rtx_expr_list *cond_list;
> >rtx_insn *insn;
> >rtx neutral, aggr;
> >regset altered, this_altered;
> > @@ -1936,7 +1935,7 @@ simplify_using_initial_values (struct loop *loop, 
> > enum rtx_code op, rtx *expr)
> >  
> >expression_valid = true;
> >last_valid_expr = *expr;
> > -  cond_list = NULL;
> > +  auto_vec cond_list;
> >while (1)
> >  {
> >insn = BB_END (e->src);
> 
> How about using "auto_vec" for some small N, since we expect
> cond_list to be used fairly often?

sure, why not?

> > @@ -1988,39 +1988,30 @@ simplify_using_initial_values (struct loop *loop, 
> > enum rtx_code op, rtx *expr)
> >  
> >   if (suitable_set_for_replacement (insn, , ))
> > {
> > - rtx_expr_list **pnote, **pnote_next;
> > -
> >   replace_in_expr (expr, dest, src);
> >   if (CONSTANT_P (*expr))
> > goto out;
> >  
> > - for (pnote = _list; *pnote; pnote = pnote_next)
> > + unsigned int len = cond_list.length ();
> > + for (unsigned int i = len - 1; i < len; i--)
> > {
> > - rtx_expr_list *note = *pnote;
> > - rtx old_cond = XEXP (note, 0);
> > + rtx old_cond = cond_list[i];
> >  
> > - pnote_next = (rtx_expr_list **) (note, 1);
> > - replace_in_expr ( (note, 0), dest, src);
> > + replace_in_expr (_list[i], dest, src);
> >  
> >   /* We can no longer use a condition that has been simplified
> >  to a constant, and simplify_using_condition will abort if
> >  we try.  */
> > - if (CONSTANT_P (XEXP (note, 0)))
> > -   {
> > - *pnote = *pnote_next;
> > - pnote_next = pnote;
> > - free_EXPR_LIST_node (note);
> > -   }
> > + if (CONSTANT_P (cond_list[i]))
> > +   cond_list.ordered_remove (i);
> 
> Do we really need ordered removes here and below?  Obviously it turns
> the original O(1) operation into O(n), and it wasn't obvious from first
> glance that the order of the conditions was relevant.

I'm not sure, but I certainly don't know that we don't need them.  I
kind of ment to not send this patch because of that question but then
forgot.  I'm not really sure what to do with these, I don't know that I
know what's going on well enough to prove unordered removes are fine,
but I guess I can try.

Trev

> 
> Thanks,
> Richard

Re: [PATCH 6/6] loop-iv.c: make cond_list a vec

[Richard Sandiford]

tbsaunde+...@tbsaunde.org writes:
> diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
> index 57fb8c1..21c3180 100644
> --- a/gcc/loop-iv.c
> +++ b/gcc/loop-iv.c
> @@ -1860,7 +1860,6 @@ simplify_using_initial_values (struct loop *loop, enum 
> rtx_code op, rtx *expr)
>  {
>bool expression_valid;
>rtx head, tail, last_valid_expr;
> -  rtx_expr_list *cond_list;
>rtx_insn *insn;
>rtx neutral, aggr;
>regset altered, this_altered;
> @@ -1936,7 +1935,7 @@ simplify_using_initial_values (struct loop *loop, enum 
> rtx_code op, rtx *expr)
>  
>expression_valid = true;
>last_valid_expr = *expr;
> -  cond_list = NULL;
> +  auto_vec cond_list;
>while (1)
>  {
>insn = BB_END (e->src);

How about using "auto_vec" for some small N, since we expect
cond_list to be used fairly often?

Wish I knew whether there was supposed to be a space before "<"...

> @@ -1988,39 +1988,30 @@ simplify_using_initial_values (struct loop *loop, 
> enum rtx_code op, rtx *expr)
>  
> if (suitable_set_for_replacement (insn, , ))
>   {
> -   rtx_expr_list **pnote, **pnote_next;
> -
> replace_in_expr (expr, dest, src);
> if (CONSTANT_P (*expr))
>   goto out;
>  
> -   for (pnote = _list; *pnote; pnote = pnote_next)
> +   unsigned int len = cond_list.length ();
> +   for (unsigned int i = len - 1; i < len; i--)
>   {
> -   rtx_expr_list *note = *pnote;
> -   rtx old_cond = XEXP (note, 0);
> +   rtx old_cond = cond_list[i];
>  
> -   pnote_next = (rtx_expr_list **) (note, 1);
> -   replace_in_expr ( (note, 0), dest, src);
> +   replace_in_expr (_list[i], dest, src);
>  
> /* We can no longer use a condition that has been simplified
>to a constant, and simplify_using_condition will abort if
>we try.  */
> -   if (CONSTANT_P (XEXP (note, 0)))
> - {
> -   *pnote = *pnote_next;
> -   pnote_next = pnote;
> -   free_EXPR_LIST_node (note);
> - }
> +   if (CONSTANT_P (cond_list[i]))
> + cond_list.ordered_remove (i);

Do we really need ordered removes here and below?  Obviously it turns
the original O(1) operation into O(n), and it wasn't obvious from first
glance that the order of the conditions was relevant.

Thanks,
Richard

[PATCH 6/6] loop-iv.c: make cond_list a vec

[tbsaunde+gcc]

From: Trevor Saunders 

gcc/ChangeLog:

2016-06-20  Trevor Saunders  

* loop-iv.c (simplify_using_initial_values): Make cond_list a vector.
---
 gcc/loop-iv.c | 55 ++-
 1 file changed, 18 insertions(+), 37 deletions(-)

diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 57fb8c1..21c3180 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -1860,7 +1860,6 @@ simplify_using_initial_values (struct loop *loop, enum 
rtx_code op, rtx *expr)
 {
   bool expression_valid;
   rtx head, tail, last_valid_expr;
-  rtx_expr_list *cond_list;
   rtx_insn *insn;
   rtx neutral, aggr;
   regset altered, this_altered;
@@ -1936,7 +1935,7 @@ simplify_using_initial_values (struct loop *loop, enum 
rtx_code op, rtx *expr)
 
   expression_valid = true;
   last_valid_expr = *expr;
-  cond_list = NULL;
+  auto_vec cond_list;
   while (1)
 {
   insn = BB_END (e->src);
@@ -1952,17 +1951,18 @@ simplify_using_initial_values (struct loop *loop, enum 
rtx_code op, rtx *expr)
  simplify_using_condition (cond, expr, altered);
  if (old != *expr)
{
- rtx note;
  if (CONSTANT_P (*expr))
goto out;
- for (note = cond_list; note; note = XEXP (note, 1))
+
+ unsigned int len = cond_list.length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- simplify_using_condition (XEXP (note, 0), expr, altered);
+ simplify_using_condition (cond_list[i], expr, altered);
  if (CONSTANT_P (*expr))
goto out;
}
}
- cond_list = alloc_EXPR_LIST (0, cond, cond_list);
+ cond_list.safe_push (cond);
}
}
 
@@ -1988,39 +1988,30 @@ simplify_using_initial_values (struct loop *loop, enum 
rtx_code op, rtx *expr)
 
  if (suitable_set_for_replacement (insn, , ))
{
- rtx_expr_list **pnote, **pnote_next;
-
  replace_in_expr (expr, dest, src);
  if (CONSTANT_P (*expr))
goto out;
 
- for (pnote = _list; *pnote; pnote = pnote_next)
+ unsigned int len = cond_list.length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- rtx_expr_list *note = *pnote;
- rtx old_cond = XEXP (note, 0);
+ rtx old_cond = cond_list[i];
 
- pnote_next = (rtx_expr_list **) (note, 1);
- replace_in_expr ( (note, 0), dest, src);
+ replace_in_expr (_list[i], dest, src);
 
  /* We can no longer use a condition that has been simplified
 to a constant, and simplify_using_condition will abort if
 we try.  */
- if (CONSTANT_P (XEXP (note, 0)))
-   {
- *pnote = *pnote_next;
- pnote_next = pnote;
- free_EXPR_LIST_node (note);
-   }
+ if (CONSTANT_P (cond_list[i]))
+   cond_list.ordered_remove (i);
  /* Retry simplifications with this condition if either the
 expression or the condition changed.  */
- else if (old_cond != XEXP (note, 0) || old != *expr)
-   simplify_using_condition (XEXP (note, 0), expr, altered);
+ else if (old_cond != cond_list[i] || old != *expr)
+   simplify_using_condition (cond_list[i], expr, altered);
}
}
  else
{
- rtx_expr_list **pnote, **pnote_next;
-
  /* If we did not use this insn to make a replacement, any overlap
 between stores in this insn and our expression will cause the
 expression to become invalid.  */
@@ -2028,19 +2019,10 @@ simplify_using_initial_values (struct loop *loop, enum 
rtx_code op, rtx *expr)
goto out;
 
  /* Likewise for the conditions.  */
- for (pnote = _list; *pnote; pnote = pnote_next)
-   {
- rtx_expr_list *note = *pnote;
- rtx old_cond = XEXP (note, 0);
-
- pnote_next = (rtx_expr_list **) (note, 1);
- if (altered_reg_used (old_cond, this_altered))
-   {
- *pnote = *pnote_next;
- pnote_next = pnote;
- free_EXPR_LIST_node (note);
-   }
-   }
+ unsigned int len = cond_list.length ();
+ for (unsigned int i = len - 1; i < len; i--)
+   if (altered_reg_used (cond_list[i], this_altered))
+ cond_list.ordered_remove (i);
}
 
  if