X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Flcm.c;h=2c0bc8445dbf45cfdda227c5177fc1f1deab7219;hb=f018d957a72d418d69c6d2d8bc80c9415666a9f6;hp=01367e36d5c24e9e33db3587d16540b77b5b0988;hpb=e48ba7aff54ae2017fde5861673bf4855cf155d5;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/lcm.c b/gcc/lcm.c index 01367e36d5c..2c0bc8445db 100644 --- a/gcc/lcm.c +++ b/gcc/lcm.c @@ -1,26 +1,25 @@ -/* Generic partial redundancy elimination with lazy code motion - support. - Copyright (C) 1998 Free Software Foundation, Inc. +/* Generic partial redundancy elimination with lazy code motion support. + Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008 + Free Software Foundation, Inc. -This file is part of GNU CC. +This file is part of GCC. -GNU CC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. -GNU CC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. You should have received a copy of the GNU General Public License -along with GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* These routines are meant to be used by various optimization - passes which can be modeled as lazy code motion problems. + passes which can be modeled as lazy code motion problems. Including, but not limited to: * Traditional partial redundancy elimination. @@ -52,7 +51,8 @@ Boston, MA 02111-1307, USA. */ #include "config.h" #include "system.h" - +#include "coretypes.h" +#include "tm.h" #include "rtl.h" #include "regs.h" #include "hard-reg-set.h" @@ -61,739 +61,750 @@ Boston, MA 02111-1307, USA. */ #include "insn-config.h" #include "recog.h" #include "basic-block.h" - -static void compute_antinout PROTO ((int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); -static void compute_earlyinout PROTO ((int, int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); -static void compute_delayinout PROTO ((int, int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_latein PROTO ((int, int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_isoinout PROTO ((int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); -static void compute_optimal PROTO ((int, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_redundant PROTO ((int, int, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); - -/* Similarly, but for the reversed flowgraph. */ -static void compute_avinout PROTO ((int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); -static void compute_fartherinout PROTO ((int, int, int_list_ptr *, - sbitmap *, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_earlierinout PROTO ((int, int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_firstout PROTO ((int, int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *)); -static void compute_rev_isoinout PROTO ((int, int_list_ptr *, sbitmap *, - sbitmap *, sbitmap *, sbitmap *)); - -/* Given local properties TRANSP, ANTLOC, return the redundant and optimal - computation points for expressions. - - To reduce overall memory consumption, we allocate memory immediately - before its needed and deallocate it as soon as possible. */ -void -pre_lcm (n_blocks, n_exprs, s_preds, s_succs, transp, - antloc, redundant, optimal) - int n_blocks; - int n_exprs; - int_list_ptr *s_preds; - int_list_ptr *s_succs; - sbitmap *transp; - sbitmap *antloc; - sbitmap *redundant; - sbitmap *optimal; -{ - sbitmap *antin, *antout, *earlyin, *earlyout, *delayin, *delayout; - sbitmap *latein, *isoin, *isoout; - - /* Compute global anticipatability. ANTOUT is not needed except to - compute ANTIN, so free its memory as soon as we return from - compute_antinout. */ - antin = sbitmap_vector_alloc (n_blocks, n_exprs); - antout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_antinout (n_blocks, s_succs, antloc, - transp, antin, antout); - free (antout); - antout = NULL; - - /* Compute earliestness. EARLYOUT is not needed except to compute - EARLYIN, so free its memory as soon as we return from - compute_earlyinout. */ - earlyin = sbitmap_vector_alloc (n_blocks, n_exprs); - earlyout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin, - earlyin, earlyout); - free (earlyout); - earlyout = NULL; - - /* Compute delayedness. DELAYOUT is not needed except to compute - DELAYIN, so free its memory as soon as we return from - compute_delayinout. We also no longer need ANTIN and EARLYIN. */ - delayin = sbitmap_vector_alloc (n_blocks, n_exprs); - delayout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_delayinout (n_blocks, n_exprs, s_preds, antloc, - antin, earlyin, delayin, delayout); - free (delayout); - delayout = NULL; - free (antin); - antin = NULL; - free (earlyin); - earlyin = NULL; - - /* Compute latestness. We no longer need DELAYIN after we compute - LATEIN. */ - latein = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein); - free (delayin); - delayin = NULL; - - /* Compute isolatedness. ISOIN is not needed except to compute - ISOOUT, so free its memory as soon as we return from - compute_isoinout. */ - isoin = sbitmap_vector_alloc (n_blocks, n_exprs); - isoout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout); - free (isoin); - isoin = NULL; - - /* Now compute optimal placement points and the redundant expressions. */ - compute_optimal (n_blocks, latein, isoout, optimal); - compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant); - free (latein); - latein = NULL; - free (isoout); - isoout = NULL; -} - -/* Given local properties TRANSP, AVLOC, return the redundant and optimal - computation points for expressions on the reverse flowgraph. - - To reduce overall memory consumption, we allocate memory immediately - before its needed and deallocate it as soon as possible. */ - -void -pre_rev_lcm (n_blocks, n_exprs, s_preds, s_succs, transp, - avloc, redundant, optimal) - int n_blocks; - int n_exprs; - int_list_ptr *s_preds; - int_list_ptr *s_succs; - sbitmap *transp; - sbitmap *avloc; - sbitmap *redundant; - sbitmap *optimal; -{ - sbitmap *avin, *avout, *fartherin, *fartherout, *earlierin, *earlierout; - sbitmap *firstout, *rev_isoin, *rev_isoout; - - /* Compute global availability. AVIN is not needed except to - compute AVOUT, so free its memory as soon as we return from - compute_avinout. */ - avin = sbitmap_vector_alloc (n_blocks, n_exprs); - avout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout); - free (avin); - avin = NULL; - - /* Compute fartherness. FARTHERIN is not needed except to compute - FARTHEROUT, so free its memory as soon as we return from - compute_earlyinout. */ - fartherin = sbitmap_vector_alloc (n_blocks, n_exprs); - fartherout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_fartherinout (n_blocks, n_exprs, s_succs, transp, - avout, fartherin, fartherout); - free (fartherin); - fartherin = NULL; - - /* Compute earlierness. EARLIERIN is not needed except to compute - EARLIEROUT, so free its memory as soon as we return from - compute_delayinout. We also no longer need AVOUT and FARTHEROUT. */ - earlierin = sbitmap_vector_alloc (n_blocks, n_exprs); - earlierout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_earlierinout (n_blocks, n_exprs, s_succs, avloc, - avout, fartherout, earlierin, earlierout); - free (earlierin); - earlierin = NULL; - free (avout); - avout = NULL; - free (fartherout); - fartherout = NULL; - - /* Compute firstness. We no longer need EARLIEROUT after we compute - FIRSTOUT. */ - firstout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout); - free (earlierout); - earlierout = NULL; - - /* Compute rev_isolatedness. ISOIN is not needed except to compute - ISOOUT, so free its memory as soon as we return from - compute_isoinout. */ - rev_isoin = sbitmap_vector_alloc (n_blocks, n_exprs); - rev_isoout = sbitmap_vector_alloc (n_blocks, n_exprs); - compute_rev_isoinout (n_blocks, s_preds, avloc, firstout, - rev_isoin, rev_isoout); - free (rev_isoout); - rev_isoout = NULL; - - /* Now compute optimal placement points and the redundant expressions. */ - compute_optimal (n_blocks, firstout, rev_isoin, optimal); - compute_redundant (n_blocks, n_exprs, avloc, firstout, rev_isoin, redundant); - free (firstout); - firstout = NULL; - free (rev_isoin); - rev_isoin = NULL; -} - -/* Compute expression anticipatability at entrance and exit of each block. */ +#include "output.h" +#include "tm_p.h" +#include "function.h" + +/* We want target macros for the mode switching code to be able to refer + to instruction attribute values. */ +#include "insn-attr.h" + +/* Edge based LCM routines. */ +static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *); +static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *, + sbitmap *, sbitmap *, sbitmap *); +static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *, + sbitmap *, sbitmap *); +static void compute_insert_delete (struct edge_list *edge_list, sbitmap *, + sbitmap *, sbitmap *, sbitmap *, sbitmap *); + +/* Edge based LCM routines on a reverse flowgraph. */ +static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *, + sbitmap*, sbitmap *, sbitmap *); +static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *, + sbitmap *, sbitmap *); +static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *, + sbitmap *, sbitmap *, sbitmap *, + sbitmap *); + +/* Edge based lcm routines. */ + +/* Compute expression anticipatability at entrance and exit of each block. + This is done based on the flow graph, and not on the pred-succ lists. + Other than that, its pretty much identical to compute_antinout. */ static void -compute_antinout (n_blocks, s_succs, antloc, transp, antin, antout) - int n_blocks; - int_list_ptr *s_succs; - sbitmap *antloc; - sbitmap *transp; - sbitmap *antin; - sbitmap *antout; +compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, + sbitmap *antout) { - int bb, changed, passes; - sbitmap old_changed, new_changed; + basic_block bb; + edge e; + basic_block *worklist, *qin, *qout, *qend; + unsigned int qlen; + edge_iterator ei; + + /* 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. */ + qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks); + + /* We want a maximal solution, so make an optimistic initialization of + ANTIN. */ + sbitmap_vector_ones (antin, last_basic_block); + + /* Put every block on the worklist; this is necessary because of the + optimistic initialization of ANTIN above. */ + FOR_EACH_BB_REVERSE (bb) + { + *qin++ = bb; + bb->aux = bb; + } - sbitmap_zero (antout[n_blocks - 1]); - sbitmap_vector_ones (antin, n_blocks); + qin = worklist; + qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks - NUM_FIXED_BLOCKS; - old_changed = sbitmap_alloc (n_blocks); - new_changed = sbitmap_alloc (n_blocks); - sbitmap_ones (old_changed); + /* Mark blocks which are predecessors of the exit block so that we + can easily identify them below. */ + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) + e->src->aux = EXIT_BLOCK_PTR; - passes = 0; - changed = 1; - while (changed) + /* Iterate until the worklist is empty. */ + while (qlen) { - changed = 0; - sbitmap_zero (new_changed); - /* We scan the blocks in the reverse order to speed up - the convergence. */ - for (bb = n_blocks - 1; bb >= 0; bb--) + /* Take the first entry off the worklist. */ + bb = *qout++; + qlen--; + + if (qout >= qend) + qout = worklist; + + if (bb->aux == EXIT_BLOCK_PTR) + /* Do not clear the aux field for blocks which are predecessors of + the EXIT block. That way we never add then to the worklist + again. */ + sbitmap_zero (antout[bb->index]); + else { - int_list_ptr ps; - - /* If none of the successors of this block have changed, - then this block is not going to change. */ - for (ps = s_succs[bb] ; ps; ps = ps->next) - { - if (INT_LIST_VAL (ps) == EXIT_BLOCK - || INT_LIST_VAL (ps) == ENTRY_BLOCK) - break; - - if (TEST_BIT (old_changed, INT_LIST_VAL (ps)) - || TEST_BIT (new_changed, INT_LIST_VAL (ps))) - break; - } - - if (!ps) - continue; + /* Clear the aux field of this block so that it can be added to + the worklist again if necessary. */ + bb->aux = NULL; + sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index); + } - if (bb != n_blocks - 1) - sbitmap_intersect_of_successors (antout[bb], antin, - bb, s_succs); - if (sbitmap_a_or_b_and_c (antin[bb], antloc[bb], - transp[bb], antout[bb])) + if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index], + transp[bb->index], antout[bb->index])) + /* If the in state of this block changed, then we need + to add the predecessors of this block to the worklist + if they are not already on the worklist. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) { - changed = 1; - SET_BIT (new_changed, bb); + *qin++ = e->src; + e->src->aux = e; + qlen++; + if (qin >= qend) + qin = worklist; } - } - sbitmap_copy (old_changed, new_changed); - passes++; } - free (old_changed); - free (new_changed); -} - -/* Compute expression earliestness at entrance and exit of each block. - From Advanced Compiler Design and Implementation pp411. + clear_aux_for_edges (); + clear_aux_for_blocks (); + free (worklist); +} - An expression is earliest at the entrance to basic block BB if no - block from entry to block BB both evaluates the expression and - produces the same value as evaluating it at the entry to block BB - does. Similarly for earlistness at basic block BB exit. */ +/* Compute the earliest vector for edge based lcm. */ static void -compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin, - earlyin, earlyout) - int n_blocks; - int n_exprs; - int_list_ptr *s_preds; - sbitmap *transp; - sbitmap *antin; - sbitmap *earlyin; - sbitmap *earlyout; +compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, + sbitmap *antout, sbitmap *avout, sbitmap *kill, + sbitmap *earliest) { - int bb, changed, passes; - sbitmap temp_bitmap; - sbitmap old_changed, new_changed; - - temp_bitmap = sbitmap_alloc (n_exprs); + sbitmap difference, temp_bitmap; + int x, num_edges; + basic_block pred, succ; - sbitmap_vector_zero (earlyout, n_blocks); - sbitmap_ones (earlyin[0]); + num_edges = NUM_EDGES (edge_list); - old_changed = sbitmap_alloc (n_blocks); - new_changed = sbitmap_alloc (n_blocks); - sbitmap_ones (old_changed); + difference = sbitmap_alloc (n_exprs); + temp_bitmap = sbitmap_alloc (n_exprs); - passes = 0; - changed = 1; - while (changed) + for (x = 0; x < num_edges; x++) { - changed = 0; - sbitmap_zero (new_changed); - for (bb = 0; bb < n_blocks; bb++) + pred = INDEX_EDGE_PRED_BB (edge_list, x); + succ = INDEX_EDGE_SUCC_BB (edge_list, x); + if (pred == ENTRY_BLOCK_PTR) + sbitmap_copy (earliest[x], antin[succ->index]); + else { - int_list_ptr ps; - - /* If none of the predecessors of this block have changed, - then this block is not going to change. */ - for (ps = s_preds[bb] ; ps; ps = ps->next) + if (succ == EXIT_BLOCK_PTR) + sbitmap_zero (earliest[x]); + else { - if (INT_LIST_VAL (ps) == EXIT_BLOCK - || INT_LIST_VAL (ps) == ENTRY_BLOCK) - break; - - if (TEST_BIT (old_changed, INT_LIST_VAL (ps)) - || TEST_BIT (new_changed, INT_LIST_VAL (ps))) - break; - } - - if (!ps) - continue; - - if (bb != 0) - sbitmap_union_of_predecessors (earlyin[bb], earlyout, - bb, s_preds); - sbitmap_not (temp_bitmap, transp[bb]); - if (sbitmap_union_of_diff (earlyout[bb], temp_bitmap, - earlyin[bb], antin[bb])) - { - changed = 1; - SET_BIT (new_changed, bb); + sbitmap_difference (difference, antin[succ->index], + avout[pred->index]); + sbitmap_not (temp_bitmap, antout[pred->index]); + sbitmap_a_and_b_or_c (earliest[x], difference, + kill[pred->index], temp_bitmap); } } - sbitmap_copy (old_changed, new_changed); - passes++; } - free (old_changed); - free (new_changed); - free (temp_bitmap); + + sbitmap_free (temp_bitmap); + sbitmap_free (difference); } -/* Compute expression delayedness at entrance and exit of each block. +/* later(p,s) is dependent on the calculation of laterin(p). + laterin(p) is dependent on the calculation of later(p2,p). + + laterin(ENTRY) is defined as all 0's + later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY) + laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)). + + If we progress in this manner, starting with all basic blocks + in the work list, anytime we change later(bb), we need to add + succs(bb) to the worklist if they are not already on the worklist. + + Boundary conditions: + + We prime the worklist all the normal basic blocks. The ENTRY block can + never be added to the worklist since it is never the successor of any + block. We explicitly prevent the EXIT block from being added to the + worklist. - From Advanced Compiler Design and Implementation pp411. + We optimistically initialize LATER. That is the only time this routine + will compute LATER for an edge out of the entry block since the entry + block is never on the worklist. Thus, LATERIN is neither used nor + computed for the ENTRY block. - An expression is delayed at the entrance to BB if it is anticipatable - and earliest at that point and if all subsequent computations of - the expression are in block BB. */ + Since the EXIT block is never added to the worklist, we will neither + use nor compute LATERIN for the exit block. Edges which reach the + EXIT block are handled in the normal fashion inside the loop. However, + the insertion/deletion computation needs LATERIN(EXIT), so we have + to compute it. */ static void -compute_delayinout (n_blocks, n_exprs, s_preds, antloc, - antin, earlyin, delayin, delayout) - int n_blocks; - int n_exprs; - int_list_ptr *s_preds; - sbitmap *antloc; - sbitmap *antin; - sbitmap *earlyin; - sbitmap *delayin; - sbitmap *delayout; +compute_laterin (struct edge_list *edge_list, sbitmap *earliest, + sbitmap *antloc, sbitmap *later, sbitmap *laterin) { - int bb, changed, passes; - sbitmap *anti_and_early; - sbitmap temp_bitmap; + int num_edges, i; + edge e; + basic_block *worklist, *qin, *qout, *qend, bb; + unsigned int qlen; + edge_iterator ei; + + num_edges = NUM_EDGES (edge_list); + + /* 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. */ + qin = qout = worklist + = XNEWVEC (basic_block, n_basic_blocks); + + /* Initialize a mapping from each edge to its index. */ + for (i = 0; i < num_edges; i++) + INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; + + /* We want a maximal solution, so initially consider LATER true for + all edges. This allows propagation through a loop since the incoming + loop edge will have LATER set, so if all the other incoming edges + to the loop are set, then LATERIN will be set for the head of the + loop. + + If the optimistic setting of LATER on that edge was incorrect (for + example the expression is ANTLOC in a block within the loop) then + this algorithm will detect it when we process the block at the head + of the optimistic edge. That will requeue the affected blocks. */ + sbitmap_vector_ones (later, num_edges); + + /* Note that even though we want an optimistic setting of LATER, we + do not want to be overly optimistic. Consider an outgoing edge from + the entry block. That edge should always have a LATER value the + same as EARLIEST for that edge. */ + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) + sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]); + + /* Add all the blocks to the worklist. This prevents an early exit from + the loop given our optimistic initialization of LATER above. */ + FOR_EACH_BB (bb) + { + *qin++ = bb; + bb->aux = bb; + } - temp_bitmap = sbitmap_alloc (n_exprs); + /* Note that we do not use the last allocated element for our queue, + as EXIT_BLOCK is never inserted into it. */ + qin = worklist; + qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks - NUM_FIXED_BLOCKS; - /* This is constant throughout the flow equations below, so compute - it once to save time. */ - anti_and_early = sbitmap_vector_alloc (n_blocks, n_exprs); - for (bb = 0; bb < n_blocks; bb++) - sbitmap_a_and_b (anti_and_early[bb], antin[bb], earlyin[bb]); - - sbitmap_vector_zero (delayout, n_blocks); - sbitmap_copy (delayin[0], anti_and_early[0]); - - passes = 0; - changed = 1; - while (changed) + /* Iterate until the worklist is empty. */ + while (qlen) { - changed = 0; - for (bb = 0; bb < n_blocks; bb++) - { - if (bb != 0) - { - sbitmap_intersect_of_predecessors (temp_bitmap, delayout, - bb, s_preds); - changed |= sbitmap_a_or_b (delayin[bb], - anti_and_early[bb], - temp_bitmap); - } - sbitmap_not (temp_bitmap, antloc[bb]); - changed |= sbitmap_a_and_b (delayout[bb], - temp_bitmap, - delayin[bb]); - } - passes++; + /* Take the first entry off the worklist. */ + bb = *qout++; + bb->aux = NULL; + qlen--; + if (qout >= qend) + qout = worklist; + + /* Compute the intersection of LATERIN for each incoming edge to B. */ + sbitmap_ones (laterin[bb->index]); + FOR_EACH_EDGE (e, ei, bb->preds) + sbitmap_a_and_b (laterin[bb->index], laterin[bb->index], + later[(size_t)e->aux]); + + /* Calculate LATER for all outgoing edges. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (sbitmap_union_of_diff_cg (later[(size_t) e->aux], + earliest[(size_t) e->aux], + laterin[e->src->index], + antloc[e->src->index]) + /* If LATER for an outgoing edge was changed, then we need + to add the target of the outgoing edge to the worklist. */ + && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0) + { + *qin++ = e->dest; + e->dest->aux = e; + qlen++; + if (qin >= qend) + qin = worklist; + } } - /* We're done with this, so go ahead and free it's memory now instead - of waiting until the end of pre. */ - free (anti_and_early); - free (temp_bitmap); + /* Computation of insertion and deletion points requires computing LATERIN + for the EXIT block. We allocated an extra entry in the LATERIN array + for just this purpose. */ + sbitmap_ones (laterin[last_basic_block]); + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) + sbitmap_a_and_b (laterin[last_basic_block], + laterin[last_basic_block], + later[(size_t) e->aux]); + + clear_aux_for_edges (); + free (worklist); } -/* Compute latestness. - - From Advanced Compiler Design and Implementation pp412. - - An expression is latest at the entrance to block BB if that is an optimal - point for computing the expression and if on every path from block BB's - entrance to the exit block, any optimal computation point for the - expression occurs after one of the points at which the expression was - computed in the original flowgraph. */ +/* Compute the insertion and deletion points for edge based LCM. */ static void -compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein) - int n_blocks; - int n_exprs; - int_list_ptr *s_succs; - sbitmap *antloc; - sbitmap *delayin; - sbitmap *latein; +compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, + sbitmap *later, sbitmap *laterin, sbitmap *insert, + sbitmap *del) { - int bb; - sbitmap temp_bitmap; + int x; + basic_block bb; - temp_bitmap = sbitmap_alloc (n_exprs); + FOR_EACH_BB (bb) + sbitmap_difference (del[bb->index], antloc[bb->index], + laterin[bb->index]); - for (bb = 0; bb < n_blocks; bb++) + for (x = 0; x < NUM_EDGES (edge_list); x++) { - /* The last block is succeeded only by the exit block; therefore, - temp_bitmap will not be set by the following call! */ - if (bb == n_blocks - 1) - { - sbitmap_intersect_of_successors (temp_bitmap, delayin, - bb, s_succs); - sbitmap_not (temp_bitmap, temp_bitmap); - } + basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); + + if (b == EXIT_BLOCK_PTR) + sbitmap_difference (insert[x], later[x], laterin[last_basic_block]); else - sbitmap_ones (temp_bitmap); - sbitmap_a_and_b_or_c (latein[bb], delayin[bb], - antloc[bb], temp_bitmap); + sbitmap_difference (insert[x], later[x], laterin[b->index]); } - free (temp_bitmap); } -/* Compute isolated. - - From Advanced Compiler Design and Implementation pp413. +/* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and + delete vectors for edge based LCM. Returns an edgelist which is used to + map the insert vector to what edge an expression should be inserted on. */ - A computationally optimal placement for the evaluation of an expression - is defined to be isolated if and only if on every path from a successor - of the block in which it is computed to the exit block, every original - computation of the expression is preceded by the optimal placement point. */ - -static void -compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout) - int n_blocks; - int_list_ptr *s_succs; - sbitmap *antloc; - sbitmap *latein; - sbitmap *isoin; - sbitmap *isoout; +struct edge_list * +pre_edge_lcm (int n_exprs, sbitmap *transp, + sbitmap *avloc, sbitmap *antloc, sbitmap *kill, + sbitmap **insert, sbitmap **del) { - int bb, changed, passes; + sbitmap *antin, *antout, *earliest; + sbitmap *avin, *avout; + sbitmap *later, *laterin; + struct edge_list *edge_list; + int num_edges; - sbitmap_vector_zero (isoin, n_blocks); - sbitmap_zero (isoout[n_blocks - 1]); + edge_list = create_edge_list (); + num_edges = NUM_EDGES (edge_list); - passes = 0; - changed = 1; - while (changed) +#ifdef LCM_DEBUG_INFO + if (dump_file) { - changed = 0; - for (bb = n_blocks - 1; bb >= 0; bb--) - { - if (bb != n_blocks - 1) - sbitmap_intersect_of_successors (isoout[bb], isoin, - bb, s_succs); - changed |= sbitmap_union_of_diff (isoin[bb], latein[bb], - isoout[bb], antloc[bb]); - } - passes++; + fprintf (dump_file, "Edge List:\n"); + verify_edge_list (dump_file, edge_list); + print_edge_list (dump_file, edge_list); + dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); + dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block); + dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block); + dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block); } -} +#endif -/* Compute the set of expressions which have optimal computational points - in each basic block. This is the set of expressions that are latest, but - that are not isolated in the block. */ + /* Compute global availability. */ + avin = sbitmap_vector_alloc (last_basic_block, n_exprs); + avout = sbitmap_vector_alloc (last_basic_block, n_exprs); + compute_available (avloc, kill, avout, avin); + sbitmap_vector_free (avin); -static void -compute_optimal (n_blocks, latein, isoout, optimal) - int n_blocks; - sbitmap *latein; - sbitmap *isoout; - sbitmap *optimal; -{ - int bb; + /* Compute global anticipatability. */ + antin = sbitmap_vector_alloc (last_basic_block, n_exprs); + antout = sbitmap_vector_alloc (last_basic_block, n_exprs); + compute_antinout_edge (antloc, transp, antin, antout); - for (bb = 0; bb < n_blocks; bb++) - sbitmap_difference (optimal[bb], latein[bb], isoout[bb]); -} +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block); + dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block); + } +#endif -/* Compute the set of expressions that are redundant in a block. They are - the expressions that are used in the block and that are neither isolated - or latest. */ + /* Compute earliestness. */ + earliest = sbitmap_vector_alloc (num_edges, n_exprs); + compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); -static void -compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant) - int n_blocks; - int n_exprs; - sbitmap *antloc; - sbitmap *latein; - sbitmap *isoout; - sbitmap *redundant; -{ - int bb; - sbitmap temp_bitmap; +#ifdef LCM_DEBUG_INFO + if (dump_file) + dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges); +#endif - temp_bitmap = sbitmap_alloc (n_exprs); + sbitmap_vector_free (antout); + sbitmap_vector_free (antin); + sbitmap_vector_free (avout); - for (bb = 0; bb < n_blocks; bb++) + later = sbitmap_vector_alloc (num_edges, n_exprs); + + /* Allocate an extra element for the exit block in the laterin vector. */ + laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); + compute_laterin (edge_list, earliest, antloc, later, laterin); + +#ifdef LCM_DEBUG_INFO + if (dump_file) { - sbitmap_a_or_b (temp_bitmap, latein[bb], isoout[bb]); - sbitmap_difference (redundant[bb], antloc[bb], temp_bitmap); + dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1); + dump_sbitmap_vector (dump_file, "later", "", later, num_edges); } - free (temp_bitmap); -} +#endif -/* Compute expression availability at entrance and exit of each block. */ + sbitmap_vector_free (earliest); -static void -compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout) - int n_blocks; - int_list_ptr *s_preds; - sbitmap *avloc; - sbitmap *transp; - sbitmap *avin; - sbitmap *avout; -{ - int bb, changed, passes; + *insert = sbitmap_vector_alloc (num_edges, n_exprs); + *del = sbitmap_vector_alloc (last_basic_block, n_exprs); + compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del); - sbitmap_zero (avin[0]); - sbitmap_vector_ones (avout, n_blocks); + sbitmap_vector_free (laterin); + sbitmap_vector_free (later); - passes = 0; - changed = 1; - while (changed) +#ifdef LCM_DEBUG_INFO + if (dump_file) { - changed = 0; - for (bb = 0; bb < n_blocks; bb++) - { - if (bb != 0) - sbitmap_intersect_of_predecessors (avin[bb], avout, - bb, s_preds); - changed |= sbitmap_a_or_b_and_c (avout[bb], avloc[bb], - transp[bb], avin[bb]); - } - passes++; + dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); + dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, + last_basic_block); } -} +#endif -/* Compute expression latestness. + return edge_list; +} - This is effectively the same as earliestness computed on the reverse - flow graph. */ +/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. + Return the number of passes we performed to iterate to a solution. */ -static void -compute_fartherinout (n_blocks, n_exprs, s_succs, - transp, avout, fartherin, fartherout) - int n_blocks; - int n_exprs; - int_list_ptr *s_succs; - sbitmap *transp; - sbitmap *avout; - sbitmap *fartherin; - sbitmap *fartherout; +void +compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, + sbitmap *avin) { - int bb, changed, passes; - sbitmap temp_bitmap; + edge e; + basic_block *worklist, *qin, *qout, *qend, bb; + unsigned int qlen; + edge_iterator ei; + + /* 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. */ + qin = qout = worklist = + XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS); + + /* We want a maximal solution. */ + sbitmap_vector_ones (avout, last_basic_block); + + /* Put every block on the worklist; this is necessary because of the + optimistic initialization of AVOUT above. */ + FOR_EACH_BB (bb) + { + *qin++ = bb; + bb->aux = bb; + } - temp_bitmap = sbitmap_alloc (n_exprs); + qin = worklist; + qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks - NUM_FIXED_BLOCKS; - sbitmap_vector_zero (fartherin, n_blocks); - sbitmap_ones (fartherout[n_blocks - 1]); + /* Mark blocks which are successors of the entry block so that we + can easily identify them below. */ + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) + e->dest->aux = ENTRY_BLOCK_PTR; - passes = 0; - changed = 1; - while (changed) + /* Iterate until the worklist is empty. */ + while (qlen) { - changed = 0; - for (bb = n_blocks - 1; bb >= 0; bb--) + /* Take the first entry off the worklist. */ + bb = *qout++; + qlen--; + + if (qout >= qend) + qout = worklist; + + /* If one of the predecessor blocks is the ENTRY block, then the + intersection of avouts is the null set. We can identify such blocks + by the special value in the AUX field in the block structure. */ + if (bb->aux == ENTRY_BLOCK_PTR) + /* Do not clear the aux field for blocks which are successors of the + ENTRY block. That way we never add then to the worklist again. */ + sbitmap_zero (avin[bb->index]); + else { - if (bb != n_blocks - 1) - sbitmap_union_of_successors (fartherout[bb], fartherin, - bb, s_succs); - sbitmap_not (temp_bitmap, transp[bb]); - changed |= sbitmap_union_of_diff (fartherin[bb], temp_bitmap, - fartherout[bb], avout[bb]); + /* Clear the aux field of this block so that it can be added to + the worklist again if necessary. */ + bb->aux = NULL; + sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index); } - passes++; + + if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index], + avin[bb->index], kill[bb->index])) + /* 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. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) + { + *qin++ = e->dest; + e->dest->aux = e; + qlen++; + + if (qin >= qend) + qin = worklist; + } } - free (temp_bitmap); + clear_aux_for_edges (); + clear_aux_for_blocks (); + free (worklist); } -/* Compute expression earlierness at entrance and exit of each block. - - This is effectively the same as delayedness computed on the reverse - flow graph. */ +/* Compute the farthest vector for edge based lcm. */ static void -compute_earlierinout (n_blocks, n_exprs, s_succs, avloc, - avout, fartherout, earlierin, earlierout) - int n_blocks; - int n_exprs; - int_list_ptr *s_succs; - sbitmap *avloc; - sbitmap *avout; - sbitmap *fartherout; - sbitmap *earlierin; - sbitmap *earlierout; +compute_farthest (struct edge_list *edge_list, int n_exprs, + sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin, + sbitmap *kill, sbitmap *farthest) { - int bb, changed, passes; - sbitmap *av_and_farther; - sbitmap temp_bitmap; + sbitmap difference, temp_bitmap; + int x, num_edges; + basic_block pred, succ; + num_edges = NUM_EDGES (edge_list); + + difference = sbitmap_alloc (n_exprs); temp_bitmap = sbitmap_alloc (n_exprs); - /* This is constant throughout the flow equations below, so compute - it once to save time. */ - av_and_farther = sbitmap_vector_alloc (n_blocks, n_exprs); - for (bb = 0; bb < n_blocks; bb++) - sbitmap_a_and_b (av_and_farther[bb], avout[bb], fartherout[bb]); - - sbitmap_vector_zero (earlierin, n_blocks); - sbitmap_copy (earlierout[n_blocks - 1], av_and_farther[n_blocks - 1]); - - passes = 0; - changed = 1; - while (changed) + for (x = 0; x < num_edges; x++) { - changed = 0; - for (bb = n_blocks - 1; bb >= 0; bb--) + pred = INDEX_EDGE_PRED_BB (edge_list, x); + succ = INDEX_EDGE_SUCC_BB (edge_list, x); + if (succ == EXIT_BLOCK_PTR) + sbitmap_copy (farthest[x], st_avout[pred->index]); + else { - if (bb != n_blocks - 1) + if (pred == ENTRY_BLOCK_PTR) + sbitmap_zero (farthest[x]); + else { - sbitmap_intersect_of_successors (temp_bitmap, earlierin, - bb, s_succs); - changed |= sbitmap_a_or_b (earlierout[bb], - av_and_farther[bb], - temp_bitmap); + sbitmap_difference (difference, st_avout[pred->index], + st_antin[succ->index]); + sbitmap_not (temp_bitmap, st_avin[succ->index]); + sbitmap_a_and_b_or_c (farthest[x], difference, + kill[succ->index], temp_bitmap); } - sbitmap_not (temp_bitmap, avloc[bb]); - changed |= sbitmap_a_and_b (earlierin[bb], - temp_bitmap, - earlierout[bb]); } - passes++; } - /* We're done with this, so go ahead and free it's memory now instead - of waiting until the end of pre. */ - free (av_and_farther); - free (temp_bitmap); + sbitmap_free (temp_bitmap); + sbitmap_free (difference); } -/* Compute firstness. +/* Compute nearer and nearerout vectors for edge based lcm. - This is effectively the same as latestness computed on the reverse - flow graph. */ + This is the mirror of compute_laterin, additional comments on the + implementation can be found before compute_laterin. */ static void -compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout) - int n_blocks; - int n_exprs; - int_list_ptr *s_preds; - sbitmap *avloc; - sbitmap *earlierout; - sbitmap *firstout; +compute_nearerout (struct edge_list *edge_list, sbitmap *farthest, + sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout) { - int bb; - sbitmap temp_bitmap; + int num_edges, i; + edge e; + basic_block *worklist, *tos, bb; + edge_iterator ei; + + num_edges = NUM_EDGES (edge_list); + + /* 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. */ + tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); + + /* Initialize NEARER for each edge and build a mapping from an edge to + its index. */ + for (i = 0; i < num_edges; i++) + INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; + + /* We want a maximal solution. */ + sbitmap_vector_ones (nearer, num_edges); + + /* Note that even though we want an optimistic setting of NEARER, we + do not want to be overly optimistic. Consider an incoming edge to + the exit block. That edge should always have a NEARER value the + same as FARTHEST for that edge. */ + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) + sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]); + + /* Add all the blocks to the worklist. This prevents an early exit + from the loop given our optimistic initialization of NEARER. */ + FOR_EACH_BB (bb) + { + *tos++ = bb; + bb->aux = bb; + } - temp_bitmap = sbitmap_alloc (n_exprs); + /* Iterate until the worklist is empty. */ + while (tos != worklist) + { + /* Take the first entry off the worklist. */ + bb = *--tos; + bb->aux = NULL; + + /* Compute the intersection of NEARER for each outgoing edge from B. */ + sbitmap_ones (nearerout[bb->index]); + FOR_EACH_EDGE (e, ei, bb->succs) + sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index], + nearer[(size_t) e->aux]); + + /* Calculate NEARER for all incoming edges. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux], + farthest[(size_t) e->aux], + nearerout[e->dest->index], + st_avloc[e->dest->index]) + /* If NEARER for an incoming edge was changed, then we need + to add the source of the incoming edge to the worklist. */ + && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0) + { + *tos++ = e->src; + e->src->aux = e; + } + } - for (bb = 0; bb < n_blocks; bb++) + /* Computation of insertion and deletion points requires computing NEAREROUT + for the ENTRY block. We allocated an extra entry in the NEAREROUT array + for just this purpose. */ + sbitmap_ones (nearerout[last_basic_block]); + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) + sbitmap_a_and_b (nearerout[last_basic_block], + nearerout[last_basic_block], + nearer[(size_t) e->aux]); + + clear_aux_for_edges (); + free (tos); +} + +/* Compute the insertion and deletion points for edge based LCM. */ + +static void +compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc, + sbitmap *nearer, sbitmap *nearerout, + sbitmap *insert, sbitmap *del) +{ + int x; + basic_block bb; + + FOR_EACH_BB (bb) + sbitmap_difference (del[bb->index], st_avloc[bb->index], + nearerout[bb->index]); + + for (x = 0; x < NUM_EDGES (edge_list); x++) { - /* The first block is preceded only by the entry block; therefore, - temp_bitmap will not be set by the following call! */ - if (bb != 0) - { - sbitmap_intersect_of_predecessors (temp_bitmap, earlierout, - bb, s_preds); - sbitmap_not (temp_bitmap, temp_bitmap); - } + basic_block b = INDEX_EDGE_PRED_BB (edge_list, x); + if (b == ENTRY_BLOCK_PTR) + sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]); else - { - sbitmap_ones (temp_bitmap); - } - sbitmap_a_and_b_or_c (firstout[bb], earlierout[bb], - avloc[bb], temp_bitmap); + sbitmap_difference (insert[x], nearer[x], nearerout[b->index]); } - free (temp_bitmap); } -/* Compute reverse isolated. +/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the + insert and delete vectors for edge based reverse LCM. Returns an + edgelist which is used to map the insert vector to what edge + an expression should be inserted on. */ - This is effectively the same as isolatedness computed on the reverse - flow graph. */ - -static void -compute_rev_isoinout (n_blocks, s_preds, avloc, firstout, - rev_isoin, rev_isoout) - int n_blocks; - int_list_ptr *s_preds; - sbitmap *avloc; - sbitmap *firstout; - sbitmap *rev_isoin; - sbitmap *rev_isoout; +struct edge_list * +pre_edge_rev_lcm (int n_exprs, sbitmap *transp, + sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, + sbitmap **insert, sbitmap **del) { - int bb, changed, passes; + sbitmap *st_antin, *st_antout; + sbitmap *st_avout, *st_avin, *farthest; + sbitmap *nearer, *nearerout; + struct edge_list *edge_list; + int num_edges; + + edge_list = create_edge_list (); + num_edges = NUM_EDGES (edge_list); + + st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs); + st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs); + sbitmap_vector_zero (st_antin, last_basic_block); + sbitmap_vector_zero (st_antout, last_basic_block); + compute_antinout_edge (st_antloc, transp, st_antin, st_antout); + + /* Compute global anticipatability. */ + st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs); + st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs); + compute_available (st_avloc, kill, st_avout, st_avin); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + fprintf (dump_file, "Edge List:\n"); + verify_edge_list (dump_file, edge_list); + print_edge_list (dump_file, edge_list); + dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); + dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); + dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); + dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block); + dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block); + dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block); + } +#endif - sbitmap_vector_zero (rev_isoout, n_blocks); - sbitmap_zero (rev_isoin[0]); +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block); + dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block); + } +#endif - passes = 0; - changed = 1; - while (changed) + /* Compute farthestness. */ + farthest = sbitmap_vector_alloc (num_edges, n_exprs); + compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin, + kill, farthest); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges); +#endif + + sbitmap_vector_free (st_antin); + sbitmap_vector_free (st_antout); + + sbitmap_vector_free (st_avin); + sbitmap_vector_free (st_avout); + + nearer = sbitmap_vector_alloc (num_edges, n_exprs); + + /* Allocate an extra element for the entry block. */ + nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); + compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout); + +#ifdef LCM_DEBUG_INFO + if (dump_file) { - changed = 0; - for (bb = 0; bb < n_blocks; bb++) - { - if (bb != 0) - sbitmap_intersect_of_predecessors (rev_isoin[bb], rev_isoout, - bb, s_preds); - changed |= sbitmap_union_of_diff (rev_isoout[bb], firstout[bb], - rev_isoin[bb], avloc[bb]); - } - passes++; + dump_sbitmap_vector (dump_file, "nearerout", "", nearerout, + last_basic_block + 1); + dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges); } +#endif + + sbitmap_vector_free (farthest); + + *insert = sbitmap_vector_alloc (num_edges, n_exprs); + *del = sbitmap_vector_alloc (last_basic_block, n_exprs); + compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, + *insert, *del); + + sbitmap_vector_free (nearerout); + sbitmap_vector_free (nearer); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); + dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, + last_basic_block); + } +#endif + return edge_list; } +