Page MenuHomePhabricator

[DAGCombiner] Fold BRCOND(FREEZE(COND)) to BRCOND(COND)
ClosedPublic

Authored by aqjune on Nov 24 2020, 2:11 AM.

Details

Summary

This patch resolves the suboptimal codegen described in http://llvm.org/pr47873 .
When CodeGenPrepare lowers select into a conditional branch, a freeze instruction is inserted.
It is then translated to BRCOND(FREEZE(SETCC)) in SelDag.
The FREEZE in the middle of SETCC and BRCOND was causing a suboptimal code generation however.
This patch adds BRCOND(FREEZE(cond)) -> BRCOND(cond) fold to DAGCombiner to remove the FREEZE.

To make this optimization sound, BRCOND(UNDEF) simply should nondeterministically jump to the branch or not, rather than raising UB.
It wasn't clear what happens when the condition was undef according to the comments in ISDOpcodes.h, however.
I updated the comments of BRCOND to make it explicit (as well as BR_CC, which is also a conditional branch instruction).

Note that it diverges from the semantics of br instruction in IR, which is explicitly UB.
Since the UB semantics was necessary to explain optimizations that use branching conditions, and SelDag doesn't seem to have such optimization, I think this divergence is okay.

Diff Detail

Event Timeline

aqjune created this revision.Nov 24 2020, 2:11 AM
aqjune requested review of this revision.Nov 24 2020, 2:11 AM
aqjune edited the summary of this revision. (Show Details)Nov 24 2020, 2:13 AM
spatel accepted this revision.Thu, Dec 31, 6:20 AM

LGTM - please pre-commit the test with the current (trunk) codegen, so we see the diff (and don't lose the test in case we have to revert).

This revision is now accepted and ready to land.Thu, Dec 31, 6:20 AM
aqjune updated this revision to Diff 314216.Fri, Jan 1, 5:44 AM

Rebase, precommit the test

aqjune added a comment.Fri, Jan 1, 6:03 AM

Thanks! I precommitted it.

BTW, @nlopes suggested that this might require more attention from backend people, with a broader context.
The undef/poison-related semantics in the SelDag/MachineIR should be discussed & explicitly stated in detail.
My idea is to clarify the low-level IR semantics as follows:

  • SelDag: has undef/poison, but branching on them is nondet choice. This allows the brcond(freeze(cond)) -> brcond(cond) folding, but now it is illegal to use branch condition to optimize code in SelDag. In order to use branch condition, the condition should be recorded using e.g., llvm.assume from IR when lowering.
  • MachineIR: has no undef/poison; all values are well-defined. This will make many reasonings easier & also make the end-to-end compilation of freeze instruction valid (currently we need FREEZE in MachineIR :/ ) This will require IMPLICIT_DEF to have 'frozen value'.

For GlobalISel, I have no idea right now... it should be somewhere between SelDag and MachineIR? Or can be simply assume that it is equivalent to MachineIR?

Maybe I can initiate a discussion about this to llvm-dev when I have enough bandwidth (maybe at the end of Jan..? There are quite a few things going on: lifetime, logical and/or, shufflevector, and my research.. 🧐 ).

Once it is settled, it should be documented somewhere. Is there a documentation like LangRef for SelDag/MachineIR? What I've seen is only comments in ISDOpcodes.h/TargetOpcodes.def .

nikic added a subscriber: nikic.Fri, Jan 1, 7:26 AM
nikic added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14556

Isn't this only valid if freeze has one use?

aqjune updated this revision to Diff 314262.Sat, Jan 2, 3:35 PM

Add one use check

aqjune marked an inline comment as done.Sat, Jan 2, 3:38 PM
aqjune added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14556

You're right, I added the condition.

aqjune marked an inline comment as done.Sat, Jan 2, 3:38 PM

Seems ok to land?

nikic added a comment.Tue, Jan 12, 9:26 AM

Yes, I think this is fine to land as-is. Note that SDAG always works on a single basic block, so I don't think there is any value in having "branch on undef is UB" semantics, as we can't infer information from branch conditions anyway.

Yes, I think this is fine to land as-is. Note that SDAG always works on a single basic block, so I don't think there is any value in having "branch on undef is UB" semantics, as we can't infer information from branch conditions anyway.

Okay. Since it would be desirable for the reported performance bug to be closed before branching, I'll land this patch.
I'll leave a link to this patch at comments as well.

aqjune updated this revision to Diff 316276.Tue, Jan 12, 4:57 PM

Leave a comment about the issue

This revision was landed with ongoing or failed builds.Tue, Jan 12, 4:57 PM
This revision was automatically updated to reflect the committed changes.