Taewook Oh via llvm-dev
2016-Feb-09 19:42 UTC
[llvm-dev] [GVN] same sequence of instructions in if and else branch
There is a phi-node "%phi = phi i64 [%cast1, %if], [%cast2, %else]" in
the common successor. The actual control flow is a bit more complex, but there
is a common successor block, and %cast1 and %cast2 are the two values that the
phi node in the common successor takes.
Does the existence of the phi node affect optimization?
Thanks,
Taewook
From: <mats.o.petersson at googlemail.com<mailto:mats.o.petersson at
googlemail.com>> on behalf of mats petersson <mats at
planetcatfish.com<mailto:mats at planetcatfish.com>>
Date: Tuesday, February 9, 2016 at 11:34 AM
To: Taewook Oh <twoh at fb.com<mailto:twoh at fb.com>>
Cc: "llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>" <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] [GVN] same sequence of instructions in if and else
branch
And there's no PHI node after this that depends on the condition?
--
Mats
On 9 February 2016 at 19:30, Taewook Oh via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hello,
I found that GVN doesn't promote identical sequence of instructions in if
and else branch to their common predecessors. For example, for the following
code snippet
pred:
…
br i1 %cmp, label %if, label %else
if:
%incdec.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 1
%cast1 = ptrtoint i8* %incdec.ptr.1 to i64
…
else:
%incdec.ptr.2 = getelementptr inbounds i8, i8* %ptr, i64 1
%cast2 = ptrtoint i8* %incdec.ptr.2 to i64
GVN doesn't move instructions in 'if' and 'else' blocks to
'pred' block even though it knows that incdec.ptr.1/case1 has a same
value number with incdec.ptr.2/cast2. I see a case where this kind of redundancy
confuses following optimization passes and ends up generating suboptimal code.
>From the GVN implementation, it seems that transformation is performed only
when the "leader" value dominates the other value, so it cannot handle
a case like the above example. I wonder if this is by design or just a missing
feature.
Thanks,
Taewook
_______________________________________________
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<https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kOsLCgQzH7N8ptZ7diJD9g&m=Xf5AAq_dBp5IcStlnft7nao-p-fDTN5AH6oItVXC3BA&s=4VUE3_dUQQ8AKzkWv5Tu6nJ979NtsOIq3qVC7CipHL8&e=>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/d1ca226d/attachment.html>
Daniel Berlin via llvm-dev
2016-Feb-09 20:26 UTC
[llvm-dev] [GVN] same sequence of instructions in if and else branch
This GVN does not do that, this is correct. It is a very simple GVN. All phi nodes are considered to have unique values. GCC's GVN, and the one i'm developing for LLVM at https://github.com/dberlin/llvm-gvn-rewrite does the right thing. On Tue, Feb 9, 2016 at 11:42 AM, Taewook Oh via llvm-dev < llvm-dev at lists.llvm.org> wrote:> There is a phi-node "%phi = phi i64 [%cast1, %if], [%cast2, %else]" in the > common successor. The actual control flow is a bit more complex, but there > is a common successor block, and %cast1 and %cast2 are the two values that > the phi node in the common successor takes. > > Does the existence of the phi node affect optimization? > > Thanks, > Taewook > > > From: <mats.o.petersson at googlemail.com> on behalf of mats petersson < > mats at planetcatfish.com> > Date: Tuesday, February 9, 2016 at 11:34 AM > To: Taewook Oh <twoh at fb.com> > Cc: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org> > Subject: Re: [llvm-dev] [GVN] same sequence of instructions in if and > else branch > > And there's no PHI node after this that depends on the condition? > > -- > Mats > > On 9 February 2016 at 19:30, Taewook Oh via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> Hello, >> >> >> I found that GVN doesn't promote identical sequence of instructions in if >> and else branch to their common predecessors. For example, for the >> following code snippet >> >> >> pred: >> >> … >> >> br i1 %cmp, label %if, label %else >> >> if: >> >> %incdec.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 1 >> >> %cast1 = ptrtoint i8* %incdec.ptr.1 to i64 >> >> … >> >> else: >> >> %incdec.ptr.2 = getelementptr inbounds i8, i8* %ptr, i64 1 >> >> %cast2 = ptrtoint i8* %incdec.ptr.2 to i64 >> >> >> GVN doesn't move instructions in 'if' and 'else' blocks to 'pred' block >> even though it knows that incdec.ptr.1/case1 has a same value number with >> incdec.ptr.2/cast2. I see a case where this kind of redundancy confuses >> following optimization passes and ends up generating suboptimal code. >> >> >> From the GVN implementation, it seems that transformation is performed >> only when the "leader" value dominates the other value, so it cannot handle >> a case like the above example. I wonder if this is by design or just a >> missing feature. >> >> >> Thanks, >> >> Taewook >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kOsLCgQzH7N8ptZ7diJD9g&m=Xf5AAq_dBp5IcStlnft7nao-p-fDTN5AH6oItVXC3BA&s=4VUE3_dUQQ8AKzkWv5Tu6nJ979NtsOIq3qVC7CipHL8&e=> >> >> > > _______________________________________________ > 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/20160209/982f7a70/attachment.html>
Daniel Berlin via llvm-dev
2016-Feb-09 20:28 UTC
[llvm-dev] [GVN] same sequence of instructions in if and else branch
and by "right thing" i mean it can hoist if you want and it can prove it will not extend the live range. Note that VBE (very busy expressions) is a code size optimization only. It does not save time. On Tue, Feb 9, 2016 at 12:26 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> This GVN does not do that, this is correct. It is a very simple GVN. All > phi nodes are considered to have unique values. > GCC's GVN, and the one i'm developing for LLVM at > https://github.com/dberlin/llvm-gvn-rewrite does the right thing. > > > > On Tue, Feb 9, 2016 at 11:42 AM, Taewook Oh via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> There is a phi-node "%phi = phi i64 [%cast1, %if], [%cast2, %else]" in >> the common successor. The actual control flow is a bit more complex, but >> there is a common successor block, and %cast1 and %cast2 are the two values >> that the phi node in the common successor takes. >> >> Does the existence of the phi node affect optimization? >> >> Thanks, >> Taewook >> >> >> From: <mats.o.petersson at googlemail.com> on behalf of mats petersson < >> mats at planetcatfish.com> >> Date: Tuesday, February 9, 2016 at 11:34 AM >> To: Taewook Oh <twoh at fb.com> >> Cc: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org> >> Subject: Re: [llvm-dev] [GVN] same sequence of instructions in if and >> else branch >> >> And there's no PHI node after this that depends on the condition? >> >> -- >> Mats >> >> On 9 February 2016 at 19:30, Taewook Oh via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> Hello, >>> >>> >>> I found that GVN doesn't promote identical sequence of instructions in >>> if and else branch to their common predecessors. For example, for the >>> following code snippet >>> >>> >>> pred: >>> >>> … >>> >>> br i1 %cmp, label %if, label %else >>> >>> if: >>> >>> %incdec.ptr.1 = getelementptr inbounds i8, i8* %ptr, i64 1 >>> >>> %cast1 = ptrtoint i8* %incdec.ptr.1 to i64 >>> >>> … >>> >>> else: >>> >>> %incdec.ptr.2 = getelementptr inbounds i8, i8* %ptr, i64 1 >>> >>> %cast2 = ptrtoint i8* %incdec.ptr.2 to i64 >>> >>> >>> GVN doesn't move instructions in 'if' and 'else' blocks to 'pred' block >>> even though it knows that incdec.ptr.1/case1 has a same value number with >>> incdec.ptr.2/cast2. I see a case where this kind of redundancy confuses >>> following optimization passes and ends up generating suboptimal code. >>> >>> >>> From the GVN implementation, it seems that transformation is performed >>> only when the "leader" value dominates the other value, so it cannot handle >>> a case like the above example. I wonder if this is by design or just a >>> missing feature. >>> >>> >>> Thanks, >>> >>> Taewook >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=kOsLCgQzH7N8ptZ7diJD9g&m=Xf5AAq_dBp5IcStlnft7nao-p-fDTN5AH6oItVXC3BA&s=4VUE3_dUQQ8AKzkWv5Tu6nJ979NtsOIq3qVC7CipHL8&e=> >>> >>> >> >> _______________________________________________ >> 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/20160209/9661e892/attachment.html>