[X86] Prevent infinite loop in SelectionDAG when lowering negations

[momo5502]

Summary

In certain cases, lowering negations can cause an infinite loop in SelectionDAG on X86.

The following snippet shows that behaviour:
https://godbolt.org/z/5hP45T4hY

What happens is that ADD(XOR(..., -1), 1) is detected as the two's complement and transformed into SUB(0, ...)
However, immediates can not be encoded as the LHS of a SUB on X86.
Therefore it is transformed back into an ADD/XOR pair, which is then again transformed into a SUB and so on.

In that specific case, I still think it is valid to display this as a SUB(0,...) , because it should eventually be lowered as a NEG.
Which seems better than an ADD/XOR pair.

Adding an exception to the X86 specific handling for SUBs with 0 LHS operand fixes this infinite loop.

[RKSimon]

llvm/test/CodeGen/X86/select-neg.ll

17

Can this not be reduced any further?

[momo5502]

llvm/test/CodeGen/X86/select-neg.ll

17

I'm afraid not. The ADD and the first XOR are needed for sure.
I think the second XOR and the PtrToInt is needed as that bug only gets triggered due to a reassociation step that switches the two XORs.

SelectionDAG loops between 3 states:

1. SUB -> ADD
2. XOR reassociation
3. ADD -> SUB

I was not able to trigger the infinte loop without ressociation step inbetween and I was not able to trigger that reassociation without the PtrToInt.

However, I extracted and reduced that bug from a 1.5k line LL file, so I was pretty happy with a 5 instruction sample :D

[RKSimon]

cheers - lgtm

[momo5502]

In D154575#4476804, @RKSimon wrote:

cheers - lgtm

Thank you very much. I don't have commit permissions. Can you please commit for me using the following details:
Maurice Heumann <[e-mail]>

[momo5502]

Is there anything missing for this to be committed?

[RKSimon]

Sorry @momo5502 I just missed this..... Will get it pushed later today

llvm/lib/Target/X86/X86ISelLowering.cpp

if (SDNode *C = DAG.isConstantIntBuildVectorOrConstantInt(Op)) {
       return true;
     }
     return false;
   };
 
   // X86 can't encode an immediate LHS of a sub. See if we can push the
   // negation into a preceding instruction. If the RHS of the sub is a XOR with
   // one use and a constant, invert the immediate, saving one register.
+  // However, ignore cases where C1 is 0, as those will become a NEG.
   // sub(C1, xor(X, C2)) -> add(xor(X, ~C2), C1+1)
   if (Op1.getOpcode() == ISD::XOR && IsNonOpaqueConstant(Op0) &&
-      IsNonOpaqueConstant(Op1.getOperand(1)) && Op1->hasOneUse()) {
+      !isNullConstant(Op0) && IsNonOpaqueConstant(Op1.getOperand(1)) &&
+      Op1->hasOneUse()) {
     SDLoc DL(N);
     EVT VT = Op0.getValueType();
     SDValue NewXor = DAG.getNode(ISD::XOR, SDLoc(Op1), VT, Op1.getOperand(0),
                                  DAG.getNOT(SDLoc(Op1), Op1.getOperand(1), VT));
     SDValue NewAdd =
         DAG.getNode(ISD::ADD, DL, VT, Op0, DAG.getConstant(1, DL, VT));
     return DAG.getNode(ISD::ADD, DL, VT, NewXor, NewAdd);
   }

llvm/test/CodeGen/X86/select-neg.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=i386-unknown-unknown | FileCheck %s
+
+@value1 = external hidden constant i32
+
+define i32 @function(i32 %arg1) {
+; CHECK-LABEL: function:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movl $value1, %eax
+; CHECK-NEXT:    xorl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    negl %eax
+; CHECK-NEXT:    retl
+entry:
+  %0 = xor i32 %arg1, xor (i32 ptrtoint (i32* @value1 to i32), i32 -1)
+  %.neg = add i32 %0, 1
+  ret i32 %.neg
+}