Merge from trunk revision 8dc2499aa62f768c6395c9754b8cabc1ce25c494

1 files changed, 0 insertions, 838 deletions

diff --git a/gcc/lcm.c b/gcc/lcm.c
deleted file mode 100644
index dbb2a67..0000000
--- a/gcc/lcm.c
+++ /dev/null
@@ -1,838 +0,0 @@
-/* Generic partial redundancy elimination with lazy code motion support.
-   Copyright (C) 1998-2021 Free Software Foundation, Inc.
-
-This file is part of GCC.
-
-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.
-
-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 GCC; see the file COPYING3.  If not see
-<http://www.gnu.org/licenses/>.  */
-
-/* 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 "coretypes.h"
-#include "backend.h"
-#include "cfganal.h"
-#include "lcm.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_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
-		       sbitmap *antout)
-{
-  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_for_fn (cfun));
-
-  /* We want a maximal solution, so make an optimistic initialization of
-     ANTIN.  */
-  bitmap_vector_ones (antin, last_basic_block_for_fn (cfun));
-
-  /* Put every block on the worklist; this is necessary because of the
-     optimistic initialization of ANTIN above.  */
-  int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
-  int postorder_num = post_order_compute (postorder, false, false);
-  for (int i = 0; i < postorder_num; ++i)
-    {
-      bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
-      *qin++ = bb;
-      bb->aux = bb;
-    }
-  free (postorder);
-
-  qin = worklist;
-  qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
-  qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
-
-  /* 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_FOR_FN (cfun)->preds)
-    e->src->aux = EXIT_BLOCK_PTR_FOR_FN (cfun);
-
-  /* Iterate until the worklist is empty.  */
-  while (qlen)
-    {
-      /* Take the first entry off the worklist.  */
-      bb = *qout++;
-      qlen--;
-
-      if (qout >= qend)
-	qout = worklist;
-
-      if (bb->aux == EXIT_BLOCK_PTR_FOR_FN (cfun))
-	/* 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.  */
-	bitmap_clear (antout[bb->index]);
-      else
-	{
-	  /* Clear the aux field of this block so that it can be added to
-	     the worklist again if necessary.  */
-	  bb->aux = NULL;
-	  bitmap_intersection_of_succs (antout[bb->index], antin, bb);
-	}
-
-      if (bitmap_or_and (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_FOR_FN (cfun))
-	    {
-	      *qin++ = e->src;
-	      e->src->aux = e;
-	      qlen++;
-	      if (qin >= qend)
-		qin = worklist;
-	    }
-    }
-
-  clear_aux_for_edges ();
-  clear_aux_for_blocks ();
-  free (worklist);
-}
-
-/* Compute the earliest vector for edge based lcm.  */
-
-static void
-compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
-		  sbitmap *antout, sbitmap *avout, sbitmap *kill,
-		  sbitmap *earliest)
-{
-  int x, num_edges;
-  basic_block pred, succ;
-
-  num_edges = NUM_EDGES (edge_list);
-
-  auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
-  for (x = 0; x < num_edges; x++)
-    {
-      pred = INDEX_EDGE_PRED_BB (edge_list, x);
-      succ = INDEX_EDGE_SUCC_BB (edge_list, x);
-      if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	bitmap_copy (earliest[x], antin[succ->index]);
-      else
-	{
-	  if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
-	    bitmap_clear (earliest[x]);
-	  else
-	    {
-	      bitmap_and_compl (difference, antin[succ->index],
-				  avout[pred->index]);
-	      bitmap_not (temp_bitmap, antout[pred->index]);
-	      bitmap_and_or (earliest[x], difference,
-				    kill[pred->index], temp_bitmap);
-	    }
-	}
-    }
-}
-
-/* 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.
-
-     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.
-
-     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_laterin (struct edge_list *edge_list, sbitmap *earliest,
-		 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
-{
-  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_for_fn (cfun));
-
-  /* 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.  */
-  bitmap_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_FOR_FN (cfun)->succs)
-    bitmap_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.  */
-  auto_vec<int, 20> postorder;
-  inverted_post_order_compute (&postorder);
-  for (unsigned int i = 0; i < postorder.length (); ++i)
-    {
-      bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
-      if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
-	  || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	continue;
-      *qin++ = bb;
-      bb->aux = bb;
-    }
-
-  /* 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_for_fn (cfun) - NUM_FIXED_BLOCKS];
-  qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
-
-  /* Iterate until the worklist is empty.  */
-  while (qlen)
-    {
-      /* 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.  */
-      bitmap_ones (laterin[bb->index]);
-      FOR_EACH_EDGE (e, ei, bb->preds)
-	bitmap_and (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 (bitmap_ior_and_compl (later[(size_t) e->aux],
-				  earliest[(size_t) e->aux],
-				  laterin[bb->index],
-				  antloc[bb->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_FOR_FN (cfun) && e->dest->aux == 0)
-	  {
-	    *qin++ = e->dest;
-	    e->dest->aux = e;
-	    qlen++;
-	    if (qin >= qend)
-	      qin = worklist;
-	  }
-    }
-
-  /* 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.  */
-  bitmap_ones (laterin[last_basic_block_for_fn (cfun)]);
-  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
-    bitmap_and (laterin[last_basic_block_for_fn (cfun)],
-		laterin[last_basic_block_for_fn (cfun)],
-		later[(size_t) e->aux]);
-
-  clear_aux_for_edges ();
-  free (worklist);
-}
-
-/* Compute the insertion and deletion points for edge based LCM.  */
-
-static void
-compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
-		       sbitmap *later, sbitmap *laterin, sbitmap *insert,
-		       sbitmap *del)
-{
-  int x;
-  basic_block bb;
-
-  FOR_EACH_BB_FN (bb, cfun)
-    bitmap_and_compl (del[bb->index], antloc[bb->index],
-			laterin[bb->index]);
-
-  for (x = 0; x < NUM_EDGES (edge_list); x++)
-    {
-      basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
-
-      if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
-	bitmap_and_compl (insert[x], later[x],
-			  laterin[last_basic_block_for_fn (cfun)]);
-      else
-	bitmap_and_compl (insert[x], later[x], laterin[b->index]);
-    }
-}
-
-/* Given local properties TRANSP, ANTLOC, AVLOC, KILL return the insert and
-   delete vectors for edge based LCM  and return the AVIN, AVOUT bitmap.
-   map the insert vector to what edge an expression should be inserted on.  */
-
-struct edge_list *
-pre_edge_lcm_avs (int n_exprs, sbitmap *transp,
-	      sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
-	      sbitmap *avin, sbitmap *avout,
-	      sbitmap **insert, sbitmap **del)
-{
-  sbitmap *antin, *antout, *earliest;
-  sbitmap *later, *laterin;
-  struct edge_list *edge_list;
-  int num_edges;
-
-  edge_list = create_edge_list ();
-  num_edges = NUM_EDGES (edge_list);
-
-#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_bitmap_vector (dump_file, "transp", "", transp,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "antloc", "", antloc,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "avloc", "", avloc,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "kill", "", kill,
-			  last_basic_block_for_fn (cfun));
-    }
-#endif
-
-  /* Compute global availability.  */
-  compute_available (avloc, kill, avout, avin);
-
-  /* Compute global anticipatability.  */
-  antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  compute_antinout_edge (antloc, transp, antin, antout);
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    {
-      dump_bitmap_vector (dump_file, "antin", "", antin,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "antout", "", antout,
-			  last_basic_block_for_fn (cfun));
-    }
-#endif
-
-  /* Compute earliestness.  */
-  earliest = sbitmap_vector_alloc (num_edges, n_exprs);
-  compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges);
-#endif
-
-  sbitmap_vector_free (antout);
-  sbitmap_vector_free (antin);
-
-  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_for_fn (cfun) + 1,
-				  n_exprs);
-  compute_laterin (edge_list, earliest, antloc, later, laterin);
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    {
-      dump_bitmap_vector (dump_file, "laterin", "", laterin,
-			  last_basic_block_for_fn (cfun) + 1);
-      dump_bitmap_vector (dump_file, "later", "", later, num_edges);
-    }
-#endif
-
-  sbitmap_vector_free (earliest);
-
-  *insert = sbitmap_vector_alloc (num_edges, n_exprs);
-  *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  bitmap_vector_clear (*insert, num_edges);
-  bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
-  compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
-
-  sbitmap_vector_free (laterin);
-  sbitmap_vector_free (later);
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    {
-      dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
-      dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
-			  last_basic_block_for_fn (cfun));
-    }
-#endif
-
-  return edge_list;
-}
-
-/* Wrapper to allocate avin/avout and call pre_edge_lcm_avs.  */
-
-struct edge_list *
-pre_edge_lcm (int n_exprs, sbitmap *transp,
-	      sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
-	      sbitmap **insert, sbitmap **del)
-{
-  struct edge_list *edge_list;
-  sbitmap *avin, *avout;
-
-  avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-
-  edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
-				 avin, avout, insert, del);
-
-  sbitmap_vector_free (avout);
-  sbitmap_vector_free (avin);
-
-  return edge_list;
-}
-
-/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
-   Return the number of passes we performed to iterate to a solution.  */
-
-void
-compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
-		   sbitmap *avin)
-{
-  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_for_fn (cfun) - NUM_FIXED_BLOCKS);
-
-  /* We want a maximal solution.  */
-  bitmap_vector_ones (avout, last_basic_block_for_fn (cfun));
-
-  /* Put every block on the worklist; this is necessary because of the
-     optimistic initialization of AVOUT above.  Use inverted postorder
-     to make the dataflow problem require less iterations.  */
-  auto_vec<int, 20> postorder;
-  inverted_post_order_compute (&postorder);
-  for (unsigned int i = 0; i < postorder.length (); ++i)
-    {
-      bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
-      if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
-	  || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	continue;
-      *qin++ = bb;
-      bb->aux = bb;
-    }
-
-  qin = worklist;
-  qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
-  qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
-
-  /* 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_FOR_FN (cfun)->succs)
-    e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun);
-
-  /* Iterate until the worklist is empty.  */
-  while (qlen)
-    {
-      /* 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_FOR_FN (cfun))
-	/* 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.  */
-	bitmap_clear (avin[bb->index]);
-      else
-	{
-	  /* Clear the aux field of this block so that it can be added to
-	     the worklist again if necessary.  */
-	  bb->aux = NULL;
-	  bitmap_intersection_of_preds (avin[bb->index], avout, bb);
-	}
-
-      if (bitmap_ior_and_compl (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_FOR_FN (cfun))
-	    {
-	      *qin++ = e->dest;
-	      e->dest->aux = e;
-	      qlen++;
-
-	      if (qin >= qend)
-		qin = worklist;
-	    }
-    }
-
-  clear_aux_for_edges ();
-  clear_aux_for_blocks ();
-  free (worklist);
-}
-
-/* Compute the farthest vector for edge based lcm.  */
-
-static void
-compute_farthest (struct edge_list *edge_list, int n_exprs,
-		  sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
-		  sbitmap *kill, sbitmap *farthest)
-{
-  int x, num_edges;
-  basic_block pred, succ;
-
-  num_edges = NUM_EDGES (edge_list);
-
-  auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
-  for (x = 0; x < num_edges; x++)
-    {
-      pred = INDEX_EDGE_PRED_BB (edge_list, x);
-      succ = INDEX_EDGE_SUCC_BB (edge_list, x);
-      if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
-	bitmap_copy (farthest[x], st_avout[pred->index]);
-      else
-	{
-	  if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	    bitmap_clear (farthest[x]);
-	  else
-	    {
-	      bitmap_and_compl (difference, st_avout[pred->index],
-				  st_antin[succ->index]);
-	      bitmap_not (temp_bitmap, st_avin[succ->index]);
-	      bitmap_and_or (farthest[x], difference,
-				    kill[succ->index], temp_bitmap);
-	    }
-	}
-    }
-}
-
-/* Compute nearer and nearerout vectors for edge based lcm.
-
-   This is the mirror of compute_laterin, additional comments on the
-   implementation can be found before compute_laterin.  */
-
-static void
-compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
-		   sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
-{
-  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_for_fn (cfun) + 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.  */
-  bitmap_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_FOR_FN (cfun)->preds)
-    bitmap_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_FN (bb, cfun)
-    {
-      *tos++ = bb;
-      bb->aux = bb;
-    }
-
-  /* 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.  */
-      bitmap_ones (nearerout[bb->index]);
-      FOR_EACH_EDGE (e, ei, bb->succs)
-	bitmap_and (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 (bitmap_ior_and_compl (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_FOR_FN (cfun) && e->src->aux == 0)
-	  {
-	    *tos++ = e->src;
-	    e->src->aux = e;
-	  }
-    }
-
-  /* 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.  */
-  bitmap_ones (nearerout[last_basic_block_for_fn (cfun)]);
-  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
-    bitmap_and (nearerout[last_basic_block_for_fn (cfun)],
-		     nearerout[last_basic_block_for_fn (cfun)],
-		     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_FN (bb, cfun)
-    bitmap_and_compl (del[bb->index], st_avloc[bb->index],
-			nearerout[bb->index]);
-
-  for (x = 0; x < NUM_EDGES (edge_list); x++)
-    {
-      basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
-      if (b == ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	bitmap_and_compl (insert[x], nearer[x],
-			  nearerout[last_basic_block_for_fn (cfun)]);
-      else
-	bitmap_and_compl (insert[x], nearer[x], nearerout[b->index]);
-    }
-}
-
-/* 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.  */
-
-struct edge_list *
-pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
-		  sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
-		  sbitmap **insert, sbitmap **del)
-{
-  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_for_fn (cfun), n_exprs);
-  st_antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  bitmap_vector_clear (st_antin, last_basic_block_for_fn (cfun));
-  bitmap_vector_clear (st_antout, last_basic_block_for_fn (cfun));
-  compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
-
-  /* Compute global anticipatability.  */
-  st_avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
-  st_avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), 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_bitmap_vector (dump_file, "transp", "", transp,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_antin", "", st_antin,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_antout", "", st_antout,
-			  last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_kill", "", kill,
-			  last_basic_block_for_fn (cfun));
-    }
-#endif
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    {
-      dump_bitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block_for_fn (cfun));
-      dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block_for_fn (cfun));
-    }
-#endif
-
-  /* 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_bitmap_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_for_fn (cfun) + 1,
-				    n_exprs);
-  compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
-
-#ifdef LCM_DEBUG_INFO
-  if (dump_file)
-    {
-      dump_bitmap_vector (dump_file, "nearerout", "", nearerout,
-			   last_basic_block_for_fn (cfun) + 1);
-      dump_bitmap_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_for_fn (cfun), 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_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
-      dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
-			   last_basic_block_for_fn (cfun));
-    }
-#endif
-  return edge_list;
-}
-