<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<br>
<div class="moz-cite-prefix">On 01/27/2016 03:56 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTU55kGL5XRsKBK8wC184dS7U0s6RJa-RnZNrckXvw9msw@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Jan 27, 2016 at 2:37 PM,
Philip Reames <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><span> <br>
<br>
<div>On 01/27/2016 07:53 AM, Daniel Berlin wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Jan 27, 2016 at
1:27 AM, Roman Gareev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:gareevroman@gmail.com"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:gareevroman@gmail.com">gareevroman@gmail.com</a></a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Thank
you for the idea! Could you please explain
it?</blockquote>
<div><br>
</div>
<div>Which part are you having trouble with,
so i know where to concetrate?</div>
<div> </div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
If I’m not<br>
mistaken, you advise to insert the unknown
insts of an every AS from<br>
AliasSetTracker::add(const AliasSetTracker
&AST) into a smallptrset<br>
and consequently append it to merged alias
sets from<br>
AliasSetTracker::findAliasSetForUnknownInst.</blockquote>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div><br>
</div>
<div>See below.</div>
<div> </div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I think that Philip<br>
proposed something similar to your approach
in<br>
<a moz-do-not-send="true"
href="https://llvm.org/bugs/show_bug.cgi?id=23077"
rel="noreferrer" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=23077</a>.<br>
</blockquote>
<div><br>
</div>
<div>You reported that you are finding
duplicates on the unknown inst list. </div>
</div>
</div>
</div>
</blockquote>
</span></div>
</blockquote>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">I don't see this in
the bug report?<span><br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
</div>
</div>
</div>
</blockquote>
</span></div>
</blockquote>
<div><br>
</div>
<div>The patch sent to the mailing list does this:</div>
<div><br>
<div>+std::set<llvm::Instruction *> ViewedInst;</div>
<div> +</div>
<div> bool AliasSet::aliasesUnknownInst(const Instruction
*Inst,</div>
<div> AliasAnalysis
&AA) const {</div>
<div> if (!Inst->mayReadOrWriteMemory())</div>
<div> return false;</div>
<div><br>
</div>
<div> for (unsigned i = 0, e = UnknownInsts.size(); i
!= e; ++i) {</div>
<div> + if (ViewedInst.count(getUnknownInst(i)))</div>
<div> + continue;</div>
<div> ImmutableCallSite C1(getUnknownInst(i)),
C2(Inst);</div>
<div> if (!C1 || !C2 || AA.getModRefInfo(C1, C2) !=
MRI_NoModRef ||</div>
AA.getModRefInfo(C2, C1) != MRI_NoModRef) <br>
</div>
<div>
<div> @@ -400,7 +405,10 @@ void AliasSetTracker::add(const
AliasSetTracker &AST) {</div>
<div>
(AliasSet::AccessLattice)AS.Access, X);</div>
<div> if (AS.isVolatile()) NewAS.setVolatile();</div>
<div> }</div>
<div> + for (unsigned i = 0, e =
AS.UnknownInsts.size(); i != e; ++i)</div>
<div> + ViewedInst.insert(AS.UnknownInsts[i]);</div>
<div> }</div>
<div> + ViewedInst.clear();</div>
<div> }</div>
</div>
<div><br>
</div>
<div><br>
</div>
<div>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 :)</div>
</div>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
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.)<br>
<br>
This code is incredibly complicated. :)<br>
<br>
<br>
<blockquote
cite="mid:CAF4BwTU55kGL5XRsKBK8wC184dS7U0s6RJa-RnZNrckXvw9msw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><span>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<div>The duplicates occur because we are not
de-duplicating the unknowninst lists
attached to each AS when we merge them.</div>
</div>
</div>
</div>
</blockquote>
</span> Danny, I think your analysis is incorrect.</div>
</blockquote>
<div><br>
</div>
<div>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 :)</div>
<div><br>
</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"> 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.</div>
</blockquote>
<div><br>
</div>
<div>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?</div>
<div>
<div>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 :)</div>
</div>
<div><br>
</div>
<div>(I try to avoid AST when i can)</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"> <br>
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.</div>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div> </div>
</div>
<br>
</div>
</div>
</blockquote>
<br>
</body>
</html>