From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3426 invoked by alias); 27 Aug 2010 13:40:18 -0000 Received: (qmail 3415 invoked by uid 22791); 27 Aug 2010 13:40:17 -0000 X-SWARE-Spam-Status: No, hits=-0.6 required=5.0 tests=AWL,BAYES_50,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-qy0-f175.google.com (HELO mail-qy0-f175.google.com) (209.85.216.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 27 Aug 2010 13:40:05 +0000 Received: by qyk8 with SMTP id 8so717161qyk.20 for ; Fri, 27 Aug 2010 06:40:03 -0700 (PDT) Received: by 10.224.29.10 with SMTP id o10mr342007qac.227.1282916403002; Fri, 27 Aug 2010 06:40:03 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.19.193 with HTTP; Fri, 27 Aug 2010 06:39:41 -0700 (PDT) From: "Paulo J. Matos" Date: Fri, 27 Aug 2010 13:49:00 -0000 Message-ID: Subject: Clustering switch cases To: gcc@gcc.gnu.org Content-Type: text/plain; charset=UTF-8 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/msg00391.txt.bz2 Hi, I have been analysing the gcc4.4 code due to the way it's handling: 1 extern void f(const char *); 2 extern void g(int); 3 4 #define C(n) case n: f(#n); break 5 6 void g(int n) 7 { 8 switch(n) 9 { 10 C(0); C(1); C(2); C(3); C(4); C(5); C(6); C(7); C(8); C(9); 11 C(10); C(11); C(12); C(13); C(14); C(15); C(16); C(17); C(18); C(19); 12 C(20); C(21); C(22); C(23); C(24); C(25); C(26); C(27); C(28); C(29); 13 14 C(1000); C(1001); C(1002); C(1003); C(1004); C(1005); C(1006); C(1007); C(1008); C(1009); 15 } 16 } The interesting thing about this is that GCC generates much better code if I do: 1 extern void f(const char *); 2 extern void g(int); 3 4 #define C(n) case n: f(#n); break 5 6 void g(int n) 7 { 8 switch(n) 9 { 10 C(0); C(1); C(2); C(3); C(4); C(5); C(6); C(7); C(8); C(9); 11 C(10); C(11); C(12); C(13); C(14); C(15); C(16); C(17); C(18); C(19); 12 C(20); C(21); C(22); C(23); C(24); C(25); C(26); C(27); C(28); C(29); 13 } 14 switch(n) 15 { 16 C(1000); C(1001); C(1002); C(1003); C(1004); C(1005); C(1006); C(1007); C(1008); C(1009); 17 } 18 } 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). Any comments on this would be appreciated. -- PMatos