X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Fcfganal.c;h=b8d67bcdb0ff8b8af3aff6dba79f8a7ecd390291;hb=138cac6426259ed3ed98371f0aa0989df32c0724;hp=63d17cede2b85e196664a475f1ba6e74f1671125;hpb=11452e7bb94745d54860580134bf0c2394251834;p=gcc.git diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 63d17cede2b..b8d67bcdb0f 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1,5 +1,5 @@ /* Control flow graph analysis code for GNU compiler. - Copyright (C) 1987-2013 Free Software Foundation, Inc. + Copyright (C) 1987-2015 Free Software Foundation, Inc. This file is part of GCC. @@ -22,8 +22,19 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "basic-block.h" +#include "predict.h" #include "vec.h" +#include "hashtab.h" +#include "hash-set.h" +#include "machmode.h" +#include "tm.h" +#include "hard-reg-set.h" +#include "input.h" +#include "function.h" +#include "dominance.h" +#include "cfg.h" +#include "cfganal.h" +#include "basic-block.h" #include "bitmap.h" #include "sbitmap.h" #include "timevar.h" @@ -72,21 +83,21 @@ mark_dfs_back_edges (void) bool found = false; /* Allocate the preorder and postorder number arrays. */ - pre = XCNEWVEC (int, last_basic_block); - post = XCNEWVEC (int, last_basic_block); + pre = XCNEWVEC (int, last_basic_block_for_fn (cfun)); + post = XCNEWVEC (int, last_basic_block_for_fn (cfun)); /* Allocate stack for back-tracking up CFG. */ - stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); + stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (last_basic_block); + visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); /* None of the nodes in the CFG have been visited yet. */ bitmap_clear (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); + stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); while (sp) { @@ -101,7 +112,8 @@ mark_dfs_back_edges (void) ei_edge (ei)->flags &= ~EDGE_DFS_BACK; /* Check if the edge destination has been visited yet. */ - if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index)) + if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && ! bitmap_bit_p (visited, + dest->index)) { /* Mark that we have visited the destination. */ bitmap_set_bit (visited, dest->index); @@ -118,12 +130,14 @@ mark_dfs_back_edges (void) } else { - if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR + if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) + && src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && pre[src->index] >= pre[dest->index] && post[dest->index] == 0) ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; - if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) + if (ei_one_before_end_p (ei) + && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) post[src->index] = postnum++; if (!ei_one_before_end_p (ei)) @@ -152,18 +166,18 @@ find_unreachable_blocks (void) edge_iterator ei; basic_block *tos, *worklist, bb; - tos = worklist = XNEWVEC (basic_block, n_basic_blocks); + tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); /* Clear all the reachability flags. */ - FOR_EACH_BB (bb) + FOR_EACH_BB_FN (bb, cfun) bb->flags &= ~BB_REACHABLE; /* Add our starting points to the worklist. Almost always there will be only one. It isn't inconceivable that we might one day directly support Fortran alternate entry points. */ - FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) { *tos++ = e->dest; @@ -217,7 +231,8 @@ create_edge_list (void) /* Determine the number of edges in the flow graph by counting successor edges on each basic block. */ num_edges = 0; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), + EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) { num_edges += EDGE_COUNT (bb->succs); } @@ -229,7 +244,8 @@ create_edge_list (void) num_edges = 0; /* Follow successors of blocks, and register these edges. */ - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), + EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) FOR_EACH_EDGE (e, ei, bb->succs) elist->index_to_edge[num_edges++] = e; @@ -256,17 +272,17 @@ print_edge_list (FILE *f, struct edge_list *elist) int x; fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", - n_basic_blocks, elist->num_edges); + n_basic_blocks_for_fn (cfun), elist->num_edges); for (x = 0; x < elist->num_edges; x++) { fprintf (f, " %-4d - edge(", x); - if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) + if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) fprintf (f, "entry,"); else fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); - if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) + if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun)) fprintf (f, "exit)\n"); else fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); @@ -285,7 +301,8 @@ verify_edge_list (FILE *f, struct edge_list *elist) basic_block bb, p, s; edge_iterator ei; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), + EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) { FOR_EACH_EDGE (e, ei, bb->succs) { @@ -310,8 +327,9 @@ verify_edge_list (FILE *f, struct edge_list *elist) /* We've verified that all the edges are in the list, now lets make sure there are no spurious edges in the list. This is an expensive check! */ - FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) - FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) + FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun), + EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) + FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb) { int found_edge = 0; @@ -340,6 +358,122 @@ verify_edge_list (FILE *f, struct edge_list *elist) } } + +/* Functions to compute control dependences. */ + +/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ +void +control_dependences::set_control_dependence_map_bit (basic_block bb, + int edge_index) +{ + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + return; + gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + bitmap_set_bit (control_dependence_map[bb->index], edge_index); +} + +/* Clear all control dependences for block BB. */ +void +control_dependences::clear_control_dependence_bitmap (basic_block bb) +{ + bitmap_clear (control_dependence_map[bb->index]); +} + +/* Find the immediate postdominator PDOM of the specified basic block BLOCK. + This function is necessary because some blocks have negative numbers. */ + +static inline basic_block +find_pdom (basic_block block) +{ + gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun)); + + if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return EXIT_BLOCK_PTR_FOR_FN (cfun); + else + { + basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); + if (! bb) + return EXIT_BLOCK_PTR_FOR_FN (cfun); + return bb; + } +} + +/* Determine all blocks' control dependences on the given edge with edge_list + EL index EDGE_INDEX, ala Morgan, Section 3.6. */ + +void +control_dependences::find_control_dependence (int edge_index) +{ + basic_block current_block; + basic_block ending_block; + + gcc_assert (INDEX_EDGE_PRED_BB (m_el, edge_index) + != EXIT_BLOCK_PTR_FOR_FN (cfun)); + + if (INDEX_EDGE_PRED_BB (m_el, edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + else + ending_block = find_pdom (INDEX_EDGE_PRED_BB (m_el, edge_index)); + + for (current_block = INDEX_EDGE_SUCC_BB (m_el, edge_index); + current_block != ending_block + && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun); + current_block = find_pdom (current_block)) + { + edge e = INDEX_EDGE (m_el, edge_index); + + /* For abnormal edges, we don't make current_block control + dependent because instructions that throw are always necessary + anyway. */ + if (e->flags & EDGE_ABNORMAL) + continue; + + set_control_dependence_map_bit (current_block, edge_index); + } +} + +/* Record all blocks' control dependences on all edges in the edge + list EL, ala Morgan, Section 3.6. */ + +control_dependences::control_dependences (struct edge_list *edges) + : m_el (edges) +{ + timevar_push (TV_CONTROL_DEPENDENCES); + control_dependence_map.create (last_basic_block_for_fn (cfun)); + for (int i = 0; i < last_basic_block_for_fn (cfun); ++i) + control_dependence_map.quick_push (BITMAP_ALLOC (NULL)); + for (int i = 0; i < NUM_EDGES (m_el); ++i) + find_control_dependence (i); + timevar_pop (TV_CONTROL_DEPENDENCES); +} + +/* Free control dependences and the associated edge list. */ + +control_dependences::~control_dependences () +{ + for (unsigned i = 0; i < control_dependence_map.length (); ++i) + BITMAP_FREE (control_dependence_map[i]); + control_dependence_map.release (); + free_edge_list (m_el); +} + +/* Returns the bitmap of edges the basic-block I is dependent on. */ + +bitmap +control_dependences::get_edges_dependent_on (int i) +{ + return control_dependence_map[i]; +} + +/* Returns the edge with index I from the edge list. */ + +edge +control_dependences::get_edge (int i) +{ + return INDEX_EDGE (m_el, i); +} + + /* Given PRED and SUCC blocks, return the edge which connects the blocks. If no such edge exists, return NULL. */ @@ -409,7 +543,7 @@ remove_fake_edges (void) { basic_block bb; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb) remove_fake_predecessors (bb); } @@ -418,7 +552,7 @@ remove_fake_edges (void) void remove_fake_exit_edges (void) { - remove_fake_predecessors (EXIT_BLOCK_PTR); + remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun)); } @@ -431,9 +565,9 @@ add_noreturn_fake_exit_edges (void) { basic_block bb; - FOR_EACH_BB (bb) + FOR_EACH_BB_FN (bb, cfun) if (EDGE_COUNT (bb->succs) == 0) - make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); + make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); } /* This function adds a fake edge between any infinite loops to the @@ -450,14 +584,14 @@ add_noreturn_fake_exit_edges (void) void connect_infinite_loops_to_exit (void) { - basic_block unvisited_block = EXIT_BLOCK_PTR; + basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun); basic_block deadend_block; struct depth_first_search_dsS dfs_ds; /* Perform depth-first search in the reverse graph to find nodes reachable from the exit block. */ flow_dfs_compute_reverse_init (&dfs_ds); - flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); + flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR_FOR_FN (cfun)); /* Repeatedly add fake edges, updating the unreachable nodes. */ while (1) @@ -468,7 +602,7 @@ connect_infinite_loops_to_exit (void) break; deadend_block = dfs_find_deadend (unvisited_block); - make_edge (deadend_block, EXIT_BLOCK_PTR, EDGE_FAKE); + make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); flow_dfs_compute_reverse_add_bb (&dfs_ds, deadend_block); } @@ -495,17 +629,17 @@ post_order_compute (int *post_order, bool include_entry_exit, post_order[post_order_num++] = EXIT_BLOCK; /* Allocate stack for back-tracking up CFG. */ - stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); + stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (last_basic_block); + visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); /* None of the nodes in the CFG have been visited yet. */ bitmap_clear (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); + stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); while (sp) { @@ -519,7 +653,8 @@ post_order_compute (int *post_order, bool include_entry_exit, dest = ei_edge (ei)->dest; /* Check if the edge destination has been visited yet. */ - if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index)) + if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) + && ! bitmap_bit_p (visited, dest->index)) { /* Mark that we have visited the destination. */ bitmap_set_bit (visited, dest->index); @@ -533,7 +668,8 @@ post_order_compute (int *post_order, bool include_entry_exit, } else { - if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) + if (ei_one_before_end_p (ei) + && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) post_order[post_order_num++] = src->index; if (!ei_one_before_end_p (ei)) @@ -553,11 +689,12 @@ post_order_compute (int *post_order, bool include_entry_exit, /* Delete the unreachable blocks if some were found and we are supposed to do it. */ - if (delete_unreachable && (count != n_basic_blocks)) + if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun))) { basic_block b; basic_block next_bb; - for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb) + for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b + != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb) { next_bb = b->next_bb; @@ -648,17 +785,17 @@ inverted_post_order_compute (int *post_order) sbitmap visited; /* Allocate stack for back-tracking up CFG. */ - stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); + stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (last_basic_block); + visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); /* None of the nodes in the CFG have been visited yet. */ bitmap_clear (visited); /* Put all blocks that have no successor into the initial work list. */ - FOR_ALL_BB (bb) + FOR_ALL_BB_FN (bb, cfun) if (EDGE_COUNT (bb->succs) == 0) { /* Push the initial edge on to the stack. */ @@ -699,7 +836,8 @@ inverted_post_order_compute (int *post_order) } else { - if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei)) + if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) + && ei_one_before_end_p (ei)) post_order[post_order_num++] = bb->index; if (!ei_one_before_end_p (ei)) @@ -712,7 +850,8 @@ inverted_post_order_compute (int *post_order) /* Detect any infinite loop and activate the kludge. Note that this doesn't check EXIT_BLOCK itself since EXIT_BLOCK is always added after the outer do-while loop. */ - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), + EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) if (!bitmap_bit_p (visited, bb->index)) { has_unvisited_bb = true; @@ -745,7 +884,7 @@ inverted_post_order_compute (int *post_order) { /* No blocks are reachable from EXIT at all. Find a dead-end from the ENTRY, and restart the iteration. */ - basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR); + basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun)); gcc_assert (be != NULL); bitmap_set_bit (visited, be->index); stack[sp++] = ei_start (be->preds); @@ -764,29 +903,31 @@ inverted_post_order_compute (int *post_order) return post_order_num; } -/* Compute the depth first search order and store in the array - PRE_ORDER if nonzero, marking the nodes visited in VISITED. If - REV_POST_ORDER is nonzero, return the reverse completion number for each - node. Returns the number of nodes visited. A depth first search - tries to get as far away from the starting point as quickly as - possible. +/* Compute the depth first search order of FN and store in the array + PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the + reverse completion number for each node. Returns the number of nodes + visited. A depth first search tries to get as far away from the starting + point as quickly as possible. - pre_order is a really a preorder numbering of the graph. - rev_post_order is really a reverse postorder numbering of the graph. - */ + In case the function has unreachable blocks the number of nodes + visited does not include them. + + pre_order is a really a preorder numbering of the graph. + rev_post_order is really a reverse postorder numbering of the graph. */ int -pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, - bool include_entry_exit) +pre_and_rev_post_order_compute_fn (struct function *fn, + int *pre_order, int *rev_post_order, + bool include_entry_exit) { edge_iterator *stack; int sp; int pre_order_num = 0; - int rev_post_order_num = n_basic_blocks - 1; + int rev_post_order_num = n_basic_blocks_for_fn (cfun) - 1; sbitmap visited; /* Allocate stack for back-tracking up CFG. */ - stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); + stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1); sp = 0; if (include_entry_exit) @@ -801,13 +942,13 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, rev_post_order_num -= NUM_FIXED_BLOCKS; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (last_basic_block); + visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); /* None of the nodes in the CFG have been visited yet. */ bitmap_clear (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); + stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs); while (sp) { @@ -821,7 +962,8 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, dest = ei_edge (ei)->dest; /* Check if the edge destination has been visited yet. */ - if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index)) + if (dest != EXIT_BLOCK_PTR_FOR_FN (fn) + && ! bitmap_bit_p (visited, dest->index)) { /* Mark that we have visited the destination. */ bitmap_set_bit (visited, dest->index); @@ -842,7 +984,8 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, } else { - if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR + if (ei_one_before_end_p (ei) + && src != ENTRY_BLOCK_PTR_FOR_FN (fn) && rev_post_order) /* There are no more successors for the SRC node so assign its reverse completion number. */ @@ -865,13 +1008,29 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, pre_order_num++; if (rev_post_order) rev_post_order[rev_post_order_num--] = EXIT_BLOCK; - /* The number of nodes visited should be the number of blocks. */ - gcc_assert (pre_order_num == n_basic_blocks); } + + return pre_order_num; +} + +/* Like pre_and_rev_post_order_compute_fn but operating on the + current function and asserting that all nodes were visited. */ + +int +pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, + bool include_entry_exit) +{ + int pre_order_num + = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order, + include_entry_exit); + if (include_entry_exit) + /* The number of nodes visited should be the number of blocks. */ + gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun)); else /* The number of nodes visited should be the number of blocks minus the entry and exit blocks which are not visited here. */ - gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS); + gcc_assert (pre_order_num + == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)); return pre_order_num; } @@ -910,11 +1069,11 @@ static void flow_dfs_compute_reverse_init (depth_first_search_ds data) { /* Allocate stack for back-tracking up CFG. */ - data->stack = XNEWVEC (basic_block, n_basic_blocks); + data->stack = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); data->sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - data->visited_blocks = sbitmap_alloc (last_basic_block); + data->visited_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun)); /* None of the nodes in the CFG have been visited yet. */ bitmap_clear (data->visited_blocks); @@ -999,7 +1158,7 @@ dfs_enumerate_from (basic_block bb, int reverse, #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index)) /* Resize the VISITED sbitmap if necessary. */ - size = last_basic_block; + size = last_basic_block_for_fn (cfun); if (size < 10) size = 10; @@ -1088,7 +1247,7 @@ compute_dominance_frontiers_1 (bitmap_head *frontiers) edge p; edge_iterator ei; basic_block b; - FOR_EACH_BB (b) + FOR_EACH_BB_FN (b, cfun) { if (EDGE_COUNT (b->preds) >= 2) { @@ -1096,7 +1255,7 @@ compute_dominance_frontiers_1 (bitmap_head *frontiers) { basic_block runner = p->src; basic_block domsb; - if (runner == ENTRY_BLOCK_PTR) + if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun)) continue; domsb = get_immediate_dominator (CDI_DOMINATORS, b); @@ -1138,11 +1297,10 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) { bitmap_iterator bi; unsigned bb_index, i; - vec work_stack; bitmap phi_insertion_points; /* Each block can appear at most twice on the work-stack. */ - work_stack.create (2 * n_basic_blocks); + auto_vec work_stack (2 * n_basic_blocks_for_fn (cfun)); phi_insertion_points = BITMAP_ALLOC (NULL); /* Seed the work list with all the blocks in DEF_BLOCKS. We use @@ -1166,7 +1324,8 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) form, the basic blocks where new and/or old names are defined may have disappeared by CFG cleanup calls. In this case, we may pull a non-existing block from the work stack. */ - gcc_checking_assert (bb_index < (unsigned) last_basic_block); + gcc_checking_assert (bb_index + < (unsigned) last_basic_block_for_fn (cfun)); EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, 0, i, bi) @@ -1176,8 +1335,6 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) } } - work_stack.release (); - return phi_insertion_points; } @@ -1203,7 +1360,7 @@ bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b) for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) { e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) continue; bitmap_copy (dst, src[e->dest->index]); @@ -1219,7 +1376,7 @@ bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b) SBITMAP_ELT_TYPE *p, *r; e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) continue; p = src[e->dest->index]->elms; @@ -1244,7 +1401,7 @@ bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b) for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) { e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) continue; bitmap_copy (dst, src[e->src->index]); @@ -1260,7 +1417,7 @@ bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b) SBITMAP_ELT_TYPE *p, *r; e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) continue; p = src[e->src->index]->elms; @@ -1285,7 +1442,7 @@ bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b) for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) { e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) continue; bitmap_copy (dst, src[e->dest->index]); @@ -1301,7 +1458,7 @@ bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b) SBITMAP_ELT_TYPE *p, *r; e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) continue; p = src[e->dest->index]->elms; @@ -1326,7 +1483,7 @@ bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b) for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) { e = EDGE_PRED (b, ix); - if (e->src== ENTRY_BLOCK_PTR) + if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun)) continue; bitmap_copy (dst, src[e->src->index]); @@ -1342,7 +1499,7 @@ bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b) SBITMAP_ELT_TYPE *p, *r; e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) continue; p = src[e->src->index]->elms; @@ -1351,3 +1508,56 @@ bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b) *r++ |= *p++; } } + +/* Returns the list of basic blocks in the function in an order that guarantees + that if a block X has just a single predecessor Y, then Y is after X in the + ordering. */ + +basic_block * +single_pred_before_succ_order (void) +{ + basic_block x, y; + basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); + unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; + unsigned np, i; + sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); + +#define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index)) +#define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index)) + + bitmap_clear (visited); + + MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + FOR_EACH_BB_FN (x, cfun) + { + if (VISITED_P (x)) + continue; + + /* Walk the predecessors of x as long as they have precisely one + predecessor and add them to the list, so that they get stored + after x. */ + for (y = x, np = 1; + single_pred_p (y) && !VISITED_P (single_pred (y)); + y = single_pred (y)) + np++; + for (y = x, i = n - np; + single_pred_p (y) && !VISITED_P (single_pred (y)); + y = single_pred (y), i++) + { + order[i] = y; + MARK_VISITED (y); + } + order[i] = y; + MARK_VISITED (y); + + gcc_assert (i == n - 1); + n -= np; + } + + sbitmap_free (visited); + gcc_assert (n == 0); + return order; + +#undef MARK_VISITED +#undef VISITED_P +}