llvm dev - Jan 2016 - Skip redundant checks in AliasSet::aliasesUnknownInst

Thank you for the idea! Could you please explain it? If I’m not
mistaken, you advise to insert the unknown insts of an every AS from
AliasSetTracker::add(const AliasSetTracker &AST) into a smallptrset
and consequently append it to merged alias sets from
AliasSetTracker::findAliasSetForUnknownInst. I think that Philip
proposed something similar to your approach in
https://llvm.org/bugs/show_bug.cgi?id=23077.

2016-01-24 22:44 GMT+05:00 Daniel Berlin <dberlin at
dberlin.org>:
> It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or
> DenseSet (if you can't do the others).
>
> Otherwise, even with your patch, we are still wasting time traversing and
> copying and .... the unknown instructions.
>
> If that doesn't work, I suspect the way you get dupes is through
mergeSetIn,
> so you also could probably just change:
>
> 00061   } else if (ASHadUnknownInsts) {
> 00062     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),
> AS.UnknownInsts.end());
> 00063     AS.UnknownInsts.clear();
> 00064   }
>
>
>
> You could insert the current unknown insts into a smallptrset, and then
only
> append them to UnknownInsts if they aren't in the set.
>
> This should remove your dupes.
>
>
>
> On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Dear llvm contributors,
>>
>> Could you please advise me how to skip
>> checks, which are performed in AliasSet::aliasesUnknownInst, of
>> unknown instructions from different alias sets of an alias set tracker
>> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
>> &AST)’?
>>
>> If this wasn’t available at the moment and someone could review me, I
>> would try to implement it. A temporary patch can be found attached
>> (for example, ViewedInst can become a second parameter of
>> AliasSetTracker::addUnknown ). It
>> passes the LLVM regression tests and helps to reduce the runtime of
>> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime
of
>> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
>> out.opt2.ll can be found on the following link
>> https://llvm.org/bugs/show_bug.cgi?id=23077).
>>
>> Thank you for the attention!
>>
>> --
>>                                     Cheers, Roman Gareev.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>


-- 
                                    Cheers, Roman Gareev.

On Wed, Jan 27, 2016 at 1:27 AM, Roman Gareev <gareevroman at gmail.com>
wrote:
> Thank you for the idea! Could you please explain it?

Which part are you having trouble with, so i know where to concetrate?

> If I’m not
> mistaken, you advise to insert the unknown insts of an every AS from
> AliasSetTracker::add(const AliasSetTracker &AST) into a smallptrset
> and consequently append it to merged alias sets from
> AliasSetTracker::findAliasSetForUnknownInst.

Well, no. This is not the only place duplication can occur, because the
merging of unknownInsts can occur through findAliasSetForPointer as well,
if that AS has unknown instructions.


See below.

> I think that Philip
> proposed something similar to your approach in
> https://llvm.org/bugs/show_bug.cgi?id=23077.
>
You reported that you are finding duplicates on the unknown inst list.

The duplicates occur because we are not de-duplicating the unknowninst
lists attached to each AS when we merge them.

If you look at the code in mergeSetIn (used by both findAliasSetForPointer
and findAliasSetForUnknownInst) you can see when we merge AS's,  we simply
append the list of unknowninsts from one AS into the "destination" AS,
without ever checking *whether that destination AS already contains any of
the same instructions on the unknowninst list*.

So things end up on the unknowninst lists multiple times.

There are many ways to solve this:

1. Don't use lists at all for unknowninsts for each AS, use SmallSets or
SmallPtrSets instead.   Then any normal merging will deduplicate them for
you.
or
2. When merging AS's, deduplicate the unknown inst list by temporarily
storing it in a set.


#2 assumes that "merging AS's" is the only place that is causing
duplicates.

> 2016-01-24 22:44 GMT+05:00 Daniel Berlin <dberlin at dberlin.org>:
> > It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet,
or
> > DenseSet (if you can't do the others).
> >
> > Otherwise, even with your patch, we are still wasting time traversing
and
> > copying and .... the unknown instructions.
> >
> > If that doesn't work, I suspect the way you get dupes is through
> mergeSetIn,
> > so you also could probably just change:
> >
> > 00061   } else if (ASHadUnknownInsts) {
> > 00062     UnknownInsts.insert(UnknownInsts.end(),
> AS.UnknownInsts.begin(),
> > AS.UnknownInsts.end());
> > 00063     AS.UnknownInsts.clear();
> > 00064   }
> >
> >
> >
> > You could insert the current unknown insts into a smallptrset, and
then
> only
> > append them to UnknownInsts if they aren't in the set.
> >
> > This should remove your dupes.
> >
> >
> >
> > On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> >>
> >> Dear llvm contributors,
> >>
> >> Could you please advise me how to skip
> >> checks, which are performed in AliasSet::aliasesUnknownInst, of
> >> unknown instructions from different alias sets of an alias set
tracker
> >> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
> >> &AST)’?
> >>
> >> If this wasn’t available at the moment and someone could review
me, I
> >> would try to implement it. A temporary patch can be found attached
> >> (for example, ViewedInst can become a second parameter of
> >> AliasSetTracker::addUnknown ). It
> >> passes the LLVM regression tests and helps to reduce the runtime
of
> >> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the
runtime of
> >> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms
(out.opt.ll and
> >> out.opt2.ll can be found on the following link
> >> https://llvm.org/bugs/show_bug.cgi?id=23077).
> >>
> >> Thank you for the attention!
> >>
> >> --
> >>                                     Cheers, Roman Gareev.
> >>
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> llvm-dev at lists.llvm.org
> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >>
> >
>
>
>
> --
>                                     Cheers, Roman Gareev.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160127/0b205b68/attachment.html>

On 01/27/2016 07:53 AM, Daniel Berlin wrote:
>
>
> On Wed, Jan 27, 2016 at 1:27 AM, Roman Gareev <gareevroman at gmail.com 
> <mailto:gareevroman at gmail.com>> wrote:
>
>     Thank you for the idea! Could you please explain it?
>
>
> Which part are you having trouble with, so i know where to concetrate?
>
>     If I’m not
>     mistaken, you advise to insert the unknown insts of an every AS from
>     AliasSetTracker::add(const AliasSetTracker &AST) into a smallptrset
>     and consequently append it to merged alias sets from
>     AliasSetTracker::findAliasSetForUnknownInst.
>
>
> Well, no. This is not the only place duplication can occur, because 
> the merging of unknownInsts can occur through findAliasSetForPointer 
> as well, if that AS has unknown instructions.
>
>
> See below.
>
>     I think that Philip
>     proposed something similar to your approach in
>     https://llvm.org/bugs/show_bug.cgi?id=23077.
>
>
> You reported that you are finding duplicates on the unknown inst list.
I don't see this in the bug report?
>
> The duplicates occur because we are not de-duplicating the unknowninst 
> lists attached to each AS when we merge them.
Danny, I think your analysis is incorrect. If we're merging two 
AliasSets, we have to consider where AliasSets can come from.  Each 
instruction initially ends up in exactly one AliasSet.  As a result, 
when we're merging two ASTs (which covered different loops/instructions 
by definition), we should never see the same instruction twice when 
merging AliasSets.

However, using a set to represent the unknown insts would still be 
useful.  In particular, it would give us a fastpath for determining if a 
particular unknown instruction was already in an alias set.  If we 
explicitly merged AliasSets from different ASTs (i.e. add all unknown at 
once to a single AliasSet, and then merge if needed), this would give us 
a fast way to avoid redundant aliasing checks when looking for things 
which need merged.
>
> If you look at the code in mergeSetIn (used by both 
> findAliasSetForPointer and findAliasSetForUnknownInst) you can see 
> when we merge AS's,  we simply append the list of unknowninsts from 
> one AS into the "destination" AS, without ever checking *whether
that
> destination AS already contains any of the same instructions on the 
> unknowninst list*.
>
> So things end up on the unknowninst lists multiple times.
>
> There are many ways to solve this:
>
> 1. Don't use lists at all for unknowninsts for each AS, use SmallSets 
> or SmallPtrSets instead.   Then any normal merging will deduplicate 
> them for you.
> or
> 2. When merging AS's, deduplicate the unknown inst list by temporarily 
> storing it in a set.
>
>
> #2 assumes that "merging AS's" is the only place that is
causing
> duplicates.
>
>
>     2016-01-24 22:44 GMT+05:00 Daniel Berlin <dberlin at dberlin.org
>     <mailto:dberlin at dberlin.org>>:
>     > It sounds like UnknownInsts should really be a SmallSet,
>     SmallPtrSet, or
>     > DenseSet (if you can't do the others).
>     >
>     > Otherwise, even with your patch, we are still wasting time
>     traversing and
>     > copying and .... the unknown instructions.
>     >
>     > If that doesn't work, I suspect the way you get dupes is
through
>     mergeSetIn,
>     > so you also could probably just change:
>     >
>     > 00061   } else if (ASHadUnknownInsts) {
>     > 00062     UnknownInsts.insert(UnknownInsts.end(),
>     AS.UnknownInsts.begin(),
>     > AS.UnknownInsts.end());
>     > 00063     AS.UnknownInsts.clear();
>     > 00064   }
>     >
>     >
>     >
>     > You could insert the current unknown insts into a smallptrset,
>     and then only
>     > append them to UnknownInsts if they aren't in the set.
>     >
>     > This should remove your dupes.
>     >
>     >
>     >
>     > On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev
>     > <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>     >>
>     >> Dear llvm contributors,
>     >>
>     >> Could you please advise me how to skip
>     >> checks, which are performed in AliasSet::aliasesUnknownInst,
of
>     >> unknown instructions from different alias sets of an alias set
>     tracker
>     >> that is a parameter of ‘AliasSetTracker::add(const
AliasSetTracker
>     >> &AST)’?
>     >>
>     >> If this wasn’t available at the moment and someone could
review
>     me, I
>     >> would try to implement it. A temporary patch can be found
attached
>     >> (for example, ViewedInst can become a second parameter of
>     >> AliasSetTracker::addUnknown ). It
>     >> passes the LLVM regression tests and helps to reduce the
runtime of
>     >> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the
>     runtime of
>     >> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms
(out.opt.ll and
>     >> out.opt2.ll can be found on the following link
>     >> https://llvm.org/bugs/show_bug.cgi?id=23077).
>     >>
>     >> Thank you for the attention!
>     >>
>     >> --
>     >>                                     Cheers, Roman Gareev.
>     >>
>     >> _______________________________________________
>     >> LLVM Developers mailing list
>     >> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>     >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     >>
>     >
>
>
>
>     --
>                                         Cheers, Roman Gareev.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160127/e4a38436/attachment.html>