[RFC] Converting end of loop computations to MIN_EXPRs.

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

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.

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

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