<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 08/31/2017 03:54 PM, Tony Jiang via
llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:OF0C4863BE.ABAD99EF-ON0025818D.0072AF44-8525818D.0072D93E@notes.na.collabserv.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<font size="2" face="Arial">Hi All,</font><br>
<br>
<font size="2" face="Arial">We have recently found some
optimization
opportunities created by replicating code into branches in order
to enable
optimization. In general, the optimization opportunity we are
pursuing
is like the following.</font><font size="2" face="Arial"><br>
</font><font size="2" face="Arial"><br>
Given pseudo-code:</font><font size="2" face="Arial"><br>
</font><font size="1" face="Courier New"><br>
// block A<br>
if (some condition)<br>
// block B<br>
// block C</font><font size="2" face="Arial"><br>
</font><font size="2" face="Arial"><br>
If it can be efficiently proven that some portion of block C can
be simplified
had control flow not gone through the if statement, it might be
useful
to convert this CFG into a diamond and hoist that portion of
block C into
both block B and the new block.<br>
</font><font size="2" face="Arial"><br>
</font><font size="2" face="Arial"><br>
Consider the following example:<br>
</font><font size="2" face="Arial"> </font><br>
<font size="2" face="Arial"><br>
</font><font size="1" face="Courier New"><br>
int test(int *Ptr, int a, int b, int c, int d) { </font><br>
<font size="1" face="Courier New"> int Ret = 0;<br>
if (__builtin_expect(!Ptr, 0)) {<br>
Ret = calli(a);<br>
// return Ret / (a|1) / (b|1) / (c|1) / (d|1); // Copy
return
to here<br>
}<br>
return Ret / (a|1) / (b|1) / (c|1) / (d|1); // This can be
simplified
to return 0<br>
}</font><font size="2" face="Arial"> </font><br>
<font size="2" face="Arial"><br>
In this case, replicating the return statement in the branch
allows the
optimizer to prove the value of Ret at the end of the function
is 0 and
eliminate the arithmetic calculations.<br>
<br>
A second example:</font><font size="2" face="Arial"> </font><br>
<br>
<font size="1" face="Courier New">unsigned long
funcReturningArbitraryi64(unsigned
char *p);</font><br>
<font size="1" face="Courier New">#define LENGTH(uv) ( (uv) <
0x80 ? 1 : \</font><br>
<font size="1" face="Courier New">
(uv) < 0x800
? 2 : \</font><br>
<font size="1" face="Courier New">
(uv) < 0x10000
? 3 : \</font><br>
<font size="1" face="Courier New">
(uv) < 0x200000
? 4 : \</font><br>
<font size="1" face="Courier New">
(uv) < 0x4000000
? 5 : \</font><br>
<font size="1" face="Courier New">
(uv) < 0x80000000
? 6 : 7 )</font><br>
<br>
<font size="1" face="Courier New">int func(unsigned char *p, bool
flag)</font><br>
<font size="1" face="Courier New">{</font><br>
<font size="1" face="Courier New"> unsigned long c = *p;</font><br>
<font size="1" face="Courier New"> int len;</font><br>
<font size="1" face="Courier New"> // ...</font><br>
<font size="1" face="Courier New">#ifdef _ORIG</font><br>
<font size="1" face="Courier New"> if(flag) {</font><br>
<font size="1" face="Courier New"> // ...</font><br>
<font size="1" face="Courier New"> c =
funcReturningArbitraryi64(p);</font><br>
<font size="1" face="Courier New"> }</font><br>
<font size="1" face="Courier New">len = LENGTH(c);</font><br>
<font size="1" face="Courier New">#else</font><br>
<font size="1" face="Courier New"> if(flag) {</font><br>
<font size="1" face="Courier New"> // ...</font><br>
<font size="1" face="Courier New"> c =
funcReturningArbitraryi64(p);</font><br>
<font size="1" face="Courier New"> len = LENGTH(c);</font><br>
<font size="1" face="Courier New"> } else {</font><br>
<font size="1" face="Courier New"> len = LENGTH(c);</font><br>
<font size="1" face="Courier New"> }</font><br>
<font size="1" face="Courier New">#endif</font><br>
<br>
<font size="1" face="Courier New"> // ...</font><br>
<br>
<font size="1" face="Courier New"> return len;</font><br>
<font size="1" face="Courier New">}</font><br>
<font size="2" face="Arial"><br>
In this case, we see that creating an else block and replicating
the return
statement in both the if and else branch (like the code snippet
guarded
by the #else) enables the macro UNISKIP in the else branch to be
optimized.</font><font size="2" face="Arial"><br>
</font><font size="2" face="Arial"><br>
<br>
Most of the examples we have come up with so far are centered
around value
ranges along the conditional branches. When the range of values
a symbol
can have along different branches is provably different,
opportunities
for optimization may arise. However, this likely isn't the only
category
of optimizations that could benefit from this.<br>
<br>
Is there an existing transformation in LLVM that should be doing
this already
that is missing this opportunity? If not, we would like to
pursue adding
this. Of course, this optimization would be subject to a cost
model as
it may result in code growth. For example, it may not be
advantageous to
do this if the simplified branch is cold. If anyone has any
comments/suggestions
we are very much interested in hearing them.</font><br>
</blockquote>
<br>
We have two transformations that track ranges along CFG edges using
LazyValueInfo: JumpThreading and CorrelatedValuePropagation. I don't
think that either does what you're proposing.<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:OF0C4863BE.ABAD99EF-ON0025818D.0072AF44-8525818D.0072D93E@notes.na.collabserv.com"
type="cite"><br>
<br>
<br>
<font size="2" face="Arial">Regards, <br>
<br>
<br>
Tony Jiang, M.Sc.<br>
LLVM PPC Backend Development<br>
IBM Toronto Lab, C2/712/8200/MKM<br>
8200 Warden Ave, Markham, L6G 1C7<br>
Email: </font><a moz-do-not-send="true"
href="mailto:nemanjai@ca.ibm.com"><font color="blue" size="2"
face="Arial"><u>jtony@ca.ibm.com</u></font></a><font size="2"
face="Arial"><br>
Phone: 905-413-3676</font><br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>