From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26042 invoked by alias); 9 Feb 2008 02:05:35 -0000 Received: (qmail 26029 invoked by uid 22791); 9 Feb 2008 02:05:34 -0000 X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.33.17) by sourceware.org (qpsmtpd/0.31) with ESMTP; Sat, 09 Feb 2008 02:05:14 +0000 Received: from zps75.corp.google.com (zps75.corp.google.com [172.25.146.75]) by smtp-out.google.com with ESMTP id m19250dZ006038; Sat, 9 Feb 2008 02:05:00 GMT Received: from smtp.corp.google.com (spacemonkey2.corp.google.com [192.168.120.114]) by zps75.corp.google.com with ESMTP id m1924vLN003326 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Fri, 8 Feb 2008 18:04:57 -0800 Received: from localhost.localdomain.google.com (69-36-227-131.cust.layer42.net [69.36.227.131] (may be forged)) (authenticated bits=0) by smtp.corp.google.com (8.13.8/8.13.8) with ESMTP id m1924jE9017730 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Fri, 8 Feb 2008 18:04:56 -0800 To: "Godmar Back" Cc: gcc-help@gcc.gnu.org Subject: Re: optimization of switch statements on i386 References: <719dced30802081629g19f67f6fi76dfaa0ede35b7aa@mail.gmail.com> <719dced30802081630q6fca95a4u747533463c9177f7@mail.gmail.com> From: Ian Lance Taylor Date: Sat, 09 Feb 2008 02:05:00 -0000 In-Reply-To: <719dced30802081630q6fca95a4u747533463c9177f7@mail.gmail.com> Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-IsSubscribed: yes 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/msg00065.txt.bz2 "Godmar Back" writes: > 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. Look at expand_case in gcc/stmt.c. > 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? No, it uses a heuristic to choose. Probably the most relevant one here is that if the difference between the maximum and minimum case labels is more than 10 * the number of case labels, gcc will use comparisons rather than a table. > If so, is this true for all variants of i386? I believe that all i386 variants are handled in the same way. > Would it depend on the number of case arms? Yes. Ian