This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch 1/3] Sort du_head list and restrict register class by PREFERRED_RENAME_CLASS
- From: Paolo Bonzini <bonzini at gnu dot org>
- To: Yao Qi <yao at codesourcery dot com>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 21 Oct 2010 10:51:27 +0200
- Subject: Re: [patch 1/3] Sort du_head list and restrict register class by PREFERRED_RENAME_CLASS
- References: <4CBFE0BD.3080807@codesourcery.com> <4CBFE2C0.8040007@codesourcery.com>
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