Philip Reames via llvm-dev
2016-Jan-27 22:37 UTC
[llvm-dev] Skip redundant checks in AliasSet::aliasesUnknownInst
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>
Daniel Berlin via llvm-dev
2016-Jan-27 23:56 UTC
[llvm-dev] Skip redundant checks in AliasSet::aliasesUnknownInst
On Wed, Jan 27, 2016 at 2:37 PM, Philip Reames <listmail at philipreames.com> wrote:> > > 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> > 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 patch sent to the mailing list does this: +std::set<llvm::Instruction *> ViewedInst; + bool AliasSet::aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const { if (!Inst->mayReadOrWriteMemory()) return false; for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { + if (ViewedInst.count(getUnknownInst(i))) + continue; ImmutableCallSite C1(getUnknownInst(i)), C2(Inst); if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef || AA.getModRefInfo(C2, C1) != MRI_NoModRef) @@ -400,7 +405,10 @@ void AliasSetTracker::add(const AliasSetTracker &AST) { (AliasSet::AccessLattice)AS.Access, X); if (AS.isVolatile()) NewAS.setVolatile(); } + for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i) + ViewedInst.insert(AS.UnknownInsts[i]); } + ViewedInst.clear(); } I can't see how this will do anything without duplicate unknown insts getting hit in the loop, but it is entirely possible i've missed something or the patch is wrong :) 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. >I based it entirely on the patch sent to the mailing list, assuming it solved the issue. I am happy to admit i did not look at the bug before starting :) 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. >Interesting. Then i fail to see how the above patch will do anything, since each of the AST's it walks should have a disjoint set of UnknownInsts, no? In any case, i am actually more than happy to have you take over the analysis and direction on this bug if you are already doing it :) (I try to avoid AST when i can)> 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. >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160127/2c76d53d/attachment.html>
Philip Reames via llvm-dev
2016-Jan-28 00:14 UTC
[llvm-dev] Skip redundant checks in AliasSet::aliasesUnknownInst
On 01/27/2016 03:56 PM, Daniel Berlin wrote:> > > On Wed, Jan 27, 2016 at 2:37 PM, Philip Reames > <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: > > > > 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 patch sent to the mailing list does this: > > +std::set<llvm::Instruction *> ViewedInst; > + > bool AliasSet::aliasesUnknownInst(const Instruction *Inst, > AliasAnalysis &AA) const { > if (!Inst->mayReadOrWriteMemory()) > return false; > > for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { > + if (ViewedInst.count(getUnknownInst(i))) > + continue; > ImmutableCallSite C1(getUnknownInst(i)), C2(Inst); > if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef || > AA.getModRefInfo(C2, C1) != MRI_NoModRef) > @@ -400,7 +405,10 @@ void AliasSetTracker::add(const AliasSetTracker > &AST) { > (AliasSet::AccessLattice)AS.Access, X); > if (AS.isVolatile()) NewAS.setVolatile(); > } > + for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i) > + ViewedInst.insert(AS.UnknownInsts[i]); > } > + ViewedInst.clear(); > } > > > I can't see how this will do anything without duplicate unknown insts > getting hit in the loop, but it is entirely possible i've missed > something or the patch is wrong :)Hm, I'd thought I'd had a case where this could happen without duplicates in the original alias sets due to the repeated addition of elements from the same set, but now I'm not seeing it. Oh wait. Ah! The trick is that you don't need to revisit the instructions you've already added. You "know" that the instruction you're now querying can't be in the same alias set as a previously added one, because, if it were, you'd have already merged them. That's what this code is implementing. (Remember, we fall through to *false* here.) This code is incredibly complicated. :)> > > > >> 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. > > > I based it entirely on the patch sent to the mailing list, assuming > it solved the issue. I am happy to admit i did not look at the bug > before starting :) > > > 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. > > > Interesting. Then i fail to see how the above patch will do anything, > since each of the AST's it walks should have a disjoint set of > UnknownInsts, no? > In any case, i am actually more than happy to have you take over the > analysis and direction on this bug if you are already doing it :) > > (I try to avoid AST when i can) > > > 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. > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160127/ad5d59fd/attachment.html>