re PR middle-end/17503 (quadratic behaviour in invalid_mode_change_p)

        PR rtl-opt/17503
        * regclass.c (subregs_of_mode): Turn into an htab.  Make static.
        (som_hash, som_eq): New.
        (init_subregs_of_mode, record_subregs_of_mode): New.
        (cannot_change_mode_set_regs): Rewrite for htab implementation.
        (invalid_mode_change_p): Likewise.
        * combine.c (gen_lowpart_for_combine): Use record_subregs_of_mode.
        * flow.c (mark_used_regs): Likewise.
        (life_analysis): Use init_subregs_of_mode.
        * regs.h (subregs_of_mode): Remove.
        * rtl.h (init_subregs_of_mode, record_subregs_of_mode): Declare.

From-SVN: r88067

1 files changed, 97 insertions, 30 deletions

diff --git a/gcc/regclass.c b/gcc/regclass.c
index 1d33a0977b2..6d1d975f093 100644
--- a/gcc/regclass.c
+++ b/gcc/regclass.c
@@ -45,6 +45,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "output.h"
 #include "ggc.h"
 #include "timevar.h"
+#include "hashtab.h"
 
 static void init_reg_sets_1 (void);
 static void init_reg_autoinc (void);
@@ -235,12 +236,6 @@ static char *in_inc_dec;
 
 #endif /* FORBIDDEN_INC_DEC_CLASSES */
 
-#ifdef CANNOT_CHANGE_MODE_CLASS
-/* All registers that have been subreged.  Indexed by regno * MAX_MACHINE_MODE
-   + mode.  */
-bitmap_head subregs_of_mode;
-#endif
-
 /* Sample MEM values for use by memory_move_secondary_cost.  */
 
 static GTY(()) rtx top_of_stack[MAX_MACHINE_MODE];
@@ -2594,6 +2589,70 @@ regset_release_memory (void)
 }
 
 #ifdef CANNOT_CHANGE_MODE_CLASS
+
+struct subregs_of_mode_node
+{
+  unsigned int block;
+  unsigned char modes[MAX_MACHINE_MODE];
+};
+
+static htab_t subregs_of_mode;
+
+static hashval_t
+som_hash (const void *x)
+{
+  const struct subregs_of_mode_node *a = x;
+  return a->block;
+}
+
+static int
+som_eq (const void *x, const void *y)
+{
+  const struct subregs_of_mode_node *a = x;
+  const struct subregs_of_mode_node *b = y;
+  return a->block == b->block;
+}
+
+void
+init_subregs_of_mode (void)
+{
+  if (subregs_of_mode)
+    htab_empty (subregs_of_mode);
+  else
+    subregs_of_mode = htab_create (100, som_hash, som_eq, free);
+}
+
+void
+record_subregs_of_mode (rtx subreg)
+{
+  struct subregs_of_mode_node dummy, *node;
+  enum machine_mode mode;
+  unsigned int regno;
+  void **slot;
+
+  if (!REG_P (SUBREG_REG (subreg)))
+    return;
+
+  regno = REGNO (SUBREG_REG (subreg));
+  mode = GET_MODE (subreg);
+
+  if (regno < FIRST_PSEUDO_REGISTER)
+    return;
+
+  dummy.block = regno & -8;
+  slot = htab_find_slot_with_hash (subregs_of_mode, &dummy,
+				   dummy.block, INSERT);
+  node = *slot;
+  if (node == NULL)
+    {
+      node = xcalloc (1, sizeof (*node));
+      node->block = regno & -8;
+      *slot = node;
+    }
+
+  node->modes[mode] |= 1 << (regno & 7);
+}
+
 /* Set bits in *USED which correspond to registers which can't change
    their mode from FROM to any mode in which REGNO was encountered.  */
 
@@ -2601,19 +2660,23 @@ void
 cannot_change_mode_set_regs (HARD_REG_SET *used, enum machine_mode from,
 			     unsigned int regno)
 {
+  struct subregs_of_mode_node dummy, *node;
   enum machine_mode to;
-  int n, i;
-  int start = regno * MAX_MACHINE_MODE;
+  unsigned char mask;
+  unsigned int i;
 
-  EXECUTE_IF_SET_IN_BITMAP (&subregs_of_mode, start, n,
-    if (n >= MAX_MACHINE_MODE + start)
-      return;
-    to = n - start;
-    for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
-      if (! TEST_HARD_REG_BIT (*used, i)
-	  && REG_CANNOT_CHANGE_MODE_P (i, from, to))
-	SET_HARD_REG_BIT (*used, i);
-  );
+  dummy.block = regno & -8;
+  node = htab_find_with_hash (subregs_of_mode, &dummy, dummy.block);
+  if (node == NULL)
+    return;
+
+  mask = 1 << (regno & 7);
+  for (to = VOIDmode; to < NUM_MACHINE_MODES; to++)
+    if (node->modes[to] & mask)
+      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+	if (!TEST_HARD_REG_BIT (*used, i)
+	    && REG_CANNOT_CHANGE_MODE_P (i, from, to))
+	  SET_HARD_REG_BIT (*used, i);
 }
 
 /* Return 1 if REGNO has had an invalid mode change in CLASS from FROM
@@ -2621,20 +2684,24 @@ cannot_change_mode_set_regs (HARD_REG_SET *used, enum machine_mode from,
 
 bool
 invalid_mode_change_p (unsigned int regno, enum reg_class class,
-		       enum machine_mode from_mode)
+		       enum machine_mode from)
 {
-  enum machine_mode to_mode;
-  int n;
-  int start = regno * MAX_MACHINE_MODE;
-
-  EXECUTE_IF_SET_IN_BITMAP (&subregs_of_mode, start, n,
-    if (n >= MAX_MACHINE_MODE + start)
-      return 0;
-    to_mode = n - start;
-    if (CANNOT_CHANGE_MODE_CLASS (from_mode, to_mode, class))
-      return 1;
-  );
-  return 0;
+  struct subregs_of_mode_node dummy, *node;
+  enum machine_mode to;
+  unsigned char mask;
+
+  dummy.block = regno & -8;
+  node = htab_find_with_hash (subregs_of_mode, &dummy, dummy.block);
+  if (node == NULL)
+    return false;
+
+  mask = 1 << (regno & 7);
+  for (to = VOIDmode; to < NUM_MACHINE_MODES; to++)
+    if (node->modes[to] & mask)
+      if (CANNOT_CHANGE_MODE_CLASS (from, to, class))
+	return true;
+
+  return false;
 }
 #endif /* CANNOT_CHANGE_MODE_CLASS */