llvm dev - Oct 2013 - [LLVMdev] Contribute a new precise pointer analysis to LLVM

On Tue, Oct 22, 2013 at 9:55 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > Hi Evan,
> >
> > We did an experiment using the LLVM test suite: we compare the
> > overhead of using our analysis to the LLVM default, both with -O2
> > option.
>
> It might also be interesting to try with -O3; I don't know if we have
any
> significant vectorizable loops in the test suite with a large number of
> arrays, but if we do, this kind of analysis should help.
>
We perform loop vectorization at -O2 now?

>
> >
> > The overall overhead of compiling the whole test suite using our
> > analysis is 36.5%.
>
> Maybe a good candidate for -fexpensive-optimizations? (or -O4?)
>
It would also be helpful to know what the execution performance impact is
to provide context.

>
> > The biggest overhead is  observed in
> > "SingleSource/Benchmarks/Misc/flops-5", where we are 5 times
slower:
> > 0.07s (with our analysis) compared to 0.0133s(default).
> > This may not be accurate as the compilation time in both cases are
> > quite small.
>
> In my experience, compile-time measurements from a normal test-suite
> configuration less than 0.1s are too noisy to use.
>
> >
> > Remind that the compilation time is reported by running our analysis
> > over individual files, the compilation time overhead will be larger
> > if
> > we link all individual compilation units together and run the
> > analysis over the whole application.
>
> Yes, LTO tests would be interesting too.
>
> Thanks again,
> Hal
>
> >
> > Regards,
> > Lian
> >
> > On Sat, Oct 19, 2013 at 7:56 AM, Evan Cheng <evan.cheng at
apple.com>
> > wrote:
> > >
> > > On Oct 17, 2013, at 10:51 PM, lian li <lianli at gmail.com>
wrote:
> > >
> > >> Thanks, Chris.
> > >>
> > >> We are interested in contributing it to LLVM itself. Our
manager
> > >> agrees to commit resources for maintenance needs if it is
accepted
> > >> by
> > >> the community.
> > >
> > > This is great. Please make sure Oracle legal sign off on
explicitly
> > > granting LLVM the use of the patents associated with the work.
> > >
> > > On the compile time front, can you do a comparison with the LLVM
> > > default and your new AA? You can just build the LLVM test suite.
> > >
> > > Thanks,
> > >
> > > Evan
> > >
> > >>
> > >> Regards,
> > >> Lian
> > >>
> > >> On Fri, Oct 18, 2013 at 3:43 PM, Chris Lattner
> > >> <clattner at apple.com> wrote:
> > >>>
> > >>> On Oct 17, 2013, at 5:20 PM, lian li <lianli at
gmail.com> wrote:
> > >>>
> > >>> Hi All,
> > >>>
> > >>> This is Lian Li  from Oracle Labs in Brisbane Australia.
> > >>>
> > >>> We have developed a precise and highly efficient pointer
analysis
> > >>> framework on top of LLVM,  The approach is flow, context,
and
> > >>> field
> > >>> sensitive, details are described in the two papers below:
> > >>>
> > >>> "Boosting the performance of flow-sensitive
points-to analysis
> > >>> using
> > >>> value flow" (in ESEC-FSE 2011), and
> > >>> "Precise and scalable context-sensitive pointer
analysis via
> > >>> value
> > >>> flow graph" (in ISMM 2013).
> > >>>
> > >>> The analysis was initially developed for the purpose of
bug
> > >>> checking,
> > >>> and is now extended to support compiler optimizations. We
have
> > >>> tested
> > >>> it with existing compiler optimizations in LLVM, and have
seen
> > >>> promising results.
> > >>>
> > >>> We are now considering to make this analysis available to
the
> > >>> LLVM
> > >>> community, and contribute resources for future
maintenance needs,
> > >>> provided that there is enough interest. We think that a
new
> > >>> precise
> > >>> pointer analysis in LLVM can enable more new optimization
and
> > >>> analysis
> > >>> techniques to be developed in LLVM.
> > >>>
> > >>> Any people interested in seeing a new precise pointer
analysis in
> > >>> LLVM?
> > >>>
> > >>>
> > >>> This sounds very interesting.  Even if it isn't fast
enough to be
> > >>> used with
> > >>> (for example) clang -O2 or -O3, having such a precise
analysis
> > >>> would be a
> > >>> great baseline for doing other alias analysis work.
> > >>>
> > >>> Are you interested in contributing this to LLVM itself,
or just
> > >>> asking if
> > >>> people would be interested to see the code in some other
form?
> > >>>
> > >>> -Chris
> > >>
> > >>
> > >>
> > >> --
> > >> // Copyright @ 2011 Authorized by ** LIAN LI **
> > >> _______________________________________________
> > >> LLVM Developers mailing list
> > >> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > >
> >
> >
> >
> > --
> > // Copyright @ 2011 Authorized by ** LIAN LI **
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131022/0ea595b6/attachment.html>

----- Original Message -----
> 
> 
> 
> On Tue, Oct 22, 2013 at 9:55 AM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> 
> ----- Original Message -----
> > Hi Evan,
> > 
> > We did an experiment using the LLVM test suite: we compare the
> > overhead of using our analysis to the LLVM default, both with -O2
> > option.
> 
> It might also be interesting to try with -O3; I don't know if we have
> any significant vectorizable loops in the test suite with a large
> number of arrays, but if we do, this kind of analysis should help.
> 
> 
> 
> We perform loop vectorization at -O2 now?
You're right, we do. I had forgotten about that. The code in
Driver/Tools.cpp now reads:

/// \brief Vectorize at all optimization levels greater than 1 except for -Oz.
static bool shouldEnableVectorizerAtOLevel(const ArgList &Args) {

(and we SLP vectorize at -O1 too)

 -Hal
> 
> 
> 
> 
> > 
> > The overall overhead of compiling the whole test suite using our
> > analysis is 36.5%.
> 
> Maybe a good candidate for -fexpensive-optimizations? (or -O4?)
> 
> 
> 
> It would also be helpful to know what the execution performance
> impact is to provide context.
> 
> 
> 
> 
> > The biggest overhead is observed in
> > "SingleSource/Benchmarks/Misc/flops-5", where we are 5 times
> > slower:
> > 0.07s (with our analysis) compared to 0.0133s(default).
> > This may not be accurate as the compilation time in both cases are
> > quite small.
> 
> In my experience, compile-time measurements from a normal test-suite
> configuration less than 0.1s are too noisy to use.
> 
> 
> > 
> > Remind that the compilation time is reported by running our
> > analysis
> > over individual files, the compilation time overhead will be larger
> > if
> > we link all individual compilation units together and run the
> > analysis over the whole application.
> 
> Yes, LTO tests would be interesting too.
> 
> Thanks again,
> Hal
> 
> 
> 
> > 
> > Regards,
> > Lian
> > 
> > On Sat, Oct 19, 2013 at 7:56 AM, Evan Cheng < evan.cheng at
apple.com
> > >
> > wrote:
> > > 
> > > On Oct 17, 2013, at 10:51 PM, lian li < lianli at gmail.com
> wrote:
> > > 
> > >> Thanks, Chris.
> > >> 
> > >> We are interested in contributing it to LLVM itself. Our
manager
> > >> agrees to commit resources for maintenance needs if it is
> > >> accepted
> > >> by
> > >> the community.
> > > 
> > > This is great. Please make sure Oracle legal sign off on
> > > explicitly
> > > granting LLVM the use of the patents associated with the work.
> > > 
> > > On the compile time front, can you do a comparison with the LLVM
> > > default and your new AA? You can just build the LLVM test suite.
> > > 
> > > Thanks,
> > > 
> > > Evan
> > > 
> > >> 
> > >> Regards,
> > >> Lian
> > >> 
> > >> On Fri, Oct 18, 2013 at 3:43 PM, Chris Lattner
> > >> < clattner at apple.com > wrote:
> > >>> 
> > >>> On Oct 17, 2013, at 5:20 PM, lian li < lianli at
gmail.com >
> > >>> wrote:
> > >>> 
> > >>> Hi All,
> > >>> 
> > >>> This is Lian Li from Oracle Labs in Brisbane Australia.
> > >>> 
> > >>> We have developed a precise and highly efficient pointer
> > >>> analysis
> > >>> framework on top of LLVM, The approach is flow, context,
and
> > >>> field
> > >>> sensitive, details are described in the two papers below:
> > >>> 
> > >>> "Boosting the performance of flow-sensitive
points-to analysis
> > >>> using
> > >>> value flow" (in ESEC-FSE 2011), and
> > >>> "Precise and scalable context-sensitive pointer
analysis via
> > >>> value
> > >>> flow graph" (in ISMM 2013).
> > >>> 
> > >>> The analysis was initially developed for the purpose of
bug
> > >>> checking,
> > >>> and is now extended to support compiler optimizations. We
have
> > >>> tested
> > >>> it with existing compiler optimizations in LLVM, and have
seen
> > >>> promising results.
> > >>> 
> > >>> We are now considering to make this analysis available to
the
> > >>> LLVM
> > >>> community, and contribute resources for future
maintenance
> > >>> needs,
> > >>> provided that there is enough interest. We think that a
new
> > >>> precise
> > >>> pointer analysis in LLVM can enable more new optimization
and
> > >>> analysis
> > >>> techniques to be developed in LLVM.
> > >>> 
> > >>> Any people interested in seeing a new precise pointer
analysis
> > >>> in
> > >>> LLVM?
> > >>> 
> > >>> 
> > >>> This sounds very interesting. Even if it isn't fast
enough to
> > >>> be
> > >>> used with
> > >>> (for example) clang -O2 or -O3, having such a precise
analysis
> > >>> would be a
> > >>> great baseline for doing other alias analysis work.
> > >>> 
> > >>> Are you interested in contributing this to LLVM itself,
or just
> > >>> asking if
> > >>> people would be interested to see the code in some other
form?
> > >>> 
> > >>> -Chris
> > >> 
> > >> 
> > >> 
> > >> --
> > >> // Copyright @ 2011 Authorized by ** LIAN LI **
> > >> _______________________________________________
> > >> LLVM Developers mailing list
> > >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > > 
> > 
> > 
> > 
> > --
> > // Copyright @ 2011 Authorized by ** LIAN LI **
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > 
> 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Wed, Oct 23, 2013 at 3:07 AM, Chandler Carruth <chandlerc at
google.com> wrote:
> On Tue, Oct 22, 2013 at 9:55 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>> ----- Original Message -----
>>
>> It might also be interesting to try with -O3; I don't know if we
have any
>> significant vectorizable loops in the test suite with a large number of
>> arrays, but if we do, this kind of analysis should help.
>
>
> We perform loop vectorization at -O2 now?
>
We did an experimental with -O3, and the compilation overhead is about 32%.

The compilation time is reported by running the analysis once over the
linked bc file.
It turns out that for the LLVM test suite, running the analysis over
the linked bc file doesn't introduce much extra overhead.

Note that we run the analysis only once in the experiment. The
analysis is not rerun after it is invalidated by an optimization pass.
>>
>>
>> >
>> > The overall overhead of compiling the whole test suite using our
>> > analysis is 36.5%.
>>
>> Maybe a good candidate for -fexpensive-optimizations? (or -O4?)
>
>
> It would also be helpful to know what the execution performance impact is
to
> provide context.
According to our experiments with SPEC, we haven't observed
significant impact in terms of execution performance.
In our experiments, we run a list of 8 optimizations that require
alias analysis (including -licm, -gvn, -bb-vectorize,...), and for
each optimization we rerun our analysis so that
its result can be used by the optimization pass.  The biggest
performance improvement we observed is close to 3%, but for some
benchmarks we also have a slow down of 2%.
The overall performance improvement is less than 0.5%.

Regards,
Lian

>
>>
>>
>> > The biggest overhead is  observed in
>> > "SingleSource/Benchmarks/Misc/flops-5", where we are 5
times slower:
>> > 0.07s (with our analysis) compared to 0.0133s(default).
>> > This may not be accurate as the compilation time in both cases are
>> > quite small.
>>
>> In my experience, compile-time measurements from a normal test-suite
>> configuration less than 0.1s are too noisy to use.
>>
>> >
>> > Remind that the compilation time is reported by running our
analysis
>> > over individual files, the compilation time overhead will be
larger
>> > if
>> > we link all individual compilation units together and run the
>> > analysis over the whole application.
>>
>> Yes, LTO tests would be interesting too.
>>
>> Thanks again,
>> Hal
>>
>> >
>> > Regards,
>> > Lian
>> >
>> > On Sat, Oct 19, 2013 at 7:56 AM, Evan Cheng <evan.cheng at
apple.com>
>> > wrote:
>> > >
>> > > On Oct 17, 2013, at 10:51 PM, lian li <lianli at
gmail.com> wrote:
>> > >
>> > >> Thanks, Chris.
>> > >>
>> > >> We are interested in contributing it to LLVM itself. Our
manager
>> > >> agrees to commit resources for maintenance needs if it is
accepted
>> > >> by
>> > >> the community.
>> > >
>> > > This is great. Please make sure Oracle legal sign off on
explicitly
>> > > granting LLVM the use of the patents associated with the
work.
>> > >
>> > > On the compile time front, can you do a comparison with the
LLVM
>> > > default and your new AA? You can just build the LLVM test
suite.
>> > >
>> > > Thanks,
>> > >
>> > > Evan
>> > >
>> > >>
>> > >> Regards,
>> > >> Lian
>> > >>
>> > >> On Fri, Oct 18, 2013 at 3:43 PM, Chris Lattner
>> > >> <clattner at apple.com> wrote:
>> > >>>
>> > >>> On Oct 17, 2013, at 5:20 PM, lian li <lianli at
gmail.com> wrote:
>> > >>>
>> > >>> Hi All,
>> > >>>
>> > >>> This is Lian Li  from Oracle Labs in Brisbane
Australia.
>> > >>>
>> > >>> We have developed a precise and highly efficient
pointer analysis
>> > >>> framework on top of LLVM,  The approach is flow,
context, and
>> > >>> field
>> > >>> sensitive, details are described in the two papers
below:
>> > >>>
>> > >>> "Boosting the performance of flow-sensitive
points-to analysis
>> > >>> using
>> > >>> value flow" (in ESEC-FSE 2011), and
>> > >>> "Precise and scalable context-sensitive pointer
analysis via
>> > >>> value
>> > >>> flow graph" (in ISMM 2013).
>> > >>>
>> > >>> The analysis was initially developed for the purpose
of bug
>> > >>> checking,
>> > >>> and is now extended to support compiler
optimizations. We have
>> > >>> tested
>> > >>> it with existing compiler optimizations in LLVM, and
have seen
>> > >>> promising results.
>> > >>>
>> > >>> We are now considering to make this analysis
available to the
>> > >>> LLVM
>> > >>> community, and contribute resources for future
maintenance needs,
>> > >>> provided that there is enough interest. We think that
a new
>> > >>> precise
>> > >>> pointer analysis in LLVM can enable more new
optimization and
>> > >>> analysis
>> > >>> techniques to be developed in LLVM.
>> > >>>
>> > >>> Any people interested in seeing a new precise pointer
analysis in
>> > >>> LLVM?
>> > >>>
>> > >>>
>> > >>> This sounds very interesting.  Even if it isn't
fast enough to be
>> > >>> used with
>> > >>> (for example) clang -O2 or -O3, having such a precise
analysis
>> > >>> would be a
>> > >>> great baseline for doing other alias analysis work.
>> > >>>
>> > >>> Are you interested in contributing this to LLVM
itself, or just
>> > >>> asking if
>> > >>> people would be interested to see the code in some
other form?
>> > >>>
>> > >>> -Chris
>> > >>
>> > >>
>> > >>
>> > >> --
>> > >> // Copyright @ 2011 Authorized by ** LIAN LI **
>> > >> _______________________________________________
>> > >> LLVM Developers mailing list
>> > >> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> > >
>> >
>> >
>> >
>> > --
>> > // Copyright @ 2011 Authorized by ** LIAN LI **
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> >
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>


-- 
// Copyright @ 2011 Authorized by ** LIAN LI **

On 10/23/2013 7:52 AM, lian li wrote:
> According to our experiments with SPEC, we haven't observed 
> significant impact in terms of execution performance. In our 
> experiments, we run a list of 8 optimizations that require alias 
> analysis (including -licm, -gvn, -bb-vectorize,...), and for each 
> optimization we rerun our analysis so that its result can be used by 
> the optimization pass. The biggest performance improvement we observed 
> is close to 3%, but for some benchmarks we also have a slow down of 
> 2%. The overall performance improvement is less than 0.5%.
Would it be possible to measure performance improvement for a large 
application or two that compiles with -fno-strict-aliasing?

-- 
Joshua Cranmer
Thunderbird and DXR developer
Source code archæologist