From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9058 invoked by alias); 9 Feb 2008 00:31:22 -0000 Received: (qmail 9047 invoked by uid 22791); 9 Feb 2008 00:31:20 -0000 X-Spam-Check-By: sourceware.org Received: from fk-out-0910.google.com (HELO fk-out-0910.google.com) (209.85.128.191) by sourceware.org (qpsmtpd/0.31) with ESMTP; Sat, 09 Feb 2008 00:31:02 +0000 Received: by fk-out-0910.google.com with SMTP id 26so4290583fkx.8 for ; Fri, 08 Feb 2008 16:31:00 -0800 (PST) Received: by 10.82.171.16 with SMTP id t16mr24213663bue.11.1202517059961; Fri, 08 Feb 2008 16:30:59 -0800 (PST) Received: by 10.82.177.10 with HTTP; Fri, 8 Feb 2008 16:30:59 -0800 (PST) Message-ID: <719dced30802081630q6fca95a4u747533463c9177f7@mail.gmail.com> Date: Sat, 09 Feb 2008 00:31:00 -0000 From: "Godmar Back" To: gcc-help@gcc.gnu.org Subject: optimization of switch statements on i386 In-Reply-To: <719dced30802081629g19f67f6fi76dfaa0ede35b7aa@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <719dced30802081629g19f67f6fi76dfaa0ede35b7aa@mail.gmail.com> Mailing-List: contact gcc-help-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-help-owner@gcc.gnu.org X-SW-Source: 2008-02/txt/msg00062.txt.bz2 Hi, I have a question regarding the compilation of switch statements for i386 targets. What heuristics or algorithm does gcc use to decide whether to use a binary search or a jump table? I'm specifically interested in switch statements for a dense range of values and in which the default: branch is unreachable. I've tried a number of approaches in order to obtain a jump table, but it seems gcc 4.x always ends up creating binary searches. For instance, I've tried casting the switch value to a limited range enum and placing a gcc_unreachable() in the default: case. A cursory inspection of the source code also didn't reveal any documentation of the strategy used. Does gcc have reason to believe that a binary search is always faster? If so, is this true for all variants of i386? Would it depend on the number of case arms? Thanks for any insights you could provide. - Godmar