<br><br><div class="gmail_quote">On Sat, Apr 17, 2010 at 10:17 PM, ether zhhb <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com">etherzhhb@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;">
Hi,<br><br>i am playing the ScalarEvolution these days. i found the the ScalarEvolution will simply return a SCEVUnknow for a ICmpInst, so i think maybe great to add a new kind of SCEV to the ScalarEvolution framework.<br>
<br><br>
for example, if i run ScalarEvolution on the bc file generate from the
following C source file:<br>
<br>
int f(int a, int b, int c, int d) {<br>
return (2 * a + 5 * c + 2) > (4 * d - 3*b +3);<br>
}<br>
<br>
i will get a SCEVUnknow for the compare instruction, but it's great if i could get something like 2 * a + 5 * c - 4 * d - 3*b - 1 > 0 for the compare instruction :)<br></blockquote><div>oh, by the way, it seems that llvm neither optimize<br>
<br>(2 * a + 5 * c + 2) > (4 * d - 3*b +3 + 2 * a) <br><br>to <br><br>(5 * c + 2) > (4 * d - 3*b + 3) <br><br>nor<br><br>(5 * c) > (4 * d - 3*b + 1) <br><br>This kind of optimization maybe preform by SCEV for integer conditions ;)<br>
<br>here is the original c source code:<br><br>int f(int a, int b, int c, int d) {<br> return (2 * a + 5 * c + 2) > (4 * d - 3*b +3 + 2 * a);<br>}<br> <br>and here is the .ll file generate from the online demo (<a href="http://llvm.org/demo/index.cgi">http://llvm.org/demo/index.cgi</a>):<br>
<pre><span class="llvm_keyword">define</span> <span class="llvm_type">i32</span> @f(<span class="llvm_type">i32</span> %a, <span class="llvm_type">i32</span> %b, <span class="llvm_type">i32</span> %c, <span class="llvm_type">i32</span> %d) <span class="llvm_keyword">nounwind</span> <span class="llvm_keyword">readnone</span> {<br>
entry:<br> %0 = <span class="llvm_keyword">shl</span> <span class="llvm_type">i32</span> %a, 1 ; <<span class="llvm_type">i32</span>> [#uses=2] <- this is 2 * a, used twice<br> %1 = <span class="llvm_keyword">mul</span> <span class="llvm_type">i32</span> %c, 5 ; <<span class="llvm_type">i32</span>> [#uses=1]<br>
%2 = <span class="llvm_keyword">add</span> nsw <span class="llvm_type">i32</span> %0, 2 ; <<span class="llvm_type">i32</span>> [#uses=1] <br> %3 = <span class="llvm_keyword">add</span> nsw <span class="llvm_type">i32</span> %2, %1 ; <<span class="llvm_type">i32</span>> [#uses=1] <- 2 * a used here for the left hand side expression<br>
%4 = <span class="llvm_keyword">shl</span> <span class="llvm_type">i32</span> %d, 2 ; <<span class="llvm_type">i32</span>> [#uses=1]<br> %5 = <span class="llvm_keyword">mul</span> <span class="llvm_type">i32</span> %b, 3 ; <<span class="llvm_type">i32</span>> [#uses=1]<br>
%6 = <span class="llvm_keyword">add</span> <span class="llvm_type">i32</span> %0, 3 ; <<span class="llvm_type">i32</span>> [#uses=1] <- 2 * a used here for the right hand side expression<br>
%7 = <span class="llvm_keyword">sub</span> <span class="llvm_type">i32</span> %6, %5 ; <<span class="llvm_type">i32</span>> [#uses=1]<br> %8 = <span class="llvm_keyword">add</span> nsw <span class="llvm_type">i32</span> %7, %4 ; <<span class="llvm_type">i32</span>> [#uses=1]<br>
%9 = <span class="llvm_keyword">icmp</span> <span class="llvm_keyword">sgt</span> <span class="llvm_type">i32</span> %3, %8 ; <<span class="llvm_type">i1</span>> [#uses=1]<br> %10 = <span class="llvm_keyword">zext</span> <span class="llvm_type">i1</span> %9 <span class="llvm_keyword">to</span> <span class="llvm_type">i32</span> ; <<span class="llvm_type">i32</span>> [#uses=1]<br>
<span class="llvm_keyword">ret</span> <span class="llvm_type">i32</span> %10<br>}<br></pre><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br><br>In my opinion, we need only 3 kind of SCEV expression to express the ICmpInst: SCEVEqCond for equal condition, SCEVNeCond for not equal condition and SCEVGtCond for others. Because we can always transform A < B to B > A, and transform A >= B to A > B - 1 (or A + 1> B), and A <= B to A < B + 1 (or A - 1 < B). Furthermore, we can transform A > B to A - B > 0 and A != B to A - B != 0, so the SCEV for conditions will be very simple.<br>
<br>As there are already some functions such as "isKnownNonZero" in ScalarEvolution, so we can compute these condition easily. <br><br>With the SCEV for conditions, we may write more meaningful code:<br><br>SCEVEQCond *S = SE.getCondition(some_icmp_instruction);<br>
<br>if (some_cond.isAlwaysTrue(SE))<br> ... do some thing ...<br>else<br> ... do some others thing ...<br><br>Dose this make sense? or i just make things unnecessarily complex?<br><br>any comment is appreciated.<br><br>
--best regards<br><font color="#888888">ether<br>
</font></blockquote></div><br>