From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22506 invoked by alias); 10 Jul 2006 09:39:07 -0000 Received: (qmail 22495 invoked by uid 22791); 10 Jul 2006 09:39:06 -0000 X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (199.232.76.164) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 10 Jul 2006 09:39:04 +0000 Received: from monty-python.gnu.org ([199.232.76.173]) by fencepost.gnu.org with esmtp (Exim 4.34) id 1FzsEI-000117-BR for gcc@gnu.org; Mon, 10 Jul 2006 05:39:02 -0400 Received: from Debian-exim by monty-python.gnu.org with spam-scanned (Exim 4.52) id 1FzsFH-0002Ad-TI for gcc@gnu.org; Mon, 10 Jul 2006 05:40:06 -0400 Received: from [62.91.19.101] (helo=mailgate.hob.de) by monty-python.gnu.org with esmtp (Exim 4.52) id 1FzsFH-0002AF-JG for gcc@gnu.org; Mon, 10 Jul 2006 05:40:03 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailgate.hob.de (Postfix) with ESMTP id 34C361D3B2 for ; Mon, 10 Jul 2006 11:38:54 +0200 (CEST) Received: from mailgate.hob.de ([127.0.0.1]) by localhost (mailgate.hob.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 27184-03 for ; Mon, 10 Jul 2006 11:38:54 +0200 (CEST) Received: from imap.hob.de (mail2.hob.de [172.25.1.102]) by mailgate.hob.de (Postfix) with ESMTP id 06CA01D3B0 for ; Mon, 10 Jul 2006 11:38:54 +0200 (CEST) Received: from hob.de (hildnecn-1.hob.de [172.22.80.122]) by imap.hob.de (Postfix on SuSE eMail Server 2.0) with ESMTP id 7EEC22CFC for ; Mon, 10 Jul 2006 11:38:53 +0200 (CEST) Message-ID: <44B2202D.3090203@hob.de> Date: Mon, 10 Jul 2006 09:39:00 -0000 From: Christian Hildner User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; de-DE; rv:1.0.2) Gecko/20030208 Netscape/7.02 MIME-Version: 1.0 To: gcc@gnu.org Subject: Switch statement optimization Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2006-07/txt/msg00155.txt.bz2 Hi, while dealing with autogenerated code I found that GCC often outputs compare trees instead of branch tables for switch statements. I found that GCC uses the density of case labels within their spanned range as the key criterion. If the density of labels is smaller than 10% (33% for size optimization) then GCC uses compare instruction rather than a branch table. What I am wondering is why no real cost estimation is done here. In my case there are around 200 to 1500 labels within the 16K range, so they are completely resolved to compares. In contrast the Intel compiler outputs branch tables more likely. The question now is whether the factors 10 (3 for size opt) have been found using any standard benchmark. And shouldn't at least the factor be optimized for a standard benchmark (like the upcoming SPEC CPU 2006 INT) if this simple linear method is used for modeling a logarithmic behavior? Or should a cost estimation be introduced? For size optimization there could be a quite accurate architecture dependent size estimation. Opinions, Comments? Christian PS: Please CC me.