From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x542.google.com (mail-ed1-x542.google.com [IPv6:2a00:1450:4864:20::542]) by sourceware.org (Postfix) with ESMTPS id B59473988801 for ; Fri, 6 Nov 2020 12:31:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org B59473988801 Received: by mail-ed1-x542.google.com with SMTP id e18so1079452edy.6 for ; Fri, 06 Nov 2020 04:31:38 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=GnvbUWOY0uN4oujeIm+4uIv5iuB6HUlBKwAvw3WxbhU=; b=N5LpY439IwqX7ehrWCZxJipZ2/kxcPCmrmxDfndLt8kqXyGfifFyLNRyaqGOOygmYU mjP4Oz9SEusmN5DZEjs0SwCzF0lfOiPg8PBL7jbj/paqMg0q8XglY8xYWuKYq+THz0QN JAeE3x6PEX9dhzm37O4tC+jlu0UkSHowtKalxATup/LFQnf72uWA8j2Pm4dla0kBQb6y mPGuaehwkf/UVuPLZ1XHnvafVofDRG4tHODlCt0KBqVh1U77ebKTlEf4aGXTHBCJ/IR6 e82xzymUT0m91dSKWGjDLLrS1mokBcIjOnMZgmYmtxuV+IAdzqNCnYn/IuEoiEGU+VXM Xp4Q== X-Gm-Message-State: AOAM531HgczKp/I5J36RNTQiDQN/IFQgPZNFwzbg72wh99N9fuVvOCD/ 2ePR0UQ2ayRJakKupBpAJMsPnA4JvCT0hykXZrQ= X-Google-Smtp-Source: ABdhPJybG9Z1IYzy84ufBFcNRiEs8XuOouyQtha8TXZbToa8r/s+Dkv37AgNd2Api7dF+8O7GX3jQ0dprKmxOZJ9fnc= X-Received: by 2002:a05:6402:716:: with SMTP id w22mr1808216edx.214.1604665897690; Fri, 06 Nov 2020 04:31:37 -0800 (PST) MIME-Version: 1.0 References: <2c3db526-cac6-4eeb-4afb-12024f8d5af2@suse.cz> <20191104144851.GJ4650@tucnak> <6169f91a-4884-55f5-c76f-ea1dae11d996@suse.cz> <35eb0279-77d8-36f8-3ab7-afb9ae97fdb3@suse.cz> <42c91f11-c1a6-3ae4-08da-0a0b77f63b80@suse.cz> <72541e13d26f92577637b8f0e23d82435f35ddea.camel@redhat.com> <46e9e574-80f8-3cce-3fcf-dbc8205e74ae@suse.cz> <0f418e79-d46b-5577-ebdf-dbc29eed8057@suse.cz> In-Reply-To: <0f418e79-d46b-5577-ebdf-dbc29eed8057@suse.cz> From: Richard Biener Date: Fri, 6 Nov 2020 13:31:26 +0100 Message-ID: Subject: Re: [PATCH v2] Add if-chain to switch conversion pass. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: David Malcolm , Jakub Jelinek , GCC Patches , Jan Hubicka Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 Nov 2020 12:31:40 -0000 On Fri, Oct 16, 2020 at 4:04 PM Martin Li=C5=A1ka wrote: > > Hello. > > There's another version of the patch that should be based on what > I discussed with Richi and Jakub: > > - the first patch introduces a new option -fbit-tests that analogue to -f= jump-tables > and will control the new if-to-switch conversion pass > > - the second patch adds the pass > - I share code with tree-ssa-reassoc.c (range_entry and init_range_entry) > - a local discovery phase is run first > - later than these local BBs are chained into a candidate list for the co= nversion > > I'm also sending transformed chains for 'make all-host' (620 transformati= ons). > Patch can bootstrap on x86_64-linux-gnu and survives regression tests. -static bool +bool no_side_effect_bb (basic_block bb) { exporting this with this name is dangerous I think because the function seems to allow side-effects in the last stmt - not sure exactly what it tries to allow - there's no comment to that :/ + free (rpo); + free_dominance_info (CDI_DOMINATORS); + + if (!all_candidates.is_empty ()) + mark_virtual_operands_for_renaming (fun); please avoid freeing dominance info when there was no change done (move it to the !all_candidates.is_empty () block). + basic_block bb; + FOR_EACH_BB_FN (bb, fun) + find_conditions (bb, &conditions_in_bbs); + if we didn't find any conditions (or found just one?) we can elide the rest of the function, no? + if_chain *chain =3D new if_chain (); + chain->m_entries.safe_push (info); + /* Try to find a chain starting in this BB. */ + while (true) + { + if (!single_pred_p (gimple_bb (info->m_cond))) + break; + edge e =3D single_pred_edge (gimple_bb (info->m_cond)); + condition_info *info2 =3D conditions_in_bbs.get (e->src); + if (!info2 || info->m_ranges[0].exp !=3D info2->m_ranges[0].e= xp) + break; + + chain->m_entries.safe_push (info2); + bitmap_set_bit (seen_bbs, e->src->index); + info =3D info2; + } so while we now record conditions per BB the above doesn't really allow matching a binary tree. What I was thinking of is to record if_chain * per BB as well and look at successors, thus (pseudo-code) if (block ends in cond) if (if_chain on true edge && if_chain on false edge) try merge else if (if_chain on true edge && this-cond tests same var) try merge else if (if_chan on false edge && ...) try merge record if_chain for block where merging would eventually detach the if_chains from the successors. For now we'd just handle the true (and maybe false) edge combos to handle linear chains. Walking reverse RPO (I'm not 100% sure reverse RPO is what we want here, but guess it will work fine for now) will gather chains accordingly. When merging from a successor to a BB fails we push the successor chain to the candidate list. +/* Algorithm of the pass runs in the following steps: + a) We walk basic blocks in DOMINATOR order so that we first reach + a first condition of a future switch. + b) We follow false edges of a if-else-chain and we record chain + of GIMPLE conditions. These blocks are only used for comparison + of a common SSA_NAME and we do not allow any side effect. + c) We remove all basic blocks (except first) of such chain and + GIMPLE switch replaces the condition in the first basic block. + d) We move all GIMPLE statements in the removed blocks into the + first one. */ the overall comment is now a bit out-of-date? Please remove the PHI mapping as I outlined in earlier review. The 0001-Add-fbit-tests-option.patch is OK for trunk. Thanks, Richard. > Thoughts? > Thanks, > Martin