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

Tue Feb 9 13:14:42 PST 2016

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>