After a few more tests, I found out that if we set -unroll-threshold to a value large enough, and run "opt -std-compile-opts" or "opt -O3" 3 times, the unroll will be able to unroll the original loop 32 times, and when you have it unrolled for at least 32 times a optimization is triggered, folding it to a single "%xor.3.3.1 = xor i32 %tmp6, -1" (dont know why it does not transform it into a NOT though).<div>
<br></div><div>Therefore, the optimization that I want is already there somewhere, but is not triggered when llvm unrolls the loop less than 32 times.</div><div><br></div><div>My goal now is to make it work for smaller unrolled loops, like for 4, 8, and 16.</div>
<div><br></div><div>Does anyone knows which function gives the information that for 32 unrolled steps it is possible to optimize but not for smaller numbers?</div><div><br></div><div>I also would like to see why the "XOR A, -1" is not turned into a NOT, any hints on that are welcome.</div>
<div><br></div><div>Thanks,</div><div><br></div><div>Daniel Nicacio</div><div><br><br><div class="gmail_quote">2011/7/26 Daniel Nicácio <span dir="ltr"><<a href="mailto:dnicacios@gmail.com">dnicacios@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hi Duncan,<div><br></div><div>when I run "opt -std-compile-opts" on the original source code it has the same output of O3.</div>
<div>when I run "opt -std-compile-opts" on the -O3 optimized code, things get even more weird, it outputs the following code:</div>
<div><br></div><div><div class="im"><div>while.body: ; preds = %while.body, %entry</div></div><div> %indvar = phi i32 [ 0, %entry ], [ %indvar.next.3, %while.body ]</div><div> %tmp = shl i32 %indvar, 2</div>
<div> %0 = lshr i32 %indvar, 3</div><div> %shr = and i32 %0, 134217727</div><div> %rem = and i32 %tmp, 16</div><div class="im"><div> %shl = shl i32 1, %rem</div><div> %arrayidx = getelementptr inbounds i32* %bitmap, i32 %shr</div>
<div>
%tmp6 = load i32* %arrayidx, align 4</div></div><div class="im"><div> %rem.1 = or i32 %rem, 1</div><div> %shl.1 = shl i32 1, %rem.1</div></div><div class="im"><div> %rem.2 = or i32 %rem, 2</div><div> %shl.2 = shl i32 1, %rem.2</div>
</div><div class="im"><div> %rem.3 = or i32 %rem, 3</div>
<div> %shl.3 = shl i32 1, %rem.3</div></div><div> %xor = xor i32 %shl, %tmp6</div><div> %xor.1 = xor i32 %xor, %shl.3</div><div class="im"><div> %xor.2 = xor i32 %xor.1, %shl.2</div></div><div> %xor.3 = xor i32 %xor.2, %shl.1</div>
<div> %rem.11 = or i32 %rem, 4</div>
<div> %shl.12 = shl i32 1, %rem.11</div><div> %rem.1.1 = or i32 %rem, 5</div><div> %shl.1.1 = shl i32 1, %rem.1.1</div><div> %rem.2.1 = or i32 %rem, 6</div><div> %shl.2.1 = shl i32 1, %rem.2.1</div><div> %rem.3.1 = or i32 %rem, 7</div>
<div> %shl.3.1 = shl i32 1, %rem.3.1</div><div> %xor.13 = xor i32 %shl.12, %xor.3</div><div> %xor.1.1 = xor i32 %xor.13, %shl.3.1</div><div> %xor.2.1 = xor i32 %xor.1.1, %shl.2.1</div><div> %xor.3.1 = xor i32 %xor.2.1, %shl.1.1</div>
<div> %rem.24 = or i32 %rem, 8</div><div> %shl.25 = shl i32 1, %rem.24</div><div> %rem.1.2 = or i32 %rem, 9</div><div> %shl.1.2 = shl i32 1, %rem.1.2</div><div> %rem.2.2 = or i32 %rem, 10</div><div> %shl.2.2 = shl i32 1, %rem.2.2</div>
<div> %rem.3.2 = or i32 %rem, 11</div><div> %shl.3.2 = shl i32 1, %rem.3.2</div><div> %xor.26 = xor i32 %shl.25, %xor.3.1</div><div> %xor.1.2 = xor i32 %xor.26, %shl.3.2</div><div> %xor.2.2 = xor i32 %xor.1.2, %shl.2.2</div>
<div> %xor.3.2 = xor i32 %xor.2.2, %shl.1.2</div><div> %rem.37 = or i32 %rem, 12</div><div> %shl.38 = shl i32 1, %rem.37</div><div> %rem.1.3 = or i32 %rem, 13</div><div> %shl.1.3 = shl i32 1, %rem.1.3</div><div> %rem.2.3 = or i32 %rem, 14</div>
<div> %shl.2.3 = shl i32 1, %rem.2.3</div><div> %rem.3.3 = or i32 %rem, 15</div><div> %shl.3.3 = shl i32 1, %rem.3.3</div><div> %xor.39 = xor i32 %shl.38, %xor.3.2</div><div> %xor.1.3 = xor i32 %xor.39, %shl.3.3</div>
<div> %xor.2.3 = xor i32 %xor.1.3, %shl.2.3</div><div> %xor.3.3 = xor i32 %xor.2.3, %shl.1.3</div><div> store i32 %xor.3.3, i32* %arrayidx, align 4</div><div> %indvar.next.3 = add i32 %indvar, 4</div><div> %exitcond.3 = icmp eq i32 %indvar.next.3, 32</div>
<div class="im">
<div> br i1 %exitcond.3, label %while.end, label %while.body</div><div><br></div><div>while.end: ; preds = %while.body</div><div> ret void</div><div><br></div><div><br></div></div>
<div>Thanks for the reply,</div>
<div><br></div><div><font color="#888888">Daniel</font><div><div></div><div class="h5"><br><br><div class="gmail_quote">On Tue, Jul 26, 2011 at 12:50 PM, Duncan Sands <span dir="ltr"><<a href="mailto:baldrick@free.fr" target="_blank">baldrick@free.fr</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Daniel,<br>
<div><br>
> Precisely. The code generated by unrolling can be folded into a single XOR and<br>
> SHL. And even if it was not inside a loop, it can still be optimized. What I<br>
> want to know is: is there any optimization supposed to optimize this code, but<br>
> for some reason it thinks it is not possible, or there is no optimization for<br>
> that situation at all?<br>
<br>
</div>it could be a phase ordering problem. If you run "opt -std-compile-opts" on the<br>
unsatisfactory bitcode, does it clean up all the bit fiddling?<br>
<br>
Ciao, Duncan.<br>
<div><div></div><div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">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>
</div></div></blockquote></div><br></div></div></div></div>
</blockquote></div><br></div>