llvm dev - Jan 2016 - Skip redundant checks in AliasSet::aliasesUnknownInst

Dear llvm contributors,

Could you please advise me how to skip
checks, which are performed in AliasSet::aliasesUnknownInst, of
unknown instructions from different alias sets of an alias set tracker
that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
&AST)’?

If this wasn’t available at the moment and someone could review me, I
would try to implement it. A temporary patch can be found attached
(for example, ViewedInst can become a second parameter of
AliasSetTracker::addUnknown ). It
passes the LLVM regression tests and helps to reduce the runtime of
'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime of
'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
out.opt2.ll can be found on the following link
https://llvm.org/bugs/show_bug.cgi?id=23077).

Thank you for the attention!

-- 
                                    Cheers, Roman Gareev.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Mark-unknown-instructions-from-the-AST-parameter.patch
Type: application/octet-stream
Size: 1813 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160124/0e29f04e/attachment-0001.obj>

It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or
DenseSet (if you can't do the others).

Otherwise, even with your patch, we are still wasting time traversing and
copying and .... the unknown instructions.

If that doesn't work, I suspect the way you get dupes is through
mergeSetIn, so you also could probably just change:

00061   } else if (ASHadUnknownInsts) {00062
UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),
AS.UnknownInsts.end());00063     AS.UnknownInsts.clear();00064   }



You could insert the current unknown insts into a smallptrset, and then
only append them to UnknownInsts if they aren't in the set.

This should remove your dupes.



On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Dear llvm contributors,
>
> Could you please advise me how to skip
> checks, which are performed in AliasSet::aliasesUnknownInst, of
> unknown instructions from different alias sets of an alias set tracker
> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
> &AST)’?
>
> If this wasn’t available at the moment and someone could review me, I
> would try to implement it. A temporary patch can be found attached
> (for example, ViewedInst can become a second parameter of
> AliasSetTracker::addUnknown ). It
> passes the LLVM regression tests and helps to reduce the runtime of
> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime of
> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
> out.opt2.ll can be found on the following link
> https://llvm.org/bugs/show_bug.cgi?id=23077).
>
> Thank you for the attention!
>
> --
>                                     Cheers, Roman Gareev.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160124/ee635011/attachment.html>

In addition to this, see my comments on the bug.  LICM is using AST in a 
particular usage pattern when most of the work done by add(AST&) ends up 
being redundant for perfectly nested loops.

Philip

On 01/24/2016 09:44 AM, Daniel Berlin via llvm-dev
wrote:
> It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, 
> or DenseSet (if you can't do the others).
>
> Otherwise, even with your patch, we are still wasting time traversing 
> and copying and .... the unknown instructions.
>
> If that doesn't work, I suspect the way you get dupes is through 
> mergeSetIn, so you also could probably just change:
>
> 00061   }else  if  (ASHadUnknownInsts) {
> 00062     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),
AS.UnknownInsts.end());
> 00063     AS.UnknownInsts.clear();
> 00064   }
>
>
> You could insert the current unknown insts into a smallptrset, and 
> then only append them to UnknownInsts if they aren't in the set.
>
> This should remove your dupes.
>
>
>
> On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>     Dear llvm contributors,
>
>     Could you please advise me how to skip
>     checks, which are performed in AliasSet::aliasesUnknownInst, of
>     unknown instructions from different alias sets of an alias set tracker
>     that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
>     &AST)’?
>
>     If this wasn’t available at the moment and someone could review me, I
>     would try to implement it. A temporary patch can be found attached
>     (for example, ViewedInst can become a second parameter of
>     AliasSetTracker::addUnknown ). It
>     passes the LLVM regression tests and helps to reduce the runtime of
>     'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime
of
>     'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
>     out.opt2.ll can be found on the following link
>     https://llvm.org/bugs/show_bug.cgi?id=23077).
>
>     Thank you for the attention!
>
>     --
>                                         Cheers, Roman Gareev.
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160124/485b4ee8/attachment.html>

Thank you for the comments! I’ll try to respond to them soon.

2016-01-24 22:44 GMT+05:00 Daniel Berlin <dberlin at
dberlin.org>:
> It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or
> DenseSet (if you can't do the others).
>
> Otherwise, even with your patch, we are still wasting time traversing and
> copying and .... the unknown instructions.
>
> If that doesn't work, I suspect the way you get dupes is through
mergeSetIn,
> so you also could probably just change:
>
> 00061   } else if (ASHadUnknownInsts) {
> 00062     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),
> AS.UnknownInsts.end());
> 00063     AS.UnknownInsts.clear();
> 00064   }
>
>
>
> You could insert the current unknown insts into a smallptrset, and then
only
> append them to UnknownInsts if they aren't in the set.
>
> This should remove your dupes.
>
>
>
> On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Dear llvm contributors,
>>
>> Could you please advise me how to skip
>> checks, which are performed in AliasSet::aliasesUnknownInst, of
>> unknown instructions from different alias sets of an alias set tracker
>> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
>> &AST)’?
>>
>> If this wasn’t available at the moment and someone could review me, I
>> would try to implement it. A temporary patch can be found attached
>> (for example, ViewedInst can become a second parameter of
>> AliasSetTracker::addUnknown ). It
>> passes the LLVM regression tests and helps to reduce the runtime of
>> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime
of
>> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
>> out.opt2.ll can be found on the following link
>> https://llvm.org/bugs/show_bug.cgi?id=23077).
>>
>> Thank you for the attention!
>>
>> --
>>                                     Cheers, Roman Gareev.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>


-- 
                                    Cheers, Roman Gareev.

Thank you for the idea! Could you please explain it? 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. I think that Philip
proposed something similar to your approach in
https://llvm.org/bugs/show_bug.cgi?id=23077.

2016-01-24 22:44 GMT+05:00 Daniel Berlin <dberlin at
dberlin.org>:
> It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or
> DenseSet (if you can't do the others).
>
> Otherwise, even with your patch, we are still wasting time traversing and
> copying and .... the unknown instructions.
>
> If that doesn't work, I suspect the way you get dupes is through
mergeSetIn,
> so you also could probably just change:
>
> 00061   } else if (ASHadUnknownInsts) {
> 00062     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(),
> AS.UnknownInsts.end());
> 00063     AS.UnknownInsts.clear();
> 00064   }
>
>
>
> You could insert the current unknown insts into a smallptrset, and then
only
> append them to UnknownInsts if they aren't in the set.
>
> This should remove your dupes.
>
>
>
> On Sun, Jan 24, 2016 at 5:28 AM, Roman Gareev via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Dear llvm contributors,
>>
>> Could you please advise me how to skip
>> checks, which are performed in AliasSet::aliasesUnknownInst, of
>> unknown instructions from different alias sets of an alias set tracker
>> that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
>> &AST)’?
>>
>> If this wasn’t available at the moment and someone could review me, I
>> would try to implement it. A temporary patch can be found attached
>> (for example, ViewedInst can become a second parameter of
>> AliasSetTracker::addUnknown ). It
>> passes the LLVM regression tests and helps to reduce the runtime of
>> 'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime
of
>> 'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
>> out.opt2.ll can be found on the following link
>> https://llvm.org/bugs/show_bug.cgi?id=23077).
>>
>> Thank you for the attention!
>>
>> --
>>                                     Cheers, Roman Gareev.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>


-- 
                                    Cheers, Roman Gareev.