1999-01-13 Vladimir N. Makarov <vmakarov@cygnus.com>

	* config/i960/i960.c (i960_function_prologue): New code (optimal
	solution) for saving global registers in local registers.
	(form_reg_groups, reg_group_compare, split_reg_group): New
	functions used by the code.
	(reg_group): New structure definition for the new code.


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

1 files changed, 129 insertions, 50 deletions

diff --git a/gcc/config/i960/i960.c b/gcc/config/i960/i960.c
index 9fa8889c301..3d62c3cc611 100644
--- a/gcc/config/i960/i960.c
+++ b/gcc/config/i960/i960.c
@@ -1184,6 +1184,95 @@ compute_frame_size (size)
   return actual_fsize;
 }
 
+/* Here register group is range of registers which can be moved by
+   one i960 instruction. */
+
+struct reg_group
+{
+  char start_reg;
+  char length;
+};
+
+/* The following functions forms the biggest as possible register
+   groups with registers in STATE.  REGS contain states of the
+   registers in range [start, finish_reg).  The function returns the
+   number of groups formed. */
+static int
+i960_form_reg_groups (start_reg, finish_reg, regs, state, reg_groups)
+     int start_reg;
+     int finish_reg;
+     int *regs;
+     int state;
+     struct reg_group *reg_groups;
+{
+  int i;
+  int nw = 0;
+
+  for (i = start_reg; i < finish_reg; )
+    {
+      if (regs [i] != state)
+	{
+	  i++;
+	  continue;
+	}
+      else if (i % 2 != 0 || regs [i + 1] != state)
+	reg_groups [nw].length = 1;
+      else if (i % 4 != 0 || regs [i + 2] != state)
+	reg_groups [nw].length = 2;
+      else if (regs [i + 3] != state)
+	reg_groups [nw].length = 3;
+      else
+	reg_groups [nw].length = 4;
+      reg_groups [nw].start_reg = i;
+      i += reg_groups [nw].length;
+      nw++;
+    }
+  return nw;
+}
+
+/* We sort register winodws in descending order by length. */
+static int
+i960_reg_group_compare (group1, group2)
+     void *group1;
+     void *group2;
+{
+  struct reg_group *w1 = group1;
+  struct reg_group *w2 = group2;
+
+  if (w1->length > w2->length)
+    return -1;
+  else if (w1->length < w2->length)
+    return 1;
+  else
+    return 0;
+}
+
+/* Split the first register group in REG_GROUPS on subgroups one of
+   which will contain SUBGROUP_LENGTH registers.  The function
+   returns new number of winodws. */
+static int
+i960_split_reg_group (reg_groups, nw, subgroup_length)
+     struct reg_group *reg_groups;
+     int nw;
+     int subgroup_length;
+{
+  if (subgroup_length < reg_groups->length - subgroup_length)
+    /* This guarantees correct alignments of the two subgroups for
+       i960 (see spliting for the group length 2, 3, 4).  More
+       generalized algorithm would require splitting the group more
+       two subgroups. */
+    subgroup_length = reg_groups->length - subgroup_length;
+  /* More generalized algorithm would require to try merging
+     subgroups here.  But in case i960 it always results in failure
+     because of register group alignment. */
+  reg_groups[nw].length = reg_groups->length - subgroup_length;
+  reg_groups[nw].start_reg = reg_groups->start_reg + subgroup_length;
+  nw++;
+  reg_groups->length = subgroup_length;
+  qsort (reg_groups, nw, sizeof (struct reg_group), i960_reg_group_compare);
+  return nw;
+}
+
 /* Output code for the function prologue.  */
 
 void
@@ -1195,10 +1284,17 @@ i960_function_prologue (file, size)
   int n_iregs = 0;
   int rsize = 0;
   int actual_fsize, offset;
+  int gnw, lnw;
+  struct reg_group *g, *l;
   char tmpstr[1000];
   /* -1 if reg must be saved on proc entry, 0 if available, 1 if saved
      somewhere.  */
   int regs[FIRST_PSEUDO_REGISTER];
+  /* All global registers (which must be saved) divided by groups. */
+  struct reg_group global_reg_groups [16];
+  /* All local registers (which are available) divided by groups. */
+  struct reg_group local_reg_groups [16];
+
 
   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
     if (regs_ever_live[i]
@@ -1226,62 +1322,43 @@ i960_function_prologue (file, size)
 	regs[i] = -1;
     }
 
-  /* First look for local registers to save globals in.  */
-  for (i = 0; i < 16; i++)
+  gnw = i960_form_reg_groups (0, 16, regs, -1, global_reg_groups);
+  lnw = i960_form_reg_groups (19, 32, regs, 0, local_reg_groups);
+  qsort (global_reg_groups, gnw, sizeof (struct reg_group),
+	 i960_reg_group_compare);
+  qsort (local_reg_groups, lnw, sizeof (struct reg_group),
+	 i960_reg_group_compare);
+  for (g = global_reg_groups, l = local_reg_groups; lnw != 0 && gnw != 0;)
     {
-      if (regs[i] == 0)
-	continue;
-
-      /* Start at r4, not r3.  */
-      for (j = 20; j < 32; j++)
+      if (g->length == l->length)
 	{
-	  if (regs[j] != 0)
-	    continue;
-
-	  regs[i] = 1;
-	  regs[j] = -1;
-	  regs_ever_live[j] = 1;
-	  nr = 1;
-	  if (i <= 14 && i % 2 == 0 && j <= 30 && j % 2 == 0
-	      && regs[i+1] != 0 && regs[j+1] == 0)
-	    {
-	      nr = 2;
-	      regs[i+1] = 1;
-	      regs[j+1] = -1;
-	      regs_ever_live[j+1] = 1;
-	    }
-	  if (nr == 2 && i <= 12 && i % 4 == 0 && j <= 28 && j % 4 == 0
-	      && regs[i+2] != 0 && regs[j+2] == 0)
-	    {
-	      nr = 3;
-	      regs[i+2] = 1;
-	      regs[j+2] = -1;
-	      regs_ever_live[j+2] = 1;
-	    }
-	  if (nr == 3 && regs[i+3] != 0 && regs[j+3] == 0)
-	    {
-	      nr = 4;
-	      regs[i+3] = 1;
-	      regs[j+3] = -1;
-	      regs_ever_live[j+3] = 1;
-	    }
-
 	  fprintf (file, "\tmov%s	%s,%s\n",
-		   ((nr == 4) ? "q" :
-		    (nr == 3) ? "t" :
-		    (nr == 2) ? "l" : ""),
-		   reg_names[i], reg_names[j]);
+		   ((g->length == 4) ? "q" :
+		    (g->length == 3) ? "t" :
+		    (g->length == 2) ? "l" : ""),
+		   reg_names[g->start_reg], reg_names[l->start_reg]);
 	  sprintf (tmpstr, "\tmov%s	%s,%s\n",
-		   ((nr == 4) ? "q" :
-		    (nr == 3) ? "t" :
-		    (nr == 2) ? "l" : ""),
-		   reg_names[j], reg_names[i]);
+		   ((g->length == 4) ? "q" :
+		    (g->length == 3) ? "t" :
+		    (g->length == 2) ? "l" : ""),
+		   reg_names[l->start_reg], reg_names[g->start_reg]);
 	  strcat (epilogue_string, tmpstr);
-
-	  n_iregs -= nr;
-	  i += nr-1;
-	  break;
+	  n_iregs -= g->length;
+	  for (i = 0; i < g->length; i++)
+	    {
+	      regs [i + g->start_reg] = 1;
+	      regs [i + l->start_reg] = -1;
+	      regs_ever_live [i + l->start_reg] = 1;
+	    }
+	  g++;
+	  l++;
+	  gnw--;
+	  lnw--;
 	}
+      else if (g->length > l->length)
+	gnw = i960_split_reg_group (g, gnw, l->length);
+      else
+	lnw = i960_split_reg_group (l, lnw, g->length);
     }
 
   /* N_iregs is now the number of global registers that haven't been saved
@@ -1314,6 +1391,8 @@ i960_function_prologue (file, size)
      into account, but store them before the argument block area.  */
   offset = 64 + actual_fsize - compute_frame_size (0) - rsize;
   /* Save registers on stack if needed.  */
+  /* ??? Is it worth to use the same algorithm as one for saving
+     global registers in local registers? */
   for (i = 0, j = n_iregs; j > 0 && i < 16; i++)
     {
       if (regs[i] != -1)