<div dir="ltr">Hello John,<br><br>I've finished the first version of my proposal on enhancing alias analysis.<br>The proposal can be downloaded at <a href="http://james0zan.github.io/resource/GSoC15-Proposal-AA.pdf">http://james0zan.github.io/resource/GSoC15-Proposal-AA.pdf</a>.<br>I hope I've successfully justified the necessity and benefits of this project.<br>If possible, please find some time to review it and give me some more feedbacks.<br><br>Thank you very much!<br><br>P.S. I'm working on the other proposal, a couple of days is needed.<br><br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On 8 March 2015 at 21:42, Mingxing Zhang <span dir="ltr"><<a href="mailto:james0zan@gmail.com" target="_blank">james0zan@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>Got it.<br></div>I'll try to find the applications for field-sensitivity (and interprocedural, etc) AA analysis.<br></div>And I'll do some preliminary evaluation on the tracing/slicing part for the bloat detection.<br><br></div>Thanks!<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On 8 March 2015 at 21:34, John Criswell <span dir="ltr"><<a href="mailto:jtcriswel@gmail.com" target="_blank">jtcriswel@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><span>
<div>On 3/8/15 8:56 AM, Mingxing Zhang
wrote:<br>
</div>
</span><blockquote type="cite">
<div dir="ltr">
<div>Hello John,<br>
<br><span>
According to the FAQ, I can submit two proposals although at
most one of them can be accepted.<br>
Thus I will prepare a proposal for each of the two projects.<br>
</span></div>
</div>
</blockquote>
<br>
Correct. Only one proposal will be accepted.<span><br>
<br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>And, after reading the code of cfl-aa and several related
papers, I've listed four milestones for the AA project: <br>
<br>
1) In order to use the fast algorithm described in PLDI'13
[1], cfl-aa makes a simplification on the CFL defined in
POPL'08 [2], which will lead to a reduction on precision (I've
confirmed this observation with the author).<br>
Thus a quantitative measurement on how much is the reduction
is needed.<br>
<br>
2) In cfl-aa, different fields of a same struct and the whole
array are represented by a single node.<br>
This is the reason of the problem 2, 4 listed in <a href="http://llvm.org/OpenProjects.html" target="_blank">http://llvm.org/OpenProjects.html</a>.<br>
We should split these large nodes.<br>
</div>
</div>
</blockquote>
<br></span>
I think the real question is whether the loss of precision matters,
and if so, to which uses of alias analysis. SAFECode, for example,
wants field information to determine type safety (so that it can
optimize away type-safe loads and stores), so field sensitivity
matters. Perhaps field sensitivity doesn't matter for other
applications (e.g., optimization). There's no point in improving
precision if it doesn't help the analyses that people care about
most.<br>
<br>
As part of your project, I think you should state the uses of alias
analysis/points-to analysis that you're aiming to improve and
understand whether your proposed improvements will help that use. I
would also recommend picking a use that matters to a significant
portion of the LLVM community.<span><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
3) Handling special global variables, such as errno.<br>
<br>
4) It seems that the current version of cfl-aa is an
intraprocedural analysis.<br>
If the time is enough, I think we may extend it to an
interprocedural analysis.<br>
The algorithm described in [3] can be applied to scaling it.<br>
<br>
As for the bloat-detection project, the final result should be
a tool that is verified by known bugs and a set of newly
detected bugs.<br>
</div>
</div>
</blockquote>
<br></span>
For the bloat detection tool, I would like to be convinced that
dynamic tracing will be, or can be, sufficiently efficient to be
practical. I hate to ask, but I think you need to run an experiment
with Giri to show that dynamic slicing is going to be practical for
the executions that you expect to analyze. Either that, or you need
to explain how you can use something more efficient than dynamic
slicing (note that dynamic slicing and dynamic tracing are not the
same, so be sure you're correctly stating which one you need).<span><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
Do you have any suggestions on these objectives?<br>
</div>
</div>
</blockquote>
<br></span>
In your proposal, be sure to include a set of milestones and how
long you think you will need to achieve those milestones. I may
have said that before, but it's worth repeating.<br>
<br>
Regards,<br>
<br>
John Criswell<div><div><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
Thanks!<br>
<br>
<br>
</div>
[1] Fast Algorithms for Dyck-CFL-Reachability with Applications
to Alias Analysis. PLDI'13<br>
<div>[2] Demand-Driven Alias Analysis for C. POPL'08<br>
[3] Demand-Driven Context-Sensitive Alias Analysis for Java.
ISSTA'11<br>
<br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On 5 March 2015 at 09:58, Mingxing
Zhang <span dir="ltr"><<a href="mailto:james0zan@gmail.com" target="_blank">james0zan@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote">
<div dir="ltr">
<div>
<div>Wow, that is cool!<br>
</div>
I'll check about it.<br>
<br>
</div>
Thank you!<br>
</div>
<div>
<div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On 4 March 2015 at 21:57,
John Criswell <span dir="ltr"><<a href="mailto:jtcriswel@gmail.com" target="_blank">jtcriswel@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote">
<div><span>
<div>On 3/4/15 2:18 AM, Mingxing Zhang wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hello John,<br>
<br>
Thank you for your advices and
congratulations~<br>
<br>
I'll read the code of cfl-aa and Giri
first and make the decision of which
project to pursue.<br>
The choice will be reported to this thread
once I made the determination (hopefully
within this week).<br>
</div>
</blockquote>
<br>
</span> You should check for yourself, but I
don't think anything prevents you from
submitting two proposals. If you have time to
write two strong proposals, I see no problem
with that.<br>
<br>
Just make sure that any proposal you write is
strong: it provides a concrete explanation of
what you want to do, some justification for why
it would benefit the community (short or long
term), and why you're the person qualified to do
it. Proposals should also include a set of
milestones and expected dates for completing
those milestones.<br>
<br>
Regards,<br>
<br>
John Criswell
<div>
<div><br>
<br>
<blockquote type="cite">
<div dir="ltr"><br>
Thanks!<br>
<br>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On 3 March 2015
at 23:12, John Criswell <span dir="ltr"><<a href="mailto:jtcriswel@gmail.com" target="_blank">jtcriswel@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote">
<div>
<div>Dear Mingxing,<br>
<br>
I think both projects are
interesting and useful.<br>
<br>
Points-to analysis is something
that is needed by research users
of LLVM, but to the best of my
knowledge, no solid
implementation currently exists
(although the cfl-aa work being
done at Google may provide us
with something; you should check
into it before writing a
proposal). My interest is in a
points-to analysis that is
robust and is useful to both
research and industry users of
LLVM. A points-to analysis
proposal must indicate how it
will help both of these subsets
of the LLVM community, and it
must argue why current efforts
do not meet the requirements of
both subsets of the community.<br>
<br>
The runtime bloat tool also
looks interesting, and your
approach (at least to me) is
interesting. One question in my
mind, though, is whether dynamic
slicing is going to work well.
Swarup Sahoo and I built a
dynamic slicer for LLVM named
Giri, and we found the tracing
required for dynamic slicing to
be slow. For our purposes, the
overhead was okay as we only
needed to record execution until
a crash (which happened
quickly). In your bloat tool,
the program will probably run
for awhile, creating a long
trace record. You should take a
look at the Giri code, use it to
trace some programs, and see if
the overheads are going to be
tolerable. If they are not,
then your first task would be to
optimize Giri for your bloat
tool.<br>
<br>
You should also be more specific
about which LLVM instructions
will be traced. For example, I
wouldn't record the outputs of
every LLVM instruction; I might
only record the outputs of loads
and stores or the end of a
def-use chain.<br>
<br>
I'd be interested in mentoring
either project.<br>
<br>
BTW, it looks like your FSE
paper won an award. Congrats.<br>
<br>
Regards,<br>
<br>
John Criswell
<div>
<div><br>
<br>
<br>
<br>
<br>
<br>
<br>
On 3/3/15 2:30 AM, Mingxing
Zhang wrote:<br>
</div>
</div>
</div>
<blockquote type="cite">
<div>
<div>
<div dir="ltr">Hi all,<br>
<br>
As a Ph.D. student majored
in Software Reliability, I
have used LLVM in many of
my projects, such as the
Anticipating Invariant (<a href="http://james0zan.github.io/AI.html" target="_blank">http://james0zan.github.io/AI.html</a>)
and some other undergoing
ones.<br>
Thus, it would be a great
pleasure for me if I could
take this opportunity to
contribute to this awesome
project.<br>
<br>
After reading the idea
list (<a href="http://llvm.org/OpenProjects.html" target="_blank">http://llvm.org/OpenProjects.html</a>),
I was most interested in
the idea of improving the
"Pointer and Alias
Analysis" passes.<br>
Could you please give me
some more tips or advices
on how to get started on
working on the
application?<br>
<br>
Simultaneously, I also
have another idea about
using LLVM to detect
runtime bloat, just like
the ThreadSanitizer tool
for data races.<br>
If there is anyone here
who would like to mentor
this project, could you
please find some time to
review the <a href="https://gist.github.com/james0zan/d03737c60b10d0d11d34" target="_blank">more
detailed proposal on
gist</a> and give me
some feedbacks?<br>
<br>
P.S. <br>
I do prefer the bloat
detection tool, but I'm
not sure about whether it
is suitable for GSoC.<br>
Thus I will apply for
the Alias Analysis one if
it is not suitable.<br>
<br>
Thanks!<br>
<br>
-- <br>
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>Mingxing
Zhang
<div><br>
</div>
<div>Tel.: <a href="tel:%2B86-10-62797143" value="+861062797143" target="_blank">+86-10-62797143</a><br>
</div>
<div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br>
</div>
<div>Addr: Room
3-122, FIT
Building,
Tsinghua
University,
Beijing
100084, China</div>
</div>
</div>
</div>
</div>
</div>
</div>
<br>
<fieldset></fieldset>
<br>
</div>
</div>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
/<span><br>
<br>
<pre cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank">http://www.cs.rochester.edu/u/criswell</a></pre>
</span></div>
</blockquote>
</div>
<br>
<br>
<br>
-- <br>
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>Mingxing Zhang
<div><br>
</div>
<div>Tel.: <a href="tel:%2B86-10-62797143" value="+861062797143" target="_blank">+86-10-62797143</a><br>
</div>
<div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br>
</div>
<div>Addr: Room 3-122, FIT
Building, Tsinghua
University, Beijing 100084,
China</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<br>
<pre cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank">http://www.cs.rochester.edu/u/criswell</a></pre>
</div>
</div>
</div>
</blockquote>
</div>
<br>
<br>
<br>
-- <br>
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>Mingxing Zhang
<div><br>
</div>
<div>Tel.: <a href="tel:%2B86-10-62797143" value="+861062797143" target="_blank">+86-10-62797143</a><br>
</div>
<div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br>
</div>
<div>Addr: Room 3-122, FIT Building,
Tsinghua University, Beijing 100084, China</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
<br>
<br>
-- <br>
<div>
<div dir="ltr">
<div>
<div dir="ltr">
<div>Mingxing Zhang
<div><br>
</div>
<div>Tel.: <a href="tel:%2B86-10-62797143" value="+861062797143" target="_blank">+86-10-62797143</a><br>
</div>
<div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br>
</div>
<div>Addr: Room 3-122, FIT Building, Tsinghua
University, Beijing 100084, China</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<br>
<pre cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank">http://www.cs.rochester.edu/u/criswell</a></pre>
</div></div></div>
</blockquote></div><br><br clear="all"><br>-- <br><div><div dir="ltr"><div><div dir="ltr"><div>Mingxing Zhang<div><br></div><div>Tel.: <a href="tel:%2B86-10-62797143" value="+861062797143" target="_blank">+86-10-62797143</a><br></div><div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br></div><div>Addr: Room 3-122, FIT Building, Tsinghua University, Beijing 100084, China</div></div></div></div></div></div>
</div>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div>Mingxing Zhang<div><br></div><div>Tel.: +86-10-62797143<br></div><div>Web: <a href="http://james0zan.github.io/" target="_blank">http://james0zan.github.io/</a><br></div><div>Addr: Room 3-122, FIT Building, Tsinghua University, Beijing 100084, China</div></div></div></div></div></div>
</div>