<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><br></div><div>The duplicates occur because we are not de-duplicating the unknowninst lists attached to each AS when we merge them.</div><div><br></div><div>If you look at the code in mergeSetIn (used by both <span style="color:rgb(0,0,0);font-family:monospace,fixed;font-size:9pt;line-height:15px;background-color:rgb(251,252,253)">findAliasSetForPointer and </span><span style="color:rgb(0,0,0);font-family:monospace,fixed;font-size:9pt;line-height:15px;background-color:rgb(251,252,253)">findAliasSetForUnknownInst)</span> you can see when we merge AS's, we simply append the list of unknowninsts from one AS into the "destination" AS, without ever checking *whether that destination AS already contains any of the same instructions on the unknowninst list*.</div><div><br></div><div>So things end up on the unknowninst lists multiple times.</div><div><br></div><div>There are many ways to solve this:<br><br></div><div>1. Don't use lists at all for unknowninsts for each AS, use SmallSets or SmallPtrSets instead. Then any normal merging will deduplicate them for you.</div><div>or</div><div>2. When merging AS's, deduplicate the unknown inst list by temporarily storing it in a set.</div><div><br></div><div><br></div><div>#2 assumes that "merging AS's" is the only place that is causing duplicates.</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"><span class="im"><br>
2016-01-24 22:44 GMT+05:00 Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>>:<br>
</span><div class=""><div class="h5">> It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or<br>
> DenseSet (if you can't do the others).<br>
><br>
> Otherwise, even with your patch, we are still wasting time traversing and<br>
> copying and .... the unknown instructions.<br>
><br>
> If that doesn't work, I suspect the way you get dupes is through mergeSetIn,<br>
> so you also could probably just change:<br>
><br>
> 00061 } else if (ASHadUnknownInsts) {<br>
> 00062 UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),<br>
> AS.UnknownInsts.end());<br>
> 00063 AS.UnknownInsts.clear();<br>
> 00064 }<br>
><br>
><br>
><br>
> You could insert the current unknown insts into a smallptrset, and then only<br>
> append them to UnknownInsts if they aren't in the set.<br>
><br>
> This should remove your dupes.<br>
><br>
><br>
><br>
> On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev<br>
> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
>><br>
>> Dear llvm contributors,<br>
>><br>
>> Could you please advise me how to skip<br>
>> checks, which are performed in AliasSet::aliasesUnknownInst, of<br>
>> unknown instructions from different alias sets of an alias set tracker<br>
>> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker<br>
>> &AST)’?<br>
>><br>
>> If this wasn’t available at the moment and someone could review me, I<br>
>> would try to implement it. A temporary patch can be found attached<br>
>> (for example, ViewedInst can become a second parameter of<br>
>> AliasSetTracker::addUnknown ). It<br>
>> passes the LLVM regression tests and helps to reduce the runtime of<br>
>> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime of<br>
>> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and<br>
>> out.opt2.ll can be found on the following link<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>
>><br>
>> Thank you for the attention!<br>
>><br>
>> --<br>
>> Cheers, Roman Gareev.<br>
>><br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
>><br>
><br>
<br>
<br>
<br>
</div></div><span class=""><font color="#888888">--<br>
Cheers, Roman Gareev.<br>
</font></span></blockquote></div><br></div></div>