From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23677 invoked by alias); 27 Aug 2010 21:56:06 -0000 Received: (qmail 23669 invoked by uid 22791); 27 Aug 2010 21:56:05 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,SPF_HELO_PASS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 27 Aug 2010 21:56:00 +0000 Received: from kpbe15.cbf.corp.google.com (kpbe15.cbf.corp.google.com [172.25.105.79]) by smtp-out.google.com with ESMTP id o7RLtwfJ001972 for ; Fri, 27 Aug 2010 14:55:58 -0700 Received: from gwj18 (gwj18.prod.google.com [10.200.10.18]) by kpbe15.cbf.corp.google.com with ESMTP id o7RLtJkj022833 for ; Fri, 27 Aug 2010 14:55:57 -0700 Received: by gwj18 with SMTP id 18so2056674gwj.2 for ; Fri, 27 Aug 2010 14:55:56 -0700 (PDT) MIME-Version: 1.0 Received: by 10.90.82.9 with SMTP id f9mr2083109agb.3.1282946156713; Fri, 27 Aug 2010 14:55:56 -0700 (PDT) Received: by 10.91.220.13 with HTTP; Fri, 27 Aug 2010 14:55:56 -0700 (PDT) In-Reply-To: References: Date: Sat, 28 Aug 2010 00:21:00 -0000 Message-ID: Subject: Re: Clustering switch cases From: Xinliang David Li To: Richard Guenther Cc: Ian Lance Taylor , "Paulo J. Matos" , gcc@gcc.gnu.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-System-Of-Record: true 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-08/txt/msg00415.txt.bz2 Another main thing missing is to consider profile information (if available) so that most frequent cases can be peeled out. David On Fri, Aug 27, 2010 at 8:03 AM, Richard Guenther wrote: > On Fri, Aug 27, 2010 at 4:47 PM, Ian Lance Taylor wrote: >> "Paulo J. Matos" writes: >> >>> In the first case, it generates a binary tree, and in the second two >>> jump tables. The jump tables solution is much more elegant (at least >>> in our situation), generating less code and being faster. >>> Now, what I am wondering is the reason why GCC doesn't try to cluster >>> the cases trying to find for clusters of contiguous values in the >>> switch. >>> >>> If there is no specific reason then I would implement such pass, which >>> would before expansion split switches according to value clustering, >>> since I find it would be a good code improvement. >>> >>> Currently GCC seems to only use jump table is the range of the switch >>> is not much bigger than its count, which works well in most cases >>> except when you have big switches with clusters of contiguous values >>> (like the first example I sent). >> >> I don't know of any specific reason not to look for clusters of switch >> cases. =A0The main issue would be the affect on compilation time. =A0If = you >> can do it with an algorithm which is linear in the number of cases, then >> I think it would be an acceptable optimization. > > In fact we might want to move switch optimization up to the tree level > (just because it's way easier to deal with there). =A0Thus, lower switch > to a mixture of binary tree & jump-tables (possibly using perfect > hashing). > > Richard. >