On Wed, Dec 1, 2021 at 3:10 PM Martin Liška <mli...@suse.cz> wrote:
>
> On 11/30/21 12:17, Richard Biener wrote:
> > On Mon, Nov 29, 2021 at 1:45 PM Martin Liška <mli...@suse.cz> wrote:
> >>
> >> On 11/26/21 09:12, Richard Biener wrote:
> >>> On Wed, Nov 24, 2021 at 3:32 PM Martin Liška <mli...@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 ?
Wednesday next week is my first day off, but I might peek into mails
now and then.
> >
> >> 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.
I don't understand. You do
> > + 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 ();
> > + }
which is compute the range of 'lhs' on edge_true into predicate->true_range,
assign that same range to ->false_range and then invert it to get the
range on the false_edge. What I am saying is that for better precision
you should do
ranger->range_on_edge (predicate->false_range, edge_false, lhs);
rather than prematurely optimize this to the inversion of the true range
since yes, ranger is CFG sensitive and only the _last_ predicate on a
long CFG path is actually inverted.
What am I missing?
>
> >
> > }
> >
> > -/* 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
>
