Phi + Select Optimization

Project Infrastructure LLVM Dev List Archives
1

Hi all,

I've just written a small enhancement to SimplifyPHINode.

The idea is the following:

If we have this:

a = phi(X, X, undef, undef, X, undef)
X = select cond, sth, a

or this:

a = phi(X, X, undef, undef, X, undef)
X = select cond, a, sth

we can replace the phi by 'a' and the select by 'sth'.

Why does this work?

Well, in those cases where control-flow happens to hit the phi from undef edges the select can just "wish" to get 'sth' instead of 'a'.
In the other case, the phi depends on itself.
Thus, we can remove it.

The attached patch implements that.
This is really useful in vectorized code, when there are a lot of selects in order to implement "vectorized control-flow".

Also, there is a minor enhancement which improves SimplifySelectInst to also simplify when the condition is a vector of all true or false values.

Enjoy,
Roland

phi_select_opt.diff (1.68 KB)

2

Oh forgot to mention:
This patch is just a small proof of concept.
Actually, the idea should also work when there is a whole chain of selects like this:

a = phi(X, X, undef, undef, X, undef)
b = select cond1, ..., a
c = select cond2, ..., b
X = select cond3, ..., c

Note the operand order in the select is not important.

3

You should probably send this to llvm-commits; llvm-dev is more for general discussion.

4

I consider my patch not mature enough to be committed.
I just wanted to hear what others are saying. I'm not quite sure how to exactly deal with these cascades of selects which induce a cycle via a Phi; I'd like to implement that as well. Also, I'm not sure whether InstructionSimplify.cpp is the proper place for this optimization.

5

Nella citazione in data sabato 19 maggio 2012 09:50:03, Roland Leißa ha scritto:

I consider my patch not mature enough to be committed.
I just wanted to hear what others are saying. I'm not quite sure how to exactly deal with these cascades of selects which induce a cycle via a Phi; I'd like to implement that as well. Also, I'm not sure whether InstructionSimplify.cpp is the proper place for this optimization.

IMHO, if you have something that improves the results and does not break anything, it should go in.It's always possible to improve it afterwards.

6

Hi Roland,

If we have this:

a = phi(X, X, undef, undef, X, undef)

such a phi should already be replaced by X if X dominates this basic block.
Is this not the case? Or does each X here not necessary represent the same
value?

Ciao, Duncan.

7

Hi Duncan,

thank you for your thoughts.

yes, X represents the same value and yes
a = phi(X, X, undef, undef, X, undef)
gets replaced by X if X dominates the BB.

But:

a = phi(X, X, undef, undef, X, undef)
X = select cond, sth, a

does *not* dominate the BB. The select instruction induces a cycle to the phi
node: X is defined by the select instruction!