Index: gcc/recog.h
===================================================================
--- gcc/recog.h	2011-03-31 10:57:29.000000000 +0100
+++ gcc/recog.h	2011-03-31 11:01:19.000000000 +0100
@@ -272,6 +272,8 @@ struct insn_operand_data
   const char is_operator;
 
   const char eliminable;
+
+  const char allows_mem;
 };
 
 /* Legal values for insn_data.output_format.  Indicate what type of data
Index: gcc/genoutput.c
===================================================================
--- gcc/genoutput.c	2011-03-31 10:57:29.000000000 +0100
+++ gcc/genoutput.c	2011-03-31 11:01:19.000000000 +0100
@@ -66,6 +66,8 @@ Software Foundation; either version 3, o
      MATCH_OPERAND; it is zero for operands that should not be changed during
      register elimination such as MATCH_OPERATORs.
 
+     g. `allows_mem', is true for operands that accept MEM rtxes.
+
   The code number of an insn is simply its position in the machine
   description; code numbers are assigned sequentially to entries in
   the description, starting with code number 0.
@@ -255,6 +257,8 @@ output_operand_data (void)
 
   for (d = odata; d; d = d->next)
     {
+      struct pred_data *pred;
+
       printf ("  {\n");
 
       printf ("    %s,\n",
@@ -268,7 +272,12 @@ output_operand_data (void)
 
       printf ("    %d,\n", d->constraint == NULL ? 1 : 0);
 
-      printf ("    %d\n", d->eliminable);
+      printf ("    %d,\n", d->eliminable);
+
+      pred = NULL;
+      if (d->predicate)
+	pred = lookup_predicate (d->predicate);
+      printf ("    %d\n", pred && pred->codes[MEM]);
 
       printf("  },\n");
     }
Index: gcc/optabs.c
===================================================================
--- gcc/optabs.c	2011-03-31 10:57:29.000000000 +0100
+++ gcc/optabs.c	2011-03-31 11:01:19.000000000 +0100
@@ -7001,6 +7001,36 @@ insn_operand_matches (enum insn_code ico
 	      (operand, insn_data[(int) icode].operand[opno].mode)));
 }
 
+/* Like maybe_legitimize_operand, but do not change the code of the
+   current rtx value.  */
+
+static bool
+maybe_legitimize_operand_same_code (enum insn_code icode, unsigned int opno,
+				    struct expand_operand *op)
+{
+  /* See if the operand matches in its current form.  */
+  if (insn_operand_matches (icode, opno, op->value))
+    return true;
+
+  /* If the operand is a memory, try forcing the address into a register.  */
+  if (MEM_P (op->value) && insn_data[(int) icode].operand[opno].allows_mem)
+    {
+      rtx addr, mem, last;
+
+      last = get_last_insn ();
+      addr = force_reg (Pmode, XEXP (op->value, 0));
+      mem = replace_equiv_address (op->value, addr);
+      if (insn_operand_matches (icode, opno, mem))
+	{
+	  op->value = mem;
+	  return true;
+	}
+      delete_insns_since (last);
+    }
+
+  return false;
+}
+
 /* Try to make OP match operand OPNO of instruction ICODE.  Return true
    on success, storing the new operand value back in OP.  */
 
@@ -7013,31 +7043,35 @@ maybe_legitimize_operand (enum insn_code
 
   old_volatile_ok = volatile_ok;
   mode = op->mode;
-  result = false;
   switch (op->type)
     {
     case EXPAND_FIXED:
       volatile_ok = true;
-      break;
+      result = maybe_legitimize_operand_same_code (icode, opno, op);
+      volatile_ok = old_volatile_ok;
+      return result;
 
     case EXPAND_OUTPUT:
       gcc_assert (mode != VOIDmode);
-      if (!op->value
-	  || op->value == const0_rtx
-	  || GET_MODE (op->value) != mode
-	  || !insn_operand_matches (icode, opno, op->value))
-	op->value = gen_reg_rtx (mode);
-      break;
+      if (op->value
+	  && op->value != const0_rtx
+	  && GET_MODE (op->value) == mode
+	  && maybe_legitimize_operand_same_code (icode, opno, op))
+	return true;
+
+      op->value = gen_reg_rtx (mode);
+      return insn_operand_matches (icode, opno, op->value);
 
     case EXPAND_INPUT:
     input:
       gcc_assert (mode != VOIDmode);
       gcc_assert (GET_MODE (op->value) == VOIDmode
 		  || GET_MODE (op->value) == mode);
-      result = insn_operand_matches (icode, opno, op->value);
-      if (!result)
-	op->value = copy_to_mode_reg (mode, op->value);
-      break;
+      if (maybe_legitimize_operand_same_code (icode, opno, op))
+	return true;
+
+      op->value = copy_to_mode_reg (mode, op->value);
+      return insn_operand_matches (icode, opno, op->value);
 
     case EXPAND_CONVERT_TO:
       gcc_assert (mode != VOIDmode);
@@ -7068,12 +7102,9 @@ maybe_legitimize_operand (enum insn_code
       mode = insn_data[(int) icode].operand[opno].mode;
       if (mode != VOIDmode && const_int_operand (op->value, mode))
 	goto input;
-      break;
+      return insn_operand_matches (icode, opno, op->value);
     }
-  if (!result)
-    result = insn_operand_matches (icode, opno, op->value);
-  volatile_ok = old_volatile_ok;
-  return result;
+  gcc_unreachable ();
 }
 
 /* Make OP describe an input operand that should have the same value
