From: Richard Biener <richard.guenther@gmail.com>
To: "Martin Liška" <mliska@suse.cz>
Cc: David Malcolm <dmalcolm@redhat.com>,
Jakub Jelinek <jakub@redhat.com>,
GCC Patches <gcc-patches@gcc.gnu.org>,
Jan Hubicka <hubicka@ucw.cz>
Subject: Re: [PATCH v2] Add if-chain to switch conversion pass.
Date: Mon, 16 Nov 2020 13:21:09 +0100 [thread overview]
Message-ID: <CAFiYyc1Z2J-MruAQ5aUaURi6ogT9JBfXGmFh2nMq2R+1R1+HVg@mail.gmail.com> (raw)
In-Reply-To: <ab606e0c-db7c-3e0c-bf6f-eaa8c08114f6@suse.cz>
On Mon, Nov 9, 2020 at 1:26 PM Martin Liška <mliska@suse.cz> wrote:
>
> On 11/6/20 1:31 PM, Richard Biener wrote:
> > On Fri, Oct 16, 2020 at 4:04 PM Martin Liška <mliska@suse.cz> 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 -fjump-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 conversion
> >>
> >> I'm also sending transformed chains for 'make all-host' (620 transformations).
> >> 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 :/
>
> All right, will fix 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?
>
> Sure.
>
> >
> > + if_chain *chain = 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 = single_pred_edge (gimple_bb (info->m_cond));
> > + condition_info *info2 = conditions_in_bbs.get (e->src);
> > + if (!info2 || info->m_ranges[0].exp != info2->m_ranges[0].exp)
> > + break;
> > +
> > + chain->m_entries.safe_push (info2);
> > + bitmap_set_bit (seen_bbs, e->src->index);
> > + info = info2;
> > + }
> >
> > so while we now record conditions per BB the above doesn't really
> > allow matching a binary tree.
>
> Yes. The pass currently only supports conditions of the following form:
> 1) index in {min, max}
> 2) index out of {min, max}
>
> which means one edge in form 1). I don't see how can be useful handling
> of a situation where both edges contain a such-chain? Can you please
> come up with a test-case that can be interesting?
Sth like
if (val < 10)
{
if (val == 1)
...
else if (val == 2)
...
else
default;
}
else
{
if (val == 99)
...
else if (val == 42)
...
else
gcc_unreachable ();
}
but the most trivial thing would be to feed the pass the
balanced-tree generated by switch expansion where I
would expect us to be able to detect it as the original switch again.
> > 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.
>
> Installed to master.
>
> Martin
>
> >
> > Thanks,
> > Richard.
> >
> >
> >> Thoughts?
> >> Thanks,
> >> Martin
>
next prev parent reply other threads:[~2020-11-16 12:21 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-11-04 14:23 [PATCH] " Martin Liška
2019-11-04 14:49 ` Jakub Jelinek
2019-11-05 12:38 ` Richard Biener
2019-11-06 21:03 ` Bernhard Reutner-Fischer
2019-11-14 9:44 ` Martin Liška
2019-11-14 12:35 ` Bernhard Reutner-Fischer
2019-11-14 9:41 ` Martin Liška
2019-11-14 10:48 ` Richard Biener
2019-11-15 13:56 ` Martin Liška
2020-09-01 11:47 ` Martin Liška
2020-09-01 14:50 ` David Malcolm
2020-09-02 11:53 ` Martin Liška
2020-09-21 8:55 ` Martin Liška
2020-09-24 12:41 ` Richard Biener
2020-09-25 14:05 ` Martin Liška
2020-09-29 8:46 ` Richard Biener
2020-10-02 13:26 ` Martin Liška
2020-10-02 14:19 ` Andrew MacLeod
2020-10-06 12:09 ` Martin Liška
2020-10-06 12:56 ` Andrew MacLeod
2020-10-06 13:09 ` Martin Liška
2020-10-06 13:23 ` Andrew MacLeod
2020-10-06 13:41 ` Richard Biener
2020-10-02 13:23 ` Martin Liška
2020-10-06 7:47 ` Richard Biener
2020-10-06 13:48 ` Martin Liška
2020-10-06 14:12 ` Jakub Jelinek
2020-10-12 12:39 ` Martin Liška
2020-10-12 13:00 ` Jakub Jelinek
2020-10-14 18:09 ` Andrew MacLeod
2020-10-07 8:00 ` Richard Biener
2020-10-12 12:44 ` Martin Liška
2020-10-12 13:01 ` Martin Liška
2020-10-15 12:38 ` Richard Biener
2020-10-16 14:04 ` [PATCH v2] " Martin Liška
2020-11-06 12:31 ` Richard Biener
2020-11-09 12:26 ` Martin Liška
2020-11-16 12:21 ` Richard Biener [this message]
2020-11-18 12:25 ` Martin Liška
2020-11-19 14:46 ` Richard Biener
2020-11-20 8:57 ` Martin Liška
2020-11-20 14:37 ` Richard Biener
2020-11-27 15:07 ` Martin Liška
2020-12-01 10:34 ` Richard Biener
2020-12-01 13:57 ` [PATCH] if-to-switch: Support chain with 2 BBs Martin Liška
2020-12-01 22:14 ` Jeff Law
2019-11-13 11:32 ` [PATCH] Add if-chain to switch conversion pass Martin Liška
2019-11-13 16:14 ` Michael Matz
2019-11-14 10:07 ` Martin Liška
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAFiYyc1Z2J-MruAQ5aUaURi6ogT9JBfXGmFh2nMq2R+1R1+HVg@mail.gmail.com \
--to=richard.guenther@gmail.com \
--cc=dmalcolm@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=jakub@redhat.com \
--cc=mliska@suse.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).