From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 62364 invoked by alias); 14 Aug 2017 08:32:49 -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 60241 invoked by uid 89); 14 Aug 2017 08:32:48 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.9 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=H*f:sk:CAFiYyc, sk:www.nex, sk:wwwnex X-HELO: mail-wm0-f44.google.com Received: from mail-wm0-f44.google.com (HELO mail-wm0-f44.google.com) (74.125.82.44) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 14 Aug 2017 08:32:37 +0000 Received: by mail-wm0-f44.google.com with SMTP id t201so32215196wmt.1 for ; Mon, 14 Aug 2017 01:32:37 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=jvxjZpzbdcSOsT/N2fsvtqXgypKAegiKfr19dPAzAQ8=; b=RqnQ2e/zZzg9ZyfH9rC4+Im0DSQAffEGMsVUrZwJuP8ArctT6Ltmilmb1hEeHcC2mf RGSqqn3+PetlSPr8AMphEytVG0z/C23V6Cro47Dguz1vpJzKt+T1PKhy8vd6UUe5EMy2 pEPw0xXkpcYV+UFjDUrD6FTam310Ct1T/vxn681lKdB4kUbW5MFNfaGyQj8FJtSjDj+u ebasRBsjodWBqaQxOj6b7Lpo4Ecj34Gz09Ua2UvpFFNaa3+JqLneP1w0Wf3vn+kpY8Fi xQJrW3PNzsuQv6xzaBKUSIoOyW/LKfAUObrSIvhdbx3OwF3bdB2VIGdaqo5sbvC5PaX1 wHQw== X-Gm-Message-State: AHYfb5g2Nb5KdpX5VzjJ4gdZTme+lqs+SQvR8j3bI7zxNgnRptRgjvyS d9zXrYafYKKi8Uz9dCZGmez/gH2rBA== X-Received: by 10.80.219.133 with SMTP id p5mr23996546edk.104.1502699555258; Mon, 14 Aug 2017 01:32:35 -0700 (PDT) MIME-Version: 1.0 Received: by 10.80.180.249 with HTTP; Mon, 14 Aug 2017 01:32:34 -0700 (PDT) In-Reply-To: References: From: Richard Biener Date: Mon, 14 Aug 2017 09:26:00 -0000 Message-ID: Subject: Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: GCC Patches , Jan Hubicka , Martin Jambor Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2017-08/txt/msg00853.txt.bz2 On Thu, Aug 10, 2017 at 9:50 AM, Martin Li=C5=A1ka wrote: > On 08/02/2017 01:51 PM, Richard Biener wrote: >> On Wed, Aug 2, 2017 at 1:20 PM, Martin Li=C5=A1ka 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 co= nvert the code >>> to expand gswitch statements on tree level. Currently the newly created= pass is executed >>> at the end of tree optimizations. >>> >>> My plan for future is to inspire in [1] and come up with some more soph= isticated switch >>> expansions. For that I've been working on a paper where I'll summarize = statistics based >>> on what I've collected in openSUSE distribution with specially instrume= nted GCC. If I'll be >>> happy I can also fit in to schedule of this year's Cauldron with a talk. >>> >>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tes= ts. >>> >>> Thoughts? >> >> First of all thanks. >> >> I think part of switch expansion moved to switch-conversion some time ago >> (emit_case_bit_tests). So maybe the full lowering should be in at least >> the same source file and it should maybe applied earlier for a subset of >> cases (very low number of cases for example). > > Hello. > > Agree! Eventually we should merge both files into a single one. I would p= refer to start > with new generic name of file (gimple-switch-low.c), which will eventuall= y eat content > of tree-switch-conversion.c. Is it acceptable approach? Hmm, but the existing "lowering" part is called from the switch-conversion pass. So I'm not sure a new file is good. > As Jeff already accepted the patch, I will install it as soon as an agree= ment in the question > will be done. > > Martin > >> >> Did you base the code on the RTL expansion code or did you re-write it f= rom >> scratch? >> >> No further comments sofar. >> >> Richard. >> >>> Martin >>> >>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf >>> >>> gcc/ChangeLog: >>> >>> 2017-07-31 Martin Liska >>> >>> * Makefile.in: Add gimple-switch-low.o. >>> * passes.def: Include pass_lower_switch. >>> * stmt.c (dump_case_nodes): Remove and move to >>> gimple-switch-low.c. >>> (case_values_threshold): Likewise. >>> (expand_switch_as_decision_tree_p): Likewise. >>> (emit_case_decision_tree): Likewise. >>> (expand_case): Likewise. >>> (balance_case_nodes): Likewise. >>> (node_has_low_bound): Likewise. >>> (node_has_high_bound): Likewise. >>> (node_is_bounded): Likewise. >>> (emit_case_nodes): Likewise. >>> * timevar.def: Add TV_TREE_SWITCH_LOWERING. >>> * tree-pass.h: Add make_pass_lower_switch. >>> * gimple-switch-low.c: New file. >>> >>> gcc/testsuite/ChangeLog: >>> >>> 2017-07-31 Martin Liska >>> >>> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in >>> switchlower. >>> * gcc.dg/tree-ssa/vrp104.c: Likewise. >>> --- >>> gcc/Makefile.in | 1 + >>> gcc/gimple-switch-low.c | 1226 ++++++++++++++++= ++++++++ >>> gcc/passes.def | 1 + >>> gcc/stmt.c | 861 ----------------- >>> gcc/testsuite/gcc.dg/tree-prof/update-loopch.c | 10 +- >>> gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +- >>> gcc/timevar.def | 1 + >>> gcc/tree-pass.h | 1 + >>> 8 files changed, 1236 insertions(+), 867 deletions(-) >>> create mode 100644 gcc/gimple-switch-low.c >>> >>> >