From: "Martin Liška" <mliska@suse.cz>
To: Richard Biener <richard.guenther@gmail.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Loop unswitching: support gswitch statements.
Date: Wed, 1 Dec 2021 15:10:33 +0100 [thread overview]
Message-ID: <e879ec96-a221-a3e1-4d71-4b6f250e0470@suse.cz> (raw)
In-Reply-To: <CAFiYyc3q70YbFGOw=ybNDVJjg+751i7KVZph8YDRMucTPAgOUQ@mail.gmail.com>
On 11/30/21 12:17, Richard Biener wrote:
> On Mon, Nov 29, 2021 at 1:45 PM Martin Liška <mliska@suse.cz> wrote:
>>
>> On 11/26/21 09:12, Richard Biener wrote:
>>> On Wed, Nov 24, 2021 at 3:32 PM Martin Liška <mliska@suse.cz> wrote:
>>>>
>>>> On 11/24/21 15:14, Martin Liška wrote:
>>>>> It likely miscompiles gcc.dg/loop-unswitch-5.c, working on that..
>>>>
>>>> Fixed that in the updated version.
>>>
>>> Function level comments need updating it seems.
>>
>> I've done that.
>>
>>>
>>> +static unsigned
>>> +evaluate_insns (class loop *loop, basic_block *bbs,
>>> + predicate_vector &predicate_path,
>>> + auto_bb_flag &reachable_flag)
>>> +{
>>> + auto_vec<basic_block> worklist (loop->num_nodes);
>>> + worklist.quick_push (bbs[0]);
>>> ...
>>>
>>> so when adding gswitch support the easiest way to make
>>>
>>> + FOR_EACH_EDGE (e, ei, bb->succs)
>>> + {
>>> ...
>>> + {
>>> + worklist.safe_push (dest);
>>> + dest->flags |= reachable_flag;
>>>
>>> work is when the gcond/gswitch simplification would mark
>>> outgoing edges as (non-)executable. For gswitch this
>>> could be achieved by iterating over the case labels and
>>> intersecting that with the range while for gcond it's a
>>> matter of setting an edge flag instead of returning true/false.
>>
>> Exactly, it can be quite naturally added to the current patch.
>>
>>> I'd call the common function evaluate_control_stmt_using_entry_checks
>>> or so and invoke it on the last stmt of a block with >= 2 outgoing
>>> edges.
>>
>> Yes, I'll do it for the gswitch support patch.
>>
>>>
>>> We still seem to do the simplification work twice, once for costing
>>> and once for transform, but that's OK for now I guess.
>>>
>>> I think you want to clear_aux_for_blocks at the end of the pass.
>>
>> Called that.
>>
>>>
>>> Otherwise I like it - it seems you have some TODO around cost
>>> modeling. Did you try to do gswitch support ontop as I suggested
>>> to see if the general structure keeps working?
>>
>> I vanished and tested the patch. No, I don't have the gswitch support patch
>> as the current patch was reworked a few times.
>>
>> Can we please progress and have installed the suggested patch?
>
> I'd like to see the gswitch support - that's what was posted before stage3
> close, this patch on its own doesn't seem worth pushing for. That said,
> I have some comments below (and the already raised ones about how
> things might need to change with gswitch support). Is it so difficult to
> develop gswitch support as a separate change ontop of this?
I'm going to work on that in the upcoming days. When are you leaving for the Christmas
holidays :P ?
>
>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>
> +#include <utility>
>
> that's included unconditionally by system.h
Good.
>
> +/* The type represents a predicate path leading to a basic block. */
> +typedef auto_vec<std::pair<unswitch_predicate *, bool>> predicate_vector;
>
> +static bool tree_unswitch_single_loop (class loop *, int,
> + predicate_vector &predicate_path,
>
> I think we don't want to pass auto_vec by reference, instead auto_vec should
> decay to vec<> when passed around.
Ok.
>
> + unswitch_predicate *predicate = new unswitch_predicate (cond, lhs);
> + if (irange::supports_type_p (TREE_TYPE (lhs)) && CONSTANT_CLASS_P (rhs))
> + {
> + ranger->range_on_edge (predicate->true_range, edge_true, lhs);
> + predicate->false_range = predicate->true_range;
>
> - return cond;
> + if (!predicate->false_range.varying_p ()
> + && !predicate->false_range.undefined_p ())
> + predicate->false_range.invert ();
> + }
>
> is that correct? I would guess range_on_edge, for
>
> if (a > 10)
> if (a < 15)
> /* true */
> else
> /* false */
>
> figures [11, 14] on the true edge of if (a < 15) (considered the
> unswitch predicate),
> inverting that yields [0, 10] u [15, +INF] but that's at least
> sub-optimal for the
> else range. I think we want to call range_on_edge again to determine the range
> on the else branch?
No, as shown in the previous emails, Ranger is CFG sensitive and we should rely
on our irange merging.
>
> }
>
> -/* Simplifies COND using checks in front of the entry of the LOOP. Just very
> - simplish (sufficient to prevent us from duplicating loop in unswitching
> - unnecessarily). */
> +static void
> +combine_range (predicate_vector &predicate_path, tree index, irange
> &path_range)
> +{
>
> unless I misread the patch combine_range misses a comment.
>
> +evaluate_control_stmt_using_entry_checks (gimple *stmt,
> + predicate_vector &predicate_path)
> {
>
> so this function for ranger does combine all predicates on the predicate_path
> but for the symbolic evaluation it looks at the last predicate only?
Yes.
> I guess
> that's because other predicate simplification opportunities are applied already,
> correct?
Exactly.
> But doesn't that mean that the combine_range could be done once
> when we build the predicate vector instead of for each stmt? I'm just
> looking at the difference in treating both cases - if we first analyze the whole
> unswitching path (including all recursions) then we'd have to simplify all
> opportunities at once, so iterating over all predicates would make sense.
> Still merging ranges when pushing the to the predicate vector rather than
> for each stmt would make sense? We'd then have at most one predicate
> supported by irange for a specific lhs on the vector?
Yes, we can do better. I have a patch that appends to the path, and merges
with the previous irange that has equal LHS. Doing that, we can only first the
last predicate for a LHS and this one would have precise range (merged with all previous).
>
> + if (EDGE_COUNT (bb->succs) == 2)
> + {
> + gcond *cond = dyn_cast<gcond *> (last_stmt (bb));
> + if (cond != NULL)
> + {
>
> since gcond always has two edges the edge count test is redundant
> and removing it allows to indent less ;)
Lemme work on the gswitch support now.
Martin
>
> Richard.
>
>
>> Ready to be installed?
>> Thanks,
>> Martin
>>
>>>
>>> Thanks,
>>> Richard.
>>>
>>>>
>>>> Martin
next prev parent reply other threads:[~2021-12-01 14:10 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-15 8:46 Martin Liška
2021-09-19 16:50 ` Jeff Law
2021-09-28 11:50 ` Richard Biener
2021-09-28 20:39 ` Andrew MacLeod
2021-09-29 8:43 ` Richard Biener
2021-09-29 15:20 ` Andrew MacLeod
2021-09-29 15:28 ` Jeff Law
2021-09-29 15:59 ` Andrew MacLeod
2021-09-30 7:33 ` Richard Biener
2021-11-08 15:05 ` Martin Liška
2021-11-08 18:34 ` Andrew MacLeod
2021-11-08 19:45 ` Andrew MacLeod
2021-11-09 13:37 ` Richard Biener
2021-11-09 16:41 ` Andrew MacLeod
2021-11-10 7:52 ` Aldy Hernandez
2021-11-10 8:50 ` Richard Biener
2021-11-09 16:44 ` Martin Liška
2021-11-10 8:59 ` Richard Biener
2021-11-10 13:29 ` Martin Liška
2021-11-11 7:15 ` Richard Biener
2021-11-16 13:53 ` Martin Liška
2021-11-19 9:49 ` Richard Biener
2021-11-16 14:40 ` Martin Liška
2021-11-19 10:00 ` Richard Biener
2021-11-22 15:06 ` Martin Liška
2021-11-23 13:58 ` Richard Biener
2021-11-23 15:20 ` Martin Liška
2021-11-23 16:36 ` Martin Liška
2021-11-24 8:00 ` Richard Biener
2021-11-24 10:48 ` Martin Liška
2021-11-24 12:48 ` Richard Biener
2021-11-24 14:14 ` Martin Liška
2021-11-24 14:32 ` Martin Liška
2021-11-26 8:12 ` Richard Biener
2021-11-29 12:45 ` Martin Liška
2021-11-30 11:17 ` Richard Biener
2021-12-01 14:10 ` Martin Liška [this message]
2021-12-01 14:19 ` Richard Biener
2021-12-01 14:25 ` Martin Liška
2021-12-01 14:34 ` Richard Biener
2021-12-01 14:48 ` Martin Liška
2021-12-01 18:21 ` Andrew MacLeod
2021-12-02 11:45 ` Martin Liška
2021-12-02 12:01 ` Richard Biener
2021-12-02 13:10 ` Martin Liška
2021-12-02 13:46 ` Richard Biener
2021-12-08 21:06 ` Andrew MacLeod
2021-12-02 14:27 ` Andrew MacLeod
2021-12-02 16:02 ` Martin Liška
2021-12-03 14:09 ` Andrew MacLeod
2021-12-09 12:59 ` Martin Liška
2021-12-09 14:44 ` Andrew MacLeod
2021-12-09 13:02 ` Martin Liška
2022-01-05 12:34 ` Richard Biener
2022-01-06 15:11 ` Andrew MacLeod
2022-01-06 16:02 ` Martin Liška
2022-01-06 16:20 ` Andrew MacLeod
2022-01-06 16:35 ` Martin Liška
2022-01-06 16:42 ` Andrew MacLeod
2022-01-06 16:32 ` Andrew MacLeod
2022-01-06 16:30 ` Martin Liška
2022-01-13 16:01 ` Martin Liška
2022-01-14 7:23 ` Richard Biener
2021-11-25 10:38 ` Aldy Hernandez
2021-11-26 7:45 ` Richard Biener
2021-11-24 7:46 ` Richard Biener
2021-10-05 17:08 ` Andrew MacLeod
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=e879ec96-a221-a3e1-4d71-4b6f250e0470@suse.cz \
--to=mliska@suse.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.guenther@gmail.com \
/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).