<div dir="ltr"><div><div><div><div>Hi Duncan, David, Sean.<br><br></div>Thanks for your reply.<br><br>> It'd be interesting if you could find a design that also treated these<br>> the same:<br>
><br>> (B ^ A) | ((A ^ B) ^ C) -> (A ^ B) | C<br>
<div class="im">> (B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C<br>
</div>> (B ^ A) | ((C ^ A) ^ B) -> (A ^ B) | C<br>
><br>
> I.e., `^` is also associative.<br><br></div>Agree with Duncan on including associative operation too. <br><br>> Can we handle this by just having a canonical ordering? Or is that too difficult to maintain through various instcombines?<br>
<br></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><br>(B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C<div><div><br></div><div>and we have written pass for pattern <br>
<br>(A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C<br><br></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>
<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).<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:1px solid rgb(204,204,204);padding-left:1ex">
</blockquote></div><br></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 class="gmail_extra"><u></u></div><div class="gmail_extra"><br>-- <br>With regards,<br>Suyog Sarda<br>
</div></div></div>