diff options
Diffstat (limited to 'gcc/flow.c')
| -rw-r--r-- | gcc/flow.c | 246 |
1 files changed, 1 insertions, 245 deletions
diff --git a/gcc/flow.c b/gcc/flow.c index 4fc8ac3ab1a..23f3236e0aa 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -6247,250 +6247,6 @@ print_rtl_with_bb (outf, rtx_first) } } -/* Compute dominator relationships using new flow graph structures. */ - -void -compute_flow_dominators (dominators, post_dominators) - sbitmap *dominators; - sbitmap *post_dominators; -{ - int bb; - sbitmap *temp_bitmap; - edge e; - basic_block *worklist, *workend, *qin, *qout; - int qlen; - - /* Allocate a worklist array/queue. Entries are only added to the - list if they were not already on the list. So the size is - bounded by the number of basic blocks. */ - worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks); - workend = &worklist[n_basic_blocks]; - - temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - sbitmap_vector_zero (temp_bitmap, n_basic_blocks); - - if (dominators) - { - /* The optimistic setting of dominators requires us to put every - block on the work list initially. */ - qin = qout = worklist; - for (bb = 0; bb < n_basic_blocks; bb++) - { - *qin++ = BASIC_BLOCK (bb); - BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb); - } - qlen = n_basic_blocks; - qin = worklist; - - /* We want a maximal solution, so initially assume everything dominates - everything else. */ - sbitmap_vector_ones (dominators, n_basic_blocks); - - /* Mark successors of the entry block so we can identify them below. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - e->dest->aux = ENTRY_BLOCK_PTR; - - /* Iterate until the worklist is empty. */ - while (qlen) - { - /* Take the first entry off the worklist. */ - basic_block b = *qout++; - if (qout >= workend) - qout = worklist; - qlen--; - - bb = b->index; - - /* Compute the intersection of the dominators of all the - predecessor blocks. - - If one of the predecessor blocks is the ENTRY block, then the - intersection of the dominators of the predecessor blocks is - defined as the null set. We can identify such blocks by the - special value in the AUX field in the block structure. */ - if (b->aux == ENTRY_BLOCK_PTR) - { - /* Do not clear the aux field for blocks which are - successors of the ENTRY block. That way we never add - them to the worklist again. - - The intersect of dominators of the preds of this block is - defined as the null set. */ - sbitmap_zero (temp_bitmap[bb]); - } - else - { - /* Clear the aux field of this block so it can be added to - the worklist again if necessary. */ - b->aux = NULL; - sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb); - } - - /* Make sure each block always dominates itself. */ - SET_BIT (temp_bitmap[bb], bb); - - /* If the out state of this block changed, then we need to - add the successors of this block to the worklist if they - are not already on the worklist. */ - if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb])) - { - for (e = b->succ; e; e = e->succ_next) - { - if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) - { - *qin++ = e->dest; - if (qin >= workend) - qin = worklist; - qlen++; - - e->dest->aux = e; - } - } - } - } - } - - if (post_dominators) - { - /* The optimistic setting of dominators requires us to put every - block on the work list initially. */ - qin = qout = worklist; - for (bb = 0; bb < n_basic_blocks; bb++) - { - *qin++ = BASIC_BLOCK (bb); - BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb); - } - qlen = n_basic_blocks; - qin = worklist; - - /* We want a maximal solution, so initially assume everything post - dominates everything else. */ - sbitmap_vector_ones (post_dominators, n_basic_blocks); - - /* Mark predecessors of the exit block so we can identify them below. */ - for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) - e->src->aux = EXIT_BLOCK_PTR; - - /* Iterate until the worklist is empty. */ - while (qlen) - { - /* Take the first entry off the worklist. */ - basic_block b = *qout++; - if (qout >= workend) - qout = worklist; - qlen--; - - bb = b->index; - - /* Compute the intersection of the post dominators of all the - successor blocks. - - If one of the successor blocks is the EXIT block, then the - intersection of the dominators of the successor blocks is - defined as the null set. We can identify such blocks by the - special value in the AUX field in the block structure. */ - if (b->aux == EXIT_BLOCK_PTR) - { - /* Do not clear the aux field for blocks which are - predecessors of the EXIT block. That way we we never - add them to the worklist again. - - The intersect of dominators of the succs of this block is - defined as the null set. */ - sbitmap_zero (temp_bitmap[bb]); - } - else - { - /* Clear the aux field of this block so it can be added to - the worklist again if necessary. */ - b->aux = NULL; - sbitmap_intersection_of_succs (temp_bitmap[bb], - post_dominators, bb); - } - - /* Make sure each block always post dominates itself. */ - SET_BIT (temp_bitmap[bb], bb); - - /* If the out state of this block changed, then we need to - add the successors of this block to the worklist if they - are not already on the worklist. */ - if (sbitmap_a_and_b (post_dominators[bb], - post_dominators[bb], - temp_bitmap[bb])) - { - for (e = b->pred; e; e = e->pred_next) - { - if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) - { - *qin++ = e->src; - if (qin >= workend) - qin = worklist; - qlen++; - - e->src->aux = e; - } - } - } - } - } - - free (worklist); - free (temp_bitmap); -} - -/* Given DOMINATORS, compute the immediate dominators into IDOM. If a - block dominates only itself, its entry remains as INVALID_BLOCK. */ - -void -compute_immediate_dominators (idom, dominators) - int *idom; - sbitmap *dominators; -{ - sbitmap *tmp; - int b; - - tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - - /* Begin with tmp(n) = dom(n) - { n }. */ - for (b = n_basic_blocks; --b >= 0;) - { - sbitmap_copy (tmp[b], dominators[b]); - RESET_BIT (tmp[b], b); - } - - /* Subtract out all of our dominator's dominators. */ - for (b = n_basic_blocks; --b >= 0;) - { - sbitmap tmp_b = tmp[b]; - int s; - - for (s = n_basic_blocks; --s >= 0;) - if (TEST_BIT (tmp_b, s)) - sbitmap_difference (tmp_b, tmp_b, tmp[s]); - } - - /* Find the one bit set in the bitmap and put it in the output array. */ - for (b = n_basic_blocks; --b >= 0;) - { - int t; - EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; }); - } - - sbitmap_vector_free (tmp); -} - -/* Given POSTDOMINATORS, compute the immediate postdominators into - IDOM. If a block is only dominated by itself, its entry remains as - INVALID_BLOCK. */ - -void -compute_immediate_postdominators (idom, postdominators) - int *idom; - sbitmap *postdominators; -{ - compute_immediate_dominators (idom, postdominators); -} - /* Recompute register set/reference counts immediately prior to register allocation. @@ -8151,7 +7907,7 @@ flow_loops_find (loops, flags) /* Compute the dominators. */ dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - compute_flow_dominators (dom, NULL); + calculate_dominance_info (NULL, dom, CDI_DOMINATORS); /* Count the number of loop edges (back edges). This should be the same as the number of natural loops. */ |