eliminate dead stores across functions

eliminate dead stores across functions

[Prathamesh Kulkarni]

Hi,
For the following test-case,

int a;

__attribute__((noinline))
static void foo()
{
  a = 3;
}

int main()
{
  a = 4;
  foo ();
  return a;
}

I assume it's safe to remove "a = 4"  since 'a' would be overwritten
by call to foo ?
IIUC, ipa-reference pass does mod/ref analysis to compute side-effects
of function call,
so could we perhaps use ipa_reference_get_not_written_global() in dse
pass to check if a global variable will be killed on call to a
function ? If not, I suppose we could write a similar ipa pass that
computes the set of killed global variables per function but I am not
sure if that's the correct approach.

Thanks,
Prathamesh

Re: eliminate dead stores across functions

[Richard Biener]

On Tue, Mar 6, 2018 at 1:00 PM, Prathamesh Kulkarni
<prathamesh.kulkarni@linaro.org> wrote:
> Hi,
> For the following test-case,
>
> int a;
>
> __attribute__((noinline))
> static void foo()
> {
>   a = 3;
> }
>
> int main()
> {
>   a = 4;
>   foo ();
>   return a;
> }
>
> I assume it's safe to remove "a = 4"  since 'a' would be overwritten
> by call to foo ?
> IIUC, ipa-reference pass does mod/ref analysis to compute side-effects
> of function call,
> so could we perhaps use ipa_reference_get_not_written_global() in dse
> pass to check if a global variable will be killed on call to a
> function ? If not, I suppose we could write a similar ipa pass that
> computes the set of killed global variables per function but I am not
> sure if that's the correct approach.

Do you think the situation happens often enough to make this worthwhile?

ipa-reference doesn't compute must-def, only may-def and may-use IIRC.

Richard.

> Thanks,
> Prathamesh

Re: eliminate dead stores across functions

[Bin.Cheng]

On Tue, Mar 6, 2018 at 2:28 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Mar 6, 2018 at 1:00 PM, Prathamesh Kulkarni
> <prathamesh.kulkarni@linaro.org> wrote:
>> Hi,
>> For the following test-case,
>>
>> int a;
>>
>> __attribute__((noinline))
>> static void foo()
>> {
>>   a = 3;
>> }
>>
>> int main()
>> {
>>   a = 4;
>>   foo ();
>>   return a;
>> }
>>
>> I assume it's safe to remove "a = 4"  since 'a' would be overwritten
>> by call to foo ?
>> IIUC, ipa-reference pass does mod/ref analysis to compute side-effects
>> of function call,
>> so could we perhaps use ipa_reference_get_not_written_global() in dse
>> pass to check if a global variable will be killed on call to a
>> function ? If not, I suppose we could write a similar ipa pass that
>> computes the set of killed global variables per function but I am not
>> sure if that's the correct approach.
>
> Do you think the situation happens often enough to make this worthwhile?
There is one probably more useful case.  Program may use global flags
controlling
how it does (heavy) computation.  Such flags are only set couple of
times in execution
time.  It would be useful if we can (IPA) propagate flags into computation heavy
functions by versioning (if necessary).  For example:

int flag = 1;
void foo ()
{
  //heavy computation wrto to flag
}
void main()
{
  flag = 2;
  foo();
  flag = 1;
  foo();
}

Of course this may only be useful for LTO.

Thanks,
bin
>
> ipa-reference doesn't compute must-def, only may-def and may-use IIRC.
>
> Richard.
>
>> Thanks,
>> Prathamesh

Re: eliminate dead stores across functions

[Richard Biener]

On Tue, Mar 6, 2018 at 4:50 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Tue, Mar 6, 2018 at 2:28 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Mar 6, 2018 at 1:00 PM, Prathamesh Kulkarni
>> <prathamesh.kulkarni@linaro.org> wrote:
>>> Hi,
>>> For the following test-case,
>>>
>>> int a;
>>>
>>> __attribute__((noinline))
>>> static void foo()
>>> {
>>>   a = 3;
>>> }
>>>
>>> int main()
>>> {
>>>   a = 4;
>>>   foo ();
>>>   return a;
>>> }
>>>
>>> I assume it's safe to remove "a = 4"  since 'a' would be overwritten
>>> by call to foo ?
>>> IIUC, ipa-reference pass does mod/ref analysis to compute side-effects
>>> of function call,
>>> so could we perhaps use ipa_reference_get_not_written_global() in dse
>>> pass to check if a global variable will be killed on call to a
>>> function ? If not, I suppose we could write a similar ipa pass that
>>> computes the set of killed global variables per function but I am not
>>> sure if that's the correct approach.
>>
>> Do you think the situation happens often enough to make this worthwhile?
> There is one probably more useful case.  Program may use global flags
> controlling
> how it does (heavy) computation.  Such flags are only set couple of
> times in execution
> time.  It would be useful if we can (IPA) propagate flags into computation heavy
> functions by versioning (if necessary).  For example:
>
> int flag = 1;
> void foo ()
> {
>   //heavy computation wrto to flag
> }
> void main()
> {
>   flag = 2;
>   foo();
>   flag = 1;
>   foo();
> }

Yeah, libquantum does this.  There's also related example
from some SPEC fortran testcase:

vodi foo()
{
  static int initialized;
  static T data;
  if (!initialized)
    {
       data.x = 1;
       initialized = 1;
    }
...
}

where we want to constant propagate from data.x.  IIRC I tried
to work on this, not sure if I solved it yet...

Richard.

> Of course this may only be useful for LTO.

> Thanks,
> bin
>>
>> ipa-reference doesn't compute must-def, only may-def and may-use IIRC.
>>
>> Richard.
>>
>>> Thanks,
>>> Prathamesh

Re: eliminate dead stores across functions

[Martin Jambor]

Hi Bin,

On Tue, Mar 06 2018, Bin Cheng wrote:
> On Tue, Mar 6, 2018 at 2:28 PM, Richard Biener
>>
>> Do you think the situation happens often enough to make this worthwhile?
> There is one probably more useful case.  Program may use global flags
> controlling
> how it does (heavy) computation.  Such flags are only set couple of
> times in execution
> time.  It would be useful if we can (IPA) propagate flags into computation heavy
> functions by versioning (if necessary).  For example:
>
> int flag = 1;
> void foo ()
> {
>   //heavy computation wrto to flag
> }
> void main()
> {
>   flag = 2;
>   foo();
>   flag = 1;
>   foo();
> }
>

So basically IPA-CP done on (not-addressable) static global variables.
Do you happen to know some real code which would benefit?  I'd like to
experiment with it but would like to have a real thing to look at, as
opposed to artificial test cases.

Thanks,

Martin

Re: eliminate dead stores across functions

[Bin.Cheng]

On Tue, Mar 6, 2018 at 4:44 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi Bin,
>
> On Tue, Mar 06 2018, Bin Cheng wrote:
>> On Tue, Mar 6, 2018 at 2:28 PM, Richard Biener
>>>
>>> Do you think the situation happens often enough to make this worthwhile?
>> There is one probably more useful case.  Program may use global flags
>> controlling
>> how it does (heavy) computation.  Such flags are only set couple of
>> times in execution
>> time.  It would be useful if we can (IPA) propagate flags into computation heavy
>> functions by versioning (if necessary).  For example:
>>
>> int flag = 1;
>> void foo ()
>> {
>>   //heavy computation wrto to flag
>> }
>> void main()
>> {
>>   flag = 2;
>>   foo();
>>   flag = 1;
>>   foo();
>> }
>>
>
> So basically IPA-CP done on (not-addressable) static global variables.
> Do you happen to know some real code which would benefit?  I'd like to
> experiment with it but would like to have a real thing to look at, as
> opposed to artificial test cases.
As Richi pointed out, I think this is not rare in spec.  For this
moment I only vaguely remember 544.nab_r for such issue, but I am sure
there are other cases.

Thanks,
bin
>
> Thanks,
>
> Martin
>
>

Re: eliminate dead stores across functions

[Bin.Cheng]

On Tue, Mar 6, 2018 at 4:50 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Tue, Mar 6, 2018 at 4:44 PM, Martin Jambor <mjambor@suse.cz> wrote:
>> Hi Bin,
>>
>> On Tue, Mar 06 2018, Bin Cheng wrote:
>>> On Tue, Mar 6, 2018 at 2:28 PM, Richard Biener
>>>>
>>>> Do you think the situation happens often enough to make this worthwhile?
>>> There is one probably more useful case.  Program may use global flags
>>> controlling
>>> how it does (heavy) computation.  Such flags are only set couple of
>>> times in execution
>>> time.  It would be useful if we can (IPA) propagate flags into computation heavy
>>> functions by versioning (if necessary).  For example:
>>>
>>> int flag = 1;
>>> void foo ()
>>> {
>>>   //heavy computation wrto to flag
>>> }
>>> void main()
>>> {
>>>   flag = 2;
>>>   foo();
>>>   flag = 1;
>>>   foo();
>>> }
>>>
>>
>> So basically IPA-CP done on (not-addressable) static global variables.
>> Do you happen to know some real code which would benefit?  I'd like to
>> experiment with it but would like to have a real thing to look at, as
>> opposed to artificial test cases.
> As Richi pointed out, I think this is not rare in spec.  For this
> moment I only vaguely remember 544.nab_r for such issue, but I am sure
> there are other cases.
Sorry I forgot to mention it might not be static variables in file
scope, that's why I mentioned LTO previously.

Thanks,
bin
>
> Thanks,
> bin
>>
>> Thanks,
>>
>> Martin
>>
>>

Re: eliminate dead stores across functions

[William Cohen]

On 03/06/2018 09:28 AM, Richard Biener wrote:
> On Tue, Mar 6, 2018 at 1:00 PM, Prathamesh Kulkarni
> <prathamesh.kulkarni@linaro.org> wrote:
>> Hi,
>> For the following test-case,
>>
>> int a;
>>
>> __attribute__((noinline))
>> static void foo()
>> {
>>   a = 3;
>> }
>>
>> int main()
>> {
>>   a = 4;
>>   foo ();
>>   return a;
>> }
>>
>> I assume it's safe to remove "a = 4"  since 'a' would be overwritten
>> by call to foo ?
>> IIUC, ipa-reference pass does mod/ref analysis to compute side-effects
>> of function call,
>> so could we perhaps use ipa_reference_get_not_written_global() in dse
>> pass to check if a global variable will be killed on call to a
>> function ? If not, I suppose we could write a similar ipa pass that
>> computes the set of killed global variables per function but I am not
>> sure if that's the correct approach.
> 
> Do you think the situation happens often enough to make this worthwhile?
> 
> ipa-reference doesn't compute must-def, only may-def and may-use IIRC.
> 
> Richard.
> 
>> Thanks,
>> Prathamesh

This dead write optimization sounds similar to "DeadSpy: a tool to pinpoint program inefficiencies" by Milind Chabbi and John Mellor-Crummey of Rice University:

https://dl.acm.org/citation.cfm?id=2259033

The abstract says there were numerous dead writes in the SPEC 2006 gcc benchmark and eliminating those provided average 15% improvement in performance.

-Will