From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5545 invoked by alias); 3 Apr 2008 18:02:39 -0000 Received: (qmail 5537 invoked by uid 22791); 3 Apr 2008 18:02:38 -0000 X-Spam-Check-By: sourceware.org Received: from www.eyesopen.com (HELO mail.eyesopen.com) (65.19.16.51) by sourceware.org (qpsmtpd/0.31) with ESMTP; Thu, 03 Apr 2008 18:02:13 +0000 Received: from proglet (c-67-164-140-198.hsd1.nm.comcast.net [67.164.140.198]) (using TLSv1 with cipher RC4-MD5 (128/128 bits)) (No client certificate requested) by mail.eyesopen.com (Postfix) with ESMTP id C815DD50422; Thu, 3 Apr 2008 12:03:35 -0600 (MDT) Message-ID: <006e01c895b4$d74b5730$6650a8c0@proglet> From: "Roger Sayle" To: "Richard Guenther" , "GCC Patches" Cc: "Martin Jambor" References: <20080229160939.GA29616@dhcp64.suse.cz> <20080403123211.GA569@virgil.suse.cz> <84fc9c000804030602u1ccea89ai463591501ab26f95@mail.gmail.com> Subject: Re: [PATCH, middle-end] Switch initializations conversion (take four.1) Date: Thu, 03 Apr 2008 18:10:00 -0000 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook Express 6.00.2900.3138 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2008-04/txt/msg00299.txt.bz2 >> +/* >> + Switch initialization conversion >> + >> +The following pass changes simple initializations of scalars in a >> switch >> +statement into initializations from a static array. Obviously, the >> values must >> +be constant and known at compile time and a default branch must be >> +provided. For example, the following code: >> + >> + int a,b; >> + >> + switch (argc) >> + { >> + case 1: >> + case 2: >> + a_1 = 8; >> + b_1 = 6; >> + break; >> + case 3: >> + a_2 = 9; >> + b_2 = 5; >> + break; >> + case 12: >> + a_3 = 10; >> + b_3 = 4; >> + break; >> + default: >> + a_4 = 16; >> + b_4 = 1; >> + } >> + a_5 = PHI >> + b_5 = PHI >> + >> + >> +is changed into: >> + >> + static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, >> 1, 4}; >> + static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, >> 16, 16, >> + 16, 16, 10}; >> + >> + if (((unsigned) argc) - 1 < 11) >> + { >> + a_6 = CSWTCH02[argc - 1]; >> + b_6 = CSWTCH01[argc - 1]; >> + } >> + else >> + { >> + a_7 = 16; >> + b_7 = 1; >> + } >> + a_5 = PHI >> + b_b = PHI >> + >> +There are further constraints. Specifically, the range of values >> across all >> +case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) >> times >> +the number of the actual switch branches. >> +*/ By a strange coincidence, one of the switch statement transformations that I'll describe at the GCC summit this year is called "index mapping" which is used to improve the density/space requirements of sparse switch statements. When combined with "switch initialization converstion" and lower bound elimination, the resulting code would look like: static const char map[13] = { 0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }; static const int CSWITCH_a[4] = { 16, 8, 9, 10 }; static const int CSWITCH_b[4] = { 1, 6, 5, 4 }; int i; // This is potentially a conditional move instruction // even if a,b are floating point or BLKmode types. if ((unsigned) argc) <= 12) i = map[argc]; else i = 0; a = CSWITCH01[i]; b = CSWITCH02[i]; You'll notice that the resulting code scales better for sparse tables and also for more (and more complex) assignments. The indexes can even be permuted based upon frequency such that the hot case values map to consecutive indexes. More in Ottawa, Roger --