[llvm-dev] Skip redundant checks in AliasSet::aliasesUnknownInst

[Daniel Berlin via llvm-dev]

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>