From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16761 invoked by alias); 15 Apr 2010 14:14:26 -0000 Received: (qmail 16702 invoked by uid 22791); 15 Apr 2010 14:14:24 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=BAYES_00,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from portal.icerasemi.com (HELO pOrtaL.icerasemi.com) (213.249.204.90) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 15 Apr 2010 14:14:18 +0000 X-ASG-Debug-ID: 1271340854-7c9f00090000-ThFIni X-Barracuda-URL: http://192.168.1.243:80/cgi-bin/mark.cgi Received: from Exchangevs.Icerasemi.com (cluster1.icerasemi.local [192.168.1.203]) by pOrtaL.icerasemi.com (Spam & Virus Firewall) with ESMTP id 80DAF8C92F; Thu, 15 Apr 2010 14:14:14 +0000 (GMT) Received: from Exchangevs.Icerasemi.com (cluster1.icerasemi.local [192.168.1.203]) by pOrtaL.icerasemi.com with ESMTP id TgJbz2WlY1MPsunm; Thu, 15 Apr 2010 14:14:14 +0000 (GMT) Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable X-ASG-Orig-Subj: RE: branch probabilities on multiway branches Subject: RE: branch probabilities on multiway branches Date: Thu, 15 Apr 2010 14:54:00 -0000 Message-ID: <4D60B0700D1DB54A8C0C6E9BE69163700E67D567@EXCHANGEVS.IceraSemi.local> References: <4D60B0700D1DB54A8C0C6E9BE69163700E572F41@EXCHANGEVS.IceraSemi.local> <20100413234337.GE20952@atrey.karlin.mff.cuni.cz> <4D60B0700D1DB54A8C0C6E9BE69163700E5F85D6@EXCHANGEVS.IceraSemi.local> From: "Rahul Kharche" To: "Steven Bosscher" Cc: "Jan Hubicka" , , "sdkteam-gnu" X-Barracuda-Connect: cluster1.icerasemi.local[192.168.1.203] X-Barracuda-Start-Time: 1271340854 X-Barracuda-Spam-Score: 0.00 X-Barracuda-Spam-Status: No, SCORE=0.00 using global scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=9.0 tests= X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.2.27487 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- X-IsSubscribed: yes 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/msg00370.txt.bz2 >>What is the problem you're trying to solve? Generally speaking I was looking for a better logic based on estimated branch probability to decide between using binary search tree and jump table implementation of a switch case. One interesting test case is where the gross structure of a function is a switch case. The function is parameterized on input to the switch i.e. of the following type: void foo (int val, int arg1, ...) { switch (val) { case 100: /* blah1 */ break; case 101: /* blah2 */ break; . . . case 10000: /* blah10000 */ break; default: ; } } On the basis of the static call graph, the estimated frequencies of the calls to foo (), and assuming argument val is constant at each call site, is it possible to optimize the switch case in foo ()? Perhaps along the line of pulling out the most frequent case like you mentioned in your example. Or specializing foo () on frequent cases of val. In this case inlining and VRP would have automatically done what I am suggesting. Inlining however is not attempted because foo () is estimated to be large. Many Thanks, Rahul