This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Update loop analysis 1/2
The following patch includes the previous ideas on the basic blocks
annotations, and removes the enums at_..._level.
Bootstrapped on x86 with c,c++,f77.
2003-07-31 Sebastian Pop <s.pop@laposte.net>
* basic-block.c: Declare bb_ann_d.
(basic_block_def): Add a field tree_annotations.
* cfg.c (entry_exit_blocks): Initialize tree_annotations to NULL.
* cfghooks.c: Remove the definition of cfg_level.
(rtl_register_cfg_hooks): Remove the initiallization of cfg_level.
* cfghooks.h (cfg_hooks): Add cfgh_loop_optimizer_init, and
cfgh_loop_optimizer_finalize.
(loop_optimizer_init, loop_optimizer_finalize): New macros.
(cfg_level): Remove.
* cfgloop.h (loop_optimizer_init, loop_optimizer_finalize): Rename
to rtl_loop_optimizer_init and rtl_loop_optimizer_finalize.
* cfgrtl.c (rtl_loop_optimizer_init, rtl_loop_optimizer_finalize):
Declare, and register them in rtl_cfg_hooks and cfg_layout_rtl_cfg_hook.
* loop-init.c (loop_optimizer_init, loop_optimizer_finalize): Rename
to rtl_loop_optimizer_init and rtl_loop_optimizer_finalize. Remove
the checks to cfg_level.
* tree-cfg.c (block_tree_ann_obstack, first_block_tree_ann_obj): New.
(create_blocks_annotations, create_block_annotation,
free_blocks_annotations, clear_blocks_annotations): New functions.
(tree_loop_optimizer_init, tree_loop_optimizer_finalize): New
functions. Register them in tree_cfg_hooks.
(build_tree_cfg, dump_tree_bb, delete_tree_cfg, tree_split_edge): Use
create_blocks_annotations instead of alloc_aux_for_blocks,
create_block_annotation instead of alloc_aux_for_block,
.tree_annotations instead of .aux,
free_blocks_annotations instead of free_aux_for_blocks.
(tree_register_cfg_hooks): Remove initialization of cfg_level.
* tree-flow-inline.h (bb_ann): Use .tree_annotations.
* tree-flow.h: Update comment.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.27
diff -d -u -p -r1.153.2.27 basic-block.h
--- basic-block.h 23 Jul 2003 16:59:28 -0000 1.153.2.27
+++ basic-block.h 31 Jul 2003 21:44:20 -0000
@@ -171,6 +171,9 @@ extern const struct gcov_ctr_summary *pr
struct loop;
struct loops;
+/* Declared in tree-flow.h. */
+struct bb_ann_d;
+
/* A basic block is a sequence of instructions with only entry and
only one exit. If any one of the instructions are executed, they
will all be executed, and in sequence from first to last.
@@ -251,6 +254,9 @@ typedef struct basic_block_def {
/* Additional data maintained by cfg_layout routines. */
struct reorder_block_def *rbi;
+
+ /* Annotations used at the tree level. */
+ struct bb_ann_d *tree_annotations;
} *basic_block;
#define BB_FREQ_MAX 10000
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.34.2.10
diff -d -u -p -r1.34.2.10 cfg.c
--- cfg.c 23 Jul 2003 16:59:32 -0000 1.34.2.10
+++ cfg.c 31 Jul 2003 21:44:20 -0000
@@ -114,7 +114,8 @@ struct basic_block_def entry_exit_blocks
0, /* count */
0, /* frequency */
0, /* flags */
- NULL /* rbi */
+ NULL, /* rbi */
+ NULL /* tree_annotations */
},
{
NULL, /* head */
@@ -136,7 +137,8 @@ struct basic_block_def entry_exit_blocks
0, /* count */
0, /* frequency */
0, /* flags */
- NULL /* rbi */
+ NULL, /* rbi */
+ NULL /* tree_annotations */
}
};
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.1.2.2
diff -d -u -p -r1.1.2.2 cfghooks.c
--- cfghooks.c 21 Jul 2003 13:50:29 -0000 1.1.2.2
+++ cfghooks.c 31 Jul 2003 21:44:20 -0000
@@ -34,16 +34,10 @@ extern struct cfg_hooks cfg_layout_rtl_c
/* A pointer to one of the hooks containers. */
struct cfg_hooks *cfg_hooks;
-/* A global variable that keeps track of the state of the cfg. */
-enum cfg_level cfg_level;
-
-
/* Initialization of functions specific to the rtl IR. */
-
void
rtl_register_cfg_hooks ()
{
- cfg_level = AT_RTL_LEVEL;
cfg_hooks = &rtl_cfg_hooks;
}
Index: cfghooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.h,v
retrieving revision 1.1.2.3
diff -d -u -p -r1.1.2.3 cfghooks.h
--- cfghooks.h 23 Jul 2003 16:59:32 -0000 1.1.2.3
+++ cfghooks.h 31 Jul 2003 21:44:20 -0000
@@ -60,6 +60,8 @@ struct cfg_hooks
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)
@@ -71,6 +73,8 @@ struct cfg_hooks
#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)
@@ -81,14 +85,6 @@ extern struct cfg_hooks rtl_cfg_hooks;
/* A pointer to one of the hooks containers. */
extern struct cfg_hooks *cfg_hooks;
-
-enum cfg_level {
- AT_TREE_LEVEL,
- AT_RTL_LEVEL
-};
-
-/* A global variable that keeps track of the state of the cfg. */
-extern enum cfg_level cfg_level;
/* Declarations. */
extern void rtl_register_cfg_hooks (void);
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.5
diff -d -u -p -r1.2.4.5 cfgloop.h
--- cfgloop.h 21 Jul 2003 13:50:30 -0000 1.2.4.5
+++ cfgloop.h 31 Jul 2003 21:44:20 -0000
@@ -324,8 +324,8 @@ extern bool remove_path (struct loops *,
extern edge split_loop_bb (struct loops *, basic_block, rtx);
/* Loop optimizer initialization. */
-extern struct loops *loop_optimizer_init (FILE *);
-extern void loop_optimizer_finalize (struct loops *, FILE *);
+extern struct loops *rtl_loop_optimizer_init (FILE *);
+extern void rtl_loop_optimizer_finalize (struct loops *, FILE *);
/* Optimization passes. */
extern void unswitch_loops (struct loops *);
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.57.2.12
diff -d -u -p -r1.57.2.12 cfgrtl.c
--- cfgrtl.c 23 Jul 2003 16:59:32 -0000 1.57.2.12
+++ cfgrtl.c 31 Jul 2003 21:44:21 -0000
@@ -2746,6 +2746,10 @@ redirect_edge_with_latch_update (edge e,
}
}
+/* Declarations from cfgloop.h. */
+extern struct loops *rtl_loop_optimizer_init (FILE *);
+extern void rtl_loop_optimizer_finalize (struct loops *, FILE *);
+
/* Implementation of CFG manipulation for linearized RTL. */
struct cfg_hooks rtl_cfg_hooks = {
rtl_verify_flow_info,
@@ -2758,7 +2762,9 @@ struct cfg_hooks rtl_cfg_hooks = {
rtl_can_merge_blocks, /* can_merge_blocks_p */
rtl_merge_blocks,
rtl_split_edge,
- rtl_make_forwarder_block
+ rtl_make_forwarder_block,
+ rtl_loop_optimizer_init,
+ rtl_loop_optimizer_finalize
};
/* Implementation of CFG manipulation for cfg layout RTL, where
@@ -2776,5 +2782,7 @@ struct cfg_hooks cfg_layout_rtl_cfg_hook
cfg_layout_can_merge_blocks_p,
cfg_layout_merge_blocks,
cfg_layout_split_edge,
- rtl_make_forwarder_block
+ rtl_make_forwarder_block,
+ rtl_loop_optimizer_init,
+ rtl_loop_optimizer_finalize
};
Index: loop-init.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-init.c,v
retrieving revision 1.2.2.5
diff -d -u -p -r1.2.2.5 loop-init.c
--- loop-init.c 23 Jul 2003 16:59:50 -0000 1.2.2.5
+++ loop-init.c 31 Jul 2003 21:44:21 -0000
@@ -31,7 +31,7 @@ Software Foundation, 59 Temple Place - S
/* Initialize loop optimizer. */
struct loops *
-loop_optimizer_init (FILE *dumpfile)
+rtl_loop_optimizer_init (FILE *dumpfile)
{
struct loops *loops = xcalloc (1, sizeof (struct loops));
edge e;
@@ -41,10 +41,9 @@ loop_optimizer_init (FILE *dumpfile)
/* Avoid annoying special cases of edges going to exit
block. */
- if (cfg_level == AT_RTL_LEVEL)
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- if ((e->flags & EDGE_FALLTHRU) && e->src->succ->succ_next)
- split_edge (e);
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ if ((e->flags & EDGE_FALLTHRU) && e->src->succ->succ_next)
+ split_edge (e);
/* Find the loops. */
@@ -59,7 +58,7 @@ loop_optimizer_init (FILE *dumpfile)
FOR_EACH_BB (bb)
if (bb->next_bb != EXIT_BLOCK_PTR)
bb->rbi->next = bb->next_bb;
- cfg_layout_finalize ();
+ cfg_layout_finalize ();
return NULL;
}
@@ -70,8 +69,7 @@ loop_optimizer_init (FILE *dumpfile)
loops->cfg.dfs_order = NULL;
/* Create pre-headers. */
- if (cfg_level == AT_RTL_LEVEL)
- create_preheaders (loops, CP_SIMPLE_PREHEADERS);
+ create_preheaders (loops, CP_SIMPLE_PREHEADERS);
/* Force all latches to have only single successor. */
force_single_succ_latches (loops);
@@ -92,16 +90,15 @@ loop_optimizer_init (FILE *dumpfile)
/* Finalize loop optimizer. */
void
-loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
+rtl_loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
{
basic_block bb;
/* Finalize layout changes. */
/* Make chain. */
- if (cfg_level == AT_RTL_LEVEL)
- FOR_EACH_BB (bb)
- if (bb->next_bb != EXIT_BLOCK_PTR)
- bb->rbi->next = bb->next_bb;
+ FOR_EACH_BB (bb)
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ bb->rbi->next = bb->next_bb;
/* Another dump. */
flow_loops_dump (loops, dumpfile, NULL, 1);
@@ -111,8 +108,7 @@ loop_optimizer_finalize (struct loops *l
free (loops);
/* Finalize changes. */
- if (cfg_level == AT_RTL_LEVEL)
- cfg_layout_finalize ();
+ cfg_layout_finalize ();
/* Checking. */
#ifdef ENABLE_CHECKING
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.138
diff -d -u -p -r1.1.4.138 tree-cfg.c
--- tree-cfg.c 31 Jul 2003 00:50:49 -0000 1.1.4.138
+++ tree-cfg.c 31 Jul 2003 21:44:21 -0000
@@ -76,7 +76,14 @@ static dominance_info pdom_info = NULL;
static struct cfg_stats_d cfg_stats;
+static struct obstack block_tree_ann_obstack;
+static void *first_block_tree_ann_obj = 0;
+
/* Basic blocks and flowgraphs. */
+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);
static basic_block make_blocks (tree *, tree, tree, basic_block);
static void make_cond_expr_blocks (tree *, tree, basic_block);
static void make_catch_expr_blocks (tree *, tree, basic_block);
@@ -109,6 +116,8 @@ static void find_contained_blocks (tree
static void compute_reachable_eh (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 *);
/* Flowgraph optimization and cleanup. */
static void remove_unreachable_blocks (void);
@@ -205,7 +214,9 @@ struct cfg_hooks tree_cfg_hooks = {
NULL, /* can_merge_blocks_p */
NULL, /* merge_blocks */
tree_split_edge, /* cfgh_split_edge */
- tree_make_forwarder_block /* cfgh_make_forward_block */
+ tree_make_forwarder_block, /* cfgh_make_forward_block */
+ tree_loop_optimizer_init, /* cfgh_loop_optimizer_init */
+ tree_loop_optimizer_finalize /* cfgh_loop_optimizer_finalize */
};
/*---------------------------------------------------------------------------
@@ -258,7 +269,7 @@ build_tree_cfg (tree fnbody)
VARRAY_GROW (basic_block_info, n_basic_blocks);
/* Create block annotations. */
- alloc_aux_for_blocks (sizeof (struct bb_ann_d));
+ create_blocks_annotations ();
/* Create the edges of the flowgraph. */
make_edges ();
@@ -304,6 +315,62 @@ build_tree_cfg (tree fnbody)
}
}
+/* Create annotations for all the basic blocks. */
+
+static void create_blocks_annotations (void)
+{
+ basic_block bb;
+ static int initialized;
+
+ if (!initialized)
+ {
+ gcc_obstack_init (&block_tree_ann_obstack);
+ initialized = 1;
+ }
+ /* Check whether TREE_ANNOTATIONS data are still allocated. */
+ else if (first_block_tree_ann_obj)
+ abort ();
+
+ first_block_tree_ann_obj = obstack_alloc (&block_tree_ann_obstack, 0);
+
+ 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)
+{
+ /* Verify that the tree_annotations field is clear. */
+ if (bb->tree_annotations || !first_block_tree_ann_obj)
+ abort ();
+ bb->tree_annotations = obstack_alloc (&block_tree_ann_obstack,
+ sizeof (struct bb_ann_d));
+ memset (bb->tree_annotations, 0, sizeof (struct bb_ann_d));
+}
+
+/* Free the annotations for all the basic blocks. */
+
+static void free_blocks_annotations (void)
+{
+ if (!first_block_tree_ann_obj)
+ abort ();
+ obstack_free (&block_tree_ann_obstack, first_block_tree_ann_obj);
+ first_block_tree_ann_obj = NULL;
+
+ clear_blocks_annotations ();
+}
+
+/* Clear the annotations for all the basic blocks. */
+
+static void
+clear_blocks_annotations (void)
+{
+ basic_block bb;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ bb->tree_annotations = NULL;
+}
/* Build a flowgraph for the statements starting at the statement pointed
by FIRST_P.
@@ -2572,7 +2639,7 @@ dump_tree_bb (FILE *outf, const char *pr
putc ('\n', outf);
fprintf (outf, "%s%sPARENT: ", s_indent, prefix);
- if (bb->aux && parent_block (bb))
+ if (bb->tree_annotations && parent_block (bb))
fprintf (outf, "%d\n", parent_block (bb)->index);
else
fputs ("nil\n", outf);
@@ -2591,7 +2658,7 @@ dump_tree_bb (FILE *outf, const char *pr
else
fprintf (outf, "nil\n");
- if (bb->aux)
+ if (bb->tree_annotations)
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
fprintf (outf, "%s%s# ", s_indent, prefix);
@@ -3060,7 +3127,7 @@ void
delete_tree_cfg (void)
{
if (n_basic_blocks > 0)
- free_aux_for_blocks ();
+ free_blocks_annotations ();
free_basic_block_vars (0);
}
@@ -4762,7 +4829,7 @@ tree_split_edge (edge edge_in)
dest = edge_in->dest;
new_bb = create_bb ();
- alloc_aux_for_block (new_bb, sizeof (struct bb_ann_d));
+ create_block_annotation (new_bb);
redirect_edge_succ (edge_in, new_bb);
new_edge = make_edge (new_bb, dest, 0);
@@ -4807,7 +4874,7 @@ tree_make_forwarder_block (basic_block b
/* Create the new basic block. */
dummy = create_bb ();
- alloc_aux_for_block (dummy, sizeof (struct bb_ann_d));
+ create_block_annotation (dummy);
dummy->count = bb->count;
dummy->frequency = bb->frequency;
dummy->loop_depth = bb->loop_depth;
@@ -4854,6 +4921,64 @@ tree_make_forwarder_block (basic_block b
void
tree_register_cfg_hooks ()
{
- cfg_level = AT_TREE_LEVEL;
cfg_hooks = &tree_cfg_hooks;
+}
+
+/* Initialize loop optimizer. */
+
+static struct loops *
+tree_loop_optimizer_init (FILE *dumpfile)
+{
+ struct loops *loops = xcalloc (1, sizeof (struct loops));
+
+ /* Find the loops. */
+ if (flow_loops_find (loops, LOOP_TREE) <= 1)
+ {
+ /* No loops. */
+ flow_loops_free (loops);
+ free (loops);
+ return NULL;
+ }
+
+ /* Not going to update these. */
+ free (loops->cfg.rc_order);
+ loops->cfg.rc_order = NULL;
+ free (loops->cfg.dfs_order);
+ loops->cfg.dfs_order = NULL;
+
+ /* Force all latches to have only single successor. */
+ force_single_succ_latches (loops);
+
+ /* Mark irreducible loops. */
+ mark_irreducible_loops (loops);
+
+ /* Dump loops. */
+ flow_loops_dump (loops, dumpfile, NULL, 1);
+
+#ifdef ENABLE_CHECKING
+ verify_dominators (loops->cfg.dom);
+ verify_loop_structure (loops);
+#endif
+
+ return loops;
+}
+
+/* Finalize loop optimizer. */
+static void
+tree_loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
+{
+ if (loops == NULL)
+ return;
+
+ /* Another dump. */
+ flow_loops_dump (loops, dumpfile, NULL, 1);
+
+ /* Clean up. */
+ flow_loops_free (loops);
+ free (loops);
+
+ /* Checking. */
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
}
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.46
diff -d -u -p -r1.1.2.46 tree-flow-inline.h
--- tree-flow-inline.h 28 Jul 2003 23:17:14 -0000 1.1.2.46
+++ tree-flow-inline.h 31 Jul 2003 21:44:21 -0000
@@ -251,7 +251,7 @@ reaching_defs (tree stmt)
static inline bb_ann_t
bb_ann (basic_block bb)
{
- return (bb_ann_t)bb->aux;
+ return (bb_ann_t)bb->tree_annotations;
}
static inline basic_block
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.97
diff -d -u -p -r1.1.4.97 tree-flow.h
--- tree-flow.h 23 Jul 2003 23:48:16 -0000 1.1.4.97
+++ tree-flow.h 31 Jul 2003 21:44:21 -0000
@@ -272,7 +272,7 @@ static inline tree parent_stmt (tree);
/*---------------------------------------------------------------------------
- Block annotations stored in basic_block.aux
+ Block annotations stored in basic_block.tree_annotations
---------------------------------------------------------------------------*/
struct bb_ann_d
{