From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20860 invoked by alias); 24 Sep 2015 10:33:03 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 20851 invoked by uid 89); 24 Sep 2015 10:33:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.8 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=no version=3.3.2 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; Thu, 24 Sep 2015 10:33:02 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (Postfix) with ESMTPS id 1951C40C4D; Thu, 24 Sep 2015 10:33:01 +0000 (UTC) Received: from localhost.localdomain (vpn1-5-35.ams2.redhat.com [10.36.5.35]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t8OAWxsD022439; Thu, 24 Sep 2015 06:33:00 -0400 Subject: Re: [PATCH 2/4] bb-reorder: Add the "simple" algorithm To: Segher Boessenkool , gcc-patches@gcc.gnu.org References: From: Bernd Schmidt Message-ID: <5603D15B.2090408@redhat.com> Date: Thu, 24 Sep 2015 11:13:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2015-09/txt/msg01843.txt.bz2 On 09/24/2015 12:06 AM, Segher Boessenkool wrote: > This is the meat of this series: a new algorithm to do basic block > reordering. It uses the simple greedy approach to maximum weighted > matching, where the weights are the predicted execution frequency of > the edges. This always finds a solution that is within a factor two > of optimal, if you disregard loops (which we cannot allow) and the > complications of block partitioning. Looks really good for the most part. The comment at the top of the file should be updated to mention both algorithms. > + /* Sort the edges, the most desirable first. */ > + > + std::stable_sort (edges, edges + n, edge_order); Any thoughts on this vs qsort? Do you need a stable sort? > + int j; > + for (j = 0; j < n; j++) for (int j ... here and in the other loop that uses j. > + /* If the entry edge no longer falls through we have to make a new > + block so it can do so again. */ > + > + edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0); > + if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux) > + { > + force_nonfallthru (e); > + e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux; > + BB_COPY_PARTITION (e->src, e->dest); > + } > +} That's a bit odd, can this situation be prevented earlier? Why wouldn't we force the entry edge to fall thru? Bernd