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

[Ramana Radhakrishnan <ramana dot radhakrishnan at linaro dot org>]

Sorry about the delayed response, I've been away for some time.

>
> 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?

The reason why I wasn't happy was because of the code we ended up
generating in this case for ARM comparing the simple examples showed
the following difference - while I'm pretty sure I can massage the
backend to generate the right form in this case with splitters I
probably didn't realize this when I wrote the mail. Given this, I
wonder if it is worth in general doing this transformation in a fold
type operation rather than restricting ourselves only to invariant
operands ?


The canonical example is as below :


#define min(x, y) ((x) < (y)) ? (x) : (y)
int foo (int i, int x ,int y)
{
// return ( i < x) && (i < y);
 return i < (min (x, y));
}


Case with min_expr:

	cmp	r2, r1	@ 8	*arm_smin_insn/1	[length = 8]
	movge	r2, r1
	cmp	r2, r0	@ 23	*arm_cmpsi_insn/3	[length = 4]
	movle	r0, #0	@ 24	*p *arm_movsi_insn/2	[length = 4]
	movgt	r0, #1	@ 25	*p *arm_movsi_insn/2	[length = 4]
	bx	lr	@ 28	*arm_return	[length = 12]


This might well be .

      cmp       r2, r0
      cmpge  r1, r0
     movle    r0, #0
     movgt    r0, #1
     bx           lr

Case without min_expr:

	cmp	r0, r2	@ 28	*cmp_and/6	[length = 8]
	cmplt	r0, r1
	movge	r0, #0	@ 29	*mov_scc	[length = 8]
	movlt	r0, #1
	bx	lr	@ 32	*arm_return	[length = 12]



>
>> #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.

Of-course considering overflow semantics you could transform this to
i < min (x +1, y) where the original condition was i <= x && i < y.

Thinking about it , it's probably right to state that

i op1 X && i op2 Y => i op min (X1, Y1)

when op1 and op2 are identical or according to the table below :

op1     op2             op            X1           Y1
  <         <=               <=            X + 1        Y
  >         >=               >                X            Y + 1
 < =        <                <=             X             Y + 1
  >=         >               >               X + 1         Y


Other than being careful about overflow semantics the second table
is probably worthwhile looking at -

>
> 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

Ok thanks - fair enough .


Ramana

>
> 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);