| Message ID | 1466418128-21257-7-git-send-email-tbsaunde+gcc@tbsaunde.org |
|---|---|
| State | New |
| Headers | show |
tbsaunde+gcc@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<rtx> cond_list; > while (1) > { > insn = BB_END (e->src); How about using "auto_vec<rtx, N>" 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, &dest, &src)) > { > - rtx_expr_list **pnote, **pnote_next; > - > replace_in_expr (expr, dest, src); > if (CONSTANT_P (*expr)) > goto out; > > - for (pnote = &cond_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 **)&XEXP (note, 1); > - replace_in_expr (&XEXP (note, 0), dest, src); > + replace_in_expr (&cond_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
On Mon, Jun 20, 2016 at 09:11:21PM +0100, Richard Sandiford wrote: > tbsaunde+gcc@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<rtx> cond_list; > > while (1) > > { > > insn = BB_END (e->src); > > How about using "auto_vec<rtx, N>" 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, &dest, &src)) > > { > > - rtx_expr_list **pnote, **pnote_next; > > - > > replace_in_expr (expr, dest, src); > > if (CONSTANT_P (*expr)) > > goto out; > > > > - for (pnote = &cond_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 **)&XEXP (note, 1); > > - replace_in_expr (&XEXP (note, 0), dest, src); > > + replace_in_expr (&cond_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
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<rtx> 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, &dest, &src)) { - rtx_expr_list **pnote, **pnote_next; - replace_in_expr (expr, dest, src); if (CONSTANT_P (*expr)) goto out; - for (pnote = &cond_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 **)&XEXP (note, 1); - replace_in_expr (&XEXP (note, 0), dest, src); + replace_in_expr (&cond_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 = &cond_list; *pnote; pnote = pnote_next) - { - rtx_expr_list *note = *pnote; - rtx old_cond = XEXP (note, 0); - - pnote_next = (rtx_expr_list **)&XEXP (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 (CONSTANT_P (*expr)) @@ -2065,7 +2047,6 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) } out: - free_EXPR_LIST_list (&cond_list); if (!CONSTANT_P (*expr)) *expr = last_valid_expr; FREE_REG_SET (altered);
From: Trevor Saunders <tbsaunde+gcc@tbsaunde.org> gcc/ChangeLog: 2016-06-20 Trevor Saunders <tbsaunde+gcc@tbsaunde.org> * loop-iv.c (simplify_using_initial_values): Make cond_list a vector. --- gcc/loop-iv.c | 55 ++++++++++++++++++------------------------------------- 1 file changed, 18 insertions(+), 37 deletions(-)