* ra-conflict.c: Include "sparseset.h".

	(conflicts): Change to HOST_WIDEST_FAST_INT.
	(allocnos_live): Redefine variable as a sparseset.
	(SET_ALLOCNO_LIVE, CLEAR_ALLOCNO_LIVE, GET_ALLOCNO_LIVE): Delete macros.
	(allocno_row_words): Removed global variable.
	(partial_bitnum, max_bitnum, adjacency_pool, adjacency): New variables.
	(CONFLICT_BITNUM, CONFLICT_BITNUM_FAST): New defines.
	(conflict_p, set_conflict_p, set_conflicts_p): New functions.
	(record_one_conflict_between_regnos): Cache allocno values and reuse.
	Use set_conflict_p.
	(record_one_conflict): Update uses of allocnos_live to use
	the sparseset routines.  Use set_conflicts_p.
	(mark_reg_store): Likewise.
	(set_reg_in_live): Likewise.
	(global_conflicts): Update uses of allocnos_live.
	Use the new adjacency list to visit an allocno's neighbors
	rather than iterating over all possible allocnos.
	Call set_conflicts_p to setup conflicts rather than adding
	them manually.
	* global.c: Comments updated.  
	(CONFLICTP): Delete define.
	(regno_compare): New function.  Add prototype.
	(global_alloc): Sort the allocno to regno mapping according to
	which basic blocks the regnos are referenced in.  Modify the
	conflict bit matrix to a compressed triangular bitmatrix.
	Only allocate the conflict bit matrix and adjacency lists if
	we are actually going to allocate something.
	(expand_preferences): Use conflict_p.  Update uses of allocnos_live.
	(prune_preferences): Use the FOR_EACH_CONFLICT macro to visit an
	allocno's neighbors rather than iterating over all possible allocnos.
	(mirror_conflicts): Removed function.
	(dump_conflicts): Iterate over regnos rather than allocnos so
	that all dump output will be sorted by regno number.
	Use the FOR_EACH_CONFLICT macro.
	* ra.h: Comments updated.
	(conflicts): Update prototype to HOST_WIDEST_FAST_INT.
	(partial_bitnum, max_bitnum, adjacency, adjacency_pool): Add prototypes.
	(ADJACENCY_VEC_LENGTH, FOR_EACH_CONFLICT): New defines.
	(adjacency_list_d, adjacency_iterator_d): New types.
	(add_neighbor, adjacency_iter_init, adjacency_iter_done,
	adjacency_iter_next, regno_basic_block): New static inline functions.
	(EXECUTE_IF_SET_IN_ALLOCNO_SET): Removed define.
	(conflict_p): Add function prototype.
	* sparseset.h, sparseset.c: New files.
	* Makefile.in (OBJS-common): Add sparseset.o.
	(sparseset.o): New rule.


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

1 files changed, 122 insertions, 32 deletions

diff --git a/gcc/ra.h b/gcc/ra.h
index 52a1cc28beb..bd4af6d2daf 100644
--- a/gcc/ra.h
+++ b/gcc/ra.h
@@ -85,49 +85,139 @@ extern struct allocno *allocno;
 
 extern int max_allocno;
 
-/* max_allocno by max_allocno array of bits, recording whether two
-   allocno's conflict (can't go in the same hardware register).
+/* max_allocno by max_allocno compressed triangular bit matrix,
+   recording whether two allocnos conflict (can't go in the same
+   hardware register).  */
 
-   `conflicts' is symmetric after the call to mirror_conflicts.  */
-
-extern HOST_WIDE_INT *conflicts;
-
-/* Number of ints required to hold max_allocno bits.
-   This is the length of a row in `conflicts'.  */
-
-extern int allocno_row_words;
+extern HOST_WIDEST_FAST_INT *conflicts;
 
 /* Indexed by (pseudo) reg number, gives the allocno, or -1
    for pseudo registers which are not to be allocated.  */
 
 extern int *reg_allocno;
 
+/* Precalculated partial bit number in the compressed triangular bit matrix.
+   For two allocnos, the final bit number is: partial_bitnum[LOW] + HIGH.  */
+
+extern int *partial_bitnum;
+
+/* Size in bits of the compressed triangular bit matrix.  */
+
+extern int max_bitnum;
+
+/* The pool to allocate the adjacency list elements from.  */
+
+extern alloc_pool adjacency_pool;
+
+/* The maximum number of neighbors stored in the neighbors vector before
+   we have to chain in another vector.  */
+
+#define ADJACENCY_VEC_LENGTH 30
+
+/* Conflict graph adjacency list.  */
+
+typedef struct adjacency_list_d
+{
+  int neighbors[ADJACENCY_VEC_LENGTH];
+  unsigned int index;
+  struct adjacency_list_d *next;
+} adjacency_t;
+
+extern adjacency_t **adjacency;
+
+/* Add NEIGHBOR to ALLOC_NO's adjacency list.  It is assumed the caller
+   has already determined that NEIGHBOR is not already neighbor by
+   checking the conflict bit matrix.  */
+
+static inline void
+add_neighbor (int alloc_no, int neighbor)
+{
+  adjacency_t *adjlist = adjacency[alloc_no];
+
+  if (adjlist == NULL || adjlist->index == ADJACENCY_VEC_LENGTH)
+    {
+      adjacency_t *new = pool_alloc (adjacency_pool);
+      new->index = 0;
+      new->next = adjlist;
+      adjlist = new;
+      adjacency[alloc_no] = adjlist;
+    }
+
+  adjlist->neighbors[adjlist->index++] = neighbor;
+}
+
+/* Iterator for adjacency lists.  */
+
+typedef struct adjacency_iterator_d
+{
+  adjacency_t *vec;
+  unsigned int idx;
+} adjacency_iter;
+
+/* Initialize a single adjacency list iterator.  */
+
+static inline int
+adjacency_iter_init (adjacency_iter *ai, int allocno1)
+{
+  ai->vec = adjacency[allocno1];
+  ai->idx = 0;
+  return ai->vec != NULL;
+}
+
+/* Test whether we have visited all of the neighbors.  */
+
+static inline int
+adjacency_iter_done (adjacency_iter *ai)
+{
+  return ai->idx > ai->vec->index;
+}
+
+/* Advance to the next neighbor in AI.  */
+
+static inline int
+adjacency_iter_next (adjacency_iter *ai)
+{
+  unsigned int idx = ai->idx;
+  int neighbor = ai->vec->neighbors[idx++];
+  if (idx >= ai->vec->index && ai->vec->next != NULL)
+    {
+      ai->vec = ai->vec->next;
+      ai->idx = 0;
+    }
+  else
+    ai->idx = idx;
+  return neighbor;
+}
+
+/* Return the one basic block regno is used in.  If regno is used
+   in more than one basic block or if it is unknown which block it
+   is used in, return 0.  */
+
+static inline int
+regno_basic_block (int regno)
+{
+  int block = REG_BASIC_BLOCK (regno);
+  if (block < 0)
+    block = 0;
+  return block;
+}
+
 extern void global_conflicts (void);
 
 /* In global.c  */
 
-/* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
-   and execute CODE.  */
-#define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE)	\
-do {									\
-  int i_;								\
-  int allocno_;								\
-  HOST_WIDE_INT *p_ = (ALLOCNO_SET);					\
-									\
-  for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0;		\
-       i_--, allocno_ += HOST_BITS_PER_WIDE_INT)			\
-    {									\
-      unsigned HOST_WIDE_INT word_ = (unsigned HOST_WIDE_INT) *p_++;	\
-									\
-      for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++)	\
-	{								\
-	  if (word_ & 1)						\
-	    {CODE;}							\
-	}								\
-    }									\
-} while (0)
-
-extern void ra_init_live_subregs (bool, sbitmap *, int *, int, rtx reg);
+/* Macro to visit all of IN_ALLOCNO's neighbors.  Neighbors are
+   returned in OUT_ALLOCNO for each iteration of the loop.  */
+
+#define FOR_EACH_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, ITER)		\
+  if (!adjacency || !adjacency_iter_init (&(ITER), (IN_ALLOCNO)))	\
+    ;									\
+  else									\
+    for ((OUT_ALLOCNO) = adjacency_iter_next (&(ITER));			\
+	 !adjacency_iter_done (&(ITER));				\
+	 (OUT_ALLOCNO) = adjacency_iter_next (&(ITER)))
 
+extern void ra_init_live_subregs (bool, sbitmap *, int *, int, rtx);
+extern bool conflict_p (int, int);
 
 #endif /* GCC_RA_H */