This is an archive of the discontinued LLVM Phabricator instance.

Differential D26605

[DAGCombiner] Fix infinite loop in vector mul/shl combining
ClosedPublic

Authored by john.brawn on Nov 14 2016, 6:08 AM.

Details

Reviewers
spatel
RKSimon
bogner
Commits
rG150addb45cb4: [DAGCombiner] Fix infinite loop in vector mul/shl combining
rL287766: [DAGCombiner] Fix infinite loop in vector mul/shl combining
Summary

We have the following DAGCombiner transformations:

(mul (shl X, c1), c2) -> (mul X, c2 << c1)
(mul (shl X, C), Y) -> (shl (mul X, Y), C)
(shl (mul x, c1), c2) -> (mul x, c1 << c2)

Usually the constant shift is optimised by SelectionDAG::getNode when it is constructed, by SelectionDAG::FoldConstantArithmetic, but when we're dealing with vectors and one of those vector constants contains an undef element FoldConstantArithmetic does not fold and we enter an infinite loop.

Fix this by making FoldConstantArithmetic use getNode to decide how to fold each vector element, the same as FoldConstantVectorArithmetic does, and rather than adding the constant shift to the work list instead only apply the transformation if it's already been folded into a constant, as if it's not we're going to loop endlessly. Additionally add missing NoOpaques to one of those transformations, which I noticed when writing the tests for this.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn updated this revision to Diff 77796.Nov 14 2016, 6:08 AM
john.brawn retitled this revision from to [DAGCombiner] Fix infinite loop in vector mul/shl combining.
john.brawn updated this object.
john.brawn added reviewers: RKSimon, bogner, spatel.
john.brawn set the repository for this revision to rL LLVM.
john.brawn added a subscriber: llvm-commits.
RKSimon added inline comments.Nov 14 2016, 6:36 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77796)

asserts need a message : assert(isConstantOrConstantVector(C3) && "Failed to constant fold");

4717 ↗(On Diff #77796)

asserts need a message : assert(isConstantOrConstantVector(Shl) && "Failed to constant fold");

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77796)

I don't think this is safe (e.g. OR(C1, UNDEF) --> at least C1).

john.brawn added inline comments.Nov 14 2016, 7:06 AM
lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77796)

Hmm, I'd thought that FoldConstantVectorArithmetic folds any undef input element into an undef output element, but looking more closely it calls getNode on each element pair and it's only for some operations that results in undef. I'll try making FoldConstantArithmetic do the same.

john.brawn updated this revision to Diff 77826.Nov 14 2016, 9:23 AM
john.brawn updated this object.

Update according to review comments.

RKSimon edited edge metadata.Nov 14 2016, 10:23 AM

Please can we have a diff with context?

john.brawn updated this revision to Diff 77963.Nov 15 2016, 2:38 AM
john.brawn edited edge metadata.

Added context to diff.

RKSimon added inline comments.Nov 15 2016, 5:40 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77963)

I'm worried that maybe instead of asserting for a constant value we should just use an if() - there still might end up being odd cases where the constant fold still fails for some reason. Same for the other case below. What do you think?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77963)

These aren't APInt any more:

// FIXME: This is valid and could be handled by truncation.
john.brawn added inline comments.Nov 16 2016, 10:22 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77963)

Sounds reasonable, I'll update the patch (though not until next week as I'll be on holiday).

john.brawn updated this revision to Diff 79077.Nov 23 2016, 7:31 AM
john.brawn updated this object.

Patch updated according to review comments.

RKSimon accepted this revision.Nov 23 2016, 7:54 AM
RKSimon edited edge metadata.

LGTM

This revision is now accepted and ready to land.Nov 23 2016, 7:54 AM
Closed by commit rL287766: [DAGCombiner] Fix infinite loop in vector mul/shl combining (authored by john.brawn). · Explain WhyNov 23 2016, 8:15 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
CodeGen/
SelectionDAG/
12 lines
21 lines
test/
CodeGen/
AArch64/
117 lines
X86/
6 lines

Diff 79085

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 2,151 Lines • ▼ Show 20 Lines return DAG.getNode(ISD::SUB, DL, VT,
DAG.getConstant(0, DL, VT), DAG.getConstant(0, DL, VT),
DAG.getNode(ISD::SHL, DL, VT, N0, DAG.getNode(ISD::SHL, DL, VT, N0,
DAG.getConstant(Log2Val, DL, DAG.getConstant(Log2Val, DL,
getShiftAmountTy(N0.getValueType())))); getShiftAmountTy(N0.getValueType()))));
} }
// (mul (shl X, c1), c2) -> (mul X, c2 << c1) // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
if (N0.getOpcode() == ISD::SHL && if (N0.getOpcode() == ISD::SHL &&
isConstantOrConstantVector(N1) && isConstantOrConstantVector(N1, /* NoOpaques */ true) &&
isConstantOrConstantVector(N0.getOperand(1))) { isConstantOrConstantVector(N0.getOperand(1), /* NoOpaques */ true)) {
SDValue C3 = DAG.getNode(ISD::SHL, SDLoc(N), VT, N1, N0.getOperand(1)); SDValue C3 = DAG.getNode(ISD::SHL, SDLoc(N), VT, N1, N0.getOperand(1));
AddToWorklist(C3.getNode()); if (isConstantOrConstantVector(C3))
return DAG.getNode(ISD::MUL, SDLoc(N), VT, N0.getOperand(0), C3); return DAG.getNode(ISD::MUL, SDLoc(N), VT, N0.getOperand(0), C3);
} }
// Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
// use. // use.
{ {
SDValue Sh(nullptr, 0), Y(nullptr, 0); SDValue Sh(nullptr, 0), Y(nullptr, 0);
// Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)). // Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)).
▲ Show 20 Lines • Show All 2,536 Lines • ▼ Show 20 Lines if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() &&
return DAG.getNode(ISD::ADD, SDLoc(N), VT, Shl0, Shl1); return DAG.getNode(ISD::ADD, SDLoc(N), VT, Shl0, Shl1);
} }
// fold (shl (mul x, c1), c2) -> (mul x, c1 << c2) // fold (shl (mul x, c1), c2) -> (mul x, c1 << c2)
if (N0.getOpcode() == ISD::MUL && N0.getNode()->hasOneUse() && if (N0.getOpcode() == ISD::MUL && N0.getNode()->hasOneUse() &&
isConstantOrConstantVector(N1, /* No Opaques */ true) && isConstantOrConstantVector(N1, /* No Opaques */ true) &&
isConstantOrConstantVector(N0.getOperand(1), /* No Opaques */ true)) { isConstantOrConstantVector(N0.getOperand(1), /* No Opaques */ true)) {
SDValue Shl = DAG.getNode(ISD::SHL, SDLoc(N1), VT, N0.getOperand(1), N1); SDValue Shl = DAG.getNode(ISD::SHL, SDLoc(N1), VT, N0.getOperand(1), N1);
AddToWorklist(Shl.getNode()); if (isConstantOrConstantVector(Shl))
return DAG.getNode(ISD::MUL, SDLoc(N), VT, N0.getOperand(0), Shl); return DAG.getNode(ISD::MUL, SDLoc(N), VT, N0.getOperand(0), Shl);
} }
if (N1C && !N1C->isOpaque()) if (N1C && !N1C->isOpaque())
if (SDValue NewSHL = visitShiftByConstant(N, N1C)) if (SDValue NewSHL = visitShiftByConstant(N, N1C))
return NewSHL; return NewSHL;
return SDValue(); return SDValue();
} }
▲ Show 20 Lines • Show All 10,736 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 3,492 Lines • ▼ Show 20 LinesSDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL,
if (!BV1 || !BV2) if (!BV1 || !BV2)
return SDValue(); return SDValue();
assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!"); assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
EVT SVT = VT.getScalarType(); EVT SVT = VT.getScalarType();
SmallVector<SDValue, 4> Outputs; SmallVector<SDValue, 4> Outputs;
for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) { for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I)); SDValue V1 = BV1->getOperand(I);
ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I)); SDValue V2 = BV2->getOperand(I);
if (!V1 || !V2) // Not a constant, bail.
return SDValue();
if (V1->isOpaque() || V2->isOpaque())
return SDValue();
// Avoid BUILD_VECTOR nodes that perform implicit truncation. // Avoid BUILD_VECTOR nodes that perform implicit truncation.
// FIXME: This is valid and could be handled by truncating the APInts. // FIXME: This is valid and could be handled by truncation.
if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT) if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
return SDValue(); return SDValue();
// Fold one vector element. // Fold one vector element.
std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(), SDValue ScalarResult = getNode(Opcode, DL, SVT, V1, V2);
V2->getAPIntValue());
if (!Folded.second) // Scalar folding only succeeded if the result is a constant or UNDEF.
if (!ScalarResult.isUndef() && ScalarResult.getOpcode() != ISD::Constant &&
ScalarResult.getOpcode() != ISD::ConstantFP)
return SDValue(); return SDValue();
Outputs.push_back(getConstant(Folded.first, DL, SVT)); Outputs.push_back(ScalarResult);
} }
assert(VT.getVectorNumElements() == Outputs.size() && assert(VT.getVectorNumElements() == Outputs.size() &&
"Vector size mismatch!"); "Vector size mismatch!");
// We may have a vector type but a scalar result. Create a splat. // We may have a vector type but a scalar result. Create a splat.
Outputs.resize(VT.getVectorNumElements(), Outputs.back()); Outputs.resize(VT.getVectorNumElements(), Outputs.back());
▲ Show 20 Lines • Show All 3,918 Lines • Show Last 20 Lines

llvm/trunk/test/CodeGen/AArch64/dag-combine-mul-shl.ll

; RUN: llc -mtriple=aarch64 < %s | FileCheck %s
; CHECK-LABEL: fn1_vector:
; CHECK: adrp x[[BASE:[0-9]+]], .LCP
; CHECK-NEXT: ldr q[[NUM:[0-9]+]], [x[[BASE]],
; CHECK-NEXT: mul v0.16b, v0.16b, v[[NUM]].16b
; CHECK-NEXT: ret
define <16 x i8> @fn1_vector(<16 x i8> %arg) {
entry:
%shl = shl <16 x i8> %arg, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
%mul = mul <16 x i8> %shl, <i8 0, i8 1, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>
ret <16 x i8> %mul
}
; CHECK-LABEL: fn2_vector:
; CHECK: adrp x[[BASE:[0-9]+]], .LCP
; CHECK-NEXT: ldr q[[NUM:[0-9]+]], [x[[BASE]],
; CHECK-NEXT: mul v0.16b, v0.16b, v[[NUM]].16b
; CHECK-NEXT: ret
define <16 x i8> @fn2_vector(<16 x i8> %arg) {
entry:
%mul = mul <16 x i8> %arg, <i8 0, i8 1, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>
%shl = shl <16 x i8> %mul, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
ret <16 x i8> %shl
}
; CHECK-LABEL: fn1_vector_undef:
; CHECK: adrp x[[BASE:[0-9]+]], .LCP
; CHECK-NEXT: ldr q[[NUM:[0-9]+]], [x[[BASE]],
; CHECK-NEXT: mul v0.16b, v0.16b, v[[NUM]].16b
; CHECK-NEXT: ret
define <16 x i8> @fn1_vector_undef(<16 x i8> %arg) {
entry:
%shl = shl <16 x i8> %arg, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
%mul = mul <16 x i8> %shl, <i8 undef, i8 1, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>
ret <16 x i8> %mul
}
; CHECK-LABEL: fn2_vector_undef:
; CHECK: adrp x[[BASE:[0-9]+]], .LCP
; CHECK-NEXT: ldr q[[NUM:[0-9]+]], [x[[BASE]],
; CHECK-NEXT: mul v0.16b, v0.16b, v[[NUM]].16b
; CHECK-NEXT: ret
define <16 x i8> @fn2_vector_undef(<16 x i8> %arg) {
entry:
%mul = mul <16 x i8> %arg, <i8 undef, i8 1, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>
%shl = shl <16 x i8> %mul, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
ret <16 x i8> %shl
}
; CHECK-LABEL: fn1_scalar:
; CHECK: mov w[[REG:[0-9]+]], #1664
; CHECK-NEXT: mul w0, w0, w[[REG]]
; CHECK-NEXT: ret
define i32 @fn1_scalar(i32 %arg) {
entry:
%shl = shl i32 %arg, 7
%mul = mul i32 %shl, 13
ret i32 %mul
}
; CHECK-LABEL: fn2_scalar:
; CHECK: mov w[[REG:[0-9]+]], #1664
; CHECK-NEXT: mul w0, w0, w[[REG]]
; CHECK-NEXT: ret
define i32 @fn2_scalar(i32 %arg) {
entry:
%mul = mul i32 %arg, 13
%shl = shl i32 %mul, 7
ret i32 %shl
}
; CHECK-LABEL: fn1_scalar_undef:
; CHECK: mov w0
; CHECK-NEXT: ret
define i32 @fn1_scalar_undef(i32 %arg) {
entry:
%shl = shl i32 %arg, 7
%mul = mul i32 %shl, undef
ret i32 %mul
}
; CHECK-LABEL: fn2_scalar_undef:
; CHECK: mov w0
; CHECK-NEXT: ret
define i32 @fn2_scalar_undef(i32 %arg) {
entry:
%mul = mul i32 %arg, undef
%shl = shl i32 %mul, 7
ret i32 %shl
}
; CHECK-LABEL: fn1_scalar_opaque:
; CHECK: mov w[[REG:[0-9]+]], #13
; CHECK-NEXT: mul w[[REG]], w0, w[[REG]]
; CHECK-NEXT: lsl w0, w[[REG]], #7
; CHECK-NEXT: ret
define i32 @fn1_scalar_opaque(i32 %arg) {
entry:
%bitcast = bitcast i32 13 to i32
%shl = shl i32 %arg, 7
%mul = mul i32 %shl, %bitcast
ret i32 %mul
}
; CHECK-LABEL: fn2_scalar_opaque:
; CHECK: mov w[[REG:[0-9]+]], #13
; CHECK-NEXT: mul w[[REG]], w0, w[[REG]]
; CHECK-NEXT: lsl w0, w[[REG]], #7
; CHECK-NEXT: ret
define i32 @fn2_scalar_opaque(i32 %arg) {
entry:
%bitcast = bitcast i32 13 to i32
%mul = mul i32 %arg, %bitcast
%shl = shl i32 %mul, 7
ret i32 %shl
}

llvm/trunk/test/CodeGen/X86/shift-pcmp.ll

Show All 20 Lines;
ret <8 x i16> %shl ret <8 x i16> %shl
} }
; Don't fail with an assert due to an undef in the buildvector ; Don't fail with an assert due to an undef in the buildvector
define <8 x i16> @bar(<8 x i16> %a, <8 x i16> %b) { define <8 x i16> @bar(<8 x i16> %a, <8 x i16> %b) {
; SSE-LABEL: bar: ; SSE-LABEL: bar:
; SSE: # BB#0: ; SSE: # BB#0:
; SSE-NEXT: pcmpeqw %xmm1, %xmm0 ; SSE-NEXT: pcmpeqw %xmm1, %xmm0
; SSE-NEXT: psrlw $15, %xmm0 ; SSE-NEXT: pand {{.*}}(%rip), %xmm0
; SSE-NEXT: psllw $5, %xmm0
; SSE-NEXT: retq ; SSE-NEXT: retq
; ;
; AVX-LABEL: bar: ; AVX-LABEL: bar:
; AVX: # BB#0: ; AVX: # BB#0:
; AVX-NEXT: vpcmpeqw %xmm1, %xmm0, %xmm0 ; AVX-NEXT: vpcmpeqw %xmm1, %xmm0, %xmm0
; AVX-NEXT: vpsrlw $15, %xmm0, %xmm0 ; AVX-NEXT: vpand {{.*}}(%rip), %xmm0, %xmm0
; AVX-NEXT: vpsllw $5, %xmm0, %xmm0
; AVX-NEXT: retq ; AVX-NEXT: retq
; ;
%icmp = icmp eq <8 x i16> %a, %b %icmp = icmp eq <8 x i16> %a, %b
%zext = zext <8 x i1> %icmp to <8 x i16> %zext = zext <8 x i1> %icmp to <8 x i16>
%shl = shl nuw nsw <8 x i16> %zext, <i16 5, i16 undef, i16 5, i16 5, i16 5, i16 5, i16 5, i16 5> %shl = shl nuw nsw <8 x i16> %zext, <i16 5, i16 undef, i16 5, i16 5, i16 5, i16 5, i16 5, i16 5>
ret <8 x i16> %shl ret <8 x i16> %shl
} }