Virgin import of the GCC 2.95.1 compilers

1 files changed, 799 insertions, 0 deletions

diff --git a/contrib/gcc/lcm.c b/contrib/gcc/lcm.c
new file mode 100644
index 0000000..01367e3
--- /dev/null
+++ b/contrib/gcc/lcm.c
@@ -0,0 +1,799 @@
+/* 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++;
+    }
+}