--- /dev/null
+Index: tree-loop-linear.c
+===================================================================
+*** tree-loop-linear.c (revision 113884)
+--- tree-loop-linear.c (working copy)
+***************
+*** 1,5 ****
+ /* Linear Loop transforms
+! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>.
+
+ This file is part of GCC.
+--- 1,5 ----
+ /* Linear Loop transforms
+! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>.
+
+ This file is part of GCC.
+*************** try_interchange_loops (lambda_trans_matr
+*** 243,248 ****
+--- 243,249 ----
+ void
+ linear_transform_loops (struct loops *loops)
+ {
++ bool modified = false;
+ unsigned int i;
+ VEC(tree,heap) *oldivs = NULL;
+ VEC(tree,heap) *invariants = NULL;
+*************** linear_transform_loops (struct loops *lo
+*** 257,263 ****
+ lambda_loopnest before, after;
+ lambda_trans_matrix trans;
+ bool problem = false;
+- bool need_perfect_nest = false;
+ /* 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:
+--- 258,263 ----
+*************** linear_transform_loops (struct loops *lo
+*** 334,345 ****
+ fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
+ continue;
+ }
+! if (!perfect_nest_p (loop_nest))
+! need_perfect_nest = true;
+! before = gcc_loopnest_to_lambda_loopnest (loops,
+! loop_nest, &oldivs,
+! &invariants,
+! need_perfect_nest);
+ if (!before)
+ continue;
+
+--- 334,342 ----
+ fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
+ continue;
+ }
+!
+! before = gcc_loopnest_to_lambda_loopnest (loops, loop_nest, &oldivs,
+! &invariants);
+ if (!before)
+ continue;
+
+*************** linear_transform_loops (struct loops *lo
+*** 357,362 ****
+--- 354,361 ----
+ }
+ lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
+ after, trans);
++ modified = true;
++
+ if (dump_file)
+ fprintf (dump_file, "Successfully transformed loop.\n");
+ free_dependence_relations (dependence_relations);
+*************** linear_transform_loops (struct loops *lo
+*** 365,369 ****
+ VEC_free (tree, heap, oldivs);
+ VEC_free (tree, heap, invariants);
+ scev_reset ();
+! rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
+ }
+--- 364,370 ----
+ VEC_free (tree, heap, oldivs);
+ VEC_free (tree, heap, invariants);
+ scev_reset ();
+!
+! if (modified)
+! rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
+ }
+Index: lambda.h
+===================================================================
+*** lambda.h (revision 113884)
+--- lambda.h (working copy)
+***************
+*** 1,5 ****
+ /* Lambda matrix and vector interface.
+! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+ This file is part of GCC.
+--- 1,5 ----
+ /* Lambda matrix and vector interface.
+! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+ This file is part of GCC.
+*************** void print_lambda_body_vector (FILE *, l
+*** 200,207 ****
+ lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
+ struct loop *,
+ VEC(tree,heap) **,
+! VEC(tree,heap) **,
+! bool);
+ void lambda_loopnest_to_gcc_loopnest (struct loop *,
+ VEC(tree,heap) *, VEC(tree,heap) *,
+ lambda_loopnest, lambda_trans_matrix);
+--- 200,206 ----
+ lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
+ struct loop *,
+ VEC(tree,heap) **,
+! VEC(tree,heap) **);
+ void lambda_loopnest_to_gcc_loopnest (struct loop *,
+ VEC(tree,heap) *, VEC(tree,heap) *,
+ lambda_loopnest, lambda_trans_matrix);
+Index: lambda-code.c
+===================================================================
+*** lambda-code.c (revision 113884)
+--- lambda-code.c (working copy)
+***************
+*** 1,5 ****
+ /* Loop transformation code generation
+! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+ This file is part of GCC.
+--- 1,5 ----
+ /* Loop transformation code generation
+! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+ This file is part of GCC.
+*************** static lambda_lattice lambda_lattice_new
+*** 149,154 ****
+--- 149,155 ----
+ static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
+
+ static tree find_induction_var_from_exit_cond (struct loop *);
++ static bool can_convert_to_perfect_nest (struct loop *);
+
+ /* Create a new lambda body vector. */
+
+*************** DEF_VEC_ALLOC_P(lambda_loop,heap);
+*** 1498,1511 ****
+
+ lambda_loopnest
+ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
+! struct loop * loop_nest,
+ VEC(tree,heap) **inductionvars,
+! VEC(tree,heap) **invariants,
+! bool need_perfect_nest)
+ {
+ lambda_loopnest ret = NULL;
+! struct loop *temp;
+! int depth = 0;
+ size_t i;
+ VEC(lambda_loop,heap) *loops = NULL;
+ VEC(tree,heap) *uboundvars = NULL;
+--- 1499,1511 ----
+
+ lambda_loopnest
+ gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
+! struct loop *loop_nest,
+ VEC(tree,heap) **inductionvars,
+! VEC(tree,heap) **invariants)
+ {
+ lambda_loopnest ret = NULL;
+! struct loop *temp = loop_nest;
+! int depth = depth_of_nest (loop_nest);
+ size_t i;
+ VEC(lambda_loop,heap) *loops = NULL;
+ VEC(tree,heap) *uboundvars = NULL;
+*************** gcc_loopnest_to_lambda_loopnest (struct
+*** 1513,1521 ****
+ VEC(int,heap) *steps = NULL;
+ lambda_loop newloop;
+ tree inductionvar = NULL;
+!
+! depth = depth_of_nest (loop_nest);
+! temp = loop_nest;
+ while (temp)
+ {
+ newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
+--- 1513,1523 ----
+ VEC(int,heap) *steps = NULL;
+ lambda_loop newloop;
+ tree inductionvar = NULL;
+! bool perfect_nest = perfect_nest_p (loop_nest);
+!
+! if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
+! goto fail;
+!
+ while (temp)
+ {
+ newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
+*************** gcc_loopnest_to_lambda_loopnest (struct
+*** 1523,1534 ****
+ &lboundvars, &uboundvars,
+ &steps);
+ if (!newloop)
+! return NULL;
+ VEC_safe_push (tree, heap, *inductionvars, inductionvar);
+ VEC_safe_push (lambda_loop, heap, loops, newloop);
+ temp = temp->inner;
+ }
+! if (need_perfect_nest)
+ {
+ if (!perfect_nestify (currloops, loop_nest,
+ lboundvars, uboundvars, steps, *inductionvars))
+--- 1525,1538 ----
+ &lboundvars, &uboundvars,
+ &steps);
+ if (!newloop)
+! goto fail;
+!
+ VEC_safe_push (tree, heap, *inductionvars, inductionvar);
+ VEC_safe_push (lambda_loop, heap, loops, newloop);
+ temp = temp->inner;
+ }
+!
+! if (!perfect_nest)
+ {
+ if (!perfect_nestify (currloops, loop_nest,
+ lboundvars, uboundvars, steps, *inductionvars))
+*************** gcc_loopnest_to_lambda_loopnest (struct
+*** 1542,1550 ****
+--- 1546,1557 ----
+ fprintf (dump_file,
+ "Successfully converted loop nest to perfect loop nest.\n");
+ }
++
+ ret = lambda_loopnest_new (depth, 2 * depth);
++
+ for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
+ LN_LOOPS (ret)[i] = newloop;
++
+ fail:
+ VEC_free (lambda_loop, heap, loops);
+ VEC_free (tree, heap, uboundvars);
+*************** replace_uses_equiv_to_x_with_y (struct l
+*** 2156,2168 ****
+ {
+ tree use = USE_FROM_PTR (use_p);
+ tree step = NULL_TREE;
+! tree access_fn = NULL_TREE;
+!
+!
+! access_fn = instantiate_parameters
+! (loop, analyze_scalar_evolution (loop, use));
+! if (access_fn != NULL_TREE && access_fn != chrec_dont_know)
+! step = evolution_part_in_loop_num (access_fn, loop->num);
+ if ((step && step != chrec_dont_know
+ && TREE_CODE (step) == INTEGER_CST
+ && int_cst_value (step) == xstep)
+--- 2163,2174 ----
+ {
+ tree use = USE_FROM_PTR (use_p);
+ tree step = NULL_TREE;
+! tree scev = instantiate_parameters (loop,
+! analyze_scalar_evolution (loop, use));
+!
+! if (scev != NULL_TREE && scev != chrec_dont_know)
+! step = evolution_part_in_loop_num (scev, loop->num);
+!
+ if ((step && step != chrec_dont_know
+ && TREE_CODE (step) == INTEGER_CST
+ && int_cst_value (step) == xstep)
+*************** replace_uses_equiv_to_x_with_y (struct l
+*** 2171,2192 ****
+ }
+ }
+
+- /* Return TRUE if STMT uses tree OP in it's uses. */
+-
+- static bool
+- stmt_uses_op (tree stmt, tree op)
+- {
+- ssa_op_iter iter;
+- tree use;
+-
+- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+- {
+- if (use == op)
+- return true;
+- }
+- return false;
+- }
+-
+ /* Return true if STMT is an exit PHI for LOOP */
+
+ static bool
+--- 2177,2182 ----
+*************** can_put_in_inner_loop (struct loop *inne
+*** 2236,2250 ****
+
+ }
+
+
+! /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
+! one. LOOPIVS is a vector of induction variables, one per loop.
+! ATM, we only handle imperfect nests of depth 2, where all of the statements
+! occur after the inner loop. */
+
+ static bool
+! can_convert_to_perfect_nest (struct loop *loop,
+! VEC(tree,heap) *loopivs)
+ {
+ basic_block *bbs;
+ tree exit_condition, phi;
+--- 2226,2264 ----
+
+ }
+
++ /* Return true if STMT can be put *after* the inner loop of LOOP. */
++
++ static bool
++ can_put_after_inner_loop (struct loop *loop, tree stmt)
++ {
++ imm_use_iterator imm_iter;
++ use_operand_p use_p;
++
++ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
++ return false;
++
++ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
++ {
++ if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
++ {
++ basic_block immbb = bb_for_stmt (USE_STMT (use_p));
++
++ if (!dominated_by_p (CDI_DOMINATORS,
++ immbb,
++ loop->inner->header)
++ && !can_put_in_inner_loop (loop->inner, stmt))
++ return false;
++ }
++ }
++ return true;
++ }
+
+! /* Return TRUE if LOOP is an imperfect nest that we can convert to a
+! perfect one. At the moment, we only handle imperfect nests of
+! depth 2, where all of the statements occur after the inner loop. */
+
+ static bool
+! can_convert_to_perfect_nest (struct loop *loop)
+ {
+ basic_block *bbs;
+ tree exit_condition, phi;
+*************** can_convert_to_perfect_nest (struct loop
+*** 2264,2282 ****
+ {
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+- size_t j;
+ tree stmt = bsi_stmt (bsi);
+! tree iv;
+!
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ continue;
+! /* If the statement uses inner loop ivs, we == screwed. */
+! for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++)
+! if (stmt_uses_op (stmt, iv))
+! goto fail;
+!
+ /* If this is a simple operation like a cast that is invariant
+ in the inner loop, only used there, and we can place it
+ there, then it's not going to hurt us.
+--- 2278,2290 ----
+ {
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+!
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ continue;
+!
+ /* If this is a simple operation like a cast that is invariant
+ in the inner loop, only used there, and we can place it
+ there, then it's not going to hurt us.
+*************** can_convert_to_perfect_nest (struct loop
+*** 2286,2295 ****
+ theory that we are going to gain a lot more by interchanging
+ the loop than we are by leaving some invariant code there for
+ some other pass to clean up. */
+! if (TREE_CODE (stmt) == MODIFY_EXPR
+! && is_gimple_cast (TREE_OPERAND (stmt, 1))
+! && can_put_in_inner_loop (loop->inner, stmt))
+! continue;
+
+ /* Otherwise, if the bb of a statement we care about isn't
+ dominated by the header of the inner loop, then we can't
+--- 2294,2358 ----
+ theory that we are going to gain a lot more by interchanging
+ the loop than we are by leaving some invariant code there for
+ some other pass to clean up. */
+! if (TREE_CODE (stmt) == MODIFY_EXPR)
+! {
+! use_operand_p use_a, use_b;
+! imm_use_iterator imm_iter;
+! ssa_op_iter op_iter, op_iter1;
+! tree op0 = TREE_OPERAND (stmt, 0);
+! tree scev = instantiate_parameters
+! (loop, analyze_scalar_evolution (loop, op0));
+!
+! /* If the IV is simple, it can be duplicated. */
+! if (!automatically_generated_chrec_p (scev))
+! {
+! tree step = evolution_part_in_loop_num (scev, loop->num);
+! if (step && step != chrec_dont_know
+! && TREE_CODE (step) == INTEGER_CST)
+! continue;
+! }
+!
+! /* The statement should not define a variable used
+! in the inner loop. */
+! if (TREE_CODE (op0) == SSA_NAME)
+! FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
+! if (bb_for_stmt (USE_STMT (use_a))->loop_father
+! == loop->inner)
+! goto fail;
+!
+! FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
+! {
+! tree node, op = USE_FROM_PTR (use_a);
+!
+! /* The variables should not be used in both loops. */
+! FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
+! if (bb_for_stmt (USE_STMT (use_b))->loop_father
+! == loop->inner)
+! goto fail;
+!
+! /* The statement should not use the value of a
+! scalar that was modified in the loop. */
+! node = SSA_NAME_DEF_STMT (op);
+! if (TREE_CODE (node) == PHI_NODE)
+! FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
+! {
+! tree arg = USE_FROM_PTR (use_b);
+!
+! if (TREE_CODE (arg) == SSA_NAME)
+! {
+! tree arg_stmt = SSA_NAME_DEF_STMT (arg);
+!
+! if (bb_for_stmt (arg_stmt)->loop_father
+! == loop->inner)
+! goto fail;
+! }
+! }
+! }
+!
+! if (can_put_in_inner_loop (loop->inner, stmt)
+! || can_put_after_inner_loop (loop, stmt))
+! continue;
+! }
+
+ /* Otherwise, if the bb of a statement we care about isn't
+ dominated by the header of the inner loop, then we can't
+*************** perfect_nestify (struct loops *loops,
+*** 2379,2392 ****
+ tree stmt;
+ tree oldivvar, ivvar, ivvarinced;
+ VEC(tree,heap) *phis = NULL;
+!
+! if (!can_convert_to_perfect_nest (loop, loopivs))
+! return false;
+!
+! /* Create the new loop */
+!
+ olddest = loop->single_exit->dest;
+! preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
+ headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+
+ /* Push the exit phi nodes that we are moving. */
+--- 2442,2451 ----
+ tree stmt;
+ tree oldivvar, ivvar, ivvarinced;
+ VEC(tree,heap) *phis = NULL;
+!
+! /* Create the new loop. */
+ olddest = loop->single_exit->dest;
+! preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
+ headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+
+ /* Push the exit phi nodes that we are moving. */
+*************** perfect_nestify (struct loops *loops,
+*** 2552,2561 ****
+ continue;
+ }
+
+! replace_uses_equiv_to_x_with_y (loop, stmt,
+! oldivvar,
+! VEC_index (int, steps, 0),
+! ivvar);
+ bsi_move_before (&bsi, &tobsi);
+
+ /* If the statement has any virtual operands, they may
+--- 2611,2619 ----
+ continue;
+ }
+
+! replace_uses_equiv_to_x_with_y
+! (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
+!
+ bsi_move_before (&bsi, &tobsi);
+
+ /* If the statement has any virtual operands, they may
+
projects / packages / gcc.git / commitdiff