From 5c0f4208a524f059780af5a79732056cc819c8be Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Mon, 19 Sep 2005 11:09:09 +0000 Subject: * Makefile.in (tree-ssa-loop-endcond.o): Add TREE_DATA_REF_H and LAMBDA_H dependency. * common.opt (freverse-loops): New flag. * passes.c (init_optimization_passes): Add pass_loop_reversal. * timevar.def (TV_TREE_LOOP_REVERSE): New timevar. * tree-pass.h (pass_loop_reversal): Declare. * tree-ssa-loop-endcond.c: Include tree-data-ref.h and lambda.h. (final_value_of_iv, may_reverse_loop_p, endcond_candidate_cost, best_endcond_candidate_cost, num_of_forward_traversals, profitable_to_reverse_loop_p, reverse_biv, replace_exit_condition, reverse_loop, loop_reversal, tree_ssa_reverse_loops): New functions. (select_condition_shape): Use final_value_of_iv. (compare_cost): Moved from tree-ssa-loop-ivopts.c. * tree-ssa-loop-ivopts.c (compare_cost): Moved to tree-ssa-loop-endcond.c. * tree-ssa-loop.c (tree_ssa_loop_reversal, * gate_tree_ssa_loop_reversal, pass_loop_reversal): New. * doc/invoke.texi (-freverse-loops): Document. * doc/passes.texi: Document loop reversal, tree-affine.c and tree-ssa-loop-endcond.c. * testsuite/gcc.dg/20050105-1.c: Do not pass -floop-optimize2. * testsuite/gcc.dg/tree-ssa/loop-12.c: New test. git-svn-id: https://gcc.gnu.org/svn/gcc/branches/killloop-branch@104420 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog.killloop | 26 +++ gcc/Makefile.in | 2 +- gcc/common.opt | 4 + gcc/doc/invoke.texi | 7 +- gcc/doc/passes.texi | 10 +- gcc/passes.c | 1 + gcc/testsuite/gcc.dg/20050105-1.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/loop-12.c | 112 +++++++++ gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + gcc/tree-ssa-loop-endcond.c | 386 +++++++++++++++++++++++++++++++- gcc/tree-ssa-loop-ivopts.c | 14 -- gcc/tree-ssa-loop.c | 35 +++ 13 files changed, 579 insertions(+), 22 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-12.c diff --git a/gcc/ChangeLog.killloop b/gcc/ChangeLog.killloop index b84a40070f2..87a9e5cca88 100644 --- a/gcc/ChangeLog.killloop +++ b/gcc/ChangeLog.killloop @@ -1,3 +1,29 @@ +2005-09-19 Zdenek Dvorak + + * Makefile.in (tree-ssa-loop-endcond.o): Add TREE_DATA_REF_H and + LAMBDA_H dependency. + * common.opt (freverse-loops): New flag. + * passes.c (init_optimization_passes): Add pass_loop_reversal. + * timevar.def (TV_TREE_LOOP_REVERSE): New timevar. + * tree-pass.h (pass_loop_reversal): Declare. + * tree-ssa-loop-endcond.c: Include tree-data-ref.h and lambda.h. + (final_value_of_iv, may_reverse_loop_p, endcond_candidate_cost, + best_endcond_candidate_cost, num_of_forward_traversals, + profitable_to_reverse_loop_p, reverse_biv, replace_exit_condition, + reverse_loop, loop_reversal, tree_ssa_reverse_loops): New functions. + (select_condition_shape): Use final_value_of_iv. + (compare_cost): Moved from tree-ssa-loop-ivopts.c. + * tree-ssa-loop-ivopts.c (compare_cost): Moved to + tree-ssa-loop-endcond.c. + * tree-ssa-loop.c (tree_ssa_loop_reversal, + * gate_tree_ssa_loop_reversal, pass_loop_reversal): New. + * doc/invoke.texi (-freverse-loops): Document. + * doc/passes.texi: Document loop reversal, tree-affine.c and + tree-ssa-loop-endcond.c. + + * testsuite/gcc.dg/20050105-1.c: Do not pass -floop-optimize2. + * testsuite/gcc.dg/tree-ssa/loop-12.c: New test. + 2005-09-15 Zdenek Dvorak * tree-data-ref.c (analyze_array, analyze_indirect_ref, init_data_ref, diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 1decc0f3a17..ebc3abf38ab 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1907,7 +1907,7 @@ tree-ssa-loop-endcond.o : tree-ssa-loop-endcond.c $(TREE_FLOW_H) $(CONFIG_H) \ output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \ $(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \ - tree-chrec.h $(VARRAY_H) + tree-chrec.h $(VARRAY_H) $(TREE_DATA_REF_H) $(LAMBDA_H) tree-affine.o : tree-affine.c tree-affine.h $(CONFIG_H) \ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \ output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) diff --git a/gcc/common.opt b/gcc/common.opt index 002d837ccaa..eb2d68b51fc 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -709,6 +709,10 @@ frerun-loop-opt Common Report Var(flag_rerun_loop_opt) Run the loop optimizer twice +freverse-loops +Common Report Var(flag_loop_reversal) Init(0) +Reverse loops when profittable. + frounding-math Common Report Var(flag_rounding_math) Disable optimizations that assume default FP rounding behavior diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index d52e6ec49a6..018068e421e 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -337,7 +337,7 @@ Objective-C and Objective-C++ Dialects}. -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol -ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol -ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre -ftree-vectorize @gol --ftree-salias -fweb @gol +-ftree-salias -fweb -freverse-loops @gol -ftree-copy-prop -ftree-store-ccp -ftree-store-copy-prop -fwhole-program @gol --param @var{name}=@var{value} -O -O0 -O1 -O2 -O3 -Os} @@ -5002,6 +5002,11 @@ determining number of iterations requires complicated analysis. Later optimizations then may determine the number easily. Useful especially in connection with unrolling. +@item -freverse-loops +Reverse loops if it is profitable, i.e., enables the exit test of the +loop to be a compare with zero or other constant, without need to +introduce a new induction variable. + @item -fivopts Perform induction variable optimizations (strength reduction, induction variable merging and induction variable elimination) on trees. diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi index e2fcc7a5d02..a10eab50118 100644 --- a/gcc/doc/passes.texi +++ b/gcc/doc/passes.texi @@ -388,10 +388,18 @@ loop using it, in case when a complicated analysis is necessary to determine the number of iterations. Later optimizations then may determine the number easily. The pass is implemented in @file{tree-ssa-loop-ivcanon.c}. +Loop reversal. This pass revereses loops if it is profitable, i.e, when +this enables the exit test of the loop to be a compare with zero or other +constant, without need to introduce a new induction variable, and this +was not possible for the original loop. This pass is implemented in +@file{tree-ssa-loop-endcond.c}. + Induction variable optimizations. This pass performs standard induction variable optimizations, including strength reduction, induction variable merging and induction variable elimination. The pass is implemented in -@file{tree-ssa-loop-ivopts.c}. +@file{tree-ssa-loop-ivopts.c}, and uses utility functions implemented in +@file{tree-ssa-address.c}, @file{tree-affine.c} and +@file{tree-ssa-loop-endcond.c}. Loop unswitching. This pass moves the conditional jumps that are invariant out of the loops. To achieve this, a duplicate of the loop is created for diff --git a/gcc/passes.c b/gcc/passes.c index 83873d737e5..cc8286d3e60 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -573,6 +573,7 @@ init_optimization_passes (void) pass_may_alias. */ NEXT_PASS (pass_lower_vector_ssa); NEXT_PASS (pass_complete_unroll); + NEXT_PASS (pass_loop_reversal); NEXT_PASS (pass_loop_prefetch); NEXT_PASS (pass_iv_optimize); NEXT_PASS (pass_tree_loop_done); diff --git a/gcc/testsuite/gcc.dg/20050105-1.c b/gcc/testsuite/gcc.dg/20050105-1.c index 46a742ffe63..58a75150bdb 100644 --- a/gcc/testsuite/gcc.dg/20050105-1.c +++ b/gcc/testsuite/gcc.dg/20050105-1.c @@ -1,6 +1,6 @@ /* PR rtl-optimization/18861 */ /* { dg-do compile } */ -/* { dg-options "-O2 -floop-optimize2" } */ +/* { dg-options "-O2" } */ extern void abort (void); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c new file mode 100644 index 00000000000..3fe6ac206f5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c @@ -0,0 +1,112 @@ +/* A test for loop reversal. */ + +/* { dg-do compile } */ +/* { dg-options "-O2 -freverse-loops -fdump-tree-revloops-details" } */ + +int a[1000], b[1000]; + +void bar(void); +void bla(int); + +void foo1 (int n) +{ + int i; + + /* This loop can be reversed, but there is no reason for doing it. */ + for (i = 0; i < n; i++) + a[i] = b[n - i - 1]; +} + +void foo2 (int n) +{ + int i; + + /* This loop can be reversed, and we get a better code if we do it + (but the array is traversed backwards -- this test may need some + tweaking if some architecture defines PREFER_PASSING_MEMORY_FORWARDS). */ + for (i = 0; i < n; i++) + a[i] = b[i]; +} + +void foo3 (int n) +{ + int i; + + /* This loop can be reversed, but would make things worse. */ + for (i = 0; i < n; i++) + a[n - i - 1] = n - i; +} + +void foo4 (int n) +{ + int i; + + /* This loop can be reversed, but it it is doubtful whether it is + profitable. */ + for (i = 0; i < n; i++) + a[n - i - 1] = i; +} + +void foo4a (int n) +{ + int i; + + /* This loop can be reversed, and it is profitable. */ + for (i = 1000; i > n; i--) + a[i] = i; +} + +/* The following three loops cannot be reversed. */ +void foo5 (int n) +{ + int i; + + for (i = 0; i < n; i++) + a[i + 1] = a[i]; +} + +void foo6 (int n) +{ + int i; + + for (i = 0; i < n; i++) + a[i] = a[i + 1]; +} + +void foo7 (int n) +{ + int i; + + for (i = 0; i < n; i++) + bla(i); +} + +void foo8 (int n) +{ + int i; + + /* The following loop can be reversed, but we fail to detect it. + Nevertheless, reversing it is not useful anyway, we may just + create a countdown iv. */ + for (i = 0; i < n; i++) + bar (); +} + +void foo9 (int n) +{ + int i; + + /* The following loop cannot be reversed. */ + for (i = 0; i < 100; i++) + { + a[7] = i; + a[10] = i; + b[i] = i; + } +} + +/* { dg-final { scan-tree-dump-times "SUCCESS: may be reversed" 5 "revloops" } } */ +/* { dg-final { scan-tree-dump-times "SUCCESS: profitable to reverse" 2 "revloops" } } */ +/* { dg-final { scan-tree-dump-times "FAILED: dependence check failed" 5 "revloops" } } */ + +/* { dg-final { cleanup-tree-dump "revloops" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 27dc698b606..57811c0c62a 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -108,6 +108,7 @@ DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree vectorization") DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear") DEFTIMEVAR (TV_TREE_PREFETCH , "tree prefetching") DEFTIMEVAR (TV_TREE_LOOP_IVOPTS , "tree iv optimization") +DEFTIMEVAR (TV_TREE_LOOP_REVERSE , "tree loop reversal") DEFTIMEVAR (TV_TREE_LOOP_INIT , "tree loop init") DEFTIMEVAR (TV_TREE_LOOP_FINI , "tree loop fini") DEFTIMEVAR (TV_TREE_CH , "tree copy headers") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 93717ee4344..c9b19849e67 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -237,6 +237,7 @@ extern struct tree_opt_pass pass_record_bounds; extern struct tree_opt_pass pass_if_conversion; extern struct tree_opt_pass pass_vectorize; extern struct tree_opt_pass pass_complete_unroll; +extern struct tree_opt_pass pass_loop_reversal; extern struct tree_opt_pass pass_loop_prefetch; extern struct tree_opt_pass pass_iv_optimize; extern struct tree_opt_pass pass_tree_loop_done; diff --git a/gcc/tree-ssa-loop-endcond.c b/gcc/tree-ssa-loop-endcond.c index 86dce7a4a62..953f267cfb1 100644 --- a/gcc/tree-ssa-loop-endcond.c +++ b/gcc/tree-ssa-loop-endcond.c @@ -80,6 +80,8 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "cfgloop.h" #include "params.h" #include "langhooks.h" +#include "tree-data-ref.h" +#include "lambda.h" /* Returns period of induction variable with step STEP. */ @@ -198,6 +200,19 @@ may_wrap_around_type_range_p (tree niter, tree step) return !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, niter, range)); } +/* Determines the final value of iv with base BASE and step STEP, in loop + that iterates NITER times. */ + +static tree +final_value_of_iv (tree base, tree step, tree niter) +{ + tree type = TREE_TYPE (base); + + return fold_build2 (PLUS_EXPR, type, base, + fold_build2 (MULT_EXPR, type, step, + fold_convert (type, niter))); +} + /* Given an exit condition comparing an induction variable with value BASE + STEP * i, such that the condition should be true (false if EXIT_P is true) for exactly NITER iterations, choose a best shape @@ -214,7 +229,6 @@ select_condition_shape (tree niter, tree base, tree step, bool exit_p, enum tree_code *cmp, tree *bound) { tree nit_type = TREE_TYPE (niter), per_type, wider_type; - tree iv_type = TREE_TYPE (step); tree period, final; /* To have chance to use this induction variable, its period must be at least @@ -232,9 +246,7 @@ select_condition_shape (tree niter, tree base, tree step, return false; /* Determine the final value of the iv. */ - final = fold_build2 (PLUS_EXPR, iv_type, base, - fold_build2 (MULT_EXPR, iv_type, step, - fold_convert (iv_type, niter))); + final = final_value_of_iv (base, step, niter); /* At this point, we know that we can express the condition as IV != FINAL. */ @@ -265,3 +277,369 @@ end: return true; } + +/* Estimate cost of comparing with BOUND. */ + +unsigned +compare_cost (tree bound) +{ + /* Prefer costants, and prefer zero even more. */ + if (zero_p (bound)) + return 0; + else if (TREE_CODE (bound) == INTEGER_CST) + return 1; + else + return 2; +} + +/* Returns true if it is possible to reverse the LOOP. List of data references + in LOOP is stored to DATAREFS. Number of iterations is stored in NITER. */ + +static bool +may_reverse_loop_p (struct loop *loop, varray_type *datarefs, tree *niter) +{ + edge exit = single_dom_exit (loop); + varray_type dependence_relations; + lambda_trans_matrix trans; + bool ret = false; + struct tree_niter_desc niter_desc; + tree phi; + + /* Only consider innermost loops with just one exit. Not strictly necessary, + but it makes things simpler. */ + if (loop->inner || !exit) + return false; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nConsidering loop %d\n", loop->num); + + /* Latch should be empty. Similarly, this condition is not strictly + necessary, but keeps things simple. */ + if (!empty_block_p (loop->latch) + || !single_pred_p (loop->latch) + || single_pred (loop->latch) != exit->src) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: nonempty latch\n"); + return false; + } + + /* We need to know # of iterations, and there should be no uses of values + defined inside loop outside of it, unless the values are invariants of + the loop. */ + if (!number_of_iterations_exit (loop, exit, &niter_desc, false) + || !zero_p (niter_desc.may_be_zero)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: cannot determine precise number of iterations\n"); + return false; + } + *niter = niter_desc.niter; + + for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) + { + tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit); + + if (is_gimple_reg (val) + && !expr_invariant_in_loop_p (loop, val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: value used outside loop\n"); + return false; + } + } + + /* The iterations of the loop may comunicate only through bivs that can be + reversed. */ + for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) + { + tree def = PHI_RESULT (phi), base, step; + + if (is_gimple_reg (def) + && !simple_iv (loop, phi, def, &base, &step, true)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: non-biv phi node\n"); + return false; + } + } + + VARRAY_GENERIC_PTR_INIT (*datarefs, 10, "datarefs"); + VARRAY_GENERIC_PTR_INIT (dependence_relations, 10, "dependence_relations"); + + /* Check for problems with dependences. */ + compute_data_dependences_for_loop (loop, true, datarefs, + &dependence_relations); + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_data_dependence_relations (dump_file, dependence_relations); + + trans = lambda_trans_matrix_new (1, 1); + LTM_MATRIX (trans)[0][0] = -1; + + if (lambda_transform_legal_p (trans, 1, dependence_relations)) + { + ret = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " SUCCESS: may be reversed\n"); + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: dependence check failed\n"); + + free_dependence_relations (dependence_relations); + return ret; +} + +/* Returns cost of basing exit condition for loop that exits after NITER + iterations on induction variable with BASE and STEP. If REVERSED + is true, we reverse the variable first. */ + +static unsigned +endcond_candidate_cost (tree base, tree step, tree niter, bool reversed) +{ + tree bound; + enum tree_code cmp; + + if (reversed) + { + base = final_value_of_iv (base, step, niter); + step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); + } + + if (!select_condition_shape (niter, base, step, true, &cmp, &bound)) + return 10; + + return compare_cost (bound); +} + +/* Returns the best cost of ending condition of LOOP based on an index of one + of DATAREFS. NITER is number of iterations of the loop. If REVERSED + is true, cost for reversed loop is returned, otherwise cost for original + loop is returned. */ + +static unsigned +best_endcond_candidate_cost (struct loop *loop, varray_type datarefs, + tree niter, bool reversed) +{ + unsigned best = 10, act, i, it; + tree base, step; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + { + struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i); + + for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++) + { + tree chrec = DR_ACCESS_FN (dr, it); + + if (TREE_CODE (chrec) != POLYNOMIAL_CHREC + || CHREC_VARIABLE (chrec) != (unsigned) loop->num) + continue; + + base = CHREC_LEFT (chrec); + step = CHREC_RIGHT (chrec); + if (TREE_CODE (step) != INTEGER_CST + || tree_contains_chrecs (base, NULL) + || chrec_contains_symbols_defined_in_loop (base, loop->num)) + continue; + + act = endcond_candidate_cost (base, step, niter, reversed); + if (act < best) + best = act; + } + } + + return best; +} + +/* Returns difference between number of arrays that are traversed forwards + and backwards in LOOP, according to DATAREFS. */ + +static int +num_of_forward_traversals (struct loop *loop, varray_type datarefs) +{ + unsigned i, it; + int n_forward = 0; + + /* Determine number of data references passed forwards/backwards + in loop. */ + for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + { + struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i); + + for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++) + { + tree chrec = DR_ACCESS_FN (dr, it); + tree tstride = evolution_part_in_loop_num (chrec, loop->num); + + if (tstride != NULL_TREE && !zero_p (tstride)) + { + if (TREE_CODE (tstride) != INTEGER_CST) + { + /* Let's be conservative, and assume everything we do not + understand goes forward. */ + n_forward++; + } + else if (tree_int_cst_sign_bit (tstride)) + n_forward--; + else + n_forward++; + break; + } + } + } + + return n_forward; +} + +/* This can be redefined by md, for architectures that prefer the arrays to be + traversed forwards (because of some simplistic hardware prefetching). */ + +#ifndef PREFER_PASSING_MEMORY_FORWARDS +#define PREFER_PASSING_MEMORY_FORWARDS 0 +#endif + +/* Returns true if it seems to be profitable to reverse the direction + in that loop iterates. DATAREFS is the list of data references in + loop. NITER is the number of iterations of a loop. */ + +static bool +profitable_to_reverse_loop_p (struct loop *loop, varray_type datarefs, + tree niter) +{ + unsigned orig_cost, reversed_cost; + + if (PREFER_PASSING_MEMORY_FORWARDS && datarefs) + { + int n_forward = num_of_forward_traversals (loop, datarefs); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " %d forward traversals\n", n_forward); + + if (n_forward > 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: prefer traversing forwards\n"); + return false; + } + + /* ??? Maybe we would like to reverse the loop just to get the arrays + traversed in the right direction? */ + } + + /* Check whether reversing the loop enables us to use a better ending + condition for it. */ + orig_cost = best_endcond_candidate_cost (loop, datarefs, niter, false); + reversed_cost = best_endcond_candidate_cost (loop, datarefs, niter, true); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " costs: %d orig, %d reversed\n", + orig_cost, reversed_cost); + + if (orig_cost <= reversed_cost) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAILED: no gain from reversing the loop\n"); + return false; + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " SUCCESS: profitable to reverse\n"); + return true; +} + +/* Reverse the biv of LOOP defined in phi node PHI. LOOP iterates NITER + times. */ + +static void +reverse_biv (struct loop *loop, tree phi, tree niter) +{ + block_stmt_iterator bsi_incr = bsi_last (single_dom_exit (loop)->src); + edge entry = loop_preheader_edge (loop); + edge latch = loop_latch_edge (loop); + tree base, step, def = PHI_RESULT (phi), var = SSA_NAME_VAR (def); + tree new_def, stmts; + bool ok; + + ok = simple_iv (loop, phi, def, &base, &step, true); + gcc_assert (ok); + + base = unshare_expr (final_value_of_iv (base, step, niter)); + base = force_gimple_operand (base, &stmts, true, var); + if (stmts) + bsi_insert_on_edge_immediate_loop (entry, stmts); + + SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, entry), base); + + /* Create the increment. */ + new_def = create_increment_stmt (&bsi_incr, false, def, MINUS_EXPR, + unshare_expr (step), var); + SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, latch), new_def); +} + +/* Replace exit condition of LOOP by a test whether NITER iterations + have elapsed. */ + +static void +replace_exit_condition (struct loop *loop, tree niter) +{ + create_canonical_iv (loop, single_dom_exit (loop), niter); +} + +/* Reverse LOOP. NITER is number of its iterations. */ + +static void +reverse_loop (struct loop *loop, tree niter) +{ + tree phi, var; + + /* Rewrite the phi nodes and adjust increments of the bivs. */ + for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) + { + var = PHI_RESULT (phi); + if (!is_gimple_reg (var)) + continue; + + reverse_biv (loop, phi, niter); + } + + replace_exit_condition (loop, niter); +} + +/* Reverse LOOP if possible and profitable. Returns true if LOOP was + reversed. */ + +static bool +loop_reversal (struct loop *loop) +{ + varray_type datarefs = NULL; + tree niter; + bool reversed = false; + + if (may_reverse_loop_p (loop, &datarefs, &niter) + && profitable_to_reverse_loop_p (loop, datarefs, niter)) + { + reverse_loop (loop, niter); + reversed = true; + } + + free_data_refs (datarefs); + return reversed; +} + +/* Try reversing the LOOPS, in case it gives a better ending condition. */ + +void +tree_ssa_reverse_loops (struct loops *loops) +{ + unsigned i; + struct loop *loop; + bool changed = false; + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (loop) + changed |= loop_reversal (loop); + } + + if (changed) + scev_reset (); +} diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index c7de71fac61..ddd7a48c526 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -3627,20 +3627,6 @@ get_computation_cost (struct ivopts_data *data, use, cand, address_p, depends_on, use->stmt); } -/* Estimate cost of comparing with BOUND. */ - -unsigned -compare_cost (tree bound) -{ - /* Prefer costants, and prefer zero even more. */ - if (zero_p (bound)) - return 0; - else if (TREE_CODE (bound) == INTEGER_CST) - return 1; - else - return 2; -} - /* Determines cost of basing replacement of USE on CAND in a generic expression. */ diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index 5e2e738ea43..f35827b3af8 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -406,6 +406,41 @@ struct tree_opt_pass pass_complete_unroll = 0 /* letter */ }; +/* Loop reversal. */ + +static void +tree_ssa_loop_reversal (void) +{ + if (!current_loops) + return; + + tree_ssa_reverse_loops (current_loops); +} + +static bool +gate_tree_ssa_loop_reversal (void) +{ + return flag_loop_reversal != 0; +} + +struct tree_opt_pass pass_loop_reversal = +{ + "revloops", /* name */ + gate_tree_ssa_loop_reversal, /* gate */ + tree_ssa_loop_reversal, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_LOOP_REVERSE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ + 0 /* letter */ +}; + + /* Prefetching. */ static void -- cgit v1.2.3