<div dir="ltr"><div><div><div><div><div>Hi Aries,<br><br></div>regarding the person who proposed a range analysis for GSOC some years ago, it is likely to have been me. I am one of the authors of a range analysis for LLVM:<br><br><a href="https://code.google.com/archive/p/range-analysis/">https://code.google.com/archive/p/range-analysis/</a><br><br></div><div>The analysis is described here:<br><a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6494996&tag=1">http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6494996&tag=1</a><br></div><div><br>It's pretty fast already (less than 2 seconds to run on SPEC's gcc), with very good precision. I keep it up to date with the newer versions of LLVM, and eventually we might try to incorporate it into the trunk. Thus we consider the implementation finished.<br><br></div></div>One guy in last year's GSOC proposed a floating-point range analysis, but I'm not sure what happened then. Send me an email in case you need to know anything about our project.<br><br></div>Good luck!<br><br></div>Victor.<br></div><div class="gmail_extra"><br><div class="gmail_quote">2016-03-22 18:13 GMT-06:00 Philip Reames via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>:<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 class="">
<br>
<br>
<div>On 03/20/2016 05:38 AM, Aries Gunawan
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div>
<p class="MsoNormal">Hi everyone,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I am very interested in contributing to
LLVM project in this year’s GSoC. I am new with LLVM, but this
is used in the compiler course in my university. So, I am
thinking to involve in LLVM development to have a better
knowledge of the system. Currently, I am preparing the
proposal. <u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">One of the project that caught my eyes is
“New Transformations and Analysis”. Several code
transformations and analyses have been introduced in the
compiler course that I am currently taking. That’s why I am
thinking to involve in writing some new transformations and
code analyses. But the list of transformations in the LLVM
Open Projects web page seems too brief for me and I need more
details on those stuffs.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><b>Loop Dependence Analysis Infrastructure.
</b>I have looked in the source codes repo and I saw that
there is a file named “DependenceAnalysis.cpp”. So, does that
mean this analysis has been implemented?
</p>
</div>
</blockquote></span>
I believe major progress has been made it, but haven't been
following it closely. I'd suggest talking to committers active in
this file in the recent past to determine what useful work might be
left of appropriate scope. <br><span class="">
<blockquote type="cite">
<div>
<p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><b><u></u> <u></u></b></p>
<p class="MsoNormal"><b>Value range propagation pass. </b>There
was a discussion about this topic (<a href="https://groups.google.com/forum/#%21topic/llvm-dev/XXqfemtDX74/discussion" target="_blank">https://groups.google.com/forum/#!topic/llvm-dev/XXqfemtDX74/discussion</a>).
Someone already proposed to do this pass for several years ago
GSoC. But I can’t find the progress of the work. If no
progress, then does it mean that the VRP based on Patterson’s
paper need to be implemented although range analysis has been
implemented?</p>
</div>
</blockquote></span>
This is largely stalled. The key problem is that between
LazyValueInfo (constant ranges) and SCEV (symbolic ranges in loops),
there's fairly little profit to be had and range analysis is
relatively expensive. I'd strongly discourage you from implementing
a traditional range analysis for LLVM without deeply understanding
the history here. <br><span class="">
<blockquote type="cite">
<div>
<p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><b><u></u> <u></u></b></p>
<p class="MsoNormal"><b>Predictive Commoning. </b>The
presentation side by Arie Tal seems provide quite clear
explanation and examples of the algorithm. I guess the
implementation should be straightforward, isn’t it?</p>
</div>
</blockquote></span>
The closest I know of to this in tree is LoadLoadElimination.cpp and
(in some cases) the PRE code inside GVN.cpp. Building something
like this on top of SCEV could be quite interesting. You should
definitely talk to Adam Nemet (CC'd) about this.<span class=""><br>
<blockquote type="cite">
<div>
<p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><b><u></u> <u></u></b></p>
<p class="MsoNormal"><b>Type Inference (aka. Devirtualization)
and Value assertions.
</b><u></u><u></u></p>
<p class="MsoNormal">Can I get more details of these topics?
Does the type inference mean the translation of
<u>auto</u> keyword or something else? For value assertions,
“unreachable” intrinsic seems has been implemented cause I can
find the usage in some of the testcases.</p>
</div>
</blockquote></span>
I believe the "value assertions" link may be stale. If I'm reading
that correctly, it looks like the motivation for @llvm.assume.<span class=""><br>
<blockquote type="cite">
<div>
<p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Finally, for this project, must I propose
to do all of these analyses and transformations in my GSoC
proposal or can I just propose some of them? In addition, I am
also looking for a mentor for guidance?</p>
</div>
</blockquote></span>
If you want further ideas, consider the list I just sent to llvm-dev
a few moments ago titled "A couple ideas for possible GSoC
projects". <br>
<blockquote type="cite"><span class="">
<div>
<p class="MsoNormal"><u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Looking forward for your comments and
feedbacks.<u></u><u></u></p>
<p class="MsoNormal">Thank you.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Best regards,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Aries Thio.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<br>
<fieldset></fieldset>
<br>
</span><pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>