This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
cfg merge part 17 - loop datastructure updates
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com,gcc-pdo at atrey dot karlin dot mff dot cuni dot cz, m dot hayes at elec dot canterbury dot ac dot nz
- Date: Mon, 13 May 2002 15:02:51 +0200
- Subject: cfg merge part 17 - loop datastructure updates
Hi,
this patch is neede for loop optimizer rewrite and depends on
http://gcc.gnu.org/ml/gcc-patches/2002-03/msg00552.html.
For loop transformations it is necesary to make loop datastructure
more dynamic to allow updates without basically rebuilding it from
the scratch.
Zdenek in last mail said:
This patch implements new loop represenation. It also makes some changes
to support moving to new loop optimizer.
It bootstrapped on i386.
Zdenek Dvorak.
Changelog:
* Makefile.in (OBJS): Add loop-new.o.
(function.o, reg-stack.o, bb-reorder.o, tracer.o):
Add dependency on basic-block.h.
(loop-new.o): New.
* basic-block.h (basic_block, struct loop, struct loops):
Change loop representation.
(update_new_blocks, commit_edge_insertions,
commit_edge_insertions_watch_calls,
find_sub_basic_blocks, flow_loop_outside_edge_p):
Changed declaration.
(flow_loop_tree_node_add): Declare.
(LOOP_EXITS_DOMS): Removed (not used anywhere and hard to maintain
just now).
(flow_loop_outside_edge_p, flow_bb_inside_loop_p,
get_loop_body, dfs_enumerate_from, add_bb_to_loop,
remove_bb_from_loops, find_common_loop, create_preheader):
Declare.
(nearest_common_dominator, set_immediate_dominator,
get_immediate_dominator, dominated_by_p,
get_dominated_by, verify_dominators):
Declare.
* bb-reorder.c (reorder_basic_blocks): Modified.
* cfg.c (entry_exit_blocks): Initialize new fields.
(dump_flow_info): Modified.
* cfganal.c (flow_call_edges_add): Modified.
* cfgbuild.c (find_bb_boundaries, find_basic_blocks,
find_many_sub_basic_blocks, find_sub_basic_blocks):
Record new blocks.
* cfglayout.c (cleanup_unconditional_jumps,
cfg_layout_duplicate_bb, cfg_layout_initialize):
Update loop structure.
* cfglayout.h (reorder_block_def): Support for loop copying.
(cfg_layout_initialize): Declaration modified.
* cfgloop.c (flow_loop_nested_p, flow_loop_entry_edges_find,
flow_loop_exit_edges_find, flow_loop_pre_header_scan,
flow_loops_cfg_dump, flow_loops_free,
flow_loop_pre_header_find, flow_loop_scan):
Adapted for new loop represenation.
(flow_loop_nodes_find, flow_loop_tree_node_add,
flow_loops_tree_build, flow_loop_level_compute):
Reworked to create new loop representation.
(make_forwarder_block, canonicalize_loop_headers): New static
functions.
* cfgloopanal.c (for_each_insn_in_loop,
not_invariant_rtx, test_invariants):
Adapted for new loop represenation.
* cfgrtl.c (commit_one_edge_insertion, update_new_blocks,
commit_edge_insertions, commit_edge_insertions_watch_calls):
Record new blocks.
* flow.c (initialize_uninitialized_subregs): Modified.
* function.c (thread_prologue_and_epilogue_insns): Modified.
* gcse.c (pre_gcse, store_motion): Modified.
* lcm.c (optimize_mode_switching): Modified.
* loop.h (loop_optimizer_init, loop_optimizer_finalize):
New loop optimizer interface declaration.
* predict.c (estimate_loops_at_level, propagate_freq,
estimate_probability, estimate_bb_frequencies):
Adapted for new loop representation.
* profile.c (instrument_edges): Modified.
* reg-stack.c (convert_regs): Modified.
* reload1.c (fixup_abnormal_edges): Modified.
* ssa.c (convert_from_ssa): Modified.
* toplev.c (rest_of_compilation): Prepare for
new loop optimizer.
* tracer.c (tracer): Modified.
* loop-new.c: New file.
(get_immediate_dominator, set_immediate_dominator,
get_dominated_by, nearest_common_dominator,
dominated_by_p, verify_dominators, recount_dominator):
Stupid dominator handling. Should be replaced soon.
(loop_optimizer_init, loop_optimizer_finalize):
New loop optimizer interface.
Index: basic-block.h
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.139
diff -c -3 -p -r1.139 basic-block.h
*** basic-block.h 8 May 2002 09:17:16 -0000 1.139
--- basic-block.h 9 May 2002 20:41:46 -0000
*************** typedef struct basic_block_def {
*** 208,213 ****
--- 208,216 ----
/* The loop depth of this block. */
int loop_depth;
+ /* Innermost loop containing the block. */
+ struct loop *loop_father;
+
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
*************** struct loop
*** 385,390 ****
--- 390,398 ----
/* The loop nesting depth. */
int depth;
+ /* Predecestors of the loop. */
+ struct loop **pred;
+
/* The height of the loop (enclosed loop levels) within the loop
hierarchy tree. */
int level;
*************** struct loop
*** 398,406 ****
/* Link to the next (sibling) loop. */
struct loop *next;
- /* Non-zero if the loop shares a header with another loop. */
- int shared;
-
/* Non-zero if the loop is invalid (e.g., contains setjmp.). */
int invalid;
--- 406,411 ----
*************** struct loops
*** 466,471 ****
--- 471,479 ----
will find the inner loops before their enclosing outer loops). */
struct loop *array;
+ /* In new loop representation, we store only pointers here. */
+ struct loop **parray;
+
/* Pointer to root of loop heirachy tree. */
struct loop *tree_root;
*************** extern void flow_loop_dump PARAMS ((cons
*** 497,502 ****
--- 505,512 ----
void (*)(const struct loop *,
FILE *, int), int));
extern int flow_loop_scan PARAMS ((struct loops *, struct loop *, int));
+ extern void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
+ extern void flow_loop_tree_node_remove PARAMS ((struct loop *));
/* This structure maintains an edge list vector. */
struct edge_list
*************** enum update_life_extent
*** 588,595 ****
#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */
#define LOOP_EXIT_EDGES 8 /* Find exit edges. */
#define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
! #define LOOP_EXITS_DOMS 16 /* Find nodes that dom. all exits. */
! #define LOOP_ALL 31 /* All of the above */
extern void life_analysis PARAMS ((rtx, FILE *, int));
extern int update_life_info PARAMS ((sbitmap, enum update_life_extent,
--- 598,604 ----
#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */
#define LOOP_EXIT_EDGES 8 /* Find exit edges. */
#define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
! #define LOOP_ALL 15 /* All of the above */
extern void life_analysis PARAMS ((rtx, FILE *, int));
extern int update_life_info PARAMS ((sbitmap, enum update_life_extent,
*************** extern void free_aux_for_edges PARAMS (
*** 670,676 ****
debugger, and it is declared extern so we don't get warnings about
it being unused. */
extern void verify_flow_info PARAMS ((void));
! extern int flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
typedef struct conflict_graph_def *conflict_graph;
--- 679,702 ----
debugger, and it is declared extern so we don't get warnings about
it being unused. */
extern void verify_flow_info PARAMS ((void));
! extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
! extern bool flow_loop_nested_p PARAMS ((const struct loop *, const struct loop *));
! extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *, basic_block));
! extern basic_block *get_loop_body PARAMS ((const struct loop *));
! extern int dfs_enumerate_from PARAMS ((basic_block, int,
! bool (*)(basic_block, void *),
! basic_block *, int, void *));
!
! extern edge loop_preheader_edge PARAMS ((struct loop *));
! extern edge loop_latch_edge PARAMS ((struct loop *));
!
! extern void add_bb_to_loop PARAMS ((basic_block, struct loop *));
! extern void remove_bb_from_loops PARAMS ((basic_block));
! extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *));
!
! extern void verify_loop_structure PARAMS ((struct loops *, int));
! #define VLS_EXPECT_PREHEADERS 1
! #define VLS_EXPECT_SIMPLE_LATCHES 2
typedef struct conflict_graph_def *conflict_graph;
Index: cfg.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.23
diff -c -3 -p -r1.23 cfg.c
*** cfg.c 10 Apr 2002 00:15:58 -0000 1.23
--- cfg.c 9 May 2002 20:41:46 -0000
*************** struct basic_block_def entry_exit_blocks
*** 94,99 ****
--- 94,100 ----
NULL, /* aux */
ENTRY_BLOCK, /* index */
0, /* loop_depth */
+ NULL, /* loop_father */
0, /* count */
0, /* frequency */
0 /* flags */
*************** struct basic_block_def entry_exit_blocks
*** 112,117 ****
--- 113,119 ----
NULL, /* aux */
EXIT_BLOCK, /* index */
0, /* loop_depth */
+ NULL, /* loop_father */
0, /* count */
0, /* frequency */
0 /* flags */
Index: cfgloop.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.6
diff -c -3 -p -r1.6 cfgloop.c
*** cfgloop.c 20 Jan 2002 09:32:27 -0000 1.6
--- cfgloop.c 9 May 2002 20:41:46 -0000
*************** Software Foundation, 59 Temple Place - S
*** 23,46 ****
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
static void flow_loops_cfg_dump PARAMS ((const struct loops *,
FILE *));
! static int flow_loop_nested_p PARAMS ((struct loop *,
! struct loop *));
! static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
! edge **));
! static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **));
! static int flow_loop_nodes_find PARAMS ((basic_block, basic_block,
! sbitmap));
static void flow_loop_pre_header_scan PARAMS ((struct loop *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
const sbitmap *));
! static void flow_loop_tree_node_add PARAMS ((struct loop *,
! struct loop *));
! static void flow_loops_tree_build PARAMS ((struct loops *));
! static int flow_loop_level_compute PARAMS ((struct loop *, int));
static int flow_loops_level_compute PARAMS ((struct loops *));
/* Dump loop related CFG information. */
--- 23,51 ----
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+ #include "toplev.h"
+
+ /* Ratio of frequencies of edges so that one of more latch edges is
+ considered to belong to inner loop with same header. */
+ #define HEAVY_EDGE_RATIO 8
static void flow_loops_cfg_dump PARAMS ((const struct loops *,
FILE *));
! static void flow_loop_entry_edges_find PARAMS ((struct loop *));
! static void flow_loop_exit_edges_find PARAMS ((struct loop *));
! static int flow_loop_nodes_find PARAMS ((basic_block, struct loop *));
static void flow_loop_pre_header_scan PARAMS ((struct loop *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
const sbitmap *));
! static int flow_loop_level_compute PARAMS ((struct loop *));
static int flow_loops_level_compute PARAMS ((struct loops *));
+ static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
+ edge, int));
+ static void canonicalize_loop_headers PARAMS ((void));
+ static bool glb_enum_p PARAMS ((basic_block, void *));
+ static void redirect_edge_with_latch_update PARAMS ((edge, basic_block));
+ static void flow_loop_free PARAMS ((struct loop *));
+
/* Dump loop related CFG information. */
*************** flow_loops_cfg_dump (loops, file)
*** 61,67 ****
fprintf (file, ";; %d succs { ", i);
for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
fprintf (file, "%d ", succ->dest->index);
! flow_nodes_print ("} dom", loops->cfg.dom[i], file);
}
/* Dump the DFS node order. */
--- 66,72 ----
fprintf (file, ";; %d succs { ", i);
for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
fprintf (file, "%d ", succ->dest->index);
! fprintf (file, "}\n");
}
/* Dump the DFS node order. */
*************** flow_loops_cfg_dump (loops, file)
*** 85,98 ****
}
}
! /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
! static int
flow_loop_nested_p (outer, loop)
! struct loop *outer;
! struct loop *loop;
{
! return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
}
/* Dump the loop information specified by LOOP to the stream FILE
--- 90,104 ----
}
}
! /* Return non-zero if the LOOP is a subset of OUTER. */
! bool
flow_loop_nested_p (outer, loop)
! const struct loop *outer;
! const struct loop *loop;
{
! return loop->depth > outer->depth
! && loop->pred[outer->depth] == outer;
}
/* Dump the loop information specified by LOOP to the stream FILE
*************** flow_loop_dump (loop, file, loop_dump_au
*** 105,126 ****
void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
if (! loop || ! loop->header)
return;
! if (loop->first->head && loop->last->end)
! fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
! loop->num, INSN_UID (loop->first->head),
! INSN_UID (loop->last->end),
! loop->shared ? " shared" : "", loop->invalid ? " invalid" : "");
! else
! fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num,
! loop->shared ? " shared" : "", loop->invalid ? " invalid" : "");
! fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
loop->header->index, loop->latch->index,
! loop->pre_header ? loop->pre_header->index : -1,
! loop->first->index, loop->last->index);
fprintf (file, ";; depth %d, level %d, outer %ld\n",
loop->depth, loop->level,
(long) (loop->outer ? loop->outer->num : -1));
--- 111,128 ----
void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
+ basic_block *bbs;
+ int i;
+
if (! loop || ! loop->header)
return;
! fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
! loop->invalid ? " invalid" : "");
! fprintf (file, ";; header %d, latch %d, pre-header %d\n",
loop->header->index, loop->latch->index,
! loop->pre_header ? loop->pre_header->index : -1);
fprintf (file, ";; depth %d, level %d, outer %ld\n",
loop->depth, loop->level,
(long) (loop->outer ? loop->outer->num : -1));
*************** flow_loop_dump (loop, file, loop_dump_au
*** 131,144 ****
flow_edge_list_print (";; entry edges", loop->entry_edges,
loop->num_entries, file);
! fprintf (file, ";; %d", loop->num_nodes);
! flow_nodes_print (" nodes", loop->nodes, file);
flow_edge_list_print (";; exit edges", loop->exit_edges,
loop->num_exits, file);
- if (loop->exits_doms)
- flow_nodes_print (";; exit doms", loop->exits_doms, file);
-
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
--- 133,147 ----
flow_edge_list_print (";; entry edges", loop->entry_edges,
loop->num_entries, file);
! fprintf (file, ";; nodes:");
! bbs = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! fprintf (file, " %d", bbs[i]->index);
! free (bbs);
! fprintf (file, "\n");
flow_edge_list_print (";; exit edges", loop->exit_edges,
loop->num_exits, file);
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
*************** flow_loops_dump (loops, file, loop_dump_
*** 153,207 ****
void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
! int i, j;
int num_loops;
num_loops = loops->num;
if (! num_loops || ! file)
return;
! fprintf (file, ";; %d loops found, %d levels\n", num_loops, loops->levels);
for (i = 0; i < num_loops; i++)
{
! struct loop *loop = &loops->array[i];
! flow_loop_dump (loop, file, loop_dump_aux, verbose);
! if (loop->shared)
! for (j = 0; j < i; j++)
! {
! struct loop *oloop = &loops->array[j];
! if (loop->header == oloop->header)
! {
! int disjoint;
! int smaller;
!
! smaller = loop->num_nodes < oloop->num_nodes;
!
! /* If the union of LOOP and OLOOP is different than
! the larger of LOOP and OLOOP then LOOP and OLOOP
! must be disjoint. */
! disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
! smaller ? oloop : loop);
! fprintf (file,
! ";; loop header %d shared by loops %d, %d %s\n",
! loop->header->index, i, j,
! disjoint ? "disjoint" : "nested");
! }
! }
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
/* Free all the memory allocated for LOOPS. */
void
flow_loops_free (loops)
struct loops *loops;
{
! if (loops->array)
{
int i;
--- 156,208 ----
void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
! int i;
int num_loops;
num_loops = loops->num;
if (! num_loops || ! file)
return;
! fprintf (file, ";; %d loops found, %d levels\n",
! num_loops, loops->levels);
!
for (i = 0; i < num_loops; i++)
{
! struct loop *loop = loops->parray[i];
! if (!loop)
! continue;
! flow_loop_dump (loop, file, loop_dump_aux, verbose);
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
+ /* Free data allocated for LOOP. */
+ static void
+ flow_loop_free (loop)
+ struct loop *loop;
+ {
+ if (loop->pre_header_edges)
+ free (loop->pre_header_edges);
+ if (loop->entry_edges)
+ free (loop->entry_edges);
+ if (loop->exit_edges)
+ free (loop->exit_edges);
+ if (loop->pred)
+ free (loop->pred);
+ free (loop);
+ }
+
/* Free all the memory allocated for LOOPS. */
void
flow_loops_free (loops)
struct loops *loops;
{
! if (loops->parray)
{
int i;
*************** flow_loops_free (loops)
*** 211,390 ****
/* Free the loop descriptors. */
for (i = 0; i < loops->num; i++)
{
! struct loop *loop = &loops->array[i];
! if (loop->pre_header_edges)
! free (loop->pre_header_edges);
! if (loop->nodes)
! sbitmap_free (loop->nodes);
! if (loop->entry_edges)
! free (loop->entry_edges);
! if (loop->exit_edges)
! free (loop->exit_edges);
! if (loop->exits_doms)
! sbitmap_free (loop->exits_doms);
}
! free (loops->array);
! loops->array = NULL;
if (loops->cfg.dom)
sbitmap_vector_free (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
- if (loops->shared_headers)
- sbitmap_free (loops->shared_headers);
}
}
! /* Find the entry edges into the loop with header HEADER and nodes
! NODES and store in ENTRY_EDGES array. Return the number of entry
! edges from the loop. */
! static int
! flow_loop_entry_edges_find (header, nodes, entry_edges)
! basic_block header;
! const sbitmap nodes;
! edge **entry_edges;
{
edge e;
int num_entries;
- *entry_edges = NULL;
-
num_entries = 0;
! for (e = header->pred; e; e = e->pred_next)
{
! basic_block src = e->src;
!
! if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
num_entries++;
}
if (! num_entries)
abort ();
! *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge));
num_entries = 0;
! for (e = header->pred; e; e = e->pred_next)
{
! basic_block src = e->src;
!
! if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
! (*entry_edges)[num_entries++] = e;
}
! return num_entries;
}
! /* Find the exit edges from the loop using the bitmap of loop nodes
! NODES and store in EXIT_EDGES array. Return the number of
! exit edges from the loop. */
! static int
! flow_loop_exit_edges_find (nodes, exit_edges)
! const sbitmap nodes;
! edge **exit_edges;
{
edge e;
! int node;
! int num_exits;
! *exit_edges = NULL;
/* Check all nodes within the loop to see if there are any
successors not in the loop. Note that a node may have multiple
exiting edges ????? A node can have one jumping edge and one fallthru
edge so only one of these can exit the loop. */
num_exits = 0;
! EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
! for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
! {
! basic_block dest = e->dest;
! if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
num_exits++;
! }
! });
if (! num_exits)
! return 0;
! *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge));
/* Store all exiting edges into an array. */
num_exits = 0;
! EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
! for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
! {
! basic_block dest = e->dest;
! if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
! (*exit_edges)[num_exits++] = e;
}
! });
!
! return num_exits;
}
! /* Find the nodes contained within the loop with header HEADER and
! latch LATCH and store in NODES. Return the number of nodes within
! the loop. */
static int
! flow_loop_nodes_find (header, latch, nodes)
basic_block header;
! basic_block latch;
! sbitmap nodes;
{
basic_block *stack;
int sp;
! int num_nodes = 0;
!
! stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
! sp = 0;
! /* Start with only the loop header in the set of loop nodes. */
! sbitmap_zero (nodes);
! SET_BIT (nodes, header->index);
! num_nodes++;
! header->loop_depth++;
! /* Push the loop latch on to the stack. */
! if (! TEST_BIT (nodes, latch->index))
{
! SET_BIT (nodes, latch->index);
! latch->loop_depth++;
num_nodes++;
! stack[sp++] = latch;
! }
!
! while (sp)
! {
! basic_block node;
! edge e;
!
! node = stack[--sp];
! for (e = node->pred; e; e = e->pred_next)
{
! basic_block ancestor = e->src;
! /* If each ancestor not marked as part of loop, add to set of
! loop nodes and push on to stack. */
! if (ancestor != ENTRY_BLOCK_PTR
! && ! TEST_BIT (nodes, ancestor->index))
{
! SET_BIT (nodes, ancestor->index);
! ancestor->loop_depth++;
! num_nodes++;
! stack[sp++] = ancestor;
}
}
}
- free (stack);
return num_nodes;
}
--- 212,375 ----
/* Free the loop descriptors. */
for (i = 0; i < loops->num; i++)
{
! struct loop *loop = loops->parray[i];
! if (!loop)
! continue;
!
! flow_loop_free (loop);
}
! free (loops->parray);
! loops->parray = NULL;
if (loops->cfg.dom)
sbitmap_vector_free (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
+ if (loops->cfg.rc_order)
+ free (loops->cfg.rc_order);
}
}
! /* Find the entry edges into the LOOP. */
! static void
! flow_loop_entry_edges_find (loop)
! struct loop *loop;
{
edge e;
int num_entries;
num_entries = 0;
! for (e = loop->header->pred; e; e = e->pred_next)
{
! if (flow_loop_outside_edge_p (loop, e))
num_entries++;
}
if (! num_entries)
abort ();
! loop->entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
num_entries = 0;
! for (e = loop->header->pred; e; e = e->pred_next)
{
! if (flow_loop_outside_edge_p (loop, e))
! loop->entry_edges[num_entries++] = e;
}
! loop->num_entries = num_entries;
}
! /* Find the exit edges from the LOOP. */
! static void
! flow_loop_exit_edges_find (loop)
! struct loop *loop;
{
edge e;
! basic_block node, *bbs;
! int num_exits, i;
! loop->exit_edges = NULL;
! loop->num_exits = 0;
/* Check all nodes within the loop to see if there are any
successors not in the loop. Note that a node may have multiple
exiting edges ????? A node can have one jumping edge and one fallthru
edge so only one of these can exit the loop. */
num_exits = 0;
! bbs = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! {
! node = bbs[i];
! for (e = node->succ; e; e = e->succ_next)
! {
! basic_block dest = e->dest;
! if (!flow_bb_inside_loop_p (loop, dest))
num_exits++;
! }
! }
if (! num_exits)
! {
! free (bbs);
! return;
! }
! loop->exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *));
/* Store all exiting edges into an array. */
num_exits = 0;
! for (i = 0; i < loop->num_nodes; i++)
! {
! node = bbs[i];
! for (e = node->succ; e; e = e->succ_next)
! {
! basic_block dest = e->dest;
! if (!flow_bb_inside_loop_p (loop, dest))
! loop->exit_edges[num_exits++] = e;
}
! }
! free (bbs);
! loop->num_exits = num_exits;
}
! /* Find the nodes contained within the LOOP with header HEADER.
! Return the number of nodes within the loop. */
static int
! flow_loop_nodes_find (header, loop)
basic_block header;
! struct loop *loop;
{
basic_block *stack;
int sp;
! int num_nodes = 1;
! int findex, lindex;
! header->loop_father = loop;
! header->loop_depth = loop->depth;
! findex = lindex = header->index;
! if (loop->latch->loop_father != loop)
{
! stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
! sp = 0;
num_nodes++;
! stack[sp++] = loop->latch;
! loop->latch->loop_father = loop;
! loop->latch->loop_depth = loop->depth;
!
! while (sp)
{
! basic_block node;
! edge e;
! node = stack[--sp];
!
! for (e = node->pred; e; e = e->pred_next)
{
! basic_block ancestor = e->src;
!
! if (ancestor != ENTRY_BLOCK_PTR
! && ancestor->loop_father != loop)
! {
! ancestor->loop_father = loop;
! ancestor->loop_depth = loop->depth;
! num_nodes++;
! stack[sp++] = ancestor;
! }
}
}
+ free (stack);
}
return num_nodes;
}
*************** flow_loop_pre_header_find (header, dom)
*** 461,518 ****
return pre_header;
}
! /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
! previously added. The insertion algorithm assumes that the loops
! are added in the order found by a depth first search of the CFG. */
! static void
! flow_loop_tree_node_add (prevloop, loop)
! struct loop *prevloop;
struct loop *loop;
{
!
! if (flow_loop_nested_p (prevloop, loop))
! {
! prevloop->inner = loop;
! loop->outer = prevloop;
! return;
! }
!
! for (; prevloop->outer; prevloop = prevloop->outer)
! if (flow_loop_nested_p (prevloop->outer, loop))
! {
! prevloop->next = loop;
! loop->outer = prevloop->outer;
! return;
! }
!
! prevloop->next = loop;
! loop->outer = NULL;
}
! /* Build the loop hierarchy tree for LOOPS. */
! static void
! flow_loops_tree_build (loops)
! struct loops *loops;
{
! int i;
! int num_loops;
! num_loops = loops->num;
! if (! num_loops)
! return;
! /* Root the loop hierarchy tree with the first loop found.
! Since we used a depth first search this should be the
! outermost loop. */
! loops->tree_root = &loops->array[0];
! loops->tree_root->outer = loops->tree_root->inner
! = loops->tree_root->next = NULL;
!
! /* Add the remaining loops to the tree. */
! for (i = 1; i < num_loops; i++)
! flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
}
/* Helper function to compute loop nesting depth and enclosed loop level
--- 446,492 ----
return pre_header;
}
! /* Add LOOP to the loop hierarchy tree where FATHER is father of the
! added loop. */
! void
! flow_loop_tree_node_add (father, loop)
! struct loop *father;
struct loop *loop;
{
! loop->next = father->inner;
! father->inner = loop;
! loop->outer = father;
!
! loop->depth = father->depth + 1;
! loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
! memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
! loop->pred[father->depth] = father;
}
! /* Remove LOOP from the loop hierarchy tree. */
! void
! flow_loop_tree_node_remove (loop)
! struct loop *loop;
{
! struct loop *prev, *father;
! father = loop->outer;
! loop->outer = NULL;
!
! /* Remove loop from the list of sons. */
! if (father->inner == loop)
! father->inner = loop->next;
! else
! {
! for (prev = father->inner; prev->next != loop; prev = prev->next);
! prev->next = loop->next;
! }
! loop->depth = -1;
! free (loop->pred);
! loop->pred = NULL;
}
/* Helper function to compute loop nesting depth and enclosed loop level
*************** flow_loops_tree_build (loops)
*** 520,528 ****
Returns the loop level. */
static int
! flow_loop_level_compute (loop, depth)
struct loop *loop;
- int depth;
{
struct loop *inner;
int level = 1;
--- 494,501 ----
Returns the loop level. */
static int
! flow_loop_level_compute (loop)
struct loop *loop;
{
struct loop *inner;
int level = 1;
*************** flow_loop_level_compute (loop, depth)
*** 537,549 ****
itself). */
for (inner = loop->inner; inner; inner = inner->next)
{
! int ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
! level = MAX (ilevel, level);
}
loop->level = level;
- loop->depth = depth;
return level;
}
--- 510,522 ----
itself). */
for (inner = loop->inner; inner; inner = inner->next)
{
! int ilevel = flow_loop_level_compute (inner) + 1;
! if (ilevel > level)
! level = ilevel;
}
loop->level = level;
return level;
}
*************** static int
*** 555,572 ****
flow_loops_level_compute (loops)
struct loops *loops;
{
! int levels = 0;
! struct loop *loop;
! int level;
!
! /* Traverse all the outer level loops. */
! for (loop = loops->tree_root; loop; loop = loop->next)
! {
! level = flow_loop_level_compute (loop, 1);
! levels = MAX (levels, level);
! }
!
! return levels;
}
/* Scan a single natural loop specified by LOOP collecting information
--- 528,534 ----
flow_loops_level_compute (loops)
struct loops *loops;
{
! return flow_loop_level_compute (loops->tree_root);
}
/* Scan a single natural loop specified by LOOP collecting information
*************** flow_loop_scan (loops, loop, flags)
*** 578,614 ****
struct loop *loop;
int flags;
{
- /* Determine prerequisites. */
- if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
- flags |= LOOP_EXIT_EDGES;
-
if (flags & LOOP_ENTRY_EDGES)
! /* Find edges which enter the loop header. Note that the entry edges
! should only enter the header of a natural loop. */
! loop->num_entries = flow_loop_entry_edges_find (loop->header, loop->nodes,
! &loop->entry_edges);
if (flags & LOOP_EXIT_EDGES)
! /* Find edges which exit the loop. */
! loop->num_exits
! = flow_loop_exit_edges_find (loop->nodes, &loop->exit_edges);
!
! if (flags & LOOP_EXITS_DOMS)
! {
! int j;
!
! /* Determine which loop nodes dominate all the exits
! of the loop. */
! loop->exits_doms = sbitmap_alloc (n_basic_blocks);
! sbitmap_copy (loop->exits_doms, loop->nodes);
! for (j = 0; j < loop->num_exits; j++)
! sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
! loops->cfg.dom[loop->exit_edges[j]->src->index]);
!
! /* The header of a natural loop must dominate
! all exits. */
! if (! TEST_BIT (loop->exits_doms, loop->header->index))
! abort ();
}
if (flags & LOOP_PRE_HEADER)
--- 540,557 ----
struct loop *loop;
int flags;
{
if (flags & LOOP_ENTRY_EDGES)
! {
! /* Find edges which enter the loop header.
! Note that the entry edges should only
! enter the header of a natural loop. */
! flow_loop_entry_edges_find (loop);
! }
if (flags & LOOP_EXIT_EDGES)
! {
! /* Find edges which exit the loop. */
! flow_loop_exit_edges_find (loop);
}
if (flags & LOOP_PRE_HEADER)
*************** flow_loop_scan (loops, loop, flags)
*** 625,630 ****
--- 568,785 ----
return 1;
}
+ #define HEADER_BLOCK(B) (* (int *) (B)->aux)
+ #define LATCH_EDGE(E) (*(int *) (E)->aux)
+
+ /* Redirect edge and update latch and header info. */
+ static void
+ redirect_edge_with_latch_update (e, to)
+ 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;
+ }
+ }
+
+ /* 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
+ make_forwarder_block (bb, redirect_latch, redirect_nonlatch, except,
+ conn_latch)
+ basic_block bb;
+ int redirect_latch;
+ int redirect_nonlatch;
+ edge except;
+ int conn_latch;
+ {
+ edge e, next_e, fallthru;
+ basic_block dummy;
+ rtx insn;
+
+ insn = PREV_INSN (first_insn_after_basic_block_note (bb));
+
+ fallthru = split_block (bb, insn);
+ 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;
+ }
+
+ /* Takes care of merging natural loops with shared headers. */
+ static void
+ canonicalize_loop_headers ()
+ {
+ sbitmap *dom;
+ basic_block header;
+ edge e;
+ int b;
+
+ /* Compute the dominators. */
+ dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+
+ alloc_aux_for_blocks (sizeof (int));
+ alloc_aux_for_edges (sizeof (int));
+
+ /* Split blocks so that each loop has only single latch. */
+ for (b = 0; b < n_basic_blocks; b++)
+ {
+ int num_latches = 0;
+ int have_abnormal_edge = 0;
+
+ header = BASIC_BLOCK (b);
+
+ for (e = header->pred; e; e = e->pred_next)
+ {
+ basic_block latch = e->src;
+
+ if (e->flags & EDGE_ABNORMAL)
+ have_abnormal_edge = 1;
+
+ if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
+ {
+ num_latches++;
+ LATCH_EDGE (e) = 1;
+ }
+ }
+ if (have_abnormal_edge)
+ HEADER_BLOCK (header) = 0;
+ else
+ HEADER_BLOCK (header) = num_latches;
+ }
+
+ if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
+ {
+ rtx insn;
+ edge fallthru, next_e;
+ basic_block bb;
+ /* We could not redirect edges freely here. On the other hand,
+ we know that no abnormal edge enters this block, so we can simply
+ split it into two... */
+ bb = ENTRY_BLOCK_PTR->succ->dest;
+ insn = PREV_INSN (first_insn_after_basic_block_note (bb));
+ fallthru = split_block (bb, insn);
+
+ /* And redirect all edges to second part. */
+ for (e = fallthru->src->pred; e; e = next_e)
+ {
+ next_e = e->pred_next;
+ if (e->src == ENTRY_BLOCK_PTR)
+ continue;
+ fallthru->src->frequency -= EDGE_FREQUENCY (e);
+ fallthru->src->count -= e->count;
+ if (fallthru->src->frequency < 0)
+ fallthru->src->frequency = 0;
+ if (fallthru->src->count < 0)
+ fallthru->src->count = 1;
+ redirect_edge_with_latch_update (e, fallthru->dest);
+ }
+ alloc_aux_for_edge (fallthru, sizeof (int));
+ LATCH_EDGE (fallthru) = 0;
+ alloc_aux_for_block (fallthru->dest, sizeof (int));
+ HEADER_BLOCK (fallthru->dest) = HEADER_BLOCK (fallthru->src);
+ HEADER_BLOCK (fallthru->src) = 0;
+ }
+
+ for (b = 0; b < n_basic_blocks; )
+ {
+ int num_latch;
+ int want_join_latch;
+ int max_freq, is_heavy;
+ edge heavy;
+
+ header = BASIC_BLOCK (b);
+ if (!HEADER_BLOCK (header))
+ {
+ b++;
+ continue;
+ }
+
+ num_latch = HEADER_BLOCK (header);
+
+ want_join_latch = (num_latch > 1);
+
+ if (!want_join_latch)
+ {
+ b++;
+ continue;
+ }
+
+ /* Find a heavy edge. */
+ is_heavy = 1;
+ heavy = NULL;
+ max_freq = 0;
+ for (e = header->pred; e; e = e->pred_next)
+ if (LATCH_EDGE (e) &&
+ EDGE_FREQUENCY (e) > max_freq)
+ max_freq = EDGE_FREQUENCY (e);
+ for (e = header->pred; e; e = e->pred_next)
+ if (LATCH_EDGE (e) &&
+ EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
+ {
+ if (heavy)
+ {
+ is_heavy = 0;
+ break;
+ }
+ else
+ heavy = e;
+ }
+
+ 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 ();
+ free_aux_for_edges ();
+ sbitmap_vector_free (dom);
+ }
+
/* Find all the natural loops in the function and save in LOOPS structure and
recalculate loop_depth information in basic block structures. FLAGS
controls which loop information is collected. Return the number of natural
*************** flow_loops_find (loops, flags)
*** 643,648 ****
--- 798,804 ----
sbitmap *dom;
int *dfs_order;
int *rc_order;
+ basic_block header;
/* This function cannot be repeatedly called with different
flags to build up the loop information. The loop tree
*************** flow_loops_find (loops, flags)
*** 660,676 ****
dfs_order = NULL;
rc_order = NULL;
/* Compute the dominators. */
! dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
! /* Count the number of loop edges (back edges). This should be the
same as the number of natural loops. */
num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
! basic_block header;
!
header = BASIC_BLOCK (b);
header->loop_depth = 0;
--- 816,838 ----
dfs_order = NULL;
rc_order = NULL;
+ /* Join loops with shared headers. */
+ canonicalize_loop_headers ();
+
/* Compute the dominators. */
! loops->cfg.dom = dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
! /* Count the number of loop headers. This should be the
same as the number of natural loops. */
+ headers = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (headers);
+
num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
! int more_latches = 0;
!
header = BASIC_BLOCK (b);
header->loop_depth = 0;
*************** flow_loops_find (loops, flags)
*** 678,697 ****
{
basic_block latch = e->src;
/* Look for back edges where a predecessor is dominated
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
! from a latch node. Note that multiple natural loops
! may share the same header. */
! if (b != header->index)
! abort ();
!
if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
! num_loops++;
}
}
if (num_loops)
{
/* Compute depth first search order of the CFG so that outer
--- 840,896 ----
{
basic_block latch = e->src;
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ if (more_latches)
+ {
+ RESET_BIT (headers, b);
+ num_loops--;
+ }
+ break;
+ }
+
/* Look for back edges where a predecessor is dominated
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
! from a latch node. */
if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
! {
! /* Shared headers should be eliminated by now. */
! if (more_latches)
! abort ();
! more_latches = 1;
! SET_BIT (headers, b);
! num_loops++;
! }
}
}
+ /* Allocate loop structures. */
+ loops->parray = (struct loop **) xcalloc (num_loops + 1, sizeof (struct loop *));
+
+ /* Dummy loop containing whole function. */
+ loops->parray[0] = xcalloc (1, sizeof (struct loop));
+ loops->parray[0]->next = NULL;
+ loops->parray[0]->inner = NULL;
+ loops->parray[0]->outer = NULL;
+ loops->parray[0]->depth = 0;
+ loops->parray[0]->pred = NULL;
+ loops->parray[0]->num_nodes = n_basic_blocks + 2;
+ loops->parray[0]->latch = EXIT_BLOCK_PTR;
+ loops->parray[0]->header = ENTRY_BLOCK_PTR;
+ ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
+ EXIT_BLOCK_PTR->loop_father = loops->parray[0];
+
+ loops->tree_root = loops->parray[0];
+
+ /* Find and record information about all the natural loops
+ in the CFG. */
+ loops->num = 1;
+ for (b = 0; b<n_basic_blocks; b++)
+ BASIC_BLOCK (b)->loop_father = loops->tree_root;
+
if (num_loops)
{
/* Compute depth first search order of the CFG so that outer
*************** flow_loops_find (loops, flags)
*** 705,808 ****
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
! /* Allocate loop structures. */
! loops->array
! = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
!
! headers = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (headers);
!
! loops->shared_headers = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (loops->shared_headers);
!
! /* Find and record information about all the natural loops
! in the CFG. */
! num_loops = 0;
! for (b = n_basic_blocks - 1; b >= 0; b--)
{
! basic_block latch;
/* Search the nodes of the CFG in reverse completion order
so that we can find outer loops first. */
! latch = BASIC_BLOCK (rc_order[b]);
! /* Look for all the possible headers for this latch block. */
! for (e = latch->succ; e; e = e->succ_next)
{
! basic_block header = e->dest;
! /* Look for forward edges where this block is dominated by
! a successor of this block. A natural loop has a single
! entry node (header) that dominates all the nodes in the
! loop. It also has single back edge to the header from a
! latch node. Note that multiple natural loops may share
! the same header. */
! if (header != EXIT_BLOCK_PTR
&& TEST_BIT (dom[latch->index], header->index))
{
- struct loop *loop;
-
- loop = loops->array + num_loops;
-
- loop->header = header;
loop->latch = latch;
! loop->num = num_loops;
!
! num_loops++;
}
}
}
! for (i = 0; i < num_loops; i++)
! {
! struct loop *loop = &loops->array[i];
! /* Keep track of blocks that are loop headers so
! that we can tell which loops should be merged. */
! if (TEST_BIT (headers, loop->header->index))
! SET_BIT (loops->shared_headers, loop->header->index);
! SET_BIT (headers, loop->header->index);
!
! /* Find nodes contained within the loop. */
! loop->nodes = sbitmap_alloc (n_basic_blocks);
! loop->num_nodes
! = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
!
! /* Compute first and last blocks within the loop.
! These are often the same as the loop header and
! loop latch respectively, but this is not always
! the case. */
! loop->first
! = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
! loop->last
! = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
!
! flow_loop_scan (loops, loop, flags);
! }
!
! /* Natural loops with shared headers may either be disjoint or
! nested. Disjoint loops with shared headers cannot be inner
! loops and should be merged. For now just mark loops that share
! headers. */
! for (i = 0; i < num_loops; i++)
! if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
! loops->array[i].shared = 1;
! sbitmap_free (headers);
}
else
! sbitmap_vector_free (dom);
!
! loops->num = num_loops;
!
! /* Build the loop hierarchy tree. */
! flow_loops_tree_build (loops);
!
! /* Assign the loop nesting depth and enclosed loop level for each
! loop. */
! loops->levels = flow_loops_level_compute (loops);
! return num_loops;
}
/* Update the information regarding the loops in the CFG
--- 904,967 ----
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
! num_loops = 1;
!
! for (b = 0; b < n_basic_blocks; b++)
{
! struct loop *loop;
/* Search the nodes of the CFG in reverse completion order
so that we can find outer loops first. */
! if (!TEST_BIT (headers, rc_order[b]))
! continue;
! header = BASIC_BLOCK (rc_order[b]);
!
! loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
!
! loop->header = header;
! loop->num = num_loops;
! num_loops++;
!
! /* Look for the latch for this header block. */
! for (e = header->pred; e; e = e->pred_next)
{
! basic_block latch = e->src;
! if (latch != ENTRY_BLOCK_PTR
&& TEST_BIT (dom[latch->index], header->index))
{
loop->latch = latch;
! break;
}
}
+
+ flow_loop_tree_node_add (header->loop_father, loop);
+ loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
}
! sbitmap_free (headers);
! /* Assign the loop nesting depth and enclosed loop level for each
! loop. */
! loops->levels = flow_loops_level_compute (loops);
!
! /* Scan the loops. */
! for (i = 1; i < num_loops; i++)
! flow_loop_scan (loops, loops->parray[i], flags);
! loops->num = num_loops;
}
else
! {
! loops->cfg.dom = NULL;
! sbitmap_vector_free (dom);
! }
! #ifdef ENABLE_CHECKING
! verify_flow_info ();
! #endif
! return loops->num;
}
/* Update the information regarding the loops in the CFG
*************** flow_loops_update (loops, flags)
*** 815,836 ****
{
/* One day we may want to update the current loop data. For now
throw away the old stuff and rebuild what we need. */
! if (loops->array)
flow_loops_free (loops);
return flow_loops_find (loops, flags);
}
/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
! int
flow_loop_outside_edge_p (loop, e)
const struct loop *loop;
edge e;
{
if (e->dest != loop->header)
abort ();
! return (e->src == ENTRY_BLOCK_PTR)
! || ! TEST_BIT (loop->nodes, e->src->index);
}
--- 974,1222 ----
{
/* One day we may want to update the current loop data. For now
throw away the old stuff and rebuild what we need. */
! if (loops->parray)
flow_loops_free (loops);
return flow_loops_find (loops, flags);
}
+ /* Return non-zero if basic block BB belongs to LOOP. */
+ bool
+ flow_bb_inside_loop_p (loop, bb)
+ const struct loop *loop;
+ const basic_block bb;
+ {
+ struct loop *source_loop;
+ if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) return 0;
+ source_loop = bb->loop_father;
+ return loop == source_loop || flow_loop_nested_p (loop, source_loop);
+ }
+
/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
! bool
flow_loop_outside_edge_p (loop, e)
const struct loop *loop;
edge e;
{
if (e->dest != loop->header)
abort ();
+ return !flow_bb_inside_loop_p (loop, e->src);
+ }
+
+ /* Enumeration predicate for get_loop_body. */
+ static bool
+ glb_enum_p (bb, glb_header)
+ basic_block bb;
+ void *glb_header;
+ {
+ return bb != (basic_block) glb_header;
+ }
+
+ /* Gets basic blocks of a loop. */
+ basic_block *
+ get_loop_body (loop)
+ const struct loop *loop;
+ {
+ basic_block *tovisit;
+ int tv = 0, i;
+ if (!loop->num_nodes)
+ abort ();
+ tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
+ tovisit[tv++] = loop->header;
+ if (loop->latch == EXIT_BLOCK_PTR)
+ {
+ /* There may be blocks unreachable from EXIT_BLOCK. */
+ if (loop->num_nodes != n_basic_blocks + 2)
+ abort ();
+ for (i = 0; i < n_basic_blocks; i++)
+ tovisit[tv++] = BASIC_BLOCK(i);
+ tovisit[tv++] = EXIT_BLOCK_PTR;
+ }
+ else if (loop->latch != loop->header)
+ {
+ tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
+ tovisit + 1, loop->num_nodes - 1,
+ loop->header) + 1;
+ }
+ if (tv != loop->num_nodes)
+ abort ();
+ return tovisit;
+ }
+
+ /* Adds basic block BB to LOOP. */
+ void
+ add_bb_to_loop (bb, loop)
+ basic_block bb;
+ struct loop *loop;
+ {
+ int i;
+ bb->loop_father = loop;
+ bb->loop_depth = loop->depth;
+ loop->num_nodes++;
+ for (i = 0; i < loop->depth; i++)
+ loop->pred[i]->num_nodes++;
+ }
! /* Remove basic block BB from loops. */
! void
! remove_bb_from_loops (bb)
! basic_block bb;
! {
! int i;
! struct loop *loop = bb->loop_father;
! loop->num_nodes--;
! for (i = 0; i < loop->depth; i++)
! loop->pred[i]->num_nodes--;
! bb->loop_father = NULL;
! bb->loop_depth = 0;
! }
!
! /* Finds nearest common ancestor in loop tree for given loops. */
! struct loop *
! find_common_loop (loop_s, loop_d)
! struct loop *loop_s;
! struct loop *loop_d;
! {
! if (!loop_s) return loop_d;
! if (!loop_d) return loop_s;
! if (loop_s->depth < loop_d->depth)
! loop_d = loop_d->pred[loop_s->depth];
! else if (loop_s->depth > loop_d->depth)
! loop_s = loop_s->pred[loop_d->depth];
! while (loop_s != loop_d)
! {
! loop_s = loop_s->outer;
! loop_d = loop_d->outer;
! }
! return loop_s;
}
+
+ /* Checks that LOOPS are allright:
+ -- sizes of loops are allright
+ -- results of get_loop_body really belong to the loop
+ -- loop header have just single entry edge and single latch edge
+ -- loop latches have only single successor that is header of their loop
+ -- sanity of frequencies */
+ void verify_loop_structure (loops, flags)
+ struct loops *loops;
+ int flags;
+ {
+ int *sizes, i, j;
+ basic_block *bbs;
+ struct loop *loop;
+ int err = 0;
+
+ /* Check sizes. */
+ sizes = xcalloc (loops->num, sizeof (int));
+ sizes[0] = 2;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ for (loop = BASIC_BLOCK (i)->loop_father; loop; loop = loop->outer)
+ sizes[loop->num]++;
+
+ for (i = 0; i < loops->num; i++)
+ {
+ if (!loops->parray[i])
+ continue;
+
+ if (loops->parray[i]->num_nodes != sizes[i])
+ {
+ error ("Size of loop %d should be %d, not %d.",
+ i, sizes[i], loops->parray[i]->num_nodes);
+ err = 1;
+ }
+ }
+
+ free (sizes);
+
+ /* Check get_loop_body. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+ bbs = get_loop_body (loop);
+
+ for (j = 0; j < loop->num_nodes; j++)
+ if (!flow_bb_inside_loop_p (loop, bbs[j]))
+ {
+ error ("Bb %d do not belong to loop %d.",
+ bbs[j]->index, i);
+ err = 1;
+ }
+ free (bbs);
+ }
+
+ /* Check headers and latches. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if ((flags & VLS_EXPECT_PREHEADERS)
+ && (!loop->header->pred->pred_next
+ || loop->header->pred->pred_next->pred_next))
+ {
+ error ("Loop %d's header does not have exactly 2 entries.", i);
+ err = 1;
+ }
+ if (flags & VLS_EXPECT_SIMPLE_LATCHES)
+ {
+ if (!loop->latch->succ
+ || loop->latch->succ->succ_next)
+ {
+ error ("Loop %d's latch does not have exactly 1 successor.", i);
+ err = 1;
+ }
+ if (loop->latch->succ->dest != loop->header)
+ {
+ error ("Loop %d's latch does not have header as successor.", i);
+ err = 1;
+ }
+ if (loop->latch->loop_father != loop)
+ {
+ error ("Loop %d's latch does not belong directly to it.", i);
+ err = 1;
+ }
+ }
+ if (loop->header->loop_father != loop)
+ {
+ error ("Loop %d's header does not belong directly to it.", i);
+ err = 1;
+ }
+ }
+
+ /* Check frequencies. */
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK(i)->frequency < 0)
+ {
+ error ("Basic block %d has negative frequency.", i);
+ err = 1;
+ }
+
+ if (err)
+ abort ();
+ }
+
+ edge
+ loop_latch_edge (loop)
+ struct loop *loop;
+ {
+ edge e;
+
+ for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next);
+ return e;
+ }
+
+ edge
+ loop_preheader_edge (loop)
+ struct loop *loop;
+ {
+ edge e;
+
+ for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next);
+ return e;
+ }
+
Index: predict.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/predict.c,v
retrieving revision 1.62
diff -c -3 -p -r1.62 predict.c
*** predict.c 8 May 2002 09:17:19 -0000 1.62
--- predict.c 9 May 2002 20:41:46 -0000
*************** static void combine_predictions_for_insn
*** 67,73 ****
static void dump_prediction PARAMS ((enum br_predictor, int,
basic_block, int));
static void estimate_loops_at_level PARAMS ((struct loop *loop));
! static void propagate_freq PARAMS ((basic_block));
static void estimate_bb_frequencies PARAMS ((struct loops *));
static void counts_to_freqs PARAMS ((void));
static void process_note_predictions PARAMS ((basic_block, int *, int *,
--- 67,73 ----
static void dump_prediction PARAMS ((enum br_predictor, int,
basic_block, int));
static void estimate_loops_at_level PARAMS ((struct loop *loop));
! static void propagate_freq PARAMS ((struct loop *));
static void estimate_bb_frequencies PARAMS ((struct loops *));
static void counts_to_freqs PARAMS ((void));
static void process_note_predictions PARAMS ((basic_block, int *, int *,
*************** estimate_probability (loops_info)
*** 365,414 ****
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
! for (i = 0; i < loops_info->num; i++)
{
int j;
int exits;
! struct loop *loop = &loops_info->array[i];
flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! for (j = loop->first->index; j <= loop->last->index; ++j)
! if (TEST_BIT (loop->nodes, j))
! {
! int header_found = 0;
! edge e;
/* Bypass loop heuristics on continue statement. These
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if (predicted_by_p (BASIC_BLOCK (j), PRED_CONTINUE))
continue;
! /* Loop branch heuristics - predict an edge back to a
! loop's head as taken. */
! for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
! if (e->dest == loop->header
! && e->src == loop->latch)
! {
! header_found = 1;
! predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
! }
!
! /* Loop exit heuristics - predict an edge exiting the loop if the
! conditinal has no loop header successors as not taken. */
! if (!header_found)
! for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
! if (e->dest->index < 0
! || !TEST_BIT (loop->nodes, e->dest->index))
! predict_edge
! (e, PRED_LOOP_EXIT,
! (REG_BR_PROB_BASE
! - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
! / exits);
! }
}
/* Attempt to predict conditional jumps using a number of heuristics. */
--- 365,417 ----
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
! for (i = 1; i < loops_info->num; i++)
{
+ basic_block bb, *bbs;
int j;
int exits;
! struct loop *loop = loops_info->parray[i];
flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! bbs = get_loop_body (loop);
! for (j = 0; j < loop->num_nodes; j++)
! {
! int header_found = 0;
! edge e;
!
! bb = bbs[j];
/* Bypass loop heuristics on continue statement. These
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if (predicted_by_p (bb, PRED_CONTINUE))
continue;
! /* Loop branch heuristics - predict an edge back to a
! loop's head as taken. */
! for (e = bb->succ; e; e = e->succ_next)
! if (e->dest == loop->header
! && e->src == loop->latch)
! {
! header_found = 1;
! predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
! }
!
! /* Loop exit heuristics - predict an edge exiting the loop if the
! conditinal has no loop header successors as not taken. */
! if (!header_found)
! for (e = bb->succ; e; e = e->succ_next)
! if (e->dest->index < 0
! || !flow_bb_inside_loop_p (loop, e->dest))
! predict_edge
! (e, PRED_LOOP_EXIT,
! (REG_BR_PROB_BASE
! - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
! / exits);
! }
}
/* Attempt to predict conditional jumps using a number of heuristics. */
*************** typedef struct edge_info_def
*** 844,857 ****
#define EDGE_INFO(E) ((edge_info) (E)->aux)
/* Helper function for estimate_bb_frequencies.
! Propagate the frequencies for loops headed by HEAD. */
static void
! propagate_freq (head)
! basic_block head;
{
! basic_block bb = head;
! basic_block last = bb;
edge e;
basic_block nextbb;
int n;
--- 847,861 ----
#define EDGE_INFO(E) ((edge_info) (E)->aux)
/* Helper function for estimate_bb_frequencies.
! Propagate the frequencies for LOOP. */
static void
! propagate_freq (loop)
! struct loop *loop;
{
! basic_block head = loop->header;
! basic_block bb;
! basic_block last;
edge e;
basic_block nextbb;
int n;
*************** propagate_freq (head)
*** 860,866 ****
we need to visit first. */
for (n = 0; n < n_basic_blocks; n++)
{
! basic_block bb = BASIC_BLOCK (n);
if (BLOCK_INFO (bb)->tovisit)
{
int count = 0;
--- 864,870 ----
we need to visit first. */
for (n = 0; n < n_basic_blocks; n++)
{
! bb = BASIC_BLOCK (n);
if (BLOCK_INFO (bb)->tovisit)
{
int count = 0;
*************** propagate_freq (head)
*** 878,884 ****
}
memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
! for (; bb; bb = nextbb)
{
REAL_VALUE_TYPE cyclic_probability, frequency;
--- 882,889 ----
}
memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
! last = head;
! for (bb = head; bb; bb = nextbb)
{
REAL_VALUE_TYPE cyclic_probability, frequency;
*************** static void
*** 977,1017 ****
estimate_loops_at_level (first_loop)
struct loop *first_loop;
{
! struct loop *l, *loop = first_loop;
for (loop = first_loop; loop; loop = loop->next)
{
- int n;
edge e;
estimate_loops_at_level (loop->inner);
!
! /* Find current loop back edge and mark it. */
! for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next)
! ;
!
! EDGE_INFO (e)->back_edge = 1;
!
! /* In case the loop header is shared, ensure that it is the last
! one sharing the same header, so we avoid redundant work. */
! if (loop->shared)
{
! for (l = loop->next; l; l = l->next)
! if (l->header == loop->header)
! break;
!
! if (l)
! continue;
! }
!
! /* Now merge all nodes of all loops with given header as not visited. */
! for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
! if (loop->header == l->header)
! EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
! BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
! );
!
! propagate_freq (loop->header);
}
}
--- 982,1009 ----
estimate_loops_at_level (first_loop)
struct loop *first_loop;
{
! struct loop *loop;
for (loop = first_loop; loop; loop = loop->next)
{
edge e;
+ basic_block *bbs;
+ int i;
estimate_loops_at_level (loop->inner);
!
! if (loop->latch->succ) /* Do not do this for dummy function loop. */
{
! /* Find current loop back edge and mark it. */
! e = loop_latch_edge (loop);
! EDGE_INFO (e)->back_edge = 1;
! }
!
! bbs = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! BLOCK_INFO (bbs[i])->tovisit = 1;
! free (bbs);
! propagate_freq (loop);
}
}
*************** estimate_bb_frequencies (loops)
*** 1173,1186 ****
/* First compute probabilities locally for each loop from innermost
to outermost to examine probabilities for back edges. */
estimate_loops_at_level (loops->tree_root);
-
- /* Now fake loop around whole function to finalize probabilities. */
- for (i = 0; i < n_basic_blocks; i++)
- BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
-
- BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
- BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
- propagate_freq (ENTRY_BLOCK_PTR);
memcpy (&freq_max, &real_zero, sizeof (real_zero));
for (i = 0; i < n_basic_blocks; i++)
--- 1165,1170 ----