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

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?

Regards,
Lian Li







--

Hi Lian,

I am certainly interested in seeing this; do you have performance numbers
(compile time)? Also, can you share more information about the promising
optimization results you mentioned?

Thanks,
Hal

----- Original Message -----
> 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?
> 
> Regards,
> 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

Hi Hal,

Thanks for your interest.

We tested with the following existing compiler optimizations in LLVM
with SPECINT2006 benchmarks:
-dse (dead store elimination),
-gvn (global value numbering),
-licm (loop invariant code motion),
-bb-vectorize (basic block vectorization),
-memcpyopt (memcpy optimization),
-sink (code sinking),
-loop-idom (recognize loop idioms),
-argpromotion (argument promotion).

As far as I know, this list includes all optmizations in LLVM that
requires alias information. With our pointer analysis, for the three
optimizations "-dse, -gvn, -licm", we have observed significant
improvements in terms of the number of optimizations being conducted.
Take licm as an example, with our analysis, the number of instructions
being hoisted out of loops more than doubled for some benchmarks. We
have not seen big changes in terms of runtime performance though.

We measure compile time by first linking all modules of the same
benchmark together, then running the analysis against the linked
module. It finishes in less than 1 minute over applications such as
httpd and sendmail, both with more than 100,000 LOC. For some
benchmarks, it is time-consuming: the analysis time for GCC is close
to 45 minutes.  But if you run the analysis over individual files (as
in your normal compilation process), there is no observable overhead
in terms of compile time.

Regards,
Lian



On Fri, Oct 18, 2013 at 12:15 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> Hi Lian,
>
> I am certainly interested in seeing this; do you have performance numbers
(compile time)? Also, can you share more information about the promising
optimization results you mentioned?
>
> Thanks,
> Hal
>
> ----- Original Message -----
>> 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?
>>
>> Regards,
>> 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


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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131017/0821f893/attachment.html>

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.

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 **