DAGCombiner: Continue combining if FoldConstantArithmetic() fails.

[MatzeB]

Summary

DAG.FoldConstantArithmetic() can fail even though both operands are
Constants if OpaqueConstants are involved. Continue trying other combine
possibilities in this case.

[MatzeB]

Is there a way to create a proper llvm-lit test for this? I assume relying on -debug-only=isel in the RUN line is not a good idea.
The test in http://reviews.llvm.org/D6940 works but it is more of an accident that aarch64 fails on non properly combined code...

[ab]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1572

How about:

if (SDValue Folded = ...)
  return Folded;

Or going further, you could remove the N0C && N1C check, since FoldConstantArithmetic also does it (a sliver more wasteful though).

[MatzeB]

Simplify by using condition variables.

[ab]

LGTM.
I'm okay with no test if it's tricky to expose, but maybe we can: what happens now on that AArch64 testcase? Specifically, is there a difference between just this patch, and this patch + the assert fix in D6940?

-Ahmed

[MatzeB]

New version: Turns out if you continue combining in the presence of OpaqueConstants you have to be very carefull to not accidentally fold them into non-Opaque ones during a combine. This patch carefully finds these cases now (I basically looked at all places that create new target constants and checked whether they would be harmfully replace OpaqueConstants with new ones). I did extensive x86 test-suite runs and couldn't find any performance differences.

[MatzeB]

ping

[ab]

Peppering "isOpaque" checks in the remaining combines seems awfully brittle.

Basically, folding to constants isn't OK, but folding to undef is, correct? How about flipping the check then: do all the combines that are valid on Opaque constants first (-> undef), and then bail out if the constant is Opaque but we couldn't do anything.

[MatzeB]

I think the rule here is: "Don't fold opaque constants into another expensive (according to TargetTransformInfo::getIntImmConst) Constant.
It's not a correctness issue but it diminishes the effects of the ConstantHoisting pass.

It is indeed very brittle, but I am not convinced that reordering the optimization rules is the way to go.
There are many other reasons on how the code/checks in a combiner should be order: What makes sense for a human reader or ordering the conditions in a way that the ones that are more likely to fail come first.
Letting a minor detail like Opaque Constants dictate the ordering feels very wrong to me. If we want to push hard to avoid accidentaly transforming OpaqueConstants back to normal ones then the way to go would be not using ISD::Constant for them anymore but to introduce a new opcode, so people need to explicitely check for them before transforming them. In the current design of Opaque being an attribute to ISD::Constant sprinkling the code with isOpaque() is a logical consequence IMO... It's not like drastic things happen we forget some isOpaque() checks anyway, it's not a correctness issue just a minor performance thing.

• Matthias

[MatzeB]

2nd ping

[ab]

Fair enough, reordering the optimizations isn't a solution. Looking through old commits, I see there are a few that do exactly this: add isOpaque checks around DAG combines.
Having a separate node type for opaque constants does sound less brittle; any idea of what would be involved?

-Ahmed

[MatzeB]

That would obviously involve changing all targets to recognize that new node type, in all sorts of different addressing modes. I also don't know whether all of this was already discussed when OpaqueConstants were introduced. Anyway I just wanted to fix a few bugs here and not rewrite all this stuff, so this patch won't get a LGTM unless it's a rewrite of the whole OpaqueConstants concepts?

• Matthias

[ab]

I think there are two parts here:

• checking the return value of FoldConstantArithmetic: that LGTM, though tests would of course be appreciated, if possible.
• disabling some optimizations on Opaque constants: that, I'll let Juergen comment on. I'm opposed to it because of the brittleness, but pragmatically (and there's precedent) that's a reasonable solution.

For your assert failure, I'm fine with just fixing that for now (that would be r230355, correct?).

-Ahmed

[MatzeB]

I can't commit the first part without the second because it leads to the DAGCombiner folding many opaque constants back to normal constants breaking lit tests and generally defeating the intention of ContantHoisting pass.

• Matthias

[MatzeB]

ping

[MatzeB]

ping

[MatzeB]

ping 3

[RKSimon]

Would it be tidier to set the N0C / N1C values to null if they are opaque instead of adding isOpaque() tests everywhere?

[hfinkel]

Can you please upload this patch with full context (see http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface for instructions).

I think the rule here is: "Don't fold opaque constants into another expensive (according to TargetTransformInfo::getIntImmConst) Constant.
It's not a correctness issue but it diminishes the effects of the ConstantHoisting pass.

That does not seem right. Am I right that we only expect isOpaque to be true on TargetConstants, not regular Constants? My understanding is that opaque TargetConstants are a correctness issue (it is not really a cost issue, but rather that sometimes we can't change the constant because it has a special meaning, a larger constant might not be representable for that operation (like the offset on an indexed load or store), etc.).

FWIW, I feel like our current handling of isOpaque is laughably sparse, and we should either complete the job (by auditing, as you've done), or rip it out. Perhaps instead we should just consider all TargetConstants opaque.

That having been said, I'd like to add some additional safety here. Such as, in ConstantSDNode:

const ConstantInt *getConstantIntValue() const { return Value; }

should become:

const ConstantInt *getConstantIntValue(bool allowOpaque = false) const {
  assert((allowOpaque || !isOpaque()) && "Invalid access to opaque value");
  return Value;
}

and likewise for the other interfaces. This way, by default, you can't even get an opaque value's numeric representation.

[MatzeB]

In D6946#174531, @hfinkel wrote:

Can you please upload this patch with full context (see http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface for instructions).

I think the rule here is: "Don't fold opaque constants into another expensive (according to TargetTransformInfo::getIntImmConst) Constant.
It's not a correctness issue but it diminishes the effects of the ConstantHoisting pass.

That does not seem right. Am I right that we only expect isOpaque to be true on TargetConstants, not regular Constants? My understanding is that opaque TargetConstants are a correctness issue (it is not really a cost issue, but rather that sometimes we can't change the constant because it has a special meaning, a larger constant might not be representable for that operation (like the offset on an indexed load or store), etc.).

No, isOpaque is not about TargetConstants but normal ConstantSDNodes which are equivalent to IR Constants. Opaque constants are created in IR by Transforms/Scalar/ConstantHoisting.cpp with the convention that a Constant that is immediately bitcasted to the same type is an opaque constant. The trick here is not to undo the work from that pass while at the same time folding as much as possible...

[hfinkel]

In D6946#174583, @MatzeB wrote:

In D6946#174531, @hfinkel wrote:

Can you please upload this patch with full context (see http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface for instructions).

I think the rule here is: "Don't fold opaque constants into another expensive (according to TargetTransformInfo::getIntImmConst) Constant.
It's not a correctness issue but it diminishes the effects of the ConstantHoisting pass.

That does not seem right. Am I right that we only expect isOpaque to be true on TargetConstants, not regular Constants? My understanding is that opaque TargetConstants are a correctness issue (it is not really a cost issue, but rather that sometimes we can't change the constant because it has a special meaning, a larger constant might not be representable for that operation (like the offset on an indexed load or store), etc.).

No, isOpaque is not about TargetConstants but normal ConstantSDNodes which are equivalent to IR Constants. Opaque constants are created in IR by Transforms/Scalar/ConstantHoisting.cpp with the convention that a Constant that is immediately bitcasted to the same type is an opaque constant. The trick here is not to undo the work from that pass while at the same time folding as much as possible...

Ah, indeed. Shouldn't the rule be: Don't fold an opaque constant into another constant unless he result is cheap or free (in the getIntImmConst sense)?

[MatzeB]

Ah, indeed. Shouldn't the rule be: Don't fold an opaque constant into another constant unless he result is cheap or free (in the getIntImmConst sense)?

Yes. In fact I did not bother to guard a few combines that produce a zero result, though admittedly the code does not check whether zero is an expensive constant - but I can't imagine that to be the case on any target.

Anyway I'm currently adapting the patch to ToT and will try out RKSimons suggestion which will probably simplify this a lot.

[MatzeB]

New revision adapted to ToT and with many explicite isOpaque() checks avoided by introducing a cast operation that returns nullptr if a node is a non-opaque constant.

[hfinkel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1548

Our general convention seems to be to name functions like this 'getAs<Name>', not 'as<Name>', so I think getAsNonOpaqueConstant would be better.

Otherwise, LGTM.

[MatzeB]

This landed in r237822. Closing manually as "Differential Revision: XXX" was not the last line of the commit message.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
       DAG.ReplaceAllUsesOfValueWith(SDValue(N, i), N->getOperand(i));
   } while (!N->use_empty());
   deleteAndRecombine(N);
   return SDValue(N, 0);   // Return N so it doesn't get rechecked!
 }
 
 SDValue DAGCombiner::visitADD(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
   EVT VT = N0.getValueType();
 
   // fold vector ops
   if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
 
     // fold (add x, 0) -> x, vector edition
     if (ISD::isBuildVectorAllZeros(N1.getNode()))
       return N0;
     if (ISD::isBuildVectorAllZeros(N0.getNode()))
       return N1;
   }
 
   // fold (add x, undef) -> undef
   if (N0.getOpcode() == ISD::UNDEF)
     return N0;
   if (N1.getOpcode() == ISD::UNDEF)
     return N1;
   // fold (add c1, c2) -> c1+c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::ADD, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::ADD, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // canonicalize constant to RHS
   if (N0C && !N1C)
     return DAG.getNode(ISD::ADD, SDLoc(N), VT, N1, N0);
   // fold (add x, 0) -> x
   if (N1C && N1C->isNullValue())
     return N0;
   // fold (add Sym, c) -> Sym+c
   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
if (ISD::isBuildVectorAllZeros(N1.getNode()))
       return N0;
   }
 
   // fold (sub x, x) -> 0
   // FIXME: Refactor this and xor and other similar operations together.
   if (N0 == N1)
     return tryFoldToZero(SDLoc(N), TLI, VT, DAG, LegalOperations, LegalTypes);
   // fold (sub c1, c2) -> c1-c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::SUB, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SUB, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (sub x, c) -> (add x, -c)
   if (N1C)
     return DAG.getNode(ISD::ADD, SDLoc(N), VT, N0,
                        DAG.getConstant(-N1C->getAPIntValue(), VT));
   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
   if (N0C && N0C->isAllOnesValue())
     return DAG.getNode(ISD::XOR, SDLoc(N), VT, N1, N0);
   // fold A-(A-B) -> B
if (VT.isVector()) {
     ConstValue0 = N0IsConst ? (dyn_cast<ConstantSDNode>(N0))->getAPIntValue()
                             : APInt();
     N1IsConst = dyn_cast<ConstantSDNode>(N1) != nullptr;
     ConstValue1 = N1IsConst ? (dyn_cast<ConstantSDNode>(N1))->getAPIntValue()
                             : APInt();
   }
 
   // fold (mul c1, c2) -> c1*c2
-  if (N0IsConst && N1IsConst)
-    return DAG.FoldConstantArithmetic(ISD::MUL, VT, N0.getNode(), N1.getNode());
+  if (N0IsConst && N1IsConst) {
+    SDValue Folded =
+        DAG.FoldConstantArithmetic(ISD::MUL, VT, N0.getNode(), N1.getNode());
+    if (Folded.getNode())
+      return Folded;
+  }
 
   // canonicalize constant to RHS
   if (N0IsConst && !N1IsConst)
     return DAG.getNode(ISD::MUL, SDLoc(N), VT, N1, N0);
   // fold (mul x, 0) -> 0
   if (N1IsConst && ConstValue1 == 0)
     return N1;
   // We require a splat of the entire scalar bit width for non-contiguous
SDValue DAGCombiner::visitSDIV(SDNode *N) {
 
   // fold vector ops
   if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
   }
 
   // fold (sdiv c1, c2) -> c1/c2
-  if (N0C && N1C && !N1C->isNullValue())
-    return DAG.FoldConstantArithmetic(ISD::SDIV, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SDIV, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (sdiv X, 1) -> X
   if (N1C && N1C->getAPIntValue() == 1LL)
     return N0;
   // fold (sdiv X, -1) -> 0-X
   if (N1C && N1C->isAllOnesValue())
     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
                        DAG.getConstant(0, VT), N0);
   // If we know the sign bits of both operands are zero, strength reduce to a
SDValue DAGCombiner::visitUDIV(SDNode *N) {
 
   // fold vector ops
   if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
   }
 
   // fold (udiv c1, c2) -> c1/c2
-  if (N0C && N1C && !N1C->isNullValue())
-    return DAG.FoldConstantArithmetic(ISD::UDIV, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::UDIV, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (udiv x, (1 << c)) -> x >>u c
   if (N1C && N1C->getAPIntValue().isPowerOf2())
     return DAG.getNode(ISD::SRL, SDLoc(N), VT, N0,
                        DAG.getConstant(N1C->getAPIntValue().logBase2(),
                                        getShiftAmountTy(N0.getValueType())));
   // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
   if (N1.getOpcode() == ISD::SHL) {
     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {

 SDValue DAGCombiner::visitSREM(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   ConstantSDNode *N0C = isConstOrConstSplat(N0);
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   EVT VT = N->getValueType(0);
 
   // fold (srem c1, c2) -> c1%c2
-  if (N0C && N1C && !N1C->isNullValue())
-    return DAG.FoldConstantArithmetic(ISD::SREM, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SREM, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // If we know the sign bits of both operands are zero, strength reduce to a
   // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
   if (!VT.isVector()) {
     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
       return DAG.getNode(ISD::UREM, SDLoc(N), VT, N0, N1);
   }
 
   // If X/C can be simplified by the division-by-constant logic, lower

 SDValue DAGCombiner::visitUREM(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   ConstantSDNode *N0C = isConstOrConstSplat(N0);
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   EVT VT = N->getValueType(0);
 
   // fold (urem c1, c2) -> c1%c2
-  if (N0C && N1C && !N1C->isNullValue())
-    return DAG.FoldConstantArithmetic(ISD::UREM, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::UREM, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (urem x, pow2) -> (and x, pow2-1)
   if (N1C && !N1C->isNullValue() && N1C->getAPIntValue().isPowerOf2())
     return DAG.getNode(ISD::AND, SDLoc(N), VT, N0,
-                       DAG.getConstant(N1C->getAPIntValue()-1,VT));
+                       DAG.getConstant(N1C->getAPIntValue() - 1, VT));
   // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
   if (N1.getOpcode() == ISD::SHL) {
     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
       if (SHC->getAPIntValue().isPowerOf2()) {
         SDValue Add =
           DAG.getNode(ISD::ADD, SDLoc(N), VT, N1,
                  DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()),
                                  VT));
if (VT.isVector()) {
     if (ISD::isBuildVectorAllOnes(N1.getNode()))
       return N0;
   }
 
   // fold (and x, undef) -> 0
   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
     return DAG.getConstant(0, VT);
   // fold (and c1, c2) -> c1&c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::AND, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::AND, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // canonicalize constant to RHS
   if (N0C && !N1C)
     return DAG.getNode(ISD::AND, SDLoc(N), VT, N1, N0);
   // fold (and x, -1) -> x
   if (N1C && N1C->isAllOnesValue())
     return N0;
   // if (and x, c) is known to be zero, return 0
   if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
SDValue DAGCombiner::visitOR(SDNode *N) {
 
   // fold (or x, undef) -> -1
   if (!LegalOperations &&
       (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)) {
     EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
     return DAG.getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
   }
   // fold (or c1, c2) -> c1|c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::OR, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::OR, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // canonicalize constant to RHS
   if (N0C && !N1C)
     return DAG.getNode(ISD::OR, SDLoc(N), VT, N1, N0);
   // fold (or x, 0) -> x
   if (N1C && N1C->isNullValue())
     return N0;
   // fold (or x, -1) -> -1
   if (N1C && N1C->isAllOnesValue())
SDValue DAGCombiner::visitXOR(SDNode *N) {
   if (N0.getOpcode() == ISD::UNDEF && N1.getOpcode() == ISD::UNDEF)
     return DAG.getConstant(0, VT);
   // fold (xor x, undef) -> undef
   if (N0.getOpcode() == ISD::UNDEF)
     return N0;
   if (N1.getOpcode() == ISD::UNDEF)
     return N1;
   // fold (xor c1, c2) -> c1^c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::XOR, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::XOR, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // canonicalize constant to RHS
   if (N0C && !N1C)
     return DAG.getNode(ISD::XOR, SDLoc(N), VT, N1, N0);
   // fold (xor x, 0) -> x
   if (N1C && N1C->isNullValue())
     return N0;
   // reassociate xor
   SDValue RXOR = ReassociateOps(ISD::XOR, SDLoc(N), N0, N1);
if (N1CV && N1CV->isConstant()) {
         }
       } else {
         N1C = isConstOrConstSplat(N1);
       }
     }
   }
 
   // fold (shl c1, c2) -> c1<<c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::SHL, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SHL, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (shl 0, x) -> 0
   if (N0C && N0C->isNullValue())
     return N0;
   // fold (shl x, c >= size(x)) -> undef
   if (N1C && N1C->getZExtValue() >= OpSizeInBits)
     return DAG.getUNDEF(VT);
   // fold (shl x, 0) -> x
   if (N1C && N1C->isNullValue())
SDValue DAGCombiner::visitSRA(SDNode *N) {
   if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
 
     N1C = isConstOrConstSplat(N1);
   }
 
   // fold (sra c1, c2) -> (sra c1, c2)
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::SRA, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SRA, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (sra 0, x) -> 0
   if (N0C && N0C->isNullValue())
     return N0;
   // fold (sra -1, x) -> -1
   if (N0C && N0C->isAllOnesValue())
     return N0;
   // fold (sra x, (setge c, size(x))) -> undef
   if (N1C && N1C->getZExtValue() >= OpSizeInBits)
SDValue DAGCombiner::visitSRL(SDNode *N) {
   if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
 
     N1C = isConstOrConstSplat(N1);
   }
 
   // fold (srl c1, c2) -> c1 >>u c2
-  if (N0C && N1C)
-    return DAG.FoldConstantArithmetic(ISD::SRL, VT, N0C, N1C);
+  if (N0C && N1C) {
+    SDValue Folded = DAG.FoldConstantArithmetic(ISD::SRL, VT, N0C, N1C);
+    if (Folded.getNode())
+      return Folded;
+  }
   // fold (srl 0, x) -> 0
   if (N0C && N0C->isNullValue())
     return N0;
   // fold (srl x, c >= size(x)) -> undef
   if (N1C && N1C->getZExtValue() >= OpSizeInBits)
     return DAG.getUNDEF(VT);
   // fold (srl x, 0) -> x
   if (N1C && N1C->isNullValue())