/* 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++; } }