On Sun, Apr 22, 2012 at 8:50 AM, Ramana Radhakrishnan
<ramana.radhakrish...@linaro.org> wrote:
> Hi,
>
> A colleague noticed that we were not vectorizing loops that had end of
> loop computations that were MIN type operations that weren't expressed
> in the form of a typical min operation. A transform from (i < x ) &&
> ( i < y) to ( i < min (x, y)) is only something that we should do in
> these situations rather than as a general transformation where we
> might be able to end up generating slightly better code because the
> condition would end up being dependent on an invariant outside the
> loop. However in the general case such a transformation would is not
> advisable - it's up to the reader to work that out.
I don't exactly understand why the general transform is not advisable.
We already synthesize min/max operations.
Can you elaborate on why you think that better code might be generated
when not doing this transform?
> #define min(x,y) ((x) <= (y) ? (x) : (y))
>
> void foo (int x, int y, int * a, int * b, int *c)
> {
> int i;
>
> for (i = 0;
> i < x && i < y;
> /* i < min (x, y); */
> i++)
> a[i] = b[i] * c[i];
>
> }
>
> The patch below deals with this case and I'm guessing that it could
> also handle more of the comparison cases and come up with more
> intelligent choices and should be made quite a lot more robust than
> what it is right now.
Yes. At least if you have i < 5 && i < y we canonicalize it to
i <= 4 && i < y, so your pattern matching would fail.
Btw, the canonical case this happens in is probably
for (i = 0; i < n; ++i)
for (j = 0; j < m && j < i; ++j)
a[i][j] = ...
thus iterating over the lower/upper triangular part of a non-square matrix
(including or not including the diagonal, thus also j < m && j <= i)
Richard.
> regards,
> Ramana
>
>
>
> diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
> index ce5eb20..a529536 100644
> --- a/gcc/tree-ssa-loop-im.c
> +++ b/gcc/tree-ssa-loop-im.c
> @@ -563,6 +563,7 @@ stmt_cost (gimple stmt)
>
> switch (gimple_assign_rhs_code (stmt))
> {
> + case MIN_EXPR:
> case MULT_EXPR:
> case WIDEN_MULT_EXPR:
> case WIDEN_MULT_PLUS_EXPR:
> @@ -971,6 +972,124 @@ rewrite_reciprocal (gimple_stmt_iterator *bsi)
> return stmt1;
> }
>
> +/* We look for a sequence that is :
> + def_stmt1 : x = a < b
> + def_stmt2 : y = a < c
> + stmt: z = x & y
> + use_stmt_cond: if ( z != 0)
> +
> + where b, c are loop invariant .
> +
> + In which case we might as well replace this by :
> +
> + t = min (b, c)
> + if ( a < t )
> +*/
> +
> +static gimple
> +rewrite_min_test (gimple_stmt_iterator *bsi)
> +{
> + gimple stmt, def_stmt_x, def_stmt_y, use_stmt_cond, stmt1;
> + tree x, y, z, a, b, c, var, t, name;
> + use_operand_p use;
> + bool is_lhs_of_comparison = false;
> +
> + stmt = gsi_stmt (*bsi);
> + z = gimple_assign_lhs (stmt);
> +
> + /* We start by looking at whether x is used in the
> + right set of conditions. */
> + if (TREE_CODE (z) != SSA_NAME
> + || !single_imm_use (z, &use, &use_stmt_cond)
> + || gimple_code (use_stmt_cond) != GIMPLE_COND)
> + return stmt;
> +
> + x = gimple_assign_rhs1 (stmt);
> + y = gimple_assign_rhs2 (stmt);
> +
> + if (TREE_CODE (x) != SSA_NAME
> + || TREE_CODE (y) != SSA_NAME)
> + return stmt;
> +
> + def_stmt_x = SSA_NAME_DEF_STMT (x);
> + def_stmt_y = SSA_NAME_DEF_STMT (y);
> +
> + /* def_stmt_x and def_stmt_y should be of the
> + form
> +
> + x = a cmp b
> + y = a cmp c
> +
> + or
> +
> + x = b cmp a
> + y = c cmp a
> + */
> + if (!is_gimple_assign (def_stmt_x)
> + || !is_gimple_assign (def_stmt_y)
> + || (gimple_assign_rhs_code (def_stmt_x)
> + != gimple_assign_rhs_code (def_stmt_y)))
> + return stmt;
> +
> + if (gimple_assign_rhs1 (def_stmt_x) == gimple_assign_rhs1 (def_stmt_y)
> + && (gimple_assign_rhs_code (def_stmt_x) == LT_EXPR
> + || gimple_assign_rhs_code (def_stmt_x) == LE_EXPR))
> + {
> + a = gimple_assign_rhs1 (def_stmt_x);
> + b = gimple_assign_rhs2 (def_stmt_x);
> + c = gimple_assign_rhs2 (def_stmt_y);
> + is_lhs_of_comparison = true;
> + }
> + else
> + {
> + if (gimple_assign_rhs2 (def_stmt_x) == gimple_assign_rhs2 (def_stmt_y)
> + && (gimple_assign_rhs_code (def_stmt_x) == GT_EXPR
> + || gimple_assign_rhs_code (def_stmt_x) == GE_EXPR))
> + {
> + a = gimple_assign_rhs2 (def_stmt_x);
> + b = gimple_assign_rhs1 (def_stmt_x);
> + c = gimple_assign_rhs1 (def_stmt_y);
> + }
> + else
> + return stmt;
> + }
> +
> + if (outermost_invariant_loop (b, loop_containing_stmt (def_stmt_x)) != NULL
> + && outermost_invariant_loop (c, loop_containing_stmt
> (def_stmt_y)) != NULL)
> +
> + {
> + if (dump_file)
> + fprintf (dump_file, "Found a potential transformation to min\n");
> +
> + /* mintmp = min (b , c). */
> +
> + var = create_tmp_var (TREE_TYPE (b), "mintmp");
> + add_referenced_var (var);
> + t = fold_build2 (MIN_EXPR, TREE_TYPE (b), b, c);
> + stmt1 = gimple_build_assign (var, t);
> + name = make_ssa_name (var, stmt1);
> + gimple_assign_set_lhs (stmt1, name);
> + gimple_cond_set_code (use_stmt_cond, gimple_assign_rhs_code
> (def_stmt_x));
> +
> +
> + if (is_lhs_of_comparison)
> + {
> + gimple_cond_set_lhs (use_stmt_cond, a);
> + gimple_cond_set_rhs (use_stmt_cond, name);
> + }
> + else
> + {
> + gimple_cond_set_lhs (use_stmt_cond, name);
> + gimple_cond_set_rhs (use_stmt_cond, a);
> + }
> + update_stmt (use_stmt_cond);
> + gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
> + return stmt1;
> + }
> +
> + return stmt;
> +}
> +
> /* Check if the pattern at *BSI is a bittest of the form
> (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
>
> @@ -1171,6 +1290,11 @@ determine_invariantness_stmt (struct
> dom_walk_data *dw_data ATTRIBUTE_UNUSED,
> && TREE_CODE (op0) == SSA_NAME
> && has_single_use (op0))
> stmt = rewrite_bittest (&bsi);
> + else
> + if (pos == MOVE_POSSIBLE
> + && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
> + stmt = rewrite_min_test (&bsi);
> +
> }
>
> lim_data = init_lim_data (stmt);
