This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Lno branch merge part 8 -- canonical induction variable creation
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 1 Aug 2004 20:26:30 +0200
- Subject: [patch] Lno branch merge part 8 -- canonical induction variable creation
Hello,
this patch introduces the following optimization:
Suppose we have a loop for that we are able to find out number
of iterations only by some complicated method (brute force
evaluation, for example). It is not feasible to repeat this
procedure often. So we instead create a simple induction variable
and replace the exit condition of the loop by condition based on
this variable.
This makes it possible to passes with only simple analysis of number
of iterations of a loop (in particular, rtl level unroller) to compute the
number of iterations. This fixes for example PR 11710.
There are few differences with respect to lno branch:
1) On lno branch the pass directly performs complete unrolling of
loops with small constant number of iterations, which makes it
possible to optimize the unrolled code already on tree level.
This part is disabled for now, since we lack the necessary
infrastructure (in particular the loop closed ssa form --
http://gcc.gnu.org/ml/gcc-patches/2004-07/msg00068.html)
in mainline.
One note -- the pass for complete loop unrolling is separated
from canonical iv creation, so that the vectorizer can work
on the loop before it is removed by unrolling, but after
the number of iterations was computed; i.e. vectorizer is
run between the two passes.
2) The pass is disabled by default, since it sometimes creates
unnecessary inuction variables. This is not problem on
lno branch, since they are optimized out in ivopts pass,
but in mainline this could lead to regressions (at least
until ivopts is merged in; but the pass depends on loop
closed ssa as well).
Bootstrapped (with optimization enabled) and regtested on i686.
Zdenek
* tree-ssa-loop-ivcanon.c: New file.
* tree-ssa-loop-manip.c: New file.
* Makefile.in (tree-ssa-loop-ivcanon.o, tree-ssa-loop-manip.o): Add.
(tree-ssa-loop.o): Add SCEV_H dependency.
* cfgloop.c (mark_single_exit_loops): New function.
(verify_loop_structure): Verify single-exit loops.
* cfgloop.h (struct loop): Add single_exit field.
(LOOPS_HAVE_MARKED_SINGLE_EXITS): New constant.
(mark_single_exit_loops): Declare.
(tree_num_loop_insns): Declare.
* cfgloopmanip.c (update_single_exits_after_duplication): New function.
(duplicate_loop_to_header_edge): Use it.
* common.opt (fivcanon): New flag.
* gimplify.c (idx_force_simple, update_addressable_flag,
force_gimple_operand): New functions.
* timevar.def (TV_TREE_LOOP_IVCANON, TV_COMPLETE_UNROLL): New timevars.
* tree-cfg.c (tree_find_edge_insert_loc): Return newly created block.
(bsi_commit_edge_inserts_1): Pass null to tree_find_edge_insert_loc.
(bsi_insert_on_edge_immediate): New function.
* tree-flow.h (bsi_insert_on_edge_immediate,
canonicalize_induction_variables, tree_unroll_loops_completely,
create_iv, force_gimple_operand): Declare.
* tree-optimize.c (init_tree_optimization_passes): Add
pass_iv_canon and pass_complete_unroll.
* tree-pass.h (pass_iv_canon, pass_complete_unroll): Declare.
* tree-scalar-evolution.c (get_loop_exit_condition,
get_exit_conditions_rec, number_of_iterations_in_loop,
scev_initialize): Use single_exit information.
* tree-ssa-loop-niter.c (number_of_iterations_cond): Use
single_exit information.
* tree-ssa-loop.c: Include tree-scalar-evolution.h.
(tree_ssa_loop_init): Mark single exit loops, call scev_initialize.
(tree_ssa_loop_ivcanon, gate_tree_ssa_loop_ivcanon, pass_iv_canon,
tree_complete_unroll, gate_tree_complete_unroll, pass_complete_unroll):
New passes.
(tree_ssa_loop_done): Call scev_finalize.
* tree-ssanames.c (make_ssa_name): Allow creating ssa name before
the defining statement is ready.
* doc/invoke.texi (-fivcanon): Document.
* doc/passes.texi: Document canonical induction variable creation.
* testsuite/gcc.dg/tree-ssa/loop-1.c: New testcase.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1336
diff -c -3 -p -r1.1336 Makefile.in
*** Makefile.in 26 Jul 2004 00:29:37 -0000 1.1336
--- Makefile.in 30 Jul 2004 21:00:45 -0000
*************** OBJS-common = \
*** 898,904 ****
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-ssa-loop-niter.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
--- 898,904 ----
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-ssa-loop-niter.o tree-ssa-loop-ivcanon.o tree-ssa-loop-manip.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** tree-eh.o : tree-eh.c $(TREE_FLOW_H) $(C
*** 1683,1693 ****
tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
! tree-pass.h $(FLAGS_H) tree-inline.h
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
tree-pass.h $(SCEV_H)
tree-ssa-loop-ch.o : tree-ssa-loop-ch.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
--- 1683,1701 ----
tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
! tree-pass.h $(FLAGS_H) tree-inline.h $(SCEV_H)
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
tree-pass.h $(SCEV_H)
+ tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) tree-inline.h \
+ output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
+ tree-pass.h $(SCEV_H)
+ tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
+ output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+ tree-pass.h $(FLAGS_H) cfglayout.h $(SCEV_H)
tree-ssa-loop-ch.o : tree-ssa-loop-ch.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.36
diff -c -3 -p -r1.36 cfgloop.c
*** cfgloop.c 29 Jul 2004 17:47:31 -0000 1.36
--- cfgloop.c 30 Jul 2004 21:00:45 -0000
*************** flow_loop_nodes_find (basic_block header
*** 370,375 ****
--- 370,432 ----
return num_nodes;
}
+ /* For each loop in the lOOPS tree that has just a single exit
+ record the exit edge. */
+
+ void
+ mark_single_exit_loops (struct loops *loops)
+ {
+ basic_block bb;
+ edge e;
+ struct loop *loop;
+ unsigned i;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (loop)
+ loop->single_exit = NULL;
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ if (bb->loop_father == loops->tree_root)
+ continue;
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
+ {
+ /* If we have already seen an exit, mark this by the edge that
+ surely does not occur as any exit. */
+ if (loop->single_exit)
+ loop->single_exit = ENTRY_BLOCK_PTR->succ;
+ else
+ loop->single_exit = e;
+ }
+ }
+ }
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (loop->single_exit == ENTRY_BLOCK_PTR->succ)
+ loop->single_exit = NULL;
+ }
+
+ loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
+ }
+
/* Find the root node of the loop pre-header extended basic block and
the edges along the trace from the root node to the loop header. */
*************** verify_loop_structure (struct loops *loo
*** 1197,1204 ****
}
}
- free (sizes);
-
/* Check get_loop_body. */
for (i = 1; i < loops->num; i++)
{
--- 1254,1259 ----
*************** verify_loop_structure (struct loops *loo
*** 1319,1326 ****
--- 1374,1444 ----
free (irreds);
}
+ /* Check the single_exit. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ memset (sizes, 0, sizeof (unsigned) * loops->num);
+ FOR_EACH_BB (bb)
+ {
+ if (bb->loop_father == loops->tree_root)
+ continue;
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
+ {
+ sizes[loop->num]++;
+ if (loop->single_exit
+ && loop->single_exit != e)
+ {
+ error ("Wrong single exit %d->%d recorded for loop %d.",
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index,
+ loop->num);
+ error ("Right exit is %d->%d.",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ }
+ }
+ }
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (sizes[i] == 1
+ && !loop->single_exit)
+ {
+ error ("Single exit not recorded for loop %d.", loop->num);
+ err = 1;
+ }
+
+ if (sizes[i] != 1
+ && loop->single_exit)
+ {
+ error ("Loop %d should not have single exit (%d -> %d).",
+ loop->num,
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index);
+ err = 1;
+ }
+ }
+ }
+
if (err)
abort ();
+
+ free (sizes);
}
/* Returns latch edge of LOOP. */
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.23
diff -c -3 -p -r1.23 cfgloop.h
*** cfgloop.h 12 Jul 2004 19:31:16 -0000 1.23
--- cfgloop.h 30 Jul 2004 21:00:45 -0000
*************** struct loop
*** 185,190 ****
--- 185,194 ----
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
+
+ /* If not NULL, loop has just single exit edge stored here (edges to the
+ EXIT_BLOCK_PTR do not count. */
+ edge single_exit;
};
/* Flags for state of loop structure. */
*************** enum
*** 192,198 ****
{
LOOPS_HAVE_PREHEADERS = 1,
LOOPS_HAVE_SIMPLE_LATCHES = 2,
! LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
};
/* Structure to hold CFG information about natural loops within a function. */
--- 196,203 ----
{
LOOPS_HAVE_PREHEADERS = 1,
LOOPS_HAVE_SIMPLE_LATCHES = 2,
! LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
! LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
};
/* Structure to hold CFG information about natural loops within a function. */
*************** extern void flow_loop_dump (const struct
*** 258,263 ****
--- 263,269 ----
extern int flow_loop_scan (struct loop *, int);
extern void flow_loop_free (struct loop *);
void mark_irreducible_loops (struct loops *);
+ void mark_single_exit_loops (struct loops *);
extern void create_loop_notes (void);
/* Loop data structure manipulation/querying. */
*************** extern bool flow_loop_nested_p (const st
*** 268,273 ****
--- 274,280 ----
extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
extern struct loop * find_common_loop (struct loop *, struct loop *);
struct loop *superloop_at_depth (struct loop *, unsigned);
+ extern unsigned tree_num_loop_insns (struct loop *);
extern int num_loop_insns (struct loop *);
extern int average_num_loop_insns (struct loop *);
extern unsigned get_loop_level (const struct loop *);
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.27
diff -c -3 -p -r1.27 cfgloopmanip.c
*** cfgloopmanip.c 9 Jul 2004 03:29:26 -0000 1.27
--- cfgloopmanip.c 30 Jul 2004 21:00:45 -0000
*************** can_duplicate_loop_p (struct loop *loop)
*** 821,826 ****
--- 821,851 ----
return ret;
}
+ /* The NBBS blocks in BBS will get duplicated and the copies will be placed
+ to LOOP. Update the single_exit information in superloops of LOOP. */
+
+ static void
+ update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
+ struct loop *loop)
+ {
+ unsigned i;
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 1;
+
+ for (; loop->outer; loop = loop->outer)
+ {
+ if (!loop->single_exit)
+ continue;
+
+ if (loop->single_exit->src->rbi->duplicated)
+ loop->single_exit = NULL;
+ }
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 0;
+ }
+
/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
LOOPS structure and dominators. E's destination must be LOOP header for
*************** duplicate_loop_to_header_edge (struct lo
*** 964,969 ****
--- 989,998 ----
first_active_latch = latch;
}
+ /* Update the information about single exits. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ update_single_exits_after_duplication (bbs, n, target);
+
/* Record exit edge in original loop body. */
if (orig && TEST_BIT (wont_exit, 0))
to_remove[(*n_to_remove)++] = orig;
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.42
diff -c -3 -p -r1.42 common.opt
*** common.opt 25 Jul 2004 22:52:11 -0000 1.42
--- common.opt 30 Jul 2004 21:00:45 -0000
*************** finstrument-functions
*** 472,477 ****
--- 472,481 ----
Common Report Var(flag_instrument_function_entry_exit)
Instrument function entry and exit with profiling calls
+ fivcanon
+ Common Report Var(flag_ivcanon)
+ Create canonical induction variables in loops
+
fkeep-inline-functions
Common Report Var(flag_keep_inline_functions)
Generate code for functions even if they are fully inlined
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.56
diff -c -3 -p -r2.56 gimplify.c
*** gimplify.c 28 Jul 2004 02:57:25 -0000 2.56
--- gimplify.c 30 Jul 2004 21:00:46 -0000
*************** gimplify_function_tree (tree fndecl)
*** 4230,4233 ****
--- 4230,4411 ----
current_function_decl = oldfn;
}
+ /* Forces IDX to be either constant or ssa name. Callback for
+ for_each_index. */
+
+ struct idx_fs_data
+ {
+ tree stmts;
+ };
+
+ static bool
+ idx_force_simple (tree base ATTRIBUTE_UNUSED, tree *idx, void *data)
+ {
+ struct idx_fs_data *d = data;
+ tree stmts;
+
+ *idx = force_gimple_operand (*idx, &stmts, true, NULL_TREE);
+
+ if (stmts)
+ {
+ tree_stmt_iterator tsi = tsi_start (d->stmts);
+ tsi_link_before (&tsi, stmts, TSI_SAME_STMT);
+ }
+
+ return true;
+ }
+
+ /* Updates TREE_ADDRESSABLE flag for the base variable of EXPR. */
+
+ static void
+ update_addressable_flag (tree expr)
+ {
+ if (TREE_CODE (expr) != ADDR_EXPR)
+ abort ();
+
+ expr = TREE_OPERAND (expr, 0);
+ while (TREE_CODE (expr) == ARRAY_REF
+ || TREE_CODE (expr) == COMPONENT_REF
+ || TREE_CODE (expr) == REALPART_EXPR
+ || TREE_CODE (expr) == IMAGPART_EXPR)
+ expr = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (expr) != VAR_DECL
+ && TREE_CODE (expr) != PARM_DECL)
+ return;
+
+ TREE_ADDRESSABLE (expr) = 1;
+ }
+
+ /* Expands EXPR to list of gimple statements STMTS, forcing it to become
+ a gimple operand that is returned. If SIMPLE is true, force the operand
+ to be either ssa_name or integer constant. If VAR is not NULL, make the
+ base variable of the final destination be VAR if possible. */
+
+ tree
+ force_gimple_operand (tree expr, tree *stmts, bool simple, tree var)
+ {
+ enum tree_code code;
+ char class;
+ tree op0, op1, stmts0, stmts1, stmt, rhs, name;
+ tree_stmt_iterator tsi;
+ struct idx_fs_data d;
+ tree atmp;
+
+ /* Throw away the useless type conversions, so that we do not create
+ unnecessary junk. */
+ STRIP_TYPE_NOPS (expr);
+ STRIP_USELESS_TYPE_CONVERSION (expr);
+
+ code = TREE_CODE (expr);
+ class = TREE_CODE_CLASS (code);
+
+ if (is_gimple_val (expr)
+ && (!simple
+ || TREE_CODE (expr) == SSA_NAME
+ || TREE_CODE (expr) == INTEGER_CST))
+ {
+ if (code == ADDR_EXPR)
+ update_addressable_flag (expr);
+
+ *stmts = NULL_TREE;
+ return expr;
+ }
+
+ if (code == ADDR_EXPR)
+ {
+ op0 = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (op0) == INDIRECT_REF)
+ return force_gimple_operand (TREE_OPERAND (op0, 0), stmts, simple,
+ NULL_TREE);
+ }
+
+ if (var)
+ atmp = var;
+ else
+ {
+ atmp = create_tmp_var (TREE_TYPE (expr), "fgotmp");
+ add_referenced_tmp_var (atmp);
+ }
+
+ switch (class)
+ {
+ case '1':
+ case '2':
+ op0 = force_gimple_operand (TREE_OPERAND (expr, 0), &stmts0, false,
+ NULL_TREE);
+ if (class == '2')
+ {
+ op1 = force_gimple_operand (TREE_OPERAND (expr, 1), &stmts1, false,
+ NULL_TREE);
+ rhs = build (code, TREE_TYPE (expr), op0, op1);
+ }
+ else
+ {
+ rhs = build1 (code, TREE_TYPE (expr), op0);
+ stmts1 = NULL_TREE;
+ }
+
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, rhs);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ if (stmts0)
+ {
+ *stmts = stmts0;
+ if (stmts1)
+ {
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmts1, TSI_CONTINUE_LINKING);
+ }
+ }
+ else if (stmts1)
+ *stmts = stmts1;
+ else
+ *stmts = alloc_stmt_list ();
+
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ return name;
+
+ default:
+ break;
+ }
+
+ /* Some specially handled codes: */
+ switch (TREE_CODE (expr))
+ {
+ case ADDR_EXPR:
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, expr);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ *stmts = alloc_stmt_list ();
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
+ d.stmts = *stmts;
+ for_each_index (&TREE_OPERAND (expr, 0), idx_force_simple, &d);
+
+ update_addressable_flag (TREE_OPERAND (stmt, 1));
+
+ return name;
+
+ case INTEGER_CST:
+ if (!TREE_OVERFLOW (expr))
+ abort ();
+
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, expr);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ *stmts = alloc_stmt_list ();
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ return name;
+
+ default:
+ abort ();
+ }
+ }
+
#include "gt-gimplify.h"
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.30
diff -c -3 -p -r1.30 timevar.def
*** timevar.def 10 Jul 2004 04:57:54 -0000 1.30
--- timevar.def 30 Jul 2004 21:00:46 -0000
*************** DEFTIMEVAR (TV_TREE_CD_DCE , "tree
*** 83,88 ****
--- 83,90 ----
DEFTIMEVAR (TV_TREE_DSE , "tree DSE")
DEFTIMEVAR (TV_TREE_LOOP , "tree loop optimization")
DEFTIMEVAR (TV_LIM , "loop invariant motion")
+ DEFTIMEVAR (TV_TREE_LOOP_IVCANON , "tree canonical iv creation")
+ DEFTIMEVAR (TV_COMPLETE_UNROLL , "complete unrolling")
DEFTIMEVAR (TV_TREE_CH , "tree copy headers")
DEFTIMEVAR (TV_TREE_SSA_TO_NORMAL , "tree SSA to normal")
DEFTIMEVAR (TV_TREE_NRV , "tree NRV optimization")
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.36
diff -c -3 -p -r2.36 tree-cfg.c
*** tree-cfg.c 23 Jul 2004 22:37:22 -0000 2.36
--- tree-cfg.c 30 Jul 2004 21:00:46 -0000
*************** bsi_replace (const block_stmt_iterator *
*** 2912,2921 ****
In all cases, the returned *BSI points to the correct location. The
return value is true if insertion should be done after the location,
! or false if it should be done before the location. */
static bool
! tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi)
{
basic_block dest, src;
tree tmp;
--- 2912,2923 ----
In all cases, the returned *BSI points to the correct location. The
return value is true if insertion should be done after the location,
! or false if it should be done before the location. If new basic block
! has to be created, it is stored in *NEW_BB. */
static bool
! tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
! basic_block *new_bb)
{
basic_block dest, src;
tree tmp;
*************** tree_find_edge_insert_loc (edge e, block
*** 2992,2997 ****
--- 2994,3001 ----
/* Otherwise, create a new basic block, and split this edge. */
dest = split_edge (e);
+ if (new_bb)
+ *new_bb = dest;
e = dest->pred;
goto restart;
}
*************** bsi_commit_edge_inserts_1 (edge e)
*** 3035,3041 ****
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
--- 3039,3045 ----
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi, NULL))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
*************** bsi_insert_on_edge (edge e, tree stmt)
*** 3052,3057 ****
--- 3056,3080 ----
append_to_statement_list (stmt, &PENDING_STMT (e));
}
+ /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If new block has to
+ be created, it is returned. */
+
+ basic_block
+ bsi_insert_on_edge_immediate (edge e, tree stmt)
+ {
+ block_stmt_iterator bsi;
+ basic_block new_bb = NULL;
+
+ if (PENDING_STMT (e))
+ abort ();
+
+ if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+
+ return new_bb;
+ }
/*---------------------------------------------------------------------------
Tree specific functions for CFG manipulation
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-flow.h
*** tree-flow.h 23 Jul 2004 22:37:23 -0000 2.29
--- tree-flow.h 30 Jul 2004 21:00:46 -0000
*************** extern basic_block label_to_block (tree)
*** 486,491 ****
--- 486,492 ----
extern void tree_optimize_tail_calls (bool, enum tree_dump_index);
extern edge tree_block_forwards_to (basic_block bb);
extern void bsi_insert_on_edge (edge, tree);
+ extern basic_block bsi_insert_on_edge_immediate (edge, tree);
extern void bsi_commit_edge_inserts (int *);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
*************** struct tree_niter_desc
*** 635,640 ****
--- 636,643 ----
/* In tree-ssa-loop*.c */
void tree_ssa_lim (struct loops *);
+ void canonicalize_induction_variables (struct loops *);
+ void tree_unroll_loops_completely (struct loops *);
void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
struct tree_niter_desc *);
*************** tree can_count_iv_in_wider_type (struct
*** 647,652 ****
--- 650,657 ----
void free_numbers_of_iterations_estimates (struct loops *);
void loop_commit_inserts (void);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
+ void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
+ tree *, tree *);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
*************** void vn_delete (void);
*** 685,690 ****
--- 690,698 ----
/* In tree-sra.c */
void insert_edge_copies (tree stmt, basic_block bb);
+ /* In gimplify.c */
+ tree force_gimple_operand (tree, tree *, bool, tree);
+
#include "tree-flow-inline.h"
#endif /* _TREE_FLOW_H */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.35
diff -c -3 -p -r2.35 tree-optimize.c
*** tree-optimize.c 28 Jul 2004 05:13:08 -0000 2.35
--- tree-optimize.c 30 Jul 2004 21:00:46 -0000
*************** init_tree_optimization_passes (void)
*** 367,372 ****
--- 367,374 ----
p = &pass_loop.sub;
NEXT_PASS (pass_loop_init);
NEXT_PASS (pass_lim);
+ NEXT_PASS (pass_iv_canon);
+ NEXT_PASS (pass_complete_unroll);
NEXT_PASS (pass_loop_done);
*p = NULL;
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.8
diff -c -3 -p -r2.8 tree-pass.h
*** tree-pass.h 28 Jul 2004 05:13:08 -0000 2.8
--- tree-pass.h 30 Jul 2004 21:00:46 -0000
*************** extern struct tree_opt_pass pass_tail_ca
*** 109,114 ****
--- 109,116 ----
extern struct tree_opt_pass pass_loop;
extern struct tree_opt_pass pass_loop_init;
extern struct tree_opt_pass pass_lim;
+ extern struct tree_opt_pass pass_iv_canon;
+ extern struct tree_opt_pass pass_complete_unroll;
extern struct tree_opt_pass pass_loop_done;
extern struct tree_opt_pass pass_ch;
extern struct tree_opt_pass pass_ccp;
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.2
diff -c -3 -p -r2.2 tree-scalar-evolution.c
*** tree-scalar-evolution.c 12 Jul 2004 19:31:16 -0000 2.2
--- tree-scalar-evolution.c 30 Jul 2004 21:00:46 -0000
*************** tree
*** 1001,1018 ****
get_loop_exit_condition (struct loop *loop)
{
tree res = NULL_TREE;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
! if (loop->exit_edges)
{
- edge exit_edge;
tree expr;
- exit_edge = loop->exit_edges[0];
expr = last_stmt (exit_edge->src);
-
if (analyzable_condition (expr))
res = expr;
}
--- 1001,1017 ----
get_loop_exit_condition (struct loop *loop)
{
tree res = NULL_TREE;
+ edge exit_edge = loop->single_exit;
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
! if (exit_edge)
{
tree expr;
expr = last_stmt (exit_edge->src);
if (analyzable_condition (expr))
res = expr;
}
*************** get_exit_conditions_rec (struct loop *lo
*** 1039,1046 ****
get_exit_conditions_rec (loop->inner, exit_conditions);
get_exit_conditions_rec (loop->next, exit_conditions);
! flow_loop_scan (loop, LOOP_EXIT_EDGES);
! if (loop->num_exits == 1)
{
tree loop_condition = get_loop_exit_condition (loop);
--- 1038,1044 ----
get_exit_conditions_rec (loop->inner, exit_conditions);
get_exit_conditions_rec (loop->next, exit_conditions);
! if (loop->single_exit)
{
tree loop_condition = get_loop_exit_condition (loop);
*************** number_of_iterations_in_loop (struct loo
*** 2185,2193 ****
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop\n");
! if (!loop->exit_edges)
goto end;
- exit = loop->exit_edges[0];
if (!number_of_iterations_exit (loop, exit, &niter_desc))
goto end;
--- 2183,2191 ----
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop\n");
! exit = loop->single_exit;
! if (!exit)
goto end;
if (!number_of_iterations_exit (loop, exit, &niter_desc))
goto end;
*************** scev_initialize (struct loops *loops)
*** 2458,2467 ****
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
! {
! flow_loop_scan (loops->parray[i], LOOP_EXIT_EDGES);
! loops->parray[i]->nb_iterations = NULL_TREE;
! }
}
/* Cleans up the information cached by the scalar evolutions analysis. */
--- 2456,2462 ----
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
! loops->parray[i]->nb_iterations = NULL_TREE;
}
/* Cleans up the information cached by the scalar evolutions analysis. */
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: tree-ssa-loop-ivcanon.c
diff -N tree-ssa-loop-ivcanon.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-ivcanon.c 30 Jul 2004 21:00:46 -0000
***************
*** 0 ****
--- 1,286 ----
+ /* Induction variable canonicalization.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ /* This pass detects the loops that iterate a constant number of times,
+ adds a canonical induction variable (step -1, tested against 0)
+ and replaces the exit test. This enables the less powerful rtl
+ level analysis to use this information.
+
+ This might spoil the code in some cases (by increasing register pressure).
+ Note that in the case the new variable is not needed, ivopts will get rid
+ of it, so it might only be a problem when there are no other linear induction
+ variables. In that case the created optimization possibilities are likely
+ to pay up.
+
+ Additionally in case we detect that it is beneficial to unroll the
+ loop completely, we do it right here to expose the optimization
+ possibilities to the following passes. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "cfgloop.h"
+ #include "tree-pass.h"
+ #include "ggc.h"
+ #include "tree-chrec.h"
+ #include "tree-scalar-evolution.h"
+ #include "params.h"
+ #include "flags.h"
+ #include "tree-inline.h"
+
+ /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
+ is the exit edge whose condition is replaced. */
+
+ static void
+ create_canonical_iv (struct loop *loop, edge exit, tree niter)
+ {
+ edge in;
+ tree cond, type, var;
+ block_stmt_iterator incr_at;
+ enum tree_code cmp;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, " iterations.\n");
+ }
+
+ cond = last_stmt (exit->src);
+ in = exit->src->succ;
+ if (in == exit)
+ in = in->succ_next;
+
+ type = TREE_TYPE (niter);
+ niter = fold (build (PLUS_EXPR, type,
+ niter, convert (type, integer_one_node)));
+ incr_at = bsi_last (in->src);
+ create_iv (niter, convert (type, integer_minus_one_node), NULL_TREE, loop,
+ &incr_at, false, NULL, &var);
+
+ cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
+ COND_EXPR_COND (cond) = build (cmp, boolean_type_node,
+ var, convert (type, integer_zero_node));
+ modify_stmt (cond);
+ }
+
+ /* Computes an estimated number of insns in LOOP. */
+
+ unsigned
+ tree_num_loop_insns (struct loop *loop)
+ {
+ basic_block *body = get_loop_body (loop);
+ block_stmt_iterator bsi;
+ unsigned size = 1, i;
+
+ for (i = 0; i < loop->num_nodes; i++)
+ for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ size += estimate_num_insns (bsi_stmt (bsi));
+ free (body);
+
+ return size;
+ }
+
+ /* Tries to unroll LOOP completely, i.e. NITER times. LOOPS is the
+ loop tree. COMPLETELY_UNROLL is true if we should unroll the loop
+ even if it may cause code growth. EXIT is the exit of the loop
+ that should be eliminated. */
+
+ static bool
+ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
+ struct loop *loop,
+ edge exit, tree niter,
+ bool completely_unroll)
+ {
+ tree max_unroll = build_int_2 (PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES),
+ 0);
+ unsigned n_unroll, ninsns;
+ tree cond, dont_exit, do_exit;
+
+ if (loop->inner)
+ return false;
+
+ if (!integer_nonzerop (fold (build (LE_EXPR, boolean_type_node,
+ niter, max_unroll))))
+ return false;
+ n_unroll = tree_low_cst (niter, 1);
+
+ if (n_unroll)
+ {
+ if (!completely_unroll)
+ return false;
+
+ ninsns = tree_num_loop_insns (loop);
+
+ if (n_unroll * ninsns
+ > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
+ return false;
+ }
+
+ if (exit->flags & EDGE_TRUE_VALUE)
+ {
+ dont_exit = boolean_false_node;
+ do_exit = boolean_true_node;
+ }
+ else
+ {
+ dont_exit = boolean_true_node;
+ do_exit = boolean_false_node;
+ }
+ cond = last_stmt (exit->src);
+
+ if (n_unroll)
+ {
+ if (!flag_unroll_loops)
+ return false;
+
+ COND_EXPR_COND (cond) = dont_exit;
+ modify_stmt (cond);
+
+ #if 0
+ /* The necessary infrastructure is not in yet. */
+ if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+ loops, n_unroll, NULL,
+ NULL, NULL, NULL, 0))
+ #endif
+ return false;
+ }
+
+ COND_EXPR_COND (cond) = do_exit;
+ modify_stmt (cond);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
+
+ return true;
+ }
+
+ /* Adds a canonical induction variable to LOOP if suitable. LOOPS is the loops
+ tree. CREATE_IV is true if we may create a new iv. COMPLETELY_UNROLL is
+ true if we should do complete unrolling even if it may cause the code
+ growth. If TRY_EVAL is true, we try to determine the number of iterations
+ of a loop by direct evaluation. Returns true if cfg is changed. */
+
+ static bool
+ canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
+ bool create_iv, bool completely_unroll,
+ bool try_eval)
+ {
+ edge exit = NULL;
+ tree niter;
+
+ niter = number_of_iterations_in_loop (loop);
+ if (TREE_CODE (niter) == INTEGER_CST)
+ {
+ exit = loop->single_exit;
+ if (!just_once_each_iteration_p (loop, exit->src))
+ return false;
+
+ /* The result of number_of_iterations_in_loop is by one higher than
+ we expect (i.e. it returns number of executions of the exit
+ condition, not of the loop latch edge). */
+ niter = fold (build (PLUS_EXPR, TREE_TYPE (niter), niter,
+ convert (TREE_TYPE (niter),
+ integer_minus_one_node)));
+ }
+ else if (try_eval)
+ niter = find_loop_niter_by_eval (loop, &exit);
+
+ if (chrec_contains_undetermined (niter)
+ || TREE_CODE (niter) != INTEGER_CST)
+ return false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Loop %d iterates ", loop->num);
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, " times.\n");
+ }
+
+ if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
+ return true;
+
+ if (create_iv)
+ create_canonical_iv (loop, exit, niter);
+
+ return false;
+ }
+
+ /* The main entry point of the pass. Adds canonical induction variables
+ to the suitable LOOPS. */
+
+ void
+ canonicalize_induction_variables (struct loops *loops)
+ {
+ unsigned i;
+ struct loop *loop;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+
+ if (loop)
+ canonicalize_loop_induction_variables (loops, loop, true, false, true);
+ }
+
+ #if 0
+ /* The necessary infrastructure is not in yet. */
+ if (changed)
+ cleanup_tree_cfg_loop ();
+ #endif
+ }
+
+ /* Unroll LOOPS completely if they iterate just few times. */
+
+ void
+ tree_unroll_loops_completely (struct loops *loops)
+ {
+ unsigned i;
+ struct loop *loop;
+ bool changed = false;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+
+ if (!loop)
+ continue;
+
+ changed |= canonicalize_loop_induction_variables (loops, loop,
+ false, true,
+ !flag_ivcanon);
+ }
+
+ #if 0
+ /* The necessary infrastructure is not in yet. */
+ if (changed)
+ cleanup_tree_cfg_loop ();
+ #endif
+ }
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: tree-ssa-loop-manip.c
diff -N tree-ssa-loop-manip.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-manip.c 30 Jul 2004 21:00:46 -0000
***************
*** 0 ****
--- 1,93 ----
+ /* High-level loop manipulation functions.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "tree-pass.h"
+ #include "cfglayout.h"
+ #include "tree-scalar-evolution.h"
+
+ /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
+ It is expected that neither BASE nor STEP are shared with other expressions
+ (unless the sharing rules allow this). Use VAR as a base var_decl for it
+ (if NULL, a new temporary will be created). The increment will occur at
+ INCR_POS (after it if AFTER is true, before it otherwise). The ssa versions
+ of the variable before and after increment will be stored in VAR_BEFORE and
+ VAR_AFTER (unless they are NULL). */
+
+ void
+ create_iv (tree base, tree step, tree var, struct loop *loop,
+ block_stmt_iterator *incr_pos, bool after,
+ tree *var_before, tree *var_after)
+ {
+ tree stmt, stmts, initial;
+ tree vb, va;
+
+ if (!var)
+ {
+ var = create_tmp_var (TREE_TYPE (base), "ivtmp");
+ add_referenced_tmp_var (var);
+ }
+
+ vb = make_ssa_name (var, NULL_TREE);
+ if (var_before)
+ *var_before = vb;
+ va = make_ssa_name (var, NULL_TREE);
+ if (var_after)
+ *var_after = va;
+
+ stmt = build (MODIFY_EXPR, void_type_node, va,
+ build (PLUS_EXPR, TREE_TYPE (base),
+ vb, step));
+ SSA_NAME_DEF_STMT (va) = stmt;
+ if (after)
+ bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
+
+ initial = force_gimple_operand (base, &stmts, false, var);
+ if (stmts)
+ {
+ basic_block new_bb;
+ edge pe = loop_preheader_edge (loop);
+
+ new_bb = bsi_insert_on_edge_immediate (pe, stmts);
+ if (new_bb)
+ add_bb_to_loop (new_bb, new_bb->pred->src->loop_father);
+ }
+
+ stmt = create_phi_node (vb, loop->header);
+ SSA_NAME_DEF_STMT (vb) = stmt;
+ add_phi_arg (&stmt, initial, loop_preheader_edge (loop));
+ add_phi_arg (&stmt, va, loop_latch_edge (loop));
+ }
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.1
diff -c -3 -p -r2.1 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 9 Jul 2004 03:19:14 -0000 2.1
--- tree-ssa-loop-niter.c 30 Jul 2004 21:00:46 -0000
*************** number_of_iterations_cond (tree type, tr
*** 367,372 ****
--- 367,379 ----
convert (niter_type, integer_one_node));
}
+ assumption = fold (build (FLOOR_MOD_EXPR, niter_type, base1, d));
+ assumption = fold (build (EQ_EXPR, boolean_type_node,
+ assumption, convert (niter_type,
+ integer_zero_node)));
+ assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ assumptions, assumption));
+
tmp = fold (build (EXACT_DIV_EXPR, niter_type, base1, d));
tmp = fold (build (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
niter->niter = fold (build (BIT_AND_EXPR, niter_type, tmp, bound));
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.8
diff -c -3 -p -r2.8 tree-ssa-loop.c
*** tree-ssa-loop.c 10 Jul 2004 04:57:54 -0000 2.8
--- tree-ssa-loop.c 30 Jul 2004 21:00:46 -0000
*************** Software Foundation, 59 Temple Place - S
*** 37,42 ****
--- 37,43 ----
#include "cfgloop.h"
#include "flags.h"
#include "tree-inline.h"
+ #include "tree-scalar-evolution.h"
/* The loop tree currently optimized. */
*************** static void
*** 93,98 ****
--- 94,106 ----
tree_ssa_loop_init (void)
{
current_loops = tree_loop_optimizer_init (dump_file);
+ if (!current_loops)
+ return;
+
+ /* Find the loops that are exitted just through a single edge. */
+ mark_single_exit_loops (current_loops);
+
+ scev_initialize (current_loops);
}
struct tree_opt_pass pass_loop_init =
*************** struct tree_opt_pass pass_lim =
*** 144,149 ****
--- 152,223 ----
TODO_dump_func /* todo_flags_finish */
};
+ /* Canonical induction variable creation pass. */
+
+ static void
+ tree_ssa_loop_ivcanon (void)
+ {
+ if (!current_loops)
+ return;
+
+ canonicalize_induction_variables (current_loops);
+ }
+
+ static bool
+ gate_tree_ssa_loop_ivcanon (void)
+ {
+ return flag_ivcanon != 0;
+ }
+
+ struct tree_opt_pass pass_iv_canon =
+ {
+ "ivcanon", /* name */
+ gate_tree_ssa_loop_ivcanon, /* gate */
+ tree_ssa_loop_ivcanon, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_LOOP_IVCANON, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func /* todo_flags_finish */
+ };
+
+ /* Complete unrolling of loops. */
+
+ static void
+ tree_complete_unroll (void)
+ {
+ if (!current_loops)
+ return;
+
+ tree_unroll_loops_completely (current_loops);
+ }
+
+ static bool
+ gate_tree_complete_unroll (void)
+ {
+ return flag_unroll_loops != 0;
+ }
+
+ struct tree_opt_pass pass_complete_unroll =
+ {
+ "cunroll", /* name */
+ gate_tree_complete_unroll, /* gate */
+ tree_complete_unroll, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_COMPLETE_UNROLL, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func /* todo_flags_finish */
+ };
+
/* Loop optimizer finalization. */
static void
*************** tree_ssa_loop_done (void)
*** 152,157 ****
--- 226,233 ----
if (!current_loops)
return;
+ free_numbers_of_iterations_estimates (current_loops);
+ scev_finalize ();
loop_optimizer_finalize (current_loops,
(dump_flags & TDF_DETAILS ? dump_file : NULL));
current_loops = NULL;
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssanames.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssanames.c
*** tree-ssanames.c 24 Jul 2004 01:05:45 -0000 2.5
--- tree-ssanames.c 30 Jul 2004 21:00:46 -0000
*************** make_ssa_name (tree var, tree stmt)
*** 121,127 ****
#if defined ENABLE_CHECKING
if ((!DECL_P (var)
&& TREE_CODE (var) != INDIRECT_REF)
! || (!IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (stmt)))
&& TREE_CODE (stmt) != PHI_NODE))
abort ();
#endif
--- 121,128 ----
#if defined ENABLE_CHECKING
if ((!DECL_P (var)
&& TREE_CODE (var) != INDIRECT_REF)
! || (stmt
! && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (stmt)))
&& TREE_CODE (stmt) != PHI_NODE))
abort ();
#endif
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.494
diff -c -3 -p -r1.494 invoke.texi
*** doc/invoke.texi 28 Jul 2004 23:57:26 -0000 1.494
--- doc/invoke.texi 30 Jul 2004 21:00:46 -0000
*************** in the following sections.
*** 314,320 ****
-funroll-all-loops -funroll-loops -fpeel-loops @gol
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
-ftree-pre -ftree-ccp -ftree-dce -ftree-loop-optimize @gol
! -ftree-lim @gol
-ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
-ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre @gol
--param @var{name}=@var{value}
--- 314,320 ----
-funroll-all-loops -funroll-loops -fpeel-loops @gol
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
-ftree-pre -ftree-ccp -ftree-dce -ftree-loop-optimize @gol
! -ftree-lim -fivcanon @gol
-ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
-ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre @gol
--param @var{name}=@var{value}
*************** operands of conditions that are invarian
*** 4427,4432 ****
--- 4427,4438 ----
just trivial invariantness analysis in loop unswitching. The pass also includes
store motion.
+ @item -fivcanon
+ Create a canonical counter for number of iterations in the loop for that
+ determining number of iterations requires complicated analysis. Later
+ optimizations then may determine the number easily. Useful especially
+ in connection with unrolling.
+
@item -ftree-sra
Perform scalar replacement of aggregates. This pass replaces structure
references with scalars to prevent committing structures to memory too
Index: doc/passes.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/passes.texi,v
retrieving revision 1.35
diff -c -3 -p -r1.35 passes.texi
*** doc/passes.texi 10 Jul 2004 04:57:58 -0000 1.35
--- doc/passes.texi 30 Jul 2004 21:00:46 -0000
*************** operands of conditions that are invarian
*** 375,382 ****
just trivial invariantness analysis in loop unswitching. The pass also includes
store motion. The pass is implemented in @file{tree-ssa-loop-im.c}.
The optimizations also use various utility functions contained in
! @file{cfgloop.c}, @file{cfgloopanal.c} and @file{cfgloopmanip.c}.
@item Conditional constant propagation
--- 375,389 ----
just trivial invariantness analysis in loop unswitching. The pass also includes
store motion. The pass is implemented in @file{tree-ssa-loop-im.c}.
+ Canonical induction variable creation. This pass creates a simple counter
+ for number of iterations of the loop and replaces the exit condition of the
+ 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}.
+
The optimizations also use various utility functions contained in
! @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
! @file{cfgloopmanip.c}.
@item Conditional constant propagation
Index: testsuite/gcc.dg/tree-ssa/loop-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/loop-1.c
diff -N testsuite/gcc.dg/tree-ssa/loop-1.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/loop-1.c 30 Jul 2004 21:00:47 -0000
***************
*** 0 ****
--- 1,17 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fivcanon -funroll-loops -fdump-tree-ivcanon-details" } */
+
+ void xxx(void)
+ {
+ int x = 45;
+
+ while (x >>= 1)
+ foo ();
+ }
+
+ /* We should be able to find out that the loop iterates four times and unroll it completely. */
+
+ /* { dg-final { scan-tree-dump-times "Added canonical iv to loop 1, 4 iterations" 1 "ivcanon"} } */
+ /* { dg-final { scan-assembler-times "foo" 4} } */
+
+