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