Page MenuHomePhabricator

[CodeGen] recognize select form of and/ors when splitting branch conditions
ClosedPublic

Authored by aqjune on Dec 28 2020, 1:00 AM.

Details

Summary

Recently a few patches are made to move towards using select i1 instead of and/or i1 to represent "a && b"/"a || b" in C/C++.
"a && b" in C/C++ does not evaluate b if a is false whereas 'and a, b' in IR evaluates b and uses its result regardless of the result of a.
This is problematic because it can cause miscompilation if b was an erroneous operation (https://llvm.org/pr48353).
In C/C++, the result is simply false because b is not evaluated, but in IR the result is poison.
The discussion at D93065 has more context about this.

This patch makes two branch-splitting optimizations (one in SelectionDAGBuilder, one in CodeGenPrepare) recognize
select form of and/or as well using m_LogicalAnd/Or.
Since it is CodeGen, I think this is semantically ok (at least as safe as what codegen already did).

Diff Detail

Event Timeline

aqjune created this revision.Dec 28 2020, 1:00 AM
aqjune requested review of this revision.Dec 28 2020, 1:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 28 2020, 1:00 AM
nikic added a comment.Dec 28 2020, 3:31 AM

This looks correct to me, as we're breaking the select up into two branches, which means the second condition will get short-circuited entirely. As far as I can see, the conditions don't get swapped or similar.

However, I think it's worthwhile to consider an alternative here: We could simply fold select -> and/or in CGP, and forget about this as far as CodeGen is concerned. This is not technically correct, because SDAG also has a poison concept, but it's kind of a moot point, as DAGCombiner will end up doing the transform anyway: https://github.com/llvm/llvm-project/blob/a485a59d2172daaee1d5e734da54fbb243f7d54c/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L9197-L9220 That's something we could revisit if we ever wanted to drop the corresponding DAGCombiner fold (but I believe our current stance is to ignore such issues in the SDAG layer, as poison reasoning is used much less in this area and we've not seen any practical poison-related miscompiles in SDAG).

llvm/lib/CodeGen/CodeGenPrepare.cpp
7867–7873

I think this will make the optimization not work for a chain of logical and/or, as this restricts to m_BinOp.

aqjune updated this revision to Diff 313889.Dec 28 2020, 1:26 PM

clang-format, address a comment

I'm slightly worried that it will still preserve unsound IR-level transformation (because CodeGenPrepare is in IR). :( A bug in CodeGenPrepare will be hard to discover because opt -O<n> won't use it.
If DAGCombiner does that, would it be still okay in terms of performance? I see that SelectionDAGISel::CodeGenAndEmitDAG invokes CurDAG->Combine first.

We do this condition splitting optimization in GlobalISel too, so that will also need fixing: see IRTranslator.cpp.

aqjune updated this revision to Diff 314067.Dec 29 2020, 10:19 PM

Support GlobalISel

aqjune marked an inline comment as done.Dec 29 2020, 10:21 PM

Thanks! Added tests for globalisel as well

nikic accepted this revision.Dec 31 2020, 3:48 AM

I'm slightly worried that it will still preserve unsound IR-level transformation (because CodeGenPrepare is in IR). :( A bug in CodeGenPrepare will be hard to discover because opt -O<n> won't use it.
If DAGCombiner does that, would it be still okay in terms of performance? I see that SelectionDAGISel::CodeGenAndEmitDAG invokes CurDAG->Combine first.

Fair enough. CGP does call things like InstructionSimplify, so there is some potential for issues... I was concerned that keeping select would cause SDAG fallback in FastISel, but apparently that will happen anyway for non-branch uses of and/or (and branch uses are split).

So this LGTM.

This revision is now accepted and ready to land.Dec 31 2020, 3:48 AM