llvm dev - Mar 2016 - Why LLVM cannot optimize this?

Hi,

Yes SCEV is pretty limited on this aspect.
This kind of code can trigger LLVM to explode in time/memory:
https://llvm.org/bugs/show_bug.cgi?id=18606
<https://llvm.org/bugs/show_bug.cgi?id=18606>

See also this llvm-dev thread:  SCEV implementation and limitations, do we need
"pow"? :
http://lists.llvm.org/pipermail/llvm-dev/2014-February/070062.html

CC: Sanjoy who may have an opinion on how to improve SCEV for this?

-- 
Mehdi

> On Mar 1, 2016, at 11:31 PM, Hongbin Zheng via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> if you replace "zero *= a;" by "zero += a;",  you get:
> 
> ; Function Attrs: norecurse nounwind readnone uwtable
> define i32 @foo(i32 %a) #0 {
> entry:
>   %0 = mul i32 %a, 10000
>   ret i32 %0
> }
> 
> I think the problem is ScalarEvolution only have "SCEVAddRecExpr"
for zero += a, but no corresponding expression to represent and optimize zero *=
a;
> 
> 
> 
> On Wed, Mar 2, 2016 at 3:24 PM, zet via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> test.c :
> -----------------------------------------------------------------------
> int foo(int a)
> {
>   int zero = 0;
>   for (int i = 0; i < 10000; i++)
>     zero *= a;
>   return zero;
> }
> -------------------------------------------------------------------------
> 
> run clang : clang -O2 -S test.c -o test.s
> 
> My clang version is 3.7.1.
> We will get a horrible assembly output.
> 
> Why constant propagation and other optimization skills can not find out
that variable zero is initialized 0, and the only statement in for loop (i.e.
zero *= a) always get a 0?
> 
> I can read the clang/llvm source, Please tell me more details.
> 
> THX
> 
> 
> -- 
> 业精于勤,荒于嬉..
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160302/2fae2532/attachment.html>

[+CC Andy]

A similar issue also comes up in cases like this:

int clz(unsigned long val) {
  unsigned result = sizeof(unsigned long);
  if (val) {
    do {
      result--;
      val >>= 1;
    } while (val);
  }
  return result;
}

where we'd like to be able to compute the tripcount of the loop as
"sizeof(long) - clz(val) - 1" and get rid of the loop entirely via
RewriteLoopExitValues.

The reason why the above issue is "similar" to wanting a
"SCEVPowExpr"
is that both are examples of SCEV node kinds that will be useful in
some very specific cases; but probably is not seen widely enough that
teaching whole of ScalarEvolution how to simplify these is a good
idea.

To get around this, I've been thinking (and only thinking, no code yet
:) ) about adding a possible "SCEVIntrinsicExpr", parameterized by an
"OpCode", like SCEVIntrinsicExpr::Pow or
SCEVIntrinsicExpr::CountLeadingZeroes.  The idea is that these would
be a low-overhead way of adding new kinds of expressions to the SCEV
hierarchy, with the only constraints being:

 - They're a pure, mathematically function of their input values
 - SCEVExpander knows how to expand them
 - It is always safe to treat them as SCEVUnknowns

-- Sanjoy

While SCEV provides a generic framework to calculate the loop exit values,
may be what zet asking is just an instcomb that replace the loop exit value
of zero by 0, when zero is initialized to 0 before the loop?

On Thu, Mar 3, 2016 at 5:23 AM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> [+CC Andy]
>
> A similar issue also comes up in cases like this:
>
> int clz(unsigned long val) {
>   unsigned result = sizeof(unsigned long);
>   if (val) {
>     do {
>       result--;
>       val >>= 1;
>     } while (val);
>   }
>   return result;
> }
>
> where we'd like to be able to compute the tripcount of the loop as
> "sizeof(long) - clz(val) - 1" and get rid of the loop entirely
via
> RewriteLoopExitValues.
>
> The reason why the above issue is "similar" to wanting a
"SCEVPowExpr"
> is that both are examples of SCEV node kinds that will be useful in
> some very specific cases; but probably is not seen widely enough that
> teaching whole of ScalarEvolution how to simplify these is a good
> idea.
>
> To get around this, I've been thinking (and only thinking, no code yet
> :) ) about adding a possible "SCEVIntrinsicExpr", parameterized
by an
> "OpCode", like SCEVIntrinsicExpr::Pow or
> SCEVIntrinsicExpr::CountLeadingZeroes.  The idea is that these would
> be a low-overhead way of adding new kinds of expressions to the SCEV
> hierarchy, with the only constraints being:
>
>  - They're a pure, mathematically function of their input values
>  - SCEVExpander knows how to expand them
>  - It is always safe to treat them as SCEVUnknowns
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160303/e5958717/attachment.html>