This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Loop optimizer bits
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: pop at gauvain dot u-strasbg dot fr
- Date: Sat, 3 Jan 2004 21:39:29 +0100
- Subject: [lno] Loop optimizer bits
Hello,
this patch adds a few bits on the path to getting rid of the old rtl
level loop optimizer.
It adds:
1) the loop header copying -- posted previously as
http://gcc.gnu.org/ml/gcc-patches/2003-12/msg00824.html.
There is a problem with this pass since it breaks many of the scev
tests (they are puzzled by the condition that is copied out of the
loop unless it is optimized out, and the value range propagation
inside dominator opts quite often is not sufficient for this. I
assume that elimination of such conditions could be added to the scev code
relatively easily).
So it is disabled by default for now, although I have also removed
the rtl counterpart; for any performance tests I strongly recommend
to enable it, since the impacts are often significant.
2) A simple loop invariant motion (disabled by default, since it is
a work in progress).
3) Some cleanups of the loop structure related code.
4) A few bugfixes neccesary to make the whole thing bootstrap.
Bootstrapped and regtested on i686.
Zdenek
* cfghooks.h (struct cfg_hooks): New fields split_block_after_labels
and move_block_after, type of cfgh_make_forwarder_block field changed.
(HEADER_BLOCK, LATCH_EDGE): Moved to cfgloop.c.
(split_block_after_labels, move_block_after): New macros.
(make_forwarder_block): Changed.
* cfgloop.c (HEADER_BLOCK, LATCH_EDGE): Moved from cfghooks.h.
(update_latch_info, mfb_keep_just, mfb_keep_nonlatch,
fill_sons_in_loop): New functions.
(canonicalize_loop_headers): Changed due to changes in
make_forwarder_block.
* cfgloopmanip.c (split_loop_bb): Don't update dominators.
(create_preheader): Use make_forwarder_block.
(mfb_keep_just, mfb_update_loops): New.
* cfgrtl.c (rtl_split_block_after_labels): New.
(redirect_edge_with_latch_update): Removed.
(rtl_make_forwarder_block): New sematics.
(rtl_split_block): Update dominators.
(rtl_cfg_hooks, cfg_layout_rtl_cfg_hooks):
Add rtl_split_block_after_labels.
* tree-cfg.c (tree_make_forwarder_block): Changed semantics.
(create_blocks_annotations): Removed.
(build_tree_cfg): Don't call create_blocks_annotations.
(create_bb): Create annotations for a new block.
(tree_split_edge): Don't call create_block_annotation.
Update irreducible loop information.
(tree_loop_optimizer_finalize): Add loop structure check.
(tree_redirect_edge_and_branch_1): Return the original edge if
no redirecting is neccessary.
(tree_split_block): Make the semantics same as for rtl_split_block.
(tree_split_block_after_labels, tree_move_block_after): New.
(tree_cfg_hooks): Add tree_split_block_after_labels and
tree_move_block_after.
* cfgloopanal.c (mark_irreducible_loops): Fix.
* loop-unswitch.c (unswitch_loop): Fix.
* Makefile.in (tree-ssa-loop.o): Add cfgloop.h and tree-inline.h
dependency.
* jump.c (next_nonnote_insn_in_loop, duplicate_loop_exit_test,
copy_loop_headers): Removed.
* rtl.h (copy_loop_headers): Declaration removed.
* toplev.c (rest_of_compilation): Do not call loop header copying.
* tree-dump.c (dump_files): Add .ch dump.
* tree-flow.h (tree_duplicate_bb, copy_loop_headers): Declare.
* tree-optimize.c (optimize_function_tree): Add loop header copying
pass.
* tree-ssa-loop.c: Include cfgloop.h and tree-inline.h.
(dump_file, dump_flags): Renamed to loop_dump_file and
loop_dump_flags.
(call_expr_p, should_duplicate_loop_header_p, copy_loop_headers):
New.
* tree.h (enum tree_dump_index): Add ch dump.
* doc/invoke.texi (-fdump-tree-copy-headers): Document.
* testsuite/gcc.dg/tree-ssa/20030711-1.c: Update test outcome.
* testsuite/gcc.dg/tree-ssa/20030714-2.c: Ditto.
* testsuite/gcc.dg/tree-ssa/copy-headers.c: New test.
* tree-cfg.c (tree_duplicate_bb): New function.
* tree-ssa-loop-im.c: New file.
* Makefile.in (tree-ssa-loop-im.o): Add.
* params.def (PARAM_LIM_EXPENSIVE): New parameter.
* tree-dump.c (dump_files): Move .loop dump.
* cfgloop.h (superloop_at_depth, get_loop_body_in_dom_order): Declare.
(loop_dump_file, loop_dump_flags): Declare variables.
* cfgloop.c (superloop_at_depth, get_loop_body_in_dom_order): New
functions.
* tree-flow.h (struct stmt_ann_d): Add aux field.
(bsi_commit_edge_inserts): Declaration changed.
(tree_ssa_lim): Declare.
* tree-mudflap.c (mf_xform_derefs_1): Use in_array_bounds_p.
* tree-optimize.c (optimize_function_tree): Move loop optimization
pass.
* tree-sra.c (scalarize_structures): Modified due to
bsi_commit_edge_inserts change.
* tree-ssa-loop.c (tree_ssa_loop_opt): Call tree_ssa_lim.
* tree-ssa.c (rewrite_trees, rewrite_vars_out_of_ssa): Modified due to
bsi_commit_edge_inserts change.
* tree.c (in_array_bounds_p): New function.
* tree.h (in_array_bounds_p): Declare.
(enum tree_dump_index): Move loop dump.
* tree-cfg.c (bsi_commit_edge_inserts): Don't take update_annotations
argument.
* tree-ssa.c (rewrite_into_ssa, rewrite_out_of_ssa): Ensure that the
closed files are not used.
* tree-tailcall.c (find_tail_calls, eliminate_tail_call): Update
phi nodes for vdefs of the eliminated call.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.2
diff -c -3 -p -r1.903.2.158.2.2 Makefile.in
*** Makefile.in 1 Jan 2004 20:16:24 -0000 1.903.2.158.2.2
--- Makefile.in 3 Jan 2004 20:16:58 -0000
*************** OBJS-common = \
*** 878,884 ****
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
tree-ssa-pre.o tree-ssa-live.o tree-must-alias.o tree-ssa-operands.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-vectorizer.o tree-ssa-loop.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 \
--- 878,885 ----
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
tree-ssa-pre.o tree-ssa-live.o tree-must-alias.o tree-ssa-operands.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-vectorizer.o \
! tree-ssa-loop.o tree-ssa-loop-im.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
*** 1594,1600 ****
$(RTL_H) $(TREE_H) $(TM_H) flags.h function.h except.h langhooks.h \
$(GGC_H) gt-tree-eh.h
tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
! $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
--- 1595,1604 ----
$(RTL_H) $(TREE_H) $(TM_H) flags.h function.h except.h langhooks.h \
$(GGC_H) gt-tree-eh.h
tree-ssa-loop.o : tree-ssa-loop.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)
! tree-ssa-loop-im.o : tree-ssa-loop-im.c $(TREE_FLOW_H) $(CONFIG_H) \
! $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h domwalk.h $(PARAMS_H)\
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
Index: cfghooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.h,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 cfghooks.h
*** cfghooks.h 3 Nov 2003 17:47:35 -0000 1.1.2.6
--- cfghooks.h 3 Jan 2004 20:16:58 -0000
*************** struct cfg_hooks
*** 51,56 ****
--- 51,62 ----
/* Split basic block B after specified instruction I. */
edge (*split_block) (basic_block b, void * i);
+ /* Split basic block B immediatelly after labels. */
+ edge (*split_block_after_labels) (basic_block b);
+
+ /* Move block B immediatelly after block A. */
+ void (*move_block_after) (basic_block b, basic_block a);
+
/* Return true when blocks A and B can be merged into single basic block. */
bool (*can_merge_blocks_p) (basic_block a, basic_block b);
*************** struct cfg_hooks
*** 60,84 ****
/* Higher level functions representable by primitive operations above if
we didn't have some oddities in RTL and Tree representations. */
basic_block (*cfgh_split_edge) (edge);
! basic_block (*cfgh_make_forwarder_block) (basic_block, int, int, edge, int);
struct loops *(*cfgh_loop_optimizer_init) (FILE *);
void (*cfgh_loop_optimizer_finalize) (struct loops *, FILE *);
};
#define redirect_edge_and_branch(e,b) cfg_hooks->redirect_edge_and_branch (e,b)
#define redirect_edge_and_branch_force(e,b) cfg_hooks->redirect_edge_and_branch_force (e,b)
! #define split_block(e,i) cfg_hooks->split_block (e,i)
#define delete_basic_block(b) cfg_hooks->delete_basic_block (b)
#define split_edge(e) cfg_hooks->cfgh_split_edge (e)
#define create_basic_block(h,e,a) cfg_hooks->create_basic_block (h,e,a)
#define can_merge_blocks_p(a,b) cfg_hooks->can_merge_blocks_p (a,b)
#define merge_blocks(a,b) cfg_hooks->merge_blocks (a,b)
! #define make_forwarder_block(a, b, c, d, e) cfg_hooks->cfgh_make_forwarder_block (a, b, c, d, e)
#define loop_optimizer_init(a) cfg_hooks->cfgh_loop_optimizer_init (a)
#define loop_optimizer_finalize(a, b) cfg_hooks->cfgh_loop_optimizer_finalize (a, b)
-
- #define HEADER_BLOCK(B) (* (int *) (B)->aux)
- #define LATCH_EDGE(E) (*(int *) (E)->aux)
/* Hooks containers. */
extern struct cfg_hooks tree_cfg_hooks;
--- 66,90 ----
/* Higher level functions representable by primitive operations above if
we didn't have some oddities in RTL and Tree representations. */
basic_block (*cfgh_split_edge) (edge);
! edge (*cfgh_make_forwarder_block) (basic_block, bool (*)(edge),
! void (*) (basic_block));
struct loops *(*cfgh_loop_optimizer_init) (FILE *);
void (*cfgh_loop_optimizer_finalize) (struct loops *, FILE *);
};
#define redirect_edge_and_branch(e,b) cfg_hooks->redirect_edge_and_branch (e,b)
#define redirect_edge_and_branch_force(e,b) cfg_hooks->redirect_edge_and_branch_force (e,b)
! #define split_block(b,i) cfg_hooks->split_block (b,i)
! #define split_block_after_labels(b) cfg_hooks->split_block_after_labels (b)
! #define move_block_after(b, a) cfg_hooks->move_block_after (b, a)
#define delete_basic_block(b) cfg_hooks->delete_basic_block (b)
#define split_edge(e) cfg_hooks->cfgh_split_edge (e)
#define create_basic_block(h,e,a) cfg_hooks->create_basic_block (h,e,a)
#define can_merge_blocks_p(a,b) cfg_hooks->can_merge_blocks_p (a,b)
#define merge_blocks(a,b) cfg_hooks->merge_blocks (a,b)
! #define make_forwarder_block(a, b, c) cfg_hooks->cfgh_make_forwarder_block (a, b, c)
#define loop_optimizer_init(a) cfg_hooks->cfgh_loop_optimizer_init (a)
#define loop_optimizer_finalize(a, b) cfg_hooks->cfgh_loop_optimizer_finalize (a, b)
/* Hooks containers. */
extern struct cfg_hooks tree_cfg_hooks;
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.14.2.12
diff -c -3 -p -r1.14.2.12 cfgloop.c
*** cfgloop.c 19 Dec 2003 01:01:47 -0000 1.14.2.12
--- cfgloop.c 3 Jan 2004 20:16:58 -0000
*************** Software Foundation, 59 Temple Place - S
*** 35,40 ****
--- 35,43 ----
considered to belong to inner loop with same header. */
#define HEAVY_EDGE_RATIO 8
+ #define HEADER_BLOCK(B) (* (int *) (B)->aux)
+ #define LATCH_EDGE(E) (*(int *) (E)->aux)
+
static void flow_loops_cfg_dump (const struct loops *, FILE *);
static void flow_loop_entry_edges_find (struct loop *);
static void flow_loop_exit_edges_find (struct loop *);
*************** flow_loop_nested_p (const struct loop *o
*** 98,103 ****
--- 101,120 ----
&& loop->pred[outer->depth] == outer;
}
+ /* Returns superloop of LOOP at given DEPTH. */
+
+ struct loop *
+ superloop_at_depth (struct loop *loop, unsigned depth)
+ {
+ if (depth > (unsigned) loop->depth)
+ abort ();
+
+ if (depth == (unsigned) loop->depth)
+ return loop;
+
+ return loop->pred[depth];
+ }
+
/* Dump the loop information specified by LOOP to the stream FILE
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
*************** flow_loop_scan (struct loop *loop, int f
*** 547,553 ****
--- 564,604 ----
return 1;
}
+ /* A callback to update latch and header info for basic block JUMP created
+ by redirecting an edge. */
+
+ static void
+ update_latch_info (basic_block jump)
+ {
+ alloc_aux_for_block (jump, sizeof (int));
+ HEADER_BLOCK (jump) = 0;
+ alloc_aux_for_edge (jump->pred, sizeof (int));
+ LATCH_EDGE (jump->pred) = 0;
+ }
+
+ /* A callback for make_forwarder block, to redirect all edges except for
+ MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
+ whether to redirect it. */
+
+ static edge mfb_kj_edge;
+ static bool
+ mfb_keep_just (edge e)
+ {
+ return e != mfb_kj_edge;
+ }
+
+ /* A callback for make_forwarder block, to redirect the latch edges into an
+ entry part. E is the edge for that we should decide whether to redirect
+ it. */
+
+ static bool
+ mfb_keep_nonlatch (edge e)
+ {
+ return LATCH_EDGE (e);
+ }
+
/* Takes care of merging natural loops with shared headers. */
+
static void
canonicalize_loop_headers (void)
{
*************** canonicalize_loop_headers (void)
*** 604,622 ****
FOR_EACH_BB (header)
{
- int num_latch;
- int want_join_latch;
int max_freq, is_heavy;
! edge heavy;
! if (!HEADER_BLOCK (header))
! continue;
!
! num_latch = HEADER_BLOCK (header);
!
! want_join_latch = (num_latch > 1);
!
! if (!want_join_latch)
continue;
/* Find a heavy edge. */
--- 655,664 ----
FOR_EACH_BB (header)
{
int max_freq, is_heavy;
! edge heavy, tmp_edge;
! if (HEADER_BLOCK (header) <= 1)
continue;
/* Find a heavy edge. */
*************** canonicalize_loop_headers (void)
*** 642,654 ****
if (is_heavy)
{
! basic_block new_header =
! make_forwarder_block (header, true, true, heavy, 0);
! if (num_latch > 2)
! make_forwarder_block (new_header, true, false, NULL, 1);
}
- else
- make_forwarder_block (header, true, false, NULL, 1);
}
free_aux_for_blocks ();
--- 684,711 ----
if (is_heavy)
{
! /* Split out the heavy edge, and create inner loop for it. */
! mfb_kj_edge = heavy;
! tmp_edge = make_forwarder_block (header, mfb_keep_just,
! update_latch_info);
! alloc_aux_for_block (tmp_edge->dest, sizeof (int));
! HEADER_BLOCK (tmp_edge->dest) = 1;
! alloc_aux_for_edge (tmp_edge, sizeof (int));
! LATCH_EDGE (tmp_edge) = 0;
! HEADER_BLOCK (header)--;
! }
!
! if (HEADER_BLOCK (header) > 1)
! {
! /* Create a new latch block. */
! tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
! update_latch_info);
! alloc_aux_for_block (tmp_edge->dest, sizeof (int));
! HEADER_BLOCK (tmp_edge->src) = 0;
! HEADER_BLOCK (tmp_edge->dest) = 1;
! alloc_aux_for_edge (tmp_edge, sizeof (int));
! LATCH_EDGE (tmp_edge) = 1;
}
}
free_aux_for_blocks ();
*************** glb_enum_p (basic_block bb, void *glb_he
*** 885,890 ****
--- 942,948 ----
/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
order against direction of edges from latch. Specially, if
header != latch, latch is the 1-st block. */
+
basic_block *
get_loop_body (const struct loop *loop)
{
*************** get_loop_body (const struct loop *loop)
*** 915,920 ****
--- 973,1034 ----
if (tv != loop->num_nodes)
abort ();
+ return tovisit;
+ }
+
+ /* Fills dominance descendants inside LOOP of the basic block BB into
+ array TOVISIT from index *TV. */
+
+ static void
+ fill_sons_in_loop (const struct loop *loop, basic_block bb,
+ basic_block *tovisit, int *tv)
+ {
+ basic_block son, postpone = NULL;
+
+ tovisit[(*tv)++] = bb;
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (!flow_bb_inside_loop_p (loop, son))
+ continue;
+
+ if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
+ {
+ postpone = son;
+ continue;
+ }
+ fill_sons_in_loop (loop, son, tovisit, tv);
+ }
+
+ if (postpone)
+ fill_sons_in_loop (loop, postpone, tovisit, tv);
+ }
+
+ /* Gets body of a LOOP (that must be different from the outermost loop)
+ sorted by dominance relation. Additionally, if a basic block s dominates
+ the latch, then only blocks dominated by s are be after it. */
+
+ basic_block *
+ get_loop_body_in_dom_order (const struct loop *loop)
+ {
+ basic_block *tovisit;
+ int tv;
+
+ if (!loop->num_nodes)
+ abort ();
+
+ tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+
+ if (loop->latch == EXIT_BLOCK_PTR)
+ abort ();
+
+ tv = 0;
+ fill_sons_in_loop (loop, loop->header, tovisit, &tv);
+
+ if (tv != (int) loop->num_nodes)
+ abort ();
+
return tovisit;
}
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.9.2.1
diff -c -3 -p -r1.2.4.9.2.1 cfgloop.h
*** cfgloop.h 27 Dec 2003 05:42:46 -0000 1.2.4.9.2.1
--- cfgloop.h 3 Jan 2004 20:16:58 -0000
*************** extern bool flow_loop_outside_edge_p (co
*** 278,288 ****
--- 278,290 ----
extern bool flow_loop_nested_p (const struct loop *, const struct loop *);
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 int num_loop_insns (struct loop *);
extern int average_num_loop_insns (struct loop *);
/* Loops & cfg manipulation. */
extern basic_block *get_loop_body (const struct loop *);
+ extern basic_block *get_loop_body_in_dom_order (const struct loop *);
extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
extern edge loop_preheader_edge (const struct loop *);
*************** loop_from_num (struct loops *loops,
*** 352,354 ****
--- 354,360 ----
{
return loops->parray[num];
}
+
+ /* Loop optimizer dump file. */
+ extern FILE *loop_dump_file;
+ extern int loop_dump_flags;
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.2.4.9
diff -c -3 -p -r1.2.4.9 cfgloopanal.c
*** cfgloopanal.c 19 Dec 2003 01:01:48 -0000 1.2.4.9
--- cfgloopanal.c 3 Jan 2004 20:16:58 -0000
*************** mark_irreducible_loops (struct loops *lo
*** 1246,1252 ****
: e->dest->index + 1;
if (closed[sidx])
{
! if (!closed[mri[sidx]])
{
if (mr[sidx] < mr[idx])
{
--- 1246,1252 ----
: e->dest->index + 1;
if (closed[sidx])
{
! if (mri[sidx] != -1 && !closed[mri[sidx]])
{
if (mr[sidx] < mr[idx])
{
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.3.2.11
diff -c -3 -p -r1.3.2.11 cfgloopmanip.c
*** cfgloopmanip.c 21 Dec 2003 09:30:58 -0000 1.3.2.11
--- cfgloopmanip.c 3 Jan 2004 20:16:58 -0000
*************** split_loop_bb (basic_block bb, rtx insn)
*** 63,73 ****
/* Add dest to loop. */
add_bb_to_loop (e->dest, e->src->loop_father);
- /* Fix dominators. */
- add_to_dominance_info (CDI_DOMINATORS, e->dest);
- redirect_immediate_dominators (CDI_DOMINATORS, e->src, e->dest);
- set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
-
return e;
}
--- 63,68 ----
*************** duplicate_loop_to_header_edge (struct lo
*** 1070,1088 ****
return true;
}
/* Creates a pre-header for a LOOP. Returns newly created block. Unless
CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
entry; otherwise we also force preheader block to have only one successor.
! The function also updates dominators stored in DOM. */
static basic_block
create_preheader (struct loop *loop, int flags)
{
edge e, fallthru;
basic_block dummy;
- basic_block jump, src = 0;
struct loop *cloop, *ploop;
int nentry = 0;
! rtx insn;
cloop = loop->outer;
--- 1065,1112 ----
return true;
}
+ /* A callback for make_forwarder block, to redirect all edges except for
+ MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
+ whether to redirect it. */
+
+ static edge mfb_kj_edge;
+ static bool
+ mfb_keep_just (edge e)
+ {
+ return e != mfb_kj_edge;
+ }
+
+ /* A callback for make_forwarder block, to update data structures for a basic
+ block JUMP created by redirecting an edge (only the latch edge is being
+ redirected). */
+
+ static void
+ mfb_update_loops (basic_block jump)
+ {
+ struct loop *loop = jump->succ->dest->loop_father;
+
+ if (dom_computed[CDI_DOMINATORS])
+ {
+ add_to_dominance_info (CDI_DOMINATORS, jump);
+ set_immediate_dominator (CDI_DOMINATORS, jump, jump->pred->src);
+ }
+ add_bb_to_loop (jump, loop);
+ loop->latch = jump;
+ }
+
/* Creates a pre-header for a LOOP. Returns newly created block. Unless
CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
entry; otherwise we also force preheader block to have only one successor.
! The function also updates dominators. */
!
static basic_block
create_preheader (struct loop *loop, int flags)
{
edge e, fallthru;
basic_block dummy;
struct loop *cloop, *ploop;
int nentry = 0;
! bool irred = false;
cloop = loop->outer;
*************** create_preheader (struct loop *loop, int
*** 1090,1095 ****
--- 1114,1120 ----
{
if (e->src == loop->latch)
continue;
+ irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
nentry++;
}
if (!nentry)
*************** create_preheader (struct loop *loop, int
*** 1102,1118 ****
return NULL;
}
! insn = first_insn_after_basic_block_note (loop->header);
! if (insn)
! insn = PREV_INSN (insn);
! else
! insn = get_last_insn ();
! if (insn == loop->header->end)
! {
! /* Split_block would not split block after its end. */
! emit_note_after (NOTE_INSN_DELETED, insn);
! }
! fallthru = split_block (loop->header, insn);
dummy = fallthru->src;
loop->header = fallthru->dest;
--- 1127,1135 ----
return NULL;
}
! mfb_kj_edge = loop_latch_edge (loop);
! fallthru = make_forwarder_block (loop->header, mfb_keep_just,
! mfb_update_loops);
dummy = fallthru->src;
loop->header = fallthru->dest;
*************** create_preheader (struct loop *loop, int
*** 1122,1156 ****
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
! add_to_dominance_info (CDI_DOMINATORS, fallthru->dest);
!
! /* Redirect edges. */
! for (e = dummy->pred; e; e = e->pred_next)
! {
! src = e->src;
! if (src == loop->latch)
! break;
}
- if (!e)
- abort ();
! dummy->frequency -= EDGE_FREQUENCY (e);
! dummy->count -= e->count;
! fallthru->count -= e->count;
! jump = redirect_edge_and_branch_force (e, loop->header);
! if (jump)
{
! add_to_dominance_info (CDI_DOMINATORS, jump);
! set_immediate_dominator (CDI_DOMINATORS, jump, src);
! add_bb_to_loop (jump, loop);
! loop->latch = jump;
}
- /* Update structures. */
- redirect_immediate_dominators (CDI_DOMINATORS, dummy, loop->header);
- set_immediate_dominator (CDI_DOMINATORS, loop->header, dummy);
- loop->header->loop_father = loop;
- add_bb_to_loop (dummy, cloop);
if (rtl_dump_file)
fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
loop->num);
--- 1139,1163 ----
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
! /* Reorganize blocks so that the preheader is not stuck in the middle of the
! loop. */
! if (cfg_hooks->move_block_after)
! {
! for (e = dummy->pred; e; e = e->pred_next)
! if (e->src != loop->latch)
! break;
! move_block_after (dummy, e->src);
}
! loop->header->loop_father = loop;
! add_bb_to_loop (dummy, cloop);
!
! if (irred)
{
! dummy->flags |= BB_IRREDUCIBLE_LOOP;
! dummy->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
}
if (rtl_dump_file)
fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
loop->num);
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.57.2.21
diff -c -3 -p -r1.57.2.21 cfgrtl.c
*** cfgrtl.c 21 Dec 2003 09:30:58 -0000 1.57.2.21
--- cfgrtl.c 3 Jan 2004 20:16:58 -0000
*************** static rtx last_loop_beg_note (rtx);
*** 76,81 ****
--- 76,82 ----
static bool back_edge_of_syntactic_loop_p (basic_block, basic_block);
basic_block force_nonfallthru_and_redirect (edge, basic_block);
static basic_block rtl_split_edge (edge);
+ static edge rtl_split_block_after_labels (basic_block);
static int rtl_verify_flow_info (void);
static edge cfg_layout_split_block (basic_block, void *);
static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
*************** static edge rtl_split_block (basic_block
*** 88,95 ****
static void rtl_dump_bb (basic_block, FILE *, int);
static int rtl_verify_flow_info_1 (void);
static void mark_killed_regs (rtx, rtx, void *);
! static basic_block rtl_make_forwarder_block (basic_block, int, int, edge, int);
! static void redirect_edge_with_latch_update (edge, basic_block);
/* Return true if NOTE is not one of the ones that must be kept paired,
so that we may simply delete it. */
--- 89,96 ----
static void rtl_dump_bb (basic_block, FILE *, int);
static int rtl_verify_flow_info_1 (void);
static void mark_killed_regs (rtx, rtx, void *);
! static edge rtl_make_forwarder_block (basic_block, bool (*) (edge),
! void (*) (basic_block));
/* Return true if NOTE is not one of the ones that must be kept paired,
so that we may simply delete it. */
*************** rtl_split_block (basic_block bb, void *i
*** 500,505 ****
--- 501,513 ----
new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
+ if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
+ {
+ add_to_dominance_info (CDI_DOMINATORS, new_bb);
+ redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
+ set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
+ }
+
if (bb->global_live_at_start)
{
new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
*************** cfg_layout_split_edge (edge e)
*** 2737,2751 ****
return new_bb;
}
! /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
! marked as latch into entry part, analogically for REDIRECT_NONLATCH.
! In both of these cases, ignore edge EXCEPT. If CONN_LATCH, set edge
! between created entry part and BB as latch one. Return created entry
! part. */
! static basic_block
! rtl_make_forwarder_block (basic_block bb, int redirect_latch,
! int redirect_nonlatch, edge except, int conn_latch)
{
edge e, next_e, fallthru;
basic_block dummy;
--- 2745,2758 ----
return new_bb;
}
! /* Split BB into entry part and the rest (the rest is the newly created block).
! Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
! part. Returns the edge connecting the entry part to the rest. Call
! NEW_BB_CALLBACK for every block created due to edge redirection. */
! static edge
! rtl_make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
! void (*new_bb_callback) (basic_block))
{
edge e, next_e, fallthru;
basic_block dummy;
*************** rtl_make_forwarder_block (basic_block bb
*** 2761,2809 ****
dummy = fallthru->src;
bb = fallthru->dest;
- bb->aux = xmalloc (sizeof (int));
- HEADER_BLOCK (dummy) = 0;
- HEADER_BLOCK (bb) = 1;
-
/* Redirect back edges we want to keep. */
for (e = dummy->pred; e; e = next_e)
{
next_e = e->pred_next;
! if (e == except
! || !((redirect_latch && LATCH_EDGE (e))
! || (redirect_nonlatch && !LATCH_EDGE (e))))
! {
! dummy->frequency -= EDGE_FREQUENCY (e);
! dummy->count -= e->count;
! if (dummy->frequency < 0)
! dummy->frequency = 0;
! if (dummy->count < 0)
! dummy->count = 0;
! redirect_edge_with_latch_update (e, bb);
! }
}
! alloc_aux_for_edge (fallthru, sizeof (int));
! LATCH_EDGE (fallthru) = conn_latch;
! return dummy;
}
! /* Redirect edge and update latch and header info. */
! static void
! redirect_edge_with_latch_update (edge e, basic_block to)
{
! basic_block jump;
! jump = redirect_edge_and_branch_force (e, to);
! if (jump)
{
! alloc_aux_for_block (jump, sizeof (int));
! HEADER_BLOCK (jump) = 0;
! alloc_aux_for_edge (jump->pred, sizeof (int));
! LATCH_EDGE (jump->succ) = LATCH_EDGE (e);
! LATCH_EDGE (jump->pred) = 0;
}
}
/* Declarations from cfgloop.h. */
--- 2768,2824 ----
dummy = fallthru->src;
bb = fallthru->dest;
/* Redirect back edges we want to keep. */
for (e = dummy->pred; e; e = next_e)
{
+ basic_block jump;
+
next_e = e->pred_next;
! if (redirect_edge_p (e))
! continue;
!
! dummy->frequency -= EDGE_FREQUENCY (e);
! dummy->count -= e->count;
! if (dummy->frequency < 0)
! dummy->frequency = 0;
! if (dummy->count < 0)
! dummy->count = 0;
!
! jump = redirect_edge_and_branch_force (e, bb);
! if (jump)
! new_bb_callback (jump);
}
! if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
! {
! basic_block doms_to_fix[2];
!
! doms_to_fix[0] = fallthru->src;
! doms_to_fix[1] = fallthru->dest;
! iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
! }
! return fallthru;
}
! /* Splits block BB immediately after the initial label. */
!
! static edge
! rtl_split_block_after_labels (basic_block bb)
{
! rtx insn = first_insn_after_basic_block_note (bb);
! if (insn)
! insn = PREV_INSN (insn);
! else
! insn = get_last_insn ();
! if (insn == bb->end)
{
! /* Split_block would not split block after its end. */
! emit_note_after (NOTE_INSN_DELETED, insn);
}
+
+ return split_block (bb, insn);
}
/* Declarations from cfgloop.h. */
*************** struct cfg_hooks rtl_cfg_hooks = {
*** 2819,2824 ****
--- 2834,2841 ----
rtl_redirect_edge_and_branch_force,
rtl_delete_block,
rtl_split_block,
+ rtl_split_block_after_labels,
+ NULL,
rtl_can_merge_blocks, /* can_merge_blocks_p */
rtl_merge_blocks,
rtl_split_edge,
*************** struct cfg_hooks cfg_layout_rtl_cfg_hook
*** 2839,2844 ****
--- 2856,2863 ----
cfg_layout_redirect_edge_and_branch_force,
cfg_layout_delete_block,
cfg_layout_split_block,
+ rtl_split_block_after_labels,
+ NULL,
cfg_layout_can_merge_blocks_p,
cfg_layout_merge_blocks,
cfg_layout_split_edge,
Index: jump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/jump.c,v
retrieving revision 1.210.2.17
diff -c -3 -p -r1.210.2.17 jump.c
*** jump.c 14 Nov 2003 00:24:28 -0000 1.210.2.17
--- jump.c 3 Jan 2004 20:16:58 -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)
*** 123,177 ****
}
}
- /* 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)
{
--- 121,126 ----
*************** mark_all_labels (rtx f)
*** 288,531 ****
}
}
- /* 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. If
- the code is sufficiently simple, make a copy of it before INSN,
- followed by a jump to the exit of the loop. Then delete the unconditional
- jump after INSN.
-
- 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;
- }
- }
-
- /* 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,
notes between START and END out before START. START and END may be such
--- 237,242 ----
Index: loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unswitch.c,v
retrieving revision 1.2.2.6
diff -c -3 -p -r1.2.2.6 loop-unswitch.c
*** loop-unswitch.c 19 Dec 2003 01:01:48 -0000 1.2.2.6
--- loop-unswitch.c 3 Jan 2004 20:16:58 -0000
*************** unswitch_loop (struct loops *loops, stru
*** 401,405 ****
--- 401,409 ----
fix_loop_placement (loop);
fix_loop_placement (nloop);
+ /* Preserve the simple loop preheaders. */
+ loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
+ loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
+
return nloop;
}
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.15.2.15
diff -c -3 -p -r1.15.2.15 params.def
*** params.def 14 Dec 2003 12:16:20 -0000 1.15.2.15
--- params.def 3 Jan 2004 20:16:58 -0000
*************** DEFPARAM(PARAM_MAX_CSE_PATH_LENGTH,
*** 258,263 ****
--- 258,270 ----
"The maximum length of path considered in cse",
10)
+ /* The cost of expression in loop invariant motion to be considered
+ expensive. */
+ DEFPARAM(PARAM_LIM_EXPENSIVE,
+ "lim-expensive",
+ "The minimum cost of expensive expression in the loop invariant motion",
+ 20)
+
#ifdef ENABLE_GC_ALWAYS_COLLECT
# define GGC_MIN_EXPAND_DEFAULT 0
# define GGC_MIN_HEAPSIZE_DEFAULT 0
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.362.2.30
diff -c -3 -p -r1.362.2.30 rtl.h
*** rtl.h 1 Dec 2003 19:38:38 -0000 1.362.2.30
--- rtl.h 3 Jan 2004 20:16:58 -0000
*************** extern enum rtx_code reversed_comparison
*** 2025,2031 ****
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);
--- 2025,2030 ----
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.84.2.2
diff -c -3 -p -r1.654.2.84.2.2 toplev.c
*** toplev.c 1 Jan 2004 20:16:25 -0000 1.654.2.84.2.2
--- toplev.c 3 Jan 2004 20:16:59 -0000
*************** rest_of_compilation (tree decl)
*** 3270,3281 ****
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);
--- 3270,3275 ----
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.244
diff -c -3 -p -r1.1.4.244 tree-cfg.c
*** tree-cfg.c 26 Dec 2003 22:38:27 -0000 1.1.4.244
--- tree-cfg.c 3 Jan 2004 20:16:59 -0000
*************** static GTY(()) tree factored_computed_go
*** 81,87 ****
/* Basic blocks and flowgraphs. */
static basic_block create_bb (tree, basic_block);
- static void create_blocks_annotations (void);
static void create_block_annotation (basic_block);
static void free_blocks_annotations (void);
static void clear_blocks_annotations (void);
--- 81,86 ----
*************** static edge tree_redirect_edge_and_branc
*** 102,108 ****
/* Various helpers. */
static inline bool stmt_starts_bb_p (tree, tree);
static int tree_verify_flow_info (void);
! static basic_block tree_make_forwarder_block (basic_block, int, int, edge, int);
static struct loops *tree_loop_optimizer_init (FILE *);
static void tree_loop_optimizer_finalize (struct loops *, FILE *);
static bool thread_jumps (void);
--- 101,108 ----
/* Various helpers. */
static inline bool stmt_starts_bb_p (tree, tree);
static int tree_verify_flow_info (void);
! static edge tree_make_forwarder_block (basic_block, bool (*) (edge),
! void (*) (basic_block));
static struct loops *tree_loop_optimizer_init (FILE *);
static void tree_loop_optimizer_finalize (struct loops *, FILE *);
static bool thread_jumps (void);
*************** build_tree_cfg (tree *fnbody)
*** 165,172 ****
/* Adjust the size of the array. */
VARRAY_GROW (basic_block_info, n_basic_blocks);
! /* Create block annotations. */
! create_blocks_annotations ();
/* Create the edges of the flowgraph. */
make_edges ();
--- 165,172 ----
/* Adjust the size of the array. */
VARRAY_GROW (basic_block_info, n_basic_blocks);
! create_block_annotation (ENTRY_BLOCK_PTR);
! create_block_annotation (EXIT_BLOCK_PTR);
/* Create the edges of the flowgraph. */
make_edges ();
*************** factor_computed_gotos (void)
*** 269,284 ****
}
}
- /* Create annotations for all the basic blocks. */
-
- static void create_blocks_annotations (void)
- {
- basic_block bb;
-
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- create_block_annotation (bb);
- }
-
/* Create annotations for a single basic block. */
static void create_block_annotation (basic_block bb)
--- 269,274 ----
*************** create_bb (tree stmt_list, basic_block a
*** 383,388 ****
--- 373,380 ----
/* Add the newly created block to the array. */
BASIC_BLOCK (n_basic_blocks) = bb;
+ create_block_annotation (bb);
+
n_basic_blocks++;
last_basic_block++;
*************** tree_find_edge_insert_loc (edge e, block
*** 2556,2567 ****
/* This routine will commit all pending edge insertions, creating any new
basic blocks which are necessary.
! If UPDATE_ANNOTATIONS is true, then new bitmaps are created for the
! dominator children, and they are updated. If specified, NEW_BLOCKS
! returns a count of the number of new basic blocks which were created. */
void
! bsi_commit_edge_inserts (bool update_annotations, int *new_blocks)
{
basic_block bb;
edge e;
--- 2548,2558 ----
/* This routine will commit all pending edge insertions, creating any new
basic blocks which are necessary.
! If specified, NEW_BLOCKS returns a count of the number of new basic blocks
! which were created. */
void
! bsi_commit_edge_inserts (int *new_blocks)
{
basic_block bb;
edge e;
*************** bsi_commit_edge_inserts (bool update_ann
*** 2577,2589 ****
if (new_blocks)
*new_blocks = n_basic_blocks - blocks;
-
- /* Expand arrays if we created new blocks and need to update them. */
- if (update_annotations && blocks != n_basic_blocks)
- {
- /* TODO. Unimplemented at the moment. */
- abort ();
- }
}
--- 2568,2573 ----
*************** tree_split_edge (edge edge_in)
*** 2668,2676 ****
after_bb = edge_in->src;
new_bb = create_bb (NULL, after_bb);
- create_block_annotation (new_bb);
new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
if (!tree_redirect_edge_and_branch_1 (edge_in, new_bb, true))
abort ();
--- 2652,2665 ----
after_bb = edge_in->src;
new_bb = create_bb (NULL, after_bb);
new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
+ if (edge_in->flags & EDGE_IRREDUCIBLE_LOOP)
+ {
+ new_edge->flags |= EDGE_IRREDUCIBLE_LOOP;
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+ }
+
if (!tree_redirect_edge_and_branch_1 (edge_in, new_bb, true))
abort ();
*************** tree_verify_flow_info (void)
*** 3137,3165 ****
return err;
}
! /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
! marked as latch into entry part, analogically for REDIRECT_NONLATCH.
! In both of these cases, ignore edge EXCEPT. If CONN_LATCH, set edge
! between created entry part and BB as latch one. Return created entry
! part. */
! static basic_block
! tree_make_forwarder_block (basic_block bb, int redirect_latch,
! int redirect_nonlatch, edge except, int conn_latch)
{
edge e, next_e, new_e, fallthru;
basic_block dummy;
tree phi, new_phi, var;
bool first;
- free_dominance_info (CDI_DOMINATORS);
-
fallthru = split_block (bb, NULL);
dummy = fallthru->src;
!
! alloc_aux_for_block (dummy, sizeof (int));
! HEADER_BLOCK (dummy) = 0;
! HEADER_BLOCK (bb) = 1;
first = true;
--- 3126,3147 ----
return err;
}
! /* Split BB into entry part and the rest (the rest is the newly created block).
! Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
! part. Returns the edge connecting the entry part to the rest. */
! static edge
! tree_make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
! void (*new_bb_cbk) (basic_block) ATTRIBUTE_UNUSED)
{
edge e, next_e, new_e, fallthru;
basic_block dummy;
tree phi, new_phi, var;
bool first;
fallthru = split_block (bb, NULL);
dummy = fallthru->src;
! bb = fallthru->dest;
first = true;
*************** tree_make_forwarder_block (basic_block b
*** 3167,3175 ****
for (e = dummy->pred; e; e = next_e)
{
next_e = e->pred_next;
! if (e != except
! && ((redirect_latch && LATCH_EDGE (e))
! || (redirect_nonlatch && !LATCH_EDGE (e))))
continue;
dummy->frequency -= EDGE_FREQUENCY (e);
--- 3149,3155 ----
for (e = dummy->pred; e; e = next_e)
{
next_e = e->pred_next;
! if (redirect_edge_p (e))
continue;
dummy->frequency -= EDGE_FREQUENCY (e);
*************** tree_make_forwarder_block (basic_block b
*** 3211,3220 ****
}
}
! alloc_aux_for_edge (fallthru, sizeof (int));
! LATCH_EDGE (fallthru) = conn_latch;
! return dummy;
}
/* Initialization of functions specific to the tree IR. */
--- 3191,3206 ----
}
}
! if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
! {
! basic_block doms_to_fix[2];
! doms_to_fix[0] = dummy;
! doms_to_fix[1] = bb;
! iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
! }
!
! return fallthru;
}
/* Initialization of functions specific to the tree IR. */
*************** tree_loop_optimizer_finalize (struct loo
*** 3271,3276 ****
--- 3257,3266 ----
if (loops == NULL)
return;
+ #ifdef ENABLE_CHECKING
+ verify_loop_structure (loops);
+ #endif
+
/* Another dump. */
flow_loops_dump (loops, dumpfile, NULL, 1);
*************** tree_redirect_edge_and_branch_1 (edge e,
*** 3558,3564 ****
return ret;
if (e->dest == dest)
! return NULL;
label = tree_block_label (dest);
--- 3548,3554 ----
return ret;
if (e->dest == dest)
! return e;
label = tree_block_label (dest);
*************** static edge
*** 3643,3697 ****
tree_split_block (basic_block bb, void *stmt)
{
block_stmt_iterator bsi, bsi_tgt;
! tree last, label;
! basic_block dummy;
edge e;
! dummy = create_bb (NULL, bb->prev_bb);
! create_block_annotation (dummy);
! dummy->count = bb->count;
! dummy->frequency = bb->frequency;
! dummy->loop_depth = bb->loop_depth;
!
! /* Redirect the incoming edges. */
! dummy->pred = bb->pred;
! bb->pred = NULL;
! for (e = dummy->pred; e; e = e->pred_next)
! e->dest = dummy;
!
! /* Move the phi nodes to the dummy block. */
! set_phi_nodes (dummy, phi_nodes (bb));
! set_phi_nodes (bb, NULL_TREE);
!
! /* Move everything up to BSI to the new basic block. */
! last = NULL_TREE;
! for (bsi = bsi_start (bb), bsi_tgt = bsi_start (dummy); !bsi_end_p (bsi); )
{
! label = bsi_stmt (bsi);
! if (TREE_CODE (label) != LABEL_EXPR)
break;
! bsi_remove (&bsi);
! bsi_insert_after (&bsi_tgt, label, BSI_NEW_STMT);
! if (label == stmt)
! last = label;
}
! while (!bsi_end_p (bsi) && last != stmt)
{
! last = bsi_stmt (bsi);
bsi_remove (&bsi);
! bsi_insert_after (&bsi_tgt, last, BSI_NEW_STMT);
}
if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
{
! set_immediate_dominator (CDI_DOMINATORS, dummy,
! get_immediate_dominator (CDI_DOMINATORS, bb));
! set_immediate_dominator (CDI_DOMINATORS, bb, dummy);
}
! return make_edge (dummy, bb, EDGE_FALLTHRU);
}
/* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
--- 3633,3748 ----
tree_split_block (basic_block bb, void *stmt)
{
block_stmt_iterator bsi, bsi_tgt;
! tree act;
! basic_block new_bb;
edge e;
! new_bb = create_bb (NULL, bb);
! new_bb->count = bb->count;
! new_bb->frequency = bb->frequency;
! new_bb->loop_depth = bb->loop_depth;
!
! /* Redirect the outgoing edges. */
! new_bb->succ = bb->succ;
! bb->succ = NULL;
! for (e = new_bb->succ; e; e = e->succ_next)
! e->src = new_bb;
!
! if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
! stmt = NULL;
!
! /* Move everything from BSI to the new basic block. */
! for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
! act = bsi_stmt (bsi);
! if (TREE_CODE (act) == LABEL_EXPR)
! continue;
!
! if (!stmt)
break;
! if (stmt == act)
! {
! bsi_next (&bsi);
! break;
! }
}
! bsi_tgt = bsi_start (new_bb);
! while (!bsi_end_p (bsi))
{
! act = bsi_stmt (bsi);
bsi_remove (&bsi);
! bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
}
if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
{
! redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
! set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
}
! return make_edge (bb, new_bb, EDGE_FALLTHRU);
! }
!
! /* Splits block BB immediatelly after initial labels. */
!
! static edge
! tree_split_block_after_labels (basic_block bb)
! {
! return tree_split_block (bb, NULL);
! }
!
! /* Moves basic block BB after block AFTER. */
!
! static void
! tree_move_block_after (basic_block bb, basic_block after)
! {
! if (bb->prev_bb == after)
! return;
!
! unlink_block (bb);
! link_block (bb, after);
! }
!
! /* 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_bb (NULL, e->src);
! bsi_tgt = bsi_start (new_bb);
! for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! {
! tree stmt = bsi_stmt (bsi);
!
! if (TREE_CODE (stmt) == LABEL_EXPR)
! continue;
!
! 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;
}
/* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
*************** struct cfg_hooks tree_cfg_hooks = {
*** 3916,3921 ****
--- 3967,3974 ----
tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force */
NULL, /* delete_basic_block */
tree_split_block, /* split_block */
+ tree_split_block_after_labels,/* split_block_after_labels */
+ tree_move_block_after, /* move_block_after */
NULL, /* can_merge_blocks_p */
NULL, /* merge_blocks */
tree_split_edge, /* cfgh_split_edge */
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.61.2.2
diff -c -3 -p -r1.6.2.61.2.2 tree-dump.c
*** tree-dump.c 1 Jan 2004 20:16:24 -0000 1.6.2.61.2.2
--- tree-dump.c 3 Jan 2004 20:16:59 -0000
*************** static struct dump_file_info dump_files[
*** 660,675 ****
{".dot", "tree-dot", 0, 0},
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
{".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
- {".loop", "tree-loop", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
{".ssa3", "tree-ssa3", 0, 0},
{".tail1", "tree-tail1", 0, 0},
{".sra", "tree-sra", 0, 0},
{".ssa4", "tree-ssa4", 0, 0},
{".ccp", "tree-ccp", 0, 0},
{".ssa5", "tree-ssa5", 0, 0},
{".pre", "tree-pre", 0, 0},
--- 660,676 ----
{".dot", "tree-dot", 0, 0},
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
+ {".ch", "tree-copy-headers", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
{".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
{".ssa3", "tree-ssa3", 0, 0},
{".tail1", "tree-tail1", 0, 0},
{".sra", "tree-sra", 0, 0},
{".ssa4", "tree-ssa4", 0, 0},
+ {".loop", "tree-loop", 0, 0},
{".ccp", "tree-ccp", 0, 0},
{".ssa5", "tree-ssa5", 0, 0},
{".pre", "tree-pre", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.1
diff -c -3 -p -r1.1.4.177.2.1 tree-flow.h
*** tree-flow.h 1 Jan 2004 20:16:25 -0000 1.1.4.177.2.1
--- tree-flow.h 3 Jan 2004 20:16:59 -0000
*************** extern bool cleanup_control_expr_graph (
*** 424,436 ****
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 void bsi_commit_edge_inserts (bool, int *);
extern void bsi_insert_on_edge_immediate (edge, tree);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
extern void compute_dominance_frontiers (bitmap *);
extern bool verify_stmt (tree);
extern void verify_stmts (void);
/* In tree-pretty-print.c. */
extern void dump_generic_bb (FILE *, basic_block, int, int);
--- 424,437 ----
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 void bsi_commit_edge_inserts (int *);
extern void bsi_insert_on_edge_immediate (edge, tree);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
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);
/* In tree-pretty-print.c. */
extern void dump_generic_bb (FILE *, basic_block, int, int);
*************** extern void propagate_copy (tree *, tree
*** 521,528 ****
/* In tree-ssa-dce.c */
void tree_ssa_dce (tree, enum tree_dump_index);
! /* In tree-ssa-loop.c */
void tree_ssa_loop_opt (tree, enum tree_dump_index);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
--- 522,531 ----
/* In tree-ssa-dce.c */
void tree_ssa_dce (tree, enum tree_dump_index);
! /* In tree-ssa-loop*.c */
void tree_ssa_loop_opt (tree, enum tree_dump_index);
+ void copy_loop_headers (tree, enum tree_dump_index);
+ void tree_ssa_lim (struct loops *loops);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
Index: tree-mudflap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-mudflap.c,v
retrieving revision 1.1.2.60
diff -c -3 -p -r1.1.2.60 tree-mudflap.c
*** tree-mudflap.c 19 Dec 2003 07:01:36 -0000 1.1.2.60
--- tree-mudflap.c 3 Jan 2004 20:16:59 -0000
*************** mf_xform_derefs_1 (tree_stmt_iterator *i
*** 500,518 ****
op0 = TREE_OPERAND (t, 0);
op1 = TREE_OPERAND (t, 1);
! while (TREE_CODE (op1) == INTEGER_CST)
{
- tree dom = TYPE_DOMAIN (TREE_TYPE (op0));
-
- /* Test for index in range. Break if not. */
- if (!dom)
- break;
- if (!TYPE_MIN_VALUE (dom) || !TYPE_MAX_VALUE (dom))
- break;
- if (tree_int_cst_lt (op1, TYPE_MIN_VALUE (dom))
- || tree_int_cst_lt (TYPE_MAX_VALUE (dom), op1))
- break;
-
/* If we're looking at a non-external VAR_DECL, then the
access must be ok. */
if (TREE_CODE (op0) == VAR_DECL && !DECL_EXTERNAL (op0))
--- 500,507 ----
op0 = TREE_OPERAND (t, 0);
op1 = TREE_OPERAND (t, 1);
! while (in_array_bounds_p (op0, op1))
{
/* If we're looking at a non-external VAR_DECL, then the
access must be ok. */
if (TREE_CODE (op0) == VAR_DECL && !DECL_EXTERNAL (op0))
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.98.2.3
diff -c -3 -p -r1.1.4.98.2.3 tree-optimize.c
*** tree-optimize.c 3 Jan 2004 01:49:35 -0000 1.1.4.98.2.3
--- tree-optimize.c 3 Jan 2004 20:16:59 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 84,89 ****
--- 84,96 ----
verify_stmts ();
#endif
+ /* Copy the loop headers. */
+ if (flag_tree_loop)
+ {
+ /* Should be on by default, but breaks some of the scev tests. */
+ copy_loop_headers (fndecl, TDI_copy_headers);
+ }
+
/* Initialize common SSA structures. */
init_tree_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 141,155 ****
verify_ssa ();
#endif
- if (flag_tree_loop)
- {
- tree_ssa_loop_opt (fndecl, TDI_loop);
-
- #ifdef ENABLE_CHECKING
- verify_ssa ();
- #endif
- }
-
/* The must-alias pass removes the aliasing and addressability bits
from variables that used to have their address taken. */
if (flag_tree_must_alias)
--- 148,153 ----
*************** optimize_function_tree (tree fndecl, tre
*** 184,189 ****
--- 182,197 ----
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
ggc_collect ();
+
+ #ifdef ENABLE_CHECKING
+ verify_ssa ();
+ #endif
+ }
+
+ /* Run loop optimizations. */
+ if (flag_tree_loop)
+ {
+ tree_ssa_loop_opt (fndecl, TDI_loop);
#ifdef ENABLE_CHECKING
verify_ssa ();
Index: tree-sra.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-sra.c,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 tree-sra.c
*** tree-sra.c 16 Dec 2003 03:26:32 -0000 1.1.2.9
--- tree-sra.c 3 Jan 2004 20:16:59 -0000
*************** scalarize_structures (void)
*** 643,649 ****
});
/* Commit edge insertions. */
! bsi_commit_edge_inserts (false, NULL);
}
--- 643,649 ----
});
/* Commit edge insertions. */
! bsi_commit_edge_inserts (NULL);
}
Index: tree-ssa-loop-im.c
===================================================================
RCS file: tree-ssa-loop-im.c
diff -N tree-ssa-loop-im.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-im.c 3 Jan 2004 20:16:59 -0000
***************
*** 0 ****
--- 1,591 ----
+ /* Loop invariant motion.
+ Copyright (C) 2003 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 "domwalk.h"
+ #include "params.h"
+
+ /* A list of dependencies. */
+
+ struct depend
+ {
+ tree stmt;
+ struct depend *next;
+ };
+
+ /* The auxiliary data kept for each statement. */
+ struct lim_aux_data
+ {
+ struct loop *max_loop; /* The outermost loop in that the statement
+ is invariant. */
+
+ struct loop *tgt_loop; /* The loop out of that we want to move the
+ invariant. */
+
+ unsigned cost; /* Cost of the computation of the value. */
+
+ struct depend *depends; /* List of statements that must be moved as
+ well. */
+ };
+
+ #define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->aux))
+
+ /* Minimum cost of an expensive expression. */
+ #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
+
+ /* The outermost loop for that execution of the header guarantees that the
+ block will be executed. */
+ #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
+
+ /* The possibilities of statement movement. */
+ enum move_pos
+ {
+ MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
+ MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
+ become executed -- memory accesses, ... */
+ MOVE_POSSIBLE /* Unlimited movement. */
+ };
+
+ /* Checks whether MEM is a memory access that might fail. */
+
+ static bool
+ unsafe_memory_access_p (tree mem)
+ {
+ tree base, idx;
+
+ switch (TREE_CODE (mem))
+ {
+ case ADDR_EXPR:
+ return false;
+
+ case COMPONENT_REF:
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ return unsafe_memory_access_p (TREE_OPERAND (mem, 0));
+
+ case ARRAY_REF:
+ base = TREE_OPERAND (mem, 0);
+ idx = TREE_OPERAND (mem, 1);
+ if (unsafe_memory_access_p (base))
+ return true;
+
+ if (TREE_CODE_CLASS (TREE_CODE (idx)) != 'c')
+ return true;
+
+ return !in_array_bounds_p (base, idx);
+
+ case INDIRECT_REF:
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ /* Determines whether it is possible to move the statement STMT. */
+
+ static enum move_pos
+ movement_possibility (tree stmt)
+ {
+ tree lhs, rhs;
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return MOVE_IMPOSSIBLE;
+
+ if (stmt_ends_bb_p (stmt))
+ return MOVE_IMPOSSIBLE;
+
+ get_stmt_operands (stmt);
+
+ if (stmt_ann (stmt)->has_volatile_ops)
+ return MOVE_IMPOSSIBLE;
+
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
+
+ if (TREE_SIDE_EFFECTS (rhs))
+ return MOVE_IMPOSSIBLE;
+
+ if (TREE_CODE (lhs) != SSA_NAME
+ || tree_could_trap_p (rhs)
+ || unsafe_memory_access_p (rhs))
+ return MOVE_PRESERVE_EXECUTION;
+
+ return MOVE_POSSIBLE;
+ }
+
+ /* Adds a dependency on DEF to DATA on statement inside LOOP. If ADD_COST is
+ true, add the cost of the computation to the cost in DATA. */
+
+ static bool
+ add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
+ bool add_cost)
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (def);
+ basic_block def_bb = bb_for_stmt (def_stmt);
+ struct loop *max_loop;
+ struct depend *dep;
+
+ if (!def_bb)
+ return true;
+
+ max_loop = find_common_loop (loop, def_bb->loop_father);
+
+ if (LIM_DATA (def_stmt))
+ max_loop = find_common_loop (max_loop,
+ LIM_DATA (def_stmt)->max_loop->outer);
+ if (max_loop == loop)
+ return false;
+ max_loop = superloop_at_depth (loop, max_loop->depth + 1);
+
+ if (flow_loop_nested_p (data->max_loop, max_loop))
+ data->max_loop = max_loop;
+
+ if (add_cost
+ && def_bb->loop_father == loop)
+ data->cost += LIM_DATA (def_stmt)->cost;
+
+ dep = xmalloc (sizeof (struct depend));
+ dep->stmt = def_stmt;
+ dep->next = data->depends;
+ data->depends = dep;
+
+ return true;
+ }
+
+ /* Estimates a cost of statement STMT. TODO -- the values here are just ad-hoc
+ constants. The estimates should be based on target-specific values. */
+
+ static unsigned
+ stmt_cost (tree stmt)
+ {
+ tree lhs, rhs;
+ unsigned cost = 1;
+
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
+
+ /* Hoisting memory references out should almost surely be a win. */
+ if (!is_gimple_variable (lhs))
+ cost += 20;
+ if (is_gimple_addr_expr_arg (rhs) && !is_gimple_variable (rhs))
+ cost += 20;
+
+ switch (TREE_CODE (rhs))
+ {
+ case CALL_EXPR:
+ /* So should be hoisting calls. */
+
+ /* Unless the call is a builtin_constant_p; this always folds to a
+ constant, so moving it is useless. */
+ rhs = get_callee_fndecl (rhs);
+ if (DECL_BUILT_IN (rhs)
+ && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
+ return 0;
+
+ cost += 20;
+ break;
+
+ case MULT_EXPR:
+ case TRUNC_DIV_EXPR:
+ case CEIL_DIV_EXPR:
+ case FLOOR_DIV_EXPR:
+ case ROUND_DIV_EXPR:
+ case EXACT_DIV_EXPR:
+ case CEIL_MOD_EXPR:
+ case FLOOR_MOD_EXPR:
+ case ROUND_MOD_EXPR:
+ case TRUNC_MOD_EXPR:
+ /* Division and multiplication are usually expensive. */
+ cost += 20;
+ break;
+
+ default:
+ break;
+ }
+
+ return cost;
+ }
+
+ /* Determine maximal level to that it is possible to move a statement STMT.
+ If MUST_PRESERVE_EXEC is true, we must preserve the fact whether the
+ statement is executed. */
+
+ static bool
+ determine_max_movement (tree stmt, bool must_preserve_exec)
+ {
+ basic_block bb = bb_for_stmt (stmt);
+ struct loop *loop = bb->loop_father;
+ struct loop *level;
+ struct lim_aux_data *lim_data = LIM_DATA (stmt);
+ use_optype uses;
+ vuse_optype vuses;
+ vdef_optype vdefs;
+ stmt_ann_t ann = stmt_ann (stmt);
+ unsigned i;
+
+ if (must_preserve_exec)
+ level = ALWAYS_EXECUTED_IN (bb);
+ else
+ level = superloop_at_depth (loop, 1);
+ lim_data->max_loop = level;
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ if (!add_dependency (USE_OP (uses, i), lim_data, loop, true))
+ return false;
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ if (!add_dependency (VUSE_OP (vuses, i), lim_data, loop, false))
+ return false;
+
+ vdefs = VDEF_OPS (ann);
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ if (!add_dependency (VDEF_OP (vdefs, i), lim_data, loop, false))
+ return false;
+
+ lim_data->cost += stmt_cost (stmt);
+
+ return true;
+ }
+
+ /* Sets a level to that the statement STMT is moved to LEVEL due to moving of
+ statement from ORIG_LOOP and update levels of all dependencies. */
+
+ static void
+ set_level (tree stmt, struct loop *orig_loop, struct loop *level)
+ {
+ struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
+ struct depend *dep;
+
+ stmt_loop = find_common_loop (orig_loop, stmt_loop);
+ if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
+ stmt_loop = find_common_loop (stmt_loop,
+ LIM_DATA (stmt)->tgt_loop->outer);
+ if (flow_loop_nested_p (stmt_loop, level))
+ return;
+
+ LIM_DATA (stmt)->tgt_loop = level;
+ for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
+ set_level (dep->stmt, orig_loop, level);
+ }
+
+ /* Determines a level to that really hoist the statement STMT. TODO -- use
+ profiling information to set it more sanely. */
+
+ static void
+ set_profitable_level (tree stmt)
+ {
+ set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
+ }
+
+ /* Checks whether STMT is a nonpure call. */
+
+ static bool
+ nonpure_call_p (tree stmt)
+ {
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ stmt = TREE_OPERAND (stmt, 1);
+
+ return (TREE_CODE (stmt) == CALL_EXPR
+ && TREE_SIDE_EFFECTS (stmt));
+ }
+
+ /* Releases the memory occupied by DATA. */
+
+ static void
+ free_lim_aux_data (struct lim_aux_data *data)
+ {
+ struct depend *dep, *next;
+
+ for (dep = data->depends; dep; dep = next)
+ {
+ next = dep->next;
+ free (dep);
+ }
+ free (data);
+ }
+
+ /* Determine invariantness of statements in basic block BB. Callback
+ for walk_dominator_tree. */
+
+ static void
+ determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
+ basic_block bb, tree last ATTRIBUTE_UNUSED)
+ {
+ enum move_pos pos;
+ block_stmt_iterator bsi;
+ tree stmt;
+ bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
+
+ if (!bb->loop_father->outer)
+ return;
+
+ if (loop_dump_file && (loop_dump_flags & TDF_DETAILS))
+ fprintf (loop_dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
+ bb->index, bb->loop_father->num, bb->loop_father->depth);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+
+ pos = movement_possibility (stmt);
+ if (pos == MOVE_IMPOSSIBLE)
+ {
+ if (nonpure_call_p (stmt))
+ maybe_never = true;
+ continue;
+ }
+
+ if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
+ continue;
+
+ stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data));
+ if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
+ {
+ free_lim_aux_data (LIM_DATA (stmt));
+ stmt_ann (stmt)->aux = NULL;
+ continue;
+ }
+
+ if (loop_dump_file && (loop_dump_flags & TDF_DETAILS))
+ {
+ print_generic_stmt_indented (loop_dump_file, stmt, 0, 2);
+ fprintf (loop_dump_file, " invariant up to level %d, cost %d.\n\n",
+ LIM_DATA (stmt)->max_loop->depth,
+ LIM_DATA (stmt)->cost);
+ }
+
+ if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
+ set_profitable_level (stmt);
+ }
+ }
+
+ /* For each statement determines the outermost loop in that it is invariant,
+ statements on whose motion it depends and the cost of the computation. */
+
+ static void
+ determine_invariantness (void)
+ {
+ struct dom_walk_data walk_data;
+
+ memset (&walk_data, 0, sizeof (struct dom_walk_data));
+ walk_data.before_dom_children_walk_stmts = determine_invariantness_stmt;
+
+ init_walk_dominator_tree (&walk_data);
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR, NULL_TREE);
+ fini_walk_dominator_tree (&walk_data);
+ }
+
+ /* Moves the statements in basic block BB to the right place. Callback
+ for walk_dominator_tree. */
+
+ static void
+ move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
+ basic_block bb, tree last ATTRIBUTE_UNUSED)
+ {
+ struct loop *level;
+ block_stmt_iterator bsi;
+ tree stmt;
+ unsigned cost = 0;
+
+ if (!bb->loop_father->outer)
+ return;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
+ {
+ stmt = bsi_stmt (bsi);
+
+ if (!LIM_DATA (stmt))
+ level = NULL;
+ else
+ {
+ cost = LIM_DATA (stmt)->cost;
+ level = LIM_DATA (stmt)->tgt_loop;
+ free_lim_aux_data (LIM_DATA (stmt));
+ stmt_ann (stmt)->aux = NULL;
+ }
+
+ if (!level)
+ {
+ bsi_next (&bsi);
+ continue;
+ }
+
+ if (loop_dump_file && (loop_dump_flags & TDF_DETAILS))
+ {
+ fprintf (loop_dump_file, "Moving statement\n");
+ print_generic_stmt (loop_dump_file, stmt, 0);
+ fprintf (loop_dump_file, "(cost %u) out of loop %d.\n\n",
+ cost, level->num);
+ }
+ bsi_insert_on_edge (loop_preheader_edge (level), stmt);
+ bsi_remove (&bsi);
+ }
+ }
+
+ /* Moves the statements to the requiered level. */
+
+ static void
+ move_computations (void)
+ {
+ struct dom_walk_data walk_data;
+ int old_last_basic_block, i;
+
+ memset (&walk_data, 0, sizeof (struct dom_walk_data));
+ walk_data.before_dom_children_walk_stmts = move_computations_stmt;
+
+ init_walk_dominator_tree (&walk_data);
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR, NULL_TREE);
+ fini_walk_dominator_tree (&walk_data);
+
+ old_last_basic_block = last_basic_block;
+ bsi_commit_edge_inserts (NULL);
+ for (i = old_last_basic_block; i < last_basic_block; i++)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ add_bb_to_loop (bb,
+ find_common_loop (bb->succ->dest->loop_father,
+ bb->pred->src->loop_father));
+ }
+ }
+
+ /* Fills ALWAYS_EXECUTED_IN for basic blocks in LOOP. CONTAINS_CALL is
+ the bitmap of blocks that contain a call. */
+
+ static void
+ fill_always_executed_in (struct loop *loop, sbitmap contains_call)
+ {
+ basic_block bb = NULL, *bbs, last = NULL;
+ unsigned i;
+ edge e;
+
+ if (!loop->header->aux)
+ {
+ bbs = get_loop_body_in_dom_order (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ bb = bbs[i];
+
+ if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+ last = bb;
+
+ if (TEST_BIT (contains_call, bb->index))
+ break;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!flow_bb_inside_loop_p (loop, e->dest))
+ break;
+ if (e)
+ break;
+ }
+
+ while (1)
+ {
+ last->aux = loop;
+ if (last == loop->header)
+ break;
+ last = get_immediate_dominator (CDI_DOMINATORS, last);
+ }
+
+ free (bbs);
+ }
+
+ for (loop = loop->inner; loop; loop = loop->next)
+ fill_always_executed_in (loop, contains_call);
+ }
+
+ /* Compute information needed by the pass. LOOPS is the loop tree. */
+
+ static void
+ tree_ssa_lim_initialize (struct loops *loops)
+ {
+ sbitmap contains_call = sbitmap_alloc (last_basic_block);
+ block_stmt_iterator bsi;
+ struct loop *loop;
+ basic_block bb;
+
+ /* Set ALWAYS_EXECUTED_IN. Quadratic, can be improved. */
+
+ sbitmap_zero (contains_call);
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ if (nonpure_call_p (bsi_stmt (bsi)))
+ break;
+ }
+
+ if (!bsi_end_p (bsi))
+ SET_BIT (contains_call, bb->index);
+ }
+
+ for (loop = loops->tree_root->inner; loop; loop = loop->next)
+ fill_always_executed_in (loop, contains_call);
+
+ sbitmap_free (contains_call);
+ }
+
+ /* Cleans up after the invariant motion pass. */
+
+ static void
+ tree_ssa_lim_finalize (void)
+ {
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ bb->aux = NULL;
+ }
+ }
+
+ /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
+ i.e. those that are likely to be win regardless of the register presure. */
+
+ void
+ tree_ssa_lim (struct loops *loops)
+ {
+ tree_ssa_lim_initialize (loops);
+
+ /* For each statement determine the outermost loop in that it is
+ invariant and cost for computing the invariant. */
+ determine_invariantness ();
+
+ /* Move the expressions that are expensive enough. */
+ move_computations ();
+
+ tree_ssa_lim_finalize ();
+ }
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 tree-ssa-loop.c
*** tree-ssa-loop.c 11 Dec 2003 19:12:23 -0000 1.1.2.3
--- tree-ssa-loop.c 3 Jan 2004 20:16:59 -0000
*************** Software Foundation, 59 Temple Place - S
*** 29,42 ****
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
- #include "basic-block.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
! /* Dump file and flags. */
! static FILE *dump_file;
! static int dump_flags;
/* The main entry into loop optimization pass. PHASE indicates which dump file
from the DUMP_FILES array to use when dumping debugging information.
--- 29,42 ----
#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-inline.h"
! FILE *loop_dump_file;
! int loop_dump_flags;
/* The main entry into loop optimization pass. PHASE indicates which dump file
from the DUMP_FILES array to use when dumping debugging information.
*************** tree_ssa_loop_opt (tree fndecl ATTRIBUTE
*** 48,67 ****
{
struct loops *loops;
! /* Does nothing for now except for checking that we are able to build the
! loops. */
! dump_file = dump_begin (phase, &dump_flags);
timevar_push (TV_TREE_LOOP);
! loops = loop_optimizer_init (dump_file);
loop_optimizer_finalize (loops,
! (dump_flags & TDF_DETAILS) ? dump_file : NULL);
timevar_pop (TV_TREE_LOOP);
! if (dump_file)
{
! dump_function_to_file (fndecl, dump_file, dump_flags);
! dump_end (phase, dump_file);
}
}
--- 48,236 ----
{
struct loops *loops;
! loop_dump_file = dump_begin (phase, &loop_dump_flags);
! timevar_push (TV_TREE_LOOP);
! loops = loop_optimizer_init (loop_dump_file);
!
! if (loops)
! {
! /* Ensure there is a place to move the computations to. */
! create_preheaders (loops, 0);
!
! /* Move the expensive loop invariants. */
! tree_ssa_lim (loops);
!
! loop_optimizer_finalize (loops,
! ((loop_dump_flags & TDF_DETAILS)
! ? loop_dump_file
! : NULL));
! cleanup_tree_cfg ();
! }
! timevar_pop (TV_TREE_LOOP);
!
! if (loop_dump_file)
! {
! dump_function_to_file (fndecl, loop_dump_file, loop_dump_flags);
! dump_end (phase, loop_dump_file);
! }
! }
!
!
! /* 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 (struct loop *loop, int *limit)
! {
! block_stmt_iterator bsi;
! basic_block header = loop->header;
! tree last;
!
! 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;
!
! 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;
! }
!
! /* For all loops, copy the condition at the end of the loop body in front
! of the loop. PHASE indicates which dump file from the DUMP_FILES array
! to use when dumping debugging information. FNDECL is the current function
! decl. */
!
! void
! copy_loop_headers (tree fndecl, enum tree_dump_index phase)
! {
! struct loops *loops;
! unsigned i;
! struct loop *loop;
! basic_block header_copy, preheader, new_header;
! edge preheader_edge, succ_in_loop;
timevar_push (TV_TREE_LOOP);
!
! loop_dump_file = dump_begin (phase, &loop_dump_flags);
!
! loops = loop_optimizer_init (loop_dump_file);
! if (!loops)
! {
! if (loop_dump_file)
! dump_end (phase, loop_dump_file);
! timevar_pop (TV_TREE_LOOP);
! 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];
!
! /* 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. */
! while (should_duplicate_loop_header_p (loop, &limit))
! {
! preheader_edge = loop_preheader_edge (loop);
! preheader = preheader_edge->src;
!
! /* 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, loop->header->succ->dest))
! succ_in_loop = loop->header->succ;
! else
! succ_in_loop = loop->header->succ->succ_next;
!
! /* But if it has more than one predecessor, split the edge so that
! we do not create loops with multiple latch edges. */
! if (!succ_in_loop->dest->pred->pred_next)
! new_header = succ_in_loop->dest;
! else
! new_header = loop_split_edge_with (succ_in_loop, NULL);
!
! /* Copy the condition and update the loop structures. */
! header_copy = tree_duplicate_bb (loop->header, preheader_edge);
! add_bb_to_loop (header_copy, preheader->loop_father);
! loop->latch = loop->header;
! loop->header = new_header;
!
! /* Ensure that the latch has just a single successor. */
! loop_split_edge_with (loop_latch_edge (loop), NULL);
! }
! }
!
! #ifdef ENABLE_CHECKING
! verify_loop_structure (loops);
! #endif
!
loop_optimizer_finalize (loops,
! ((loop_dump_flags & TDF_DETAILS)
! ? loop_dump_file
! : NULL));
!
timevar_pop (TV_TREE_LOOP);
! /* 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 ();
!
! if (loop_dump_file)
{
! dump_function_to_file (fndecl, loop_dump_file, loop_dump_flags);
! dump_end (phase, loop_dump_file);
}
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.180
diff -c -3 -p -r1.1.4.180 tree-ssa.c
*** tree-ssa.c 19 Dec 2003 07:01:36 -0000 1.1.4.180
--- tree-ssa.c 3 Jan 2004 20:16:59 -0000
*************** rewrite_into_ssa (tree fndecl, bitmap va
*** 448,453 ****
--- 448,454 ----
dump_function_to_file (fndecl, dump_file, dump_flags);
dump_end (phase, dump_file);
+ dump_file = NULL;
}
/* Free allocated memory. */
*************** rewrite_trees (var_map map, tree *values
*** 2475,2482 ****
delete_elim_graph (g);
/* If any copies were inserted on edges, actually insert them now. */
! bsi_commit_edge_inserts (0, NULL);
!
}
/* Remove the variables specified in a var map from SSA form. */
--- 2476,2482 ----
delete_elim_graph (g);
/* If any copies were inserted on edges, actually insert them now. */
! bsi_commit_edge_inserts (NULL);
}
/* Remove the variables specified in a var map from SSA form. */
*************** rewrite_vars_out_of_ssa (bitmap vars)
*** 2649,2655 ****
}
/* If any copies were inserted on edges, actually insert them now. */
! bsi_commit_edge_inserts (0, NULL);
/* Now register partitions for all instances of the variables we
are taking out of SSA form. */
--- 2649,2655 ----
}
/* If any copies were inserted on edges, actually insert them now. */
! bsi_commit_edge_inserts (NULL);
/* Now register partitions for all instances of the variables we
are taking out of SSA form. */
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2718,2723 ****
--- 2718,2724 ----
{
dump_function_to_file (fndecl, dump_file, dump_flags & ~TDF_VOPS);
dump_end (phase, dump_file);
+ dump_file = NULL;
}
/* Flush out flow graph and SSA data. */
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-tailcall.c
*** tree-tailcall.c 19 Dec 2003 07:01:36 -0000 1.1.2.12
--- tree-tailcall.c 3 Jan 2004 20:16:59 -0000
*************** find_tail_calls (basic_block bb, struct
*** 148,153 ****
--- 148,157 ----
if (act->return_block)
abort ();
+ if (STMT_VDEF_OPS (stmt)
+ || STMT_VUSE_OPS (stmt))
+ return;
+
act->ret_variable = TREE_OPERAND (stmt, 0);
if (act->ret_variable
&& TREE_CODE (act->ret_variable) == MODIFY_EXPR)
*************** static void
*** 249,259 ****
eliminate_tail_call (struct tailcall *t)
{
tree param, stmt, args;
! basic_block bb;
edge e;
tree phi;
stmt = bsi_stmt (t->call_bsi);
bb = t->call_block;
if (dump_file && (dump_flags & TDF_DETAILS))
--- 253,268 ----
eliminate_tail_call (struct tailcall *t)
{
tree param, stmt, args;
! basic_block bb, first;
edge e;
tree phi;
+ stmt_ann_t ann;
+ vdef_optype vdefs;
+ unsigned i;
stmt = bsi_stmt (t->call_bsi);
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
bb = t->call_block;
if (dump_file && (dump_flags & TDF_DETAILS))
*************** eliminate_tail_call (struct tailcall *t)
*** 274,298 ****
}
bsi_remove (&t->call_bsi);
! e = redirect_edge_and_branch (t->call_block->succ,
! ENTRY_BLOCK_PTR->succ->dest);
if (!e)
abort ();
! /* We expect that each PHI node on first basic block represent an argument.
! Add proper entries. */
! for (phi = phi_nodes (ENTRY_BLOCK_PTR->succ->dest); phi;
! phi = TREE_CHAIN (phi))
! {
! for (param = DECL_ARGUMENTS (current_function_decl),
! args = TREE_OPERAND (stmt, 1);
! param;
! param = TREE_CHAIN (param),
! args = TREE_CHAIN (args))
if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
break;
! if (!param)
! abort ();
add_phi_arg (&phi, TREE_VALUE (args), e);
}
}
--- 283,334 ----
}
bsi_remove (&t->call_bsi);
! first = ENTRY_BLOCK_PTR->succ->dest;
! e = redirect_edge_and_branch (t->call_block->succ, first);
if (!e)
abort ();
!
! /* Add phi node entries for arguments. */
! for (param = DECL_ARGUMENTS (current_function_decl),
! args = TREE_OPERAND (stmt, 1);
! param;
! param = TREE_CHAIN (param),
! args = TREE_CHAIN (args))
! {
! for (phi = phi_nodes (first); phi; phi = TREE_CHAIN (phi))
if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
break;
! if (!phi)
! continue;
!
add_phi_arg (&phi, TREE_VALUE (args), e);
+ }
+
+ /* Add phi nodes for the call clobbered variables. */
+ vdefs = VDEF_OPS (ann);
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ {
+ param = SSA_NAME_VAR (VDEF_RESULT (vdefs, i));
+ for (phi = phi_nodes (first); phi; phi = TREE_CHAIN (phi))
+ if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
+ break;
+
+ if (!phi)
+ {
+ tree name = var_ann (param)->default_def;
+ tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
+
+ var_ann (param)->default_def = new_name;
+ phi = create_phi_node (name, first);
+ SSA_NAME_DEF_STMT (name) = phi;
+ add_phi_arg (&phi, new_name, ENTRY_BLOCK_PTR->succ);
+
+ /* For all calls the same set of variables should be clobbered. */
+ if (first->pred->pred_next->pred_next)
+ abort ();
+ }
+
+ add_phi_arg (&phi, VDEF_OP (vdefs, i), e);
}
}
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.263.2.75.2.1
diff -c -3 -p -r1.263.2.75.2.1 tree.c
*** tree.c 2 Jan 2004 23:32:39 -0000 1.263.2.75.2.1
--- tree.c 3 Jan 2004 20:16:59 -0000
*************** is_essa_node (tree t)
*** 5199,5202 ****
--- 5199,5231 ----
return false;
}
+ /* Checks whether IDX is in array bounds for ARRAY. */
+
+ bool
+ in_array_bounds_p (tree array, tree idx)
+ {
+ tree dom = TYPE_DOMAIN (TREE_TYPE (array));
+ tree min, max;
+
+ if (TREE_CODE (idx) != INTEGER_CST)
+ return false;
+
+ if (!dom)
+ return false;
+
+ min = TYPE_MIN_VALUE (dom);
+ max = TYPE_MAX_VALUE (dom);
+ if (!min
+ || !max
+ || TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST)
+ return false;
+
+ if (tree_int_cst_lt (idx, min)
+ || tree_int_cst_lt (max, idx))
+ return false;
+
+ return true;
+ }
+
#include "gt-tree.h"
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.154.2.4
diff -c -3 -p -r1.342.2.154.2.4 tree.h
*** tree.h 2 Jan 2004 23:32:39 -0000 1.342.2.154.2.4
--- tree.h 3 Jan 2004 20:16:59 -0000
*************** extern tree build_offset_type (tree, tre
*** 2637,2642 ****
--- 2637,2643 ----
extern tree build_complex_type (tree);
extern tree build_vector_type (tree, int);
extern tree array_type_nelts (tree);
+ extern bool in_array_bounds_p (tree, tree);
extern tree value_member (tree, tree);
extern tree purpose_member (tree, tree);
*************** enum tree_dump_index
*** 3590,3605 ****
/* Optimization passes. The ordering and numbering of these phases must
be the same as the one in optimize_function_tree. */
TDI_ssa_1,
TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
- TDI_loop,
TDI_mustalias,
TDI_ssa_3,
TDI_tail1, /* dump after tail recursion elimination */
TDI_sra,
TDI_ssa_4,
TDI_ccp,
TDI_ssa_5,
TDI_pre,
--- 3591,3607 ----
/* Optimization passes. The ordering and numbering of these phases must
be the same as the one in optimize_function_tree. */
+ TDI_copy_headers,
TDI_ssa_1,
TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
TDI_mustalias,
TDI_ssa_3,
TDI_tail1, /* dump after tail recursion elimination */
TDI_sra,
TDI_ssa_4,
+ TDI_loop,
TDI_ccp,
TDI_ssa_5,
TDI_pre,
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.152.2.63.2.2
diff -c -3 -p -r1.152.2.63.2.2 invoke.texi
*** doc/invoke.texi 1 Jan 2004 20:16:26 -0000 1.152.2.63.2.2
--- doc/invoke.texi 3 Jan 2004 20:16:59 -0000
*************** in the following sections.
*** 251,256 ****
--- 251,257 ----
-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-copy-headers @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
*************** made by appending @file{.cfg} to the sou
*** 3526,3531 ****
--- 3527,3540 ----
@opindex fdump-tree-dot
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 copy-headers
+ @opindex fdump-tree-copy-headers
+ Dump each function after copying loop headers. The file name is made by
+ appending @file{.ch} to the source file name.
+
+ Dump the control flow graph of each function to a file. The file name is
+ made by appending @file{.cfg} to the source file name.
@item ssa
@opindex fdump-tree-ssa
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.4
diff -c -3 -p -r1.1.2.4 20030711-1.c
*** testsuite/gcc.dg/tree-ssa/20030711-1.c 21 Sep 2003 22:14:30 -0000 1.1.2.4
--- testsuite/gcc.dg/tree-ssa/20030711-1.c 3 Jan 2004 20:17:00 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2" } */
union tree_node;
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2 -ftree-loop-optimize" } */
union tree_node;
*************** record_component_aliases (type)
*** 42,53 ****
/* The call to blah can not be eliminated.
/* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "dom2" } } */
! /* There should be three IF conditionals. */
! /* { dg-final { scan-tree-dump-times "if " 3 "dom2"} } */
/* There should be two loads of type.binfo. */
/* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "dom2"} } */
! /* There should be three loads of vec.length. */
! /* { dg-final { scan-tree-dump-times "vec.length" 3 "dom2"} } */
--- 42,53 ----
/* The call to blah can not be eliminated.
/* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "dom2" } } */
! /* There should be four IF conditionals. */
! /* { dg-final { scan-tree-dump-times "if " 4 "dom2"} } */
/* There should be two loads of type.binfo. */
/* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "dom2"} } */
! /* There should be four loads of vec.length. */
! /* { dg-final { scan-tree-dump-times "vec.length" 4 "dom2"} } */
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.2
diff -c -3 -p -r1.1.2.2 20030714-2.c
*** testsuite/gcc.dg/tree-ssa/20030714-2.c 21 Sep 2003 22:14:30 -0000 1.1.2.2
--- testsuite/gcc.dg/tree-ssa/20030714-2.c 3 Jan 2004 20:17:00 -0000
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2" } */
union tree_node;
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2 -ftree-loop-optimize" } */
union tree_node;
*************** 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 "dom2"} } */
--- 32,39 ----
}
}
! /* There should be exactly four IF conditionals if we thread jumps
properly. */
! /* { dg-final { scan-tree-dump-times "if " 4 "dom2"} } */
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 3 Jan 2004 20:17:00 -0000
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-dom1 -ftree-loop-optimize" } */
+
+ extern void link_error (void);
+
+ void bla (void)
+ {
+ int i, j = 1;
+
+ for (i = 0; i < 100; i++)
+ j = 0;
+
+ if (j)
+ link_error ();
+ }
+
+ /* There should be no link_error call in the dom1 dump. */
+ /* { dg-final { scan-tree-dump-times "link_error" 0 "dom1"} } */