<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Arial","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:738409410;
mso-list-type:hybrid;
mso-list-template-ids:-1594301980 1794647856 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:\F0D8;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:12.0pt;
font-family:Wingdings;
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
color:black;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body bgcolor="white" lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoListParagraph" style="text-indent:-.25in;mso-list:l0 level1 lfo1"><![if !supportLists]><span style="font-family:Wingdings"><span style="mso-list:Ignore">Ø<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]>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
<span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-.25in;mso-list:l0 level1 lfo1"><![if !supportLists]><span style="font-family:Wingdings"><span style="mso-list:Ignore">Ø<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]>that I've been thinking about that for other reasons as well.
<br>
<br>
<span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">FWIW, I think adding known bits, and known values (of known bits) is an excellent way to go. The Intel compiler has done this as well
in its own framework, and the compiler source base from the old Digital/Compaq C/C++ and Fortran compilers had this also. Sounded (from another post here) like the Apollo compiler did as well. This turns out to be highly valuable in a surprisingly large amount
of code, especially where macros/class members hide a lot of bit-masking kind of operation, thus leading to many redundant checks. This also turns out to give alignment proving using the same framework, and even represents known modulo information.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">I also like the idea (that Apollo post had) to add into the SSA graph where specific paths caused more knowledge of values.
<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Kevin Smith<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext"> llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]
<b>On Behalf Of </b>Philip Reames<br>
<b>Sent:</b> Thursday, December 04, 2014 11:11 AM<br>
<b>To:</b> Lars Rasmusson SICS; LLVMdev@cs.uiuc.edu<br>
<b>Subject:</b> Re: [LLVMdev] Optimising bit-flipping code<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On 12/04/2014 02:19 AM, Lars Rasmusson SICS wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">Hi, <o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I'm compiling a large code base that uses tagged data, with the tag in the two lowest bits.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">When I compile the code, I notice that there are places where -O3 doesn't remove<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">unnecessary tag bit tests and manipulations, when they are performed with bitwise<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">manipulation (which is how it is implemented in the large code base I'm working with).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I've provided a small example below.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">However, when I change from using 'and' and 'or' to using subtraction and addition, llvm<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">is able to detect and optimise the code correctly.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Is there perhaps an optional optimisation pass that I could run that could detect this optimisation opportunity?<o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal">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:<o:p></o:p></p>
<div>
<p class="MsoNormal"> %5 = and i64 %1, -4 < --compute known bits should give low zeros<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %6 = or i64 %5, 2 <-- equivalent to + 2 given known bits<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %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<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>
call void @llvm.assume(i1 %3)<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>
store i64 %7, i64* %x0, align 8<br>
ret void<br>
; <label>:8 ; preds = %0<br>
tail call void @go_error() #2<br>
unreachable<br>
}<br>
<br>
declare void @llvm.assume(i1)<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks for any ideas,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">/Lars<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
/***************************************************/<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">/* The two LSB of x0 are 'tag bits' */<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">/* that we want to manipulate. */<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">extern long x0;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">void go_error(void) __attribute__ ((noreturn));<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">void example_not_optimized(void)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> if((x0 & 3) == 2) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> // Here the tag bits are removed and added<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> // with bitwise 'and' and 'or'.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> x0 = ((x0 & ~3) | 2) + 12;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> } else {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> go_error();<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">/*<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">define void @example_not_optimized() #0 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %1 = load i64* @x0, align 8, !tbaa !1<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %2 = and i64 %1, 3<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %3 = icmp eq i64 %2, 2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> br i1 %3, label %4, label %8<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">; <label>:4 ; preds = %0<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %5 = and i64 %1, -4 ; this should be optimized away<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %6 = or i64 %5, 2 ; this should be optimized away<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %7 = add nsw i64 %6, 12<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> store i64 %7, i64* @x0, align 8, !tbaa !1<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> ret void<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">; <label>:8 ; preds = %0<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> tail call void @go_error() #2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">*/<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">void example_optimized(void)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> if((x0 & 3) == 2) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> // Here the tag bits are removed and added<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> // with subtraction and addition.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> x0 = (x0 - (x0 & 3) + 2) + 12;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> } else {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> go_error();<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">/*<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">define void @example_optimized() #0 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %1 = load i64* @x0, align 8, !tbaa !1<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %2 = and i64 %1, 3<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %3 = icmp eq i64 %2, 2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> br i1 %3, label %4, label %6<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">; <label>:4 ; preds = %0<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> %5 = add i64 %1, 12<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> store i64 %5, i64* @x0, align 8, !tbaa !1<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> ret void<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">; <label>:6 ; preds = %0<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> tail call void @go_error() #2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> unreachable<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> */<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><o:p></o:p></pre>
<pre><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><o:p></o:p></pre>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>