This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Preliminary patch for PR23820 and PR24309
On 10/13/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> Nope. VRP inserts loop preheaders. So, does
>
> Index: tree-vrp.c
> ===================================================================
> --- tree-vrp.c (revision 129282)
> +++ tree-vrp.c (working copy)
> @@ -6089,7 +6089,7 @@ vrp_finalize (void)
> static unsigned int
> execute_vrp (void)
> {
> - loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
> + loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
> rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
> scev_initialize ();
>
> fix it as well?
>
Nope, and there are a bunch of other tree-ssa.exp fails with that patch.
Attached is the patch that I used and that allows the ltrans-3 to pass.
This patch passed bootstrap on amd64-linux and test with one extra fail:
gcc.dg/fold-compare-2.c
Sebastian
Index: tree-loop-linear.c
===================================================================
--- tree-loop-linear.c (revision 129276)
+++ tree-loop-linear.c (working copy)
@@ -244,6 +244,46 @@ try_interchange_loops (lambda_trans_matr
return trans;
}
+/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
+ are not perfectly nested. */
+
+static unsigned int
+perfect_loop_nest_depth (struct loop *loop_nest)
+{
+ struct loop *temp;
+ unsigned int depth = 1;
+
+ /* If it's not a loop nest, we don't want it. We also don't handle
+ sibling loops properly, which are loops of the following form:
+
+ | for (i = 0; i < 50; i++)
+ | {
+ | for (j = 0; j < 50; j++)
+ | {
+ | ...
+ | }
+ | for (j = 0; j < 50; j++)
+ | {
+ | ...
+ | }
+ | }
+ */
+
+ if (!loop_nest->inner || !single_exit (loop_nest))
+ return 0;
+
+ for (temp = loop_nest->inner; temp; temp = temp->inner)
+ {
+ /* If we have a sibling loop or multiple exit edges, jump ship. */
+ if (temp->next || !single_exit (temp))
+ return 0;
+
+ depth++;
+ }
+
+ return depth;
+}
+
/* Perform a set of linear transforms on loops. */
void
@@ -263,47 +303,18 @@ linear_transform_loops (void)
unsigned int depth = 0;
VEC (ddr_p, heap) *dependence_relations;
VEC (data_reference_p, heap) *datarefs;
- struct loop *temp;
lambda_loopnest before, after;
lambda_trans_matrix trans;
- bool problem = false;
struct obstack lambda_obstack;
gcc_obstack_init (&lambda_obstack);
- /* If it's not a loop nest, we don't want it.
- We also don't handle sibling loops properly,
- which are loops of the following form:
- for (i = 0; i < 50; i++)
- {
- for (j = 0; j < 50; j++)
- {
- ...
- }
- for (j = 0; j < 50; j++)
- {
- ...
- }
- } */
- if (!loop_nest->inner || !single_exit (loop_nest))
+ depth = perfect_loop_nest_depth (loop_nest);
+ if (depth == 0)
continue;
+
VEC_truncate (tree, oldivs, 0);
VEC_truncate (tree, invariants, 0);
- depth = 1;
- for (temp = loop_nest->inner; temp; temp = temp->inner)
- {
- /* If we have a sibling loop or multiple exit edges, jump ship. */
- if (temp->next || !single_exit (temp))
- {
- problem = true;
- break;
- }
- depth ++;
- }
- if (problem)
- continue;
- /* Analyze data references and dependence relations using scev. */
-
datarefs = VEC_alloc (data_reference_p, heap, 10);
dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
compute_data_dependences_for_loop (loop_nest, true, &datarefs,
@@ -353,12 +364,12 @@ linear_transform_loops (void)
print_lambda_loopnest (dump_file, after, 'u');
}
- lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
- &remove_ivs,
- after, trans, &lambda_obstack);
- modified = true;
+ modified = lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs,
+ invariants, &remove_ivs,
+ after, trans,
+ &lambda_obstack);
- if (dump_file)
+ if (modified && dump_file)
fprintf (dump_file, "Successfully transformed loop.\n");
free_and_continue:
Index: testsuite/gcc.dg/tree-ssa/pr23820.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr23820.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr23820.c (revision 0)
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+int t [2][4];
+
+void foo (void)
+{
+ int i, j, k, v;
+ float e;
+ for (;;)
+ {
+ v = 0;
+ for (j = 0; j < 2; j ++)
+ {
+ for (k = 2; k < 4; k ++)
+ {
+ e = 0.0;
+ for (i = 0; i < 4; i ++)
+ e += t [j][i];
+ if (e)
+ v = j;
+ }
+ }
+ t [v][0] = 0;
+ }
+}
Index: testsuite/gcc.dg/tree-ssa/ltrans-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ltrans-3.c (revision 129276)
+++ testsuite/gcc.dg/tree-ssa/ltrans-3.c (working copy)
@@ -17,5 +17,5 @@ int foo(int N, int *res)
*res = sum + N;
}
-/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans" } } */
/* { dg-final { cleanup-tree-dump "ltrans" } } */
Index: testsuite/gcc.dg/tree-ssa/pr24309.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr24309.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr24309.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+float weight[10];
+void lsp_weight_quant(float *x, char *cdbk)
+{
+ int i,j;
+ float dist;
+ int best_id=0;
+ for (i=0;i<16;i++)
+ {
+ for (j=0;j<10;j++)
+ dist=dist+weight[j];
+ if (dist<0)
+ best_id=i;
+ }
+ x[j] = cdbk[best_id*10+j];
+}
Index: lambda.h
===================================================================
--- lambda.h (revision 129276)
+++ lambda.h (working copy)
@@ -204,7 +204,7 @@ lambda_loopnest gcc_loopnest_to_lambda_l
VEC(tree,heap) **,
VEC(tree,heap) **,
struct obstack *);
-void lambda_loopnest_to_gcc_loopnest (struct loop *,
+bool lambda_loopnest_to_gcc_loopnest (struct loop *,
VEC(tree,heap) *, VEC(tree,heap) *,
VEC(tree,heap) **,
lambda_loopnest, lambda_trans_matrix,
Index: lambda-code.c
===================================================================
--- lambda-code.c (revision 129276)
+++ lambda-code.c (working copy)
@@ -1675,6 +1675,37 @@ remove_iv (tree iv_stmt)
}
}
+/* Return true if we are sure that the code generation cannot be
+ performed for this loop nest. */
+
+static bool
+lambda_cannot_generate_loop_nest (VEC (tree, heap) *old_ivs)
+{
+ unsigned i;
+ tree oldiv;
+
+ for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
+ {
+ imm_use_iterator imm_iter;
+ tree oldiv_def;
+ tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
+ tree stmt;
+
+ if (TREE_CODE (oldiv_stmt) == PHI_NODE)
+ oldiv_def = PHI_RESULT (oldiv_stmt);
+ else
+ oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
+ gcc_assert (oldiv_def != NULL_TREE);
+
+ FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
+ {
+ if (TREE_CODE (stmt) == PHI_NODE)
+ return true;
+ }
+ }
+
+ return false;
+}
/* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
it, back into gcc code. This changes the
@@ -1686,9 +1717,11 @@ remove_iv (tree iv_stmt)
INVARIANTS is a vector of loop invariants from the old loopnest.
NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get
- NEW_LOOPNEST. */
+ NEW_LOOPNEST.
+
+ Returns true when the code generation succeeded. */
-void
+bool
lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
VEC(tree,heap) *old_ivs,
VEC(tree,heap) *invariants,
@@ -1705,6 +1738,14 @@ lambda_loopnest_to_gcc_loopnest (struct
block_stmt_iterator bsi;
+ if (lambda_cannot_generate_loop_nest (old_ivs))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Lambda code generation failed to produce code.\n");
+
+ return false;
+ }
+
if (dump_file)
{
transform = lambda_trans_matrix_inverse (transform);
@@ -1865,6 +1906,8 @@ lambda_loopnest_to_gcc_loopnest (struct
VEC_safe_push (tree, heap, *remove_ivs, oldiv_stmt);
}
VEC_free (tree, heap, new_ivs);
+
+ return true;
}
/* Return TRUE if this is not interesting statement from the perspective of
@@ -1972,32 +2015,42 @@ perfect_nest_p (struct loop *loop)
size_t i;
tree exit_cond;
+ /* Loops at depth 0 are perfect nests. */
if (!loop->inner)
return true;
+
bbs = get_loop_body (loop);
exit_cond = get_loop_exit_condition (loop);
+
for (i = 0; i < loop->num_nodes; i++)
{
if (bbs[i]->loop_father == loop)
{
block_stmt_iterator bsi;
+
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == COND_EXPR
+ && exit_cond != stmt)
+ goto non_perfectly_nested;
+
if (stmt == exit_cond
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
+
+ non_perfectly_nested:
free (bbs);
return false;
}
}
}
+
free (bbs);
- /* See if the inner loops are perfectly nested as well. */
- if (loop->inner)
- return perfect_nest_p (loop->inner);
- return true;
+
+ return perfect_nest_p (loop->inner);
}
/* Replace the USES of X in STMT, or uses with the same step as X with Y.
Index: passes.c
===================================================================
--- passes.c (revision 129276)
+++ passes.c (working copy)
@@ -567,8 +567,8 @@ init_optimization_passes (void)
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_merge_phi);
- NEXT_PASS (pass_vrp);
NEXT_PASS (pass_dce);
+ NEXT_PASS (pass_vrp);
NEXT_PASS (pass_cselim);
NEXT_PASS (pass_dominator);
/* The only const/copy propagation opportunities left after