[DAGCombiner] Fold SETCC(FREEZE(x),const) to FREEZE(SETCC(x,const)) if SETCC is used by BRCOND

[aqjune]

Summary

This patch adds a peephole optimization SETCC(FREEZE(x),const) => FREEZE(SETCC(x,const))
if the SETCC is only used by BRCOND.

Combined with BRCOND(FREEZE(X)) => BRCOND(X), this leads to a nice improvement in the generated assembly when x is a masked loaded value.

[aqjune]

Found while investigating the impact of D104569.

[aqjune]

clang-format

[nikic]

Might it make sense to consider this as a fold on freeze, which walks a chain of one-use instructions down to a brcond? That would make it easier to generalize for looking through other instructions.

[aqjune]

In D105344#2855925, @nikic wrote:

Might it make sense to consider this as a fold on freeze, which walks a chain of one-use instructions down to a brcond? That would make it easier to generalize for looking through other instructions.

Yep, it makes sense; will do that.

[aqjune]

Update a comment

[aqjune]

In D105344#2856825, @aqjune wrote:

In D105344#2855925, @nikic wrote:

Might it make sense to consider this as a fold on freeze, which walks a chain of one-use instructions down to a brcond? That would make it easier to generalize for looking through other instructions.

Yep, it makes sense; will do that.

Well, I wanted to write a generalized worklist algorithm that traverses one-use operands from BRCOND and folds freeze if possible, but it seems SDNode is an immutable data structure?
I couldn't find setOperand()-like function from SDNode.

[aqjune]

Rebase

[aqjune]

This optimization seems still helpful after D105392 is landed.
Should we generalize this transform and optimize away all freezes used by BRCOND? This will need an introduction of a new helper function that is analogous to canCreateUndefOrPoison.

[nikic]

In D105344#2869740, @aqjune wrote:

This optimization seems still helpful after D105392 is landed.
Should we generalize this transform and optimize away all freezes used by BRCOND? This will need an introduction of a new helper function that is analogous to canCreateUndefOrPoison.

Hm, why do we need canCreateUndefOrPoison()? TBH I'm not quite sure when exactly doing this is valid. Let me think out load. Using a freeze instruction can only be necessary if either

• It is used multiple times (or a recursive user is used multiple times). In this case freeze makes sure that the same value is seen by all users.
• It is used in an instruction where undef/poison are immediate UB. In this case freeze launders UB.

On the IR level this covers pretty much all uses, because we either have additional uses we don't see (function return/arg, store value) or the operand is UB on undef (branch, pointer operand). On the DAG level the issue with additional uses remains (store value, CopyToReg) but the UB on undef problem mostly goes away. At least we define BRCOND on undef as not UB -- I don't know about load/store addresses.

So basically it's okay to drop freeze if we can walk a one-use chain down to a "sink" instruction that both doesn't have implicit uses and does not have UB on undef. One such sink is BRCOND. Whether instructions along the way can produce poison shouldn't matter.

All that said, handling this fully generically is probably not simple, but writing it in a way that allows adding ISD opcodes to a whitelist as needed would probably still be nice.

[aqjune]

In D105344#2872095, @nikic wrote:

In D105344#2869740, @aqjune wrote:

This optimization seems still helpful after D105392 is landed.
Should we generalize this transform and optimize away all freezes used by BRCOND? This will need an introduction of a new helper function that is analogous to canCreateUndefOrPoison.

Hm, why do we need canCreateUndefOrPoison()?

It's because pushing freeze forward doesn't hold for certain poison-generating operations like mul nsw:
https://alive2.llvm.org/ce/z/boohtf
Actually, it depends on operations: add nsw is fine because add nsw x, 0 is simply equivalent to x and add nsw x, y for any non-zero y there exists x that makes the result overflow.
Didn't think enough in which case the transformation is correct in general, yet.

TBH I'm not quite sure when exactly doing this is valid. Let me think out load. Using a freeze instruction can only be necessary if either

• It is used multiple times (or a recursive user is used multiple times). In this case freeze makes sure that the same value is seen by all users.
• It is used in an instruction where undef/poison are immediate UB. In this case freeze launders UB.

On the IR level this covers pretty much all uses, because we either have additional uses we don't see (function return/arg, store value) or the operand is UB on undef (branch, pointer operand). On the DAG level the issue with additional uses remains (store value, CopyToReg) but the UB on undef problem mostly goes away. At least we define BRCOND on undef as not UB -- I don't know about load/store addresses.

So basically it's okay to drop freeze if we can walk a one-use chain down to a "sink" instruction that both doesn't have implicit uses and does not have UB on undef. One such sink is BRCOND. Whether instructions along the way can produce poison shouldn't matter.

All that said, handling this fully generically is probably not simple, but writing it in a way that allows adding ISD opcodes to a whitelist as needed would probably still be nice.

I think splitting the transformation into smaller steps would be easier.
For some op1 and op2, folding op2(op1(FREEZE(x),y)) => op2(op1(x,y)) can be broken down into three steps:

  %z = op1(FREEZE(x), y)
  op2(%z)
=> // step 1
  %z = op1(FREEZE(x), FREEZE(y))
  op2(%z)
=> // step 2
  %z = op1(x, y)
  %z.fr = FREEZE(%z)
  op2(%z.fr)
=> // step 3
  %z = op1(x, y)
  op2(%z)

Step 1 is trivially correct.

Step 2: Relying on canCreateUndefOrPoison makes checking this step simpler, maybe?

Step 3: Optimizing freeze away is correct if the result of op2 on undef/poison is equivalent to op2 on some random number. In this case, op2 is BRCOND, and BRCOND(undef) is equivalent to BRCOND(0) or BRCOND(1), so this holds.
This property doesn't hold for e.g. mul; mul undef, 2 returns a set of even numbers, whereas mul n, 2 for any n is a single even number.

That being said, I'm fine with the current patch - it still allows optimizing the setcc-freeze.ll example.

[aqjune]

  %z = op1(FREEZE(x), y)
  op2(%z)
=> // step 1
  %z = op1(FREEZE(x), FREEZE(y))
  op2(%z)
=> // step 2
  %z = op1(x, y)
  %z.fr = FREEZE(%z)
  op2(%z.fr)
=> // step 3
  %z = op1(x, y)
  op2(%z)

Step 2: Relying on canCreateUndefOrPoison makes checking this step simpler, maybe?

I found that canCreateUndefOrPoison isn't enough. A non-poison-generating operation can be problematic as well.
Look at this example: https://alive2.llvm.org/ce/z/xGDGHF

    %n.fr = freeze i8 %n           // Assume that %n = poison
    %m.fr = freeze i8 %m           // Assume that %m = -128
    %v = icmp slt i8 %n.fr, %m.fr  // This is always false, but...
=>
    %v = icmp slt i8 %n, %m        // This is poison, so
    %v.fr = freeze i1 %v           // This (freeze poison) can be true.
    ret i1 %v.fr

So, even in SETCC (which is analogous to icmp) pushing freeze should have been carefully done.

Fortunately, we only need to deal with one operand being constant, so this can be checked in advance.

[nikic]

@aqjune That's a great point. So we need to limit the transform to having a constant operand and showing that the constant operand does not imply always-true/always-false setcc?

[aqjune]

Yes, I think so. Will update this patch tmr.

[aqjune]

Enable SETCC folding only when it holds the discussed constraint

[aqjune]

This patch is fixed to deal with pulling out FREEZE from SETCC only. The removal of FREEZE is delegated to visitBRCOND's simplification.

llvm/test/CodeGen/X86/setcc-freeze.ll

31

These suboptimal codes were being generated even if %cond was not frozen as well.

[aqjune]

ping

[efriedma]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10233

Maybe worth calling out the one-use constraint in this comment?

10243

I don't think the IsIntComparison check does anything. The cod codes are shared between int and fp ops. The way to check if you have an integer comparison is just to check the types of the operands... which you're implicitly doing by casting to ConstantSDNode.

[aqjune]

Remove int predicate check, update a comment

[aqjune]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10243

Didn't realize that ConstantSDNode only has an integer, thanks.

[efriedma]

LGTM

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) {
     return Value->getLimitedValue(Limit);
   }
   MaybeAlign getMaybeAlignValue() const { return Value->getMaybeAlignValue(); }
   Align getAlignValue() const { return Value->getAlignValue(); }
 
   bool isOne() const { return Value->isOne(); }
   bool isNullValue() const { return Value->isZero(); }
   bool isAllOnesValue() const { return Value->isMinusOne(); }
+  bool isMaxSignedValue() const { return Value->isMaxValue(true); }
+  bool isMinSignedValue() const { return Value->isMinValue(true); }
 
   bool isOpaque() const { return ConstantSDNodeBits.IsOpaque; }
 
   static bool classof(const SDNode *N) {
     return N->getOpcode() == ISD::Constant ||
            N->getOpcode() == ISD::TargetConstant;
   }
 };

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 
 SDValue DAGCombiner::visitSETCC(SDNode *N) {
   // setcc is very commonly used as an argument to brcond. This pattern
   // also lend itself to numerous combines and, as a result, it is desired
   // we keep the argument to a brcond as a setcc as much as possible.
   bool PreferSetCC =
       N->hasOneUse() && N->use_begin()->getOpcode() == ISD::BRCOND;
 
-  SDValue Combined = SimplifySetCC(
-      N->getValueType(0), N->getOperand(0), N->getOperand(1),
-      cast<CondCodeSDNode>(N->getOperand(2))->get(), SDLoc(N), !PreferSetCC);
+  ISD::CondCode Cond = cast<CondCodeSDNode>(N->getOperand(2))->get();
+  EVT VT = N->getValueType(0);
+
+  //   SETCC(FREEZE(X), CONST, Cond)
+  // =>
+  //   FREEZE(SETCC(X, CONST, Cond))
+  // This is correct if FREEZE(X) has one use and SETCC(FREEZE(X), CONST, Cond)
+  // isn't equivalent to true or false.
+  // For example, SETCC(FREEZE(X), -128, SETULT) cannot be folded to
+  // FREEZE(SETCC(X, -128, SETULT)) because X can be poison.
+  //
+  // This transformation is beneficial because visitBRCOND can fold
+  // BRCOND(FREEZE(X)) to BRCOND(X).
+
+  // Conservatively optimize integer comparisons only.
+  if (PreferSetCC) {
+    // Do this only when SETCC is going to be used by BRCOND.
+
+    SDValue N0 = N->getOperand(0), N1 = N->getOperand(1);
+    ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
+    ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+    bool Updated = false;
+
+    // Is 'X Cond C' always true or false?
+    auto IsAlwaysTrueOrFalse = [](ISD::CondCode Cond, ConstantSDNode *C) {
+      bool False = (Cond == ISD::SETULT && C->isNullValue()) ||
+                   (Cond == ISD::SETLT  && C->isMinSignedValue()) ||
+                   (Cond == ISD::SETUGT && C->isAllOnesValue()) ||
+                   (Cond == ISD::SETGT  && C->isMaxSignedValue());
+      bool True =  (Cond == ISD::SETULE && C->isAllOnesValue()) ||
+                   (Cond == ISD::SETLE  && C->isMaxSignedValue()) ||
+                   (Cond == ISD::SETUGE && C->isNullValue()) ||
+                   (Cond == ISD::SETGE  && C->isMinSignedValue());
+      return True || False;
+    };
+
+    if (N0->getOpcode() == ISD::FREEZE && N0.hasOneUse() && N1C) {
+      if (!IsAlwaysTrueOrFalse(Cond, N1C)) {
+        N0 = N0->getOperand(0);
+        Updated = true;
+      }
+    }
+    if (N1->getOpcode() == ISD::FREEZE && N1.hasOneUse() && N0C) {
+      if (!IsAlwaysTrueOrFalse(ISD::getSetCCSwappedOperands(Cond),
+                               N0C)) {
+        N1 = N1->getOperand(0);
+        Updated = true;
+      }
+    }
+
+    if (Updated)
+      return DAG.getFreeze(DAG.getSetCC(SDLoc(N), VT, N0, N1, Cond));
+  }
+
+  SDValue Combined = SimplifySetCC(VT, N->getOperand(0), N->getOperand(1), Cond,
+                                   SDLoc(N), !PreferSetCC);
 
   if (!Combined)
     return SDValue();
 
   // If we prefer to have a setcc, and we don't, we'll try our best to
   // recreate one using rebuildSetCC.
   if (PreferSetCC && Combined.getOpcode() != ISD::SETCC) {
     SDValue NewSetCC = rebuildSetCC(Combined);

llvm/test/CodeGen/X86/setcc-freeze.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu < %s 2>&1 | FileCheck %s
 
 define i32 @f(i16* %p) {
 ; CHECK-LABEL: f:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movzwl (%rdi), %eax
-; CHECK-NEXT:    andl $2048, %eax # imm = 0x800
-; CHECK-NEXT:    testw %ax, %ax
+; CHECK-NEXT:    testb $8, 1(%rdi)
 ; CHECK-NEXT:    je .LBB0_1
 ; CHECK-NEXT:  # %bb.2: # %B
 ; CHECK-NEXT:    movl $20, %eax
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_1: # %A
 ; CHECK-NEXT:    movl $10, %eax
 ; CHECK-NEXT:    retq
   %v = load i16, i16* %p, align 2
   %and = and i16 %v, 2048
   %cond = icmp eq i16 %and, 0
   %cond.fr = freeze i1 %cond
   br i1 %cond.fr, label %A, label %B
 A:
   ret i32 10
 B:
   ret i32 20
 }
 
 define i32 @f_false(i16* %p) {
 ; CHECK-LABEL: f_false:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movb $1, %al
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB1_2
 ; CHECK-NEXT:  # %bb.1: # %A
 ; CHECK-NEXT:    movl $10, %eax
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB1_2: # %B
 ; CHECK-NEXT:    movl $20, %eax
 ; CHECK-NEXT:    retq
   %v = load i16, i16* %p, align 2
   %and = and i16 %v, 2048