Skip to content

Commit 9293865

Browse files
rotaterightrotateright
committedMar 1, 2017
[DAGCombiner] fold binops with constant into select-of-constants
This is part of the ongoing attempt to improve select codegen for all targets and select canonicalization in IR (see D24480 for more background). The transform is a subset of what is done in InstCombine's FoldOpIntoSelect(). I first noticed a regression in the x86 avx512-insert-extract.ll tests with a patch that hopes to convert more selects to basic math ops. This appears to be a general missing DAG transform though, so I added tests for all standard binops in rL296621 (PowerPC was chosen semi-randomly; it has scripted FileCheck support, but so do ARM and x86). The poor output for "sel_constants_shl_constant" is tracked with: https://bugs.llvm.org/show_bug.cgi?id=32105 Differential Revision: https://reviews.llvm.org/D30502 llvm-svn: 296699
1 parent d80b69f commit 9293865

File tree

7 files changed

+346
-335
lines changed

7 files changed

+346
-335
lines changed
 

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

+112
Original file line numberDiff line numberDiff line change
@@ -337,6 +337,7 @@ namespace {
337337
SDValue visitShiftByConstant(SDNode *N, ConstantSDNode *Amt);
338338

339339
SDValue foldSelectOfConstants(SDNode *N);
340+
SDValue foldBinOpIntoSelect(SDNode *BO);
340341
bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
341342
SDValue SimplifyBinOpWithSameOpcodeHands(SDNode *N);
342343
SDValue SimplifySelect(const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2);
@@ -1747,6 +1748,59 @@ static ConstantSDNode *getAsNonOpaqueConstant(SDValue N) {
17471748
return Const != nullptr && !Const->isOpaque() ? Const : nullptr;
17481749
}
17491750

1751+
SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
1752+
auto BinOpcode = BO->getOpcode();
1753+
assert((BinOpcode == ISD::ADD || BinOpcode == ISD::SUB ||
1754+
BinOpcode == ISD::MUL || BinOpcode == ISD::SDIV ||
1755+
BinOpcode == ISD::UDIV || BinOpcode == ISD::SREM ||
1756+
BinOpcode == ISD::UREM || BinOpcode == ISD::AND ||
1757+
BinOpcode == ISD::OR || BinOpcode == ISD::XOR ||
1758+
BinOpcode == ISD::SHL || BinOpcode == ISD::SRL ||
1759+
BinOpcode == ISD::SRA || BinOpcode == ISD::FADD ||
1760+
BinOpcode == ISD::FSUB || BinOpcode == ISD::FMUL ||
1761+
BinOpcode == ISD::FDIV || BinOpcode == ISD::FREM) &&
1762+
"Unexpected binary operator");
1763+
1764+
SDValue C1 = BO->getOperand(1);
1765+
if (!isConstantOrConstantVector(C1) &&
1766+
!isConstantFPBuildVectorOrConstantFP(C1))
1767+
return SDValue();
1768+
1769+
// Don't do this unless the old select is going away. We want to eliminate the
1770+
// binary operator, not replace a binop with a select.
1771+
// TODO: Handle ISD::SELECT_CC.
1772+
SDValue Sel = BO->getOperand(0);
1773+
if (Sel.getOpcode() != ISD::SELECT || !Sel.hasOneUse())
1774+
return SDValue();
1775+
1776+
SDValue CT = Sel.getOperand(1);
1777+
if (!isConstantOrConstantVector(CT) &&
1778+
!isConstantFPBuildVectorOrConstantFP(CT))
1779+
return SDValue();
1780+
1781+
SDValue CF = Sel.getOperand(2);
1782+
if (!isConstantOrConstantVector(CF) &&
1783+
!isConstantFPBuildVectorOrConstantFP(CF))
1784+
return SDValue();
1785+
1786+
// We have a select-of-constants followed by a binary operator with a
1787+
// constant. Eliminate the binop by pulling the constant math into the select.
1788+
// Example: add (select Cond, CT, CF), C1 --> select Cond, CT + C1, CF + C1
1789+
EVT VT = Sel.getValueType();
1790+
SDLoc DL(Sel);
1791+
SDValue NewCT = DAG.getNode(BinOpcode, DL, VT, CT, C1);
1792+
assert((isConstantOrConstantVector(NewCT) ||
1793+
isConstantFPBuildVectorOrConstantFP(NewCT)) &&
1794+
"Failed to constant fold a binop with constant operands");
1795+
1796+
SDValue NewCF = DAG.getNode(BinOpcode, DL, VT, CF, C1);
1797+
assert((isConstantOrConstantVector(NewCF) ||
1798+
isConstantFPBuildVectorOrConstantFP(NewCF)) &&
1799+
"Failed to constant fold a binop with constant operands");
1800+
1801+
return DAG.getSelect(DL, VT, Sel.getOperand(0), NewCT, NewCF);
1802+
}
1803+
17501804
SDValue DAGCombiner::visitADD(SDNode *N) {
17511805
SDValue N0 = N->getOperand(0);
17521806
SDValue N1 = N->getOperand(1);
@@ -1795,6 +1849,9 @@ SDValue DAGCombiner::visitADD(SDNode *N) {
17951849
}
17961850
}
17971851

1852+
if (SDValue NewSel = foldBinOpIntoSelect(N))
1853+
return NewSel;
1854+
17981855
// reassociate add
17991856
if (SDValue RADD = ReassociateOps(ISD::ADD, DL, N0, N1))
18001857
return RADD;
@@ -1999,6 +2056,9 @@ SDValue DAGCombiner::visitSUB(SDNode *N) {
19992056
N1.getNode());
20002057
}
20012058

2059+
if (SDValue NewSel = foldBinOpIntoSelect(N))
2060+
return NewSel;
2061+
20022062
ConstantSDNode *N1C = getAsNonOpaqueConstant(N1);
20032063

20042064
// fold (sub x, c) -> (add x, -c)
@@ -2210,6 +2270,10 @@ SDValue DAGCombiner::visitMUL(SDNode *N) {
22102270
// fold (mul x, 1) -> x
22112271
if (N1IsConst && ConstValue1 == 1 && IsFullSplat)
22122272
return N0;
2273+
2274+
if (SDValue NewSel = foldBinOpIntoSelect(N))
2275+
return NewSel;
2276+
22132277
// fold (mul x, -1) -> 0-x
22142278
if (N1IsConst && ConstValue1.isAllOnesValue()) {
22152279
SDLoc DL(N);
@@ -2401,6 +2465,9 @@ SDValue DAGCombiner::visitSDIV(SDNode *N) {
24012465
return DAG.getNode(ISD::SUB, DL, VT,
24022466
DAG.getConstant(0, DL, VT), N0);
24032467

2468+
if (SDValue NewSel = foldBinOpIntoSelect(N))
2469+
return NewSel;
2470+
24042471
// If we know the sign bits of both operands are zero, strength reduce to a
24052472
// udiv instead. Handles (X&15) /s 4 -> X&15 >> 2
24062473
if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
@@ -2493,6 +2560,9 @@ SDValue DAGCombiner::visitUDIV(SDNode *N) {
24932560
N0C, N1C))
24942561
return Folded;
24952562

2563+
if (SDValue NewSel = foldBinOpIntoSelect(N))
2564+
return NewSel;
2565+
24962566
// fold (udiv x, (1 << c)) -> x >>u c
24972567
if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
24982568
DAG.isKnownToBeAPowerOfTwo(N1)) {
@@ -2561,6 +2631,9 @@ SDValue DAGCombiner::visitREM(SDNode *N) {
25612631
if (SDValue Folded = DAG.FoldConstantArithmetic(Opcode, DL, VT, N0C, N1C))
25622632
return Folded;
25632633

2634+
if (SDValue NewSel = foldBinOpIntoSelect(N))
2635+
return NewSel;
2636+
25642637
if (isSigned) {
25652638
// If we know the sign bits of both operands are zero, strength reduce to a
25662639
// urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15
@@ -3267,6 +3340,10 @@ SDValue DAGCombiner::visitAND(SDNode *N) {
32673340
if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
32683341
APInt::getAllOnesValue(BitWidth)))
32693342
return DAG.getConstant(0, SDLoc(N), VT);
3343+
3344+
if (SDValue NewSel = foldBinOpIntoSelect(N))
3345+
return NewSel;
3346+
32703347
// reassociate and
32713348
if (SDValue RAND = ReassociateOps(ISD::AND, SDLoc(N), N0, N1))
32723349
return RAND;
@@ -4008,6 +4085,10 @@ SDValue DAGCombiner::visitOR(SDNode *N) {
40084085
// fold (or x, -1) -> -1
40094086
if (isAllOnesConstant(N1))
40104087
return N1;
4088+
4089+
if (SDValue NewSel = foldBinOpIntoSelect(N))
4090+
return NewSel;
4091+
40114092
// fold (or x, c) -> c iff (x & ~c) == 0
40124093
if (N1C && DAG.MaskedValueIsZero(N0, ~N1C->getAPIntValue()))
40134094
return N1;
@@ -4753,6 +4834,10 @@ SDValue DAGCombiner::visitXOR(SDNode *N) {
47534834
// fold (xor x, 0) -> x
47544835
if (isNullConstant(N1))
47554836
return N0;
4837+
4838+
if (SDValue NewSel = foldBinOpIntoSelect(N))
4839+
return NewSel;
4840+
47564841
// reassociate xor
47574842
if (SDValue RXOR = ReassociateOps(ISD::XOR, SDLoc(N), N0, N1))
47584843
return RXOR;
@@ -5040,6 +5125,10 @@ SDValue DAGCombiner::visitSHL(SDNode *N) {
50405125
// fold (shl undef, x) -> 0
50415126
if (N0.isUndef())
50425127
return DAG.getConstant(0, SDLoc(N), VT);
5128+
5129+
if (SDValue NewSel = foldBinOpIntoSelect(N))
5130+
return NewSel;
5131+
50435132
// if (shl x, c) is known to be zero, return 0
50445133
if (DAG.MaskedValueIsZero(SDValue(N, 0),
50455134
APInt::getAllOnesValue(OpSizeInBits)))
@@ -5243,6 +5332,10 @@ SDValue DAGCombiner::visitSRA(SDNode *N) {
52435332
// fold (sra x, 0) -> x
52445333
if (N1C && N1C->isNullValue())
52455334
return N0;
5335+
5336+
if (SDValue NewSel = foldBinOpIntoSelect(N))
5337+
return NewSel;
5338+
52465339
// fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports
52475340
// sext_inreg.
52485341
if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) {
@@ -5390,6 +5483,10 @@ SDValue DAGCombiner::visitSRL(SDNode *N) {
53905483
// fold (srl x, 0) -> x
53915484
if (N1C && N1C->isNullValue())
53925485
return N0;
5486+
5487+
if (SDValue NewSel = foldBinOpIntoSelect(N))
5488+
return NewSel;
5489+
53935490
// if (srl x, c) is known to be zero, return 0
53945491
if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
53955492
APInt::getAllOnesValue(OpSizeInBits)))
@@ -9064,6 +9161,9 @@ SDValue DAGCombiner::visitFADD(SDNode *N) {
90649161
if (N0CFP && !N1CFP)
90659162
return DAG.getNode(ISD::FADD, DL, VT, N1, N0, Flags);
90669163

9164+
if (SDValue NewSel = foldBinOpIntoSelect(N))
9165+
return NewSel;
9166+
90679167
// fold (fadd A, (fneg B)) -> (fsub A, B)
90689168
if ((!LegalOperations || TLI.isOperationLegalOrCustom(ISD::FSUB, VT)) &&
90699169
isNegatibleForFree(N1, LegalOperations, TLI, &Options) == 2)
@@ -9211,6 +9311,9 @@ SDValue DAGCombiner::visitFSUB(SDNode *N) {
92119311
if (N0CFP && N1CFP)
92129312
return DAG.getNode(ISD::FSUB, DL, VT, N0, N1, Flags);
92139313

9314+
if (SDValue NewSel = foldBinOpIntoSelect(N))
9315+
return NewSel;
9316+
92149317
// fold (fsub A, (fneg B)) -> (fadd A, B)
92159318
if (isNegatibleForFree(N1, LegalOperations, TLI, &Options))
92169319
return DAG.getNode(ISD::FADD, DL, VT, N0,
@@ -9290,6 +9393,9 @@ SDValue DAGCombiner::visitFMUL(SDNode *N) {
92909393
if (N1CFP && N1CFP->isExactlyValue(1.0))
92919394
return N0;
92929395

9396+
if (SDValue NewSel = foldBinOpIntoSelect(N))
9397+
return NewSel;
9398+
92939399
if (Options.UnsafeFPMath) {
92949400
// fold (fmul A, 0) -> 0
92959401
if (N1CFP && N1CFP->isZero())
@@ -9544,6 +9650,9 @@ SDValue DAGCombiner::visitFDIV(SDNode *N) {
95449650
if (N0CFP && N1CFP)
95459651
return DAG.getNode(ISD::FDIV, SDLoc(N), VT, N0, N1, Flags);
95469652

9653+
if (SDValue NewSel = foldBinOpIntoSelect(N))
9654+
return NewSel;
9655+
95479656
if (Options.UnsafeFPMath) {
95489657
// fold (fdiv X, c2) -> fmul X, 1/c2 if losing precision is acceptable.
95499658
if (N1CFP) {
@@ -9647,6 +9756,9 @@ SDValue DAGCombiner::visitFREM(SDNode *N) {
96479756
return DAG.getNode(ISD::FREM, SDLoc(N), VT, N0, N1,
96489757
&cast<BinaryWithFlagsSDNode>(N)->Flags);
96499758

9759+
if (SDValue NewSel = foldBinOpIntoSelect(N))
9760+
return NewSel;
9761+
96509762
return SDValue();
96519763
}
96529764

‎llvm/test/CodeGen/ARM/select_xform.ll

+5-7
Original file line numberDiff line numberDiff line change
@@ -223,21 +223,19 @@ entry:
223223
ret i32 %add
224224
}
225225

226-
; Do not fold the xor into the select
226+
; Fold the xor into the select.
227227
define i32 @t15(i32 %p) {
228228
entry:
229229
; ARM-LABEL: t15:
230-
; ARM: mov [[REG:r[0-9]+]], #2
230+
; ARM: mov [[REG:r[0-9]+]], #3
231231
; ARM: cmp r0, #8
232-
; ARM: movwgt [[REG:r[0-9]+]], #1
233-
; ARM: eor r0, [[REG:r[0-9]+]], #1
232+
; ARM: movwgt [[REG:r[0-9]+]], #0
234233

235234
; T2-LABEL: t15:
236-
; T2: movs [[REG:r[0-9]+]], #2
235+
; T2: movs [[REG:r[0-9]+]], #3
237236
; T2: cmp [[REG:r[0-9]+]], #8
238237
; T2: it gt
239-
; T2: movgt [[REG:r[0-9]+]], #1
240-
; T2: eor r0, [[REG:r[0-9]+]], #1
238+
; T2: movgt [[REG:r[0-9]+]], #0
241239
%cmp = icmp sgt i32 %p, 8
242240
%a = select i1 %cmp, i32 1, i32 2
243241
%xor = xor i32 %a, 1

0 commit comments

Comments
 (0)