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

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


-- 
业精于勤,荒于嬉..
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160302/f15da086/attachment.html>

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>
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
> 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/606c2416/attachment.html>

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>