Summary
I think it would be good to have the CFG simplification options provided by TTI, including the limit on phi->select transformation. We have some code on Hexagon that would benefit not only from converting 1 phi to select (as is the limit now), but 4 of them.
-Krzysztof
I didn’t look closely at the new patch, but this appears to be a small extension to:
https://reviews.llvm.org/D38566
…and the GVN-based reasons for delaying transformation to ‘select’ are discussed in detail in the motivating bug for that patch:
https://bugs.llvm.org/show_bug.cgi?id=34603
So this sounds like the right direction to me. Note that there was objection to the implementation (a pile of pass options vs. uniquely named passes).
Here’s another motivating bug where early transform to select prevents optimization:
https://bugs.llvm.org/show_bug.cgi?id=36760
Is that case affected by this patch?
I’m concerned that we’re focusing on one side of this. Let me point out a few concerns w/changing the canonical form here:
- LICM does not know how to hoist or sink regions. It does know how to hoist and sink selects.
- InstCombine has limited support for triangles/diamonds, but fairly extensive support for selects.
- EarlyCSE and GVN do not know how to eliminate fully redundant triangles/diamonds. PRE may get some of these cases, but that is by no means guaranteed or likely to be robust.
My personal opinion is that selects are the appropriate canonical form.
For the one of the specific cases mentioned, teaching GVN to do FRE and PRE for loads from selects of pointers just doesn’t seem that painful. I would be really tempted to do that instead. Similarly, walking facts back from select uses in CVP seems generally useful since we have use dependent facts in a bunch of contexts, not just selects. (Call arguments for instance, non-null from unconditional deref, etc…)
To be clear, I am raising concerns, not actively objecting to this. If you want to move forward and commit to work through all of the issues identified I wont actively stand in the way.
Philip
As I’ve expressed in the past, I think that not using select as part of our canonical form is potentially a superior design. However, it would be a major change. In addition to the issues that Philip mentions, there’s also the fact that we’ll just have more basic blocks and that, in itself, could lead to an increase in compile time. However, working through these issues will likely leave us with a more-robust optimizer. See also: -Hal
I think we should teach LICM to do this eventually.
- InstCombine has limited support for triangles/diamonds, but fairly extensive support for selects.
- EarlyCSE and GVN do not know how to eliminate fully redundant triangles/diamonds. PRE may get some of these cases, but that is by no means guaranteed or likely to be robust.
Agreed, we’ll need a plan to deal with these issues.
My personal opinion is that selects are the appropriate canonical form.
For the one of the specific cases mentioned, teaching GVN to do FRE and PRE for loads from selects of pointers just doesn’t seem that painful. I would be really tempted to do that instead. Similarly, walking facts back from select uses in CVP seems generally useful since we have use dependent facts in a bunch of contexts, not just selects. (Call arguments for instance, non-null from unconditional deref, etc…)
To be clear, I am raising concerns, not actively objecting to this. If you want to move forward and commit to work through all of the issues identified I wont actively stand in the way.
As I’ve expressed in the past, I think that not using select as part of our canonical form is potentially a superior design. However, it would be a major change. In addition to the issues that Philip mentions, there’s also the fact that we’ll just have more basic blocks and that, in itself, could lead to an increase in compile time. However, working through these issues will likely leave us with a more-robust optimizer.
Canonicalizing to phis is my preference too.
-Hal
Philip
Is scheduling another simplifycfg, instcombine + earlycse pass really necessary? I’m concerned about the compile time impact.
Cheers,
Amara
Agreed. I just don’t currently see patches to do so. Once LICM supports region hoisting, much of my concern disappears. Again, I’d love to see these issues fixed. Once that’s done, the convert about phi vs select as canonical form is much less relevant.
Here’s another motivating bug where early transform to select prevents optimization:
Is that case affected by this patch?
From a quick reading of that bug it looks like CVP needs to be enhanced to do a certain transformation, but the presence
of a select means that even with that enhancement it wouldn’t do anything. With this patch we have a phi and so I think
that if the CVP enhancement were done it should work.
- LICM does not know how to hoist or sink regions. It does know how to hoist and sink selects.
I think we should teach LICM to do this eventually.
Agreed. I just don’t currently see patches to do so. Once LICM supports region hoisting, much of my concern disappears.
I’ve looked into what happens with LICM with this change, and it looks like everything except the phi gets hoisted, then
later the phi is turned into a select, then a later LICM pass hoists the select. For the very simple tests I tried we end up with
the same result in the end, but I wouldn’t be surprised if indeed LICM not doing this makes things worse in more complex
cases.
I’ve hacked together a modification to LICM to make it able to hoist phis (by essentially hoisting entire blocks instead of
moving everything into a single preheader block) and it seemed to work OK, so I’ll get to work on getting that working
properly and committed before I touch phi-to-select transformation.
InstCombine has limited support for triangles/diamonds, but fairly extensive support for selects.
Currently I have InstCombine running directly after phis have been turned into selects, so this should only be a problem if
something before that relies on the select instcombine having already happened. I’ll look into that to see if it is indeed a
problem.
EarlyCSE and GVN do not know how to eliminate fully redundant triangles/diamonds. PRE may get some of these cases, but that is by no means guaranteed or likely to be robust.
Agreed, we’ll need a plan to deal with these issues.
Again, I’d love to see these issues fixed. Once that’s done, the convert about phi vs select as canonical form is much less relevant.
I’ll look into this.
For the one of the specific cases mentioned, teaching GVN to do FRE and PRE for loads from selects of pointers just doesn’t seem that painful. I would be really tempted to do that
instead. Similarly, walking facts back from select uses in CVP seems generally useful since we have use dependent facts in a bunch of contexts, not just selects. (Call arguments for
instance, non-null from unconditional deref, etc…)
Actually making GVN able to handle selects being painful is exactly the reason I’m proposing doing this. GVN has a hard
constraint that a single block can only have a single available value, and attempting to change that (which you have to do
when selecting between values defined in the same block) causes a ton of problems that have to be resolved.
John
Sorry for the delayed response.
This would be a really useful extension to LICM. I look forward to the patch. I was half considering an approach recently where LICM itself did phi-to-select if all of the operands to the resulting phi would be loop invariant. It was just ugly enough I didn’t move forward with it, but we have seen cases where it would resolve pass ordering problems leading to strictly better results overall. I suspect your region hoister would have the same overall effect.