From patchwork Fri Mar 11 21:09:37 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 596505 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 8584E1402BC for ; Sat, 12 Mar 2016 08:09:49 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=UzWwrwE7; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=SFIeNdwE1ctiq3Wau Olxodxz0wJWu+X0HvO8vyb9HhfWAJSKcW4+lb8AAlE4BjWivzIhcb+PEXBh0WLrw xx+9eXAUCiq+FBjqWykFD8P/MB4EiprLbLTsqWZZcrwGWM4oACVOrLVm6qO5C/UV vuV1qKG/Mqv8V2kwyxGIS21AQQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=aw2WpjuDnHM/ef8wL4058Xq 6Ih4=; b=UzWwrwE7mvA/NQQi4zm2Ex/fYT94iIDGj895O5EEyMB64EW/ReKOIgN KprlkAhXGQDhitwGgGLvxCH1UaQh3bb829kQccHQOxYmdJnu8SpkZQNX56WKJ1IW QV8JrfR2xeLSoJmsdtCtwTw97njPXCzj5JdXGeOeyRraYM8QaZUY= Received: (qmail 66312 invoked by alias); 11 Mar 2016 21:09:41 -0000 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 Received: (qmail 66255 invoked by uid 89); 11 Mar 2016 21:09:40 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=Actual, 25913, Big X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 11 Mar 2016 21:09:39 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (Postfix) with ESMTPS id D1252C00EB30; Fri, 11 Mar 2016 21:09:37 +0000 (UTC) Received: from slagheap.utah.redhat.com (ovpn-113-182.phx2.redhat.com [10.3.113.182]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u2BL9bvh004253; Fri, 11 Mar 2016 16:09:37 -0500 Subject: Re: [RFA][PATCH][PR tree-optimization/64058] Improve and stabilize sorting of coalesce pairs To: Richard Biener References: <56E234EE.9080804@redhat.com> Cc: gcc-patches From: Jeff Law Message-ID: <56E33411.5050000@redhat.com> Date: Fri, 11 Mar 2016 14:09:37 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.6.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes On 03/11/2016 03:02 AM, Richard Biener wrote: [Big snip] > > Can you please split out the 'index' introduction as a separate patch > and apply that? > I think it is quite obviously a good idea and might make regression > hunting easier later if needed. Done. Actual patch installed attached for archival purposes. I'll address your comments on the rest of the patch independently. Jeff commit 0171eb6090691291571a8db83a5789ecac118e57 Author: law Date: Fri Mar 11 21:07:31 2016 +0000 PR tree-optimization/64058 * tree-ssa-coalesce.c (struct coalesce_pair): Add new field INDEX. (num_coalesce_pairs): Move up earlier in file. (find_coalesce_pair): Initialize the INDEX field for each pair discovered. (compare_pairs): No longer sort on the elements in each pair. Instead break ties with the index of the coalesce pair. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@234149 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c69c753..f3a7351 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2016-03-11 Jeff Law + + PR tree-optimization/64058 + * tree-ssa-coalesce.c (struct coalesce_pair): Add new field INDEX. + (num_coalesce_pairs): Move up earlier in file. + (find_coalesce_pair): Initialize the INDEX field for each pair + discovered. + (compare_pairs): No longer sort on the elements in each pair. + Instead break ties with the index of the coalesce pair. + 2016-03-11 Kyrylo Tkachov PR target/70002 diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 6624e7e..e49876e 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -50,6 +50,11 @@ struct coalesce_pair int first_element; int second_element; int cost; + + /* The order in which coalescing pairs are discovered is recorded in this + field, which is used as the final tie breaker when sorting coalesce + pairs. */ + int index; }; /* Coalesce pair hashtable helpers. */ @@ -254,6 +259,13 @@ delete_coalesce_list (coalesce_list *cl) free (cl); } +/* Return the number of unique coalesce pairs in CL. */ + +static inline int +num_coalesce_pairs (coalesce_list *cl) +{ + return cl->list->elements (); +} /* Find a matching coalesce pair object in CL for the pair P1 and P2. If one isn't found, return NULL if CREATE is false, otherwise create a new @@ -290,6 +302,7 @@ find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create) pair->first_element = p.first_element; pair->second_element = p.second_element; pair->cost = 0; + pair->index = num_coalesce_pairs (cl); *slot = pair; } @@ -343,29 +356,14 @@ compare_pairs (const void *p1, const void *p2) int result; result = (* pp1)->cost - (* pp2)->cost; - /* Since qsort does not guarantee stability we use the elements - as a secondary key. This provides us with independence from - the host's implementation of the sorting algorithm. */ + /* And if everything else is equal, then sort based on which + coalesce pair was found first. */ if (result == 0) - { - result = (* pp2)->first_element - (* pp1)->first_element; - if (result == 0) - result = (* pp2)->second_element - (* pp1)->second_element; - } + result = (*pp2)->index - (*pp1)->index; return result; } - -/* Return the number of unique coalesce pairs in CL. */ - -static inline int -num_coalesce_pairs (coalesce_list *cl) -{ - return cl->list->elements (); -} - - /* Iterate over CL using ITER, returning values in PAIR. */ #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \