* Makefile.in (OBJS-common): Add postreload-gcse.c.

	Add new postreload-gcse.o.
	* cse.c (SAFE_HASH): Define as wrapper around safe_hash.
	(lookup_as_function, insert, rehash_using_reg, use_related_value,
	equiv_constant): Use SAFE_HASH instead of safe_hash.
	(exp_equiv_p): Export.  Add for_gcse argument when comparing
	for GCSE.
	(lookup, lookup_for_remove, merge_equiv_classes, find_best_addr,
	find_comparison_args, fold_rtx, cse_insn): Update callers.
	(hash_rtx): New function derived from old canon_hash and bits
	from gcse.c hash_expr_1.
	(canon_hash_string): Rename to hash_rtx_string.
	(canon_hash, safe_hash): Make static inline.  Call hash_rtx.
	* cselib.c (hash_rtx): Rename to cselib_hash_rtx.
	(cselib_lookup): Update this caller.
	* gcse.c (modify_mem_list_set, canon_modify_mem_list_set):
	Make static.
	(hash_expr): Call hash_rtx.
	(ldst_entry): Likewise.
	(expr_equiv_p): Call exp_equiv_p.
	(struct unoccr, hash_expr_1, hash_string_1, lookup_expr,
	reg_used_on_edge, reg_set_between_after_reload_p,
	reg_used_between_after_reload_p, get_avail_load_store_reg,
	is_jump_table_basic_block, bb_has_well_behaved_predecessors,
	get_bb_avail_insn, hash_scan_set_after_reload,
	compute_hash_table_after_reload,
	eliminate_partially_redundant_loads, gcse_after_reload,
	get_bb_avail_insn, gcse_after_reload_main): Remove.
	* postreload-gcse.c: New file, reincarnating most of the above.
	* rtl.h (exp_equiv_p, hash_rtx): New prototypes.
	(gcse_after_reload_main): Update prototype.
	* timevar.def (TV_GCSE_AFTER_RELOAD): New timevar.
	* passes.c (rest_of_handle_gcse2): Use it.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@86206 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1379 insertions, 0 deletions

diff --git a/gcc/postreload-gcse.c b/gcc/postreload-gcse.c
new file mode 100644
index 00000000000..a9d03440573
--- /dev/null
+++ b/gcc/postreload-gcse.c
@@ -0,0 +1,1379 @@
+/* Post reload partially redundant load elimination
+   Copyright (C) 2004
+   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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "toplev.h"
+
+#include "rtl.h"
+#include "tree.h"
+#include "tm_p.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"
+#include "output.h"
+#include "function.h"
+#include "expr.h"
+#include "except.h"
+#include "intl.h"
+#include "obstack.h"
+#include "hashtab.h"
+#include "params.h"
+
+/* The following code implements gcse after reload, the purpose of this
+   pass is to cleanup redundant loads generated by reload and other
+   optimizations that come after gcse. It searches for simple inter-block
+   redundancies and tries to eliminate them by adding moves and loads
+   in cold places.
+
+   Perform partially redundant load elimination, try to eliminate redundant
+   loads created by the reload pass.  We try to look for full or partial
+   redundant loads fed by one or more loads/stores in predecessor BBs,
+   and try adding loads to make them fully redundant.  We also check if
+   it's worth adding loads to be able to delete the redundant load.
+
+   Algorithm:
+   1. Build available expressions hash table:
+       For each load/store instruction, if the loaded/stored memory didn't
+       change until the end of the basic block add this memory expression to
+       the hash table.
+   2. Perform Redundancy elimination:
+      For each load instruction do the following:
+	 perform partial redundancy elimination, check if it's worth adding
+	 loads to make the load fully redundant.  If so add loads and
+	 register copies and delete the load.
+   3. Delete instructions made redundant in step 2.
+
+   Future enhancement:
+     If the loaded register is used/defined between load and some store,
+     look for some other free register between load and all its stores,
+     and replace the load with a copy from this register to the loaded
+     register.
+*/
+
+
+/* Keep statistics of this pass.  */
+static struct
+{
+  int moves_inserted;
+  int copies_inserted;
+  int insns_deleted;
+} stats;
+
+/* We need to keep a hash table of expressions.  The table entries are of
+   type 'struct expr', and for each expression there is a single linked
+   list of occurences.  */
+
+/* The table itself.  */
+static htab_t expr_table;
+
+/* Expression elements in the hash table.  */
+struct expr
+{
+  /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
+  rtx expr;
+
+  /* The same hash for this entry.  */
+  hashval_t hash;
+
+  /* List of available occurrence in basic blocks in the function.  */
+  struct occr *avail_occr;
+};
+
+static struct obstack expr_obstack;
+
+/* Occurrence of an expression.
+   There is at most one occurence per basic block.  If a pattern appears
+   more than once, the last appearance is used.  */
+
+struct occr
+{
+  /* Next occurrence of this expression.  */
+  struct occr *next;
+  /* The insn that computes the expression.  */
+  rtx insn;
+  /* Nonzero if this [anticipatable] occurrence has been deleted.  */
+  char deleted_p;
+};
+
+static struct obstack occr_obstack;
+
+/* The following structure holds the information about the occurrences of
+   the redundant instructions.  */
+struct unoccr
+{
+  struct unoccr *next;
+  edge pred;
+  rtx insn;
+};
+
+static struct obstack unoccr_obstack;
+
+/* Array where each element is the CUID if the insn that last set the hard
+   register with the number of the element, since the start of the current
+   basic block.  */
+static int *reg_avail_info;
+
+/* A list of insns that may modify memory within the current basic block.  */
+struct modifies_mem
+{
+  rtx insn;
+  struct modifies_mem *next;
+};
+static struct modifies_mem *modifies_mem_list;
+
+/* The modifies_mem structs also go on an obstack, only this obstack is
+   freed each time after completing the analysis or transformations on
+   a basic block.  So we allocate a dummy modifies_mem_obstack_bottom
+   object on the obstack to keep track of the bottom of the obstack.  */
+static struct obstack modifies_mem_obstack;
+static struct modifies_mem  *modifies_mem_obstack_bottom;
+
+/* Mapping of insn UIDs to CUIDs.
+   CUIDs are like UIDs except they increase monotonically in each basic
+   block, have no gaps, and only apply to real insns.  */
+static int *uid_cuid;
+#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+
+
+/* Helpers for memory allocation/freeing.  */
+static void alloc_mem (void);
+static void free_mem (void);
+
+/* Support for hash table construction and transformations.  */
+static bool oprs_unchanged_p (rtx, rtx, bool);
+static void record_last_reg_set_info (rtx, int);
+static void record_last_mem_set_info (rtx);
+static void record_last_set_info (rtx, rtx, void *);
+static void mark_call (rtx);
+static void mark_set (rtx, rtx);
+static void mark_clobber (rtx, rtx);
+static void mark_oprs_set (rtx);
+
+static void find_mem_conflicts (rtx, rtx, void *);
+static int load_killed_in_block_p (int, rtx, bool);
+static void reset_opr_set_tables (void);
+
+/* Hash table support.  */
+static hashval_t hash_expr (rtx, int *);
+static hashval_t hash_expr_for_htab (const void *);
+static int expr_equiv_p (const void *, const void *);
+static void insert_expr_in_table (rtx, rtx);
+static struct expr *lookup_expr_in_table (rtx);
+static int dump_hash_table_entry (void **, void *);
+static void dump_hash_table (FILE *);
+
+/* Helpers for eliminate_partially_redundant_load.  */
+static bool reg_killed_on_edge (rtx, edge);
+static bool reg_used_on_edge (rtx, edge);
+
+static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
+static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
+static rtx get_avail_load_store_reg (rtx);
+
+static bool bb_has_well_behaved_predecessors (basic_block);
+static struct occr* get_bb_avail_insn (basic_block, struct occr *);
+static void hash_scan_set (rtx);
+static void compute_hash_table (void);
+
+/* The work horses of this pass.  */
+static void eliminate_partially_redundant_load (basic_block,
+						rtx,
+						struct expr *);
+static void eliminate_partially_redundant_loads (void);
+
+
+/* Allocate memory for the CUID mapping array and register/memory
+   tracking tables.  */
+
+static void
+alloc_mem (void)
+{
+  int i;
+  basic_block bb;
+  rtx insn;
+
+  /* Find the largest UID and create a mapping from UIDs to CUIDs.  */
+  uid_cuid = xcalloc (get_max_uid () + 1, sizeof (int));
+  i = 0;
+  FOR_EACH_BB (bb)
+    FOR_BB_INSNS (bb, insn)
+      {
+        if (INSN_P (insn))
+	  uid_cuid[INSN_UID (insn)] = i++;
+	else
+	  uid_cuid[INSN_UID (insn)] = i;
+      }
+
+  /* Allocate the available expressions hash table.  We don't want to
+     make the hash table too small, but unnecessarily making it too large
+     also doesn't help.  The i/4 is a gcse.c relic, and seems like a
+     reasonable choice.  */
+  expr_table = htab_create (MAX (i / 4, 13),
+			    hash_expr_for_htab, expr_equiv_p, NULL);
+
+  /* We allocate everything on obstacks because we often can roll back
+     the whole obstack to some point.  Freeing obstacks is very fast.  */
+  gcc_obstack_init (&expr_obstack);
+  gcc_obstack_init (&occr_obstack);
+  gcc_obstack_init (&unoccr_obstack);
+  gcc_obstack_init (&modifies_mem_obstack);
+
+  /* Working array used to track the last set for each register
+     in the current block.  */
+  reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int));
+
+  /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
+     can roll it back in reset_opr_set_tables.  */
+  modifies_mem_obstack_bottom =
+    (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
+					   sizeof (struct modifies_mem));
+}
+
+/* Free memory allocated by alloc_mem.  */
+
+static void
+free_mem (void)
+{
+  free (uid_cuid);
+
+  htab_delete (expr_table);
+
+  obstack_free (&expr_obstack, NULL);
+  obstack_free (&occr_obstack, NULL);
+  obstack_free (&unoccr_obstack, NULL);
+  obstack_free (&modifies_mem_obstack, NULL);
+
+  free (reg_avail_info);
+}
+
+
+/* Hash expression X.
+   DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
+   or if the expression contains something we don't want to insert in the
+   table.  */
+
+static hashval_t
+hash_expr (rtx x, int *do_not_record_p)
+{
+  *do_not_record_p = 0;
+  return hash_rtx (x, GET_MODE (x), do_not_record_p,
+		   NULL,  /*have_reg_qty=*/false);
+}
+
+/* Callback for hashtab.
+   Return the hash value for expression EXP.  We don't actually hash
+   here, we just return the cached hash value.  */
+
+static hashval_t
+hash_expr_for_htab (const void *expp)
+{
+  struct expr *exp = (struct expr *) expp;
+  return exp->hash;
+}
+
+/* Callbach for hashtab.
+   Return nonzero if exp1 is equivalent to exp2.  */
+
+static int
+expr_equiv_p (const void *exp1p, const void *exp2p)
+{
+  struct expr *exp1 = (struct expr *) exp1p;
+  struct expr *exp2 = (struct expr *) exp2p;
+  int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
+  if (equiv_p
+      && exp1->hash != exp2->hash)
+    abort ();
+  return equiv_p;
+}
+
+
+/* Insert expression X in INSN in the hash TABLE.
+   If it is already present, record it as the last occurrence in INSN's
+   basic block.  */
+
+static void
+insert_expr_in_table (rtx x, rtx insn)
+{
+  int do_not_record_p;
+  hashval_t hash;
+  struct expr *cur_expr, **slot;
+  struct occr *avail_occr, *last_occr = NULL;
+
+  hash = hash_expr (x, &do_not_record_p);
+
+  /* Do not insert expression in the table if it contains volatile operands,
+     or if hash_expr determines the expression is something we don't want
+     to or can't handle.  */
+  if (do_not_record_p)
+    return;
+
+  /* We anticipate that redundant expressions are rare, so for convenience
+     allocate a new hash table element here already and set its fields.
+     If we don't do this, we need a hack with a static struct expr.  Anyway,
+     obstack_free is really fast and one more obstack_alloc doesn't hurt if
+     we're going to see more expressions later on.  */
+  cur_expr = (struct expr *) obstack_alloc (&expr_obstack,
+					    sizeof (struct expr));
+  cur_expr->expr = x;
+  cur_expr->hash = hash;
+  cur_expr->avail_occr = NULL;
+
+  slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr,
+						    hash, INSERT);
+  
+  if (! (*slot))
+    /* The expression isn't found, so insert it.  */
+    *slot = cur_expr;
+  else
+    {
+      /* The expression is already in the table, so roll back the
+	 obstack and use the existing table entry.  */
+      obstack_free (&expr_obstack, cur_expr);
+      cur_expr = *slot;
+    }
+
+  /* Search for another occurrence in the same basic block.  */
+  avail_occr = cur_expr->avail_occr;
+  while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
+    {
+      /* If an occurrence isn't found, save a pointer to the end of
+	 the list.  */
+      last_occr = avail_occr;
+      avail_occr = avail_occr->next;
+    }
+
+  if (avail_occr)
+    /* Found another instance of the expression in the same basic block.
+       Prefer this occurrence to the currently recorded one.  We want
+       the last one in the block and the block is scanned from start
+       to end.  */
+    avail_occr->insn = insn;
+  else
+    {
+      /* First occurrence of this expression in this basic block.  */
+      avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
+						  sizeof (struct occr));
+
+      /* First occurrence of this expression in any block?  */
+      if (cur_expr->avail_occr == NULL)
+        cur_expr->avail_occr = avail_occr;
+      else
+        last_occr->next = avail_occr;
+
+      avail_occr->insn = insn;
+      avail_occr->next = NULL;
+      avail_occr->deleted_p = 0;
+    }
+}
+
+
+/* Lookup pattern PAT in the expression hash table.
+   The result is a pointer to the table entry, or NULL if not found.  */
+
+static struct expr *
+lookup_expr_in_table (rtx pat)
+{
+  int do_not_record_p;
+  struct expr **slot, *tmp_expr;
+  hashval_t hash = hash_expr (pat, &do_not_record_p);
+
+  if (do_not_record_p)
+    return NULL;
+
+  tmp_expr = (struct expr *) obstack_alloc (&expr_obstack,
+					    sizeof (struct expr));
+  tmp_expr->expr = pat;
+  tmp_expr->hash = hash;
+  tmp_expr->avail_occr = NULL;
+
+  slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr,
+                                                    hash, INSERT);
+  obstack_free (&expr_obstack, tmp_expr);
+
+  if (!slot)
+    return NULL;
+  else
+    return (*slot);
+}
+
+
+/* Dump all expressions and occurences that are currently in the
+   expression hash table to FILE.  */
+
+/* This helper is called via htab_traverse.  */
+static int
+dump_hash_table_entry (void **slot, void *filep)
+{
+  struct expr *expr = (struct expr *) *slot;
+  FILE *file = (FILE *) filep;
+  struct occr *occr;
+
+  fprintf (file, "expr: ");
+  print_rtl (file, expr->expr);
+  fprintf (file,"\nhashcode: %u\n", expr->hash);
+  fprintf (file,"list of occurences:\n");
+  occr = expr->avail_occr;
+  while (occr)
+    {
+      rtx insn = occr->insn;
+      print_rtl_single (file, insn);
+      fprintf (file, "\n");
+      occr = occr->next;
+    }
+  fprintf (file, "\n");
+  return 1;
+}
+
+static void
+dump_hash_table (FILE *file)
+{
+  fprintf (file, "\n\nexpression hash table\n");
+  fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+           (long) htab_size (expr_table),
+           (long) htab_elements (expr_table),
+           htab_collisions (expr_table));
+  if (htab_elements (expr_table) > 0)
+    {
+      fprintf (file, "\n\ntable entries:\n");
+      htab_traverse (expr_table, dump_hash_table_entry, file);
+    }
+  fprintf (file, "\n");
+}
+
+
+/* Return nonzero if the operands of expression X are unchanged from the
+   start of INSN's basic block up to but not including INSN if AFTER_INSN
+   is false, or from INSN to the end of INSN's basic block if AFTER_INSN
+   is true.  */
+
+static bool
+oprs_unchanged_p (rtx x, rtx insn, bool after_insn)
+{
+  int i, j;
+  enum rtx_code code;
+  const char *fmt;
+
+  if (x == 0)
+    return 1;
+
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case REG:
+#ifdef ENABLE_CHECKING
+      /* We are called after register allocation.  */
+      if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+	abort ();
+#endif
+      if (after_insn)
+	/* If the last CUID setting the insn is less than the CUID of
+	   INSN, then reg X is not changed in or after INSN.  */
+	return reg_avail_info[REGNO (x)] < INSN_CUID (insn);
+      else
+	/* Reg X is not set before INSN in the current basic block if
+	   we have not yet recorded the CUID of an insn that touches
+	   the reg.  */
+	return reg_avail_info[REGNO (x)] == 0;
+
+    case MEM:
+      if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
+	return 0;
+      else
+	return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
+
+    case PC:
+    case CC0: /*FIXME*/
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST_VECTOR:
+    case SYMBOL_REF:
+    case LABEL_REF:
+    case ADDR_VEC:
+    case ADDR_DIFF_VEC:
+      return 1;
+
+    case PRE_DEC:
+    case PRE_INC:
+    case POST_DEC:
+    case POST_INC:
+    case PRE_MODIFY:
+    case POST_MODIFY:
+      if (after_insn)
+	return 0;
+      break;
+
+    default:
+      break;
+    }
+
+  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn))
+	    return 0;
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn))
+	    return 0;
+    }
+
+  return 1;
+}
+
+
+/* Used for communication between find_mem_conflicts and
+   load_killed_in_block_p.  Nonzero if find_mem_conflicts finds a
+   conflict between two memory references.
+   This is a bit of a hack to work around the limitations of note_stores.  */
+static int mems_conflict_p;
+
+/* DEST is the output of an instruction.  If it is a memory reference, and
+   possibly conflicts with the load found in DATA, then set mems_conflict_p
+   to a nonzero value.  */
+
+static void
+find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED,
+		    void *data)
+{
+  rtx mem_op = (rtx) data;
+
+  while (GET_CODE (dest) == SUBREG
+	 || GET_CODE (dest) == ZERO_EXTRACT
+	 || GET_CODE (dest) == SIGN_EXTRACT
+	 || GET_CODE (dest) == STRICT_LOW_PART)
+    dest = XEXP (dest, 0);
+
+  /* If DEST is not a MEM, then it will not conflict with the load.  Note
+     that function calls are assumed to clobber memory, but are handled
+     elsewhere.  */
+  if (! MEM_P (dest))
+    return;
+
+  if (true_dependence (dest, GET_MODE (dest), mem_op,
+		       rtx_addr_varies_p))
+    mems_conflict_p = 1;
+}
+
+
+/* Return nonzero if the expression in X (a memory reference) is killed
+   in block BB before if (AFTER_INSN is false) or after (if AFTER_INSN
+   is true) the insn with the CUID in UID_LIMIT.  */
+
+static int
+load_killed_in_block_p (int uid_limit, rtx x, bool after_insn)
+{
+  struct modifies_mem *list_entry = modifies_mem_list;
+
+  while (list_entry)
+    {
+      rtx setter = list_entry->insn;
+
+      /* Ignore entries in the list that do not apply.  */
+      if ((after_insn
+	   && INSN_CUID (setter) < uid_limit)
+	  || (! after_insn
+	      && INSN_CUID (setter) > uid_limit))
+	{
+	  list_entry = list_entry->next;
+	  continue;
+	}
+
+      /* If SETTER is a call everything is clobbered.  Note that calls
+	 to pure functions are never put on the list, so we need not
+	 worry about them.  */
+      if (CALL_P (setter))
+	return 1;
+
+      /* SETTER must be an insn of some kind that sets memory.  Call
+	 note_stores to examine each hunk of memory that is modified.
+	 It will set mems_conflict_p to nonzero if there may be a
+	 conflict between X and SETTER.  */
+      mems_conflict_p = 0;
+      note_stores (PATTERN (setter), find_mem_conflicts, x);
+      if (mems_conflict_p)
+	return 1;
+
+      list_entry = list_entry->next;
+    }
+  return 0;
+}
+
+
+/* Record register first/last/block set information for REGNO in INSN.  */
+
+static void
+record_last_reg_set_info (rtx insn, int regno)
+{
+  reg_avail_info[regno] = INSN_CUID (insn);
+}
+
+
+/* Record memory modification information for INSN.  We do not actually care
+   about the memory location(s) that are set, or even how they are set (consider
+   a CALL_INSN).  We merely need to record which insns modify memory.  */
+
+static void
+record_last_mem_set_info (rtx insn)
+{
+  struct modifies_mem *list_entry;
+
+  list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
+						      sizeof (struct modifies_mem));
+  list_entry->insn = insn;
+  list_entry->next = modifies_mem_list;
+  modifies_mem_list = list_entry;
+}
+
+/* Called from compute_hash_table via note_stores to handle one
+   SET or CLOBBER in an insn.  DATA is really the instruction in which
+   the SET is taking place.  */
+
+static void
+record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
+{
+  rtx last_set_insn = (rtx) data;
+
+  if (GET_CODE (dest) == SUBREG)
+    dest = SUBREG_REG (dest);
+
+  if (REG_P (dest))
+    record_last_reg_set_info (last_set_insn, REGNO (dest));
+  else if (MEM_P (dest)
+	   /* Ignore pushes, they clobber nothing.  */
+	   && ! push_operand (dest, GET_MODE (dest)))
+    record_last_mem_set_info (last_set_insn);
+}
+
+
+/* Reset tables used to keep track of what's still available since the
+   start of the block.  */
+
+static void
+reset_opr_set_tables (void)
+{
+  memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int));
+  obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom);
+  modifies_mem_list = NULL;
+}
+
+/* Mark things set by a CALL.  */
+
+static void
+mark_call (rtx insn)
+{
+  if (! CONST_OR_PURE_CALL_P (insn))
+    record_last_mem_set_info (insn);
+}
+
+/* Mark things set by a SET.  */
+
+static void
+mark_set (rtx pat, rtx insn)
+{
+  rtx dest = SET_DEST (pat);
+
+  while (GET_CODE (dest) == SUBREG
+	 || GET_CODE (dest) == ZERO_EXTRACT
+	 || GET_CODE (dest) == SIGN_EXTRACT
+	 || GET_CODE (dest) == STRICT_LOW_PART)
+    dest = XEXP (dest, 0);
+
+  if (REG_P (dest))
+    record_last_reg_set_info (insn, REGNO (dest));
+  else if (MEM_P (dest))
+    record_last_mem_set_info (insn);
+
+  if (GET_CODE (SET_SRC (pat)) == CALL)
+    mark_call (insn);
+}
+
+/* Record things set by a CLOBBER.  */
+
+static void
+mark_clobber (rtx pat, rtx insn)
+{
+  rtx clob = XEXP (pat, 0);
+
+  while (GET_CODE (clob) == SUBREG
+	 || GET_CODE (clob) == STRICT_LOW_PART)
+    clob = XEXP (clob, 0);
+
+  if (REG_P (clob))
+    record_last_reg_set_info (insn, REGNO (clob));
+  else
+    record_last_mem_set_info (insn);
+}
+
+/* Record things set by INSN.
+   This data is used by oprs_unchanged_p.  */
+
+static void
+mark_oprs_set (rtx insn)
+{
+  rtx pat = PATTERN (insn);
+  int i;
+
+  if (GET_CODE (pat) == SET)
+    mark_set (pat, insn);
+
+  else if (GET_CODE (pat) == PARALLEL)
+    for (i = 0; i < XVECLEN (pat, 0); i++)
+      {
+	rtx x = XVECEXP (pat, 0, i);
+
+	if (GET_CODE (x) == SET)
+	  mark_set (x, insn);
+	else if (GET_CODE (x) == CLOBBER)
+	  mark_clobber (x, insn);
+	else if (GET_CODE (x) == CALL)
+	  mark_call (insn);
+      }
+
+  else if (GET_CODE (pat) == CLOBBER)
+    mark_clobber (pat, insn);
+
+  else if (GET_CODE (pat) == CALL)
+    mark_call (insn);
+}
+
+
+/* Scan the pattern of INSN and add an entry to the hash TABLE.
+   After reload we are interested in loads/stores only.  */
+
+static void
+hash_scan_set (rtx insn)
+{
+  rtx pat = PATTERN (insn);
+  rtx src = SET_SRC (pat);
+  rtx dest = SET_DEST (pat);
+
+  /* We are only interested in loads and stores.  */
+  if (! MEM_P (src) && ! MEM_P (dest))
+    return;
+
+  /* Don't mess with jumps and nops.  */
+  if (JUMP_P (insn) || set_noop_p (pat))
+    return;
+
+#ifdef ENABLE_CHEKCING
+  /* We shouldn't have any EH_REGION notes post reload.  */
+  if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
+    abort ();
+#endif
+
+  if (REG_P (dest))
+    {
+      if (/* Don't GCSE something if we can't do a reg/reg copy.  */
+	  can_copy_p (GET_MODE (dest))
+	  /* Is SET_SRC something we want to gcse?  */
+	  && general_operand (src, GET_MODE (src))
+	  /* An expression is not available if its operands are
+	     subsequently modified, including this insn.  */
+	  && oprs_unchanged_p (src, insn, true))
+	{
+	  insert_expr_in_table (src, insn);
+	}
+    }
+  else if (REG_P (src))
+    {
+      /* Only record sets of pseudo-regs in the hash table.  */
+      if (/* Don't GCSE something if we can't do a reg/reg copy.  */
+	  can_copy_p (GET_MODE (src))
+	  /* Is SET_DEST something we want to gcse?  */
+	  && general_operand (dest, GET_MODE (dest))
+	  && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
+	  /* Check if the memory expression is killed after insn.  */
+	  && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
+	  && oprs_unchanged_p (XEXP (dest, 0), insn, true))
+	{
+	  insert_expr_in_table (dest, insn);
+	}
+    }
+}
+
+/* Create hash table of memory expressions available at end of basic
+   blocks.  */
+
+static void
+compute_hash_table (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      rtx insn;
+      unsigned int regno;
+
+      reset_opr_set_tables ();
+
+      /* First pass over the instructions records information used to
+	 determine when registers and memory are first and last set.  */
+      FOR_BB_INSNS (bb, insn)
+	{
+	  if (! INSN_P (insn))
+	    continue;
+
+	  if (CALL_P (insn))
+	    {
+	      bool clobbers_all = false;
+
+#ifdef NON_SAVING_SETJMP
+	      if (NON_SAVING_SETJMP
+		  && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+		clobbers_all = true;
+#endif
+
+	      for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+		if (clobbers_all
+		    || TEST_HARD_REG_BIT (regs_invalidated_by_call,
+					  regno))
+		  record_last_reg_set_info (insn, regno);
+
+	      if (! CONST_OR_PURE_CALL_P (insn))
+		record_last_mem_set_info (insn);
+	    }
+
+	  note_stores (PATTERN (insn), record_last_set_info, insn);
+
+	  if (GET_CODE (PATTERN (insn)) == SET)
+	    {
+	      rtx src, dest;
+
+	      src = SET_SRC (PATTERN (insn));
+	      dest = SET_DEST (PATTERN (insn));
+	      if (MEM_P (src) && auto_inc_p (XEXP (src, 0)))
+		{
+		  regno = REGNO (XEXP (XEXP (src, 0), 0));
+		  record_last_reg_set_info (insn, regno);
+		}
+	      if (MEM_P (dest) && auto_inc_p (XEXP (dest, 0)))
+		{
+		  regno = REGNO (XEXP (XEXP (dest, 0), 0));
+		  record_last_reg_set_info (insn, regno);
+		}
+	     }
+	  }
+
+      /* The next pass builds the hash table.  */
+      FOR_BB_INSNS (bb, insn)
+	if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
+	  hash_scan_set (insn);
+    }
+}
+
+
+/* Check if register REG is killed in any insn waiting to be inserted on
+   edge E.  This function is required to check that our data flow analysis
+   is still valid prior to commit_edge_insertions.  */
+
+static bool
+reg_killed_on_edge (rtx reg, edge e)
+{
+  rtx insn;
+
+  for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
+    if (INSN_P (insn) && reg_set_p (reg, insn))
+      return true;
+
+  return false;
+}
+
+/* Similar to above - check if register REG is used in any insn waiting
+   to be inserted on edge E.
+   Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
+   with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p.  */
+
+static bool
+reg_used_on_edge (rtx reg, edge e)
+{
+  rtx insn;
+
+  for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
+    if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
+      return true;
+
+  return false;
+}
+
+
+/* Return the insn that sets register REG or clobbers it in between
+   FROM_INSN and TO_INSN (exclusive of those two).
+   Just like reg_set_between but for hard registers and not pseudos.  */
+
+static rtx
+reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
+{
+  rtx insn;
+  int regno;
+
+#ifdef ENABLE_CHECKING
+  /* We are called after register allocation.  */
+  if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
+    abort ();
+#endif
+
+  if (from_insn == to_insn)
+    return NULL_RTX;
+
+  regno = REGNO (reg);
+  for (insn = NEXT_INSN (from_insn);
+       insn != to_insn;
+       insn = NEXT_INSN (insn))
+    {
+      if (INSN_P (insn))
+	{
+	  if (FIND_REG_INC_NOTE (insn, reg)
+	      || (CALL_P (insn)
+		  && call_used_regs[regno])
+	      || find_reg_fusage (insn, CLOBBER, reg))
+	    return insn;
+	}
+      if (set_of (reg, insn) != NULL_RTX)
+	return insn;
+    }
+
+  return NULL_RTX;
+}
+
+/* Return the insn that uses register REG in between FROM_INSN and TO_INSN
+   (exclusive of those two). Similar to reg_used_between but for hard
+   registers and not pseudos.  */
+
+static rtx
+reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
+{
+  rtx insn;
+  int regno;
+
+#ifdef ENABLE_CHECKING
+  /* We are called after register allocation.  */
+  if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
+    abort ();
+#endif
+
+  if (from_insn == to_insn)
+    return NULL_RTX;
+
+  regno = REGNO (reg);
+  for (insn = NEXT_INSN (from_insn);
+       insn != to_insn;
+       insn = NEXT_INSN (insn))
+    if (INSN_P (insn)
+	&& (reg_overlap_mentioned_p (reg, PATTERN (insn))
+	    || (CALL_P (insn)
+		&& call_used_regs[regno])
+	    || find_reg_fusage (insn, USE, reg)
+	    || find_reg_fusage (insn, CLOBBER, reg)))
+      return insn;
+
+  return NULL_RTX;
+}
+
+/* Return true if REG is used, set, or killed between the beginning of
+   basic block BB and UP_TO_INSN.  Caches the result in reg_avail_info.  */
+
+static bool
+reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
+{
+  rtx insn, start = PREV_INSN (BB_HEAD (bb));
+
+  if (reg_avail_info[REGNO (reg)] != 0)
+    return true;
+
+  insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
+  if (! insn)
+    insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
+
+  if (insn)
+    reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
+
+  return insn != NULL_RTX;
+}
+
+/* Return the loaded/stored register of a load/store instruction.  */
+
+static rtx
+get_avail_load_store_reg (rtx insn)
+{
+  if (REG_P (SET_DEST (PATTERN (insn))))  /* A load.  */
+    return SET_DEST(PATTERN(insn));
+  if (REG_P (SET_SRC (PATTERN (insn))))  /* A store.  */
+    return SET_SRC (PATTERN (insn));
+  abort ();
+}
+
+/* Return nonzero if the predecessors of BB are "well behaved".  */
+
+static bool
+bb_has_well_behaved_predecessors (basic_block bb)
+{
+  edge pred;
+
+  if (! bb->pred)
+    return false;
+
+  for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
+    {
+      if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
+	return false;
+
+      if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
+	return false;
+    }
+  return true;
+}
+
+
+/* Search for the occurrences of expression in BB.  */
+
+static struct occr*
+get_bb_avail_insn (basic_block bb, struct occr *occr)
+{
+  for (; occr != NULL; occr = occr->next)
+    if (BLOCK_FOR_INSN (occr->insn) == bb)
+      return occr;
+  return NULL;
+}
+
+
+/* This handles the case where several stores feed a partially redundant
+   load. It checks if the redundancy elimination is possible and if it's
+   worth it.  */
+
+static void
+eliminate_partially_redundant_load (basic_block bb, rtx insn,
+				    struct expr *expr)
+{
+  edge pred;
+  rtx avail_insn = NULL_RTX;
+  rtx avail_reg;
+  rtx dest, pat;
+  struct occr *a_occr;
+  struct unoccr *occr, *avail_occrs = NULL;
+  struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
+  int npred_ok = 0;
+  gcov_type ok_count = 0; /* Redundant load execution count.  */
+  gcov_type critical_count = 0; /* Execution count of critical edges.  */
+
+  /* The execution count of the loads to be added to make the
+     load fully redundant.  */
+  gcov_type not_ok_count = 0;
+  basic_block pred_bb;
+
+  pat = PATTERN (insn);
+  dest = SET_DEST (pat);
+
+  /* Check that the loaded register is not used, set, or killed from the
+     beginning of the block.  */
+  if (reg_set_or_used_since_bb_start (dest, bb, insn))
+    return;
+
+  /* Check potential for replacing load with copy for predecessors.  */
+  for (pred = bb->pred; pred; pred = pred->pred_next)
+    {
+      rtx next_pred_bb_end;
+
+      avail_insn = NULL_RTX;
+      pred_bb = pred->src;
+      next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
+      for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
+	   a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
+	{
+	  /* Check if the loaded register is not used.  */
+	  avail_insn = a_occr->insn;
+	  if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
+	    abort ();
+	  /* Make sure we can generate a move from register avail_reg to
+	     dest.  */
+	  extract_insn (gen_move_insn (copy_rtx (dest),
+				       copy_rtx (avail_reg)));
+	  if (! constrain_operands (1)
+	      || reg_killed_on_edge (avail_reg, pred)
+	      || reg_used_on_edge (dest, pred))
+	    {
+	      avail_insn = NULL;
+	      continue;
+	    }
+	  if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
+						next_pred_bb_end))
+	    /* AVAIL_INSN remains non-null.  */
+	    break;
+	  else
+	    avail_insn = NULL;
+	}
+
+      if (EDGE_CRITICAL_P (pred))
+	critical_count += pred->count;
+
+      if (avail_insn != NULL_RTX)
+	{
+	  npred_ok++;
+	  ok_count += pred->count;
+	  occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
+						  sizeof (struct occr));
+	  occr->insn = avail_insn;
+	  occr->pred = pred;
+	  occr->next = avail_occrs;
+	  avail_occrs = occr;
+	  if (! rollback_unoccr)
+	    rollback_unoccr = occr;
+	}
+      else
+	{
+	  not_ok_count += pred->count;
+	  unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
+						    sizeof (struct unoccr));
+	  unoccr->insn = NULL_RTX;
+	  unoccr->pred = pred;
+	  unoccr->next = unavail_occrs;
+	  unavail_occrs = unoccr;
+	  if (! rollback_unoccr)
+	    rollback_unoccr = unoccr;
+	}
+    }
+
+  if (/* No load can be replaced by copy.  */
+      npred_ok == 0
+      /* Prevent exploding the code.  */ 
+      || (optimize_size && npred_ok > 1))
+    goto cleanup;
+
+  /* Check if it's worth applying the partial redundancy elimination.  */
+  if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
+    goto cleanup;
+  if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
+    goto cleanup;
+
+  /* Generate moves to the loaded register from where
+     the memory is available.  */
+  for (occr = avail_occrs; occr; occr = occr->next)
+    {
+      avail_insn = occr->insn;
+      pred = occr->pred;
+      /* Set avail_reg to be the register having the value of the
+	 memory.  */
+      avail_reg = get_avail_load_store_reg (avail_insn);
+      if (! avail_reg)
+	abort ();
+
+      insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
+					  copy_rtx (avail_reg)),
+			   pred);
+      stats.moves_inserted++;
+
+      if (dump_file)
+	fprintf (dump_file,
+		 "generating move from %d to %d on edge from %d to %d\n",
+		 REGNO (avail_reg),
+		 REGNO (dest),
+		 pred->src->index,
+		 pred->dest->index);
+    }
+
+  /* Regenerate loads where the memory is unavailable.  */
+  for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
+    {
+      pred = unoccr->pred;
+      insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
+      stats.copies_inserted++;
+
+      if (dump_file)
+	{
+	  fprintf (dump_file,
+		   "generating on edge from %d to %d a copy of load: ",
+		   pred->src->index,
+		   pred->dest->index);
+	  print_rtl (dump_file, PATTERN (insn));
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  /* Delete the insn if it is not available in this block and mark it
+     for deletion if it is available. If insn is available it may help
+     discover additional redundancies, so mark it for later deletion.  */
+  for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
+       a_occr && (a_occr->insn != insn);
+       a_occr = get_bb_avail_insn (bb, a_occr->next));
+
+  if (!a_occr)
+    delete_insn (insn);
+  else
+    a_occr->deleted_p = 1;
+
+cleanup:
+  if (rollback_unoccr)
+    obstack_free (&unoccr_obstack, rollback_unoccr);
+}
+
+/* Performing the redundancy elimination as described before.  */
+
+static void
+eliminate_partially_redundant_loads (void)
+{
+  rtx insn;
+  basic_block bb;
+
+  /* Note we start at block 1.  */
+
+  if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+    return;
+
+  FOR_BB_BETWEEN (bb,
+		  ENTRY_BLOCK_PTR->next_bb->next_bb,
+		  EXIT_BLOCK_PTR,
+		  next_bb)
+    {
+      if (! bb_has_well_behaved_predecessors (bb))
+	continue;
+
+      /* Do not try this optimization on cold basic blocks.  */
+      if (probably_cold_bb_p (bb))
+	continue;
+
+      reset_opr_set_tables ();
+
+      FOR_BB_INSNS (bb, insn)
+	{
+	  /* Is it a load - of the form (set (reg) (mem))?  */
+	  if (NONJUMP_INSN_P (insn)
+              && GET_CODE (PATTERN (insn)) == SET
+	      && REG_P (SET_DEST (PATTERN (insn)))
+	      && MEM_P (SET_SRC (PATTERN (insn))))
+	    {
+	      rtx pat = PATTERN (insn);
+	      rtx src = SET_SRC (pat);
+	      struct expr *expr;
+
+	      if (!MEM_VOLATILE_P (src)
+		  && GET_MODE (src) != BLKmode
+		  && general_operand (src, GET_MODE (src))
+		  /* Are the operands unchanged since the start of the
+		     block?  */
+		  && oprs_unchanged_p (src, insn, false)
+		  && !(flag_non_call_exceptions && may_trap_p (src))
+		  && !side_effects_p (src)
+		  /* Is the expression recorded?  */
+		  && (expr = lookup_expr_in_table (src)) != NULL)
+		{
+		  /* We now have a load (insn) and an available memory at
+		     its BB start (expr). Try to remove the loads if it is
+		     redundant.  */
+		  eliminate_partially_redundant_load (bb, insn, expr);
+		}
+	    }
+
+	  /* Keep track of everything modified by this insn.  */
+	  if (INSN_P (insn))
+	    mark_oprs_set (insn);
+	}
+    }
+
+  commit_edge_insertions ();
+}
+
+/* Go over the expression hash table and delete insns that were
+   marked for later deletion.  */
+
+/* This helper is called via htab_traverse.  */
+static int
+delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  struct expr *expr = (struct expr *) *slot;
+  struct occr *occr;
+
+  for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
+    {
+      if (occr->deleted_p)
+	{
+	  delete_insn (occr->insn);
+	  stats.insns_deleted++;
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "deleting insn:\n");
+	      print_rtl_single (dump_file, occr->insn);
+	      fprintf (dump_file, "\n");
+	    }
+	}
+    }
+
+  return 1;
+}
+
+static void
+delete_redundant_insns (void)
+{
+  htab_traverse (expr_table, delete_redundant_insns_1, NULL);
+  if (dump_file)
+    fprintf (dump_file, "\n");
+}
+
+/* Main entry point of the GCSE after reload - clean some redundant loads
+   due to spilling.  */
+
+void
+gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
+{
+  memset (&stats, 0, sizeof (stats));
+
+  /* Allocate ememory for this pass.
+     Also computes and initializes the insns' CUIDs.  */
+  alloc_mem ();
+
+  /* We need alias analysis.  */
+  init_alias_analysis ();
+
+  compute_hash_table ();
+
+  if (dump_file)
+    dump_hash_table (dump_file);
+
+  if (htab_elements (expr_table) > 0)
+    {
+      eliminate_partially_redundant_loads ();
+      delete_redundant_insns ();
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
+	  fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
+	  fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
+	  fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
+	  fprintf (dump_file, "\n\n");
+	}
+    }
+    
+  /* We are finished with alias.  */
+  end_alias_analysis ();
+
+  free_mem ();
+}
+