<font size=2 face="sans-serif">Hi All, </font><br><br><font size=2 face="sans-serif">The </font><font size=2 face="Arial">macro
UNISKIP</font><font size=2 face="sans-serif"> mentioned in the second example
should be LENGTH. Sorry about that.</font><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 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">Tony Jiang/Toronto/IBM</font><br><font size=1 color=#5f5f5f face="sans-serif">To:      
 </font><font size=1 face="sans-serif">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 04:54 PM</font><br><font size=1 color=#5f5f5f face="sans-serif">Subject:    
   </font><font size=1 face="sans-serif">[RFC] Value
Range Based Optimization Opportunity in LLVM</font><br><hr noshade><br><br><br><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><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 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>