On Tue, May 26, 2015 at 6:48 PM, Aditya Kumar <hiradi...@msn.com> wrote:
> w.r.t. the PR48052, here is the patch which finds out if scev would wrap or
> not.
> The patch symbolically evaluates if valid_niter >= loop->nb_iterations is
> true.
> In that case the scev would not wrap.
> Currently, we only look for two special 'patterns', which are sufficient to
> analyze the test cases.
>
> valid_niter = ~s (= UNIT_MAX - s)
>
> We have to prove that valid_niter >= loop->nb_iterations
>
> Pattern1
> loop->nb_iterations: s>= e ? s - e : 0
> In this case we prove that valid_niter >= loop->nb_iterations in both the
> cases
> i.e., when s >= e and when not.
>
> Pattern2
> loop->nb_iterations: (e - s) -1
> In this case we prove valid_niter >= loop->nb_iterations, by simple analysis
> that
> UINT_MAXi >= e is true in all cases.
>
> We symbolically evaluate conditionals, and subtraction when additional
> constraints are provided.
>
> Adding this evaluation mechanism helps vectorize some loops on 64bit machines
> because on 64bit, a typecast appears which causes scev to bail out.
>
> This patch passes bootstrap and no additional failures on regression test.
The simplifications look generic and thus belong in fold-const.c fold_comparison
(there may be already code that tries to handle those cases but fails for some
unknown reason - you may want to go through existing simplifications to check
that - some comparison folding is also done directly in fold_binary_loc).
Thanks,
Richard.
> gcc/ChangeLog:
>
> 2015-05-21 Aditya Kumar <aditya...@samsung.com>
> 2015-05-21 Sebastian Pop <s....@samsung.com>
> 2015-05-21 Abderrazek Zaafrani <a.zaafr...@samsung.com>
>
> * gcc.dg/vect/pr48052.c: New test.
> * tree-ssa-loop-niter.c (fold_binary_cond_p): Fold a conditional
> operation
> when additional constraints are available.
> (fold_binary_minus_p): Fold a subtraction operations of the form (A -
> B -1)
> when additional constraints are available.
> (scev_probably_wraps_p): Use the above two functions to find whether
> valid_niter>= loop->nb_iterations.
> ---
> gcc/testsuite/gcc.dg/vect/pr48052.c | 26 +++++++
> gcc/tree-ssa-loop-niter.c | 138
> ++++++++++++++++++++++++++++++++++++
> 2 files changed, 164 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/vect/pr48052.c
>
> diff --git a/gcc/testsuite/gcc.dg/vect/pr48052.c
> b/gcc/testsuite/gcc.dg/vect/pr48052.c
> new file mode 100644
> index 0000000..534fb54
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vect/pr48052.c
> @@ -0,0 +1,26 @@
> +/* { dg-do compile } */
> +/* { dg-additional-options "-O3" } */
> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
> +/* { dg-final { cleanup-tree-dump "vect" } } */
> +
> +int foo(int* A, int* B, unsigned start, unsigned BS)
> +{
> + int s;
> + for (unsigned k = start; k < start + BS; k++)
> + {
> + s += A[k] * B[k];
> + }
> +
> + return s;
> +}
> +
> +int bar(int* A, int* B, unsigned BS)
> +{
> + int s;
> + for (unsigned k = 0; k < BS; k++)
> + {
> + s += A[k] * B[k];
> + }
> +
> + return s;
> +}
> diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
> index 042f8df..a14f7e5 100644
> --- a/gcc/tree-ssa-loop-niter.c
> +++ b/gcc/tree-ssa-loop-niter.c
> @@ -3773,6 +3773,133 @@ nowrap_type_p (tree type)
> return false;
> }
>
> +/* Return true when op0>= op1.
> + For example:
> + Where, op0 = ~start_3(D);
> + op1 = start_3(D) <= stop_6(D) ? stop_6(D) - start_3(D) : 0;
> + In this case op0 = UINT_MAX - start_3(D);
> + So, op0>= op1 in all cases because UINT_MAX>= stop_6(D),
> + when TREE_TYPE(stop_6(D)) == unsigned int; */
> +bool
> +fold_binary_cond_p (enum tree_code code, tree type, tree op0, tree op1)
> +{
> + gcc_assert (type == boolean_type_node);
> +
> + if (TREE_TYPE (op0) != TREE_TYPE (op1))
> + return false;
> +
> + /* TODO: Handle other operations. */
> + if (code != GE_EXPR)
> + return false;
> +
> + /* The type of op0 and op1 should be unsigned. */
> + if (!TYPE_UNSIGNED (TREE_TYPE (op0)))
> + return false;
> +
> + if ((TREE_CODE (op0) != BIT_NOT_EXPR) || (TREE_CODE (op1) != COND_EXPR))
> + return false;
> +
> + /* We have to show that in both the cases,
> + (when cond is true and when cond is false) op (op0, op1) is true. */
> + tree neg_op0 = TREE_OPERAND (op0, 0);
> + tree cond_op1 = TREE_OPERAND (op1, 0);
> + tree true_op1 = TREE_OPERAND (op1, 1);
> + tree false_op1 = TREE_OPERAND (op1, 2);
> +
> + gcc_assert (neg_op0 && cond_op1 && true_op1 && false_op1);
> +
> + /* When cond is false. Evaluate op (op0, false_op1). */
> + tree running_exp = fold_binary (code, boolean_type_node, op0, false_op1);
> +
> + if (running_exp == NULL || integer_zerop (running_exp))
> + /* TODO: Handle more cases here. */
> + return false;
> +
> + /* When cond is true. Evaluate op (op0, true_op1). */
> + running_exp = fold_binary (code, boolean_type_node, op0, true_op1);
> +
> + if (running_exp != NULL && integer_nonzerop (running_exp))
> + return true;
> +
> + tree smaller, bigger;
> + if (TREE_CODE (cond_op1) == LE_EXPR)
> + {
> + smaller = TREE_OPERAND (cond_op1, 0);
> + bigger = TREE_OPERAND (cond_op1, 1);
> + }
> + else
> + return false;
> +
> + if (TREE_CODE (true_op1) == MINUS_EXPR)
> + {
> + tree minuend = TREE_OPERAND (true_op1, 0);
> + tree subtrahend = TREE_OPERAND (true_op1, 1);
> +
> + if (subtrahend == neg_op0 && subtrahend == smaller && minuend ==
> bigger)
> + {
> + tree extreme = upper_bound_in_type (TREE_TYPE (neg_op0),
> + TREE_TYPE (neg_op0));
> + running_exp = fold_binary (code, boolean_type_node, extreme,
> minuend);
> + return running_exp != NULL && integer_nonzerop (running_exp);
> + }
> + else
> + return false;
> + }
> + else
> + return false;
> +}
> +
> +/* Return true when op0>= op1 and
> + op0 is ~start3(D) or, UINT_MAX - start3(D)
> + op1 is (_21 - start_3(D)) - 1; */
> +bool
> +fold_binary_minus_p (enum tree_code code, tree type, tree op0, tree op1)
> +{
> + gcc_assert (type == boolean_type_node);
> +
> + if (TREE_TYPE (op0) != TREE_TYPE (op1))
> + return false;
> +
> + /* TODO: Handle other operations. */
> + if (code != GE_EXPR)
> + return false;
> +
> + /* The type of op0 and op1 should be unsigned. */
> + if (!TYPE_UNSIGNED (TREE_TYPE (op0)))
> + return false;
> +
> + if ((TREE_CODE (op0) != BIT_NOT_EXPR) || (TREE_CODE (op1) != MINUS_EXPR))
> + return false;
> +
> + /* We have to show that op (op0, op1) is true. */
> + tree neg_op0 = TREE_OPERAND (op0, 0);
> + tree minuend_op1 = TREE_OPERAND (op1, 0);
> + tree subtrahend_op1 = TREE_OPERAND (op1, 1);
> +
> + gcc_assert (neg_op0 && subtrahend_op1 && minuend_op1);
> +
> + /* TODO: Also check that the integer_cst is positive. */
> + if (TREE_CODE (minuend_op1) != MINUS_EXPR ||
> + TREE_CODE (subtrahend_op1) != INTEGER_CST)
> + return false;
> +
> + tree minuend_minuend_op1 = TREE_OPERAND (minuend_op1, 0);
> + tree subtrahend_minuend_op1 = TREE_OPERAND (minuend_op1, 1);
> +
> + /* TODO: Extend this to evaluate the subtrahends.
> + i.e., when there are complicated operations in the subtrahend. */
> + if (subtrahend_minuend_op1 != neg_op0)
> + return false;
> +
> + tree extreme = upper_bound_in_type (TREE_TYPE (neg_op0), TREE_TYPE
> (neg_op0));
> + tree compare_minuend = fold_binary (GE_EXPR, boolean_type_node,
> + extreme, minuend_minuend_op1);
> +
> + if (compare_minuend != NULL && integer_nonzerop (compare_minuend))
> + return true;
> + return false;
> +}
> +
> /* Return false only when the induction variable BASE + STEP * I is
> known to not overflow: i.e. when the number of iterations is small
> enough with respect to the step and initial condition in order to
> @@ -3867,6 +3994,17 @@ scev_probably_wraps_p (tree base, tree step,
> fold_undefer_and_ignore_overflow_warnings ();
> return false;
> }
> +
> + if (loop->nb_iterations && at_stmt
> + && (fold_binary_cond_p (GE_EXPR, boolean_type_node,
> + valid_niter, loop->nb_iterations)
> + || fold_binary_minus_p (GE_EXPR, boolean_type_node,
> + valid_niter, loop->nb_iterations)))
> + {
> + fold_undefer_and_ignore_overflow_warnings ();
> + return false;
> + }
> +
> if (at_stmt)
> for (bound = loop->bounds; bound; bound = bound->next)
> {
> --
> 2.1.0.243.g30d45f7
>
