[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

And there’s no PHI node after this that depends on the condition?

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

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

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.

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.

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

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 :slight_smile:

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 :slight_smile:

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"