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

[aqjune]

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.

[spatel]

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).

[aqjune]

Rebase, precommit the test

[aqjune]

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]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14556

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

[aqjune]

Add one use check

[aqjune]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14556

You're right, I added the condition.

[xbolva00]

Seems ok to land?

[nikic]

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.

[aqjune]

In D92015#2493214, @nikic wrote:

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]

Leave a comment about the issue

llvm/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
 
   /// BR_JT - Jumptable branch. The first operand is the chain, the second
   /// is the jumptable index, the last one is the jumptable entry index.
   BR_JT,
 
   /// BRCOND - Conditional branch.  The first operand is the chain, the
   /// second is the condition, the third is the block to branch to if the
   /// condition is true.  If the type of the condition is not i1, then the
-  /// high bits must conform to getBooleanContents.
+  /// high bits must conform to getBooleanContents. If the condition is undef,
+  /// it nondeterministically jumps to the block.
+  /// TODO: Its semantics w.r.t undef requires further discussion; we need to
+  /// make it sure that it is consistent with optimizations in MIR & the
+  /// meaning of IMPLICIT_DEF. See https://reviews.llvm.org/D92015
   BRCOND,
 
   /// BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
   /// that the condition is represented as condition code, and two nodes to
   /// compare, rather than as a combined SetCC node.  The operands in order
-  /// are chain, cc, lhs, rhs, block to branch to if condition is true.
+  /// are chain, cc, lhs, rhs, block to branch to if condition is true. If
+  /// condition is undef, it nondeterministically jumps to the block.
   BR_CC,
 
   /// INLINEASM - Represents an inline asm block.  This node always has two
   /// return values: a chain and a flag result.  The inputs are as follows:
   ///   Operand #0  : Input chain.
   ///   Operand #1  : a ExternalSymbolSDNode with a pointer to the asm string.
   ///   Operand #2  : a MDNodeSDNode with the !srcloc metadata.
   ///   Operand #3  : HasSideEffect, IsAlignStack bits.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitFABS(SDNode *N) {
   return SDValue();
 }
 
 SDValue DAGCombiner::visitBRCOND(SDNode *N) {
   SDValue Chain = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue N2 = N->getOperand(2);
 
+  // BRCOND(FREEZE(cond)) is equivalent to BRCOND(cond) (both are
+  // nondeterministic jumps).
+  if (N1->getOpcode() == ISD::FREEZE && N1.hasOneUse()) {
+    return DAG.getNode(ISD::BRCOND, SDLoc(N), MVT::Other, Chain,
+                       N1->getOperand(0), N2);
+  }
+
   // If N is a constant we could fold this into a fallthrough or unconditional
   // branch. However that doesn't happen very often in normal code, because
   // Instcombine/SimplifyCFG should have handled the available opportunities.
   // If we did this folding here, it would be necessary to update the
   // MachineBasicBlock CFG, which is awkward.
 
   // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal
   // on the target.

llvm/test/CodeGen/X86/select-prof-codegen.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
 
-; TODO: Compiling the select should not create 'seta - testb $1 - jump' sequence.
+; Compiling the select should not create 'seta - testb $1 - jump' sequence.
 define i32 @f(i32 %x, i32 %y) {
 ; CHECK-LABEL: f:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    cmpl %esi, %edi
-; CHECK-NEXT:    seta %cl
-; CHECK-NEXT:    testb $1, %cl
-; CHECK-NEXT:    jne .LBB0_2
+; CHECK-NEXT:    ja .LBB0_2
 ; CHECK-NEXT:  # %bb.1: # %select.false
 ; CHECK-NEXT:    movl %esi, %eax
 ; CHECK-NEXT:  .LBB0_2: # %select.end
 ; CHECK-NEXT:    retq
 entry:
   %cmp = icmp ugt i32 %x, %y
   %z = select i1 %cmp, i32 %x, i32 %y, !prof !0
   ret i32 %z
 }
 
 !0 = !{!"branch_weights", i32 1, i32 2000}