llvm dev - Feb 2016 - [GVN] same sequence of instructions in if and else branch

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/9c0994e0/attachment.html>

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/31b156dc/attachment.html>

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>

I believe SimplifyCFG instead of GVN does that:
http://llvm.org/docs/doxygen/html/SimplifyCFG_8cpp_source.html#l01080

On Tue, Feb 9, 2016 at 11:30 AM, 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/e08b6ff1/attachment.html>