From patchwork Sun Sep 30 15:35:49 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 188169 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 462592C00DB for ; Mon, 1 Oct 2012 01:36:05 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1349624166; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Subject:Message-ID:MIME-Version:Content-Type: Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=l1JBGzJA9A+wThfMfs2GTJGwaPA=; b=VNP3iuU4Ye38v+2 1eQ5poSVuDbjLYl+JwPwK2brNbsr3R6g5oRYAE0acKUpt9qg2Xp6y+pUKESErJxN dyliXbJl5+LbUwBgzZn4raquI88cAr40kLLq3R82dvPxMEapM6ZZNAT3RLNOYtxy gq8wCyvhkga7w1Xz3DqKlDCOTgYI= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Date:From:To:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=WyWO6VRrAxCK5DtPPkhHXkyt6nyV/4z951vIco6RSTMhpHNGEHYnET8+yAStqN bIACfz4vvdFcBwIAVuW6JtajzJ5VybxZd49emZDJPr3wZi0AmrdsWheqNnkKQTWX zqBn6cBI/i9f37cixsdzBSuLrD1PKFW8HECPc6WXokYb0=; Received: (qmail 17340 invoked by alias); 30 Sep 2012 15:36:00 -0000 Received: (qmail 17007 invoked by uid 22791); 30 Sep 2012 15:35:57 -0000 X-SWARE-Spam-Status: No, hits=-4.9 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 30 Sep 2012 15:35:51 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id C0F76542869; Sun, 30 Sep 2012 17:35:49 +0200 (CEST) Date: Sun, 30 Sep 2012 17:35:49 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Profile housekeeping 4/n (scale_loop_profile cleanup) Message-ID: <20120930153549.GA17664@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) 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 Hi, when writting scale_loop_profile I forgot about scale_loop_frequency that already sits in the tree for few years. The functions are slightly different. While scale_loop_frequency only cales frequency of each BB in the loop, scale_loop_profile takes care of reducing iteration count to known bound. For this reason I kept them both, and I am not really able to think of better names for them. I moved them to same place. I also simplified cale_loop_profile to call scale_loop_frequency to take care of the final update. Honza * cfgloop.c (scale_loop_profile): Move to... * cfgloopmanip.c (scale_loop_profile): .. here; use scale_loop_frequencies. (loopify): Use RDIV. Index: cfgloop.c =================================================================== --- cfgloop.c (revision 191850) +++ cfgloop.c (working copy) @@ -1666,121 +1666,3 @@ loop_exits_from_bb_p (struct loop *loop, return false; } - -/* Scale the profile estiamte within loop by SCALE. - If ITERATION_BOUND is non-zero, scale even further if loop is predicted - to iterate too many times. */ -void -scale_loop_profile (struct loop *loop, int scale, int iteration_bound) -{ - gcov_type iterations = expected_loop_iterations_unbounded (loop); - basic_block *bbs; - unsigned int i; - edge e; - edge_iterator ei; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ";; Scaling loop %i with scale %f, " - "bounding iterations to %i from guessed %i\n", - loop->num, (double)scale / REG_BR_PROB_BASE, - iteration_bound, (int)iterations); - - /* See if loop is predicted to iterate too many times. */ - if (iteration_bound && iterations > 0 - && RDIV (iterations * scale, REG_BR_PROB_BASE) > iteration_bound) - { - /* Fixing loop profile for different trip count is not trivial; the exit - probabilities has to be updated to match and frequencies propagated down - to the loop body. - - We fully update only the simple case of loop with single exit that is - either from the latch or BB just before latch and leads from BB with - simple conditional jump. This is OK for use in vectorizer. */ - e = single_exit (loop); - if (e) - { - edge other_e; - int freq_delta; - gcov_type count_delta; - - FOR_EACH_EDGE (other_e, ei, e->src->succs) - if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE)) - && e != other_e) - break; - - /* Probability of exit must be 1/iterations. */ - freq_delta = EDGE_FREQUENCY (e); - e->probability = REG_BR_PROB_BASE / iteration_bound; - other_e->probability = inverse_probability (e->probability); - freq_delta -= EDGE_FREQUENCY (e); - - /* Adjust counts accordingly. */ - count_delta = e->count; - e->count = apply_probability (e->src->count, e->probability); - other_e->count = apply_probability (e->src->count, other_e->probability); - count_delta -= e->count; - - /* If latch exists, change its frequency and count, since we changed - probability of exit. Theoretically we should update everything from - source of exit edge to latch, but for vectorizer this is enough. */ - if (loop->latch - && loop->latch != e->src) - { - loop->latch->frequency += freq_delta; - if (loop->latch->frequency < 0) - loop->latch->frequency = 0; - loop->latch->count += count_delta; - if (loop->latch->count < 0) - loop->latch->count = 0; - } - } - - /* Roughly speaking we want to reduce the loop body profile by the - the difference of loop iterations. We however can do better if - we look at the actual profile, if it is available. */ - scale = RDIV (iteration_bound * scale, iterations); - if (loop->header->count) - { - gcov_type count_in = 0; - - FOR_EACH_EDGE (e, ei, loop->header->preds) - if (e->src != loop->latch) - count_in += e->count; - - if (count_in != 0) - scale = RDIV (count_in * iteration_bound * REG_BR_PROB_BASE, loop->header->count); - } - else if (loop->header->frequency) - { - int freq_in = 0; - - FOR_EACH_EDGE (e, ei, loop->header->preds) - if (e->src != loop->latch) - freq_in += EDGE_FREQUENCY (e); - - if (freq_in != 0) - scale = RDIV (freq_in * iteration_bound * REG_BR_PROB_BASE, loop->header->frequency); - } - if (!scale) - scale = 1; - } - - if (scale == REG_BR_PROB_BASE) - return; - - /* Scale the actual probabilities. */ - bbs = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = bbs[i]; - - bb->count = RDIV (bb->count * scale, REG_BR_PROB_BASE); - bb->frequency = RDIV (bb->frequency * scale, REG_BR_PROB_BASE); - FOR_EACH_EDGE (e, ei, bb->succs) - e->count = RDIV (e->count * scale, REG_BR_PROB_BASE); - } - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ";; guessed iterations are now %i\n", - (int)expected_loop_iterations_unbounded (loop)); - free (bbs); -} Index: cfgloopmanip.c =================================================================== --- cfgloopmanip.c (revision 191850) +++ cfgloopmanip.c (working copy) @@ -39,8 +39,6 @@ static bool fix_bb_placement (basic_bloc static void fix_bb_placements (basic_block, bool *); static void unloop (struct loop *, bool *); -#define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) - /* Checks whether basic block BB is dominated by DATA. */ static bool rpe_enum_p (const_basic_block bb, const void *data) @@ -462,6 +460,7 @@ add_loop (struct loop *loop, struct loop } /* Multiply all frequencies in LOOP by NUM/DEN. */ + void scale_loop_frequencies (struct loop *loop, int num, int den) { @@ -472,6 +471,113 @@ scale_loop_frequencies (struct loop *loo free (bbs); } +/* Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE. + If ITERATION_BOUND is non-zero, scale even further if loop is predicted + to iterate too many times. */ + +void +scale_loop_profile (struct loop *loop, int scale, int iteration_bound) +{ + gcov_type iterations = expected_loop_iterations_unbounded (loop); + edge e; + edge_iterator ei; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Scaling loop %i with scale %f, " + "bounding iterations to %i from guessed %i\n", + loop->num, (double)scale / REG_BR_PROB_BASE, + iteration_bound, (int)iterations); + + /* See if loop is predicted to iterate too many times. */ + if (iteration_bound && iterations > 0 + && RDIV (iterations * scale, REG_BR_PROB_BASE) > iteration_bound) + { + /* Fixing loop profile for different trip count is not trivial; the exit + probabilities has to be updated to match and frequencies propagated down + to the loop body. + + We fully update only the simple case of loop with single exit that is + either from the latch or BB just before latch and leads from BB with + simple conditional jump. This is OK for use in vectorizer. */ + e = single_exit (loop); + if (e) + { + edge other_e; + int freq_delta; + gcov_type count_delta; + + FOR_EACH_EDGE (other_e, ei, e->src->succs) + if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE)) + && e != other_e) + break; + + /* Probability of exit must be 1/iterations. */ + freq_delta = EDGE_FREQUENCY (e); + e->probability = REG_BR_PROB_BASE / iteration_bound; + other_e->probability = inverse_probability (e->probability); + freq_delta -= EDGE_FREQUENCY (e); + + /* Adjust counts accordingly. */ + count_delta = e->count; + e->count = apply_probability (e->src->count, e->probability); + other_e->count = apply_probability (e->src->count, other_e->probability); + count_delta -= e->count; + + /* If latch exists, change its frequency and count, since we changed + probability of exit. Theoretically we should update everything from + source of exit edge to latch, but for vectorizer this is enough. */ + if (loop->latch + && loop->latch != e->src) + { + loop->latch->frequency += freq_delta; + if (loop->latch->frequency < 0) + loop->latch->frequency = 0; + loop->latch->count += count_delta; + if (loop->latch->count < 0) + loop->latch->count = 0; + } + } + + /* Roughly speaking we want to reduce the loop body profile by the + the difference of loop iterations. We however can do better if + we look at the actual profile, if it is available. */ + scale = RDIV (iteration_bound * scale, iterations); + if (loop->header->count) + { + gcov_type count_in = 0; + + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (e->src != loop->latch) + count_in += e->count; + + if (count_in != 0) + scale = RDIV (count_in * iteration_bound * REG_BR_PROB_BASE, loop->header->count); + } + else if (loop->header->frequency) + { + int freq_in = 0; + + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (e->src != loop->latch) + freq_in += EDGE_FREQUENCY (e); + + if (freq_in != 0) + scale = RDIV (freq_in * iteration_bound * REG_BR_PROB_BASE, loop->header->frequency); + } + if (!scale) + scale = 1; + } + + if (scale == REG_BR_PROB_BASE) + return; + + /* Scale the actual probabilities. */ + scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; guessed iterations are now %i\n", + (int)expected_loop_iterations_unbounded (loop)); +} + /* Recompute dominance information for basic blocks outside LOOP. */ static void @@ -772,7 +878,7 @@ loopify (edge latch_edge, edge header_ed switch_bb->count = cnt; FOR_EACH_EDGE (e, ei, switch_bb->succs) { - e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE; + e->count = RDIV (switch_bb->count * e->probability, REG_BR_PROB_BASE); } } scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE);