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 . 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 . 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 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 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 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 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