[llvm-dev] Failure to turn a div by power of 2 into a single shift

[Haicheng Wu via llvm-dev]

Thank you, both of you.

In Sanjoy's example, CorrelatedValuePropagation makes the change.  I guess I can do the similar thing to turn the sdiv to udiv.

Best,

Haicheng

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Thursday, March 03, 2016 6:29 PM
To: Philip Reames
Cc: Haicheng Wu; llvm-dev
Subject: Re: [llvm-dev] Failure to turn a div by power of 2 into a single shift

SCEV certainly should be able to prove that "j" is positive; but I'm not sure if it is being queried about that via isKnownPredicate.

An interesting variant of the original example is

void foo(int n, volatile int* p) {
  int i, j;
  for (j = n; j > 1; j = i) {
    *p = (j > 0);
    i = j / 2;
  }
}

where the volatile store to *p does get optimized to "*p = true", but that happens before loop rotation, when the loop is still in the form of

define void @foo(i32 %n, i32* nocapture %p) #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.body, %entry
  %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
  %cmp = icmp sgt i32 %j.0, 1
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %cmp1 = icmp sgt i32 %j.0, 0
  %conv = zext i1 %cmp1 to i32
  store volatile i32 %conv, i32* %p, align 4, !tbaa !2
  %div = sdiv i32 %j.0, 2
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}

and the dominating check on j > 1 is still "obvious".

-- Sanjoy


On Thu, Mar 3, 2016 at 2:39 PM, Philip Reames <listmail at philipreames.com> wrote:
> I'd missed the fact that j wasn't just being decremented.  This isn't 
> as easy as I said.
>
> Philip
>
>
> On 03/03/2016 02:36 PM, Philip Reames via llvm-dev wrote:
>
> SCEV should be able to easily prove that j is positive here.  I'm not 
> sure where the right place to use that information would be in this case.
> Sanjoy, can you comment?
>
> Philip
>
> On 03/03/2016 02:06 PM, Haicheng Wu wrote:
>
> Hello,
>
>
>
> I have  a simple loop like below
>
>
>
> int I, j;
>
> for (j = n; j > 1; j = i) {
>
>   i = j / 2;
>
> }
>
>
>
> The signed division can be safely turned into a single shift since j 
> is known to be positive from the loop guard.  LLVM currently cannot 
> find out j is positive and compiles the above division into 3 
> instructions.  Any thoughts on where to fix this?
>
>
>
> Thank you in advance,
>
>
>
> Haicheng
>
>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>



--
Sanjoy Das
http://playingwithpointers.com