<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 3/29/12 3:59 PM, Victor Campos wrote:
<blockquote
cite="mid:CAM-fum5EWnt+3J1QK-4E0FjN86KwOWja2uT3itnZ1a36mMrDCg@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<div>Dear LLVMers,</div>
<div><br>
</div>
<div> I have been working on Douglas's range analysis, and
today, after</div>
<div>toiling with it for two years, we have a very mature and
robust</div>
<div>implementation, which is publicly available at</div>
<div><a moz-do-not-send="true"
href="http://code.google.com/p/range-analysis/"
target="_blank">http://code.google.com/p/range-analysis/</a>.
We can, at this point,</div>
<div>perform range analysis on very large benchmarks in a few
seconds. To</div>
<div>give you an idea, we take less than 10 seconds to globally
analyze</div>
<div>SPEC 2006 gcc benchmark with function inlining enabled. And
the</div>
<div>analysis is fairly precise. We have a gallery of examples at</div>
<div><a moz-do-not-send="true"
href="http://code.google.com/p/range-analysis/wiki/gallery"
target="_blank">http://code.google.com/p/range-analysis/wiki/gallery</a>
that will give</div>
<div>you an idea of what kind of information we can find. Our
analysis</div>
<div>comes together with a dynamic profiler that points the
minimum and</div>
<div>maximum values that each variable assumes during program
execution</div>
<div>too. And it uses a live range splitting strategy to obtain
data-flow</div>
<div>sparsity that is lightning fast. It is more than 100x faster
than the</div>
<div>original implementation of SSI in LLVM 2.7, for instance.
There are a</div>
<div>number of LLVMers, outside my university, that use our
analysis.</div>
</blockquote>
<br>
What version of LLVM does your analysis use currently?<br>
<br>
It sounds like your analysis is fast. Can you show results on how
fast it is on various programs? Do you have measurements on how
much memory it uses? How large is the largest program you've
compiled with it?<br>
<br>
<blockquote
cite="mid:CAM-fum5EWnt+3J1QK-4E0FjN86KwOWja2uT3itnZ1a36mMrDCg@mail.gmail.com"
type="cite">
<div> So, I would like to propose a summer of code that consists
in (i)</div>
<div>integrating our infra-structure in the LLVM main tree, and
(ii)</div>
<div>writing a dead-code elimination pass that uses the analysis
as a</div>
<div>client. So far people have been using our analysis to check
for buffer</div>
<div>overflows, and to eliminate array bound checks.</div>
</blockquote>
<br>
If possible, I think you should first implement the dead-code
elimination optimization that uses your analysis to show how much of
a performance win your analysis provides for LLVM. If the
optimization is sufficiently fast and provides enough of a speedup,
then it can be integrated into LLVM (because you will have proof
that it is a performance win; that will help convince current
developers with commit access to review your code for inclusion).<br>
<br>
We in the SAFECode project would be interested in trying your
analysis out for eliminating bounds checks. We just haven't had the
time to do that yet (I'm assuming you're the same person that wanted
to do Value Range analysis last year).<br>
<br>
<blockquote
cite="mid:CAM-fum5EWnt+3J1QK-4E0FjN86KwOWja2uT3itnZ1a36mMrDCg@mail.gmail.com"
type="cite">
<div> Yet, I think there is</div>
<div>a lot of potential to optimizations. Dead code elimination at
branches</div>
<div>would be one such optimization. Given that the analysis is
pretty</div>
<div>mature, I think that it would not be too difficult to
integrate it in</div>
<div>the current infra-structure that LLVM offers, e.g., Lazy
Values. As</div>
<div>for dead-code, we already can flag variables that have
impossible</div>
<div>intervals, in which the lower bound is larger than the upper
bound.</div>
<div>So, it is only a matter of adapting it to remove this code.</div>
</blockquote>
<br>
<br>
Regarding a dead-code elimination algorithm, I can see something
like an Aggressive Dead Code Elimination pass using your analysis to
prove that certain branches are never taken. One thing you could do
would be to write a pass that looks for icmp instructions and uses
your analysis to change them to true/false when possible. SCCP,
ADCE, and other optimizations would then take care of the rest.<br>
<br>
The idea of integrating your pass as a lazy value pass sounds good.
The question I have is what optimizations benefit from LazyInfo? I
only see one or two transforms that use it in LLVM 3.0.<br>
<br>
<blockquote
cite="mid:CAM-fum5EWnt+3J1QK-4E0FjN86KwOWja2uT3itnZ1a36mMrDCg@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>I would like to hear from you what you think about this
Summer of Code</div>
<div>project. If you think it could be interesting, I will write a
proposal</div>
<div>richer in details.</div>
</blockquote>
<br>
My interest in range analysis is for using it with SAFECode, but if
it can be used for standard compiler optimization and gets
integrated into LLVM, all the better for me.<br>
<br>
-- John T.<br>
<blockquote
cite="mid:CAM-fum5EWnt+3J1QK-4E0FjN86KwOWja2uT3itnZ1a36mMrDCg@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>Sincerely yours,</div>
<div><br>
</div>
<div>Victor</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>