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

[Daniel Berlin via llvm-dev]

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>