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 -------------- next part -------------- A non-text attachment was scrubbed... Name: phi_select_opt.diff Type: text/x-patch Size: 1720 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120518/6cecec0f/attachment.bin>
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. -- Roland ----- Original Message -----> From: "Roland Leißa" <leissa at cs.uni-saarland.de> > To: llvmdev at cs.uiuc.edu > Sent: Donnerstag, 17. Mai 2012 19:15:22 > Subject: [LLVMdev] Phi + Select Optimization > > 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
You should probably send this to llvm-commits; llvm-dev is more for general discussion. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120519/89a11e83/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: cafxx.vcf Type: text/x-vcard Size: 230 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120519/89a11e83/attachment.vcf>
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. -- Roland ----- Original Message -----> From: "Carlo Alberto Ferraris" <cafxx at strayorange.com> > To: llvmdev at cs.uiuc.edu > Sent: Samstag, 19. Mai 2012 09:17:38 > Subject: Re: [LLVMdev] Phi + Select Optimization > > > You should probably send this to llvm-commits; llvm-dev is more for > general discussion. > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
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.> 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 > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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! -- 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. > > > 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 > > > > > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev