This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Loop header copying on trees
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 Feb 2004 14:58:17 +0100
- Subject: [tree-ssa] Loop header copying on trees
Hello,
this patch moves loop header copying from rtl to trees; this is
important since it should increase effectivity of code motion
transformations (and also because the rtl loop header copying code
is just ugly).
The loop header copying is done just after the first dominator
optimization pass, so that we do not miss opportunities for redundancy
elimination.
The impacts on performance of specint on x86_64 (base without the patch,
peak with):
Base Base Base Peak Peak Peak
Benchmarks Ref Time Run Time Ratio Ref Time Run Time Ratio
------------ -------- -------- -------- -------- -------- --------
164.gzip 1400 218 641 * 1400 215 651 *
175.vpr 1400 197 712 * 1400 196 715 *
176.gcc 1100 -- X 1100 -- X
181.mcf 1800 369 488 * 1800 358 503 *
186.crafty 1000 81.9 1221 * 1000 81.6 1225 *
197.parser 1800 348 518 * 1800 345 522 *
252.eon 1300 -- X 1300 -- X
253.perlbmk 1800 -- X 1800 -- X
254.gap 1100 157 701 * 1100 156 706 *
255.vortex 1900 175 1085 * 1900 174 1091 *
256.bzip2 1500 207 726 * 1500 209 718 *
300.twolf 3000 379 792 * 3000 385 780 *
Bootstrapped & regtested on i686.
Zdenek
* Makefile.in (tree-ssa-loop.o): Add tree-inline.h dependency.
* basic-block.h (struct reorder_block_def): Moved from cfglayout.h.
(alloc_rbi_pool, initialize_bb_rbi, free_rbi_pool): New.
* bb-reorder.c (copy_bb): Use cfghooks for bb duplication.
* cfg.c (rbi_pool): New variable.
(alloc_rbi_pool, free_rbi_pool, initialize_bb_rbi): New functions.
* cfghooks.c (can_duplicate_block_p, duplicate_block): New functions.
* cfghooks.h (struct cfg_hooks): Add can_duplicate_block_p and
duplicate_block hooks.
(can_duplicate_block_p, duplicate_block): Declare.
* cfglayout.c (cfg_layout_pool, cfg_layout_initialize_rbi): Removed.
(fixup_reorder_chain): Use initialize_bb_rbi.
(cfg_layout_can_duplicate_bb_p, cfg_layout_duplicate_bb): Hookized.
(cfg_layout_initialize): Use cfg.c rbi pool manipulation functions.
(can_copy_bbs_p, copy_bbs): Use cfghooks for bb duplication.
* cfglayout.h (typedef struct reorder_block_def): Moved to
basic_block.h.
(cfg_layout_can_duplicate_bb_p, cfg_layout_duplicate_bb): Declaration
removed.
* cfgrtl.c (cfg_layout_create_basic_block): Use initialize_bb_rbi.
(rtl_cfg_hooks, cfg_layout_rtl_cfg_hook): Fill in can_duplicate_block_p
and duplicate_block fields.
* common.opt (ftree-ch): Add.
* flags.h (flag_tree_ch): Declare.
* jump.c (next_nonnote_insn_in_loop, duplicate_loop_exit_test,
copy_loop_headers): Removed.
* loop-unswitch.c (unswitch_loop): Use cfghooks for bb duplication.
* opts.c (decode_options): Enable flag_tree_ch at -O1.
(common_handle_option): Handle -ftree_ch.
* rtl.h (copy_loop_headers): Declaration removed.
* timevar.def (TV_TREE_CH): New.
* toplev.c (flag_tree_ch): New.
(rest_of_compilation): Do not call copy_loop_headers.
* tracer.c (tail_duplicate): Use cfghooks for bb duplication.
* tree-cfg.c (build_tree_cfg): Call alloc_rbi_pool.
(create_bb): Call initialize_bb_rbi.
(delete_tree_cfg): Call free_rbi_pool.
(tree_duplicate_bb): Hookize.
(tree_can_duplicate_bb_p): New.
(tree_cfg_hooks): Fill in can_duplicate_block_p and duplicate_block
fields.
* tree-flow.h (tree_duplicate_bb): Declaration removed.
* tree-optimize.c (init_tree_optimization_passes): Add pass_ch.
* tree-pass.h (pass_ch): Declare.
* tree-ssa-loop.c: Include tree-inline.h.
(call_expr_p, should_duplicate_loop_header_p, mark_defs_for_rewrite,
duplicate_blocks, copy_loop_headers, gate_ch): New functions.
(pass_ch): New.
* doc/invoke.texi (-fdump-tree-ch, -ftree-ch): Document.
* testsuite/gcc.dg/tree-ssa/20030711-1.c: Update outcome.
* testsuite/gcc.dg/tree-ssa/20030714-2.c: Ditto.
* testsuite/gcc.dg/tree-ssa/20030807-3.c: Ditto.
* testsuite/gcc.dg/tree-ssa/copy-headers.c: New test.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.178
diff -c -3 -p -r1.903.2.178 Makefile.in
*** Makefile.in 13 Feb 2004 00:10:24 -0000 1.903.2.178
--- Makefile.in 13 Feb 2004 11:27:39 -0000
*************** tree-eh.o : tree-eh.c $(TREE_FLOW_H) $(C
*** 1586,1592 ****
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-ssa-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h flags.h \
function.h $(TIMEVAR_H) tree-alias-common.h convert.h $(TM_H) coretypes.h \
--- 1586,1592 ----
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-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h flags.h \
function.h $(TIMEVAR_H) tree-alias-common.h convert.h $(TM_H) coretypes.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.46
diff -c -3 -p -r1.153.2.46 basic-block.h
*** basic-block.h 13 Feb 2004 00:10:26 -0000 1.153.2.46
--- basic-block.h 13 Feb 2004 11:27:39 -0000
*************** struct basic_block_def GTY((chain_next (
*** 277,282 ****
--- 277,297 ----
typedef struct basic_block_def *basic_block;
+ /* Structure to hold information about the blocks during reordering. */
+ typedef struct reorder_block_def
+ {
+ rtx header;
+ rtx footer;
+ basic_block next;
+ basic_block original;
+ /* Used by loop copying. */
+ basic_block copy;
+ int duplicated;
+
+ /* These fields are used by bb-reorder pass. */
+ int visited;
+ } *reorder_block_def;
+
#define BB_FREQ_MAX 10000
/* Masks for basic_block.flags. */
*************** extern bool control_flow_insn_p (rtx);
*** 635,640 ****
--- 650,660 ----
/* In bb-reorder.c */
extern void reorder_basic_blocks (void);
+
+ /* In cfg.c */
+ extern void alloc_rbi_pool (void);
+ extern void initialize_bb_rbi (basic_block bb);
+ extern void free_rbi_pool (void);
/* In dominance.c */
Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.49.2.6
diff -c -3 -p -r1.49.2.6 bb-reorder.c
*** bb-reorder.c 3 Jan 2004 23:01:35 -0000 1.49.2.6
--- bb-reorder.c 13 Feb 2004 11:27:39 -0000
*************** copy_bb (basic_block old_bb, edge e, bas
*** 656,662 ****
{
basic_block new_bb;
! new_bb = cfg_layout_duplicate_bb (old_bb, e);
if (e->dest != new_bb)
abort ();
if (e->dest->rbi->visited)
--- 656,662 ----
{
basic_block new_bb;
! new_bb = duplicate_block (old_bb, e);
if (e->dest != new_bb)
abort ();
if (e->dest->rbi->visited)
*************** copy_bb_p (basic_block bb, int code_may_
*** 1010,1016 ****
return false;
if (!bb->pred || !bb->pred->pred_next)
return false;
! if (!cfg_layout_can_duplicate_bb_p (bb))
return false;
/* Avoid duplicating blocks which have many successors (PR/13430). */
--- 1010,1016 ----
return false;
if (!bb->pred || !bb->pred->pred_next)
return false;
! if (!can_duplicate_block_p (bb))
return false;
/* Avoid duplicating blocks which have many successors (PR/13430). */
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.34.2.23
diff -c -3 -p -r1.34.2.23 cfg.c
*** cfg.c 30 Jan 2004 13:13:37 -0000 1.34.2.23
--- cfg.c 13 Feb 2004 11:27:39 -0000
*************** varray_type basic_block_info;
*** 89,94 ****
--- 89,97 ----
/* The special entry and exit blocks. */
basic_block ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR;
+ /* Memory alloc pool for bb member rbi. */
+ alloc_pool rbi_pool;
+
void debug_flow_info (void);
static void free_edge (edge);
*************** alloc_block (void)
*** 179,184 ****
--- 182,216 ----
basic_block bb;
bb = ggc_alloc_cleared (sizeof (*bb));
return bb;
+ }
+
+ /* Create memory pool for rbi_pool. */
+
+ void
+ alloc_rbi_pool (void)
+ {
+ rbi_pool = create_alloc_pool ("rbi pool",
+ sizeof (struct reorder_block_def),
+ n_basic_blocks + 2);
+ }
+
+ /* Free rbi_pool. */
+
+ void
+ free_rbi_pool (void)
+ {
+ free_alloc_pool (rbi_pool);
+ }
+
+ /* Initialize rbi for the given basic block. */
+
+ void
+ initialize_bb_rbi (basic_block bb)
+ {
+ if (bb->rbi)
+ abort ();
+ bb->rbi = pool_alloc (rbi_pool);
+ memset (bb->rbi, 0, sizeof (struct reorder_block_def));
}
/* Link block B to chain after AFTER. */
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 cfghooks.c
*** cfghooks.c 13 Feb 2004 00:10:26 -0000 1.1.2.9
--- cfghooks.c 13 Feb 2004 11:27:39 -0000
*************** tidy_fallthru_edges (void)
*** 610,615 ****
--- 610,710 ----
}
}
+ /* Returns true if we can duplicate basic block BB. */
+
+ bool
+ can_duplicate_block_p (basic_block bb)
+ {
+ edge e;
+
+ if (!cfg_hooks->can_duplicate_block_p)
+ internal_error ("%s does not support can_duplicate_block_p.",
+ cfg_hooks->name);
+
+ if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
+ return false;
+
+ /* Duplicating fallthru block to exit would require adding a jump
+ and splitting the real last BB. */
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU)
+ return false;
+
+ return cfg_hooks->can_duplicate_block_p (bb);
+ }
+
+ /* Duplicates basic block BB and redirects edge E to it. Returns the
+ new basic block. */
+
+ basic_block
+ duplicate_block (basic_block bb, edge e)
+ {
+ edge s, n;
+ basic_block new_bb;
+ gcov_type new_count = e ? e->count : 0;
+
+ if (!cfg_hooks->duplicate_block)
+ internal_error ("%s does not support duplicate_block.",
+ cfg_hooks->name);
+
+ if (bb->count < new_count)
+ new_count = bb->count;
+ if (!bb->pred)
+ abort ();
+ #ifdef ENABLE_CHECKING
+ if (!can_duplicate_block_p (bb))
+ abort ();
+ #endif
+
+ new_bb = cfg_hooks->duplicate_block (bb);
+
+ new_bb->loop_depth = bb->loop_depth;
+ new_bb->flags = bb->flags;
+ for (s = bb->succ; s; s = s->succ_next)
+ {
+ /* Since we are creating edges from a new block to successors
+ of another block (which therefore are known to be disjoint), there
+ is no need to actually check for duplicated edges. */
+ n = unchecked_make_edge (new_bb, s->dest, s->flags);
+ n->probability = s->probability;
+ if (e && bb->count)
+ {
+ /* Take care for overflows! */
+ n->count = s->count * (new_count * 10000 / bb->count) / 10000;
+ s->count -= n->count;
+ }
+ else
+ n->count = s->count;
+ n->aux = s->aux;
+ }
+
+ if (e)
+ {
+ new_bb->count = new_count;
+ bb->count -= new_count;
+
+ new_bb->frequency = EDGE_FREQUENCY (e);
+ bb->frequency -= EDGE_FREQUENCY (e);
+
+ redirect_edge_and_branch_force (e, new_bb);
+
+ if (bb->count < 0)
+ bb->count = 0;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+ }
+ else
+ {
+ new_bb->count = bb->count;
+ new_bb->frequency = bb->frequency;
+ }
+
+ new_bb->rbi->original = bb;
+ bb->rbi->copy = new_bb;
+
+ return new_bb;
+ }
+
/* Return 1 if BB ends with a call, possibly followed by some
instructions that must stay with the call, 0 otherwise. */
Index: cfghooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.h,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 cfghooks.h
*** cfghooks.h 13 Feb 2004 00:10:26 -0000 1.1.2.10
--- cfghooks.h 13 Feb 2004 11:27:39 -0000
*************** struct cfg_hooks
*** 70,75 ****
--- 70,81 ----
PREDICTOR. */
bool (*predicted_by_p) (basic_block bb, enum br_predictor predictor);
+ /* Return true when block A can be duplicated. */
+ bool (*can_duplicate_block_p) (basic_block a);
+
+ /* Duplicate block A. */
+ basic_block (*duplicate_block) (basic_block a);
+
/* Higher level functions representable by primitive operations above if
we didn't have some oddities in RTL and Tree representations. */
basic_block (*split_edge) (edge);
*************** extern void tidy_fallthru_edge (edge);
*** 115,120 ****
--- 121,128 ----
extern void tidy_fallthru_edges (void);
extern void predict_edge (edge e, enum br_predictor predictor, int probability);
extern bool predicted_by_p (basic_block bb, enum br_predictor predictor);
+ extern bool can_duplicate_block_p (basic_block);
+ extern basic_block duplicate_block (basic_block, edge);
extern bool block_ends_with_call_p (basic_block bb);
extern bool block_ends_with_condjump_p (basic_block bb);
extern int flow_call_edges_add (sbitmap);
Index: cfglayout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.19.2.17
diff -c -3 -p -r1.19.2.17 cfglayout.c
*** cfglayout.c 14 Jan 2004 07:16:34 -0000 1.19.2.17
--- cfglayout.c 13 Feb 2004 11:27:39 -0000
*************** Software Foundation, 59 Temple Place - S
*** 40,47 ****
in this obstack, and all are freed at the end of the function. */
extern struct obstack flow_obstack;
- alloc_pool cfg_layout_pool;
-
/* Holds the interesting trailing notes for the function. */
rtx cfg_layout_function_footer, cfg_layout_function_header;
--- 40,45 ----
*************** fixup_reorder_chain (void)
*** 774,780 ****
nb = force_nonfallthru (e_fall);
if (nb)
{
! cfg_layout_initialize_rbi (nb);
nb->rbi->visited = 1;
nb->rbi->next = bb->rbi->next;
bb->rbi->next = nb;
--- 772,778 ----
nb = force_nonfallthru (e_fall);
if (nb)
{
! initialize_bb_rbi (nb);
nb->rbi->visited = 1;
nb->rbi->next = bb->rbi->next;
bb->rbi->next = nb;
*************** fixup_fallthru_exit_predecessor (void)
*** 889,908 ****
/* Return true in case it is possible to duplicate the basic block BB. */
bool
cfg_layout_can_duplicate_bb_p (basic_block bb)
{
- edge s;
-
- if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
- return false;
-
- /* Duplicating fallthru block to exit would require adding a jump
- and splitting the real last BB. */
- for (s = bb->succ; s; s = s->succ_next)
- if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
- return false;
-
/* Do not attempt to duplicate tablejumps, as we need to unshare
the dispatch table. This is difficult to do, as the instructions
computing jump destination may be hoisted outside the basic block. */
--- 887,896 ----
/* Return true in case it is possible to duplicate the basic block BB. */
+ extern bool cfg_layout_can_duplicate_bb_p (basic_block);
bool
cfg_layout_can_duplicate_bb_p (basic_block bb)
{
/* Do not attempt to duplicate tablejumps, as we need to unshare
the dispatch table. This is difficult to do, as the instructions
computing jump destination may be hoisted outside the basic block. */
*************** duplicate_insn_chain (rtx from, rtx to)
*** 1017,1042 ****
delete_insn (last);
return insn;
}
! /* Create a duplicate of the basic block BB and redirect edge E into it.
! If E is not specified, BB is just copied, but updating the frequencies
! etc. is left to the caller. */
basic_block
! cfg_layout_duplicate_bb (basic_block bb, edge e)
{
rtx insn;
- edge s, n;
basic_block new_bb;
- gcov_type new_count = e ? e->count : 0;
-
- if (bb->count < new_count)
- new_count = bb->count;
- if (!bb->pred)
- abort ();
- #ifdef ENABLE_CHECKING
- if (!cfg_layout_can_duplicate_bb_p (bb))
- abort ();
- #endif
insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
new_bb = create_basic_block (insn,
--- 1005,1018 ----
delete_insn (last);
return insn;
}
! /* Create a duplicate of the basic block BB. */
+ extern basic_block cfg_layout_duplicate_bb (basic_block);
basic_block
! cfg_layout_duplicate_bb (basic_block bb)
{
rtx insn;
basic_block new_bb;
insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
new_bb = create_basic_block (insn,
*************** cfg_layout_duplicate_bb (basic_block bb,
*** 1071,1132 ****
COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
}
- new_bb->loop_depth = bb->loop_depth;
- new_bb->flags = bb->flags;
- for (s = bb->succ; s; s = s->succ_next)
- {
- /* Since we are creating edges from a new block to successors
- of another block (which therefore are known to be disjoint), there
- is no need to actually check for duplicated edges. */
- n = unchecked_make_edge (new_bb, s->dest, s->flags);
- n->probability = s->probability;
- if (e && bb->count)
- {
- /* Take care for overflows! */
- n->count = s->count * (new_count * 10000 / bb->count) / 10000;
- s->count -= n->count;
- }
- else
- n->count = s->count;
- n->aux = s->aux;
- }
-
- if (e)
- {
- new_bb->count = new_count;
- bb->count -= new_count;
-
- new_bb->frequency = EDGE_FREQUENCY (e);
- bb->frequency -= EDGE_FREQUENCY (e);
-
- redirect_edge_and_branch_force (e, new_bb);
-
- if (bb->count < 0)
- bb->count = 0;
- if (bb->frequency < 0)
- bb->frequency = 0;
- }
- else
- {
- new_bb->count = bb->count;
- new_bb->frequency = bb->frequency;
- }
-
- new_bb->rbi->original = bb;
- bb->rbi->copy = new_bb;
-
return new_bb;
}
! void
! cfg_layout_initialize_rbi (basic_block bb)
! {
! if (bb->rbi)
! abort ();
! bb->rbi = pool_alloc (cfg_layout_pool);
! memset (bb->rbi, 0, sizeof (struct reorder_block_def));
! }
!
/* Main entry point to this module - initialize the datastructures for
CFG layout changes. It keeps LOOPS up-to-date if not null. */
--- 1047,1056 ----
COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
}
return new_bb;
}
!
/* Main entry point to this module - initialize the datastructures for
CFG layout changes. It keeps LOOPS up-to-date if not null. */
*************** cfg_layout_initialize (void)
*** 1137,1147 ****
/* Our algorithm depends on fact that there are now dead jumptables
around the code. */
! cfg_layout_pool =
! create_alloc_pool ("cfg layout pool", sizeof (struct reorder_block_def),
! n_basic_blocks + 2);
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
! cfg_layout_initialize_rbi (bb);
cfg_layout_rtl_register_cfg_hooks ();
--- 1061,1070 ----
/* Our algorithm depends on fact that there are now dead jumptables
around the code. */
! alloc_rbi_pool ();
!
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
! initialize_bb_rbi (bb);
cfg_layout_rtl_register_cfg_hooks ();
*************** cfg_layout_finalize (void)
*** 1198,1204 ****
verify_insn_chain ();
#endif
! free_alloc_pool (cfg_layout_pool);
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
bb->rbi = NULL;
--- 1121,1127 ----
verify_insn_chain ();
#endif
! free_rbi_pool ();
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
bb->rbi = NULL;
*************** can_copy_bbs_p (basic_block *bbs, unsign
*** 1231,1237 ****
goto end;
}
! if (!cfg_layout_can_duplicate_bb_p (bbs[i]))
{
ret = false;
break;
--- 1154,1160 ----
goto end;
}
! if (!can_duplicate_block_p (bbs[i]))
{
ret = false;
break;
*************** copy_bbs (basic_block *bbs, unsigned n,
*** 1274,1280 ****
{
/* Duplicate. */
bb = bbs[i];
! new_bb = new_bbs[i] = cfg_layout_duplicate_bb (bb, NULL);
bb->rbi->duplicated = 1;
/* Add to loop. */
add_bb_to_loop (new_bb, bb->loop_father->copy);
--- 1197,1203 ----
{
/* Duplicate. */
bb = bbs[i];
! new_bb = new_bbs[i] = duplicate_block (bb, NULL);
bb->rbi->duplicated = 1;
/* Add to loop. */
add_bb_to_loop (new_bb, bb->loop_father->copy);
Index: cfglayout.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.h,v
retrieving revision 1.3.2.3
diff -c -3 -p -r1.3.2.3 cfglayout.h
*** cfglayout.h 19 Dec 2003 01:01:47 -0000 1.3.2.3
--- cfglayout.h 13 Feb 2004 11:27:39 -0000
***************
*** 18,47 ****
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
- /* Structure to hold information about the blocks during reordering. */
- typedef struct reorder_block_def
- {
- rtx header;
- rtx footer;
- basic_block next;
- basic_block original;
- /* Used by loop copying. */
- basic_block copy;
- int duplicated;
-
- /* These fields are used by bb-reorder pass. */
- int visited;
- } *reorder_block_def;
-
extern rtx cfg_layout_function_footer;
extern void cfg_layout_initialize (void);
extern void cfg_layout_finalize (void);
- extern bool cfg_layout_can_duplicate_bb_p (basic_block);
- extern basic_block cfg_layout_duplicate_bb (basic_block, edge);
extern void insn_locators_initialize (void);
extern void reemit_insn_block_notes (void);
extern bool can_copy_bbs_p (basic_block *, unsigned);
extern void copy_bbs (basic_block *, unsigned, basic_block *,
edge *, unsigned, edge *, struct loop *);
- extern void cfg_layout_initialize_rbi (basic_block);
--- 18,29 ----
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.57.2.27
diff -c -3 -p -r1.57.2.27 cfgrtl.c
*** cfgrtl.c 13 Feb 2004 00:10:26 -0000 1.57.2.27
--- cfgrtl.c 13 Feb 2004 11:27:39 -0000
*************** cfg_layout_create_basic_block (void *hea
*** 353,359 ****
{
basic_block newbb = rtl_create_basic_block (head, end, after);
! cfg_layout_initialize_rbi (newbb);
return newbb;
}
--- 353,359 ----
{
basic_block newbb = rtl_create_basic_block (head, end, after);
! initialize_bb_rbi (newbb);
return newbb;
}
*************** struct cfg_hooks rtl_cfg_hooks = {
*** 2848,2853 ****
--- 2848,2855 ----
rtl_merge_blocks,
rtl_predict_edge,
rtl_predicted_by_p,
+ NULL, /* can_duplicate_block_p */
+ NULL, /* duplicate_block */
rtl_split_edge,
rtl_make_forwarder_block,
rtl_tidy_fallthru_edge,
*************** struct cfg_hooks rtl_cfg_hooks = {
*** 2860,2865 ****
--- 2862,2871 ----
basic block connected via fallthru edges does not have to be adjacent.
This representation will hopefully become the default one in future
version of the compiler. */
+
+ extern bool cfg_layout_can_duplicate_bb_p (basic_block);
+ extern basic_block cfg_layout_duplicate_bb (basic_block);
+
struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
"cfglayout mode",
rtl_verify_flow_info_1,
*************** struct cfg_hooks cfg_layout_rtl_cfg_hook
*** 2874,2879 ****
--- 2880,2887 ----
cfg_layout_merge_blocks,
rtl_predict_edge,
rtl_predicted_by_p,
+ cfg_layout_can_duplicate_bb_p,
+ cfg_layout_duplicate_bb,
cfg_layout_split_edge,
rtl_make_forwarder_block,
NULL,
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.14.2.19
diff -c -3 -p -r1.14.2.19 common.opt
*** common.opt 13 Feb 2004 00:10:27 -0000 1.14.2.19
--- common.opt 13 Feb 2004 11:27:39 -0000
*************** ftree-ccp
*** 711,716 ****
--- 711,720 ----
Common
Enable SSA-CCP optimization on trees
+ ftree-ch
+ Common
+ Enable loop header copying on trees
+
ftree-combine-temps
Common
Coalesce memory temporaries in the SSA->normal pass
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.45
diff -c -3 -p -r1.86.2.45 flags.h
*** flags.h 6 Feb 2004 23:20:05 -0000 1.86.2.45
--- flags.h 13 Feb 2004 11:27:39 -0000
*************** extern int flag_tree_ter;
*** 729,734 ****
--- 729,737 ----
/* Enable dominator optimizations while re-writing into SSA form. */
extern int flag_tree_dom;
+ /* Enable loop header copying on tree-ssa. */
+ extern int flag_tree_ch;
+
/* Enable loop optimization on tree-ssa. */
extern int flag_tree_loop;
Index: jump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/jump.c,v
retrieving revision 1.210.2.19
diff -c -3 -p -r1.210.2.19 jump.c
*** jump.c 4 Feb 2004 20:49:24 -0000 1.210.2.19
--- jump.c 13 Feb 2004 11:27:40 -0000
*************** Software Foundation, 59 Temple Place - S
*** 63,72 ****
or even change what is live at any point.
So perhaps let combiner do it. */
- static rtx next_nonnote_insn_in_loop (rtx);
static void init_label_info (rtx);
static void mark_all_labels (rtx);
- static int duplicate_loop_exit_test (rtx);
static void delete_computation (rtx);
static void redirect_exp_1 (rtx *, rtx, rtx, rtx);
static int redirect_exp (rtx, rtx, rtx);
--- 63,70 ----
*************** cleanup_barriers (void)
*** 122,176 ****
}
}
}
-
- /* Return the next insn after INSN that is not a NOTE and is in the loop,
- i.e. when there is no such INSN before NOTE_INSN_LOOP_END return NULL_RTX.
- This routine does not look inside SEQUENCEs. */
-
- static rtx
- next_nonnote_insn_in_loop (rtx insn)
- {
- while (insn)
- {
- insn = NEXT_INSN (insn);
- if (insn == 0 || GET_CODE (insn) != NOTE)
- break;
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
- return NULL_RTX;
- }
-
- return insn;
- }
-
- void
- copy_loop_headers (rtx f)
- {
- rtx insn, next;
- /* Now iterate optimizing jumps until nothing changes over one pass. */
- for (insn = f; insn; insn = next)
- {
- rtx temp, temp1;
-
- next = NEXT_INSN (insn);
-
- /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
- jump. Try to optimize by duplicating the loop exit test if so.
- This is only safe immediately after regscan, because it uses
- the values of regno_first_uid and regno_last_uid. */
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
- && (temp1 = next_nonnote_insn_in_loop (insn)) != 0
- && any_uncondjump_p (temp1) && onlyjump_p (temp1))
- {
- temp = PREV_INSN (insn);
- if (duplicate_loop_exit_test (insn))
- {
- next = NEXT_INSN (temp);
- }
- }
- }
- }
void
purge_line_number_notes (rtx f)
--- 120,125 ----
*************** mark_all_labels (rtx f)
*** 286,553 ****
}
}
}
- }
-
- /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
- jump. Assume that this unconditional jump is to the exit test code.
-
- Search the exit code for a conditional branch back to the first code
- label after LOOP_START.
-
- If such a conditional jump is found and the exit code is sufficiently
- simple, then make a copy of it before LOOP_START followed by a jump to
- fall-thru path of the exit code. Then delete the unconditional jump after
- LOOP_START.
-
- Note that if the loop exit code has multiple paths back to the start
- of the loop, then we only copy the first path. I.e. the fall-thru
- path of the exit code can still be part of the semantic loop.
-
- Return 1 if we made the change, else 0.
-
- This is only safe immediately after a regscan pass because it uses the
- values of regno_first_uid and regno_last_uid. */
-
- static int
- duplicate_loop_exit_test (rtx loop_start)
- {
- rtx insn, set, reg, p, link;
- rtx copy = 0, first_copy = 0;
- int num_insns = 0;
- rtx exitcode
- = NEXT_INSN (JUMP_LABEL (next_nonnote_insn_in_loop (loop_start)));
- rtx lastexit;
- int max_reg = max_reg_num ();
- rtx *reg_map = 0;
- rtx loop_pre_header_label;
-
- /* Scan the exit code. We do not perform this optimization if any insn:
-
- is a CALL_INSN
- is a CODE_LABEL
- has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
- is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
-
- We also do not do this if we find an insn with ASM_OPERANDS. While
- this restriction should not be necessary, copying an insn with
- ASM_OPERANDS can confuse asm_noperands in some cases.
-
- Also, don't do this if the exit code is more than 20 insns. */
-
- for (insn = exitcode;
- insn
- && ! (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
- insn = NEXT_INSN (insn))
- {
- switch (GET_CODE (insn))
- {
- case CODE_LABEL:
- case CALL_INSN:
- return 0;
- case NOTE:
-
- if (optimize < 2
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
- /* If we were to duplicate this code, we would not move
- the BLOCK notes, and so debugging the moved code would
- be difficult. Thus, we only move the code with -O2 or
- higher. */
- return 0;
-
- break;
- case JUMP_INSN:
- case INSN:
- if (++num_insns > 20
- || find_reg_note (insn, REG_RETVAL, NULL_RTX)
- || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
- return 0;
- break;
- default:
- break;
- }
-
- /* If this is a conditional jump back to the first label after
- LOOP_START, then we stop our search. */
- if (GET_CODE (insn) == JUMP_INSN
- && JUMP_LABEL (insn)
- && JUMP_LABEL (insn) == NEXT_INSN (NEXT_INSN (NEXT_INSN (loop_start)))
- && any_condjump_p (insn)
- && onlyjump_p (insn))
- {
- /* Advance INSN over the conditional jump since we want to
- copy the jump. */
- insn = NEXT_INSN (insn);
- break;
- }
- }
-
- /* Unless INSN is zero, we can do the optimization. */
- if (insn == 0)
- return 0;
-
- lastexit = insn;
-
- /* See if any insn sets a register only used in the loop exit code and
- not a user variable. If so, replace it with a new register. */
- for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == INSN
- && (set = single_set (insn)) != 0
- && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
- || (GET_CODE (reg) == SUBREG
- && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
- && REGNO (reg) >= FIRST_PSEUDO_REGISTER
- && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
- {
- for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
- if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
- break;
-
- if (p != lastexit)
- {
- /* We can do the replacement. Allocate reg_map if this is the
- first replacement we found. */
- if (reg_map == 0)
- reg_map = xcalloc (max_reg, sizeof (rtx));
-
- REG_LOOP_TEST_P (reg) = 1;
-
- reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
- }
- }
- loop_pre_header_label = gen_label_rtx ();
-
- /* Now copy each insn. */
- for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
- {
- switch (GET_CODE (insn))
- {
- case BARRIER:
- copy = emit_barrier_before (loop_start);
- break;
- case NOTE:
- /* Only copy line-number notes. */
- if (NOTE_LINE_NUMBER (insn) >= 0)
- {
- copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
- NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
- }
- break;
-
- case INSN:
- copy = emit_insn_before (copy_insn (PATTERN (insn)), loop_start);
- if (reg_map)
- replace_regs (PATTERN (copy), reg_map, max_reg, 1);
-
- mark_jump_label (PATTERN (copy), copy, 0);
- INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
-
- /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
- make them. */
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- if (REG_NOTE_KIND (link) != REG_LABEL)
- {
- if (GET_CODE (link) == EXPR_LIST)
- REG_NOTES (copy)
- = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
- XEXP (link, 0),
- REG_NOTES (copy)));
- else
- REG_NOTES (copy)
- = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
- XEXP (link, 0),
- REG_NOTES (copy)));
- }
-
- if (reg_map && REG_NOTES (copy))
- replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
- break;
-
- case JUMP_INSN:
- copy = emit_jump_insn_before (copy_insn (PATTERN (insn)),
- loop_start);
- INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
- if (reg_map)
- replace_regs (PATTERN (copy), reg_map, max_reg, 1);
- mark_jump_label (PATTERN (copy), copy, 0);
- if (REG_NOTES (insn))
- {
- REG_NOTES (copy) = copy_insn_1 (REG_NOTES (insn));
- if (reg_map)
- replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
- }
-
- /* Predict conditional jump that do make loop looping as taken.
- Other jumps are probably exit conditions, so predict
- them as untaken. */
- if (any_condjump_p (copy))
- {
- rtx label = JUMP_LABEL (copy);
- if (label)
- {
- /* The jump_insn after loop_start should be followed
- by barrier and loopback label. */
- if (prev_nonnote_insn (label)
- && (prev_nonnote_insn (prev_nonnote_insn (label))
- == next_nonnote_insn (loop_start)))
- {
- predict_insn_def (copy, PRED_LOOP_HEADER, TAKEN);
- /* To keep pre-header, we need to redirect all loop
- entrances before the LOOP_BEG note. */
- redirect_jump (copy, loop_pre_header_label, 0);
- }
- else
- predict_insn_def (copy, PRED_LOOP_HEADER, NOT_TAKEN);
- }
- }
- break;
-
- default:
- abort ();
- }
-
- /* Record the first insn we copied. We need it so that we can
- scan the copied insns for new pseudo registers. */
- if (! first_copy)
- first_copy = copy;
- }
-
- /* Now clean up by emitting a jump to the end label and deleting the jump
- at the start of the loop. */
- if (! copy || GET_CODE (copy) != BARRIER)
- {
- copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
- loop_start);
-
- /* Record the first insn we copied. We need it so that we can
- scan the copied insns for new pseudo registers. This may not
- be strictly necessary since we should have copied at least one
- insn above. But I am going to be safe. */
- if (! first_copy)
- first_copy = copy;
-
- mark_jump_label (PATTERN (copy), copy, 0);
- emit_barrier_before (loop_start);
- }
-
- emit_label_before (loop_pre_header_label, loop_start);
-
- /* Now scan from the first insn we copied to the last insn we copied
- (copy) for new pseudo registers. Do this after the code to jump to
- the end label since that might create a new pseudo too. */
- reg_scan_update (first_copy, copy, max_reg);
-
- /* Mark the exit code as the virtual top of the converted loop. */
- emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
-
- delete_related_insns (next_nonnote_insn (loop_start));
-
- /* Clean up. */
- if (reg_map)
- free (reg_map);
-
- return 1;
}
/* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, loop-end,
--- 235,240 ----
Index: loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unswitch.c,v
retrieving revision 1.2.2.8
diff -c -3 -p -r1.2.2.8 loop-unswitch.c
*** loop-unswitch.c 14 Jan 2004 07:16:35 -0000 1.2.2.8
--- loop-unswitch.c 13 Feb 2004 11:27:40 -0000
*************** unswitch_loop (struct loops *loops, stru
*** 346,352 ****
/* Will we be able to perform redirection? */
if (!any_condjump_p (BB_END (unswitch_on)))
return NULL;
! if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
return NULL;
entry = loop_preheader_edge (loop);
--- 346,352 ----
/* Will we be able to perform redirection? */
if (!any_condjump_p (BB_END (unswitch_on)))
return NULL;
! if (!can_duplicate_block_p (unswitch_on))
return NULL;
entry = loop_preheader_edge (loop);
*************** unswitch_loop (struct loops *loops, stru
*** 368,374 ****
/* Make a copy of the block containing the condition; we will use
it as switch to decide which loop we want to use. */
! switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
if (irred_flag)
{
switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
--- 368,374 ----
/* Make a copy of the block containing the condition; we will use
it as switch to decide which loop we want to use. */
! switch_bb = duplicate_block (unswitch_on, NULL);
if (irred_flag)
{
switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.31.2.27
diff -c -3 -p -r1.31.2.27 opts.c
*** opts.c 13 Feb 2004 00:10:27 -0000 1.31.2.27
--- opts.c 13 Feb 2004 11:27:40 -0000
*************** decode_options (unsigned int argc, const
*** 541,546 ****
--- 541,547 ----
flag_tree_ccp = 1;
flag_tree_dce = 1;
flag_tree_dom = 1;
+ flag_tree_ch = 1;
flag_tree_loop = 0;
flag_tree_pre = 1;
flag_tree_ter = 1;
*************** common_handle_option (size_t scode, cons
*** 1453,1458 ****
--- 1454,1463 ----
case OPT_ftree_dominator_opts:
flag_tree_dom = value;
+ break;
+
+ case OPT_ftree_ch:
+ flag_tree_ch = value;
break;
case OPT_ftree_loop_optimize:
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.362.2.33
diff -c -3 -p -r1.362.2.33 rtl.h
*** rtl.h 13 Feb 2004 00:10:25 -0000 1.362.2.33
--- rtl.h 13 Feb 2004 11:27:40 -0000
*************** extern enum rtx_code reversed_comparison
*** 2042,2048 ****
extern void delete_for_peephole (rtx, rtx);
extern int condjump_in_parallel_p (rtx);
extern void purge_line_number_notes (rtx);
- extern void copy_loop_headers (rtx);
/* In emit-rtl.c. */
extern int max_reg_num (void);
--- 2042,2047 ----
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.14.2.34
diff -c -3 -p -r1.14.2.34 timevar.def
*** timevar.def 11 Feb 2004 21:32:31 -0000 1.14.2.34
--- timevar.def 13 Feb 2004 11:27:40 -0000
*************** DEFTIMEVAR (TV_TREE_FORWPROP , "tre
*** 79,84 ****
--- 79,85 ----
DEFTIMEVAR (TV_TREE_DCE , "tree conservative DCE")
DEFTIMEVAR (TV_TREE_CD_DCE , "tree aggressive DCE")
DEFTIMEVAR (TV_TREE_LOOP , "tree loop optimization")
+ DEFTIMEVAR (TV_TREE_CH , "tree copy headers")
DEFTIMEVAR (TV_TREE_SSA_TO_NORMAL , "tree SSA to normal")
DEFTIMEVAR (TV_TREE_SSA_VERIFY , "tree SSA verifier")
DEFTIMEVAR (TV_TREE_STMT_VERIFY , "tree STMT verifier")
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.96
diff -c -3 -p -r1.654.2.96 toplev.c
*** toplev.c 13 Feb 2004 00:10:29 -0000 1.654.2.96
--- toplev.c 13 Feb 2004 11:27:40 -0000
*************** int flag_tree_ccp = 0;
*** 974,979 ****
--- 974,982 ----
/* Enable SSA-DCE on trees. */
int flag_tree_dce = 0;
+ /* Enable loop header copying on tree-ssa. */
+ int flag_tree_ch = 0;
+
/* Enable loop optimization on tree-ssa. */
int flag_tree_loop = 0;
*************** static const lang_independent_options f_
*** 1184,1189 ****
--- 1187,1193 ----
{ "tree-dominator-opts", &flag_tree_dom, 1 },
{ "tree-combine-temps", &flag_tree_combine_temps, 1 },
{ "tree-ter", &flag_tree_ter, 1 },
+ { "tree-ch", &flag_tree_ch, 1 },
{ "tree-loop-optimize", &flag_tree_loop, 1 }
};
*************** rest_of_compilation (tree decl)
*** 3305,3316 ****
create_loop_notes ();
- if (optimize)
- {
- free_bb_for_insn ();
- copy_loop_headers (insns);
- find_basic_blocks (insns, max_reg_num (), rtl_dump_file);
- }
purge_line_number_notes (insns);
timevar_pop (TV_JUMP);
--- 3309,3314 ----
Index: tracer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tracer.c,v
retrieving revision 1.2.6.10
diff -c -3 -p -r1.2.6.10 tracer.c
*** tracer.c 3 Jan 2004 23:02:02 -0000 1.2.6.10
--- tracer.c 13 Feb 2004 11:27:40 -0000
*************** tail_duplicate (void)
*** 271,277 ****
}
traced_insns += bb2->frequency * counts [bb2->index];
if (bb2->pred && bb2->pred->pred_next
! && cfg_layout_can_duplicate_bb_p (bb2))
{
edge e = bb2->pred;
basic_block old = bb2;
--- 271,277 ----
}
traced_insns += bb2->frequency * counts [bb2->index];
if (bb2->pred && bb2->pred->pred_next
! && can_duplicate_block_p (bb2))
{
edge e = bb2->pred;
basic_block old = bb2;
*************** tail_duplicate (void)
*** 279,285 ****
while (e->src != bb)
e = e->pred_next;
nduplicated += counts [bb2->index];
! bb2 = cfg_layout_duplicate_bb (bb2, e);
/* Reconsider the original copy of block we've duplicated.
Removing the most common predecessor may make it to be
--- 279,285 ----
while (e->src != bb)
e = e->pred_next;
nduplicated += counts [bb2->index];
! bb2 = duplicate_block (bb2, e);
/* Reconsider the original copy of block we've duplicated.
Removing the most common predecessor may make it to be
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.267
diff -c -3 -p -r1.1.4.267 tree-cfg.c
*** tree-cfg.c 13 Feb 2004 00:10:25 -0000 1.1.4.267
--- tree-cfg.c 13 Feb 2004 11:27:40 -0000
*************** build_tree_cfg (tree *tp)
*** 130,135 ****
--- 130,138 ----
/* Register specific tree functions. */
tree_register_cfg_hooks ();
+ /* Initialize rbi_pool. */
+ alloc_rbi_pool ();
+
/* Initialize the basic block array. */
init_flow ();
n_basic_blocks = 0;
*************** create_bb (void *h, void *e, basic_block
*** 393,398 ****
--- 396,402 ----
n_basic_blocks++;
last_basic_block++;
+ initialize_bb_rbi (bb);
return bb;
}
*************** tree_can_merge_blocks_p (basic_block a,
*** 770,776 ****
/* There may be no phi nodes at the start of b. Most of these degenerate
phi nodes should be cleaned up by kill_redundant_phi_nodes. */
-
if (phi_nodes (b))
return false;
--- 774,779 ----
*************** delete_tree_cfg (void)
*** 2359,2364 ****
--- 2362,2368 ----
free_basic_block_vars (0);
basic_block_info = NULL;
label_to_block_map = NULL;
+ free_rbi_pool ();
}
/* Return the first statement in basic block BB, stripped of any NOP
*************** tree_move_block_after (basic_block bb, b
*** 3672,3691 ****
return true;
}
! /* Create a duplicate of the basic block BB and redirect edge E into it. Does
! not work over ssa. */
! basic_block
! tree_duplicate_bb (basic_block bb, edge e)
{
- edge s, n;
basic_block new_bb;
block_stmt_iterator bsi, bsi_tgt;
! if (e->dest != bb)
! abort ();
!
! new_bb = create_empty_bb (e->src);
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
--- 3676,3697 ----
return true;
}
! /* Return true if basic_block can be duplicated. */
! static bool
! tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
! {
! return true;
! }
!
! /* Create a duplicate of the basic block BB. Does not work over ssa. */
! static basic_block
! tree_duplicate_bb (basic_block bb)
{
basic_block new_bb;
block_stmt_iterator bsi, bsi_tgt;
! new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
*************** tree_duplicate_bb (basic_block bb, edge
*** 3697,3714 ****
bsi_insert_after (&bsi_tgt, unshare_expr (stmt), BSI_NEW_STMT);
}
- new_bb->loop_depth = bb->loop_depth;
- new_bb->flags = bb->flags;
- for (s = bb->succ; s; s = s->succ_next)
- {
- /* Since we are creating edges from a new block to successors
- of another block (which therefore are known to be disjoint), there
- is no need to actually check for duplicated edges. */
- n = unchecked_make_edge (new_bb, s->dest, s->flags);
- }
-
- redirect_edge_and_branch_force (e, new_bb);
-
return new_bb;
}
--- 3703,3708 ----
*************** struct cfg_hooks tree_cfg_hooks = {
*** 4106,4111 ****
--- 4100,4107 ----
tree_merge_blocks, /* merge_blocks */
tree_predict_edge, /* predict_edge */
tree_predicted_by_p, /* predicted_by_p */
+ tree_can_duplicate_bb_p, /* can_duplicate_block_p */
+ tree_duplicate_bb, /* duplicate_block */
tree_split_edge, /* split_edge */
tree_make_forwarder_block, /* make_forward_block */
NULL, /* tidy_fallthru_edge */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.187
diff -c -3 -p -r1.1.4.187 tree-flow.h
*** tree-flow.h 13 Feb 2004 11:15:56 -0000 1.1.4.187
--- tree-flow.h 13 Feb 2004 11:27:40 -0000
*************** extern void clear_special_calls (void);
*** 479,487 ****
extern void compute_dominance_frontiers (bitmap *);
extern bool verify_stmt (tree);
extern void verify_stmts (void);
- extern basic_block tree_duplicate_bb (basic_block, edge);
extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
-
/* In tree-pretty-print.c. */
extern void dump_generic_bb (FILE *, basic_block, int, int);
--- 479,485 ----
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.121
diff -c -3 -p -r1.1.4.121 tree-optimize.c
*** tree-optimize.c 13 Feb 2004 11:15:57 -0000 1.1.4.121
--- tree-optimize.c 13 Feb 2004 11:27:40 -0000
*************** init_tree_optimization_passes (void)
*** 287,292 ****
--- 287,293 ----
NEXT_PASS (DUP_PASS (pass_dce));
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
+ NEXT_PASS (pass_ch);
NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_del_pta);
NEXT_PASS (pass_profile);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-pass.h,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-pass.h
*** tree-pass.h 13 Feb 2004 11:15:57 -0000 1.1.2.12
--- tree-pass.h 13 Feb 2004 11:27:40 -0000
*************** extern struct tree_opt_pass pass_sra;
*** 102,107 ****
--- 102,108 ----
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_ch;
extern struct tree_opt_pass pass_ccp;
extern struct tree_opt_pass pass_build_ssa;
extern struct tree_opt_pass pass_del_ssa;
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-ssa-loop.c
*** tree-ssa-loop.c 14 Jan 2004 07:16:36 -0000 1.1.2.6
--- tree-ssa-loop.c 13 Feb 2004 11:27:40 -0000
*************** Software Foundation, 59 Temple Place - S
*** 36,41 ****
--- 36,42 ----
#include "timevar.h"
#include "cfgloop.h"
#include "flags.h"
+ #include "tree-inline.h"
/* The main entry into loop optimization pass. PHASE indicates which dump file
*************** struct tree_opt_pass pass_loop =
*** 76,79 ****
--- 77,367 ----
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ };
+
+ /* Checks whether the STMT is a call, and if so, returns the call_expr. */
+
+ static tree
+ call_expr_p (tree stmt)
+ {
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ stmt = TREE_OPERAND (stmt, 1);
+
+ return TREE_CODE (stmt) == CALL_EXPR ? stmt : NULL_TREE;
+ }
+
+ /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
+ instructions should be duplicated, limit is decreased by the actual
+ amount. */
+
+ static bool
+ should_duplicate_loop_header_p (basic_block header, struct loop *loop,
+ int *limit)
+ {
+ block_stmt_iterator bsi;
+ tree last;
+
+ /* Do not copy one block more than once (we do not really want to do
+ loop peeling here). */
+ if (header->aux)
+ return false;
+
+ if (!header->succ)
+ abort ();
+ if (!header->succ->succ_next)
+ return false;
+ if (header->succ->succ_next->succ_next)
+ return false;
+ if (flow_bb_inside_loop_p (loop, header->succ->dest)
+ && flow_bb_inside_loop_p (loop, header->succ->succ_next->dest))
+ return false;
+
+ /* If this is not the original loop header, we want it to have just
+ one predecessor in order to match the && pattern. */
+ if (header != loop->header
+ && header->pred->pred_next)
+ return false;
+
+ last = last_stmt (header);
+ if (TREE_CODE (last) != COND_EXPR)
+ return false;
+
+ /* Aproximately copy the conditions that used to be used in jump.c --
+ at most 20 insns and no calls. */
+ for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ last = bsi_stmt (bsi);
+
+ if (TREE_CODE (last) == LABEL_EXPR)
+ continue;
+
+ if (call_expr_p (last))
+ return false;
+
+ *limit -= estimate_num_insns (last);
+ if (*limit < 0)
+ return false;
+ }
+
+ return true;
+ }
+
+ /* Marks variables defined in basic block BB for rewriting. */
+
+ static void
+ mark_defs_for_rewrite (basic_block bb)
+ {
+ tree stmt, var;
+ block_stmt_iterator bsi;
+ stmt_ann_t ann;
+ def_optype defs;
+ vdef_optype vdefs;
+ vuse_optype vuses;
+ unsigned i;
+
+ for (stmt = phi_nodes (bb); stmt; stmt = TREE_CHAIN (stmt))
+ {
+ var = SSA_NAME_VAR (PHI_RESULT (stmt));
+ bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ }
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ defs = DEF_OPS (ann);
+ for (i = 0; i < NUM_DEFS (defs); i++)
+ {
+ var = SSA_NAME_VAR (DEF_OP (defs, i));
+ bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ }
+
+ vdefs = VDEF_OPS (ann);
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ {
+ var = SSA_NAME_VAR (VDEF_RESULT (vdefs, i));
+ bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ }
+
+ /* We also need to rewrite vuses, since we will copy the statements
+ and the ssa versions could not be recovered in the copy. */
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ {
+ var = SSA_NAME_VAR (VUSE_OP (vuses, i));
+ bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ }
+ }
+ }
+
+ /* Duplicates destinations of edges in BBS_TO_DUPLICATE. */
+
+ static void
+ duplicate_blocks (varray_type bbs_to_duplicate)
+ {
+ unsigned i;
+ edge preheader_edge, e, e1;
+ basic_block header, new_header;
+ tree phi;
+ size_t old_num_referenced_vars = num_referenced_vars;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
+ {
+ preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
+ header = preheader_edge->dest;
+
+ mark_defs_for_rewrite (header);
+ }
+
+ rewrite_vars_out_of_ssa (vars_to_rename);
+
+ for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
+ {
+ bitmap_set_bit (vars_to_rename, i);
+ var_ann (referenced_var (i))->out_of_ssa_tag = 0;
+ }
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
+ {
+ preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
+ header = preheader_edge->dest;
+
+ /* We might have split the edge into the loop header when we have
+ eliminated the phi nodes, so find the edge to that we want to
+ copy the header. */
+ while (!header->aux)
+ {
+ preheader_edge = header->succ;
+ header = preheader_edge->dest;
+ }
+ header->aux = NULL;
+
+ new_header = duplicate_block (header, preheader_edge);
+
+ /* Add the phi arguments to the outgoing edges. */
+ for (e = header->succ; e; e = e->succ_next)
+ {
+ for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
+ continue;
+
+ for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ {
+ tree def = phi_element_for_edge (phi, e)->def;
+ add_phi_arg (&phi, def, e1);
+ }
+ }
+ }
+ }
+
+ /* For all loops, copy the condition at the end of the loop body in front
+ of the loop. */
+
+ static void
+ copy_loop_headers (void)
+ {
+ struct loops *loops;
+ unsigned i;
+ struct loop *loop;
+ basic_block header;
+ edge preheader_edge;
+ varray_type bbs_to_duplicate = NULL;
+
+ loops = loop_optimizer_init (tree_dump_file);
+ if (!loops)
+ return;
+
+ /* We are not going to need or update dominators. */
+ free_dominance_info (CDI_DOMINATORS);
+
+ create_preheaders (loops, CP_SIMPLE_PREHEADERS);
+
+ /* We do not try to keep the information about irreductible regions
+ up-to-date. */
+ loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_structure (loops);
+ #endif
+
+ for (i = 1; i < loops->num; i++)
+ {
+ /* Copy at most 20 insns. */
+ int limit = 20;
+
+ loop = loops->parray[i];
+ preheader_edge = loop_preheader_edge (loop);
+ header = preheader_edge->dest;
+
+ /* Iterate the header copying up to limit; this takes care of the cases
+ like while (a && b) {...}, where we want to have both of the conditions
+ copied. TODO -- handle while (a || b) - like cases, by not requiring
+ the header to have just a single successor and copying up to
+ postdominator.
+
+ We do not really copy the blocks immediatelly, so that we do not have
+ to worry about updating loop structures, and also so that we do not
+ have to rewrite variables out of and into ssa form for each block.
+ Instead we just record the block into worklist and duplicate all of
+ them at once. */
+ while (should_duplicate_loop_header_p (header, loop, &limit))
+ {
+ if (!bbs_to_duplicate)
+ VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
+ "bbs_to_duplicate");
+ VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
+ header->aux = &header->aux;
+
+ if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
+ fprintf (tree_dump_file,
+ "Scheduled basic block %d for duplication.\n",
+ header->index);
+
+ /* Find a successor of header that is inside a loop; i.e. the new
+ header after the condition is copied. */
+ if (flow_bb_inside_loop_p (loop, header->succ->dest))
+ preheader_edge = header->succ;
+ else
+ preheader_edge = header->succ->succ_next;
+ header = preheader_edge->dest;
+ }
+ }
+
+ loop_optimizer_finalize (loops, NULL);
+
+ if (bbs_to_duplicate)
+ {
+ duplicate_blocks (bbs_to_duplicate);
+ VARRAY_FREE (bbs_to_duplicate);
+ }
+
+ /* Run cleanup_tree_cfg here regardless of whether we have done anything, so
+ that we cleanup the blocks created in order to get the loops into a
+ canonical shape. */
+ cleanup_tree_cfg ();
+ }
+
+ static bool
+ gate_ch (void)
+ {
+ return flag_tree_ch != 0;
+ }
+
+ struct tree_opt_pass pass_ch =
+ {
+ "ch", /* name */
+ gate_ch, /* gate */
+ copy_loop_headers, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_CH, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ (TODO_rename_vars
+ | TODO_dump_func
+ | TODO_verify_ssa) /* todo_flags_finish */
};
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.152.2.72
diff -c -3 -p -r1.152.2.72 invoke.texi
*** doc/invoke.texi 13 Feb 2004 00:10:30 -0000 1.152.2.72
--- doc/invoke.texi 13 Feb 2004 11:27:40 -0000
*************** in the following sections.
*** 250,255 ****
--- 250,256 ----
-fdump-tree-optimized@r{[}-@var{n}@r{]} @gol
-fdump-tree-inlined@r{[}-@var{n}@r{]} @gol
-fdump-tree-cfg -fdump-tree-dot -fdump-tree-alias @gol
+ -fdump-tree-ch @gol
-fdump-tree-ssa@r{[}-@var{n}@r{]} -fdump-tree-pre@r{[}-@var{n}@r{]} @gol
-fdump-tree-ccp@r{[}-@var{n}@r{]} -fdump-tree-dce@r{[}-@var{n}@r{]} @gol
-fdump-tree-gimple@r{[}-raw@r{]} -fdump-tree-mudflap@r{[}-@var{n}@r{]} @gol
*************** in the following sections.
*** 307,313 ****
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
-ftree-pre -ftree-ccp -ftree-dce -ftree-copyprop @gol
-ftree-dominator-opts @gol
! -ftree-loop-optimize -ftree-sra @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
--- 308,314 ----
-funswitch-loops -fold-unroll-loops -fold-unroll-all-loops @gol
-ftree-pre -ftree-ccp -ftree-dce -ftree-copyprop @gol
-ftree-dominator-opts @gol
! -ftree-ch -ftree-loop-optimize -ftree-sra @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
*************** made by appending @file{.cfg} to the sou
*** 3489,3494 ****
--- 3490,3500 ----
Dump a dot language representation of the control flow graph to a file. The
file name is made by appending @file{.dot} to the source file name.
+ @item ch
+ @opindex fdump-tree-ch
+ Dump each function after copying loop headers. The file name is made by
+ appending @file{.ch} to the source file name.
+
@item ssa
@opindex fdump-tree-ssa
Dump SSA related information to a file. The file name is made by appending
*************** default at -O and higher.
*** 4303,4308 ****
--- 4309,4318 ----
@item -ftree-dominator-opts
Perform dead code elimination (DCE) on trees. This flag is enabled by
+ default at -O and higher.
+
+ @item -ftree-ch
+ Perform loop header copying on trees. This flag is enabled by
default at -O and higher.
@item -ftree-loop-optimize
Index: testsuite/gcc.dg/tree-ssa/20030711-1.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/20030711-1.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 20030711-1.c
*** testsuite/gcc.dg/tree-ssa/20030711-1.c 7 Jan 2004 23:44:17 -0000 1.1.2.5
--- testsuite/gcc.dg/tree-ssa/20030711-1.c 13 Feb 2004 11:27:41 -0000
*************** record_component_aliases (type)
*** 39,53 ****
}
}
! /* The call to blah can not be eliminated.
/* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "dom3" } } */
! /* There should be three IF conditionals. */
! /* { dg-final { scan-tree-dump-times "if " 3 "dom3"} } */
/* There should be two loads of type.binfo. */
/* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "dom3"} } */
! /* There should be three loads of vec.length. */
! /* { dg-final { scan-tree-dump-times "vec.length" 3 "dom3"} } */
--- 39,53 ----
}
}
! /* The call to blah can not be eliminated. */
/* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "dom3" } } */
! /* There should be four IF conditionals. */
! /* { dg-final { scan-tree-dump-times "if " 4 "dom3"} } */
/* There should be two loads of type.binfo. */
/* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "dom3"} } */
! /* There should be four loads of vec.length. */
! /* { dg-final { scan-tree-dump-times "vec.length" 4 "dom3"} } */
Index: testsuite/gcc.dg/tree-ssa/20030714-2.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/20030714-2.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 20030714-2.c
*** testsuite/gcc.dg/tree-ssa/20030714-2.c 7 Jan 2004 23:44:17 -0000 1.1.2.3
--- testsuite/gcc.dg/tree-ssa/20030714-2.c 13 Feb 2004 11:27:41 -0000
*************** get_alias_set (t)
*** 32,39 ****
}
}
! /* There should be exactly three IF conditionals if we thread jumps
properly. */
! /* { dg-final { scan-tree-dump-times "if " 3 "dom3"} } */
--- 32,39 ----
}
}
! /* There should be exactly four IF conditionals if we thread jumps
properly. */
! /* { dg-final { scan-tree-dump-times "if " 4 "dom3"} } */
Index: testsuite/gcc.dg/tree-ssa/20030807-3.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/20030807-3.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 20030807-3.c
*** testsuite/gcc.dg/tree-ssa/20030807-3.c 7 Jan 2004 23:44:17 -0000 1.1.2.5
--- testsuite/gcc.dg/tree-ssa/20030807-3.c 13 Feb 2004 11:27:41 -0000
*************** cpp_parse_escape (pstr, limit, wide)
*** 21,27 ****
foo();
}
! /* There should be precisely two IF statements. If there is
more than two, then the dominator optimizations failed. */
! /* { dg-final { scan-tree-dump-times "if " 2 "dom3"} } */
--- 21,27 ----
foo();
}
! /* There should be precisely three IF statements. If there is
more than two, then the dominator optimizations failed. */
! /* { dg-final { scan-tree-dump-times "if " 3 "dom3"} } */
Index: testsuite/gcc.dg/tree-ssa/copy-headers.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/copy-headers.c
diff -N testsuite/gcc.dg/tree-ssa/copy-headers.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/copy-headers.c 13 Feb 2004 11:27:41 -0000
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-ch-details" } */
+
+ extern void foo (int);
+ extern int bar (void);
+
+ void bla (void)
+ {
+ int i;
+
+ for (i = bar (); i < 100; i++)
+ foo (i);
+ }
+
+ /* There should be a header scheduled for duplication. */
+ /* { dg-final { scan-tree-dump-times "Scheduled" 1 "ch"} } */