<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 07:53 AM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTUqM1AZPDpzK-TgpZXV6+YO3OMGQ8w3Sess-8dU1OotHg@mail.gmail.com"
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">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 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>
I don't see this in the bug report?<br>
<blockquote
cite="mid:CAF4BwTUqM1AZPDpzK-TgpZXV6+YO3OMGQ8w3Sess-8dU1OotHg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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>
</div>
</div>
</blockquote>
Danny, I think your analysis is incorrect. 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.<br>
<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.<br>
<blockquote
cite="mid:CAF4BwTUqM1AZPDpzK-TgpZXV6+YO3OMGQ8w3Sess-8dU1OotHg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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
moz-do-not-send="true"
href="mailto:dberlin@dberlin.org"><a class="moz-txt-link-abbreviated" href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a></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 moz-do-not-send="true"
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 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>
>><br>
>> Thank you for the attention!<br>
>><br>
>> --<br>
>> Cheers,
Roman Gareev.<br>
>><br>
>>
_______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> <a moz-do-not-send="true"
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>
</blockquote>
<br>
</body>
</html>