Re: [PATCH] Fold more aggressively for trip counts

["Richard Guenther" <richard.guenther@gmail.com>]

On 1/3/07, Robert Kennedy <jimbob@google.com> wrote:
> Attached is a patch to do a little bit of extra work in analyzing trip
> counts for loops. As a side benefit, some other phases will perhaps
> get slightly better folding results.
>
> The motivation for this patch came from some experiments I did with
> doing strength reduction and linear function test replacement rather
> early in optimization, before, e.g., vectorization. At first, code
> introduced by SR caused some failures by keeping loops from being
> analyzed well, hence the genesis of this patch.
>
> Bootstrapped and tested on i686-pc-linux-gnu.

The fold-const change is ok if you add a testcase.
tree_simplify_using_condition_1
is already complex, ugly and slow - we shouldn't add to that more.
Can you provide
a testcase and see where we create a comparison that makes this extra testing
worthwhile?  Can you fix this place instead?

Thanks,
Richard.

>
>         -- Robert Kennedy
>
>                     ------------------------------
>
> 2007-01-02  Robert Kennedy <jimbob@google.com>
>
>         * tree-ssa-loop-niter.c (tree_simplify_using_condition_1):
>         Simplify using simply related variables, not just identical
>         ones.
>         * fold-const.c (fold_comparison): Fold comparisons like (x *
>         1000 < 0) to (x < 0).
>
> ==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c#16 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c ====
> # action=edit type=text
> --- gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c        2006-12-21 16:55:26.000000000 -0800
> +++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c        2007-01-02 11:06:35.000000000 -0800
> @@ -42,7 +42,7 @@
>     force_fit_type takes a constant, an overflowable flag and prior
>     overflow indicators.  It forces the value to fit the type and sets
>     TREE_OVERFLOW and TREE_CONSTANT_OVERFLOW as appropriate.
> -
> +
>     Note: Since the folders get called on non-gimple code as well as
>     gimple code, we need to handle GIMPLE tuples as well as their
>     corresponding tree equivalents.  */
> @@ -8065,6 +8065,29 @@
>                             variable2);
>      }
>
> +  /* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the
> +     signed arithmetic case.  That form is created by the compiler
> +     often enough for folding it to be of value. One example is in
> +     computing loop trip counts after Operator Strength Reduction.  */
> +  if (!(flag_wrapv || flag_trapv)
> +      && !TYPE_UNSIGNED (TREE_TYPE (arg0))
> +      && TREE_CODE (arg0) == MULT_EXPR
> +      && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
> +          && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)))
> +      && integer_zerop (arg1))
> +    {
> +      tree const1 = TREE_OPERAND (arg0, 1);
> +      tree const2 = arg1;                       /* zero */
> +      tree variable1 = TREE_OPERAND (arg0, 0);
> +      enum tree_code cmp_code = code;
> +
> +      /* If const1 is negative we swap the sense of the comparison.  */
> +      if (tree_int_cst_sgn (const1) < 0)
> +        cmp_code = swap_tree_comparison (cmp_code);
> +
> +      return fold_build2 (cmp_code, type, variable1, const2);
> +    }
> +
>    tem = maybe_canonicalize_comparison (code, type, arg0, arg1);
>    if (tem)
>      return tem;
> ==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c#10 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c ====
> # action=edit type=text
> --- gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c       2006-12-29 11:18:58.000000000 -0800
> +++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c       2007-01-02 11:11:41.000000000 -0800
> @@ -837,6 +837,55 @@
>    if (e && integer_zerop (e))
>      return e;
>
> +  /* Try something a little aggressive: If te is easily expressible in
> +     terms of a variable in cond (resp. notcond), we can give a
> +     stronger answer.  Get the definitions of te's variable(s) and try
> +     checks based on equivalent (or weaker) conditions in terms of
> +     them. The original motivation was to keep Operator Strength
> +     Reduction from hurting subsequent loop optimizations by making
> +     trip counts harder to compute.
> +
> +     TODO: Consider iterating here through copies instead of checking
> +     just one level up.  */
> +
> +  if (COMPARISON_CLASS_P (te))
> +    {
> +      tree def0;
> +      tree def1;
> +
> +      def0 = e0 = TREE_OPERAND (te, 0);
> +      def1 = e1 = TREE_OPERAND (te, 1);
> +
> +      /* Did somebody make sure te is canonicalized somehow? What are the
> +         rules for its canonicalization? */
> +      if (TREE_CODE (e0) == SSA_NAME)
> +        {
> +          tree def = SSA_NAME_DEF_STMT (e0);
> +          if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
> +            def0 = GIMPLE_STMT_OPERAND (def, 1);
> +        }
> +      if (TREE_CODE (e1) == SSA_NAME)
> +        {
> +          tree def = SSA_NAME_DEF_STMT (e1);
> +          if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
> +            def1 = GIMPLE_STMT_OPERAND (def, 1);
> +        }
> +
> +      if (def0 != e0
> +          || def1 != e1)
> +        te = fold_build2 (TREE_CODE (te), boolean_type_node, def0, def1);
> +
> +      /* Check whether COND ==> EXPR.  */
> +      e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
> +      if (e && integer_nonzerop (e))
> +        return e;
> +
> +      /* Check whether COND ==> not EXPR.  */
> +      e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
> +      if (e && integer_zerop (e))
> +        return e;
> +    }
> +
>    return expr;
>  }
>