From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 106948 invoked by alias); 3 Aug 2017 13:20:19 -0000 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 Received: (qmail 106930 invoked by uid 89); 3 Aug 2017 13:20:18 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=Hx-languages-length:2081, honest, HContent-Transfer-Encoding:8bit X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 03 Aug 2017 13:20:17 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id DC27754901F; Thu, 3 Aug 2017 15:20:13 +0200 (CEST) Date: Thu, 03 Aug 2017 13:20:00 -0000 From: Jan Hubicka To: Richard Biener Cc: Steven Bosscher , Martin =?iso-8859-2?Q?Li=B9ka?= , GCC Patches , Martin Jambor Subject: Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level. Message-ID: <20170803132013.GA332@kam.mff.cuni.cz> References: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-2 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-SW-Source: 2017-08/txt/msg00293.txt.bz2 > On Thu, Aug 3, 2017 at 2:52 PM, Steven Bosscher wrote: > > On Wed, Aug 2, 2017 at 1:20 PM, Martin Li¹ka wrote: > >> Hello. > >> > >> After some discussions with Honza, I've decided to convert current code in stmt.c that > >> is responsible for switch expansion. More precisely, I would like to convert the code > >> to expand gswitch statements on tree level. Currently the newly created pass is executed > >> at the end of tree optimizations. > > > > Hah, something I promissed myself (and others) to do years ago! Thanks > > thanks thanks! :-) > > > > The end of the gimple optimizations is seems late for the lowering. > > Before there were gimple optimizations, switch lowering was part of > > the first compiler pass (to generate RTL from the front end) *before* > > all code transformation passes ("optimizations" ;-). Because the > > lowering of switch statements was rewritten as a gimple lowering pass, > > it now runs *after* optimizations. But to be honest, I can't think of > > any optimization opportunities exposed by lowering earlier than at the > > end of gimple optimizations. Years ago there was some RTL jump > > threading still done after lowering of small switch statements, but I > > can't find the related PRs anymore. > > I think the main reason for not doing it early is the benefit is small > (unless it is GIMPLE optimizations triggering) and we can't get rid of > switches completely because we eventually have to support casei RTL expansion. > (and no, computed goto with an array of label addresses at GIMPLE is really > too ugly ;)) Also later in optimization you have better idea of value ranges and you can shape the decision tree better for given context. In theory at least ;) One thing that would benefit from earlier expansion is code size/runtime estimation for inlining. But perhaps we could just run the algorithm to see how hard the switch is when we decide on its size (what is there right now is bit lame) Honza > > Richard.