From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 119164 invoked by alias); 16 Jun 2017 17:15:23 -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 118944 invoked by uid 89); 16 Jun 2017 17:15:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-14.6 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_LAZY_DOMAIN_SECURITY,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=Critical, 11617 X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 16 Jun 2017 17:15:00 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 229CF548193; Fri, 16 Jun 2017 19:15:03 +0200 (CEST) Date: Fri, 16 Jun 2017 17:15:00 -0000 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Make edge profiling slightly faster Message-ID: <20170616171502.GB59896@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-SW-Source: 2017-06/txt/msg01222.txt.bz2 Hi, edge profling builds spanning tree and then intstruments all remaining edges of CFG. With branch prediction we could pick up those edges that are expected to execute more often saving some of -fprofile-generate overhead (about 3% on tramp3d but likely more on testcases with more complicated control flow). Bootstrapped/regtested x86_64-linux, comitted. Honza * profile.c (compare_freqs): New function. (branch_prob): Sort edge list. (find_spanning_tree): Assume that the list is priority sorted. * gcc.dg/tree-ssa/ssa-lim-11.c: Disable branch prediction. Index: profile.c =================================================================== --- profile.c (revision 249223) +++ profile.c (working copy) @@ -987,6 +987,27 @@ output_location (char const *file_name, } } +/* Helper for qsort so edges get sorted from highest frequency to smallest. + This controls the weight for minimal spanning tree algorithm */ +static int +compare_freqs (const void *p1, const void *p2) +{ + const_edge e1 = *(const const_edge *)p1; + const_edge e2 = *(const const_edge *)p2; + + /* Critical edges needs to be split which introduce extra control flow. + Make them more heavy. */ + int m1 = EDGE_CRITICAL_P (e1) ? 2 : 1; + int m2 = EDGE_CRITICAL_P (e2) ? 2 : 1; + + if (EDGE_FREQUENCY (e1) * m1 + m1 != EDGE_FREQUENCY (e2) * m2 + m2) + return EDGE_FREQUENCY (e2) * m2 + m2 - EDGE_FREQUENCY (e1) * m1 - m1; + /* Stabilize sort. */ + if (e1->src->index != e2->src->index) + return e2->src->index - e1->src->index; + return e2->dest->index - e1->dest->index; +} + /* Instrument and/or analyze program behavior based on program the CFG. This function creates a representation of the control flow graph (of @@ -1140,6 +1161,7 @@ branch_prob (void) el = create_edge_list (); num_edges = NUM_EDGES (el); + qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs); alloc_aux_for_edges (sizeof (struct edge_profile_info)); /* The basic blocks are expected to be numbered sequentially. */ @@ -1431,22 +1453,8 @@ find_spanning_tree (struct edge_list *el } } - /* Now insert all critical edges to the tree unless they form a cycle. */ - for (i = 0; i < num_edges; i++) - { - edge e = INDEX_EDGE (el, i); - if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore - && find_group (e->src) != find_group (e->dest)) - { - if (dump_file) - fprintf (dump_file, "Critical edge %d to %d put to tree\n", - e->src->index, e->dest->index); - EDGE_INFO (e)->on_tree = 1; - union_groups (e->src, e->dest); - } - } - - /* And now the rest. */ + /* And now the rest. Edge list is sorted according to frequencies and + thus we will produce minimal spanning tree. */ for (i = 0; i < num_edges; i++) { edge e = INDEX_EDGE (el, i);