This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Cleanup code generation in lambda-code


Hi,

Here is a patch with the testcase that lead us to consider cleaning
up this part of lamdba:

int medium_loop_interchange(int A[HEIGHT][WIDTH])
{
int i,j;
for(j = 0; j < WIDTH; j++)
  for(i = 0; i < HEIGHT; i++)
     A[i][j] = A[i][j] + A[i][j];
return A[1][1];
}

we tried to interchange this kernel and then vectorize it,
but the vectorization was not able and still is not able to deal
with the code produced by lambda.  The code contained
constructs like that:

lbvtmp.38D.2061_47 = 0;
lbvtmp.38D.2061_48 = lnivtmp.34D.2057_41;
lbvtmp.38D.2061_49 = lbvtmp.38D.2061_47 + lbvtmp.38D.2061_48;

that were generated quite often.  With the proposed patch we no
longer generate such sequences, because we just construct a
linear expression that gets gimplified correctly with a call to
force_gimple_operands.  At least the code that is generated with
this patch is not as difficult to pattern match as it was before.

The next steps are to make sure that the generated code from
lambda is vectorizable, and then also implement some more
transforms like loop skewing, etc.

The patch passed bootstrap on i686-linux with all languages and
BOOT_CFLAGS="-g -O2 -fcheck-data-deps -ftree-loop-linear"
The testsuite is still running, but I verified before that a
make -k check RUNTESTFLAGS=tree-ssa.exp had no regressions.
Ok for trunk?

Sebastian

2007-06-05  Jan Sjodin  <jan.sjodin@amd.com>
	    Sebastian Pop  <sebpop@gmail.com>

	* lambda.h (build_linear_expr): New.
	* lambda-code.c (lbv_to_gcc_expression, lle_to_gcc_expression):
	Use build_linear_expr, call fold and force_gimple_operand.
	(lambda_loopnest_to_gcc_loopnest): Check that there is
	something to insert.
Index: ChangeLog
===================================================================
*** ChangeLog	(revision 125335)
--- ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,12 ----
+ 2007-06-05  Jan Sjodin  <jan.sjodin@amd.com>
+ 	    Sebastian Pop  <sebpop@gmail.com>
+ 
+ 	* lambda.h (build_linear_expr): New.
+ 	* lambda-code.c (lbv_to_gcc_expression, lle_to_gcc_expression): 
+ 	Use build_linear_expr, call fold and force_gimple_operand.
+ 	(lambda_loopnest_to_gcc_loopnest): Check that there is
+ 	something to insert.
+ 
  2007-06-05  Ian Lance Taylor  <iant@google.com>
  
  	* tree-vrp.c (compare_values_warnv): Check TREE_NO_WARNING on a
Index: testsuite/gcc.dg/tree-ssa/ltrans-6.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/ltrans-6.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/ltrans-6.c	(revision 0)
***************
*** 0 ****
--- 1,21 ----
+ /* { dg-do compile } */ 
+ /* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+ /* { dg-require-effective-target size32plus } */
+ 
+ 
+ 
+ int medium_loop_interchange(int A[100][200])
+ {
+   int i,j;
+ 
+   /* This loop should be interchanged. */
+ 
+   for(j = 0; j < 200; j++)
+     for(i = 0; i < 100; i++)
+       A[i][j] = A[i][j] + A[i][j];
+ 
+   return A[1][1];
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
+ /* { dg-final { cleanup-tree-dump "ltrans" } } */
Index: lambda.h
===================================================================
*** lambda.h	(revision 125335)
--- lambda.h	(working copy)
*************** lambda_vector_lexico_pos (lambda_vector 
*** 434,438 ****
--- 434,465 ----
    return true;
  }
  
+ /* Given a vector of induction variables IVS, and a vector of
+    coefficients COEFS, build a tree that is a linear combination of
+    the induction variables.  */
+ 
+ static inline tree
+ build_linear_expr (tree type, lambda_vector coefs, VEC (tree, heap) *ivs)
+ {
+   unsigned i;
+   tree iv;
+   tree expr = fold_convert (type, integer_zero_node);
+ 
+   for (i = 0; VEC_iterate (tree, ivs, i, iv); i++)
+     {
+       int k = coefs[i];
+ 
+       if (k == 1)
+ 	expr = build2 (PLUS_EXPR, type, expr, iv);
+ 
+       else if (k != 0)
+ 	expr = build2 (PLUS_EXPR, type, expr,
+ 		       fold_build2 (MULT_EXPR, type, iv,
+ 				    build_int_cst (type, k)));
+     }
+ 
+   return expr;
+ }
+ 
  #endif /* LAMBDA_H  */
  
Index: lambda-code.c
===================================================================
*** lambda-code.c	(revision 125335)
--- lambda-code.c	(working copy)
*************** lbv_to_gcc_expression (lambda_body_vecto
*** 1528,1598 ****
  		       tree type, VEC(tree,heap) *induction_vars, 
  		       tree *stmts_to_insert)
  {
!   tree stmts, stmt, resvar, name;
!   tree iv;
!   size_t i;
!   tree_stmt_iterator tsi;
  
-   /* Create a statement list and a linear expression temporary.  */
-   stmts = alloc_stmt_list ();
    resvar = create_tmp_var (type, "lbvtmp");
    add_referenced_var (resvar);
! 
!   /* Start at 0.  */
!   stmt = build_gimple_modify_stmt (resvar,
! 				   fold_convert (type, integer_zero_node));
!   name = make_ssa_name (resvar, stmt);
!   GIMPLE_STMT_OPERAND (stmt, 0) = name;
!   tsi = tsi_last (stmts);
!   tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
!   for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
!     {
!       if (LBV_COEFFICIENTS (lbv)[i] != 0)
! 	{
! 	  tree newname;
! 	  tree coeffmult;
! 	  
! 	  /* newname = coefficient * induction_variable */
! 	  coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
! 	  stmt = build_gimple_modify_stmt (resvar,
! 					   fold_build2 (MULT_EXPR, type,
! 							iv, coeffmult));
! 
! 	  newname = make_ssa_name (resvar, stmt);
! 	  GIMPLE_STMT_OPERAND (stmt, 0) = newname;
! 	  fold_stmt (&stmt);
! 	  tsi = tsi_last (stmts);
! 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
! 	  /* name = name + newname */
! 	  stmt = build_gimple_modify_stmt (resvar,
! 					   build2 (PLUS_EXPR, type,
! 						   name, newname));
! 	  name = make_ssa_name (resvar, stmt);
! 	  GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	  fold_stmt (&stmt);
! 	  tsi = tsi_last (stmts);
! 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
! 	}
!     }
! 
!   /* Handle any denominator that occurs.  */
!   if (LBV_DENOMINATOR (lbv) != 1)
!     {
!       tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
!       stmt = build_gimple_modify_stmt (resvar,
! 				       build2 (CEIL_DIV_EXPR, type,
! 					       name, denominator));
!       name = make_ssa_name (resvar, stmt);
!       GIMPLE_STMT_OPERAND (stmt, 0) = name;
!       fold_stmt (&stmt);
!       tsi = tsi_last (stmts);
!       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
!     }
!   *stmts_to_insert = stmts;
!   return name;
  }
  
  /* Convert a linear expression from coefficient and constant form to a
--- 1528,1545 ----
  		       tree type, VEC(tree,heap) *induction_vars, 
  		       tree *stmts_to_insert)
  {
!   int k;
!   tree resvar;
!   tree expr = build_linear_expr (type, LBV_COEFFICIENTS (lbv), induction_vars);
! 
!   k = LBV_DENOMINATOR (lbv);
!   gcc_assert (k != 0);
!   if (k != 1)
!     expr = build2 (CEIL_DIV_EXPR, type, expr, build_int_cst (type, k));
  
    resvar = create_tmp_var (type, "lbvtmp");
    add_referenced_var (resvar);
!   return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
  }
  
  /* Convert a linear expression from coefficient and constant form to a
*************** lle_to_gcc_expression (lambda_linear_exp
*** 1616,1797 ****
  		       VEC(tree,heap) *invariants,
  		       enum tree_code wrap, tree *stmts_to_insert)
  {
!   tree stmts, stmt, resvar, name;
!   size_t i;
!   tree_stmt_iterator tsi;
!   tree iv, invar;
    VEC(tree,heap) *results = NULL;
  
    gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
-   name = NULL_TREE;
-   /* Create a statement list and a linear expression temporary.  */
-   stmts = alloc_stmt_list ();
-   resvar = create_tmp_var (type, "lletmp");
-   add_referenced_var (resvar);
  
!   /* Build up the linear expressions, and put the variable representing the
!      result in the results array.  */
    for (; lle != NULL; lle = LLE_NEXT (lle))
      {
!       /* Start at name = 0.  */
!       stmt = build_gimple_modify_stmt (resvar,
! 				       fold_convert (type, integer_zero_node));
!       name = make_ssa_name (resvar, stmt);
!       GIMPLE_STMT_OPERAND (stmt, 0) = name;
!       fold_stmt (&stmt);
!       tsi = tsi_last (stmts);
!       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
!       /* First do the induction variables.  
!          at the end, name = name + all the induction variables added
!          together.  */
!       for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
! 	{
! 	  if (LLE_COEFFICIENTS (lle)[i] != 0)
! 	    {
! 	      tree newname;
! 	      tree mult;
! 	      tree coeff;
! 
! 	      /* mult = induction variable * coefficient.  */
! 	      if (LLE_COEFFICIENTS (lle)[i] == 1)
! 		{
! 		  mult = VEC_index (tree, induction_vars, i);
! 		}
! 	      else
! 		{
! 		  coeff = build_int_cst (type,
! 					 LLE_COEFFICIENTS (lle)[i]);
! 		  mult = fold_build2 (MULT_EXPR, type, iv, coeff);
! 		}
! 
! 	      /* newname = mult */
! 	      stmt = build_gimple_modify_stmt (resvar, mult);
! 	      newname = make_ssa_name (resvar, stmt);
! 	      GIMPLE_STMT_OPERAND (stmt, 0) = newname;
! 	      fold_stmt (&stmt);
! 	      tsi = tsi_last (stmts);
! 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
! 	      /* name = name + newname */
! 	      stmt = build_gimple_modify_stmt (resvar,
! 					       build2 (PLUS_EXPR, type,
! 						       name, newname));
! 	      name = make_ssa_name (resvar, stmt);
! 	      GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	      fold_stmt (&stmt);
! 	      tsi = tsi_last (stmts);
! 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 	    }
! 	}
! 
!       /* Handle our invariants.
!          At the end, we have name = name + result of adding all multiplied
!          invariants.  */
!       for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
! 	{
! 	  if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
! 	    {
! 	      tree newname;
! 	      tree mult;
! 	      tree coeff;
! 	      int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
! 	      /* mult = invariant * coefficient  */
! 	      if (invcoeff == 1)
! 		{
! 		  mult = invar;
! 		}
! 	      else
! 		{
! 		  coeff = build_int_cst (type, invcoeff);
! 		  mult = fold_build2 (MULT_EXPR, type, invar, coeff);
! 		}
  
! 	      /* newname = mult */
! 	      stmt = build_gimple_modify_stmt (resvar, mult);
! 	      newname = make_ssa_name (resvar, stmt);
! 	      GIMPLE_STMT_OPERAND (stmt, 0) = newname;
! 	      fold_stmt (&stmt);
! 	      tsi = tsi_last (stmts);
! 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 
! 	      /* name = name + newname */
! 	      stmt = build_gimple_modify_stmt (resvar,
! 					       build2 (PLUS_EXPR, type,
! 						       name, newname));
! 	      name = make_ssa_name (resvar, stmt);
! 	      GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	      fold_stmt (&stmt);
! 	      tsi = tsi_last (stmts);
! 	      tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 	    }
! 	}
  
!       /* Now handle the constant.
!          name = name + constant.  */
!       if (LLE_CONSTANT (lle) != 0)
! 	{
! 	  tree incr = build_int_cst (type, LLE_CONSTANT (lle));
! 	  stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
! 							   name, incr));
! 	  name = make_ssa_name (resvar, stmt);
! 	  GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	  fold_stmt (&stmt);
! 	  tsi = tsi_last (stmts);
! 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 	}
  
!       /* Now handle the offset.
!          name = name + linear offset.  */
!       if (LLE_CONSTANT (offset) != 0)
! 	{
! 	  tree incr = build_int_cst (type, LLE_CONSTANT (offset));
! 	  stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
! 							   name, incr));
! 	  name = make_ssa_name (resvar, stmt);
! 	  GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	  fold_stmt (&stmt);
! 	  tsi = tsi_last (stmts);
! 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 	}
  
!       /* Handle any denominator that occurs.  */
!       if (LLE_DENOMINATOR (lle) != 1)
! 	{
! 	  stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
! 	  stmt = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
! 			 type, name, stmt);
! 	  stmt = build_gimple_modify_stmt (resvar, stmt);
! 
! 	  /* name = {ceil, floor}(name/denominator) */
! 	  name = make_ssa_name (resvar, stmt);
! 	  GIMPLE_STMT_OPERAND (stmt, 0) = name;
! 	  tsi = tsi_last (stmts);
! 	  tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
! 	}
!       VEC_safe_push (tree, heap, results, name);
      }
  
!   /* Again, out of laziness, we don't handle this case yet.  It's not
!      hard, it just hasn't occurred.  */
!   gcc_assert (VEC_length (tree, results) <= 2);
!   
    /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR.  */
    if (VEC_length (tree, results) > 1)
      {
!       tree op1 = VEC_index (tree, results, 0);
!       tree op2 = VEC_index (tree, results, 1);
!       stmt = build_gimple_modify_stmt (resvar, build2 (wrap, type, op1, op2));
!       name = make_ssa_name (resvar, stmt);
!       GIMPLE_STMT_OPERAND (stmt, 0) = name;
!       tsi = tsi_last (stmts);
!       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
      }
  
    VEC_free (tree, heap, results);
!   
!   *stmts_to_insert = stmts;
!   return name;
  }
  
  /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
--- 1563,1618 ----
  		       VEC(tree,heap) *invariants,
  		       enum tree_code wrap, tree *stmts_to_insert)
  {
!   int k;
!   tree resvar;
!   tree expr = NULL_TREE;
    VEC(tree,heap) *results = NULL;
  
    gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
  
!   /* Build up the linear expressions.  */
    for (; lle != NULL; lle = LLE_NEXT (lle))
      {
!       expr = build_linear_expr (type, LLE_COEFFICIENTS (lle), induction_vars);
!       expr = build2 (PLUS_EXPR, type, expr,
! 		     build_linear_expr (type, LLE_INVARIANT_COEFFICIENTS (lle),
! 					invariants));
  
!       k = LLE_CONSTANT (lle);
!       if (k)
! 	expr = build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
  
!       k = LLE_CONSTANT (offset);
!       if (k)
! 	expr = build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
  
!       k = LLE_DENOMINATOR (lle);
!       if (k != 1)
! 	expr = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
! 		       type, expr, build_int_cst (type, k));
  
!       expr = fold (expr);
!       VEC_safe_push (tree, heap, results, expr);
      }
  
!   gcc_assert (expr);
! 
    /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR.  */
    if (VEC_length (tree, results) > 1)
      {
!       size_t i;
!       tree op;
! 
!       expr = VEC_index (tree, results, 0);
!       for (i = 1; VEC_iterate (tree, results, i, op); i++)
! 	expr = build2 (wrap, type, expr, op);
      }
  
    VEC_free (tree, heap, results);
! 
!   resvar = create_tmp_var (type, "lletmp");
!   add_referenced_var (resvar);
!   return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
  }
  
  /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
*************** lambda_loopnest_to_gcc_loopnest (struct 
*** 1869,1876 ****
  					     type,
  					     new_ivs,
  					     invariants, MAX_EXPR, &stmts);
!       bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
!       bsi_commit_edge_inserts ();
        /* Build the new upper bound and insert its statements in the
           basic block of the exit condition */
        newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
--- 1690,1701 ----
  					     type,
  					     new_ivs,
  					     invariants, MAX_EXPR, &stmts);
! 
!       if (stmts)
! 	{
! 	  bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
! 	  bsi_commit_edge_inserts ();
! 	}
        /* Build the new upper bound and insert its statements in the
           basic block of the exit condition */
        newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
*************** lambda_loopnest_to_gcc_loopnest (struct 
*** 1882,1888 ****
        exitcond = get_loop_exit_condition (temp);
        bb = bb_for_stmt (exitcond);
        bsi = bsi_after_labels (bb);
!       bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
  
        /* Create the new iv.  */
  
--- 1707,1714 ----
        exitcond = get_loop_exit_condition (temp);
        bb = bb_for_stmt (exitcond);
        bsi = bsi_after_labels (bb);
!       if (stmts)
! 	bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
  
        /* Create the new iv.  */
  
*************** lambda_loopnest_to_gcc_loopnest (struct 
*** 1960,1969 ****
  
  	  newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
  					 new_ivs, &stmts);
! 	  bsi = bsi_for_stmt (stmt);
! 	  /* Insert the statements to build that
! 	     expression.  */
! 	  bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
  
  	  FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
  	    propagate_value (use_p, newiv);
--- 1786,1796 ----
  
  	  newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
  					 new_ivs, &stmts);
! 	  if (stmts)
! 	    {
! 	      bsi = bsi_for_stmt (stmt);
! 	      bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
! 	    }
  
  	  FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
  	    propagate_value (use_p, newiv);

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]