From 2ecfd709c24bcc376504af4317552e7e492c6702 Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Sat, 1 Jun 2002 11:24:41 +0200 Subject: [PATCH] basic-block.h (struct basic_block_def): New field loop_father. * basic-block.h (struct basic_block_def): New field loop_father. (BB_VISITED): New flag. (struct loop): New field pred, removed field shared. (struct loops): New field parray. (LOOP_EXITS_DOMS): Removed. (flow_loop_tree_node_add, flow_loop_tree_node_remove, flow_loop_nested_p, flow_bb_inside_loop_p, get_loop_body, dfs_enumerate_from, loop_preheader_edge, loop_latch_edge, add_bb_to_loop, remove_bb_from_loops, find_common_loop, verify_loop_structure): Declare. * cfg.c (entry_exit_blocks): Initialize loop_father field. * cfganal.c (dfs_enumerate_from): New function. * cfgloop.c (HEAVY_EDGE_RATIO): New constant. (flow_loop_entry_edges_find, flow_loop_exit_edges_find, flow_loop_nodes_find, flow_loop_level_compute, flow_loop_nested_p, flow_loop_dump, flow_loops_dump, flow_loops_free, flow_loop_tree_node_add, flow_loop_level_compute, flow_loops_level_compute, flow_loop_scan, flow_loops_update, flow_loop_outside_edge_p): Modified for new infrastructure. (make_forwarder_block, canonicalize_loop_headers, glb_enum_p, redirect_edge_with_latch_update, flow_loop_free): New static functions. (flow_loop_tree_node_remove, flow_bb_inside_loop_p, get_loop_body, add_bb_to_loop, remove_bb_from_loops, find_common_loop, verify_loop_structure, loop_latch_edge, loop_preheader_edge): New functions. (flow_loops_cfg_dump): Do not show dominators, as this information does not remain up to date long. (flow_loops_find): Store results in new format. * predict.c (propagate_freq, estimate_probability, estimate_loops_at_level, estimate_bb_frequencies): Use new loop infrastructure. From-SVN: r54142 --- gcc/ChangeLog | 34 ++ gcc/basic-block.h | 39 +- gcc/cfg.c | 2 + gcc/cfganal.c | 51 +++ gcc/cfgloop.c | 1059 +++++++++++++++++++++++++++++++++++------------------ gcc/predict.c | 118 +++--- 6 files changed, 884 insertions(+), 419 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0d4ada794cd..a4d913ec2c1 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,37 @@ +Sat Jun 1 11:23:22 CEST 2002 Zdenek Dvorak + + * basic-block.h (struct basic_block_def): New field loop_father. + (BB_VISITED): New flag. + (struct loop): New field pred, removed field shared. + (struct loops): New field parray. + (LOOP_EXITS_DOMS): Removed. + (flow_loop_tree_node_add, flow_loop_tree_node_remove, + flow_loop_nested_p, flow_bb_inside_loop_p, get_loop_body, + dfs_enumerate_from, loop_preheader_edge, loop_latch_edge, + add_bb_to_loop, remove_bb_from_loops, find_common_loop, + verify_loop_structure): Declare. + * cfg.c (entry_exit_blocks): Initialize loop_father field. + * cfganal.c (dfs_enumerate_from): New function. + * cfgloop.c (HEAVY_EDGE_RATIO): New constant. + (flow_loop_entry_edges_find, flow_loop_exit_edges_find, + flow_loop_nodes_find, flow_loop_level_compute, flow_loop_nested_p, + flow_loop_dump, flow_loops_dump, flow_loops_free, + flow_loop_tree_node_add, flow_loop_level_compute, + flow_loops_level_compute, flow_loop_scan, flow_loops_update, + flow_loop_outside_edge_p): Modified for new infrastructure. + (make_forwarder_block, canonicalize_loop_headers, glb_enum_p, + redirect_edge_with_latch_update, flow_loop_free): New static functions. + (flow_loop_tree_node_remove, flow_bb_inside_loop_p, + get_loop_body, add_bb_to_loop, remove_bb_from_loops, + find_common_loop, verify_loop_structure, loop_latch_edge, + loop_preheader_edge): New functions. + (flow_loops_cfg_dump): Do not show dominators, as this information + does not remain up to date long. + (flow_loops_find): Store results in new format. + * predict.c (propagate_freq, estimate_probability, + estimate_loops_at_level, estimate_bb_frequencies): Use new loop + infrastructure. + 2002-06-01 Alan Lehotsky * except.c (nothrow_function_p): Walk epilogue delay list diff --git a/gcc/basic-block.h b/gcc/basic-block.h index a848e946e91..4fe64d44c92 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -212,6 +212,9 @@ typedef struct basic_block_def { /* The loop depth of this block. */ int loop_depth; + /* Outermost loop containing the block. */ + struct loop *loop_father; + /* Expected number of executions: calculated in profile.c. */ gcov_type count; @@ -228,6 +231,7 @@ typedef struct basic_block_def { #define BB_DIRTY 1 #define BB_NEW 2 #define BB_REACHABLE 4 +#define BB_VISITED 8 /* Number of basic blocks in the current function. */ @@ -403,6 +407,9 @@ struct loop /* The loop nesting depth. */ int depth; + /* Superloops of the loop. */ + struct loop **pred; + /* The height of the loop (enclosed loop levels) within the loop hierarchy tree. */ int level; @@ -416,9 +423,6 @@ struct loop /* 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; @@ -484,6 +488,11 @@ struct loops will find the inner loops before their enclosing outer loops). */ struct loop *array; + /* The above array is unused in new loop infrastructure and is kept only for + purposes of the old loop optimizer. Instead we store just pointers to + loops here. */ + struct loop **parray; + /* Pointer to root of loop heirachy tree. */ struct loop *tree_root; @@ -515,6 +524,8 @@ extern void flow_loop_dump PARAMS ((const struct loop *, FILE *, 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 @@ -613,8 +624,7 @@ enum update_life_extent #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 */ +#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, @@ -701,7 +711,24 @@ extern void free_aux_for_edges PARAMS ((void)); 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)); +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; diff --git a/gcc/cfg.c b/gcc/cfg.c index 3e8c9488f27..33599d354e0 100644 --- a/gcc/cfg.c +++ b/gcc/cfg.c @@ -100,6 +100,7 @@ struct basic_block_def entry_exit_blocks[2] NULL, /* prev_bb */ EXIT_BLOCK_PTR, /* next_bb */ 0, /* loop_depth */ + NULL, /* loop_father */ 0, /* count */ 0, /* frequency */ 0 /* flags */ @@ -120,6 +121,7 @@ struct basic_block_def entry_exit_blocks[2] ENTRY_BLOCK_PTR, /* prev_bb */ NULL, /* next_bb */ 0, /* loop_depth */ + NULL, /* loop_father */ 0, /* count */ 0, /* frequency */ 0 /* flags */ diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 5f69d1ab2d4..24759e1141e 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1103,3 +1103,54 @@ flow_dfs_compute_reverse_finish (data) free (data->stack); sbitmap_free (data->visited_blocks); } + +/* Performs dfs search from BB over vertices satisfying PREDICATE; + if REVERSE, go against direction of edges. Returns number of blocks + found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ +int +dfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max, data) + basic_block bb; + int reverse; + bool (*predicate) (basic_block, void *); + basic_block *rslt; + int rslt_max; + void *data; +{ + basic_block *st, lbb; + int sp = 0, tv = 0; + + st = xcalloc (rslt_max, sizeof (basic_block)); + rslt[tv++] = st[sp++] = bb; + bb->flags |= BB_VISITED; + while (sp) + { + edge e; + lbb = st[--sp]; + if (reverse) + { + for (e = lbb->pred; e; e = e->pred_next) + if (!(e->src->flags & BB_VISITED) && predicate (e->src, data)) + { + if (tv == rslt_max) + abort (); + rslt[tv++] = st[sp++] = e->src; + e->src->flags |= BB_VISITED; + } + } + else + { + for (e = lbb->succ; e; e = e->succ_next) + if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data)) + { + if (tv == rslt_max) + abort (); + rslt[tv++] = st[sp++] = e->dest; + e->dest->flags |= BB_VISITED; + } + } + } + free (st); + for (sp = 0; sp < tv; sp++) + rslt[sp]->flags &= ~BB_VISITED; + return tv; +} diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 7b0c8415d88..e5cc41b4131 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -23,24 +23,28 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #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 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_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 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_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. */ @@ -62,7 +66,7 @@ flow_loops_cfg_dump (loops, file) fprintf (file, ";; %d succs { ", bb->index); for (succ = bb->succ; succ; succ = succ->succ_next) fprintf (file, "%d ", succ->dest->index); - flow_nodes_print ("} dom", loops->cfg.dom[bb->index], file); + fprintf (file, "}\n"); } /* Dump the DFS node order. */ @@ -88,12 +92,13 @@ flow_loops_cfg_dump (loops, file) /* Return non-zero if the nodes of LOOP are a subset of OUTER. */ -static int +bool flow_loop_nested_p (outer, loop) - struct loop *outer; - struct loop *loop; + const struct loop *outer; + const struct loop *loop; { - return sbitmap_a_subset_b_p (loop->nodes, outer->nodes); + return loop->depth > outer->depth + && loop->pred[outer->depth] == outer; } /* Dump the loop information specified by LOOP to the stream FILE @@ -106,22 +111,18 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); int verbose; { + basic_block *bbs; + int i; + 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, ";;\n;; Loop %d:%s\n", loop->num, + loop->invalid ? " invalid" : ""); - fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n", + fprintf (file, ";; header %d, latch %d, pre-header %d\n", loop->header->index, loop->latch->index, - loop->pre_header ? loop->pre_header->index : -1, - loop->first->index, loop->last->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)); @@ -132,14 +133,15 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) 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); + 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->exits_doms) - flow_nodes_print (";; exit doms", loop->exits_doms, file); - if (loop_dump_aux) loop_dump_aux (loop, file, verbose); } @@ -154,55 +156,53 @@ flow_loops_dump (loops, file, loop_dump_aux, verbose) void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); int verbose; { - int i, j; + 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); + 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]; + struct loop *loop = loops->parray[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) + continue; - 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"); - } - } + 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->array) + if (loops->parray) { int i; @@ -212,180 +212,163 @@ flow_loops_free (loops) /* 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); + struct loop *loop = loops->parray[i]; + + if (!loop) + continue; + + flow_loop_free (loop); } - free (loops->array); - loops->array = NULL; + 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); - 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. */ +/* Find the entry edges into the LOOP. */ -static int -flow_loop_entry_edges_find (header, nodes, entry_edges) - basic_block header; - const sbitmap nodes; - edge **entry_edges; +static void +flow_loop_entry_edges_find (loop) + struct loop *loop; { edge e; int num_entries; - *entry_edges = NULL; - num_entries = 0; - for (e = header->pred; e; e = e->pred_next) + for (e = loop->header->pred; e; e = e->pred_next) { - basic_block src = e->src; - - if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) + if (flow_loop_outside_edge_p (loop, e)) num_entries++; } if (! num_entries) abort (); - *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge)); + loop->entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *)); num_entries = 0; - for (e = header->pred; e; e = e->pred_next) + for (e = loop->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; + if (flow_loop_outside_edge_p (loop, e)) + loop->entry_edges[num_entries++] = e; } - return num_entries; + loop->num_entries = 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. */ +/* Find the exit edges from the LOOP. */ -static int -flow_loop_exit_edges_find (nodes, exit_edges) - const sbitmap nodes; - edge **exit_edges; +static void +flow_loop_exit_edges_find (loop) + struct loop *loop; { edge e; - int node; - int num_exits; + basic_block node, *bbs; + int num_exits, i; - *exit_edges = NULL; + 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. */ + exiting edges. */ 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; + 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 (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) + if (!flow_bb_inside_loop_p (loop, dest)) num_exits++; - } - }); + } + } if (! num_exits) - return 0; + { + free (bbs); + return; + } - *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge)); + loop->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; + 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 (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) - (*exit_edges)[num_exits++] = e; + if (!flow_bb_inside_loop_p (loop, dest)) + loop->exit_edges[num_exits++] = e; } - }); - - return num_exits; + } + free (bbs); + loop->num_exits = 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. */ +/* 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, latch, nodes) +flow_loop_nodes_find (header, loop) basic_block header; - basic_block latch; - sbitmap nodes; + struct loop *loop; { basic_block *stack; int sp; - int num_nodes = 0; - - stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block)); - sp = 0; + int num_nodes = 1; + int findex, lindex; - /* 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++; + header->loop_father = loop; + header->loop_depth = loop->depth; + findex = lindex = header->index; - /* Push the loop latch on to the stack. */ - if (! TEST_BIT (nodes, latch->index)) + if (loop->latch->loop_father != loop) { - SET_BIT (nodes, latch->index); - latch->loop_depth++; + stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block)); + sp = 0; num_nodes++; - stack[sp++] = latch; - } - - while (sp) - { - basic_block node; - edge e; - - node = stack[--sp]; - for (e = node->pred; e; e = e->pred_next) + stack[sp++] = loop->latch; + loop->latch->loop_father = loop; + loop->latch->loop_depth = loop->depth; + + while (sp) { - basic_block ancestor = e->src; + basic_block node; + edge e; - /* 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)) + node = stack[--sp]; + + for (e = node->pred; e; e = e->pred_next) { - SET_BIT (nodes, ancestor->index); - ancestor->loop_depth++; - num_nodes++; - stack[sp++] = ancestor; + 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); } - free (stack); return num_nodes; } @@ -462,68 +445,55 @@ flow_loop_pre_header_find (header, dom) 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. */ +/* Add LOOP to the loop hierarchy tree where FATHER is father of the + added loop. */ -static void -flow_loop_tree_node_add (prevloop, loop) - struct loop *prevloop; +void +flow_loop_tree_node_add (father, loop) + struct loop *father; 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; + 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; } -/* Build the loop hierarchy tree for LOOPS. */ +/* Remove LOOP from the loop hierarchy tree. */ -static void -flow_loops_tree_build (loops) - struct loops *loops; +void +flow_loop_tree_node_remove (loop) + struct loop *loop; { - int i; - int num_loops; + struct loop *prev, *father; - num_loops = loops->num; - if (! num_loops) - return; + father = loop->outer; + loop->outer = NULL; - /* 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; + /* 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; + } - /* 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]); + loop->depth = -1; + free (loop->pred); + loop->pred = NULL; } /* Helper function to compute loop nesting depth and enclosed loop level - for the natural loop specified by LOOP at the loop depth DEPTH. - Returns the loop level. */ + for the natural loop specified by LOOP. Returns the loop level. */ static int -flow_loop_level_compute (loop, depth) +flow_loop_level_compute (loop) struct loop *loop; - int depth; { struct loop *inner; int level = 1; @@ -538,13 +508,13 @@ flow_loop_level_compute (loop, depth) itself). */ for (inner = loop->inner; inner; inner = inner->next) { - int ilevel = flow_loop_level_compute (inner, depth + 1) + 1; + int ilevel = flow_loop_level_compute (inner) + 1; - level = MAX (ilevel, level); + if (ilevel > level) + level = ilevel; } loop->level = level; - loop->depth = depth; return level; } @@ -556,18 +526,7 @@ static int 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; + return flow_loop_level_compute (loops->tree_root); } /* Scan a single natural loop specified by LOOP collecting information @@ -579,37 +538,18 @@ flow_loop_scan (loops, loop, flags) 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); + { + /* 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. */ - 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 (last_basic_block); - 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 (); + /* Find edges which exit the loop. */ + flow_loop_exit_edges_find (loop); } if (flags & LOOP_PRE_HEADER) @@ -626,6 +566,190 @@ flow_loop_scan (loops, loop, flags) 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; + + /* Compute the dominators. */ + dom = sbitmap_vector_alloc (last_basic_block, last_basic_block); + 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_EACH_BB (header) + { + int num_latches = 0; + int have_abnormal_edge = 0; + + 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], header->index)) + { + 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)) + { + basic_block bb; + + /* We could not redirect edges freely here. On the other hand, + we can simply split the edge from entry block. */ + bb = split_edge (ENTRY_BLOCK_PTR->succ); + + alloc_aux_for_edge (bb->succ, sizeof (int)); + LATCH_EDGE (bb->succ) = 0; + alloc_aux_for_block (bb, sizeof (int)); + HEADER_BLOCK (bb) = 0; + } + + 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. */ + 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 @@ -662,32 +786,81 @@ flow_loops_find (loops, flags) dfs_order = NULL; rc_order = NULL; + /* Join loops with shared headers. */ + canonicalize_loop_headers (); + /* Compute the dominators. */ - dom = sbitmap_vector_alloc (last_basic_block, last_basic_block); + loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block); calculate_dominance_info (NULL, dom, CDI_DOMINATORS); - /* Count the number of loop edges (back edges). This should be the + /* Count the number of loop headers. This should be the same as the number of natural loops. */ + headers = sbitmap_alloc (last_basic_block); + sbitmap_zero (headers); + num_loops = 0; FOR_EACH_BB (header) { + int more_latches = 0; + header->loop_depth = 0; for (e = header->pred; e; e = e->pred_next) { basic_block latch = e->src; + if (e->flags & EDGE_ABNORMAL) + { + if (more_latches) + { + RESET_BIT (headers, header->index); + 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. Note that multiple natural loops - may share the same header. */ - if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], header->index)) - num_loops++; + from a latch node. */ + if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], + header->index)) + { + /* Shared headers should be eliminated by now. */ + if (more_latches) + abort (); + more_latches = 1; + SET_BIT (headers, header->index); + 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_EACH_BB (bb) + bb->loop_father = loops->tree_root; + if (num_loops) { /* Compute depth first search order of the CFG so that outer @@ -701,110 +874,65 @@ flow_loops_find (loops, flags) 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 (last_basic_block); - sbitmap_zero (headers); + num_loops = 1; - loops->shared_headers = sbitmap_alloc (last_basic_block); - 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--) + for (b = 0; b < n_basic_blocks; b++) { - basic_block latch; + struct loop *loop; /* Search the nodes of the CFG in reverse completion order so that we can find outer loops first. */ - latch = BASIC_BLOCK (rc_order[b]); + if (!TEST_BIT (headers, rc_order[b])) + continue; + + header = BASIC_BLOCK (rc_order[b]); + + loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); - /* Look for all the possible headers for this latch block. */ - for (e = latch->succ; e; e = e->succ_next) + 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 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 + basic_block latch = e->src; + + if (latch != ENTRY_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++; + break; } } - } - - 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 (last_basic_block); - 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. */ - - FOR_EACH_BB (bb) - if (TEST_BIT (loop->nodes, bb->index)) - break; - loop->first = bb; - - FOR_EACH_BB_REVERSE (bb) - if (TEST_BIT (loop->nodes, bb->index)) - break; - loop->last = bb; - flow_loop_scan (loops, loop, flags); + flow_loop_tree_node_add (header->loop_father, loop); + loop->num_nodes = flow_loop_nodes_find (loop->header, loop); } - /* 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; + /* Assign the loop nesting depth and enclosed loop level for each + loop. */ + loops->levels = flow_loops_level_compute (loops); - /* Build the loop hierarchy tree. */ - flow_loops_tree_build (loops); + /* Scan the loops. */ + for (i = 1; i < num_loops; i++) + flow_loop_scan (loops, loops->parray[i], flags); - /* Assign the loop nesting depth and enclosed loop level for each - loop. */ - loops->levels = flow_loops_level_compute (loops); + loops->num = num_loops; + } + else + { + loops->cfg.dom = NULL; + sbitmap_vector_free (dom); + } +#ifdef ENABLE_CHECKING + verify_flow_info (); + verify_loop_structure (loops, 0); +#endif - return num_loops; + return loops->num; } /* Update the information regarding the loops in the CFG @@ -817,22 +945,259 @@ flow_loops_update (loops, flags) { /* 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) + 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. */ -int +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, bb; + int tv = 0; + + 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_EACH_BB (bb) + tovisit[tv++] = bb; + 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 + */ +void +verify_loop_structure (loops, flags) + struct loops *loops; + int flags; +{ + int *sizes, i, j; + basic_block *bbs, bb; + struct loop *loop; + int err = 0; + + /* Check sizes. */ + sizes = xcalloc (loops->num, sizeof (int)); + sizes[0] = 2; + + FOR_EACH_BB (bb) + for (loop = bb->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; + } + } + + if (err) + abort (); +} + +/* Returns latch edge of LOOP. */ +edge +loop_latch_edge (loop) + struct loop *loop; +{ + edge e; + + for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next) + continue; - return (e->src == ENTRY_BLOCK_PTR) - || ! TEST_BIT (loop->nodes, e->src->index); + return e; } + +/* Returns preheader edge of LOOP. */ +edge +loop_preheader_edge (loop) + struct loop *loop; +{ + edge e; + + for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next) + continue; + + return e; +} + diff --git a/gcc/predict.c b/gcc/predict.c index a5131d4a475..c00c86409f3 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -70,7 +70,7 @@ static void combine_predictions_for_insn PARAMS ((rtx, basic_block)); 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 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 *, @@ -419,19 +419,23 @@ estimate_probability (loops_info) /* Try to predict out blocks in a loop that are not part of a natural loop. */ - for (i = 0; i < loops_info->num; i++) + for (i = 1; i < loops_info->num; i++) { + basic_block bb, *bbs; + int j; int exits; - struct loop *loop = &loops_info->array[i]; + struct loop *loop = loops_info->parray[i]; flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES); exits = loop->num_exits; - FOR_BB_BETWEEN (bb, loop->first, loop->last->next_bb, next_bb) - if (TEST_BIT (loop->nodes, bb->index)) - { - int header_found = 0; - edge e; + 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 @@ -440,28 +444,28 @@ estimate_probability (loops_info) 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 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 - || !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); - } + /* 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. */ @@ -896,12 +900,13 @@ typedef struct edge_info_def #define EDGE_INFO(E) ((edge_info) (E)->aux) /* Helper function for estimate_bb_frequencies. - Propagate the frequencies for loops headed by HEAD. */ + Propagate the frequencies for LOOP. */ static void -propagate_freq (head) - basic_block head; +propagate_freq (loop) + struct loop *loop; { + basic_block head = loop->header; basic_block bb; basic_block last; edge e; @@ -1028,41 +1033,28 @@ static void estimate_loops_at_level (first_loop) struct loop *first_loop; { - struct loop *l, *loop = first_loop; + struct loop *loop; for (loop = first_loop; loop; loop = loop->next) { - int n; edge e; + basic_block *bbs; + int i; 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) + + if (loop->latch->succ) /* Do not do this for dummy function loop. */ { - 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); + /* 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); } } @@ -1202,12 +1194,6 @@ estimate_bb_frequencies (loops) 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_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) - BLOCK_INFO (bb)->tovisit = 1; - - propagate_freq (ENTRY_BLOCK_PTR); - memcpy (&freq_max, &real_zero, sizeof (real_zero)); FOR_EACH_BB (bb) if (REAL_VALUES_LESS -- 2.11.4.GIT