Re: commutative asm operands

[Roman Zippel <zippel at linux-m68k dot org>]

Hi,

Alan Modra wrote:

> Hey, so have I!  I'd better post it..
> 
>         * recog.c (constrain_operands): Handle commutative operands.

What exactly does this patch fix?
What is the assembly output for this test case (register names might
need a change):

int f()
{
        register int a asm("%ebx");
        register int b asm("%ecx");
        register int c asm("%edx");
        register int d asm("%edi");

        asm volatile ("addc %0, %2, %3\n\tadde %1, %4, %5"
                : "=r" (a), "=r" (b)
                : "%0" (a), "r" (c), "%1" (b), "r" (d));
        asm volatile ("addc %0, %2, %3\n\tadde %1, %4, %5"
                : "=r" (a), "=r" (b)
                : "%0" (c), "r" (a), "%1" (d), "r" (b));
}

I attached my patch, it still applies, but it's untested for a while.
That patch really tries to find the best combination of commutative
operands.

bye, Roman
Index: gcc/reload.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/reload.c,v
retrieving revision 1.180
diff -u -p -r1.180 reload.c
--- reload.c	2002/03/10 23:51:08	1.180
+++ reload.c	2002/04/03 23:21:30
@@ -2449,6 +2449,7 @@ find_reloads (insn, replace, ind_levels,
   char this_alternative_earlyclobber[MAX_RECOG_OPERANDS];
   int this_alternative_matches[MAX_RECOG_OPERANDS];
   int swapped;
+  int n_permutation;
   int goal_alternative[MAX_RECOG_OPERANDS];
   int this_alternative_number;
   int goal_alternative_number = 0;
@@ -2461,7 +2462,8 @@ find_reloads (insn, replace, ind_levels,
   char goal_alternative_earlyclobber[MAX_RECOG_OPERANDS];
   int goal_alternative_swapped;
   int best;
-  int commutative;
+  int commutative[MAX_RECOG_OPERANDS];
+  int commutative_op[MAX_RECOG_OPERANDS/2];
   char operands_match[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
   rtx substed_operand[MAX_RECOG_OPERANDS];
   rtx body = PATTERN (insn);
@@ -2527,14 +2529,14 @@ find_reloads (insn, replace, ind_levels,
 	  noperands * sizeof (enum machine_mode));
   memcpy (constraints, recog_data.constraints, noperands * sizeof (char *));
 
-  commutative = -1;
-
   /* If we will need to know, later, whether some pair of operands
      are the same, we must compare them now and save the result.
      Reloading the base and index registers will clobber them
      and afterward they will fail to match.  */
-
   for (i = 0; i < noperands; i++)
+    commutative[i] = i;
+
+  for (i = 0, j = 0; i < noperands; i++)
     {
       char *p;
       int c;
@@ -2555,11 +2557,14 @@ find_reloads (insn, replace, ind_levels,
 	    modified[i] = RELOAD_READ_WRITE;
 	  else if (c == '%')
 	    {
-	      /* The last operand should not be marked commutative.  */
-	      if (i == noperands - 1)
+	      /* The last operand and two consecutive operands should not be
+	          marked commutative.  */
+	      if (i == noperands - 1 || commutative[i] != i)
 		abort ();
 
-	      commutative = i;
+	      commutative_op[j++] = i;
+	      commutative[i] = i + 1;
+	      commutative[i + 1] = i;
 	    }
 	  else if (ISDIGIT (c))
 	    {
@@ -2573,32 +2578,31 @@ find_reloads (insn, replace, ind_levels,
 	      if (c == i)
 		abort ();
 
+	      if (commutative[i] != i)
+		operands_match[c][commutative[i]]
+		  = operands_match_p (recog_data.operand[c],
+				      recog_data.operand[commutative[i]]);
+
 	      /* If C can be commuted with C+1, and C might need to match I,
 		 then C+1 might also need to match I.  */
-	      if (commutative >= 0)
-		{
-		  if (c == commutative || c == commutative + 1)
-		    {
-		      int other = c + (c == commutative ? 1 : -1);
-		      operands_match[other][i]
-			= operands_match_p (recog_data.operand[other],
-					    recog_data.operand[i]);
-		    }
-		  if (i == commutative || i == commutative + 1)
-		    {
-		      int other = i + (i == commutative ? 1 : -1);
-		      operands_match[c][other]
-			= operands_match_p (recog_data.operand[c],
-					    recog_data.operand[other]);
-		    }
-		  /* Note that C is supposed to be less than I.
-		     No need to consider altering both C and I because in
-		     that case we would alter one into the other.  */
-		}
+	      if (commutative[c] != c)
+		operands_match[commutative[c]][i]
+		  = operands_match_p (recog_data.operand[commutative[c]],
+				      recog_data.operand[i]);
+	      if (commutative[i] != i && commutative[c] != c)
+		operands_match[commutative[c]][commutative[i]]
+		  = operands_match_p (recog_data.operand[commutative[c]],
+				      recog_data.operand[commutative[i]]);
 	    }
 	}
     }
 
+  /* # of loops needed to test all possible combinations of commutable operands.
+     for a single loop, keep n_permutation 0 to keep the test below easier.  */
+  n_permutation = 0;
+  if (j)
+    n_permutation = 1 << j;
+
   /* Examine each operand that is a memory reference or memory address
      and reload parts of the addresses into index registers.
      Also here any references to pseudo regs that didn't get hard regs
@@ -2755,6 +2759,8 @@ find_reloads (insn, replace, ind_levels,
 
   swapped = 0;
   goal_alternative_swapped = 0;
+  for (i = 0; i < noperands; i++)
+    commutative[i] = i;
  try_swapped:
 
   /* The constraints are made of several alternatives.
@@ -2926,13 +2932,7 @@ find_reloads (insn, replace, ind_levels,
 	  while (*p && (c = *p++) != ',')
 	    switch (c)
 	      {
-	      case '=':  case '+':  case '*':
-		break;
-
-	      case '%':
-		/* The last operand should not be marked commutative.  */
-		if (i != noperands - 1)
-		  commutative = i;
+	      case '=':  case '+':  case '*': case '%':
 		break;
 
 	      case '?':
@@ -2962,19 +2962,10 @@ find_reloads (insn, replace, ind_levels,
 		   only a single reload insn will be needed to make
 		   the two operands win.  As a result, this alternative
 		   may be rejected when it is actually desirable.)  */
-		if ((swapped && (c != commutative || i != commutative + 1))
-		    /* If we are matching as if two operands were swapped,
-		       also pretend that operands_match had been computed
-		       with swapped.
-		       But if I is the second of those and C is the first,
-		       don't exchange them, because operands_match is valid
-		       only on one side of its diagonal.  */
-		    ? (operands_match
-		       [(c == commutative || c == commutative + 1)
-		       ? 2 * commutative + 1 - c : c]
-		       [(i == commutative || i == commutative + 1)
-		       ? 2 * commutative + 1 - i : i])
-		    : operands_match[c][i])
+		/* If we are matching as if two operands were swapped,
+		   also pretend that operands_match had been computed
+		   with swapped. */
+		if (operands_match[commutative[c]][commutative[i]])
 		  {
 		    /* If we are matching a non-offsettable address where an
 		       offsettable address was expected, then we must reject
@@ -3431,11 +3422,22 @@ find_reloads (insn, replace, ind_levels,
       if (losers == 0)
 	{
 	  /* Unswap these so that they are never swapped at `finish'.  */
-	  if (commutative >= 0)
+	  if (swapped)
 	    {
-	      recog_data.operand[commutative] = substed_operand[commutative];
-	      recog_data.operand[commutative + 1]
-		= substed_operand[commutative + 1];
+	      int s = swapped;
+	      s ^= s >> 1;
+
+	      for (i = 0; s; i++, s >>= 1)
+		{
+		  register int c;
+
+		  if (!(s & 1))
+		    continue;
+		  c = commutative_op[i];
+
+		  recog_data.operand[c] = substed_operand[c];
+		  recog_data.operand[c + 1] = substed_operand[c + 1];
+		}
 	    }
 	  for (i = 0; i < noperands; i++)
 	    {
@@ -3485,52 +3487,50 @@ find_reloads (insn, replace, ind_levels,
      then we need to try each alternative twice,
      the second time matching those two operands
      as if we had exchanged them.
-     To do this, really exchange them in operands.
+     To do this, really exchange them in operands.  */
 
-     If we have just tried the alternatives the second time,
-     return operands to normal and drop through.  */
-
-  if (commutative >= 0)
+  if (++swapped <= n_permutation)
     {
-      swapped = !swapped;
-      if (swapped)
+      int s, t;
+      rtx x;
+
+      /* In every loop we just swap a single pair of operands, so that in the
+	 last loop we only need to swap a single pair back to return operands
+	 to normal and drop through.  */
+      s = swapped - 1;
+      if (swapped < n_permutation)
+	s ^= swapped;
+      s ^= s >> 1;
+
+      for (i = 0; s; i++, s >>= 1)
+	if (s & 1)
+	  break;
+      i = commutative_op[i];
+
+      t = commutative[i];
+      commutative[i] = commutative[i + 1];
+      commutative[i + 1] = t;
+
+      x = recog_data.operand[i];
+      recog_data.operand[i] = recog_data.operand[i + 1];
+      recog_data.operand[i + 1] = x;
+
+      if (swapped < n_permutation)
 	{
 	  enum reg_class tclass;
-	  int t;
 
-	  recog_data.operand[commutative] = substed_operand[commutative + 1];
-	  recog_data.operand[commutative + 1] = substed_operand[commutative];
-	  /* Swap the duplicates too.  */
-	  for (i = 0; i < recog_data.n_dups; i++)
-	    if (recog_data.dup_num[i] == commutative
-		|| recog_data.dup_num[i] == commutative + 1)
-	      *recog_data.dup_loc[i]
-		 = recog_data.operand[(int) recog_data.dup_num[i]];
-
-	  tclass = preferred_class[commutative];
-	  preferred_class[commutative] = preferred_class[commutative + 1];
-	  preferred_class[commutative + 1] = tclass;
-
-	  t = pref_or_nothing[commutative];
-	  pref_or_nothing[commutative] = pref_or_nothing[commutative + 1];
-	  pref_or_nothing[commutative + 1] = t;
+	  tclass = preferred_class[i];
+	  preferred_class[i] = preferred_class[i + 1];
+	  preferred_class[i + 1] = tclass;
+
+	  t = pref_or_nothing[i];
+	  pref_or_nothing[i] = pref_or_nothing[i + 1];
+	  pref_or_nothing[i + 1] = t;
 
 	  memcpy (constraints, recog_data.constraints,
 		  noperands * sizeof (char *));
 	  goto try_swapped;
 	}
-      else
-	{
-	  recog_data.operand[commutative] = substed_operand[commutative];
-	  recog_data.operand[commutative + 1]
-	    = substed_operand[commutative + 1];
-	  /* Unswap the duplicates too.  */
-	  for (i = 0; i < recog_data.n_dups; i++)
-	    if (recog_data.dup_num[i] == commutative
-		|| recog_data.dup_num[i] == commutative + 1)
-	      *recog_data.dup_loc[i]
-		 = recog_data.operand[(int) recog_data.dup_num[i]];
-	}
     }
 
   /* The operands don't meet the constraints.
@@ -3577,25 +3577,44 @@ find_reloads (insn, replace, ind_levels,
 
   if (goal_alternative_swapped)
     {
-      rtx tem;
+      int s = goal_alternative_swapped;
+      s ^= s >> 1;
 
-      tem = substed_operand[commutative];
-      substed_operand[commutative] = substed_operand[commutative + 1];
-      substed_operand[commutative + 1] = tem;
-      tem = recog_data.operand[commutative];
-      recog_data.operand[commutative] = recog_data.operand[commutative + 1];
-      recog_data.operand[commutative + 1] = tem;
-      tem = *recog_data.operand_loc[commutative];
-      *recog_data.operand_loc[commutative]
-	= *recog_data.operand_loc[commutative + 1];
-      *recog_data.operand_loc[commutative + 1] = tem;
-
-      for (i = 0; i < n_reloads; i++)
+      for (i = 0; s; i++, s >>= 1)
 	{
-	  if (rld[i].opnum == commutative)
-	    rld[i].opnum = commutative + 1;
-	  else if (rld[i].opnum == commutative + 1)
-	    rld[i].opnum = commutative;
+	  int c;
+	  rtx tem;
+
+	  if (!(s & 1))
+	    continue;
+	  c = commutative_op[i];
+
+	  tem = substed_operand[c];
+	  substed_operand[c] = substed_operand[c + 1];
+	  substed_operand[c + 1] = tem;
+
+	  tem = recog_data.operand[c];
+	  recog_data.operand[c] = recog_data.operand[c + 1];
+	  recog_data.operand[c + 1] = tem;
+
+	  tem = *recog_data.operand_loc[c];
+	  *recog_data.operand_loc[c] = *recog_data.operand_loc[c + 1];
+	  *recog_data.operand_loc[c + 1] = tem;
+
+	  /* Swap the duplicates too.  */
+	  for (j = 0; j < recog_data.n_dups; j++)
+	    if (recog_data.dup_num[j] == c
+		|| recog_data.dup_num[j] == c + 1)
+	      *recog_data.dup_loc[j]
+		= recog_data.operand[(int) recog_data.dup_num[j]];
+
+	  for (j = 0; j < n_reloads; j++)
+	    {
+	      if (rld[j].opnum == c)
+		rld[j].opnum = c + 1;
+	      else if (rld[j].opnum == c + 1)
+		rld[j].opnum = c;
+	    }
 	}
     }