<font size=2 face="sans-serif">Hi Daniel,</font><br><br><font size=2 face="sans-serif">Thank you very much for you valuable
feedback. We are </font><font size=3>looking into the range analysis
you mentioned. Once we have a better understand about it, we can discuss
more in the follow-up emails.</font><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 href=mailto:nemanjai@ca.ibm.com><font size=2 color=blue face="Arial"><u>jtony@ca.ibm.com</u></font></a><font size=2 face="Arial"><br>Phone: 905-413-3676</font><br><br><br><br><font size=1 color=#5f5f5f face="sans-serif">From:
</font><font size=1 face="sans-serif">Daniel Berlin <dberlin@dberlin.org></font><br><font size=1 color=#5f5f5f face="sans-serif">To:
</font><font size=1 face="sans-serif">Hal Finkel <hfinkel@anl.gov></font><br><font size=1 color=#5f5f5f face="sans-serif">Cc:
</font><font size=1 face="sans-serif">Tony Jiang <jtony@ca.ibm.com>,
llvm-dev <llvm-dev@lists.llvm.org></font><br><font size=1 color=#5f5f5f face="sans-serif">Date:
</font><font size=1 face="sans-serif">08/31/2017 10:08 PM</font><br><font size=1 color=#5f5f5f face="sans-serif">Subject:
</font><font size=1 face="sans-serif">Re: [llvm-dev]
[RFC] Value Range Based Optimization Opportunity in LLVM</font><br><hr noshade><br><br><br><font size=3>NewGVN does some of it.</font><br><font size=3>It will discover if backpropagation through a phi enables
an operation to be put in terms of existing expressions or constants.</font><br><font size=3>It does not track ranges though, only explicit values.</font><br><br><font size=3>In your ORIG block, if LENGTH can be expressed as a merge
of already-computed expressions or constants in the program, it will
discover it.</font><br><br><font size=3>You can stare at examples of this (and compute quite complicated
ones if you wish) at test/Transforms/NewGVN/completeness.ll</font><br><br><font size=3>Both your examples already have a phi in it in llvm ir,
so that is just a matter of the proper range propagation.</font><br><font size=3>It is really:</font><br><font size=3><br>int test()</font><br><font size=3>{<br> int Ret0 = 0;</font><br><font size=3> if (!Ptr)</font><br><font size=3> Ret1= calli(a)</font><br><font size=3> RetPhi = PHI(Ret0, Ret1)</font><br><font size=3> return RetPhi;</font><br><font size=3>}</font><br><br><font size=3>It should already be possible to determine the value of
Ret0 to be 0 based on ranges without duplicating anything, and the extra
return doesn't give you anything. </font><br><br><font size=3>If you want to do it based on ranges: a combination
of a value range computation using the existing sparse propagation engine,
and a transform at phi nodes like we use for NewGVN, should be able to
handle what you want here. The existing lazy value info may
not get an optimal answer for various reasons (it is trying to propagate
in the wrong direction, so it loses some context)</font><br><br><font size=3>You could also use the same basic infrastructure that
predicateinfo uses, and rename info at points the ranges could have changed
to get additional precision.</font><br><font size=3> (unlike predicateinfo, which renames when there
are branches). </font><br><br><font size=3>There are quite a number of papers on making SSA forms
that are effective at range propagation. PredicateInfo is building pruned
e-ssa, which is the basis of a number of range analysis (see </font><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__homepages.dcc.ufmg.br_-7Efernando_publications_papers_CGO13-5Fraphael.pdf&d=DwMFaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=mBGb2CsSgiVUuYo0ta9GLw&m=USltm4Wzio_SM2yOe3ySnSzaIdUkOqvbcrfP2KjciCw&s=rl9nKdQmTZPQqvQhmfVlpk1250DBVkQhU5iAPTZ4pig&e="><font size=3 color=blue><u>http://homepages.dcc.ufmg.br/~fernando/publications/papers/CGO13_raphael.pdf</u></font></a><font size=3>and the slides at </font><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__laure.gonnord.org_pro_research_ER03-5F2015_RangeAnalysis.pdf&d=DwMFaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=mBGb2CsSgiVUuYo0ta9GLw&m=USltm4Wzio_SM2yOe3ySnSzaIdUkOqvbcrfP2KjciCw&s=9oR71GuZpUdxHv95B8sA4sNa8SEnGdeSKX9A3EQe9qg&e="><font size=3 color=blue><u>http://laure.gonnord.org/pro/research/ER03_2015/RangeAnalysis.pdf</u></font></a><font size=3>).</font><br><br><font size=3>The only case you should ever need to duplicate code is
when the expression is something not already computed in the program.
That's not the case for your first example, it can be done without code
duplication. For your second example, it would require insertion,
but you could know ahead of time which computations you actually need to
insert.</font><br><br><br><br><font size=3>On Thu, Aug 31, 2017 at 6:22 PM, Hal Finkel via llvm-dev
<</font><a href="mailto:llvm-dev@lists.llvm.org" target=_blank><font size=3 color=blue><u>llvm-dev@lists.llvm.org</u></font></a><font size=3>>
wrote:</font><br><p><font size=3>On 08/31/2017 03:54 PM, Tony Jiang via llvm-dev wrote:</font><br><font size=2 face="Arial">Hi All,</font><font size=3><br></font><font size=2 face="Arial"><br>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.<br><br>Given pseudo-code:</font><font size=1 face="Courier New"><br><br>// block A<br>if (some condition)<br> // block B<br>// block C</font><font size=2 face="Arial"><br><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> <br><br>Consider the following example:<br> <br></font><font size=1 face="Courier New"><br><br>int test(int *Ptr, int a, int b, int c, int d) { <br> 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"> <br><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=3><br></font><font size=1 face="Courier New"><br>unsigned long funcReturningArbitraryi64(unsigned char *p);<br>#define LENGTH(uv) ( (uv) < 0x80
? 1 : \<br>
(uv) < 0x800 ? 2 : \<br>
(uv) < 0x10000 ? 3 : \<br>
(uv) < 0x200000 ? 4 : \<br>
(uv) < 0x4000000 ? 5 : \<br>
(uv) < 0x80000000 ? 6 : 7 )</font><font size=3><br></font><font size=1 face="Courier New"><br>int func(unsigned char *p, bool flag)<br>{<br> unsigned long c = *p;<br> int len;<br> // ...<br>#ifdef _ORIG<br> if(flag) {<br> // ...<br> c = funcReturningArbitraryi64(p);<br> }<br>len = LENGTH(c);<br>#else<br> if(flag) {<br> // ...<br> c = funcReturningArbitraryi64(p);<br> len = LENGTH(c);<br> } else {<br> len = LENGTH(c);<br> }<br>#endif</font><font size=3><br></font><font size=1 face="Courier New"><br> // ...</font><font size=3><br></font><font size=1 face="Courier New"><br> return len;<br>}</font><font size=2 face="Arial"><br><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.<br><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><br><font size=3>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></font><br><font size=3><br><br></font><font size=2 face="Arial"><br>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 href=mailto:nemanjai@ca.ibm.com target=_blank><font size=2 color=blue face="Arial"><u>jtony@ca.ibm.com</u></font></a><font size=2 face="Arial"><br>Phone: </font><a href="tel:(905)%20413-3676" target=_blank><font size=2 color=blue face="Arial"><u>905-413-3676</u></font></a><font size=3><br><br></font><br><tt><font size=3>_______________________________________________<br>LLVM Developers mailing list<br></font></tt><a href="mailto:llvm-dev@lists.llvm.org" target=_blank><tt><font size=3 color=blue><u>llvm-dev@lists.llvm.org</u></font></tt></a><tt><font size=3><br></font></tt><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=mBGb2CsSgiVUuYo0ta9GLw&m=USltm4Wzio_SM2yOe3ySnSzaIdUkOqvbcrfP2KjciCw&s=rSm2rt8_wGZQ7m7bv_ZTIrh_u8MCKWQCr91G8ipOm0E&e=" target=_blank><tt><font size=3 color=blue><u>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</u></font></tt></a><tt><font size=3 color=#8f8f8f><br></font></tt><br><br><tt><font size=3 color=#8f8f8f>-- <br>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory</font></tt><br><font size=3><br>_______________________________________________<br>LLVM Developers mailing list</font><font size=3 color=blue><u><br></u></font><a href="mailto:llvm-dev@lists.llvm.org"><font size=3 color=blue><u>llvm-dev@lists.llvm.org</u></font></a><font size=3 color=blue><u><br></u></font><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=mBGb2CsSgiVUuYo0ta9GLw&m=USltm4Wzio_SM2yOe3ySnSzaIdUkOqvbcrfP2KjciCw&s=rSm2rt8_wGZQ7m7bv_ZTIrh_u8MCKWQCr91G8ipOm0E&e=" target=_blank><font size=3 color=blue><u>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</u></font></a><font size=3><br></font><br><br><br><BR>