This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Lno branch merge part 4 -- loop optimizer skeleton
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 29 Jun 2004 20:42:41 +0200
- Subject: [patch] Lno branch merge part 4 -- loop optimizer skeleton
Hello,
this patch adds a framework into that the tree-level loop optimizations
are to be added.
Bootstrapped & regtested on i686.
Zdenek
* common.opt (ftree-loop-optimize): New flag.
* tree-flow.h (rewrite_into_ssa): Declaration changed.
(kill_redundant_phi_nodes): Declare.
* tree-into-ssa.c (rewrite_into_ssa): Use parameter to decide whether
to create ssa form for all variables.
(rewrite_all_into_ssa): New.
(pass_build_ssa): Use rewrite_all_into_ssa.
* tree-optimize.c (init_tree_optimization_passes): Add pass_loop.
(execute_todo): Do not free vars_to_rename bitmap.
(execute_one_pass): Do not allocate vars_to_rename bitmap.
(tree_rest_of_compilation): Allocate vars_to_rename the first time.
* tree-pass.h (pass_loop_init, pass_loop_done): Declare.
* tree-ssa-dom.c (tree_ssa_dominator_optimize): Pass false to
rewrite_into_ssa.
* tree-ssa-loop.c (current_loops): New variable.
(tree_loop_optimizer_init, gate_loop, tree_ssa_loop_init,
tree_ssa_loop_done): New functions.
(pass_loop, pass_loop_init, pass_loop_done): New passes.
* tree-ssa.c (kill_redundant_phi_nodes): Export.
* doc/invoke.texi (-ftree-loop-optimize): Document.
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.38
diff -c -3 -p -r1.38 common.opt
*** common.opt 29 Jun 2004 01:53:02 -0000 1.38
--- common.opt 29 Jun 2004 15:03:19 -0000
*************** ftree-fre
*** 777,782 ****
--- 777,786 ----
Common Report Var(flag_tree_fre)
Enable Full Redundancy Elimination (FRE) on trees
+ ftree-loop-optimize
+ Common Report Var(flag_tree_loop_optimize) Init(1)
+ Enable loop optimizations on tree level
+
ftree-points-to=
Common Joined RejectNegative
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.15
diff -c -3 -p -r2.15 tree-flow.h
*** tree-flow.h 29 Jun 2004 06:59:34 -0000 2.15
--- tree-flow.h 29 Jun 2004 15:03:19 -0000
*************** extern void verify_ssa (void);
*** 573,581 ****
extern void delete_tree_ssa (void);
extern void register_new_def (tree, varray_type *);
extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
/* In tree-into-ssa.c */
! extern void rewrite_into_ssa (void);
/* In tree-ssa-ccp.c */
bool fold_stmt (tree *);
--- 573,582 ----
extern void delete_tree_ssa (void);
extern void register_new_def (tree, varray_type *);
extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
+ extern void kill_redundant_phi_nodes (void);
/* In tree-into-ssa.c */
! extern void rewrite_into_ssa (bool);
/* In tree-ssa-ccp.c */
bool fold_stmt (tree *);
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.11
diff -c -3 -p -r2.11 tree-into-ssa.c
*** tree-into-ssa.c 17 Jun 2004 18:13:15 -0000 2.11
--- tree-into-ssa.c 29 Jun 2004 15:03:19 -0000
*************** invalidate_name_tags (bitmap vars_to_ren
*** 1081,1102 ****
(rewrite_stmt).
Steps 3 and 5 are done using the dominator tree walker
! (walk_dominator_tree). */
void
! rewrite_into_ssa (void)
{
bitmap *dfs;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
! unsigned int i;
timevar_push (TV_TREE_SSA_OTHER);
! /* Initialize the array of variables to rename. */
! if (vars_to_rename != NULL)
{
invalidate_name_tags (vars_to_rename);
/* Now remove all the existing PHI nodes (if any) for the variables
--- 1081,1118 ----
(rewrite_stmt).
Steps 3 and 5 are done using the dominator tree walker
! (walk_dominator_tree).
!
! ALL is true if all variables should be renamed (otherwise just those
! mentioned in vars_to_rename are taken into account). */
void
! rewrite_into_ssa (bool all)
{
bitmap *dfs;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
! bitmap old_vars_to_rename = vars_to_rename;
! unsigned i;
timevar_push (TV_TREE_SSA_OTHER);
! if (all)
! vars_to_rename = NULL;
! else
{
+ /* Initialize the array of variables to rename. */
+
+ if (vars_to_rename == NULL)
+ abort ();
+
+ if (bitmap_first_set_bit (vars_to_rename) < 0)
+ {
+ timevar_pop (TV_TREE_SSA_OTHER);
+ return;
+ }
+
invalidate_name_tags (vars_to_rename);
/* Now remove all the existing PHI nodes (if any) for the variables
*************** rewrite_into_ssa (void)
*** 1211,1224 ****
htab_delete (def_blocks);
timevar_pop (TV_TREE_SSA_OTHER);
}
struct tree_opt_pass pass_build_ssa =
{
"ssa", /* name */
NULL, /* gate */
! rewrite_into_ssa, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
--- 1227,1249 ----
htab_delete (def_blocks);
+ vars_to_rename = old_vars_to_rename;
timevar_pop (TV_TREE_SSA_OTHER);
}
+ /* Rewrites all variables into ssa. */
+
+ static void
+ rewrite_all_into_ssa (void)
+ {
+ rewrite_into_ssa (true);
+ }
+
struct tree_opt_pass pass_build_ssa =
{
"ssa", /* name */
NULL, /* gate */
! rewrite_all_into_ssa, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.21
diff -c -3 -p -r2.21 tree-optimize.c
*** tree-optimize.c 23 Jun 2004 20:12:42 -0000 2.21
--- tree-optimize.c 29 Jun 2004 15:03:19 -0000
*************** init_tree_optimization_passes (void)
*** 319,324 ****
--- 319,325 ----
NEXT_PASS (pass_fold_builtins);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
+ NEXT_PASS (pass_loop);
NEXT_PASS (DUP_PASS (pass_dominator));
NEXT_PASS (DUP_PASS (pass_redundant_phi));
NEXT_PASS (pass_cd_dce);
*************** init_tree_optimization_passes (void)
*** 333,338 ****
--- 334,344 ----
NEXT_PASS (pass_remove_useless_vars);
*p = NULL;
+ p = &pass_loop.sub;
+ NEXT_PASS (pass_loop_init);
+ NEXT_PASS (pass_loop_done);
+ *p = NULL;
+
#undef NEXT_PASS
#undef DUP_PASS
*************** execute_todo (unsigned int flags)
*** 349,357 ****
{
if (flags & TODO_rename_vars)
{
! if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa ();
! BITMAP_XFREE (vars_to_rename);
}
if ((flags & TODO_dump_func) && dump_file)
--- 355,362 ----
{
if (flags & TODO_rename_vars)
{
! rewrite_into_ssa (false);
! bitmap_clear (vars_to_rename);
}
if ((flags & TODO_dump_func) && dump_file)
*************** execute_one_pass (struct tree_opt_pass *
*** 407,416 ****
if (pass->tv_id)
timevar_push (pass->tv_id);
- /* If the pass is requesting ssa variable renaming, allocate the bitmap. */
- if (pass->todo_flags_finish & TODO_rename_vars)
- vars_to_rename = BITMAP_XMALLOC ();
-
/* Do it! */
if (pass->execute)
pass->execute ();
--- 412,417 ----
*************** tree_rest_of_compilation (tree fndecl, b
*** 509,514 ****
--- 510,518 ----
}
}
+ if (!vars_to_rename)
+ vars_to_rename = BITMAP_XMALLOC ();
+
/* If this is a nested function, protect the local variables in the stack
above us from being collected while we're compiling this function. */
if (nested_p)
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-pass.h
*** tree-pass.h 29 Jun 2004 01:53:03 -0000 2.3
--- tree-pass.h 29 Jun 2004 15:03:19 -0000
*************** extern struct tree_opt_pass pass_sra;
*** 106,111 ****
--- 106,113 ----
extern struct tree_opt_pass pass_tail_recursion;
extern struct tree_opt_pass pass_tail_calls;
extern struct tree_opt_pass pass_loop;
+ extern struct tree_opt_pass pass_loop_init;
+ extern struct tree_opt_pass pass_loop_done;
extern struct tree_opt_pass pass_ch;
extern struct tree_opt_pass pass_ccp;
extern struct tree_opt_pass pass_build_ssa;
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-dom.c
*** tree-ssa-dom.c 29 Jun 2004 06:59:35 -0000 2.18
--- tree-ssa-dom.c 29 Jun 2004 15:03:19 -0000
*************** tree_ssa_dominator_optimize (void)
*** 631,637 ****
if (cfg_altered
&& bitmap_first_set_bit (vars_to_rename) >= 0)
{
! rewrite_into_ssa ();
bitmap_clear (vars_to_rename);
/* The into SSA translation may have created new SSA_NAMES whic
--- 631,637 ----
if (cfg_altered
&& bitmap_first_set_bit (vars_to_rename) >= 0)
{
! rewrite_into_ssa (false);
bitmap_clear (vars_to_rename);
/* The into SSA translation may have created new SSA_NAMES whic
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop.c
*** tree-ssa-loop.c 17 Jun 2004 18:13:18 -0000 2.5
--- tree-ssa-loop.c 29 Jun 2004 15:03:19 -0000
*************** Software Foundation, 59 Temple Place - S
*** 38,43 ****
--- 38,145 ----
#include "flags.h"
#include "tree-inline.h"
+ /* The loop tree currently optimized. */
+
+ struct loops *current_loops;
+
+ /* Initializes the loop structures. DUMP is the file to that the details
+ about the analysis should be dumped. */
+
+ static struct loops *
+ tree_loop_optimizer_init (FILE *dump)
+ {
+ struct loops *loops = loop_optimizer_init (dump);
+
+ if (!loops)
+ return NULL;
+
+ /* Creation of preheaders may create redundant phi nodes if the loop is
+ entered by more than one edge, but the initial value of the induction
+ variable is the same on all of them. */
+ kill_redundant_phi_nodes ();
+ rewrite_into_ssa (false);
+ bitmap_clear (vars_to_rename);
+
+ return loops;
+ }
+
+ /* The loop superpass. */
+
+ static bool
+ gate_loop (void)
+ {
+ return flag_tree_loop_optimize != 0;
+ }
+
+ struct tree_opt_pass pass_loop =
+ {
+ "loop", /* name */
+ gate_loop, /* gate */
+ NULL, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_LOOP, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ TODO_ggc_collect, /* todo_flags_start */
+ TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
+ };
+
+ /* Loop optimizer initialization. */
+
+ static void
+ tree_ssa_loop_init (void)
+ {
+ current_loops = tree_loop_optimizer_init (dump_file);
+ }
+
+ struct tree_opt_pass pass_loop_init =
+ {
+ "loopinit", /* name */
+ NULL, /* gate */
+ tree_ssa_loop_init, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+ };
+
+ /* Loop optimizer finalization. */
+
+ static void
+ tree_ssa_loop_done (void)
+ {
+ if (!current_loops)
+ return;
+
+ loop_optimizer_finalize (current_loops,
+ (dump_flags & TDF_DETAILS ? dump_file : NULL));
+ current_loops = NULL;
+ cleanup_tree_cfg ();
+ }
+
+ struct tree_opt_pass pass_loop_done =
+ {
+ "loopdone", /* name */
+ NULL, /* gate */
+ tree_ssa_loop_done, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+ };
/* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
instructions should be duplicated, limit is decreased by the actual
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-ssa.c
*** tree-ssa.c 29 Jun 2004 01:53:03 -0000 2.16
--- tree-ssa.c 29 Jun 2004 15:03:19 -0000
*************** check_phi_redundancy (tree phi, tree *eq
*** 926,932 ****
The most important effect of this pass is to remove degenerate PHI
nodes created by removing unreachable code. */
! static void
kill_redundant_phi_nodes (void)
{
tree *eq_to;
--- 926,932 ----
The most important effect of this pass is to remove degenerate PHI
nodes created by removing unreachable code. */
! void
kill_redundant_phi_nodes (void)
{
tree *eq_to;
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.474
diff -c -3 -p -r1.474 invoke.texi
*** doc/invoke.texi 29 Jun 2004 01:53:04 -0000 1.474
--- doc/invoke.texi 29 Jun 2004 15:03:20 -0000
*************** in the following sections.
*** 312,318 ****
-fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol
-funroll-all-loops -funroll-loops -fpeel-loops @gol
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
! -ftree-pre -ftree-ccp -ftree-dce @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}
--- 312,318 ----
-fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol
-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-dominator-opts -ftree-dse -ftree-copyrename @gol
-ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre @gol
--param @var{name}=@var{value}
*************** effectivity of code motion optimizations
*** 4400,4405 ****
--- 4400,4409 ----
is enabled by default at -O and higher. It is not enabled for -Os, since it
usually increases code size.
+ @item -ftree-loop-optimize
+ Perform loop optimizations on trees. This flag is enabled by default at -O
+ and higher.
+
@item -ftree-sra
Perform scalar replacement of aggregates. This pass replaces structure
references with scalars to prevent committing structures to memory too