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

[Roman Gareev via llvm-dev]

2016-01-28 5:14 GMT+05:00 Philip Reames <listmail at philipreames.com>:
>
>
> 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>
> 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 :)
>
>
> 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.

Sorry for the confusion.

-- 
                                    Cheers, Roman Gareev.