skip vector profiles multiple exits

skip vector profiles multiple exits

[Tamar Christina]

Hi Honza,

I wasn't sure what to do here so I figured I'd ask.

In adding support for multiple exits to the vectorizer I didn't know how to update this bit:

https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-vect-loop-manip.cc#L3363

Essentially, if skip_vector (i.e. not enough iteration to enter the vector loop) then the
previous code would update the new probability to be the same as that of the
exit edge.  This made sense because that's the only edge which could bring you to
the next loop preheader.

With multiple exits this is no longer the case since any exit can bring you to the
Preaheader node.  I figured the new counts should simply be the sum of all exit
edges.  But that gives quite large count values compared to the rest of the loop.

I then thought I would need to scale the counts by the probability of the edge
being taken.  The problem here is that the probabilities don't end up to 100%

so the scaled counts also looked kinda wonkey.   Any suggestions?

If you want some small examples to look at, testcases
./gcc/testsuite/gcc.dg/vect/vect-early-break_90.c to ./gcc/testsuite/gcc.dg/vect/vect-early-break_93.c
should be relevant here.

Thanks,
Tamar

Re: skip vector profiles multiple exits

[Jan Hubicka]

> Hi Honza,
Hi,
> 
> I wasn't sure what to do here so I figured I'd ask.
> 
> In adding support for multiple exits to the vectorizer I didn't know how to update this bit:
> 
> https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-vect-loop-manip.cc#L3363
> 
> Essentially, if skip_vector (i.e. not enough iteration to enter the vector loop) then the
> previous code would update the new probability to be the same as that of the
> exit edge.  This made sense because that's the only edge which could bring you to
> the next loop preheader.
> 
> With multiple exits this is no longer the case since any exit can bring you to the
> Preaheader node.  I figured the new counts should simply be the sum of all exit
> edges.  But that gives quite large count values compared to the rest of the loop.
The sum of all exit counts (not probabilities) relative to header count should
give you estimated probability that the loop iterates at any given
iteration.  I am not sure how good estimate this is for loop
preconditioning to be true (without profile histograms it is really hard
to tell).
> 
> I then thought I would need to scale the counts by the probability of the edge
> being taken.  The problem here is that the probabilities don't end up to 100%

So you are summing exit_edge->count ()?
I am not sure how useful would be summit probabilities since they are
conditional (relative to probability of entering BB you go to).
How complicated CFG we now handle with vectorization?

Honza
> 
> so the scaled counts also looked kinda wonkey.   Any suggestions?
> 
> If you want some small examples to look at, testcases
> ./gcc/testsuite/gcc.dg/vect/vect-early-break_90.c to ./gcc/testsuite/gcc.dg/vect/vect-early-break_93.c
> should be relevant here.
> 
> Thanks,
> Tamar

RE: skip vector profiles multiple exits

[Tamar Christina]

> -----Original Message-----
> From: Jan Hubicka <hubicka@ucw.cz>
> Sent: Friday, December 29, 2023 10:32 PM
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: rguenther@suse.de; GCC Patches <gcc-patches@gcc.gnu.org>; nd
> <nd@arm.com>
> Subject: Re: skip vector profiles multiple exits
> 
> > Hi Honza,
> Hi,
> >
> > I wasn't sure what to do here so I figured I'd ask.
> >
> > In adding support for multiple exits to the vectorizer I didn't know how to update
> this bit:
> >
> > https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-vect-loop-
> manip.cc#L3363
> >
> > Essentially, if skip_vector (i.e. not enough iteration to enter the vector loop) then
> the
> > previous code would update the new probability to be the same as that of the
> > exit edge.  This made sense because that's the only edge which could bring you to
> > the next loop preheader.
> >
> > With multiple exits this is no longer the case since any exit can bring you to the
> > Preaheader node.  I figured the new counts should simply be the sum of all exit
> > edges.  But that gives quite large count values compared to the rest of the loop.
> The sum of all exit counts (not probabilities) relative to header count should
> give you estimated probability that the loop iterates at any given
> iteration.  I am not sure how good estimate this is for loop
> preconditioning to be true (without profile histograms it is really hard
> to tell).
Happy new years!

Ah, so I need to subtract the loop header from the sum? I'll try 😊

> >
> > I then thought I would need to scale the counts by the probability of the edge
> > being taken.  The problem here is that the probabilities don't end up to 100%
> 
> So you are summing exit_edge->count ()?
> I am not sure how useful would be summit probabilities since they are
> conditional (relative to probability of entering BB you go to).
> How complicated CFG we now handle with vectorization?
> 

Yeah I as trying to sum the edge counts.  The CFG can get quite complicated
because we allow vectorization of any arbitrary number of exits as long as
that exit leaves the loop body.

In this current version we force everything to the scalar epilog, so the merge
block can get any number of incoming edges now.  Aside from this we still
support versioning and skip_epilog so you have the additional edges coming
in from there too.

Regards,
Tamar

> Honza
> >
> > so the scaled counts also looked kinda wonkey.   Any suggestions?
> >
> > If you want some small examples to look at, testcases
> > ./gcc/testsuite/gcc.dg/vect/vect-early-break_90.c to
> ./gcc/testsuite/gcc.dg/vect/vect-early-break_93.c
> > should be relevant here.
> >
> > Thanks,
> > Tamar