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