[patch] Handle equivalent loop invariants as one in loop-invariant.c

[Steven Bosscher <stevenb at suse dot de>]

Hi,

This patch makes loop-invariant.c deal with equivalent invariants.
This is a very significant improvement.  For example it gives a 6%
speedup for gzip with "-O2 -floop-optimize2 -fmove-loop-invariants".


The loop-invariant.c bits are pretty obvious, I'd say.  But to 
make reviewing this patch easier, I'll try to clarify the changes:

- Each invariant has two uids: inv->invno and inv->eqto.  The first
  is an index to the queue of all invariants.  The second is the
  index of the representative equivalent invariant in the queue.

- find_or_insert_inv looks for an equivalent in a hashtable, and
  returns the existing invariant if there is one.  Otherwise it
  puts it in the table.  Used for merging equivalent invariants.
  We use the libiberty hashtab, which explains the Makefile change.

- merge_identical_invariants sets up the inv->eqto indices, by
  calling find_or_insert_inv on all invariants.

- invariant_for_use is just code factoring.  record_uses used to
  test for the things invariant_for_use now checks, but the hash
  and equivalence functions for the hash table need to do the
  same, so it's now split out into a separate function.

- the move_invariant_reg hunk may look large, but it's really only
  re-indentation.  The only new thing is that if an invariant is
  not the representative of a class, the invariant is not moved out
  because the representative will have been moved out already.

- the whole thing is put together like this:
  1) find all loop invariant expressions.
  2) merge equivalent loop invariant expressions.
  3) determine which classes of invariants to move out of the loop.
     The cost function takes dependent invariants into account.
  4) move the selected expressions out of the loop.
  The only new part is step 2.

The patch hunks for df.[ch] are two bug fixes and one new function.
The df_bitmaps_free edit is just a speedup.  The df_bb_modify change
avoids an ICE in SPEC.  The new function is used in loop-invariant.c


When this patch is in mainline, I'll take care of putting all the
loop-invariant.c changes on the dataflow branch, including these
df bits.  Once that is finished, I can start working on a fix for
the EH_RETURN registers bug, which is still present on the dataflow
branch too.

But until then...

Bootstrapped and tested (all except Ada) on x86_64-suse-linux-gnu.
Also bootstrapped (c,c++) and tested on {ia64,x86_64}-suse-linux-gnu
with "-O2 -floop-optimize2 -fmove-loop-invariants" hard-coded and
the old RTL loop optimized disabled.  Also bootstrapped some time
ago on i686, powerpc, and powerpc64 with the new code enabled.

OK for mainline?

Thanks,

Gr.
Steven


	* df.c (df_bitmaps_free): Only work for bbs for that structures are
	allocated.
	(df_bb_modify): Realloc tables to the new index.
	(df_find_use): New function.
	* df.h (df_find_use): Declare.

	* loop-invariant.c: Include hashtab.h.
	(struct invariant): Remove processed field, add eqto and reg fields.
	(struct invariant_expr_entry): New.
	(invariant_for_use, hash_invariant_expr_1, invariant_expr_equal_p,
	hash_invariant_expr, eq_invariant_expr, find_or_insert_inv,
	find_identical_invariants, merge_identical_invariants): New functions.
	(create_new_invariant): Return the new invariant.  Initialize new
	fields.
	(find_invariants): Call merge_identical_invariants.
	(get_inv_cost, best_gain_for_invariant, set_move_mark,
	move_invariant_reg): Handle equivalent invariants.
	* Makefile.in (loop-invariant.o): Add HASHTAB_H dependency.

Index: df.c
===================================================================
--- df.c	(revision 108654)
+++ df.c	(working copy)
@@ -451,14 +451,11 @@ df_bitmaps_alloc (struct df *df, bitmap 
 static void
 df_bitmaps_free (struct df *df, int flags)
 {
-  basic_block bb;
+  unsigned i;
 
-  FOR_EACH_BB (bb)
+  for (i = 0; i < df->n_bbs; i++)
     {
-      struct bb_info *bb_info = DF_BB_INFO (df, bb);
-
-      if (!bb_info)
-	continue;
+      struct bb_info *bb_info = &df->bbs[i];
 
       if ((flags & DF_RD) && bb_info->rd_in)
 	{
@@ -2649,7 +2646,7 @@ static void
 df_bb_modify (struct df *df, basic_block bb)
 {
   if ((unsigned) bb->index >= df->n_bbs)
-    df_bb_table_realloc (df, df->n_bbs);
+    df_bb_table_realloc (df, bb->index);
 
   bitmap_set_bit (df->bbs_modified, bb->index);
 }
@@ -3052,6 +3049,27 @@ df_find_def (struct df *df, rtx insn, rt
   return NULL;
 }
 
+/* Finds the reference corresponding to the use of REG in INSN.
+   DF is the dataflow object.  */
+
+struct ref *
+df_find_use (struct df *df, rtx insn, rtx reg)
+{
+  struct df_link *uses;
+
+  for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
+    {
+      rtx areg = DF_REF_REG (uses->ref);
+      if (GET_CODE (areg) == SUBREG)
+	areg = SUBREG_REG (areg);
+
+      if (rtx_equal_p (areg, reg))
+	return uses->ref;
+    }
+
+  return NULL;
+}
+
 /* Return 1 if REG is referenced in INSN, zero otherwise.  */ 
 
 int
Index: df.h
===================================================================
--- df.h	(revision 108654)
+++ df.h	(working copy)
@@ -293,6 +293,8 @@ extern struct ref *df_bb_regno_last_def_
 
 extern struct ref *df_find_def (struct df *, rtx, rtx);
 
+extern struct ref *df_find_use (struct df *, rtx, rtx);
+
 extern int df_reg_used (struct df *, rtx, rtx);
 
 /* Functions for debugging from GDB.  */
Index: loop-invariant.c
===================================================================
--- loop-invariant.c	(revision 108655)
+++ 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,282 @@ 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 ref *use)
+{
+  struct df_link *defs;
+  struct 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 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;
+}
+
+/* Compares invariant expressions E1 and E2 in modes MODE1 and MODE2 used in
+   insns INSN1 and INSN2.  */
+
+static bool
+invariant_expr_equal_p (rtx insn1, rtx e1, enum machine_mode mode1,
+			rtx insn2, rtx e2, enum machine_mode mode2)
+{
+  enum rtx_code code = GET_CODE (e1);
+  int i, j;
+  const char *fmt;
+  struct ref *use1, *use2;
+  struct invariant *inv1 = NULL, *inv2 = NULL;
+  rtx sub1, sub2;
+  enum machine_mode submode1, submode2;
+
+  gcc_assert (GET_MODE (e1) == VOIDmode || GET_MODE (e1) == mode1);
+  gcc_assert (GET_MODE (e2) == VOIDmode || GET_MODE (e2) == mode2);
+
+  if (code != GET_CODE (e2) || mode1 != mode2)
+    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);
+	  submode1 = GET_MODE (sub1);
+	  if (submode1 == VOIDmode)
+	    submode1 = mode1;
+	  submode2 = GET_MODE (sub2);
+	  if (submode2 == VOIDmode)
+	    submode2 = mode2;
+
+	  if (!invariant_expr_equal_p (insn1, sub1, submode1,
+				       insn2, sub2, submode2))
+	    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);
+	      submode1 = GET_MODE (sub1);
+	      if (submode1 == VOIDmode)
+		submode1 = mode1;
+	      submode2 = GET_MODE (sub2);
+	      if (submode2 == VOIDmode)
+		submode2 = mode2;
+
+	      if (!invariant_expr_equal_p (insn1, sub1, submode1,
+					   insn2, sub2, submode2))
+		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;
+
+  return invariant_expr_equal_p (entry1->inv->insn, entry1->expr, entry1->mode,
+				 entry2->inv->insn, entry2->expr, entry2->mode);
+}
+
+/* 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
@@ -320,9 +619,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)
 {
@@ -341,11 +641,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);
@@ -357,6 +658,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.  */
@@ -387,7 +690,8 @@ check_dependencies (rtx insn, bitmap dep
   struct ref *use, *def;
   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
   struct def *def_data;
-  
+  struct invariant *inv;
+
   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
     {
       use = uses->ref;
@@ -400,11 +704,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;
 
@@ -426,13 +736,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;
@@ -465,15 +776,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.  */
@@ -481,26 +794,16 @@ find_invariant_insn (rtx insn, bool alwa
 static void
 record_uses (rtx insn)
 {
-  struct df_link *uses, *defs;
-  struct ref *use, *def;
-  basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
-  
+  struct df_link *uses;
+  struct ref *use;
+  struct invariant *inv;
+
   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
     {
       use = uses->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));
     }
 }
 
@@ -573,6 +876,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);
@@ -607,6 +911,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
@@ -683,6 +990,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)
@@ -704,6 +1015,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;
@@ -766,50 +1080,68 @@ 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)));
-  df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
-			 BLOCK_FOR_INSN (inv->insn), 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));
-      df_insn_modify (df, preheader, inv->insn);
+      /* 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)));
+      df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
+			     BLOCK_FOR_INSN (inv->insn), 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));
+	  df_insn_modify (df, preheader, inv->insn);
+	}
+      else
+	{
+	  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
     {
-      df_pattern_emit_after (df, gen_move_insn (reg, SET_SRC (set)),
-			     preheader, BB_END (preheader));
+      move_invariant_reg (loop, repr->invno);
+      reg = repr->reg;
+      set = single_set (inv->insn);
+      df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
+			     BLOCK_FOR_INSN (inv->insn), inv->insn);
       df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn);
     }
 
+  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.  */
@@ -833,10 +1165,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.  */
@@ -863,9 +1192,11 @@ free_inv_motion_data (void)
       if (!df->defs[i])
 	continue;
 
-      def = DF_REF_DATA (df->defs[i]);
-      if (!def)
+      inv = DF_REF_DATA (df->defs[i]);
+      if (!inv)
 	continue;
+      def = inv->def;
+      gcc_assert (def != NULL);
 
       free_use_list (def->uses);
       free (def);
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 108654)
+++ Makefile.in	(working copy)
@@ -2372,7 +2372,8 @@ loop-iv.o : loop-iv.c $(CONFIG_H) $(SYST
    output.h intl.h
 loop-invariant.o : loop-invariant.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h \
-   $(TM_H) $(TM_P_H) function.h $(FLAGS_H) $(DF_H) $(OBSTACK_H) output.h
+   $(TM_H) $(TM_P_H) function.h $(FLAGS_H) $(DF_H) $(OBSTACK_H) output.h \
+   $(HASHTAB_H)
 cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) output.h \
    coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H)