Dear LLVM community,<br><br>A revised version of my GSoC proposal is listed below. Please, let me know your comments.<br><br><h1 style="text-align: center; margin-top: 0pt; margin-bottom: 0pt;" id="internal-source-marker_0.3250383698050683">

<font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Adding Range Analysis to LLVM</span></font></h1>

<span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Abstract</span></font><br><span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">The
 objective of this work is patch our implementation of range analysis 
into LLVM. I have a working implementation of range analysis in LLVM, 
but it is not currently part of the main distribution. I propose to 
integrate our range analysis implementation into the Lazy Value Info 
(LVI) interface that LLVM provides. Range analysis finds the intervals 
of values that may be bound to the integer variables during the 
execution of programs and is useful in several scenarios: constant 
propagation, detection of potential buffer overflow attacks, dead branch
 elimination, array bound check elimination, elimination of overflow 
tests in scripting languages such as JavaScript and Lua, etc.</span></font><br><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;"></span><br><font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Objective</span></font><br>

<span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">The
 objective of this project is to augment LLVM with range analysis. We 
will do this integration by patching the current implementation of range
 analysis that we have onto the Lazy Value Info (LVI) interface that 
LLVM already provides. In addition, we will develop new optimizations 
using LVI. In particular, we will provide a pass that performs 
conditional constant propagation [5], and elimination of dead-branches.</span></font><br><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Criteria of Success</span><ul>

<li style="list-style-type: disc; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">To
 improve substantially the precision of the current implementation of 
LVI. Currently, LVI’s interface only allows a client to know if a 
variable contains a constant. We want to allow LVI to report that a 
variable either contains a constant, or a known-range.</span></font></li><li style="list-style-type: disc; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">To
 improve the current implementation of constant propagation that LLVM 
uses. We hope to obtain a small performance gain on the C benchmarks in 
the LLVM test suite, and a larger gain on Java programs that are 
compiled using VMKit.</span></font></li><li style="list-style-type: disc; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">To
 improve the implementation of JumpThreading, in such a way that more 
dead-branches will be eliminated. Again, we hope to achieve a small 
speed-up on the C benchmarks, and a larger speed-up on the Java 
benchmarks.</span></font></li></ul><br><font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Background</span></font><br>

<span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Range
 Analysis is a technique that maps integer variables to the possible 
ranges of values that they may assume throughout the execution of a 
program. Thus, for each integer variable, a range analysis determines 
its lower and upper limits. A very simple range analysis would, for 
instance, map each variable to the limits imposed by its type. That is, 
an 8-bit signed integer variable can be correctly mapped to the 
interval [-128, 127], and an 16-bit signed integer variable can be mapped to 
[-32768, 32767]. However, the precision of this analysis can greatly be 
improved from information inferred from the program text.</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Ideally
 this range should be as constrained as possible, so that an optimizing 
compiler could learn more information about each variable. However, the 
range analysis must be conservative, that is, it will only constrain the
 range of a variable if it can prove that it is safe to do so. As an 
example, consider the program:</span></font><br><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">i = read();</span><br>

<span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">if (i < 10) {</span><br>

<span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">  print (i + 1);</span><br>

<span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">else {</span><br><span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">  print(i - 1);</span><br>

<span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">}</span><br><span style="font-size: 11pt; font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">In
 this program we know, from the conditional test, that the value of<i> ‘i’</i> 
in the true side of the branch is in the range [-INF, 9], and in the 
false side is in the range [10, +INF].</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">During
 the Summer of Code 2010 I have designed and implemented, under the 
orientation of Duncan Sands, a non-iterative range analysis algorithm. 
Our implementation is currently fully functional, been able to analyze 
the whole LLVM test suite. For more details, see [4]. However, this 
implementation has never been integrated into the LLVM main trunc, for 
two reasons:</span></font><ol><li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">We
 use an intermediate representation called extended static assignment 
form [6], which the LLVM contributors were reluctant to use;</span></font></li><li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">During
 the SoC 2010 we did not have time to completely finish our 
implementation, and runtime numbers were available only by the end of 
2010.</span></font></li></ol><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">In
 order to address the first item, we propose to integrate the 
intermediate representation directly into our analysis, yet, as a module
 that can be used in separate by other clients, if necessary. We are 
using the e-SSA form to gain precision but it is not a requirement. The 
use of the e-SSA form increases a lot of the precision of the analysis, 
but we still can work without it. A previous Summer of Code, authored by
 Andre Tavares, has shown that the e-SSA form increases the number of 
phi-functions in the program code by less than 10%, and it is very fast 
to build [6].</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">The
 second item of our list of hindrances is no longer a problem. Our 
implementation is ready for use. We have been able to analyze the whole 
LLVM test suite, plus SPEC CPU 2006 - over 4 million LLVM bytecoes - in 
44 seconds on a 2.4GHz machine. We obtain non-trivial bit size 
reductions for the small benchmarks, having results that match those 
found by previous, non-conservative works, such as Stephenson’s et al’s 
[2]. Moreover, our implementation is based on a very modern algorithm, 
by Su and Wagner [1], augmented with Gawlitza’s technique to handle 
cycles [3]. We believe that this is the fastest implementation of such 
an analysis.</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">In small benchmarks (such as the </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">bitwise</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">
 benchmark used by Stephenson et al. [2]), we have been able to reduce 
the bitwidth of the variables by 35%, in average. In the other hand, in 
large benchmarks (such as SPEC CPU 2006), the bitwidth reduction is 8%, 
in average. This happens because the analysis is intra-procedural. I 
guess the other optimizations that LLVM uses suffer from this limitation
 too. This would happen with any type of range analysis algorithm. In 
order to solve this, one of my lab mates is working on an 
inter-procedural version of the analysis but his project is on a very 
initial stage though.</span></font><br><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Timeline and Testing Methodology</span></font><ol>

<li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Change
 the LVI interface, adding a new method to it: <span style="font-family: courier new,monospace;">getRange(Value *V)</span>, so 
that we can not only know if a variable is a constant, but also know its
 range of values whenever it is not a constant.</span></font></li><li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Change the implementation of the prototype range analysis that LVI already uses, so that it will use our implementation.</span></font></li>

<li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Implement
 the sparse conditional constant propagation to use LVI. I plan to 
implement Zadeck’s optimization to deal with ranges instead of simple 
constants. So, instead of being able to eliminate:  </span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">if (x != 10) {}</span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">when we know that x is, say, 11, we could eliminate also branches that uses other relational operators, eg, </span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"><</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">, </span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"><=</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">, </span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">></span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">, </span><span style="font-family: Courier New; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">>=</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">.
 I believe that it would be good for array bounds check elimination in 
memory safe languages such as Java. This, in addition to JumpThreading 
will be another client that will use LVI.</span></font></li><li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Run
 experiments on the LLVM test suite to verify that our new optimization 
improves on the current dead branch elimination pass that LLVM already 
uses.</span></font></li><li style="list-style-type: decimal; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Run
 experiments using VMKit, to check the impact of dead branch elimination
 on Java programs. We hope to deliver better performance numbers in this
 case because Java, as a memory safe language, is notorious for using 
many checks to ensure that memory is used only in ways that obey the 
contract of the variable types.</span></font><br></li></ol><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Biograph</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">y</span></font><br>

<span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">I am currently a third year Computer Science undergraduate student at the</span><a href="http://www.dcc.ufmg.br/dcc/"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> </span><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">Federal University of Minas Gerais</span></a><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">, Brazil, and I work as a research assistant at the</span><a href="http://www2.dcc.ufmg.br/laboratorios/llp/"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> </span><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">Programming Languages Lab</span></a><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> (LLP), in that university.</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">I
 believe I am a good candidate to work in the proposed project because I
 have already a good knowledge of LLVM. I have implemented range 
analysis, and currently it can find the ranges of integer variables used
 in the programs. In addition to this, I have been working as a 
programmer for three years before joining the LLP as a research 
assistant and I am experienced with C++, the language in which LLVM is 
implemented. </span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">Furthermore,
 I am a student at a very good university (UFMG). To justify this 
statement I would like to point out that the Department of Computer 
Science of UFMG got the</span><a href="http://www.ufmg.br/online/arquivos/012977.shtml"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> </span><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">best mark</span></a><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> in the Brazilian National Undergrad Exam (ENADE). </span></font><br>

<span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">References</span></font><br><span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">1. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">A Class of Polynomially Solvable Range Constraints for Interval Analysis without Widenings and Narrowings</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">, Zhendong Su and David Wagner, In Theoretical Computer Science, Volume 345 , Issue 1, 2005.</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">2. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">Bitwidth Analysis with Application to Silicon Compilation</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">,
 Mark Stephenson, Jonathan Babb, and Saman Amarasinghe, In Proceedings 
of the SIGPLAN conference on Programming Language Design and 
Implementation, 2000.</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">3. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">Polynomial Precise Interval Analysis Revisited.</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> Thomas Gawlitza, Jérôme Leroux, Jan Reineke, Helmut Seidl, Grégoire Sutre, Reinhard Wilhelm: Efficient Algorithms 2009: 422-437</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">4. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">Linear Time Range Analysis with Affine Constraints.</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> Douglas do Couto Teixeira and Fernando Magno Quintao Pereira </span><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">(</span><a href="http://homepages.dcc.ufmg.br/%7Edouglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf"><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf</span></a><span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;">)</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 153); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: underline; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">5. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">Constant propagation with conditional branches</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">. Mark N. Wegman and F. Kenneth Zadeck, In ACM Transactions on Programming Languages and Systems (TOPLAS), 181-210, 1991.</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">6. </span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: italic; text-decoration: none; vertical-align: baseline;">Efficient SSI Conversion.</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">
 André Luiz C. Tavares, Fernando Magno Quintão Pereira, Mariza A. S. 
Bigonha and Roberto S. Bigonha. Simpósio Brasileiro de Linguagens de 
Programação. 2010.</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">7.
 ABCD: eliminating array bounds checks on demand, Rajkslav Bodik, Rajiv 
Gupta and Vivek Sarkar, In Proceedings of the SIGPLAN conference on 
Programming Language Design and Implementation, 2000.</span><br><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span></font><br>

<font size="4"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Contact Info</span></font><br><span style="font-size: 14pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;"></span><br>

<font size="2"><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">Name:</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> Douglas do Couto Teixeira</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">e-mail 1:</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"> douglas at dcc dot ufmg dot br</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: bold; font-style: normal; text-decoration: none; vertical-align: baseline;">e-mail 2</span><span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;">: douglasdocouto at gmail dot com</span><br>

<span style="font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline;"></span></font><br><br><br>--<br>Douglas do Couto Teixeira<br>

<br><div class="gmail_quote">On Thu, Mar 24, 2011 at 11:05 AM, Allan Tong <span dir="ltr"><<a href="mailto:actong88@gmail.com">actong88@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<div class="im">On Wed, Mar 23, 2011 at 6:24 PM, John Criswell <<a href="mailto:criswell@illinois.edu">criswell@illinois.edu</a>> wrote:<br>
><br>
</div><div class="im">> > On 3/23/11 8:06 AM, Douglas do Couto Teixeira wrote:<br>
> ><br>
</div><div class="im">> > the execution of a program. Thus, for each integer variable, a range<br>
> > analysis determines its lower and upper limits. A very simple range analysis<br>
> > > would, for instance, map each variable to the limits imposed by its type.<br>
> > That is, an 8-bit unsigned integer variable can be correctly mapped to the<br>
> > interval [0, 255], and an 16-bit signed integer can be mapped to [-32767,<br>
> > 32766].<br>
><br>
> You probably want to be consistent in how numbers are interpreted.  Use the<br>
> unsigned or signed interpretations in both examples above.<br>
<br>
</div>Also, if you keep the 16-bit signed example, it should be [-32768, 32767].<br>
<br>
 - Allan<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br>