<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 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 href="mailto:gareevroman@gmail.com" target="_blank">gareevroman@gmail.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">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 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><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>