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>
Taewook Oh via llvm-dev
2016-Feb-09 20:51 UTC
[llvm-dev] [GVN] same sequence of instructions in if and else branch
Thanks all for replies.
Does LLVM have a separate VBE pass? I couldn't find one. Although VBE is
primarily for a code size, I see a case that VBE can affect following
optimizations to reduce redundant moves in the binary.
Daniel, great to hear that you are working on a more advanced GVN
implementation. I wonder if you have a timeline to upstream yours.
Best,
Taewook
From: Daniel Berlin <dberlin at dberlin.org<mailto:dberlin at
dberlin.org>>
Date: Tuesday, February 9, 2016 at 12:28 PM
To: Taewook Oh <twoh at fb.com<mailto:twoh at fb.com>>
Cc: mats petersson <mats at planetcatfish.com<mailto:mats at
planetcatfish.com>>, "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 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<mailto: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<mailto: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<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=>
_______________________________________________
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=odyMzWAVRsllwAiB8t4HxXDitjnyM3jpIDKTeJ7R9cU&s=qUYTUrwO6X2i6yPxLpCfdpEFL6q5AtiKHTfIdwO7Pvo&e=>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/b2c48a50/attachment.html>
Daniel Berlin via llvm-dev
2016-Feb-09 21:14 UTC
[llvm-dev] [GVN] same sequence of instructions in if and else branch
On Tue, Feb 9, 2016 at 12:51 PM, Taewook Oh <twoh at fb.com> wrote:> Thanks all for replies. > > Does LLVM have a separate VBE pass? >No. In GCC, this is done by GVN-PRE infrastructure. LLVM does PRE but not really GVN-PRE, and where it does PRE, it does not offer the infrastructure for use as a generic code hoisting pass. (I am working on GVN-PRE after GVN). I couldn't find one. Although VBE is primarily for a code size, I see a> case that VBE can affect following optimizations to reduce redundant moves > in the binary. >This likely means the optimization algorithm used is not powerful enough, and we should fix that :) In the case of GVN, it is going to be because of what i mentioned Given: b = phi(a, <thing provably equivalent to a>) GCC and the new gvn will replace users of b with "a". GVN right now will not. I would not recommend doing code hoisting just to effect this optimization. It is better to just fix the optimizers :)> Daniel, great to hear that you are working on a more advanced GVN > implementation. I wonder if you have a timeline to upstream yours. > >One of the major pieces (MemorySSA) went in last week. I have just about completed duplicating all optimizations GVN performs. Over the next few months i plan on breaking the completed pass back down into parts so it can be submitted incrementally (and any design rework done). So i'd put it at "prototyping and testing just about done"> Best, > Taewook > > From: Daniel Berlin <dberlin at dberlin.org> > Date: Tuesday, February 9, 2016 at 12:28 PM > To: Taewook Oh <twoh at fb.com> > Cc: mats petersson <mats at planetcatfish.com>, "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 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 >>> <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=odyMzWAVRsllwAiB8t4HxXDitjnyM3jpIDKTeJ7R9cU&s=qUYTUrwO6X2i6yPxLpCfdpEFL6q5AtiKHTfIdwO7Pvo&e=> >>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/544b0027/attachment-0001.html>