<div dir="ltr">Hi all,<div><br></div><div><font face="arial, helvetica, sans-serif">I had a second thought of the dynamic slicing, as well as the source code generating.</font></div><div><font face="arial, helvetica, sans-serif"><br>


</font></div><div><font face="arial, helvetica, sans-serif">Firstly, the dynamic slicing is very useful to software community (I'll illustrate more in the refined proposal later), but it's already implemented by Swarup and John Criswell from UIUC. The static slicing code has been released as Giri project in LLVM, and they would kindly release the dynamic slicing too if this proposal is accepted. </font></div>


<div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">I'd like to study and enhance the Giri code to make it better. However, I don't know the exact part to which I can contribute. I'll ask Swarup (I cc this email to him) for help. I would be honored to be directed by him if this proposal is selected.</font></div>


<div><br></div><div><span style="font-family:arial,helvetica,sans-serif">Moreover, I don't know how the static and dynamic slicing fit together. Does the static code of Giri need some improvements? For example, taking into consideration the pointer aliases. Our group need the static slicing to generate I/O benchmarks (see below please).</span></div>


<div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">Secondly, to generate source code, which is human-readable and compilable seems</span><font face="arial, helvetica, sans-serif"> a bit ambitious. My previous scripts in python can generate the source code of the original program by deleting useless line of code. It's kind of tricky. We used dozens of regular expressions to match the boundary of blocks, loops and functions to avoid deleting lines unexpectedly. I thought employing clang was a better idea. I don't know whether you think the source code genration is a good idea or not. I can release our simple script and improve it later. So I have more time/energy to contribute to the dynamic slicer.</font></div>


<div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">I think the slicing pass can be loaded by the opt. There is no need to change the front-end or other passes. I'm not sure whether the link time optimization can be exploited. We borrowed the LLVMSlicer code previously without LTO.</font></div>


<div class="gmail_extra"><br></div><div class="gmail_extra">Lastly, I'd like to introduce myself briefly. I'm a three-years PhD candidate student from Tsinghua University, China. My research area covers performance analysis, compiler techniques for high performance computing, and parallel computing (MPI/OpenMP). </div>


<div class="gmail_extra"><br></div><div class="gmail_extra">One of my on-going work is to generate an I/O benchmark from the original application. The base observation is that the computation and communication statements can be deleted if they're irrelevant to the I/O pattern, e.g. computing the buffer content to be written into a file. We take use of the program slicing technique to find relevant/irrelevant statements. The static slicer was borrowed from LLVMSlicer and I wrote code to make it work for our application. We generated the line number of sliced code. There is a very simple source code generation script using ugly and tricky regular expressions to delete original source code according to the sliced line number. We're going to submit the first version of the paper recently.</div>


<div class="gmail_extra"><br></div><div class="gmail_extra">I also took part in one project in Open64 compiler several year ago, the purpose of which is to fast collect the communication trace. We used program slicing to delete the computation statements and kept the communication related statements. We generated executable binaries instead of source code from IR.</div>


<div class="gmail_extra"><br></div><div class="gmail_extra">Now we plan to do a project that can automatically find manual configuration errors in software deployment. The dynamic slicing can help a lot since the input is the key factor to locate errors. We have not a concrete plan for this project, but the dynamic slicing is heavily needed.</div>


<div class="gmail_extra"><br></div><div class="gmail_extra">Regards.</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, May 2, 2013 at 8:00 AM, Sahoo, Swarup Kumar <span dir="ltr"><<a href="mailto:ssahoo2@illinois.edu" target="_blank">ssahoo2@illinois.edu</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">




<div style="word-wrap:break-word">
<div style="direction:ltr;font-size:10pt;font-family:Tahoma">Hi Mingliang,<br>
<br>
    We already implemented an usable version of Dynamic Backward Slicing as part of our ASPLOS paper. So, I think this will be a good idea to extend this project. I will also be interested in mentoring you for this project. Please let me know, if you need any
 help.<br>
<br>
Thanks,<br>
Swarup.<br>
<br>
<div style="font-size:16px;font-family:'Times New Roman'">
<hr>
<div style="direction:ltr"><font color="#000000" face="Tahoma"><b>From:</b> <a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.uiuc.edu</a> [<a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.uiuc.edu</a>] on behalf of Mingliang LIU [<a href="mailto:liuml07@mails.tsinghua.edu.cn" target="_blank">liuml07@mails.tsinghua.edu.cn</a>]<br>



<b>Sent:</b> Saturday, April 27, 2013 2:53 PM<br>
<b>To:</b> LLVM<br>
<b>Subject:</b> [LLVMdev] GSoC Proposal: Inter-Procedure Program Slicing in LLVM<br>
</font><br>
</div><div><div>
<div></div>
<div>Hi all,
<div><br>
</div>
<div>
<div>This is a GSoC 2013 proposal for LLVM project. Please see the formatted version at here: <span style="text-decoration:underline;color:rgb(71,135,255)"><a href="http://pacman.cs.tsinghua.edu.cn/~liuml07/files/gsoc2013-proposal-program-slicing.pdf" target="_blank">http://pacman.cs.tsinghua.edu.cn/~liuml07/files/gsoc2013-proposal-program-slicing.pdf</a></span></div>



<div><span style="text-decoration:underline;color:rgb(71,135,255)"><br>
</span></div>
<div>Program slicing has been used in many applications, the criteria of which is a pair of statement and variables. I would like to write an inter-procedural program slicing pass in LLVM, which is able to calculate C program slices of source code effectively.
 There is no previous work implemented in LLVM, which considers both the dynamic program slicing and source code of the sliced program. Program slice contains all statements in a program that directly or indirectly act the value of a variable occurrence [5].
 Program slicing has been used in many applications, e.g., program verification, testing, maintenance, automatic parallelization of program execution, automatic integration of program versions.</div>
<div><br>
</div>
<div>While it's straightforward to implement the slicer in the back-end of compiler using SSA form, the source code of the original program instead of intermediate</div>
<div>representation is preferred in most cases. Moreover, we can further narrow the notion of slice, which contains statements that influence the value of a</div>
<div>variable occurrence for speci c program inputs. This is referred as dynamic program slicing [1]. However, there is no previous work implemented in LLVM</div>
<div>which solved the two problems.</div>
</div>
<div><br>
</div>
<div>
<div>There are two public projects which implement the backwards static slicing in LLVM.</div>
<div>
<ul>
<li>Giri Written by John Criswell from UIUC, a subproject of LLVM. The Giri code contains the static backwards intra-procedure slicing passes, and runs with an older version of LLVM. It also only backtracks until it hits a load. Additional code must be written
 to backtrack further to find potentially reaching stores.</li><li>LLVMSlicer This implementation is a complete static backwards slicer from Masaryk University. It works on the well de ned data and control flow equations in a white paper by F. Tip [4]. However, this code was written for special purpose, thus it's not general
 enough to be use by others. They implemented the Andersen's alias algorithm [2], callgraph, and modi es analysis to support the slicer, instead of using the LLVM APIs.</li></ul>
</div>
<div><br>
</div>
<div>They eliminate the useless IR statements and keep the ones a ect the values of the criteria. However, neither of them generates the compilable source code</div>
<div>slice, which is heavily needed in reality. There are several ways to do this. One is to generate the source code from sliced IR using llc tool. The issue is that</div>
<div>the IR is not concerned with high-level semantic. The generated source code is different from the original program and not suitable for human reading. An-</div>
<div>other approach is deleting the source code according to sliced IR, with line number information (in meta-data of each instruction). The naive script deleting</div>
<div>sliced source code one by one fails to handle tricky cases. I think a better source code slicer is to take use of the AST info.</div>
</div>
<div>
<div><br>
</div>
<div>There are three main parts of this work.</div>
<div>
<ol>
<li>First, borrow an implementation of static back-wards slicing from Giri or LLVMSlicer, and use the LLVM callgraph, mod/ref and alias interfaces as much as possible.</li><li>Second, implement the dynamic program slicing using the approach 3 in the paper [1].</li>


<li>Third, generate the source code of the sliced program. To make the sliced source code compile directly, we need to employ clang front-end</li></ol>
</div>
</div>
<div><br>
</div>
<div>
<div>The final result of this summer of code is to make this pass work e effectively and documented well. Further, I'll write test cases and behave as the active</div>
<div>maintainer for this project. My long-term plan is to add more features, e.g. Objective-C/C++ support, thing slicing [3], to this project.</div>
<div><br>
</div>
<div>Any comment is highly appreciated.</div>
<div><br>
</div>
<div><br>
</div>
<div>
<div>[1] H AGRAWAL. Dynamic Program Slicing. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI),1990.</div>
<div>
<div>2] L.O. Andersen. Program analysis and specialization for the C programming language. PhD thesis, University of Cophenhagen, Germany, 1994.</div>
<div>[3] M. Sridharan, S.J. Fink, and R. Bodik. Thin slicing. In PLDI'07, 2007.</div>
<div>[4] F. Tip. A survey of program slicing techniques.Journal of Programming Languages, 1995.</div>
<div>[5] M. Weiser. Program slicing. In Proceedings of the 5th International Conference on Software Engineering, ICSE, pages 439{449. IEEE, 1981.</div>
</div>
<div><br>
</div>
<div>
<div>--<br>
Mingliang LIU (刘明亮 in Chinese)<br>
<br>
PACMAN Group,  Dept. of Computer Science & Technology<br>
Tsinghua University, Beijing 100084, China<br>
Email: <a href="mailto:liuml07@mails.tsinghua.edu.cn" target="_blank">liuml07@mails.tsinghua.edu.cn</a><br>
Homepage: <a href="http://pacman.cs.tsinghua.edu.cn/~liuml07/" target="_blank">http://pacman.cs.tsinghua.edu.cn/~liuml07/</a>
</div>
<br>
</div>
</div>
</div>
</div>
</div></div></div>
</div>
</div>

</blockquote></div><br><br clear="all"><div><br></div>-- <br><span style="color:rgb(102,102,102)">Mingliang Liu (刘明亮 in Chinese)</span><br style="color:rgb(102,102,102)"><br style="color:rgb(102,102,102)"><span style="color:rgb(102,102,102)">PACMAN Group,  Dept. of Computer Science & Technology</span><br style="color:rgb(102,102,102)">


<span style="color:rgb(102,102,102)">Tsinghua University, Beijing 100084, China</span><font color="#666666"><br></font><span style="color:rgb(102,102,102)">Email: <a href="mailto:liuml07@mails.tsinghua.edu.cn" target="_blank">liuml07@mails.tsinghua.edu.cn</a></span>
</div></div>