+++ /dev/null
-*** gcc/gcc/tree-loop-linear.c (revision 113884)
---- gcc/gcc/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);
- }
-*** gcc/gcc/lambda.h (revision 113884)
---- gcc/gcc/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);
-*** gcc/gcc/lambda-code.c (revision 113884)
---- gcc/gcc/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
-