[PATCH] Vectorize loops with parameterized loop bounds
Aditya Kumar
hiraditya@msn.com
Tue May 26 17:22:00 GMT 2015
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.
gcc/ChangeLog:
2015-05-21 Aditya Kumar <aditya.k7@samsung.com>
2015-05-21 Sebastian Pop <s.pop@samsung.com>
2015-05-21 Abderrazek Zaafrani <a.zaafrani@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
More information about the Gcc-patches
mailing list