RE: PATCH committed to dataflow branch.

[Kenneth Zadeck <Kenneth dot Zadeck at NaturalBridge dot com>]

I forgot the patch and the date on the changelog entry was wrong. But
asside from that it was perfect.


> This patch fixes the inconsistencies that were generated by zdenek's 
> latest patch to loop-invariant.c.
> 
> The dataflow branch is now ready for another mainline merge.  Just 
> ignore all of the changes
> to loop-invariant.c.
> 
> 2005-12-22  Kenneth Zadeck <zadeck@naturalbridge.com>
>     * df-core.c (df_find_def, df_find_use):  Added subreg aware code.
>     (df_reg_defined, df_reg_used): New function.
>     df.h (df_reg_defined, df_reg_used): New function.
>     loop-invariant.c (struct invariant, hash_invariant_expr,
>     eq_invariant_expr, find_or_insert_inv, find_or_insert_inv,
>     find_identical_invariants, merge_identical_invariants,
>     find_defs, create_new_invariant, check_dependencies,
>     find_invariant_insn, find_invariants, get_inv_cost,
>     best_gain_for_invariant, set_move_mark, move_invariants,
>     free_inv_motion_data): Functions added from mainline patch.
>     (invariant_for_use, hash_invariant_expr_1, invariant_expr_equal_p,
>     check_dependencies, create_new_invariant, find_invariant_insn
>     move_invariant_reg): Functions modified from mainline patch to be
>     consistent with latest df.
> 
> bootstraped and tested on i686-pc-linux-gnu.
> 
> Kenny

===File ~/patches/dataflow/dataflow16.diff==================
Index: df-core.c
===================================================================
--- df-core.c	(revision 109148)
+++ df-core.c	(working copy)
@@ -128,12 +128,6 @@ The df_instance is also freed and its po
 
 
 
-One instance of df is stored in the cfun structure.  This instance is
-used to manage persistent dataflow in the backend.  This support is
-currently primitive.  The live variables and uninitialized variables
-problems are defined with DF_HARD_REGS.
-
-
 Scanning produces a `struct df_ref' data structure (ref) is allocated
 for every register reference (def or use) and this records the insn
 and bb the ref is found within.  The refs are linked together in
@@ -146,56 +140,38 @@ Different optimizations have different n
 register allocation and schedulers should be using the bitmaps and the
 rest of the backend should be upgraded to using and maintaining the
 linked information.  
-*/
 
 
-/* 
-LINKAGE PROBLEMS:
-
-While incremental bitmaps are not worthwhile to maintian, incremental
-chains are perfectly reasonable.  The fastest way to build chains from
-scratch or after significant modifications is to build reaching
-definitions (RD) and build the chains from this.  
-
-However, these are not suitable datastructures to maintain
-incrementally so the bitmaps are destroyed after the chains are built
-and the incremental calls should be used as instructions are modified,
-added or deleted.
-
 
 PHILOSOPHY:
 
-Note that the dataflow information is not updated for every newly
-deleted or created insn.  If the dataflow information requires
-updating then all the changed, new, or deleted insns needs to be
-marked with df_insn_modify (or df_insns_modify) either directly or
-indirectly (say through calling df_insn_delete).  df_insn_modify
-marks all the modified insns to get processed the next time df_analyze
- is called.
-
-Beware that tinkering with insns may invalidate the dataflow information.
-The philosophy behind these routines is that once the dataflow
-information has been gathered, the user should store what they require
-before they tinker with any insn.  Once a reg is replaced, for example,
-then the reg-def/reg-use chains will point to the wrong place.  Once a
-whole lot of changes have been made, df_analyze can be called again
-to update the dataflow information.  Currently, this is not very smart
-with regard to propagating changes to the dataflow so it should not
-be called very often.
-
-
-INCREMENTAL DATAFLOW
-
-There is no interface to give a set of blocks over with to resolve the
-iteration.  In general, restarting a dataflow iteration is difficult
-and expensive.  The best way to keep the dataflow infomation up to
-data (if this is really what is needed) it to formulate a problem
-specific solution.
+While incremental bitmaps are not worthwhile to maintian, incremental
+chains may be perfectly reasonable.  The fastest way to build chains
+from scratch or after significant modifications is to build reaching
+definitions (RD) and build the chains from this.
+
+However, general algorithms for maintaining use-def or def-use chains
+are not practical.  The amount of work to recompute the chain any
+chain after an arbitrary change is large.  However, with a modest
+amount of work it is generally possible to have the application that
+uses the chains keep them up to date.  The high level knowledge of
+what is really happening is essential to crafting efficient
+incremental algorithms.
+
+As for the bit vector problems, there is no interface to give a set of
+blocks over with to resolve the iteration.  In general, restarting a
+dataflow iteration is difficult and expensive.  Again, the best way to
+keep the dataflow infomation up to data (if this is really what is
+needed) it to formulate a problem specific solution.
+
+There are fine grained calls for creating and deleting references from
+instructions in df-scan.c.  However, these are not currently connected
+to the engine that resolves the dataflow equations.
 
 
 DATA STRUCTURES:
 
-The basic object is a REF (reference) and this may either be a 
+The basic object is a DF_REF (reference) and this may either be a 
 DEF (definition) or a USE of a register.
 
 These are linked into a variety of lists; namely reg-def, reg-use,
@@ -1016,31 +992,58 @@ df_find_def (struct df *df, rtx insn, rt
   unsigned int uid;
   struct df_ref *def;
 
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+  gcc_assert (REG_P (reg));
+
   uid = INSN_UID (insn);
   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
-    if (rtx_equal_p (DF_REF_REG (def), reg))
+    if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
       return def;
 
   return NULL;
 }
 
 
-/* Return true if REG is referenced in INSN, zero otherwise.  */ 
+/* Return true if REG is defined in INSN, zero otherwise.  */ 
+
+bool
+df_reg_defined (struct df *df, rtx insn, rtx reg)
+{
+  return df_find_def (df, insn, reg) != NULL;
+}
+  
 
+/* Finds the reference corresponding to the use of REG in INSN.
+   DF is the dataflow object.  */
+  
 struct df_ref *
 df_find_use (struct df *df, rtx insn, rtx reg)
 {
   unsigned int uid;
   struct df_ref *use;
 
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+  gcc_assert (REG_P (reg));
+
   uid = INSN_UID (insn);
   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
-    if (rtx_equal_p (DF_REF_REG (use), reg))
+    if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
       return use; 
 
   return NULL;
 }
 
+
+/* Return true if REG is referenced in INSN, zero otherwise.  */ 
+
+bool
+df_reg_used (struct df *df, rtx insn, rtx reg)
+{
+  return df_find_use (df, insn, reg) != NULL;
+}
+  
 
 /****************************************************************************/
 /* Debugging and printing functions.                                        */
Index: df.h
===================================================================
--- df.h	(revision 109148)
+++ df.h	(working copy)
@@ -310,13 +310,6 @@ struct df
   bitmap exit_block_uses;        /* The set of hardware registers used in exit block.  */
 };
 
-struct df_map
-{
-  rtx old;
-  rtx new;
-};
-
-
 #define DF_SCAN_BB_INFO(DF, BB) (df_scan_get_bb_info((DF)->problems_by_index[DF_SCAN],(BB)->index))
 #define DF_RU_BB_INFO(DF, BB) (df_ru_get_bb_info((DF)->problems_by_index[DF_RU],(BB)->index))
 #define DF_RD_BB_INFO(DF, BB) (df_rd_get_bb_info((DF)->problems_by_index[DF_RD],(BB)->index))
@@ -515,7 +508,9 @@ extern struct df_ref * df_bb_regno_first
 extern struct df_ref * df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
 extern bool df_insn_regno_def_p (struct df *, rtx, unsigned int);
 extern struct df_ref * df_find_def (struct df *, rtx, rtx);
+extern bool df_reg_defined (struct df *, rtx, rtx);
 extern struct df_ref * df_find_use (struct df *, rtx, rtx);
+extern bool df_reg_used (struct df *, rtx, rtx);
 extern void df_iterative_dataflow (struct dataflow *, bitmap, bitmap, int *, int, bool);
 extern void df_dump (struct df *, FILE *);
 extern void df_chain_dump (struct df *, struct df_link *, FILE *);
Index: loop-invariant.c
===================================================================
--- loop-invariant.c	(revision 109148)
+++ loop-invariant.c	(working copy)
@@ -46,10 +46,12 @@ Software Foundation, 51 Franklin Street,
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "expr.h"
+#include "recog.h"
 #include "output.h"
 #include "function.h"
 #include "flags.h"
 #include "df.h"
+#include "hashtab.h"
 
 /* The data stored for the loop.  */
 
@@ -88,8 +90,12 @@ struct invariant
   /* The number of the invariant.  */
   unsigned invno;
 
-  /* Whether we already processed the invariant.  */
-  bool processed;
+  /* The number of the invariant with the same value.  */
+  unsigned eqto;
+
+  /* If we moved the invariant out of the loop, the register that contains its
+     value.  */
+  rtx reg;
 
   /* The definition of the invariant.  */
   struct def *def;
@@ -114,6 +120,23 @@ struct invariant
   unsigned stamp;
 };
 
+/* Entry for hash table of invariant expressions.  */
+
+struct invariant_expr_entry
+{
+  /* The invariant.  */
+  struct invariant *inv;
+
+  /* Its value.  */
+  rtx expr;
+
+  /* Its mode.  */
+  enum machine_mode mode;
+
+  /* Its hash.  */
+  hashval_t hash;
+};
+
 /* The actual stamp for marking already visited invariants during determining
    costs of movements.  */
 
@@ -199,6 +222,269 @@ check_maybe_invariant (rtx x)
   return true;
 }
 
+/* Returns the invariant definition for USE, or NULL if USE is not
+   invariant.  */
+
+static struct invariant *
+invariant_for_use (struct df_ref *use)
+{
+  struct df_link *defs;
+  struct df_ref *def;
+  basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
+
+  defs = DF_REF_CHAIN (use);
+  if (!defs || defs->next)
+    return NULL;
+  def = defs->ref;
+  if (!DF_REF_DATA (def))
+    return NULL;
+
+  def_bb = DF_REF_BB (def);
+  if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
+    return NULL;
+  return DF_REF_DATA (def);
+}
+
+/* Computes hash value for invariant expression X in INSN.  */
+
+static hashval_t
+hash_invariant_expr_1 (rtx insn, rtx x)
+{
+  enum rtx_code code = GET_CODE (x);
+  int i, j;
+  const char *fmt;
+  hashval_t val = code;
+  int do_not_record_p;
+  struct df_ref *use;
+  struct invariant *inv;
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case CONST:
+    case LABEL_REF:
+      return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
+
+    case REG:
+      use = df_find_use (df, insn, x);
+      if (!use)
+	return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
+      inv = invariant_for_use (use);
+      if (!inv)
+	return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
+
+      gcc_assert (inv->eqto != ~0u);
+      return inv->eqto;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
+      else if (fmt[i] == 'E')
+	{
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
+	}
+    }
+
+  return val;
+}
+
+/* Returns true if the invariant expressions E1 and E2 used in insns INSN1
+   and INSN2 have always the same value.  */
+
+static bool
+invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
+{
+  enum rtx_code code = GET_CODE (e1);
+  int i, j;
+  const char *fmt;
+  struct df_ref *use1, *use2;
+  struct invariant *inv1 = NULL, *inv2 = NULL;
+  rtx sub1, sub2;
+
+  /* If mode of only one of the operands is VOIDmode, it is not equivalent to
+     the other one.  If both are VOIDmode, we rely on the caller of this
+     function to verify that their modes are the same.  */
+  if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
+    return false;
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case CONST:
+    case LABEL_REF:
+      return rtx_equal_p (e1, e2);
+
+    case REG:
+      use1 = df_find_use (df, insn1, e1);
+      use2 = df_find_use (df, insn2, e2);
+      if (use1)
+	inv1 = invariant_for_use (use1);
+      if (use2)
+	inv2 = invariant_for_use (use2);
+
+      if (!inv1 && !inv2)
+	return rtx_equal_p (e1, e2);
+
+      if (!inv1 || !inv2)
+	return false;
+
+      gcc_assert (inv1->eqto != ~0u);
+      gcc_assert (inv2->eqto != ~0u);
+      return inv1->eqto == inv2->eqto;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  sub1 = XEXP (e1, i);
+	  sub2 = XEXP (e2, i);
+
+	  if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
+	    return false;
+	}
+
+      else if (fmt[i] == 'E')
+	{
+	  if (XVECLEN (e1, i) != XVECLEN (e2, i))
+	    return false;
+
+	  for (j = 0; j < XVECLEN (e1, i); j++)
+	    {
+	      sub1 = XVECEXP (e1, i, j);
+	      sub2 = XVECEXP (e2, i, j);
+
+	      if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
+		return false;
+	    }
+	}
+    }
+
+  return true;
+}
+
+/* Returns hash value for invariant expression entry E.  */
+
+static hashval_t
+hash_invariant_expr (const void *e)
+{
+  const struct invariant_expr_entry *entry = e;
+
+  return entry->hash;
+}
+
+/* Compares invariant expression entries E1 and E2.  */
+
+static int
+eq_invariant_expr (const void *e1, const void *e2)
+{
+  const struct invariant_expr_entry *entry1 = e1;
+  const struct invariant_expr_entry *entry2 = e2;
+
+  if (entry1->mode != entry2->mode)
+    return 0;
+
+  return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
+				 entry2->inv->insn, entry2->expr);
+}
+
+/* Checks whether invariant with value EXPR in machine mode MODE is
+   recorded in EQ.  If this is the case, return the invariant.  Otherwise
+   insert INV to the table for this expression and return INV.  */
+
+static struct invariant *
+find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
+		    struct invariant *inv)
+{
+  hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
+  struct invariant_expr_entry *entry;
+  struct invariant_expr_entry pentry;
+  PTR *slot;
+
+  pentry.expr = expr;
+  pentry.inv = inv;
+  pentry.mode = mode;
+  slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
+  entry = *slot;
+
+  if (entry)
+    return entry->inv;
+
+  entry = xmalloc (sizeof (struct invariant_expr_entry));
+  entry->inv = inv;
+  entry->expr = expr;
+  entry->mode = mode;
+  entry->hash = hash;
+  *slot = entry;
+
+  return inv;
+}
+
+/* Finds invariants identical to INV and records the equivalence.  EQ is the
+   hash table of the invariants.  */
+
+static void
+find_identical_invariants (htab_t eq, struct invariant *inv)
+{
+  unsigned depno;
+  bitmap_iterator bi;
+  struct invariant *dep;
+  rtx expr, set;
+  enum machine_mode mode;
+
+  if (inv->eqto != ~0u)
+    return;
+
+  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
+    {
+      dep = VEC_index (invariant_p, invariants, depno);
+      find_identical_invariants (eq, dep);
+    }
+
+  set = single_set (inv->insn);
+  expr = SET_SRC (set);
+  mode = GET_MODE (expr);
+  if (mode == VOIDmode)
+    mode = GET_MODE (SET_DEST (set));
+  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
+
+  if (dump_file && inv->eqto != inv->invno)
+    fprintf (dump_file,
+	     "Invariant %d is equivalent to invariant %d.\n ",
+	     inv->invno, inv->eqto);
+}
+
+/* Find invariants with the same value and record the equivalences.  */
+
+static void
+merge_identical_invariants (void)
+{
+  unsigned i;
+  struct invariant *inv;
+  htab_t eq = htab_create (VEC_length (invariant_p, invariants),
+			   hash_invariant_expr, eq_invariant_expr, free);
+
+  for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
+    find_identical_invariants (eq, inv);
+
+  htab_delete (eq);
+}
+
 /* Determines the basic blocks inside LOOP that are always executed and
    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
    basic blocks that may either exit the loop, or contain the call that
@@ -321,9 +607,10 @@ find_defs (struct loop *loop, basic_bloc
 
 /* Creates a new invariant for definition DEF in INSN, depending on invariants
    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
-   unless the program ends due to a function call.  */
+   unless the program ends due to a function call.  The newly created invariant
+   is returned.  */
 
-static void
+static struct invariant *
 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
 		      bool always_executed)
 {
@@ -342,11 +629,12 @@ create_new_invariant (struct def *def, r
     inv->cost = rtx_cost (SET_SRC (set), SET);
 
   inv->move = false;
-  inv->processed = false;
+  inv->reg = NULL_RTX;
   inv->stamp = 0;
   inv->insn = insn;
 
   inv->invno = VEC_length (invariant_p, invariants);
+  inv->eqto = ~0u;
   if (def)
     def->invno = inv->invno;
   VEC_safe_push (invariant_p, heap, invariants, inv);
@@ -358,6 +646,8 @@ create_new_invariant (struct def *def, r
 	       INSN_UID (insn), inv->invno, inv->cost);
       dump_bitmap (dump_file, inv->depends_on);
     }
+
+  return inv;
 }
 
 /* Record USE at DEF.  */
@@ -388,7 +678,8 @@ check_dependencies (rtx insn, bitmap dep
   struct df_ref *use, *def;
   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
   struct def *def_data;
-  
+  struct invariant *inv;
+
   for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
     {
       defs = DF_REF_CHAIN (use);
@@ -399,11 +690,17 @@ check_dependencies (rtx insn, bitmap dep
 	return false;
 
       def = defs->ref;
-      def_data = DF_REF_DATA (def);
-      if (!def_data)
+      inv = DF_REF_DATA (def);
+      if (!inv)
 	return false;
 
+      def_data = inv->def;
+      gcc_assert (def_data != NULL);
+
       def_bb = DF_REF_BB (def);
+      /* Note that in case bb == def_bb, we know that the definition dominates
+	 insn, because def has DF_REF_DATA defined and we process the insns
+	 in the basic block bb sequentially.  */
       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 	return false;
 
@@ -425,13 +722,14 @@ find_invariant_insn (rtx insn, bool alwa
   bitmap depends_on;
   rtx set, dest;
   bool simple = true;
+  struct invariant *inv;
 
   /* Until we get rid of LIBCALLS.  */
   if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
       || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
       || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
     return;
- 
+
   set = single_set (insn);
   if (!set)
     return;
@@ -464,15 +762,17 @@ find_invariant_insn (rtx insn, bool alwa
     }
 
   if (simple)
-    {
-      ref = df_find_def (df, insn, dest);
-      def = xcalloc (1, sizeof (struct def));
-      DF_REF_DATA (ref) = def;
-    }
+    def = xcalloc (1, sizeof (struct def));
   else
     def = NULL;
 
-  create_new_invariant (def, insn, depends_on, always_executed);
+  inv = create_new_invariant (def, insn, depends_on, always_executed);
+
+  if (simple)
+    {
+      ref = df_find_def (df, insn, dest);
+      DF_REF_DATA (ref) = inv;
+    }
 }
 
 /* Record registers used in INSN that have a unique invariant definition.  */
@@ -480,24 +780,14 @@ find_invariant_insn (rtx insn, bool alwa
 static void
 record_uses (rtx insn)
 {
-  struct df_link *defs;
-  struct df_ref *use, *def;
-  basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
-  
+  struct df_ref *use;
+  struct invariant *inv;
+
   for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
     {
-      defs = DF_REF_CHAIN (use);
-      if (!defs || defs->next)
-	continue;
-      def = defs->ref;
-      if (!DF_REF_DATA (def))
-	continue;
-
-      def_bb = DF_REF_BB (def);
-      if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
-	continue;
-
-      record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
+      inv = invariant_for_use (use);
+      if (inv)
+	record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use));
     }
 }
 
@@ -570,6 +860,7 @@ find_invariants (struct loop *loop)
 
   find_defs (loop, body);
   find_invariants_body (loop, body, always_reached, always_executed);
+  merge_identical_invariants ();
 
   BITMAP_FREE (always_reached);
   BITMAP_FREE (always_executed);
@@ -604,6 +895,9 @@ get_inv_cost (struct invariant *inv, int
   struct invariant *dep;
   bitmap_iterator bi;
 
+  /* Find the representative of the class of the equivalent invariants.  */
+  inv = VEC_index (invariant_p, invariants, inv->eqto);
+
   *comp_cost = 0;
   *regs_needed = 0;
   if (inv->move
@@ -680,6 +974,10 @@ best_gain_for_invariant (struct invarian
       if (inv->move)
 	continue;
 
+      /* Only consider the "representatives" of equivalent invariants.  */
+      if (inv->eqto != inv->invno)
+	continue;
+
       again = gain_for_invariant (inv, &aregs_needed,
 				  new_regs, regs_used, n_inv_uses);
       if (again > gain)
@@ -701,6 +999,9 @@ set_move_mark (unsigned invno)
   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
   bitmap_iterator bi;
 
+  /* Find the representative of the class of the equivalent invariants.  */
+  inv = VEC_index (invariant_p, invariants, inv->eqto);
+
   if (inv->move)
     return;
   inv->move = true;
@@ -764,74 +1065,71 @@ static void
 move_invariant_reg (struct loop *loop, unsigned invno)
 {
   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
+  struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
   unsigned i;
   basic_block preheader = loop_preheader_edge (loop)->src;
   rtx reg, set;
   struct use *use;
   bitmap_iterator bi;
 
-  if (inv->processed)
+  if (inv->reg
+      || !repr->move)
     return;
-  inv->processed = true;
 
-  if (inv->depends_on)
+  /* If this is a representative of the class of equivalent invariants,
+     really move the invariant.  Otherwise just replace its use with
+     the register used for the representative.  */
+  if (inv == repr)
     {
-      EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
+      if (inv->depends_on)
 	{
-	  move_invariant_reg (loop, i);
+	  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
+	    {
+	      move_invariant_reg (loop, i);
+	    }
 	}
-    }
 
-  /* Move the set out of the loop.  If the set is always executed (we could
-     omit this condition if we know that the register is unused outside of the
-     loop, but it does not seem worth finding out) and it has no uses that
-     would not be dominated by it, we may just move it (TODO).  Otherwise we
-     need to create a temporary register.  */
-  set = single_set (inv->insn);
-  reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
-
-#if 0
-  df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
-			 BLOCK_FOR_INSN (inv->insn), inv->insn);
-#else
-  emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
-#endif
-
-  /* If the SET_DEST of the invariant insn is a reg, we can just move
-     the insn out of the loop.  Otherwise, we have to use gen_move_insn
-     to let emit_move_insn produce a valid instruction stream.  */
-  if (REG_P (SET_DEST (set)))
-    {
-      SET_DEST (set) = reg;
-      reorder_insns (inv->insn, inv->insn, BB_END (preheader));
-#if 0
-      df_insn_modify (df, preheader, inv->insn);
-#endif
+      /* Move the set out of the loop.  If the set is always executed (we could
+	 omit this condition if we know that the register is unused outside of the
+	 loop, but it does not seem worth finding out) and it has no uses that
+	 would not be dominated by it, we may just move it (TODO).  Otherwise we
+	 need to create a temporary register.  */
+      set = single_set (inv->insn);
+      reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
+      emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
+
+      /* If the SET_DEST of the invariant insn is a reg, we can just move
+	 the insn out of the loop.  Otherwise, we have to use gen_move_insn
+	 to let emit_move_insn produce a valid instruction stream.  */
+      if (REG_P (SET_DEST (set)))
+	{
+	  SET_DEST (set) = reg;
+	  reorder_insns (inv->insn, inv->insn, BB_END (preheader));
+	}
+      else
+	{
+	  emit_insn_after (gen_move_insn (reg, SET_SRC (set)), BB_END (preheader));
+	  delete_insn (inv->insn);
+	}
     }
   else
     {
-#if 0
-      df_pattern_emit_after (df, gen_move_insn (reg, SET_SRC (set)),
-			     preheader, BB_END (preheader));
-      df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn);
-#else
-      emit_insn_after (gen_move_insn (reg, SET_SRC (set)), BB_END (preheader));
+      move_invariant_reg (loop, repr->invno);
+      reg = repr->reg;
+      set = single_set (inv->insn);
+      emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
       delete_insn (inv->insn);
-#endif
     }
 
+  inv->reg = reg;
+
   /* Replace the uses we know to be dominated.  It saves work for copy
      propagation, and also it is necessary so that dependent invariants
      are computed right.  */
   if (inv->def)
     {
       for (use = inv->def->uses; use; use = use->next)
-	{
-	  *use->pos = reg;
-#if 0
-	  df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
-#endif
-	}
+	*use->pos = reg;
     }
 }
 
@@ -845,10 +1143,7 @@ move_invariants (struct loop *loop)
   unsigned i;
 
   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
-    {
-      if (inv->move)
-	move_invariant_reg (loop, i);
-    }
+    move_invariant_reg (loop, i);
 }
 
 /* Initializes invariant motion data.  */
@@ -869,18 +1164,20 @@ free_inv_motion_data (void)
   unsigned i;
   struct def *def;
   struct invariant *inv;
-  unsigned int n_defs = DF_DEFS_SIZE (df);
 
-  for (i = 0; i < n_defs; i++)
+  for (i = 0; i < DF_DEFS_SIZE (df); i++)
     {
       struct df_ref * ref = DF_DEFS_GET (df, i);
       if (!ref)
 	continue;
 
-      def = DF_REF_DATA (ref);
-      if (!def)
+      inv = DF_REF_DATA (ref);
+      if (!inv)
 	continue;
 
+      def = inv->def;
+      gcc_assert (def != NULL);
+
       free_use_list (def->uses);
       free (def);
       DF_REF_DATA (ref) = NULL;
============================================================