[patch 1/3] Sort du_head list and restrict register class by PREFERRED_RENAME_CLASS

[Paolo Bonzini]

On 10/21/2010 08:50 AM, Yao Qi wrote:

> +/* Get the next LENGTH element in list from START.  If length of
> +   list from START is less than LENGTH, return the last one.  */

Looks like it is "If the length of the list headed 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;
> +    }

Useless braces.

> +
> +  return start;
> +}
> +
> +
> +/* Merge the linked list starting from START_NODE.  CMP is callback
> +   for comparison.  */

This comments leaves some questions unanswered: merge with what?  What 
is returned, and what is left in *START_NODE?

In other words, something like this should do:

/* 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.  */

> +static struct du_head *
> +merge(struct du_head **start_node, int current_length,
> +      int(*cmp)(const struct du_head *, const struct du_head *))

Spaces required after function name and return type ("int (*cmp) (const 
etc.").

> +{
> +  int can_merge_p, 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;
> +
> +  can_merge_p = 1;
> +  left = right = *start_node;
> +  right_count = left_count = 0;
> +
> +  for (i = 0; i<  current_length; i++)
> +    {
> +      right = right->next_chain;
> +      if (right == NULL)
> +	{
> +	  can_merge_p = 0;

Just return NULL right away.

> +	  break;
> +	}
> +    }
> +
> +  if (!can_merge_p)
> +    return NULL;

In sort_du_head:

> +   while (1)
> +    {
> +      last_tail = merge(head, current_length, cmp);
> +      if (last_tail != NULL)
> +	{
> +	  do
> +	    {
> +	      last_tail = merge (&last_tail->next_chain,
> +				 current_length, cmp);
> +	    }
> +	  while (last_tail != NULL);
> +	  current_length *= 2;
> +	}
> +      else
> +	break;
> +    }

Very nice algorithm!

What about however something even simpler, like:

   do
     {
       segment = head;
       segments = 1;
       while ((last_tail = merge(segment, current_length, cmp)) != NULL)
         {
           segment = &last_tail->next_chain;
           segments++;
         }
       current_length *= 2;
     }
   while (segments > 1);

(Untested).

> +/* Call back function of merge sort.  Return true if A is less than
> +   B, otherwise return false.  */
> +static int
> +merge_sort_callback(const struct du_head *a,
> +		    const struct du_head *b)
> +{
> +  return a->length<  b->length;
> +}

Maybe this can be inlined?

>   /* Perform register renaming on the current function.  */
>
>   static unsigned int
> @@ -195,6 +340,8 @@ regrename_optimize (void)
>         if (dump_file)
>   	dump_def_use_chain (all_chains);
>
> +      sort_du_head (&all_chains, merge_sort_callback);
> +
>         CLEAR_HARD_REG_SET (unavailable);
>         /* Don't clobber traceback for noreturn functions.  */
>         if (frame_pointer_needed)
> @@ -251,8 +398,11 @@ regrename_optimize (void)
>   	      if (DEBUG_INSN_P (tmp->insn))
>   		continue;
>   	      n_uses++;
> +#ifndef PREFERRED_RENAME_CLASS
> +#define PREFERRED_RENAME_CLASS(CLASS) CLASS
> +#endif

This goes in defaults.h.  I'm not sure about the performance 
implications of making this a target hook.  Also, it looks like 
everything except PREFERRED_RENAME_CLASS is actually a separate 
improvement to rename-registers that could go in first.  So, I would 
structure the series like this.:

- patch 1 does everything except adding PREFERRED_RENAME_CLASS

- patch 2 adds PREFERRED_RENAME_CLASS to docs and code

- patch 3 adds the macro to the ARM backend.

>   	      IOR_COMPL_HARD_REG_SET (this_unavailable,
> -				      reg_class_contents[tmp->cl]);
> +				      reg_class_contents[PREFERRED_RENAME_CLASS(tmp->cl)]);
>   	    }
>
>   	  if (n_uses<  2)


>   static bool
>   gate_handle_regrename (void)
>   {
> -  return (optimize>  0&&  (flag_rename_registers));
> +  return ((optimize>  0 || optimize_size)&&  (flag_rename_registers));
>   }

Not needed, optimize_size should always be set.  (Sorry for the garbling 
of spaces that my mailer did).

Thanks,

Paolo