This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Cleanup code generation in lambda-code
- From: "Sebastian Pop" <sebpop at gmail dot com>
- To: "GCC Patches" <gcc-patches at gcc dot gnu dot org>, "Daniel Berlin" <dberlin at dberlin dot org>
- Cc: "Sjodin, Jan" <Jan dot Sjodin at amd dot com>
- Date: Wed, 6 Jun 2007 01:53:06 +0200
- Subject: [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);