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

[Philip Reames via llvm-dev]

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>