Re: [RFC] Converting end of loop computations to MIN_EXPRs.

[Richard Guenther <richard dot guenther at gmail dot com>]

On Sun, Apr 22, 2012 at 8:50 AM, Ramana Radhakrishnan
<ramana.radhakrishnan@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);