Philip Reames via llvm-dev
2016-Mar-03 22:39 UTC
[llvm-dev] Failure to turn a div by power of 2 into a single shift
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-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160303/8e011711/attachment.html>
Sanjoy Das via llvm-dev
2016-Mar-03 23:29 UTC
[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
Haicheng Wu via llvm-dev
2016-Mar-04 18:50 UTC
[llvm-dev] Failure to turn a div by power of 2 into a single shift
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
Haicheng Wu via llvm-dev
2016-Mar-07 21:54 UTC
[llvm-dev] Failure to turn a div by power of 2 into a single shift
I created a patch in D17921 to address this.
Best,
Haicheng
-----Original Message-----
From: Haicheng Wu [mailto:haicheng at codeaurora.org]
Sent: Friday, March 04, 2016 1:51 PM
To: 'Sanjoy Das'; 'Philip Reames'
Cc: 'llvm-dev'
Subject: RE: [llvm-dev] Failure to turn a div by power of 2 into a single shift
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