Fix PR45948: Handle COND_EXPR in expression_expensive_p.

Hi,

this patch makes SCEV const propagation handle COND_EXPRs: previously
they were considered expensive to generate, and now we look at its
operands to decide if it is expensive.

I am testing this on amd64-linux.  Ok for trunk after test?

Thanks,
Sebastian

2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/45948
	* tree-scalar-evolution.c (expression_expensive_p): Handle COND_EXPR.

	* gcc.dg/tree-ssa/ldist-pr45948.c: New.
---
 gcc/ChangeLog                                 |    5 +++++
 gcc/testsuite/ChangeLog                       |    5 +++++
 gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c |   23 +++++++++++++++++++++++
 gcc/tree-scalar-evolution.c                   |    6 ++++++
 4 files changed, 39 insertions(+), 0 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c

On Thu, Dec 2, 2010 at 13:15, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> this patch makes SCEV const propagation handle COND_EXPRs: previously
> they were considered expensive to generate, and now we look at its
> operands to decide if it is expensive.
>
> I am testing this on amd64-linux.  Ok for trunk after test?

This passed regstrap on amd64-linux.

Sebastian

On Thu, Dec 2, 2010 at 8:15 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> this patch makes SCEV const propagation handle COND_EXPRs: previously
> they were considered expensive to generate, and now we look at its
> operands to decide if it is expensive.
>
> I am testing this on amd64-linux.  Ok for trunk after test?

I don't think we should treat COND_EXPRs as inexpensive.  Well,
at least not if we are not sure that doing the propagation allows us
to remove either the complete loop or at least one induction variable.

Richard.

> Thanks,
> Sebastian
>
> 2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR middle-end/45948
>        * tree-scalar-evolution.c (expression_expensive_p): Handle COND_EXPR.
>
>        * gcc.dg/tree-ssa/ldist-pr45948.c: New.
> ---
>  gcc/ChangeLog                                 |    5 +++++
>  gcc/testsuite/ChangeLog                       |    5 +++++
>  gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c |   23 +++++++++++++++++++++++
>  gcc/tree-scalar-evolution.c                   |    6 ++++++
>  4 files changed, 39 insertions(+), 0 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index da56fb6..7502bc5 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,5 +1,10 @@
>  2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>
>
> +       PR middle-end/45948
> +       * tree-scalar-evolution.c (expression_expensive_p): Handle COND_EXPR.
> +
> +2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>
> +
>        PR middle-end/45297
>        * tree-scalar-evolution.c (interpret_rhs_expr): Handle ADDR_EXPR
>        with MEM_REFs as POINTER_PLUS_EXPR.
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 3eeee83..43b1ae5 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,5 +1,10 @@
>  2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>
>
> +       PR middle-end/45948
> +       * gcc.dg/tree-ssa/ldist-pr45948.c: New.
> +
> +2010-12-02  Sebastian Pop  <sebastian.pop@amd.com>
> +
>        PR tree-optimization/45199
>        * gcc.dg/tree-ssa/ldist-15.c: New.
>        * gcc.dg/tree-ssa/ldist-16.c: New.
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c
> new file mode 100644
> index 0000000..f0d07cc
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-pr45948.c
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -ftree-loop-distribution -fdump-tree-ldist-details" } */
> +
> +extern void bar(int);
> +
> +void
> +foo (int i, int n)
> +{
> +  int a[30];
> +  int b[30];
> +  for (; i < n; i++)
> +    a[i] = b[i] = 0;
> +
> +  while (1)
> +    if (b[0])
> +      bar (a[i - 1]);
> +}
> +
> +/* We should apply loop distribution and generate 2 memset (0).  */
> +
> +/* { dg-final { scan-tree-dump "distributed: split to 2" "ldist" } } */
> +/* { dg-final { scan-tree-dump-times "__builtin_memset" 4 "ldist" } } */
> +/* { dg-final { cleanup-tree-dump "ldist" } } */
> diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
> index 4a4bda9..ab21092 100644
> --- a/gcc/tree-scalar-evolution.c
> +++ b/gcc/tree-scalar-evolution.c
> @@ -3253,6 +3253,12 @@ expression_expensive_p (tree expr)
>     return false;
>
>   code = TREE_CODE (expr);
> +
> +  if (code == COND_EXPR)
> +    return expression_expensive_p (TREE_OPERAND (expr, 0))
> +      || expression_expensive_p (TREE_OPERAND (expr, 1))
> +      || expression_expensive_p (TREE_OPERAND (expr, 2));
> +
>   if (code == TRUNC_DIV_EXPR
>       || code == CEIL_DIV_EXPR
>       || code == FLOOR_DIV_EXPR
> --
> 1.7.1
>
>

Hi,

On Fri, Dec 3, 2010 at 05:25, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Dec 2, 2010 at 8:15 PM, Sebastian Pop <sebpop@gmail.com> wrote:
>> Hi,
>>
>> this patch makes SCEV const propagation handle COND_EXPRs: previously
>> they were considered expensive to generate, and now we look at its
>> operands to decide if it is expensive.
>>
>> I am testing this on amd64-linux.  Ok for trunk after test?
>
> I don't think we should treat COND_EXPRs as inexpensive.  Well,

I am looking at the cost of div/mod in the processor_costs tables,
and I see that these are an order of magnitude larger than an add
or a conditional move:

  {COSTS_N_INSNS (19),			/* cost of a divide/mod for QI */

and so we also consider these expressions expensive to generate in
scev const prop.  Now I still fail to see why a COND_EXPR would be
expensive...

Richi, could you please explain why COND_EXPRs are expensive?

Thanks,
Sebastian

On Mon, 6 Dec 2010, Sebastian Pop wrote:

> Hi,
> 
> On Fri, Dec 3, 2010 at 05:25, Richard Guenther
> <richard.guenther@gmail.com> wrote:
> > On Thu, Dec 2, 2010 at 8:15 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> >> Hi,
> >>
> >> this patch makes SCEV const propagation handle COND_EXPRs: previously
> >> they were considered expensive to generate, and now we look at its
> >> operands to decide if it is expensive.
> >>
> >> I am testing this on amd64-linux.  Ok for trunk after test?
> >
> > I don't think we should treat COND_EXPRs as inexpensive.  Well,
> 
> I am looking at the cost of div/mod in the processor_costs tables,
> and I see that these are an order of magnitude larger than an add
> or a conditional move:
> 
>   {COSTS_N_INSNS (19),			/* cost of a divide/mod for QI */
> 
> and so we also consider these expressions expensive to generate in
> scev const prop.  Now I still fail to see why a COND_EXPR would be
> expensive...
> 
> Richi, could you please explain why COND_EXPRs are expensive?

Because COND_EXPRs can expand to control flow - not all CPUs have
conditional moves and we do not expand COND_EXPRs to conditional
moves but rely on RTL if-conversion.

That said, the expression-expensive test lacks tracking of the
size of the expression.  It'll happily treat infinitely nested
COND_EXPRs as cheap (well, so it does for adds).

It would be better to fix the real problem with PR45948 than to
adjust cost metrics here (I will re-consider adjusting cost metrics
during next stage1 if the cost metric gets at least some accumulation
of cost during its expression walk).

Thanks,
Richard.