<div dir="ltr"><div>Would it be wrong to generate the llvm.assume IR suggested below? in GVN? <br><br>Given more info via the AssumptionCache, InstCombine can then do more optimizing.<br></div><div><br><div><div class="gmail_extra"><div class="gmail_quote">On Thu, Dec 4, 2014 at 12:10 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><span>
<br>
<div>On 12/04/2014 02:19 AM, Lars Rasmusson
SICS wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi,
<div><br>
</div>
<div>I'm compiling a large code base that uses tagged data, with
the tag in the two lowest bits.</div>
<div><br>
</div>
<div>I.e. ints are shifted two steps to the left and have 2 in
the tag bits, pointers have 0 in the tag bits, etc.</div>
<div><br>
</div>
<div>When I compile the code, I notice that there are places
where -O3 doesn't remove</div>
<div>unnecessary tag bit tests and manipulations, when they are
performed with bitwise</div>
<div>manipulation (which is how it is implemented in the large
code base I'm working with).</div>
<div><br>
</div>
<div>I've provided a small example below.</div>
<div><br>
</div>
<div>However, when I change from using 'and' and 'or' to using
subtraction and addition, llvm</div>
<div>is able to detect and optimise the code correctly.</div>
<div><br>
</div>
<div>Is there perhaps an optional optimisation pass that I could
run that could detect this optimisation opportunity?</div>
</div>
</blockquote></span>
This looks like it's simply a missed optimization. Could you file a
bug with both the working and non-working IR fragements? The
add/sub case is probably being caught by GVN and constant prop. <br>
<br>
One useful trick to determine if something is a missing optimization
or a pass ordering problem is to run the IR through opt -O3 twice.
If the second run improves the IR, there's likely a pass ordering
issue. In this case, it doesn't appear to be a pass ordering issue.<br>
<br>
There's one missing inst combine:<br>
<div> %5 = and i64 %1, -4 < --compute known bits should give low
zeros<br>
</div>
<div> %6 = or i64 %5, 2 <-- equivalent to + 2 given known bits<br>
</div>
<div> %7 = add nsw i64 %6, 12 <-- equivalent to add nsw %5, 14<br>
<br>
Getting rid of the 'and' itself is harder. I'm thinking we'd need
to add known bits to the lattice in LazyValueInfo, but I'm open to
alternate approaches. I'll note that I've been thinking about
that for other reasons as well. <br>
<br>
One very small tweak you could make would be to add an llvm.assume
inside the if case of the if condition. (Yes, that is as silly as
it sounds.) I tested that, and it did optimize as expected. It's
essentially working around a deficiency in the optimizer around
path constraints.<br>
<br>
define void @example_tweaked(i64* %x0) #0 {<br>
%1 = load i64* %x0, align 8<span><br>
%2 = and i64 %1, 3<br>
%3 = icmp eq i64 %2, 2<br>
br i1 %3, label %4, label %8<br>
; <label>:4 ; preds =
%0<br></span>
call void @llvm.assume(i1 %3)<span><br>
%5 = and i64 %1, -4 ; this should be optimized
away<br>
%6 = or i64 %5, 2 ; this should be optimized
away<br>
%7 = add nsw i64 %6, 12<br></span>
store i64 %7, i64* %x0, align 8<span><br>
ret void<br>
; <label>:8 ; preds =
%0<br>
tail call void @go_error() #2<br>
unreachable<br>
}<br>
<br></span>
declare void @llvm.assume(i1)<br>
</div>
<br>
<br>
<blockquote type="cite"><div><div>
<div dir="ltr">
<div><br>
</div>
<div>Thanks for any ideas,</div>
<div>/Lars</div>
<br>
/***************************************************/<br>
<div><br>
</div>
<div>/* The two LSB of x0 are 'tag bits' */</div>
<div>/* that we want to manipulate. */</div>
<div>extern long x0;</div>
<div><br>
</div>
<div>void go_error(void) __attribute__ ((noreturn));</div>
<div><br>
</div>
<div>void example_not_optimized(void)</div>
<div>{</div>
<div> if((x0 & 3) == 2) {</div>
<div> // Here the tag bits are removed and added</div>
<div> // with bitwise 'and' and 'or'.</div>
<div> x0 = ((x0 & ~3) | 2) + 12;</div>
<div> } else {</div>
<div> go_error();</div>
<div> }</div>
<div>}</div>
<div><br>
</div>
<div>/*</div>
<div>define void @example_not_optimized() #0 {</div>
<div> %1 = load i64* @x0, align 8, !tbaa !1</div>
<div> %2 = and i64 %1, 3</div>
<div> %3 = icmp eq i64 %2, 2</div>
<div> br i1 %3, label %4, label %8</div>
<div><br>
</div>
<div>; <label>:4 ;
preds = %0</div>
<div> %5 = and i64 %1, -4 ; this should be
optimized away</div>
<div> %6 = or i64 %5, 2 ; this should be
optimized away</div>
<div> %7 = add nsw i64 %6, 12</div>
<div> store i64 %7, i64* @x0, align 8, !tbaa !1</div>
<div> ret void</div>
<div><br>
</div>
<div>; <label>:8 ;
preds = %0</div>
<div> tail call void @go_error() #2</div>
<div> unreachable</div>
<div>}</div>
<div>*/</div>
<div><br>
</div>
<div><br>
</div>
<div>void example_optimized(void)</div>
<div>{</div>
<div> if((x0 & 3) == 2) {</div>
<div> // Here the tag bits are removed and added</div>
<div> // with subtraction and addition.</div>
<div> x0 = (x0 - (x0 & 3) + 2) + 12;</div>
<div> } else {</div>
<div> go_error();</div>
<div> }</div>
<div>}</div>
<div><br>
</div>
<div>/*</div>
<div>define void @example_optimized() #0 {</div>
<div> %1 = load i64* @x0, align 8, !tbaa !1</div>
<div> %2 = and i64 %1, 3</div>
<div> %3 = icmp eq i64 %2, 2</div>
<div> br i1 %3, label %4, label %6</div>
<div><br>
</div>
<div>; <label>:4 ;
preds = %0</div>
<div> %5 = add i64 %1, 12</div>
<div> store i64 %5, i64* @x0, align 8, !tbaa !1</div>
<div> ret void</div>
<div><br>
</div>
<div>; <label>:6 ;
preds = %0</div>
<div> tail call void @go_error() #2</div>
<div> unreachable</div>
<div>}</div>
<div><br>
</div>
<div> */</div>
<div><br>
</div>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><pre>_______________________________________________
LLVM Developers mailing list
<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>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</div>
<br>_______________________________________________<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>
<br></blockquote></div><br></div></div></div></div>