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

[Philip Reames via llvm-dev]

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>