| /* Generic partial redundancy elimination with lazy code motion |
| support. |
| Copyright (C) 1998 Free Software Foundation, Inc. |
| |
| This file is part of GNU CC. |
| |
| 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. |
| |
| 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. |
| |
| 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. */ |
| |
| /* These routines are meant to be used by various optimization |
| passes which can be modeled as lazy code motion problems. |
| Including, but not limited to: |
| |
| * Traditional partial redundancy elimination. |
| |
| * Placement of caller/caller register save/restores. |
| |
| * Load/store motion. |
| |
| * Copy motion. |
| |
| * Conversion of flat register files to a stacked register |
| model. |
| |
| * Dead load/store elimination. |
| |
| These routines accept as input: |
| |
| * Basic block information (number of blocks, lists of |
| predecessors and successors). Note the granularity |
| does not need to be basic block, they could be statements |
| or functions. |
| |
| * Bitmaps of local properties (computed, transparent and |
| anticipatable expressions). |
| |
| The output of these routines is bitmap of redundant computations |
| and a bitmap of optimal placement points. */ |
| |
| |
| #include "config.h" |
| #include "system.h" |
| |
| #include "rtl.h" |
| #include "regs.h" |
| #include "hard-reg-set.h" |
| #include "flags.h" |
| #include "real.h" |
| #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. */ |
| |
| 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; |
| { |
| int bb, changed, passes; |
| sbitmap old_changed, new_changed; |
| |
| sbitmap_zero (antout[n_blocks - 1]); |
| sbitmap_vector_ones (antin, n_blocks); |
| |
| old_changed = sbitmap_alloc (n_blocks); |
| new_changed = sbitmap_alloc (n_blocks); |
| sbitmap_ones (old_changed); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| 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--) |
| { |
| 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; |
| |
| 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])) |
| { |
| changed = 1; |
| SET_BIT (new_changed, bb); |
| } |
| } |
| 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. |
| |
| 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. */ |
| |
| 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; |
| { |
| int bb, changed, passes; |
| sbitmap temp_bitmap; |
| sbitmap old_changed, new_changed; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| sbitmap_vector_zero (earlyout, n_blocks); |
| sbitmap_ones (earlyin[0]); |
| |
| old_changed = sbitmap_alloc (n_blocks); |
| new_changed = sbitmap_alloc (n_blocks); |
| sbitmap_ones (old_changed); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| changed = 0; |
| sbitmap_zero (new_changed); |
| for (bb = 0; bb < n_blocks; bb++) |
| { |
| 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 (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_copy (old_changed, new_changed); |
| passes++; |
| } |
| free (old_changed); |
| free (new_changed); |
| free (temp_bitmap); |
| } |
| |
| /* Compute expression delayedness at entrance and exit of each block. |
| |
| From Advanced Compiler Design and Implementation pp411. |
| |
| 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. */ |
| |
| 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; |
| { |
| int bb, changed, passes; |
| sbitmap *anti_and_early; |
| sbitmap temp_bitmap; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| /* 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) |
| { |
| 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++; |
| } |
| |
| /* 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); |
| } |
| |
| /* 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. */ |
| |
| 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; |
| { |
| int bb; |
| sbitmap temp_bitmap; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| for (bb = 0; bb < n_blocks; bb++) |
| { |
| /* 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); |
| } |
| else |
| sbitmap_ones (temp_bitmap); |
| sbitmap_a_and_b_or_c (latein[bb], delayin[bb], |
| antloc[bb], temp_bitmap); |
| } |
| free (temp_bitmap); |
| } |
| |
| /* Compute isolated. |
| |
| From Advanced Compiler Design and Implementation pp413. |
| |
| 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; |
| { |
| int bb, changed, passes; |
| |
| sbitmap_vector_zero (isoin, n_blocks); |
| sbitmap_zero (isoout[n_blocks - 1]); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| 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++; |
| } |
| } |
| |
| /* 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. */ |
| |
| static void |
| compute_optimal (n_blocks, latein, isoout, optimal) |
| int n_blocks; |
| sbitmap *latein; |
| sbitmap *isoout; |
| sbitmap *optimal; |
| { |
| int bb; |
| |
| for (bb = 0; bb < n_blocks; bb++) |
| sbitmap_difference (optimal[bb], latein[bb], isoout[bb]); |
| } |
| |
| /* 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. */ |
| |
| 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; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| for (bb = 0; bb < n_blocks; bb++) |
| { |
| sbitmap_a_or_b (temp_bitmap, latein[bb], isoout[bb]); |
| sbitmap_difference (redundant[bb], antloc[bb], temp_bitmap); |
| } |
| free (temp_bitmap); |
| } |
| |
| /* Compute expression availability at entrance and exit of each block. */ |
| |
| 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; |
| |
| sbitmap_zero (avin[0]); |
| sbitmap_vector_ones (avout, n_blocks); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| 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++; |
| } |
| } |
| |
| /* Compute expression latestness. |
| |
| This is effectively the same as earliestness computed on the reverse |
| flow graph. */ |
| |
| 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; |
| { |
| int bb, changed, passes; |
| sbitmap temp_bitmap; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| sbitmap_vector_zero (fartherin, n_blocks); |
| sbitmap_ones (fartherout[n_blocks - 1]); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| changed = 0; |
| for (bb = n_blocks - 1; bb >= 0; bb--) |
| { |
| 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]); |
| } |
| passes++; |
| } |
| |
| free (temp_bitmap); |
| } |
| |
| /* Compute expression earlierness at entrance and exit of each block. |
| |
| This is effectively the same as delayedness computed on the reverse |
| flow graph. */ |
| |
| 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; |
| { |
| int bb, changed, passes; |
| sbitmap *av_and_farther; |
| sbitmap temp_bitmap; |
| |
| 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) |
| { |
| changed = 0; |
| for (bb = n_blocks - 1; bb >= 0; bb--) |
| { |
| if (bb != n_blocks - 1) |
| { |
| sbitmap_intersect_of_successors (temp_bitmap, earlierin, |
| bb, s_succs); |
| changed |= sbitmap_a_or_b (earlierout[bb], |
| av_and_farther[bb], |
| 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); |
| } |
| |
| /* Compute firstness. |
| |
| This is effectively the same as latestness computed on the reverse |
| flow graph. */ |
| |
| 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; |
| { |
| int bb; |
| sbitmap temp_bitmap; |
| |
| temp_bitmap = sbitmap_alloc (n_exprs); |
| |
| for (bb = 0; bb < n_blocks; bb++) |
| { |
| /* 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); |
| } |
| else |
| { |
| sbitmap_ones (temp_bitmap); |
| } |
| sbitmap_a_and_b_or_c (firstout[bb], earlierout[bb], |
| avloc[bb], temp_bitmap); |
| } |
| free (temp_bitmap); |
| } |
| |
| /* Compute reverse isolated. |
| |
| 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; |
| { |
| int bb, changed, passes; |
| |
| sbitmap_vector_zero (rev_isoout, n_blocks); |
| sbitmap_zero (rev_isoin[0]); |
| |
| passes = 0; |
| changed = 1; |
| while (changed) |
| { |
| 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++; |
| } |
| } |