thr3ads.net - llvm dev - [llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?) [Oct 2017]

If this information is useful, please help other people find it:
Share via:

Daniel Berlin via llvm-dev

2017-Oct-10 02:05 UTC

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

Yes, this is odd.

On my clang.bc

Without:
   2.2967 ( 53.8%)   0.0242 ( 26.4%)   2.3210 ( 53.2%)   2.3227 ( 53.2%)
Memory SSA
   2.3364 ( 53.7%)   0.0246 ( 25.7%)   2.3610 ( 53.1%)   2.3636 ( 53.1%)
Memory SSA
   2.3353 ( 54.0%)   0.0258 ( 27.0%)   2.3611 ( 53.4%)   2.3632 ( 53.3%)
Memory SSA

With two getModRefInfo calls:
   3.0302 ( 58.8%)   0.0328 ( 29.9%)   3.0630 ( 58.2%)   3.0858 ( 58.2%)
Memory SSA
   3.0097 ( 58.9%)   0.0325 ( 30.0%)   3.0422 ( 58.3%)   3.0590 ( 58.3%)
Memory SSA
   3.0486 ( 58.8%)   0.0317 ( 29.4%)   3.0804 ( 58.2%)   3.1331 ( 58.3%)
Memory SSA

with alias followed by getModRefInfo
   2.2487 ( 52.9%)   0.0259 ( 27.1%)   2.2746 ( 52.4%)   2.2820 ( 52.4%)
Memory SSA
etc


Not entirely sure what is going on.

But if alias is free, problem solved!


On Mon, Oct 9, 2017 at 4:05 PM, Alina Sbirlea <alina.sbirlea at gmail.com>
wrote:
> On Mon, Oct 9, 2017 at 2:08 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
> wrote:
>
>> On Mon, Oct 9, 2017 at 1:57 PM, Daniel Berlin <dberlin at
dberlin.org>
>> wrote:
>>
>>> FWIW:  Bootstrap is probably not a good test of this, there are
bugs
>>> filed where we end up with tons of loads and stores to test against
each
>>> other.  That's actually fairly rare in bootstrap, as you can
see.
>>> Let me get you some test cases.
>>>
>>
>> SG, thanks!
>>
>
> I ran a few quick timings of "opt -memoryssa" for
gvn_hoist.small.bc in
> PR28670/PR28832, and a larger version extracted then.
>
> Reporting:
> mssalimit    /  single call getModRef   /   call getModRef followed by
> alias().
>
> Smaller test hits the case with 2 alias calls 1282 times. Timings, average
> over 5-10 runs (s):
> 100 / 8.99 / 8.87
> 200 / 9.24 / 9.113
> 500 / 48.228 / 48.453
>
> Larger case hits it 1872 times. Timings, average over 5 runs (s):
> 100 / 23.575 / 23.962
> 200 /  23.874 / 23.848
>
>
> My guess is that we should go with mustmod.
>>>
>>>
>>> As for callsites, adding mustmod works for call, memloc and call,
call
>>> testing.
>>>
>>
>>>
>>
>>>
>>> On Mon, Oct 9, 2017, 4:48 PM Alina Sbirlea <alina.sbirlea at
gmail.com>
>>> wrote:
>>>
>>>> Hi,
>>>>
>>>> This came up in https://reviews.llvm.org/D38569, and I'd
like some
>>>> input on what's the best way to get alias and mod-ref info
without having
>>>> two alias calls.
>>>>
>>>> A couple of ideas:
>>>> (a) Extend the getModRefInfo interface (+getModRefBehavior,
>>>> +gerArgModRefInfo) to return a pair {ModRefInfo, AliasResult}.
>>>>
>>>> The AliasResult can be optional based on an argument
>>>>      e.g.:
>>>>     struct MRI_AR { ModRefInfo MRI, AliasResult AR };
>>>>     MRI_AR getModRefInfoAlias (LoadInst *LI, MemoryLocation
Loc, bool
>>>> SetAliasResultField);
>>>>
>>>> Add wrapper APIs to preserve current calls.
>>>>     e.g.:
>>>>      ModRefInfo getModRefInfo (LoadInst *LI, MemoryLocation
Loc) {
>>>>           return getModRefInfoAlias (LI, Loc, false).MRI;
>>>>       }
>>>>
>>>> (b) From talking offline with George, introducing a MRI_MustMod
in
>>>> ModRefInfo.
>>>>
>>>>
>>>> Open question: How to handle callsites.
>>>>
>>>>
>>>> In terms of whether this is worth doing, as a preliminary
timing test I
>>>> timed the llvm bootstrap build with 1 vs 2 alias calls in
D38569:
>>>> instructionClobbersQuery:296, and got the following:
>>>> 2 alias calls:
>>>> real    62m52.627s
>>>> user    2769m46.964s
>>>> sys     17m48.072s
>>>> 1 alias call:
>>>> real    62m56.659s
>>>> user    2766m40.452s
>>>> sys     17m46.312s
>>>>
>>>> Thoughts?
>>>>
>>>>
>>>> Thanks,
>>>> Alina
>>>>
>>>>
>>>>
>>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171009/f6d1676e/attachment.html>

Alina Sbirlea via llvm-dev

2017-Oct-10 16:16 UTC

head link

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

I should have clarified, by 2 calls meant getModRef followed by alias, not
two getModRef calls.
The timings you got seem to concur, but I'm quite skeptical about the alias
call being free...

On Mon, Oct 9, 2017 at 7:05 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> Yes, this is odd.
>
> On my clang.bc
>
> Without:
>    2.2967 ( 53.8%)   0.0242 ( 26.4%)   2.3210 ( 53.2%)   2.3227 ( 53.2%)
> Memory SSA
>    2.3364 ( 53.7%)   0.0246 ( 25.7%)   2.3610 ( 53.1%)   2.3636 ( 53.1%)
> Memory SSA
>    2.3353 ( 54.0%)   0.0258 ( 27.0%)   2.3611 ( 53.4%)   2.3632 ( 53.3%)
> Memory SSA
>
> With two getModRefInfo calls:
>    3.0302 ( 58.8%)   0.0328 ( 29.9%)   3.0630 ( 58.2%)   3.0858 ( 58.2%)
> Memory SSA
>    3.0097 ( 58.9%)   0.0325 ( 30.0%)   3.0422 ( 58.3%)   3.0590 ( 58.3%)
> Memory SSA
>    3.0486 ( 58.8%)   0.0317 ( 29.4%)   3.0804 ( 58.2%)   3.1331 ( 58.3%)
> Memory SSA
>
> with alias followed by getModRefInfo
>    2.2487 ( 52.9%)   0.0259 ( 27.1%)   2.2746 ( 52.4%)   2.2820 ( 52.4%)
> Memory SSA
> etc
>
>
> Not entirely sure what is going on.
>
> But if alias is free, problem solved!
>
>
> On Mon, Oct 9, 2017 at 4:05 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
> wrote:
>
>> On Mon, Oct 9, 2017 at 2:08 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
>> wrote:
>>
>>> On Mon, Oct 9, 2017 at 1:57 PM, Daniel Berlin <dberlin at
dberlin.org>
>>> wrote:
>>>
>>>> FWIW:  Bootstrap is probably not a good test of this, there are
bugs
>>>> filed where we end up with tons of loads and stores to test
against each
>>>> other.  That's actually fairly rare in bootstrap, as you
can see.
>>>> Let me get you some test cases.
>>>>
>>>
>>> SG, thanks!
>>>
>>
>> I ran a few quick timings of "opt -memoryssa" for
gvn_hoist.small.bc in
>> PR28670/PR28832, and a larger version extracted then.
>>
>> Reporting:
>> mssalimit    /  single call getModRef   /   call getModRef followed by
>> alias().
>>
>> Smaller test hits the case with 2 alias calls 1282 times. Timings,
>> average over 5-10 runs (s):
>> 100 / 8.99 / 8.87
>> 200 / 9.24 / 9.113
>> 500 / 48.228 / 48.453
>>
>> Larger case hits it 1872 times. Timings, average over 5 runs (s):
>> 100 / 23.575 / 23.962
>> 200 /  23.874 / 23.848
>>
>>
>> My guess is that we should go with mustmod.
>>>>
>>>>
>>>> As for callsites, adding mustmod works for call, memloc and
call, call
>>>> testing.
>>>>
>>>
>>>>
>>>
>>>>
>>>> On Mon, Oct 9, 2017, 4:48 PM Alina Sbirlea <alina.sbirlea at
gmail.com>
>>>> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> This came up in https://reviews.llvm.org/D38569, and
I'd like some
>>>>> input on what's the best way to get alias and mod-ref
info without having
>>>>> two alias calls.
>>>>>
>>>>> A couple of ideas:
>>>>> (a) Extend the getModRefInfo interface (+getModRefBehavior,
>>>>> +gerArgModRefInfo) to return a pair {ModRefInfo,
AliasResult}.
>>>>>
>>>>> The AliasResult can be optional based on an argument
>>>>>      e.g.:
>>>>>     struct MRI_AR { ModRefInfo MRI, AliasResult AR };
>>>>>     MRI_AR getModRefInfoAlias (LoadInst *LI, MemoryLocation
Loc, bool
>>>>> SetAliasResultField);
>>>>>
>>>>> Add wrapper APIs to preserve current calls.
>>>>>     e.g.:
>>>>>      ModRefInfo getModRefInfo (LoadInst *LI, MemoryLocation
Loc) {
>>>>>           return getModRefInfoAlias (LI, Loc, false).MRI;
>>>>>       }
>>>>>
>>>>> (b) From talking offline with George, introducing a
MRI_MustMod in
>>>>> ModRefInfo.
>>>>>
>>>>>
>>>>> Open question: How to handle callsites.
>>>>>
>>>>>
>>>>> In terms of whether this is worth doing, as a preliminary
timing test
>>>>> I timed the llvm bootstrap build with 1 vs 2 alias calls in
D38569:
>>>>> instructionClobbersQuery:296, and got the following:
>>>>> 2 alias calls:
>>>>> real    62m52.627s
>>>>> user    2769m46.964s
>>>>> sys     17m48.072s
>>>>> 1 alias call:
>>>>> real    62m56.659s
>>>>> user    2766m40.452s
>>>>> sys     17m46.312s
>>>>>
>>>>> Thoughts?
>>>>>
>>>>>
>>>>> Thanks,
>>>>> Alina
>>>>>
>>>>>
>>>>>
>>>>>
>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/d1a4e08f/attachment.html>

Alina Sbirlea via llvm-dev

2017-Oct-10 17:19 UTC

head link

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

I'm trying to understand what is the result we'd seek in the example
in D38569 (pasting here for quick access)

double f(double a)
 {
   double b;
   double c,d;
   double (*fp) (double) __attribute__ ((const));

   /* Partially redundant call */
   if (a < 2.0)
     {
       fp = sin;
       c = fp (a);
     }
   else
     {
       c = 1.0;
       fp = cos;
     }
   d = fp (a);
   return d + c;
 }

the fp call will get pushed into the else branch.
In the equivalent loop, we could promote it (PRE could promote it too if
you let it speculate)
If we determine it is a must-alias of a single thing, we could do the same.
If we determine it's a must-alias of a set of things, we could do the same
If we determine it's a must-alias of the live on entry def, etc



If I understand correctly, the necessary info for fp in this example is:
isMustAlias (CallSite argument a, Value a) &&
getModRefBehavior(CallSite)=onlyReadsMemory.
So adding a MRI_MustMod is insufficient?

Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and test
for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must?
In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if
doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems
correct.

I may be missing something here, I don't want to dive into the wrong
implementation.



On Tue, Oct 10, 2017 at 9:16 AM, Alina Sbirlea <alina.sbirlea at
gmail.com>
wrote:
> I should have clarified, by 2 calls meant getModRef followed by alias, not
> two getModRef calls.
> The timings you got seem to concur, but I'm quite skeptical about the
> alias call being free...
>
> On Mon, Oct 9, 2017 at 7:05 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>
>> Yes, this is odd.
>>
>> On my clang.bc
>>
>> Without:
>>    2.2967 ( 53.8%)   0.0242 ( 26.4%)   2.3210 ( 53.2%)   2.3227 (
53.2%)
>> Memory SSA
>>    2.3364 ( 53.7%)   0.0246 ( 25.7%)   2.3610 ( 53.1%)   2.3636 (
53.1%)
>> Memory SSA
>>    2.3353 ( 54.0%)   0.0258 ( 27.0%)   2.3611 ( 53.4%)   2.3632 (
53.3%)
>> Memory SSA
>>
>> With two getModRefInfo calls:
>>    3.0302 ( 58.8%)   0.0328 ( 29.9%)   3.0630 ( 58.2%)   3.0858 (
58.2%)
>> Memory SSA
>>    3.0097 ( 58.9%)   0.0325 ( 30.0%)   3.0422 ( 58.3%)   3.0590 (
58.3%)
>> Memory SSA
>>    3.0486 ( 58.8%)   0.0317 ( 29.4%)   3.0804 ( 58.2%)   3.1331 (
58.3%)
>> Memory SSA
>>
>> with alias followed by getModRefInfo
>>    2.2487 ( 52.9%)   0.0259 ( 27.1%)   2.2746 ( 52.4%)   2.2820 (
52.4%)
>> Memory SSA
>> etc
>>
>>
>> Not entirely sure what is going on.
>>
>> But if alias is free, problem solved!
>>
>>
>> On Mon, Oct 9, 2017 at 4:05 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
>> wrote:
>>
>>> On Mon, Oct 9, 2017 at 2:08 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
>>> wrote:
>>>
>>>> On Mon, Oct 9, 2017 at 1:57 PM, Daniel Berlin <dberlin at
dberlin.org>
>>>> wrote:
>>>>
>>>>> FWIW:  Bootstrap is probably not a good test of this, there
are bugs
>>>>> filed where we end up with tons of loads and stores to test
against each
>>>>> other.  That's actually fairly rare in bootstrap, as
you can see.
>>>>> Let me get you some test cases.
>>>>>
>>>>
>>>> SG, thanks!
>>>>
>>>
>>> I ran a few quick timings of "opt -memoryssa" for
gvn_hoist.small.bc in
>>> PR28670/PR28832, and a larger version extracted then.
>>>
>>> Reporting:
>>> mssalimit    /  single call getModRef   /   call getModRef followed
by
>>> alias().
>>>
>>> Smaller test hits the case with 2 alias calls 1282 times. Timings,
>>> average over 5-10 runs (s):
>>> 100 / 8.99 / 8.87
>>> 200 / 9.24 / 9.113
>>> 500 / 48.228 / 48.453
>>>
>>> Larger case hits it 1872 times. Timings, average over 5 runs (s):
>>> 100 / 23.575 / 23.962
>>> 200 /  23.874 / 23.848
>>>
>>>
>>> My guess is that we should go with mustmod.
>>>>>
>>>>>
>>>>> As for callsites, adding mustmod works for call, memloc and
call, call
>>>>> testing.
>>>>>
>>>>
>>>>>
>>>>
>>>>>
>>>>> On Mon, Oct 9, 2017, 4:48 PM Alina Sbirlea
<alina.sbirlea at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> This came up in https://reviews.llvm.org/D38569, and
I'd like some
>>>>>> input on what's the best way to get alias and
mod-ref info without having
>>>>>> two alias calls.
>>>>>>
>>>>>> A couple of ideas:
>>>>>> (a) Extend the getModRefInfo interface
(+getModRefBehavior,
>>>>>> +gerArgModRefInfo) to return a pair {ModRefInfo,
AliasResult}.
>>>>>>
>>>>>> The AliasResult can be optional based on an argument
>>>>>>      e.g.:
>>>>>>     struct MRI_AR { ModRefInfo MRI, AliasResult AR };
>>>>>>     MRI_AR getModRefInfoAlias (LoadInst *LI,
MemoryLocation Loc, bool
>>>>>> SetAliasResultField);
>>>>>>
>>>>>> Add wrapper APIs to preserve current calls.
>>>>>>     e.g.:
>>>>>>      ModRefInfo getModRefInfo (LoadInst *LI,
MemoryLocation Loc) {
>>>>>>           return getModRefInfoAlias (LI, Loc,
false).MRI;
>>>>>>       }
>>>>>>
>>>>>> (b) From talking offline with George, introducing a
MRI_MustMod in
>>>>>> ModRefInfo.
>>>>>>
>>>>>>
>>>>>> Open question: How to handle callsites.
>>>>>>
>>>>>>
>>>>>> In terms of whether this is worth doing, as a
preliminary timing test
>>>>>> I timed the llvm bootstrap build with 1 vs 2 alias
calls in D38569:
>>>>>> instructionClobbersQuery:296, and got the following:
>>>>>> 2 alias calls:
>>>>>> real    62m52.627s
>>>>>> user    2769m46.964s
>>>>>> sys     17m48.072s
>>>>>> 1 alias call:
>>>>>> real    62m56.659s
>>>>>> user    2766m40.452s
>>>>>> sys     17m46.312s
>>>>>>
>>>>>> Thoughts?
>>>>>>
>>>>>>
>>>>>> Thanks,
>>>>>> Alina
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>
>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/3c058104/attachment.html>

llvm dev - Oct 2017 - Expose aliasing information in getModRefInfo (or viceversa?)

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)