<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Aug 8, 2014 at 1:34 PM, suyog sarda <span dir="ltr"><<a href="mailto:sardask01@gmail.com" target="_blank">sardask01@gmail.com</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 dir="ltr"><div><div><div><div>Hi Duncan, David, Sean.<br>
<br></div>Thanks for your reply.<div class=""><br><br>> It'd be interesting if you could find a design that also treated these<br>> the same:<br>
><br></div>> (B ^ A) | ((A ^ B) ^ C) -> (A ^ B) | C<div class=""><br>
<div>> (B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C<br>
</div></div><div class="">> (B ^ A) | ((C ^ A) ^ B) -> (A ^ B) | C<br>
><br>
> I.e., `^` is also associative.<br><br></div></div>Agree with Duncan on including associative operation too. <br><div class=""><br>> Can we handle this by just having a canonical ordering? Or is that too difficult to maintain through various instcombines?<br>
<br></div></div>Yes, its the easiest way to do that. If i am not wrong, what Sean is suggesting is that if we get <br><br></div>something like <br><div class=""><br>(B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C</div><div><div>
<br></div><div>and we have written pass for pattern <br><div class="">
<br>(A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C<br><br></div></div><div>we could just swap 'B' and 'A' before matching the pattern i.e. we do canonical re-ordering <br>(Sean, Correct me if i am wrong on my understanding of what you meant by canonical ordering).<br>
</div></div></div></blockquote><div><br></div><div>You understood correctly.</div><div> </div><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 dir="ltr"><div><div>
<br></div><div>I have seen in the "instcombine" module that many times std::swap was used for the same.<br><br></div><div>But it becomes too much repetitive and somewhat irritating to keep doing this for every pattern.<br>
</div><div class="gmail_extra">Shouldn't we do this in more generic way where we do not have to worry about swapping operands? <br>(How to do it - i don't know for now. I looked at the matchers implementation for modification/improvement, <br>
but didn't find any clue on it).<div class=""><br><br>> It seems to me that we could rejigger Reassociate to reduce the number of possibilities that InstCombine could expect.<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
</blockquote></div><br></div></div><div class="gmail_extra">Agree with David that infact it should be reassociate pass which should handle this.<br></div><div class="gmail_extra"><br>But following is something interesting and rather worrying things i have found :<br>
</div><div class="gmail_extra">(I have omitted unimportant code and highlighted important one in following example)<br></div><div class="gmail_extra"><u>e.x. </u><br><br>((~A & B) | A) --> (A | B) ; Code is implemented for this already<br>
<br></div><div class="gmail_extra"><u>C code :</u><br><br>suyog@suyog-Inspiron-N5010:~$ cat 1.c<br>#include<stdio.h><br>int cal(int a, int b) {<br><b>return ((~a & b) | a);</b><br>}<br><br>int main(){<br>int a, b;<br>
scanf("%d %d", &a, &b);<br>return cal(a,b);<br>}<br><br></div><div class="gmail_extra">LLVM IR at O0 :<br><br>suyog@suyog-Inspiron-N5010:~$ Open/rbuild/bin/clang -S -O0 -emit-llvm 1.c <br><br>; Function Attrs: nounwind<br>
<b>define i32 @cal(i32 %a, i32 %b) #0 {<br> %1 = xor i32 %a, -1<br> %2 = and i32 %1, %b<br> %3 = or i32 %2, %a<br> ret i32 %3</b><br>}<br><br>; Function Attrs: nounwind<br>define i32 @main() #0 {<br> ..<br> ..<br> %4 = call i32 @cal(i32 %2, i32 %3)<br>
ret i32 %4<br>}<br><br></div><div class="gmail_extra"><u>LLVM IR at instcombine :</u><br><br>suyog@suyog-Inspiron-N5010:~$ Open/rbuild/bin/opt -S -instcombine 1.ll<br><br><b>; Function Attrs: nounwind<br>define i32 @cal(i32 %a, i32 %b) #0 {<br>
%1 = or i32 %a, %b<br> ret i32 %1<br>}</b><br>..<br>..<br>..<br><br></div><div class="gmail_extra">which is OK as per expected transform.<br></div><div class="gmail_extra"><u><br></u></div><div class="gmail_extra"><u>LLVM IR at reassociate and instcombine :<br>
<br></u>suyog@suyog-Inspiron-N5010:~$ Open/rbuild/bin/opt -S -reassociate -instcombine 2.ll<u><br><br></u><b>; Function Attrs: nounwind<br>define i32 @cal(i32 %a, i32 %b) #0 {<br> %1 = xor i32 %a, -1<br> %2 = and i32 %b, %1<br>
%3 = or i32 %2, %a<br> ret i32 %3<br>}</b><br><br>..<br>..<br><br></div><div class="gmail_extra">Reassociate converted (~a&b) to (b&~a) and instruction combine failed to optimize.<br><br></div><div class="gmail_extra">
As evident, sometimes, reassociate pass actually harms the optimization opportunity !!<br><br></div><div class="gmail_extra">Some more interesting findings on how can this affect the final machine code:<br><br></div><div class="gmail_extra">
<u>Test case :</u><br></div><div class="gmail_extra">1.c :<br></div><div class="gmail_extra"><br>#include<stdio.h><br>int cal(int a, int b) {<br><b>return ((~a & b) | a);</b><br>}<br><br>int main(){<br>int a, b;<br>
scanf("%d %d", &a, &b);<br>return cal(a,b);<br>}<br><br></div><div class="gmail_extra"><u>X86 .s file with clang at O2 for above program :</u><br><br>suyog@suyog-Inspiron-N5010:~$ Open/rbuild/bin/clang -S -O2 1.c<br>
<br>main: # @main<br># BB#0:<br> subl $28, %esp<br> leal 20(%esp), %eax<br> movl %eax, 8(%esp)<br> leal 24(%esp), %eax<br> movl %eax, 4(%esp)<br> movl $.L.str, (%esp)<br>
calll __isoc99_scanf<br> movl 20(%esp), %eax<br><b> orl 24(%esp), %eax</b><br> addl $28, %esp<br> retl<br><br></div><div class="gmail_extra">As seen, optimization happened at IR level itself reflected in .s file.<br>
<br></div><div class="gmail_extra"><u>GCC output for the same:</u><br><br></div><div class="gmail_extra">suyog@suyog-Inspiron-N5010:~$ gcc -S -O2 1.c<br><br>main:<br>.LFB23:<br> .cfi_startproc<br> pushl %ebp<br>
.cfi_def_cfa_offset 8<br>
.cfi_offset 5, -8<br> movl %esp, %ebp<br> .cfi_def_cfa_register 5<br> andl $-16, %esp<br> subl $32, %esp<br> leal 28(%esp), %eax<br> movl %eax, 8(%esp)<br> leal 24(%esp), %eax<br>
movl %eax, 4(%esp)<br> movl $.LC0, (%esp)<br> call __isoc99_scanf<br> movl 24(%esp), %eax<br><b> orl 28(%esp), %eax</b><br> leave<br> .cfi_restore 5<br> .cfi_def_cfa 4, 4<br> ret<br>
.cfi_endproc<br></div><div class="gmail_extra"><br>GCC also did the optimization.<br><br></div><div class="gmail_extra">Now we just <b>slightly flip</b> the test case :<br></div><div class="gmail_extra"><u><br></u></div>
<div class="gmail_extra"><u>1.c Test case:<br><br></u>#include<stdio.h><br>int cal(int a, int b) {<br><b>return ((b & ~a) | a);</b><br>}<br><br>int main(){<br>int a, b;<br>scanf("%d %d", &a, &b);<br>
return cal(a,b);<br>}<u><br></u><br><u>X86 .s file with clang at O2 for above program :<br><br></u>suyog@suyog-Inspiron-N5010:~$ Open/rbuild/bin/clang -S -O2 1.c<br><br>main: # @main<br>
# BB#0:<br>
subl $28, %esp<br> leal 20(%esp), %eax<br> movl %eax, 8(%esp)<br> leal 24(%esp), %eax<br> movl %eax, 4(%esp)<br> movl $.L.str, (%esp)<br> calll __isoc99_scanf<br> movl 24(%esp), %ecx<br>
movl %ecx, %eax<br> <b>notl %eax<br> andl 20(%esp), %eax<br> orl %ecx, %eax</b><br> addl $28, %esp<br> retl<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">We lost the Optimization opportunity here !!<br>
<br></div><div class="gmail_extra"><u>GCC output for the same:</u><br><br>suyog@suyog-Inspiron-N5010:~$ gcc -S -O2 1.c<br><br>main:<br>.LFB23:<br> .cfi_startproc<br> pushl %ebp<br> .cfi_def_cfa_offset 8<br> .cfi_offset 5, -8<br>
movl %esp, %ebp<br> .cfi_def_cfa_register 5<br> andl $-16, %esp<br> subl $32, %esp<br> leal 28(%esp), %eax<br> movl %eax, 8(%esp)<br> leal 24(%esp), %eax<br> movl %eax, 4(%esp)<br>
movl $.LC0, (%esp)<br> call __isoc99_scanf<br> movl 24(%esp), %eax<br><b> orl 28(%esp), %eax</b><br> leave<br> .cfi_restore 5<br> .cfi_def_cfa 4, 4<br> ret<br> .cfi_endproc<br><br>
</div>
<div class="gmail_extra">GCC still optimized it !!<br><br></div><div class="gmail_extra">Clearly evident that llvm is losing because of naive approach of pattern matching.<br><br></div><div class="gmail_extra">How can we improve this so that LLVM also recognizes commutative/associative <br>
pattern efficiently with single 'matchers' call? I am not having any idea so far.<br></div><div class="gmail_extra">I will think more on it. Any help would be really helpful.<br></div><div class="gmail_extra"><br>
</div><div class="gmail_extra">Any suggestions/comments/rectification are most awaited :)<br></div></div></div></blockquote><div><br></div><div><br></div><div><div>I'm actually sort of wondering if instead of hardcoding all these bitwise simplifications, we can just use a general boolean minimization algorithm.</div>
<div><br></div><div>Is there a reason we don't? Maybe it's just compile time? But eventually (maybe already?) adding enough special case combines will be slower than using the general optimization.</div><div><br></div>
<div>-- Sean </div></div><div> </div><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 dir="ltr"><div><div class="gmail_extra">
</div><div class=""><div class="gmail_extra"><u></u></div><div class="gmail_extra"><br>-- <br>With regards,<br>Suyog Sarda<br>
</div></div></div></div>
</blockquote></div><br></div></div>