diff options
author | kan <kan@FreeBSD.org> | 2004-07-28 03:11:36 +0000 |
---|---|---|
committer | kan <kan@FreeBSD.org> | 2004-07-28 03:11:36 +0000 |
commit | 5e00ec74d8ce58f99801200d4d3d0412c7cc1b28 (patch) | |
tree | 052f4bb635f2bea2c5e350bd60c902be100a0d1e /contrib/gcc/cfgloop.c | |
parent | 87b8398a7d9f9bf0e28bbcd54a4fc27db2125f38 (diff) | |
download | FreeBSD-src-5e00ec74d8ce58f99801200d4d3d0412c7cc1b28.zip FreeBSD-src-5e00ec74d8ce58f99801200d4d3d0412c7cc1b28.tar.gz |
Gcc 3.4.2 20040728.
Diffstat (limited to 'contrib/gcc/cfgloop.c')
-rw-r--r-- | contrib/gcc/cfgloop.c | 420 |
1 files changed, 253 insertions, 167 deletions
diff --git a/contrib/gcc/cfgloop.c b/contrib/gcc/cfgloop.c index c8f7603..69097c00 100644 --- a/contrib/gcc/cfgloop.c +++ b/contrib/gcc/cfgloop.c @@ -1,5 +1,5 @@ /* Natural loop discovery code for GNU compiler. - Copyright (C) 2000, 2001 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. This file is part of GCC. @@ -20,43 +20,42 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "rtl.h" #include "hard-reg-set.h" #include "basic-block.h" #include "toplev.h" +#include "cfgloop.h" +#include "flags.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, - dominance_info)); -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 *)); +static void flow_loops_cfg_dump (const struct loops *, FILE *); +static void flow_loop_entry_edges_find (struct loop *); +static void flow_loop_exit_edges_find (struct loop *); +static int flow_loop_nodes_find (basic_block, struct loop *); +static void flow_loop_pre_header_scan (struct loop *); +static basic_block flow_loop_pre_header_find (basic_block); +static int flow_loop_level_compute (struct loop *); +static int flow_loops_level_compute (struct loops *); +static void establish_preds (struct loop *); +static basic_block make_forwarder_block (basic_block, int, int, edge, int); +static void canonicalize_loop_headers (void); +static bool glb_enum_p (basic_block, void *); +static void redirect_edge_with_latch_update (edge, basic_block); /* Dump loop related CFG information. */ static void -flow_loops_cfg_dump (loops, file) - const struct loops *loops; - FILE *file; +flow_loops_cfg_dump (const struct loops *loops, FILE *file) { int i; basic_block bb; - if (! loops->num || ! file || ! loops->cfg.dom) + if (! loops->num || ! file) return; FOR_EACH_BB (bb) @@ -93,9 +92,7 @@ flow_loops_cfg_dump (loops, file) /* Return nonzero if the nodes of LOOP are a subset of OUTER. */ bool -flow_loop_nested_p (outer, loop) - const struct loop *outer; - const struct loop *loop; +flow_loop_nested_p (const struct loop *outer, const struct loop *loop) { return loop->depth > outer->depth && loop->pred[outer->depth] == outer; @@ -105,14 +102,12 @@ flow_loop_nested_p (outer, loop) using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ void -flow_loop_dump (loop, file, loop_dump_aux, verbose) - const struct loop *loop; - FILE *file; - void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); - int verbose; +flow_loop_dump (const struct loop *loop, FILE *file, + void (*loop_dump_aux) (const struct loop *, FILE *, int), + int verbose) { basic_block *bbs; - int i; + unsigned i; if (! loop || ! loop->header) return; @@ -150,11 +145,7 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ void -flow_loops_dump (loops, file, loop_dump_aux, verbose) - const struct loops *loops; - FILE *file; - void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); - int verbose; +flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) { int i; int num_loops; @@ -181,9 +172,8 @@ flow_loops_dump (loops, file, loop_dump_aux, verbose) } /* Free data allocated for LOOP. */ -static void -flow_loop_free (loop) - struct loop *loop; +void +flow_loop_free (struct loop *loop) { if (loop->pre_header_edges) free (loop->pre_header_edges); @@ -199,12 +189,11 @@ flow_loop_free (loop) /* Free all the memory allocated for LOOPS. */ void -flow_loops_free (loops) - struct loops *loops; +flow_loops_free (struct loops *loops) { if (loops->parray) { - int i; + unsigned i; if (! loops->num) abort (); @@ -223,9 +212,6 @@ flow_loops_free (loops) free (loops->parray); loops->parray = NULL; - if (loops->cfg.dom) - free_dominance_info (loops->cfg.dom); - if (loops->cfg.dfs_order) free (loops->cfg.dfs_order); if (loops->cfg.rc_order) @@ -236,9 +222,8 @@ flow_loops_free (loops) /* Find the entry edges into the LOOP. */ -static void -flow_loop_entry_edges_find (loop) - struct loop *loop; +static void +flow_loop_entry_edges_find (struct loop *loop) { edge e; int num_entries; @@ -253,7 +238,7 @@ flow_loop_entry_edges_find (loop) if (! num_entries) abort (); - loop->entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *)); + loop->entry_edges = xmalloc (num_entries * sizeof (edge *)); num_entries = 0; for (e = loop->header->pred; e; e = e->pred_next) @@ -268,12 +253,11 @@ flow_loop_entry_edges_find (loop) /* Find the exit edges from the LOOP. */ static void -flow_loop_exit_edges_find (loop) - struct loop *loop; +flow_loop_exit_edges_find (struct loop *loop) { edge e; basic_block node, *bbs; - int num_exits, i; + unsigned num_exits, i; loop->exit_edges = NULL; loop->num_exits = 0; @@ -301,7 +285,7 @@ flow_loop_exit_edges_find (loop) return; } - loop->exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *)); + loop->exit_edges = xmalloc (num_exits * sizeof (edge *)); /* Store all exiting edges into an array. */ num_exits = 0; @@ -324,35 +308,31 @@ flow_loop_exit_edges_find (loop) Return the number of nodes within the loop. */ static int -flow_loop_nodes_find (header, loop) - basic_block header; - struct loop *loop; +flow_loop_nodes_find (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)); + stack = 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; @@ -376,8 +356,7 @@ flow_loop_nodes_find (header, loop) the edges along the trace from the root node to the loop header. */ static void -flow_loop_pre_header_scan (loop) - struct loop *loop; +flow_loop_pre_header_scan (struct loop *loop) { int num; basic_block ebb; @@ -398,7 +377,7 @@ flow_loop_pre_header_scan (loop) num++) ebb = ebb->pred->src; - loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge)); + loop->pre_header_edges = xmalloc (num * sizeof (edge)); loop->num_pre_header_edges = num; /* Store edges in order that they are followed. The source of the first edge @@ -409,13 +388,10 @@ flow_loop_pre_header_scan (loop) } /* Return the block for the pre-header of the loop with header - HEADER where DOM specifies the dominator information. Return NULL if - there is no pre-header. */ + HEADER. Return NULL if there is no pre-header. */ static basic_block -flow_loop_pre_header_find (header, dom) - basic_block header; - dominance_info dom; +flow_loop_pre_header_find (basic_block header) { basic_block pre_header; edge e; @@ -428,7 +404,7 @@ flow_loop_pre_header_find (header, dom) basic_block node = e->src; if (node != ENTRY_BLOCK_PTR - && ! dominated_by_p (dom, node, header)) + && ! dominated_by_p (CDI_DOMINATORS, node, header)) { if (pre_header == NULL) pre_header = node; @@ -445,29 +421,40 @@ flow_loop_pre_header_find (header, dom) return pre_header; } +static void +establish_preds (struct loop *loop) +{ + struct loop *ploop, *father = loop->outer; + + loop->depth = father->depth + 1; + if (loop->pred) + free (loop->pred); + loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); + memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); + loop->pred[father->depth] = father; + + for (ploop = loop->inner; ploop; ploop = ploop->next) + establish_preds (ploop); +} + /* Add LOOP to the loop hierarchy tree where FATHER is father of the - added loop. */ + added loop. If LOOP has some children, take care of that their + pred field will be initialized correctly. */ void -flow_loop_tree_node_add (father, loop) - struct loop *father; - struct loop *loop; +flow_loop_tree_node_add (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; + establish_preds (loop); } /* Remove LOOP from the loop hierarchy tree. */ void -flow_loop_tree_node_remove (loop) - struct loop *loop; +flow_loop_tree_node_remove (struct loop *loop) { struct loop *prev, *father; @@ -492,8 +479,7 @@ flow_loop_tree_node_remove (loop) for the natural loop specified by LOOP. Returns the loop level. */ static int -flow_loop_level_compute (loop) - struct loop *loop; +flow_loop_level_compute (struct loop *loop) { struct loop *inner; int level = 1; @@ -523,8 +509,7 @@ flow_loop_level_compute (loop) level. */ static int -flow_loops_level_compute (loops) - struct loops *loops; +flow_loops_level_compute (struct loops *loops) { return flow_loop_level_compute (loops->tree_root); } @@ -533,10 +518,7 @@ flow_loops_level_compute (loops) about it specified by FLAGS. */ int -flow_loop_scan (loops, loop, flags) - struct loops *loops; - struct loop *loop; - int flags; +flow_loop_scan (struct loop *loop, int flags) { if (flags & LOOP_ENTRY_EDGES) { @@ -555,8 +537,7 @@ flow_loop_scan (loops, loop, flags) if (flags & LOOP_PRE_HEADER) { /* Look to see if the loop has a pre-header node. */ - loop->pre_header - = flow_loop_pre_header_find (loop->header, loops->cfg.dom); + loop->pre_header = flow_loop_pre_header_find (loop->header); /* Find the blocks within the extended basic block of the loop pre-header. */ @@ -571,9 +552,7 @@ flow_loop_scan (loops, loop, flags) /* Redirect edge and update latch and header info. */ static void -redirect_edge_with_latch_update (e, to) - edge e; - basic_block to; +redirect_edge_with_latch_update (edge e, basic_block to) { basic_block jump; @@ -595,13 +574,7 @@ redirect_edge_with_latch_update (e, to) 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; +make_forwarder_block (basic_block bb, int redirect_latch, int redirect_nonlatch, edge except, int conn_latch) { edge e, next_e, fallthru; basic_block dummy; @@ -609,6 +582,10 @@ make_forwarder_block (bb, redirect_latch, redirect_nonlatch, except, insn = PREV_INSN (first_insn_after_basic_block_note (bb)); + /* For empty block split_block will return NULL. */ + if (BB_END (bb) == insn) + emit_note_after (NOTE_INSN_DELETED, insn); + fallthru = split_block (bb, insn); dummy = fallthru->src; bb = fallthru->dest; @@ -643,14 +620,13 @@ make_forwarder_block (bb, redirect_latch, redirect_nonlatch, except, /* Takes care of merging natural loops with shared headers. */ static void -canonicalize_loop_headers () +canonicalize_loop_headers (void) { - dominance_info dom; basic_block header; edge e; - + /* Compute the dominators. */ - dom = calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_DOMINATORS); alloc_aux_for_blocks (sizeof (int)); alloc_aux_for_edges (sizeof (int)); @@ -669,7 +645,7 @@ canonicalize_loop_headers () have_abnormal_edge = 1; if (latch != ENTRY_BLOCK_PTR - && dominated_by_p (dom, latch, header)) + && dominated_by_p (CDI_DOMINATORS, latch, header)) { num_latches++; LATCH_EDGE (e) = 1; @@ -681,6 +657,8 @@ canonicalize_loop_headers () HEADER_BLOCK (header) = num_latches; } + free_dominance_info (CDI_DOMINATORS); + if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest)) { basic_block bb; @@ -688,7 +666,7 @@ canonicalize_loop_headers () /* 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)); @@ -746,7 +724,6 @@ canonicalize_loop_headers () free_aux_for_blocks (); free_aux_for_edges (); - free_dominance_info (dom); } /* Find all the natural loops in the function and save in LOOPS structure and @@ -755,16 +732,13 @@ canonicalize_loop_headers () loops found. */ int -flow_loops_find (loops, flags) - struct loops *loops; - int flags; +flow_loops_find (struct loops *loops, int flags) { int i; int b; int num_loops; edge e; sbitmap headers; - dominance_info dom; int *dfs_order; int *rc_order; basic_block header; @@ -790,7 +764,7 @@ flow_loops_find (loops, flags) canonicalize_loop_headers (); /* Compute the dominators. */ - dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_DOMINATORS); /* Count the number of loop headers. This should be the same as the number of natural loops. */ @@ -801,7 +775,7 @@ flow_loops_find (loops, flags) FOR_EACH_BB (header) { int more_latches = 0; - + header->loop_depth = 0; /* If we have an abnormal predecessor, do not consider the @@ -824,7 +798,8 @@ flow_loops_find (loops, flags) 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 && dominated_by_p (dom, latch, header)) + if (latch != ENTRY_BLOCK_PTR + && dominated_by_p (CDI_DOMINATORS, latch, header)) { /* Shared headers should be eliminated by now. */ if (more_latches) @@ -837,7 +812,7 @@ flow_loops_find (loops, flags) } /* Allocate loop structures. */ - loops->parray = (struct loop **) xcalloc (num_loops + 1, sizeof (struct loop *)); + loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *)); /* Dummy loop containing whole function. */ loops->parray[0] = xcalloc (1, sizeof (struct loop)); @@ -864,12 +839,11 @@ flow_loops_find (loops, flags) { /* Compute depth first search order of the CFG so that outer natural loops will be found before inner natural loops. */ - dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); - rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); + dfs_order = xmalloc (n_basic_blocks * sizeof (int)); + rc_order = xmalloc (n_basic_blocks * sizeof (int)); flow_depth_first_order_compute (dfs_order, rc_order); /* Save CFG derived information to avoid recomputing it. */ - loops->cfg.dom = dom; loops->cfg.dfs_order = dfs_order; loops->cfg.rc_order = rc_order; @@ -885,7 +859,7 @@ flow_loops_find (loops, flags) continue; header = BASIC_BLOCK (rc_order[b]); - + loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); loop->header = header; @@ -898,7 +872,7 @@ flow_loops_find (loops, flags) basic_block latch = e->src; if (latch != ENTRY_BLOCK_PTR - && dominated_by_p (dom, latch, header)) + && dominated_by_p (CDI_DOMINATORS, latch, header)) { loop->latch = latch; break; @@ -909,26 +883,27 @@ flow_loops_find (loops, flags) 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); + flow_loop_scan (loops->parray[i], flags); loops->num = num_loops; } else { - loops->cfg.dom = NULL; - free_dominance_info (dom); + free_dominance_info (CDI_DOMINATORS); } + + sbitmap_free (headers); + + loops->state = 0; #ifdef ENABLE_CHECKING verify_flow_info (); - verify_loop_structure (loops, 0); + verify_loop_structure (loops); #endif return loops->num; @@ -938,9 +913,7 @@ flow_loops_find (loops, flags) specified by LOOPS. */ int -flow_loops_update (loops, flags) - struct loops *loops; - int flags; +flow_loops_update (struct loops *loops, int flags) { /* One day we may want to update the current loop data. For now throw away the old stuff and rebuild what we need. */ @@ -952,9 +925,7 @@ flow_loops_update (loops, flags) /* Return nonzero if basic block BB belongs to LOOP. */ bool -flow_bb_inside_loop_p (loop, bb) - const struct loop *loop; - const basic_block bb; +flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) { struct loop *source_loop; @@ -968,9 +939,7 @@ flow_bb_inside_loop_p (loop, bb) /* Return nonzero 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; +flow_loop_outside_edge_p (const struct loop *loop, edge e) { if (e->dest != loop->header) abort (); @@ -979,20 +948,19 @@ flow_loop_outside_edge_p (loop, e) /* Enumeration predicate for get_loop_body. */ static bool -glb_enum_p (bb, glb_header) - basic_block bb; - void *glb_header; +glb_enum_p (basic_block bb, void *glb_header) { return bb != (basic_block) glb_header; } -/* Gets basic blocks of a loop. */ +/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs + order against direction of edges from latch. Specially, if + header != latch, latch is the 1-st block. */ basic_block * -get_loop_body (loop) - const struct loop *loop; +get_loop_body (const struct loop *loop) { basic_block *tovisit, bb; - int tv = 0; + unsigned tv = 0; if (!loop->num_nodes) abort (); @@ -1003,7 +971,7 @@ get_loop_body (loop) if (loop->latch == EXIT_BLOCK_PTR) { /* There may be blocks unreachable from EXIT_BLOCK. */ - if (loop->num_nodes != n_basic_blocks + 2) + if (loop->num_nodes != (unsigned) n_basic_blocks + 2) abort (); FOR_EACH_BB (bb) tovisit[tv++] = bb; @@ -1021,14 +989,41 @@ get_loop_body (loop) return tovisit; } +/* Gets exit edges of a LOOP, returning their number in N_EDGES. */ +edge * +get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges) +{ + edge *edges, e; + unsigned i, n; + basic_block * body; + + if (loop->latch == EXIT_BLOCK_PTR) + abort (); + + body = get_loop_body (loop); + n = 0; + for (i = 0; i < loop->num_nodes; i++) + for (e = body[i]->succ; e; e = e->succ_next) + if (!flow_bb_inside_loop_p (loop, e->dest)) + n++; + edges = xmalloc (n * sizeof (edge)); + *n_edges = n; + n = 0; + for (i = 0; i < loop->num_nodes; i++) + for (e = body[i]->succ; e; e = e->succ_next) + if (!flow_bb_inside_loop_p (loop, e->dest)) + edges[n++] = e; + free (body); + + return edges; +} + /* Adds basic block BB to LOOP. */ void -add_bb_to_loop (bb, loop) - basic_block bb; - struct loop *loop; - { +add_bb_to_loop (basic_block bb, struct loop *loop) +{ int i; - + bb->loop_father = loop; bb->loop_depth = loop->depth; loop->num_nodes++; @@ -1038,9 +1033,8 @@ add_bb_to_loop (bb, loop) /* Remove basic block BB from loops. */ void -remove_bb_from_loops (bb) - basic_block bb; - { +remove_bb_from_loops (basic_block bb) +{ int i; struct loop *loop = bb->loop_father; @@ -1053,13 +1047,11 @@ remove_bb_from_loops (bb) /* 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; +find_common_loop (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) @@ -1073,21 +1065,56 @@ find_common_loop (loop_s, loop_d) return loop_s; } -/* Checks that LOOPS are allright: - -- sizes of loops are allright +/* Cancels the LOOP; it must be innermost one. */ +void +cancel_loop (struct loops *loops, struct loop *loop) +{ + basic_block *bbs; + unsigned i; + + if (loop->inner) + abort (); + + /* Move blocks up one level (they should be removed as soon as possible). */ + bbs = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + bbs[i]->loop_father = loop->outer; + + /* Remove the loop from structure. */ + flow_loop_tree_node_remove (loop); + + /* Remove loop from loops array. */ + loops->parray[loop->num] = NULL; + + /* Free loop data. */ + flow_loop_free (loop); +} + +/* Cancels LOOP and all its subloops. */ +void +cancel_loop_tree (struct loops *loops, struct loop *loop) +{ + while (loop->inner) + cancel_loop_tree (loops, loop->inner); + cancel_loop (loops, loop); +} + +/* Checks that LOOPS are all right: + -- sizes of loops are all right -- 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 + -- irreducible loops are correctly marked */ void -verify_loop_structure (loops, flags) - struct loops *loops; - int flags; +verify_loop_structure (struct loops *loops) { - int *sizes, i, j; + unsigned *sizes, i, j; + sbitmap irreds; basic_block *bbs, bb; struct loop *loop; int err = 0; + edge e; /* Check sizes. */ sizes = xcalloc (loops->num, sizeof (int)); @@ -1137,14 +1164,14 @@ verify_loop_structure (loops, flags) if (!loop) continue; - if ((flags & VLS_EXPECT_PREHEADERS) + if ((loops->state & LOOPS_HAVE_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 (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) { if (!loop->latch->succ || loop->latch->succ->succ_next) @@ -1168,6 +1195,68 @@ verify_loop_structure (loops, flags) error ("Loop %d's header does not belong directly to it.", i); err = 1; } + if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) + { + error ("Loop %d's latch is marked as part of irreducible region.", i); + err = 1; + } + } + + /* Check irreducible loops. */ + if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + { + /* Record old info. */ + irreds = sbitmap_alloc (last_basic_block); + FOR_EACH_BB (bb) + { + if (bb->flags & BB_IRREDUCIBLE_LOOP) + SET_BIT (irreds, bb->index); + else + RESET_BIT (irreds, bb->index); + for (e = bb->succ; e; e = e->succ_next) + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + e->flags |= EDGE_ALL_FLAGS + 1; + } + + /* Recount it. */ + mark_irreducible_loops (loops); + + /* Compare. */ + FOR_EACH_BB (bb) + { + if ((bb->flags & BB_IRREDUCIBLE_LOOP) + && !TEST_BIT (irreds, bb->index)) + { + error ("Basic block %d should be marked irreducible.", bb->index); + err = 1; + } + else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) + && TEST_BIT (irreds, bb->index)) + { + error ("Basic block %d should not be marked irreducible.", bb->index); + err = 1; + } + for (e = bb->succ; e; e = e->succ_next) + { + if ((e->flags & EDGE_IRREDUCIBLE_LOOP) + && !(e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) + && (e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should not be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + e->flags &= ~(EDGE_ALL_FLAGS + 1); + } + } + free (irreds); } if (err) @@ -1176,8 +1265,7 @@ verify_loop_structure (loops, flags) /* Returns latch edge of LOOP. */ edge -loop_latch_edge (loop) - struct loop *loop; +loop_latch_edge (const struct loop *loop) { edge e; @@ -1189,8 +1277,7 @@ loop_latch_edge (loop) /* Returns preheader edge of LOOP. */ edge -loop_preheader_edge (loop) - struct loop *loop; +loop_preheader_edge (const struct loop *loop) { edge e; @@ -1199,4 +1286,3 @@ loop_preheader_edge (loop) return e; } - |