<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
The general problem of exploiting path sensitive facts for
optimization is a very open one. I've been thinking about this
myself a bit recently, but haven't come up with a particularly
workable approach yet. The major problem is finding the right trade
off between compile time and optimization quality. <br>
<br>
One simplification I think I've talked myself into is completely
ignoring merging of conditions (i.e. dataflow) and simply rely on
dominating conditions. At least so far, this seems to handle most
of the cases I care about. (I'm mostly looking at cases involving
either null checks or range checks.)<br>
<br>
I've more or less convinced myself that any approach taken would
have to be lazy, and make aggressive use of analysis caching. The
only exception to this might be a early dominance based early
propagation restricted to specific narrow cases. (Either an
extension to EarlyCSE, or something similar.)<br>
<br>
In an ideal world, the analysis results would feed all other
optimization passes (in particular, InstSimplify and InstCombine).
Not sure if this is doable for version one though. <br>
<br>
It's also worth mentioning that a between LVI, GVN, &
LoopUnswitch, we actually do get a lot of conditions inside loops.
In particular, any check inside a loop *header* block with an
immediately dominating check outside the loop is generally taken
care of. <br>
<br>
Philip<br>
<br>
<div class="moz-cite-prefix">On 01/16/2015 08:46 AM, Sanjay Patel
wrote:<br>
</div>
<blockquote
cite="mid:CA+wODitTk2YUg8FFGq1sx3jtGoaV7wQtXmLmg0ESTMOsYA2Jng@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>Thanks, LLVM Ol' Timers! Your ghost stories are scary
enough that I'll tread quietly past predsimplify's grave.<br>
<br>
</div>
I was peeking into this because - and I'm happy to be corrected
if I've misdiagnosed these - we've seen a few VRP-related bugs
cropping up lately:<br>
1. <a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-November/079038.html"
target="_blank">http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-November/079038.html</a>
(remove alignment checks)<br>
2. <a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-December/079345.html"
target="_blank">http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-December/079345.html</a>
(remove tag bit tests)<br>
3. <a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-January/080314.html"
target="_blank">http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-January/080314.html</a>
(remove FP range checks, patch submitted)<br>
4. <a moz-do-not-send="true"
href="http://llvm.org/bugs/show_bug.cgi?id=17683">http://llvm.org/bugs/show_bug.cgi?id=17683</a>
(range check to improve division)<br>
5. <a moz-do-not-send="true"
href="http://llvm.org/bugs/show_bug.cgi?id=17713">http://llvm.org/bugs/show_bug.cgi?id=17713</a>
(propagate FP equalities, patch committed)<br>
<br>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Jan 15, 2015 at 3:42 PM, Nick
Lewycky <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote"><span class="">On 15 January
2015 at 10:49, Chandler Carruth <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:chandlerc@google.com"
target="_blank">chandlerc@google.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 class="gmail_extra">
<div class="gmail_quote"><span>On Thu, Jan 15,
2015 at 10:30 AM, Sanjay Patel <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:spatel@rotateright.com"
target="_blank">spatel@rotateright.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>Would it be wrong to generate the
llvm.assume IR suggested below? in
GVN?</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>I think so... Because:</div>
<span>
<div><br>
</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>
<div class="gmail_extra">
<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">
<div bgcolor="#FFFFFF"
text="#000000">
<div>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>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>Once upon a time, there was an
optimization for this called predsimplify.
I believe Nick can tell you a long,
glorious, tragic tale about its life and
ultimate death.</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>Okay, gather 'round the fire. ;-)</div>
<div><br>
</div>
<div>Predsimplify was the first optimization pass I
tried to write, to fix PR807. The basis was that it
would propagate properties (icmp's between two SSA
values) down paths in the domtree. In its various
rewrites it knew all sorts of tricks. For instance
it could do:</div>
<div><br>
</div>
<div> a = b + c</div>
<div> if b == 5:</div>
<div> if c == 3:</div>
<div> print a # replace 'a' with 8</div>
<div><br>
</div>
<div>which requires that it solve a bidirectional
dataflow problem. It also knew that a < b implied
b > 0, and a < b < c implies that c > 1.
Some of the things predsimplify used to do are now
implemented inside gvn's processEquality.
Predsimplify also had an odd trick:</div>
<div><br>
</div>
<div> a = phi [0, a.i]</div>
<div> b = phi [10, x]</div>
<div> if a == 1:</div>
<div> # here we know that b == x. (x could still
equal 10 though.)</div>
<div><br>
</div>
<div>which I haven't seen replicated elsewhere in
llvm.</div>
<div><br>
</div>
<div>I went through many iterations of the
implementation trying to minimize the compile time
impact. So why predsimplify die?</div>
<div><br>
</div>
<div>The first largest problem is that it rarely
fired. It turns out that people don't write code
which needs this sort of optimization in C very
often, or at least in the llvm test suite.
Instcombine already does a ton of optimization that
overlapped with predsimplify in its demanded bits
analysis, and that does a much better job of getting
the cases that show up in real-world code. The cost
of the analysis that predsimplify was doing, eagerly
building up its value graph was too expensive to fit
in llvm, especially when instcombine's demanded bits
analysis tended to get the cases already. If your IR
looks different, it might be worth adding to the
pass pipeline for you.</div>
<div><br>
</div>
<div>I think a future VRP (value range propagation)
pass would need to be a superset of
simplify-demanded-bits, so that we could remove the
cost of running simplify-demanded-bits to help pay
for the VRP. I've been thinking about the data
structure we could use for that, but haven't worked
out all the operations yet.</div>
<span class="HOEnZb"><font color="#888888">
<div><br>
</div>
<div>Nick</div>
</font></span>
<div>
<div class="h5">
<div><br>
</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 class="gmail_extra">
<div class="gmail_quote">
<div>In particular:<br>
</div>
<span>
<div><br>
</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>
<div class="gmail_extra">
<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">
<div bgcolor="#FFFFFF"
text="#000000">
<div> <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)</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>We don't need the assume here. If we
want to do predicate-based
simplification, we can just have
<whatever> look at dominating
branch conditions, much like it looks at
dominating assume calls. Worst case is
that it requires more fancy-ness in the
assumption tracking infrastructure to
actually funnel queries through to
different ways of saying "this value is
true at this point".</div>
<div><br>
</div>
<div>However, that is the core essence of
predsimplify. Historically, we have
found a really terrifying amount of
complexity and compile time hit for
relatively small gains in terms of
generated code quality. =/ Maybe we just
need to handle the "obvious" cases much
like the very limited calls to
assumption tracker do, but I think this
path needs to be trod with great care.</div>
<div>
<div>
<div><br>
</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>
<div class="gmail_extra">
<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">
<div bgcolor="#FFFFFF"
text="#000000">
<div><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 moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a>
<a moz-do-not-send="true" 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
moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>
<a
moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a
moz-do-not-send="true"
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>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu"
target="_blank">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu"
target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
</blockquote>
</div>
</div>
</div>
<br>
</div>
</div>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu"
target="_blank">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
</blockquote>
</div>
</div>
</div>
<br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>