Re: [Ping] [patch 0/3] New macro PREFERRED_RENAME_CLASS

[Yao Qi <yao@codesourcery.com>]

[-- Attachment #1: Type: text/plain, Size: 4671 bytes --]

On 11/05/2010 04:55 PM, Eric Botcazou wrote:
>> Patch 1: does everything except adding target hook
>> preferred_rename_class .  It is a separate improvement to register-rename.
>> http://gcc.gnu.org/ml/gcc-patches/2010-10/msg02197.html
>
> You didn't really inline the callback, did you?  If you want to keep the
> comparer function standalone, then remove the superfluous indirection.
>

Done.  Removed function pointer CMP, and use merge_sort_callback directly.

>
> @@ -51,6 +51,8 @@ struct du_head
>     struct du_head *next_chain;
>     /* The first and last elements of this chain.  */
>     struct du_chain *first, *last;
> +  /* The length of du_chain for non-debug insns.  */
> +  int length;
>     /* Describes the register being tracked.  */
>     unsigned regno, nregs;
>
> du_chain is a structure tag, so you need to elaborate.
>
>

Add one sentence in comment to explain it a little more, "The du_head 
linked list can be sorted by this, and register-rename can prefer 
register classes according to this order.".

>
> @@ -154,6 +156,141 @@ merge_overlapping_regs (HARD_REG_SET *pset, struct
> du_head *head)
>       }
>   }
>
> +/* Get the next LENGTH element in list from START.  If length of
> +   list from START is less than or equal to LENGTH, return the
> +   last element.  */
> +static struct du_head *
> +get_tail_du_head (struct du_head *start, int length)
> +{
> +  while (length--&&  start->next_chain != NULL)
> +      start = start->next_chain;
> +
> +  return start;
>
> Avoid TAIL and HEAD in the same function name.  GET_ELEMENT is clearer.  And
> LENGTH is a poor choice for the parameter name, use N instead.
>
> /* Return the Nth element in LIST.  If LIST contains less than N elements,
>     return the last one.  */
>
> static struct du_head *
> get_element (struct du_head *list, int n)
>
>

Fixed as you suggested.

>
> +/* Merge the first two sequences of CURRENT_LENGTH nodes in the
> +   linked list pointed by START_NODE.  Update START_NODE to point
> +   to the merged nodes, and return a pointer to the last merged
> +   node.   CMP is callback  for comparison.  */
> +
> +static struct du_head *
> +merge(struct du_head **start_node, int current_length,
> +      int (*cmp) (const struct du_head *, const struct du_head *))
>
> Why CURRENT_LENGTH?  Just use LENGTH.
>

Done.

> The first sentence is somewhat ambiguous as one might get the impression that
> the 2 sequences aren't already present in the list.
>
> /* Merge the first 2 sub-lists of LENGTH nodes contained in the linked list
>     pointed to by START_NODE.  Update...
>
> Document what happens when the linked list doesn't contain enough elements.
>
>

Done.

> +	  current_tail_node =
> +	    get_tail_du_head (current_sorted_node,
> +			      current_length - left_count);
>
> '=' on the next line
>
>

Done.

> +  return current_tail_node->next_chain != NULL ?
> +    current_tail_node : NULL;
>
> return (current_tail_node->next_chain ? current_tail_node : NULL);
>

Done.

>
> +/* Non-recursive merge sort to du_head list.  */
> +static void
> +sort_du_head (struct du_head **head,
> +	      int(*cmp)(const struct du_head *, const struct du_head *))
>
> /* Sort the linked list pointed to by HEAD.  The algorithm is a non-recursive
>     merge sort [that ...optional more detailed explanation...]
>
>

Done.  Add more detailed explanation in comments.

> +  do
> +    {
> +      struct du_head **segment = head;
> +
>
> Trailing spaces.
>

Which one is trailing space?

> +      while ((last_tail = merge(segment, current_length, cmp))
> +	     != NULL)
>
> Why breaking the line?
>

Fixed.

> +	{
> +	  segment =&last_tail->next_chain;
> +	}
>
> Superfluous curly braces.
>

Fixed.

>
> Are you sure that this revised implementation works as expected?  Won't it
> stop after the 1-length merge phase?
>

Ur, my first version is correct.  Revert it to my first version.

>
> @@ -265,13 +405,13 @@ regrename_optimize (void)
>
>   	  /* Now potential_regs is a reasonable approximation, let's
>   	     have a closer look at each register still in there.  */
> -	  for (new_reg = 0; new_reg<  FIRST_PSEUDO_REGISTER; new_reg++)
> +	  for (new_reg = FIRST_PSEUDO_REGISTER - 1; new_reg>= 0; new_reg--)
>
> What is this hunk for?  It isn't mentioned in the ChangeLog.
>

Yeah, we should explain it a little bit in comments.  I add this 
paragraph below in comments, and ChangeLog will be updated accordingly.
"Registers from high to low is iterated here, in order to 	     prefer 
low registers.  On some ports, low registers are 	     better than high 
registers in terms of final code size."

-- 
Yao Qi
CodeSourcery
yao@codesourcery.com
(650) 331-3385 x739

[-- Attachment #2: regrename_improve_1105.patch --]
[-- Type: text/x-patch, Size: 7438 bytes --]

gcc/
        * regrename.c (struct du_head): Add new element length.
        (sort_du_head, get_element, merge, merge_sort_callback):
        New functions of merge sort implementation to du_head list.
        (regrename_optimize): Sort du_head linked list by length.
	Iterate registers in a reversed order to prefer low registers.
        (create_new_chain):  Initialize length.
        (scan_rtx_reg): Increase length for non-debug insns.

diff --git a/gcc/regrename.c b/gcc/regrename.c
index 2535ab7..31745f8 100644
--- a/gcc/regrename.c
+++ b/gcc/regrename.c
@@ -51,6 +51,10 @@ struct du_head
   struct du_head *next_chain;
   /* The first and last elements of this chain.  */
   struct du_chain *first, *last;
+  /* The length of du_chain for non-debug insns.  The du_head linked
+     list can be sorted by this, and register-rename can prefer
+     register classes according to this order.  */
+  int length;
   /* Describes the register being tracked.  */
   unsigned regno, nregs;
 
@@ -154,6 +158,151 @@ merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
     }
 }
 
+/* Return the Nth element in LIST.  If LIST contains less than N
+   elements, return the last one.  */
+static struct du_head *
+get_element (struct du_head *list, int n)
+{
+  while (n-- && list->next_chain != NULL)
+    list = list->next_chain;
+
+  return list;
+}
+
+/* Comparison function of merge sort.  Return true if A is less than
+   B, otherwise return false.  */
+static inline int 
+merge_sort_callback(const struct du_head *a, 
+		    const struct du_head *b)
+{
+  return a->length < b->length;
+}
+
+/* Merge the first 2 sub-lists of LENGTH nodes contained in the
+   linked list pointed to by START_NODE.  Update START_NODE to point 
+   to the merged nodes, and return a pointer to the last merged
+   node.  Return NULL if START_NODE doesn't contain enough
+   elements, or this pass of merge is done.  */
+static struct du_head *
+merge(struct du_head **start_node, int length)
+{
+  int i, left_count, right_count;
+  struct du_head *left, *right;
+  /* Current node of sort result.  */
+  struct du_head *current_sorted_node;
+  /* Tail node of sort, used to connect with next piece of list.  */
+  struct du_head *current_tail_node;
+
+  if (*start_node == NULL)
+    return NULL;
+
+  left = right = *start_node;
+  right_count = left_count = 0;
+
+  /* Step RIGHT along the list by LENGTH places.  */
+  for (i = 0; i < length; i++)
+    {
+      right = right->next_chain;
+      if (right == NULL)
+	  return NULL;
+    }
+
+  /* Initialize current_sorted_node.  */
+  if (merge_sort_callback (left, right))
+    {
+      ++right_count;
+      current_sorted_node = right;
+      *start_node = right;
+      right = right->next_chain;
+    }
+  else
+    {
+      ++left_count;
+      current_sorted_node = left;
+      left = left->next_chain;
+    }
+
+  while (1)
+    {
+      /* Choose LEFT or RIGHT to take the next element from.  If 
+	 either is empty, choose from the other one.  */
+      if (left_count == length || left == NULL)
+	{
+	  current_sorted_node->next_chain = right;
+	  current_tail_node 
+	    = get_element (current_sorted_node, 
+			   length - right_count);
+
+	  break;
+	}
+      else if (right_count == length || right == NULL)
+	{
+	  /* Save the head node of next piece of linked list.  */
+	  struct du_head *tmp = current_sorted_node->next_chain;
+
+	  current_sorted_node->next_chain = left;
+	  current_tail_node
+	    = get_element (current_sorted_node,
+			   length - left_count);
+	  /* Connect sorted list to next piece of list.  */
+	  current_tail_node->next_chain = tmp;
+	  break;
+	}
+      else
+	{
+	  /* Normal merge operations.  If both LEFT and RIGHT are 
+	     non-empty, compare the first element of each and choose 
+	     the lower one.  */
+	  if (merge_sort_callback (left, right))
+	    {
+	      right_count++;
+	      current_sorted_node->next_chain = right;
+	      right = right->next_chain;
+	    }
+	  else
+	    {
+	      left_count++;
+	      current_sorted_node->next_chain = left;
+	      left = left->next_chain;
+	    }
+	  current_sorted_node = current_sorted_node->next_chain;
+	}
+    }
+  /* Returns NULL if this pass of merge is done.  */
+  return (current_tail_node->next_chain ? current_tail_node : NULL);
+}
+
+/* Sort the linked list pointed to by HEAD.  The algorithm is a
+   non-recursive merge sort to linked list.  */
+static void
+sort_du_head (struct du_head **head)
+{
+  int current_length = 1;
+  struct du_head *last_tail;
+
+  /* In each pass, lists of size current_length is merged to 
+     lists of size 2xcurrent_length (Initially current_length 
+     is 1).  */
+  while (1)
+    {
+      last_tail = merge(head, current_length);
+      if (last_tail != NULL)
+	{
+	  do
+	    {
+	      last_tail = merge (&last_tail->next_chain, 
+				 current_length);
+	    }
+	  while (last_tail != NULL);
+	  current_length *= 2;
+	}
+      else
+	break;
+    }
+}
+
 /* Perform register renaming on the current function.  */
 
 static unsigned int
@@ -195,6 +344,8 @@ regrename_optimize (void)
       if (dump_file)
 	dump_def_use_chain (all_chains);
 
+      sort_du_head (&all_chains);
+
       CLEAR_HARD_REG_SET (unavailable);
       /* Don't clobber traceback for noreturn functions.  */
       if (frame_pointer_needed)
@@ -251,6 +402,7 @@ regrename_optimize (void)
 	      if (DEBUG_INSN_P (tmp->insn))
 		continue;
 	      n_uses++;
 	      IOR_COMPL_HARD_REG_SET (this_unavailable,
 				      reg_class_contents[tmp->cl]);
 	    }
@@ -264,14 +416,17 @@ regrename_optimize (void)
 	  merge_overlapping_regs (&this_unavailable, this_head);
 
 	  /* Now potential_regs is a reasonable approximation, let's
-	     have a closer look at each register still in there.  */
-	  for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
+	     have a closer look at each register still in there.
+	     Registers from high to low is iterated here, in order to
+	     prefer low registers.  On some ports, low registers are
+	     better than high registers in terms of final code size.  */
+	  for (new_reg = FIRST_PSEUDO_REGISTER - 1; new_reg >= 0; new_reg--)
 	    {
 	      enum machine_mode mode = GET_MODE (*this_head->first->loc);
 	      int nregs = hard_regno_nregs[new_reg][mode];
 
 	      for (i = nregs - 1; i >= 0; --i)
-	        if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
+		if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
 		    || fixed_regs[new_reg + i]
 		    || global_regs[new_reg + i]
 		    /* Can't use regs which aren't saved by the prologue.  */
@@ -527,6 +682,7 @@ create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
   head->need_caller_save_reg = 0;
   head->cannot_rename = 0;
   head->terminated = 0;
+  head->length = 0;
 
   VEC_safe_push (du_head_p, heap, id_to_chain, head);
   head->id = current_id++;
@@ -572,6 +728,8 @@ create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
   this_du->loc = loc;
   this_du->insn = insn;
   this_du->cl = cl;
+
+  head->length = 1;
 }
 
 static void
@@ -661,6 +819,8 @@ scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
 		head->last->next_use = this_du;
 	      head->last = this_du;
 
+	      if (!DEBUG_INSN_P (insn))
+		head->length++;
 	    }
 	  /* Avoid adding the same location in a DEBUG_INSN multiple times,
 	     which could happen with non-exact overlap.  */