From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23244 invoked by alias); 15 Apr 2010 11:56:46 -0000 Received: (qmail 23224 invoked by uid 22791); 15 Apr 2010 11:56:45 -0000 X-SWARE-Spam-Status: No, hits=-1.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SARE_MSGID_LONG45 X-Spam-Check-By: sourceware.org Received: from mail-qy0-f193.google.com (HELO mail-qy0-f193.google.com) (209.85.221.193) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 15 Apr 2010 11:56:39 +0000 Received: by qyk31 with SMTP id 31so1294428qyk.20 for ; Thu, 15 Apr 2010 04:56:37 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.37.137 with HTTP; Thu, 15 Apr 2010 04:56:37 -0700 (PDT) In-Reply-To: <4D60B0700D1DB54A8C0C6E9BE69163700E5F85D6@EXCHANGEVS.IceraSemi.local> References: <4D60B0700D1DB54A8C0C6E9BE69163700E572F41@EXCHANGEVS.IceraSemi.local> <20100413234337.GE20952@atrey.karlin.mff.cuni.cz> <4D60B0700D1DB54A8C0C6E9BE69163700E5F85D6@EXCHANGEVS.IceraSemi.local> Date: Thu, 15 Apr 2010 11:57:00 -0000 Received: by 10.224.53.150 with SMTP id m22mr1288144qag.69.1271332597112; Thu, 15 Apr 2010 04:56:37 -0700 (PDT) Message-ID: Subject: Re: branch probabilities on multiway branches From: Steven Bosscher To: Rahul Kharche Cc: Jan Hubicka , gcc@gcc.gnu.org, sdkteam-gnu Content-Type: text/plain; charset=ISO-8859-1 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2010-04/txt/msg00363.txt.bz2 On Thu, Apr 15, 2010 at 1:11 PM, Rahul Kharche wrote: > The calculate branch probabilities algorithm (1) in the Wu Larus paper > also evenly distributes branch probabilities when number of outgoing > edges is > 2, e.g. switch cases implemented as jump tables. > > Are they any known heuristics to generate better branch probabilities > in this case? Probably not. GCC has some funny heuristics for mutli-way branches itself, but these heuristics are not used for estimating edge probabilities. They should be only used to determine the expand order of switch-statements with a char-typed switch-expr to a series of if-then-else blocks. In practice they're also used for all integer switch-exprs with case label values between 0 and 127. See estimate_case_costs. I have no idea whether this heuristic makes any sense. Multi-way branches are not predictable in general. Profile information is much more useful. There is a transformation implemented in GCC's value profiling to put the most-frequently taken case-label of a switch-expr at the top of the switch, i.e. switch (bla) { case 1: /* happens 1000 times */ blah3; break; case 2: /* happens 10 times */ blah2; break; case 3: /* happens 1 times */ blah3; break; ... } => if (bla == 1) { blah3; } else switch (bla) { case 2: /* happens 10 times */ blah2; break; case 3: /* happens 1 times */ blah3; break; ... } but you need profiling for this. What is the problem you're trying to solve? Ciao! Steven