From patchwork Fri Nov 5 15:35:19 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yao Qi X-Patchwork-Id: 70265 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id EE29C1007D1 for ; Sat, 6 Nov 2010 02:36:15 +1100 (EST) Received: (qmail 6024 invoked by alias); 5 Nov 2010 15:36:13 -0000 Received: (qmail 5769 invoked by uid 22791); 5 Nov 2010 15:36:10 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 05 Nov 2010 15:35:34 +0000 Received: (qmail 14382 invoked from network); 5 Nov 2010 15:35:31 -0000 Received: from unknown (HELO ?192.168.0.101?) (yao@127.0.0.2) by mail.codesourcery.com with ESMTPA; 5 Nov 2010 15:35:31 -0000 Message-ID: <4CD42437.8060404@codesourcery.com> Date: Fri, 05 Nov 2010 23:35:19 +0800 From: Yao Qi User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.15) Gecko/20101027 Thunderbird/3.0.10 MIME-Version: 1.0 To: Eric Botcazou CC: gcc-patches@gcc.gnu.org Subject: Re: [Ping] [patch 0/3] New macro PREFERRED_RENAME_CLASS References: <4CD24091.1020904@codesourcery.com> <201011050955.56412.ebotcazou@adacore.com> In-Reply-To: <201011050955.56412.ebotcazou@adacore.com> X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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." 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. */