1 //===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Nate Begeman and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass combines dag nodes to form fewer, simpler DAG nodes. It can be run
11 // both before and after the DAG is legalized.
13 // FIXME: Missing folds
14 // sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into
15 // a sequence of multiplies, shifts, and adds. This should be controlled by
16 // some kind of hint from the target that int div is expensive.
17 // various folds of mulh[s,u] by constants such as -1, powers of 2, etc.
19 // FIXME: Should add a corresponding version of fold AND with
20 // ZERO_EXTEND/SIGN_EXTEND by converting them to an ANY_EXTEND node which
23 // FIXME: select C, 16, 0 -> shr C, 4
24 // FIXME: select C, pow2, pow2 -> something smart
25 // FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z)
26 // FIXME: (select C, load A, load B) -> load (select C, A, B)
27 // FIXME: store -> load -> forward substitute
28 // FIXME: Dead stores -> nuke
29 // FIXME: shr X, (and Y,31) -> shr X, Y
30 // FIXME: TRUNC (LOAD) -> EXT_LOAD/LOAD(smaller)
31 // FIXME: mul (x, const) -> shifts + adds
32 // FIXME: undef values
33 // FIXME: zero extend when top bits are 0 -> drop it ?
34 // FIXME: make truncate see through SIGN_EXTEND and AND
35 // FIXME: sext_in_reg(setcc) on targets that return zero or one, and where
36 // EVT != MVT::i1 can drop the sext.
37 // FIXME: (sra (sra x, c1), c2) -> (sra x, c1+c2)
38 // FIXME: verify that getNode can't return extends with an operand whose type
39 // is >= to that of the extend.
40 // FIXME: divide by zero is currently left unfolded. do we want to turn this
42 // FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false
44 //===----------------------------------------------------------------------===//
46 #define DEBUG_TYPE "dagcombine"
47 #include "llvm/ADT/Statistic.h"
48 #include "llvm/CodeGen/SelectionDAG.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/MathExtras.h"
51 #include "llvm/Target/TargetLowering.h"
57 Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");
64 // Worklist of all of the nodes that need to be simplified.
65 std::vector<SDNode*> WorkList;
67 /// AddUsersToWorkList - When an instruction is simplified, add all users of
68 /// the instruction to the work lists because they might get more simplified
71 void AddUsersToWorkList(SDNode *N) {
72 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
74 WorkList.push_back(*UI);
77 /// removeFromWorkList - remove all instances of N from the worklist.
78 void removeFromWorkList(SDNode *N) {
79 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
83 /// visit - call the node-specific routine that knows how to fold each
84 /// particular type of node.
85 SDOperand visit(SDNode *N);
87 // Visitation implementation - Implement dag node combining for different
88 // node types. The semantics are as follows:
90 // SDOperand.Val == 0 - No change was made
91 // otherwise - N should be replaced by the returned Operand.
93 SDOperand visitTokenFactor(SDNode *N);
94 SDOperand visitADD(SDNode *N);
95 SDOperand visitSUB(SDNode *N);
96 SDOperand visitMUL(SDNode *N);
97 SDOperand visitSDIV(SDNode *N);
98 SDOperand visitUDIV(SDNode *N);
99 SDOperand visitSREM(SDNode *N);
100 SDOperand visitUREM(SDNode *N);
101 SDOperand visitMULHU(SDNode *N);
102 SDOperand visitMULHS(SDNode *N);
103 SDOperand visitAND(SDNode *N);
104 SDOperand visitOR(SDNode *N);
105 SDOperand visitXOR(SDNode *N);
106 SDOperand visitSHL(SDNode *N);
107 SDOperand visitSRA(SDNode *N);
108 SDOperand visitSRL(SDNode *N);
109 SDOperand visitCTLZ(SDNode *N);
110 SDOperand visitCTTZ(SDNode *N);
111 SDOperand visitCTPOP(SDNode *N);
112 SDOperand visitSELECT(SDNode *N);
113 SDOperand visitSELECT_CC(SDNode *N);
114 SDOperand visitSETCC(SDNode *N);
115 SDOperand visitSIGN_EXTEND(SDNode *N);
116 SDOperand visitZERO_EXTEND(SDNode *N);
117 SDOperand visitSIGN_EXTEND_INREG(SDNode *N);
118 SDOperand visitTRUNCATE(SDNode *N);
120 SDOperand visitFADD(SDNode *N);
121 SDOperand visitFSUB(SDNode *N);
122 SDOperand visitFMUL(SDNode *N);
123 SDOperand visitFDIV(SDNode *N);
124 SDOperand visitFREM(SDNode *N);
125 SDOperand visitSINT_TO_FP(SDNode *N);
126 SDOperand visitUINT_TO_FP(SDNode *N);
127 SDOperand visitFP_TO_SINT(SDNode *N);
128 SDOperand visitFP_TO_UINT(SDNode *N);
129 SDOperand visitFP_ROUND(SDNode *N);
130 SDOperand visitFP_ROUND_INREG(SDNode *N);
131 SDOperand visitFP_EXTEND(SDNode *N);
132 SDOperand visitFNEG(SDNode *N);
133 SDOperand visitFABS(SDNode *N);
134 SDOperand visitBRCOND(SDNode *N);
135 SDOperand visitBRCONDTWOWAY(SDNode *N);
136 SDOperand visitBR_CC(SDNode *N);
137 SDOperand visitBRTWOWAY_CC(SDNode *N);
139 SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2);
140 SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2,
141 SDOperand N3, ISD::CondCode CC);
142 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
143 ISD::CondCode Cond, bool foldBooleans = true);
145 DAGCombiner(SelectionDAG &D)
146 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {}
148 /// Run - runs the dag combiner on all nodes in the work list
149 void Run(bool RunningAfterLegalize);
153 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
154 /// this predicate to simplify operations downstream. V and Mask are known to
155 /// be the same type.
156 static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask,
157 const TargetLowering &TLI) {
159 if (Mask == 0) return true;
161 // If we know the result of a setcc has the top bits zero, use this info.
162 switch (Op.getOpcode()) {
164 return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
166 // FIXME: teach this about non ZeroOrOne values, such as 0 or -1
167 return ((Mask & 1) == 0) &&
168 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
170 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
171 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
172 case ISD::ZERO_EXTEND:
173 SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
174 return MaskedValueIsZero(Op.getOperand(0),Mask & ((1ULL << SrcBits)-1),TLI);
175 case ISD::AssertZext:
176 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
177 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
179 // (X & C1) & C2 == 0 iff C1 & C2 == 0.
180 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
181 return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI);
185 return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) &&
186 MaskedValueIsZero(Op.getOperand(1), Mask, TLI);
188 return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) &&
189 MaskedValueIsZero(Op.getOperand(2), Mask, TLI);
191 return MaskedValueIsZero(Op.getOperand(2), Mask, TLI) &&
192 MaskedValueIsZero(Op.getOperand(3), Mask, TLI);
194 // (ushr X, C1) & C2 == 0 iff X & (C2 << C1) == 0
195 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
196 uint64_t NewVal = Mask << ShAmt->getValue();
197 SrcBits = MVT::getSizeInBits(Op.getValueType());
198 if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1;
199 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
203 // (ushl X, C1) & C2 == 0 iff X & (C2 >> C1) == 0
204 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
205 uint64_t NewVal = Mask >> ShAmt->getValue();
206 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
210 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
211 // We know that the top bits of C-X are clear if X contains less bits
212 // than C (i.e. no wrap-around can happen). For example, 20-X is
213 // positive if we can prove that X is >= 0 and < 16.
214 unsigned Bits = MVT::getSizeInBits(CLHS->getValueType(0));
215 if ((CLHS->getValue() & (1 << (Bits-1))) == 0) { // sign bit clear
216 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
217 uint64_t MaskV = (1ULL << (63-NLZ))-1;
218 if (MaskedValueIsZero(Op.getOperand(1), ~MaskV, TLI)) {
219 // High bits are clear this value is known to be >= C.
220 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
221 if ((Mask & ((1ULL << (64-NLZ2))-1)) == 0)
230 // Bit counting instructions can not set the high bits of the result
231 // register. The max number of bits sets depends on the input.
232 return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0;
234 // TODO we could handle some SRA cases here.
240 // isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
241 // that selects between the values 1 and 0, making it equivalent to a setcc.
242 // Also, set the incoming LHS, RHS, and CC references to the appropriate
243 // nodes based on the type of node we are checking. This simplifies life a
244 // bit for the callers.
245 static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS,
247 if (N.getOpcode() == ISD::SETCC) {
248 LHS = N.getOperand(0);
249 RHS = N.getOperand(1);
250 CC = N.getOperand(2);
253 if (N.getOpcode() == ISD::SELECT_CC &&
254 N.getOperand(2).getOpcode() == ISD::Constant &&
255 N.getOperand(3).getOpcode() == ISD::Constant &&
256 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 &&
257 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) {
258 LHS = N.getOperand(0);
259 RHS = N.getOperand(1);
260 CC = N.getOperand(4);
266 // isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only
267 // one use. If this is true, it allows the users to invert the operation for
268 // free when it is profitable to do so.
269 static bool isOneUseSetCC(SDOperand N) {
270 SDOperand N0, N1, N2;
271 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse())
276 // FIXME: This should probably go in the ISD class rather than being duplicated
278 static bool isCommutativeBinOp(unsigned Opcode) {
284 case ISD::XOR: return true;
285 default: return false; // FIXME: Need commutative info for user ops!
289 void DAGCombiner::Run(bool RunningAfterLegalize) {
290 // set the instance variable, so that the various visit routines may use it.
291 AfterLegalize = RunningAfterLegalize;
293 // Add all the dag nodes to the worklist.
294 WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end());
296 // Create a dummy node (which is not added to allnodes), that adds a reference
297 // to the root node, preventing it from being deleted, and tracking any
298 // changes of the root.
299 HandleSDNode Dummy(DAG.getRoot());
301 // while the worklist isn't empty, inspect the node on the end of it and
302 // try and combine it.
303 while (!WorkList.empty()) {
304 SDNode *N = WorkList.back();
307 // If N has no uses, it is dead. Make sure to revisit all N's operands once
308 // N is deleted from the DAG, since they too may now be dead or may have a
309 // reduced number of uses, allowing other xforms.
310 if (N->use_empty() && N != &Dummy) {
311 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
312 WorkList.push_back(N->getOperand(i).Val);
314 removeFromWorkList(N);
319 SDOperand RV = visit(N);
322 // If we get back the same node we passed in, rather than a new node or
323 // zero, we know that the node must have defined multiple values and
324 // CombineTo was used. Since CombineTo takes care of the worklist
325 // mechanics for us, we have no work to do in this case.
327 DEBUG(std::cerr << "\nReplacing "; N->dump();
328 std::cerr << "\nWith: "; RV.Val->dump();
330 DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV));
332 // Push the new node and any users onto the worklist
333 WorkList.push_back(RV.Val);
334 AddUsersToWorkList(RV.Val);
336 // Nodes can end up on the worklist more than once. Make sure we do
337 // not process a node that has been replaced.
338 removeFromWorkList(N);
340 // Finally, since the node is now dead, remove it from the graph.
346 // If the root changed (e.g. it was a dead load, update the root).
347 DAG.setRoot(Dummy.getValue());
350 SDOperand DAGCombiner::visit(SDNode *N) {
351 switch(N->getOpcode()) {
353 case ISD::TokenFactor: return visitTokenFactor(N);
354 case ISD::ADD: return visitADD(N);
355 case ISD::SUB: return visitSUB(N);
356 case ISD::MUL: return visitMUL(N);
357 case ISD::SDIV: return visitSDIV(N);
358 case ISD::UDIV: return visitUDIV(N);
359 case ISD::SREM: return visitSREM(N);
360 case ISD::UREM: return visitUREM(N);
361 case ISD::MULHU: return visitMULHU(N);
362 case ISD::MULHS: return visitMULHS(N);
363 case ISD::AND: return visitAND(N);
364 case ISD::OR: return visitOR(N);
365 case ISD::XOR: return visitXOR(N);
366 case ISD::SHL: return visitSHL(N);
367 case ISD::SRA: return visitSRA(N);
368 case ISD::SRL: return visitSRL(N);
369 case ISD::CTLZ: return visitCTLZ(N);
370 case ISD::CTTZ: return visitCTTZ(N);
371 case ISD::CTPOP: return visitCTPOP(N);
372 case ISD::SELECT: return visitSELECT(N);
373 case ISD::SELECT_CC: return visitSELECT_CC(N);
374 case ISD::SETCC: return visitSETCC(N);
375 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N);
376 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N);
377 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N);
378 case ISD::TRUNCATE: return visitTRUNCATE(N);
379 case ISD::FADD: return visitFADD(N);
380 case ISD::FSUB: return visitFSUB(N);
381 case ISD::FMUL: return visitFMUL(N);
382 case ISD::FDIV: return visitFDIV(N);
383 case ISD::FREM: return visitFREM(N);
384 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N);
385 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N);
386 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N);
387 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N);
388 case ISD::FP_ROUND: return visitFP_ROUND(N);
389 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N);
390 case ISD::FP_EXTEND: return visitFP_EXTEND(N);
391 case ISD::FNEG: return visitFNEG(N);
392 case ISD::FABS: return visitFABS(N);
393 case ISD::BRCOND: return visitBRCOND(N);
394 case ISD::BRCONDTWOWAY: return visitBRCONDTWOWAY(N);
395 case ISD::BR_CC: return visitBR_CC(N);
396 case ISD::BRTWOWAY_CC: return visitBRTWOWAY_CC(N);
401 SDOperand DAGCombiner::visitTokenFactor(SDNode *N) {
402 // If the token factor has two operands and one is the entry token, replace
403 // the token factor with the other operand.
404 if (N->getNumOperands() == 2) {
405 if (N->getOperand(0).getOpcode() == ISD::EntryToken)
406 return N->getOperand(1);
407 if (N->getOperand(1).getOpcode() == ISD::EntryToken)
408 return N->getOperand(0);
413 SDOperand DAGCombiner::visitADD(SDNode *N) {
414 SDOperand N0 = N->getOperand(0);
415 SDOperand N1 = N->getOperand(1);
416 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
417 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
418 MVT::ValueType VT = N0.getValueType();
420 // fold (add c1, c2) -> c1+c2
422 return DAG.getConstant(N0C->getValue() + N1C->getValue(), VT);
423 // canonicalize constant to RHS
428 // fold (add x, 0) -> x
429 if (N1C && N1C->isNullValue())
431 // fold (add (add x, c1), c2) -> (add x, c1+c2)
432 if (N1C && N0.getOpcode() == ISD::ADD) {
433 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
434 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
436 return DAG.getNode(ISD::ADD, VT, N0.getOperand(1),
437 DAG.getConstant(N1C->getValue()+N00C->getValue(), VT));
439 return DAG.getNode(ISD::ADD, VT, N0.getOperand(0),
440 DAG.getConstant(N1C->getValue()+N01C->getValue(), VT));
442 // fold ((0-A) + B) -> B-A
443 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
444 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
445 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1));
446 // fold (A + (0-B)) -> A-B
447 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
448 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
449 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1));
450 // fold (A+(B-A)) -> B
451 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
452 return N1.getOperand(0);
456 SDOperand DAGCombiner::visitSUB(SDNode *N) {
457 SDOperand N0 = N->getOperand(0);
458 SDOperand N1 = N->getOperand(1);
459 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
460 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
462 // fold (sub c1, c2) -> c1-c2
464 return DAG.getConstant(N0C->getValue() - N1C->getValue(),
466 // fold (sub x, 0) -> x
467 if (N1C && N1C->isNullValue())
470 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
471 return N0.getOperand(1);
473 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
474 return N0.getOperand(0);
478 SDOperand DAGCombiner::visitMUL(SDNode *N) {
479 SDOperand N0 = N->getOperand(0);
480 SDOperand N1 = N->getOperand(1);
481 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
482 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
483 MVT::ValueType VT = N0.getValueType();
485 // fold (mul c1, c2) -> c1*c2
487 return DAG.getConstant(N0C->getValue() * N1C->getValue(),
489 // canonicalize constant to RHS
494 // fold (mul x, 0) -> 0
495 if (N1C && N1C->isNullValue())
497 // fold (mul x, -1) -> 0-x
498 if (N1C && N1C->isAllOnesValue())
499 return DAG.getNode(ISD::SUB, N->getValueType(0),
500 DAG.getConstant(0, N->getValueType(0)), N0);
501 // fold (mul x, (1 << c)) -> x << c
502 if (N1C && isPowerOf2_64(N1C->getValue()))
503 return DAG.getNode(ISD::SHL, N->getValueType(0), N0,
504 DAG.getConstant(Log2_64(N1C->getValue()),
505 TLI.getShiftAmountTy()));
506 // fold (mul (mul x, c1), c2) -> (mul x, c1*c2)
507 if (N1C && N0.getOpcode() == ISD::MUL) {
508 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
509 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
511 return DAG.getNode(ISD::MUL, VT, N0.getOperand(1),
512 DAG.getConstant(N1C->getValue()*N00C->getValue(), VT));
514 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0),
515 DAG.getConstant(N1C->getValue()*N01C->getValue(), VT));
520 SDOperand DAGCombiner::visitSDIV(SDNode *N) {
521 SDOperand N0 = N->getOperand(0);
522 SDOperand N1 = N->getOperand(1);
523 MVT::ValueType VT = N->getValueType(0);
524 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
525 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
527 // fold (sdiv c1, c2) -> c1/c2
528 if (N0C && N1C && !N1C->isNullValue())
529 return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(),
532 // If we know the sign bits of both operands are zero, strength reduce to a
533 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2
534 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
535 if (MaskedValueIsZero(N1, SignBit, TLI) &&
536 MaskedValueIsZero(N0, SignBit, TLI))
537 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1);
543 SDOperand DAGCombiner::visitUDIV(SDNode *N) {
544 SDOperand N0 = N->getOperand(0);
545 SDOperand N1 = N->getOperand(1);
546 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
547 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
549 // fold (udiv c1, c2) -> c1/c2
550 if (N0C && N1C && !N1C->isNullValue())
551 return DAG.getConstant(N0C->getValue() / N1C->getValue(),
553 // fold (udiv x, (1 << c)) -> x >>u c
554 if (N1C && isPowerOf2_64(N1C->getValue()))
555 return DAG.getNode(ISD::SRL, N->getValueType(0), N0,
556 DAG.getConstant(Log2_64(N1C->getValue()),
557 TLI.getShiftAmountTy()));
561 SDOperand DAGCombiner::visitSREM(SDNode *N) {
562 SDOperand N0 = N->getOperand(0);
563 SDOperand N1 = N->getOperand(1);
564 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
565 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
567 // fold (srem c1, c2) -> c1%c2
568 if (N0C && N1C && !N1C->isNullValue())
569 return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(),
574 SDOperand DAGCombiner::visitUREM(SDNode *N) {
575 SDOperand N0 = N->getOperand(0);
576 SDOperand N1 = N->getOperand(1);
577 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
578 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
580 // fold (urem c1, c2) -> c1%c2
581 if (N0C && N1C && !N1C->isNullValue())
582 return DAG.getConstant(N0C->getValue() % N1C->getValue(),
584 // FIXME: c2 power of 2 -> mask?
588 SDOperand DAGCombiner::visitMULHS(SDNode *N) {
589 SDOperand N0 = N->getOperand(0);
590 SDOperand N1 = N->getOperand(1);
591 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
593 // fold (mulhs x, 0) -> 0
594 if (N1C && N1C->isNullValue())
596 // fold (mulhs x, 1) -> (sra x, size(x)-1)
597 if (N1C && N1C->getValue() == 1)
598 return DAG.getNode(ISD::SRA, N0.getValueType(), N0,
599 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
600 TLI.getShiftAmountTy()));
604 SDOperand DAGCombiner::visitMULHU(SDNode *N) {
605 SDOperand N0 = N->getOperand(0);
606 SDOperand N1 = N->getOperand(1);
607 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
609 // fold (mulhu x, 0) -> 0
610 if (N1C && N1C->isNullValue())
612 // fold (mulhu x, 1) -> 0
613 if (N1C && N1C->getValue() == 1)
614 return DAG.getConstant(0, N0.getValueType());
618 SDOperand DAGCombiner::visitAND(SDNode *N) {
619 SDOperand N0 = N->getOperand(0);
620 SDOperand N1 = N->getOperand(1);
621 SDOperand LL, LR, RL, RR, CC0, CC1;
622 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
623 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
624 MVT::ValueType VT = N1.getValueType();
625 unsigned OpSizeInBits = MVT::getSizeInBits(VT);
627 // fold (and c1, c2) -> c1&c2
629 return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT);
630 // canonicalize constant to RHS
635 // fold (and x, -1) -> x
636 if (N1C && N1C->isAllOnesValue())
638 // if (and x, c) is known to be zero, return 0
639 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
640 return DAG.getConstant(0, VT);
641 // fold (and x, c) -> x iff (x & ~c) == 0
642 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)),
645 // fold (and (and x, c1), c2) -> (and x, c1^c2)
646 if (N1C && N0.getOpcode() == ISD::AND) {
647 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
648 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
650 return DAG.getNode(ISD::AND, VT, N0.getOperand(1),
651 DAG.getConstant(N1C->getValue()&N00C->getValue(), VT));
653 return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
654 DAG.getConstant(N1C->getValue()&N01C->getValue(), VT));
656 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
657 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) {
658 unsigned ExtendBits =
659 MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT());
660 if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0)
661 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1);
663 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF
664 if (N0.getOpcode() == ISD::OR)
665 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
666 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue())
668 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
669 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
670 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
671 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
673 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
674 MVT::isInteger(LL.getValueType())) {
675 // fold (X == 0) & (Y == 0) -> (X|Y == 0)
676 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) {
677 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
678 WorkList.push_back(ORNode.Val);
679 return DAG.getSetCC(VT, ORNode, LR, Op1);
681 // fold (X == -1) & (Y == -1) -> (X&Y == -1)
682 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) {
683 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
684 WorkList.push_back(ANDNode.Val);
685 return DAG.getSetCC(VT, ANDNode, LR, Op1);
687 // fold (X > -1) & (Y > -1) -> (X|Y > -1)
688 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) {
689 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
690 WorkList.push_back(ORNode.Val);
691 return DAG.getSetCC(VT, ORNode, LR, Op1);
694 // canonicalize equivalent to ll == rl
695 if (LL == RR && LR == RL) {
696 Op1 = ISD::getSetCCSwappedOperands(Op1);
699 if (LL == RL && LR == RR) {
700 bool isInteger = MVT::isInteger(LL.getValueType());
701 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
702 if (Result != ISD::SETCC_INVALID)
703 return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
706 // fold (and (zext x), (zext y)) -> (zext (and x, y))
707 if (N0.getOpcode() == ISD::ZERO_EXTEND &&
708 N1.getOpcode() == ISD::ZERO_EXTEND &&
709 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
710 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
711 N0.getOperand(0), N1.getOperand(0));
712 WorkList.push_back(ANDNode.Val);
713 return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode);
715 // fold (and (shl/srl x), (shl/srl y)) -> (shl/srl (and x, y))
716 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) ||
717 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL)) &&
718 N0.getOperand(1) == N1.getOperand(1)) {
719 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
720 N0.getOperand(0), N1.getOperand(0));
721 WorkList.push_back(ANDNode.Val);
722 return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1));
727 SDOperand DAGCombiner::visitOR(SDNode *N) {
728 SDOperand N0 = N->getOperand(0);
729 SDOperand N1 = N->getOperand(1);
730 SDOperand LL, LR, RL, RR, CC0, CC1;
731 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
732 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
733 MVT::ValueType VT = N1.getValueType();
734 unsigned OpSizeInBits = MVT::getSizeInBits(VT);
736 // fold (or c1, c2) -> c1|c2
738 return DAG.getConstant(N0C->getValue() | N1C->getValue(),
740 // canonicalize constant to RHS
745 // fold (or x, 0) -> x
746 if (N1C && N1C->isNullValue())
748 // fold (or x, -1) -> -1
749 if (N1C && N1C->isAllOnesValue())
751 // fold (or x, c) -> c iff (x & ~c) == 0
752 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)),
755 // fold (or (or x, c1), c2) -> (or x, c1|c2)
756 if (N1C && N0.getOpcode() == ISD::OR) {
757 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
758 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
760 return DAG.getNode(ISD::OR, VT, N0.getOperand(1),
761 DAG.getConstant(N1C->getValue()|N00C->getValue(), VT));
763 return DAG.getNode(ISD::OR, VT, N0.getOperand(0),
764 DAG.getConstant(N1C->getValue()|N01C->getValue(), VT));
766 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
767 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
768 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
769 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
771 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
772 MVT::isInteger(LL.getValueType())) {
773 // fold (X != 0) | (Y != 0) -> (X|Y != 0)
774 // fold (X < 0) | (Y < 0) -> (X|Y < 0)
775 if (cast<ConstantSDNode>(LR)->getValue() == 0 &&
776 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) {
777 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
778 WorkList.push_back(ORNode.Val);
779 return DAG.getSetCC(VT, ORNode, LR, Op1);
781 // fold (X != -1) | (Y != -1) -> (X&Y != -1)
782 // fold (X > -1) | (Y > -1) -> (X&Y > -1)
783 if (cast<ConstantSDNode>(LR)->isAllOnesValue() &&
784 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) {
785 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
786 WorkList.push_back(ANDNode.Val);
787 return DAG.getSetCC(VT, ANDNode, LR, Op1);
790 // canonicalize equivalent to ll == rl
791 if (LL == RR && LR == RL) {
792 Op1 = ISD::getSetCCSwappedOperands(Op1);
795 if (LL == RL && LR == RR) {
796 bool isInteger = MVT::isInteger(LL.getValueType());
797 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger);
798 if (Result != ISD::SETCC_INVALID)
799 return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
802 // fold (or (zext x), (zext y)) -> (zext (or x, y))
803 if (N0.getOpcode() == ISD::ZERO_EXTEND &&
804 N1.getOpcode() == ISD::ZERO_EXTEND &&
805 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
806 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(),
807 N0.getOperand(0), N1.getOperand(0));
808 WorkList.push_back(ORNode.Val);
809 return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode);
814 SDOperand DAGCombiner::visitXOR(SDNode *N) {
815 SDOperand N0 = N->getOperand(0);
816 SDOperand N1 = N->getOperand(1);
817 SDOperand LHS, RHS, CC;
818 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
819 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
820 MVT::ValueType VT = N0.getValueType();
822 // fold (xor c1, c2) -> c1^c2
824 return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT);
825 // canonicalize constant to RHS
830 // fold (xor x, 0) -> x
831 if (N1C && N1C->isNullValue())
833 // fold !(x cc y) -> (x !cc y)
834 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) {
835 bool isInt = MVT::isInteger(LHS.getValueType());
836 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
838 if (N0.getOpcode() == ISD::SETCC)
839 return DAG.getSetCC(VT, LHS, RHS, NotCC);
840 if (N0.getOpcode() == ISD::SELECT_CC)
841 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC);
842 assert(0 && "Unhandled SetCC Equivalent!");
845 // fold !(x or y) -> (!x and !y) iff x or y are setcc
846 if (N1C && N1C->getValue() == 1 &&
847 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
848 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
849 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) {
850 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
851 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS
852 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS
853 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val);
854 return DAG.getNode(NewOpcode, VT, LHS, RHS);
857 // fold !(x or y) -> (!x and !y) iff x or y are constants
858 if (N1C && N1C->isAllOnesValue() &&
859 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
860 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
861 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) {
862 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
863 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS
864 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS
865 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val);
866 return DAG.getNode(NewOpcode, VT, LHS, RHS);
869 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2)
870 if (N1C && N0.getOpcode() == ISD::XOR) {
871 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
872 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
874 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1),
875 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT));
877 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0),
878 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT));
880 // fold (xor x, x) -> 0
882 return DAG.getConstant(0, VT);
883 // fold (xor (zext x), (zext y)) -> (zext (xor x, y))
884 if (N0.getOpcode() == ISD::ZERO_EXTEND &&
885 N1.getOpcode() == ISD::ZERO_EXTEND &&
886 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
887 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(),
888 N0.getOperand(0), N1.getOperand(0));
889 WorkList.push_back(XORNode.Val);
890 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode);
895 SDOperand DAGCombiner::visitSHL(SDNode *N) {
896 SDOperand N0 = N->getOperand(0);
897 SDOperand N1 = N->getOperand(1);
898 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
899 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
900 MVT::ValueType VT = N0.getValueType();
901 unsigned OpSizeInBits = MVT::getSizeInBits(VT);
903 // fold (shl c1, c2) -> c1<<c2
905 return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT);
906 // fold (shl 0, x) -> 0
907 if (N0C && N0C->isNullValue())
909 // fold (shl x, c >= size(x)) -> undef
910 if (N1C && N1C->getValue() >= OpSizeInBits)
911 return DAG.getNode(ISD::UNDEF, VT);
912 // fold (shl x, 0) -> x
913 if (N1C && N1C->isNullValue())
915 // if (shl x, c) is known to be zero, return 0
916 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
917 return DAG.getConstant(0, VT);
918 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
919 if (N1C && N0.getOpcode() == ISD::SHL &&
920 N0.getOperand(1).getOpcode() == ISD::Constant) {
921 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
922 uint64_t c2 = N1C->getValue();
923 if (c1 + c2 > OpSizeInBits)
924 return DAG.getConstant(0, VT);
925 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0),
926 DAG.getConstant(c1 + c2, N1.getValueType()));
928 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or
929 // (srl (and x, -1 << c1), c1-c2)
930 if (N1C && N0.getOpcode() == ISD::SRL &&
931 N0.getOperand(1).getOpcode() == ISD::Constant) {
932 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
933 uint64_t c2 = N1C->getValue();
934 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0),
935 DAG.getConstant(~0ULL << c1, VT));
937 return DAG.getNode(ISD::SHL, VT, Mask,
938 DAG.getConstant(c2-c1, N1.getValueType()));
940 return DAG.getNode(ISD::SRL, VT, Mask,
941 DAG.getConstant(c1-c2, N1.getValueType()));
943 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1)
944 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
945 return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
946 DAG.getConstant(~0ULL << N1C->getValue(), VT));
950 SDOperand DAGCombiner::visitSRA(SDNode *N) {
951 SDOperand N0 = N->getOperand(0);
952 SDOperand N1 = N->getOperand(1);
953 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
954 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
955 MVT::ValueType VT = N0.getValueType();
956 unsigned OpSizeInBits = MVT::getSizeInBits(VT);
958 // fold (sra c1, c2) -> c1>>c2
960 return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT);
961 // fold (sra 0, x) -> 0
962 if (N0C && N0C->isNullValue())
964 // fold (sra -1, x) -> -1
965 if (N0C && N0C->isAllOnesValue())
967 // fold (sra x, c >= size(x)) -> undef
968 if (N1C && N1C->getValue() >= OpSizeInBits)
969 return DAG.getNode(ISD::UNDEF, VT);
970 // fold (sra x, 0) -> x
971 if (N1C && N1C->isNullValue())
973 // If the sign bit is known to be zero, switch this to a SRL.
974 if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI))
975 return DAG.getNode(ISD::SRL, VT, N0, N1);
979 SDOperand DAGCombiner::visitSRL(SDNode *N) {
980 SDOperand N0 = N->getOperand(0);
981 SDOperand N1 = N->getOperand(1);
982 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
983 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
984 MVT::ValueType VT = N0.getValueType();
985 unsigned OpSizeInBits = MVT::getSizeInBits(VT);
987 // fold (srl c1, c2) -> c1 >>u c2
989 return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT);
990 // fold (srl 0, x) -> 0
991 if (N0C && N0C->isNullValue())
993 // fold (srl x, c >= size(x)) -> undef
994 if (N1C && N1C->getValue() >= OpSizeInBits)
995 return DAG.getNode(ISD::UNDEF, VT);
996 // fold (srl x, 0) -> x
997 if (N1C && N1C->isNullValue())
999 // if (srl x, c) is known to be zero, return 0
1000 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
1001 return DAG.getConstant(0, VT);
1002 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
1003 if (N1C && N0.getOpcode() == ISD::SRL &&
1004 N0.getOperand(1).getOpcode() == ISD::Constant) {
1005 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1006 uint64_t c2 = N1C->getValue();
1007 if (c1 + c2 > OpSizeInBits)
1008 return DAG.getConstant(0, VT);
1009 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0),
1010 DAG.getConstant(c1 + c2, N1.getValueType()));
1015 SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
1016 SDOperand N0 = N->getOperand(0);
1017 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1019 // fold (ctlz c1) -> c2
1021 return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()),
1026 SDOperand DAGCombiner::visitCTTZ(SDNode *N) {
1027 SDOperand N0 = N->getOperand(0);
1028 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1030 // fold (cttz c1) -> c2
1032 return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()),
1037 SDOperand DAGCombiner::visitCTPOP(SDNode *N) {
1038 SDOperand N0 = N->getOperand(0);
1039 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1041 // fold (ctpop c1) -> c2
1043 return DAG.getConstant(CountPopulation_64(N0C->getValue()),
1048 SDOperand DAGCombiner::visitSELECT(SDNode *N) {
1049 SDOperand N0 = N->getOperand(0);
1050 SDOperand N1 = N->getOperand(1);
1051 SDOperand N2 = N->getOperand(2);
1052 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1053 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1054 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
1055 MVT::ValueType VT = N->getValueType(0);
1057 // fold select C, X, X -> X
1060 // fold select true, X, Y -> X
1061 if (N0C && !N0C->isNullValue())
1063 // fold select false, X, Y -> Y
1064 if (N0C && N0C->isNullValue())
1066 // fold select C, 1, X -> C | X
1067 if (MVT::i1 == VT && N1C && N1C->getValue() == 1)
1068 return DAG.getNode(ISD::OR, VT, N0, N2);
1069 // fold select C, 0, X -> ~C & X
1070 // FIXME: this should check for C type == X type, not i1?
1071 if (MVT::i1 == VT && N1C && N1C->isNullValue()) {
1072 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1073 WorkList.push_back(XORNode.Val);
1074 return DAG.getNode(ISD::AND, VT, XORNode, N2);
1076 // fold select C, X, 1 -> ~C | X
1077 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) {
1078 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1079 WorkList.push_back(XORNode.Val);
1080 return DAG.getNode(ISD::OR, VT, XORNode, N1);
1082 // fold select C, X, 0 -> C & X
1083 // FIXME: this should check for C type == X type, not i1?
1084 if (MVT::i1 == VT && N2C && N2C->isNullValue())
1085 return DAG.getNode(ISD::AND, VT, N0, N1);
1086 // fold X ? X : Y --> X ? 1 : Y --> X | Y
1087 if (MVT::i1 == VT && N0 == N1)
1088 return DAG.getNode(ISD::OR, VT, N0, N2);
1089 // fold X ? Y : X --> X ? Y : 0 --> X & Y
1090 if (MVT::i1 == VT && N0 == N2)
1091 return DAG.getNode(ISD::AND, VT, N0, N1);
1092 // fold selects based on a setcc into other things, such as min/max/abs
1093 if (N0.getOpcode() == ISD::SETCC)
1094 return SimplifySelect(N0, N1, N2);
1098 SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) {
1099 SDOperand N0 = N->getOperand(0);
1100 SDOperand N1 = N->getOperand(1);
1101 SDOperand N2 = N->getOperand(2);
1102 SDOperand N3 = N->getOperand(3);
1103 SDOperand N4 = N->getOperand(4);
1104 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1105 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1106 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
1107 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get();
1109 // Determine if the condition we're dealing with is constant
1110 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
1111 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1113 // fold select_cc lhs, rhs, x, x, cc -> x
1116 // fold select_cc into other things, such as min/max/abs
1117 return SimplifySelectCC(N0, N1, N2, N3, CC);
1120 SDOperand DAGCombiner::visitSETCC(SDNode *N) {
1121 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1),
1122 cast<CondCodeSDNode>(N->getOperand(2))->get());
1125 SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
1126 SDOperand N0 = N->getOperand(0);
1127 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1128 MVT::ValueType VT = N->getValueType(0);
1130 // fold (sext c1) -> c1
1132 return DAG.getConstant(N0C->getSignExtended(), VT);
1133 // fold (sext (sext x)) -> (sext x)
1134 if (N0.getOpcode() == ISD::SIGN_EXTEND)
1135 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
1139 SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) {
1140 SDOperand N0 = N->getOperand(0);
1141 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1142 MVT::ValueType VT = N->getValueType(0);
1144 // fold (zext c1) -> c1
1146 return DAG.getConstant(N0C->getValue(), VT);
1147 // fold (zext (zext x)) -> (zext x)
1148 if (N0.getOpcode() == ISD::ZERO_EXTEND)
1149 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0));
1153 SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
1154 SDOperand N0 = N->getOperand(0);
1155 SDOperand N1 = N->getOperand(1);
1156 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1157 MVT::ValueType VT = N->getValueType(0);
1158 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
1160 // fold (sext_in_reg c1) -> c1
1162 SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT);
1163 return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate);
1165 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1
1166 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1167 cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) {
1170 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
1171 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1172 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
1173 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
1175 // fold (sext_in_reg (assert_sext x)) -> (assert_sext x)
1176 if (N0.getOpcode() == ISD::AssertSext &&
1177 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
1180 // fold (sext_in_reg (sextload x)) -> (sextload x)
1181 if (N0.getOpcode() == ISD::SEXTLOAD &&
1182 cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) {
1185 // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1
1186 // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here
1187 if (N0.getOpcode() == ISD::SETCC &&
1188 TLI.getSetCCResultContents() ==
1189 TargetLowering::ZeroOrNegativeOneSetCCResult)
1191 // FIXME: this code is currently just ported over from SelectionDAG.cpp
1192 // we probably actually want to handle this in two pieces. Rather than
1193 // checking all the top bits for zero, just check the sign bit here and turn
1194 // it into a zero extend inreg (AND with constant).
1195 // then, let the code for AND figure out if the mask is superfluous rather
1196 // than doing so here.
1197 if (N0.getOpcode() == ISD::AND &&
1198 N0.getOperand(1).getOpcode() == ISD::Constant) {
1199 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1200 unsigned NumBits = MVT::getSizeInBits(EVT);
1201 if ((Mask & (~0ULL << (NumBits-1))) == 0)
1207 SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) {
1208 SDOperand N0 = N->getOperand(0);
1209 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1210 MVT::ValueType VT = N->getValueType(0);
1213 if (N0.getValueType() == N->getValueType(0))
1215 // fold (truncate c1) -> c1
1217 return DAG.getConstant(N0C->getValue(), VT);
1218 // fold (truncate (truncate x)) -> (truncate x)
1219 if (N0.getOpcode() == ISD::TRUNCATE)
1220 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
1221 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x
1222 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){
1223 if (N0.getValueType() < VT)
1224 // if the source is smaller than the dest, we still need an extend
1225 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
1226 else if (N0.getValueType() > VT)
1227 // if the source is larger than the dest, than we just need the truncate
1228 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
1230 // if the source and dest are the same type, we can drop both the extend
1232 return N0.getOperand(0);
1237 SDOperand DAGCombiner::visitFADD(SDNode *N) {
1238 SDOperand N0 = N->getOperand(0);
1239 SDOperand N1 = N->getOperand(1);
1240 MVT::ValueType VT = N->getValueType(0);
1242 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1243 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1244 // fold floating point (fadd c1, c2)
1245 return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(),
1246 N->getValueType(0));
1248 // fold (A + (-B)) -> A-B
1249 if (N1.getOpcode() == ISD::FNEG)
1250 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0));
1252 // fold ((-A) + B) -> B-A
1253 if (N0.getOpcode() == ISD::FNEG)
1254 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0));
1259 SDOperand DAGCombiner::visitFSUB(SDNode *N) {
1260 SDOperand N0 = N->getOperand(0);
1261 SDOperand N1 = N->getOperand(1);
1262 MVT::ValueType VT = N->getValueType(0);
1264 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1265 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1266 // fold floating point (fsub c1, c2)
1267 return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(),
1268 N->getValueType(0));
1270 // fold (A-(-B)) -> A+B
1271 if (N1.getOpcode() == ISD::FNEG)
1272 return DAG.getNode(ISD::FADD, N0.getValueType(), N0, N1.getOperand(0));
1277 SDOperand DAGCombiner::visitFMUL(SDNode *N) {
1278 SDOperand N0 = N->getOperand(0);
1279 SDOperand N1 = N->getOperand(1);
1280 MVT::ValueType VT = N->getValueType(0);
1282 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1283 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1284 // fold floating point (fmul c1, c2)
1285 return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(),
1286 N->getValueType(0));
1291 SDOperand DAGCombiner::visitFDIV(SDNode *N) {
1292 SDOperand N0 = N->getOperand(0);
1293 SDOperand N1 = N->getOperand(1);
1294 MVT::ValueType VT = N->getValueType(0);
1296 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1297 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1298 // fold floating point (fdiv c1, c2)
1299 return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(),
1300 N->getValueType(0));
1305 SDOperand DAGCombiner::visitFREM(SDNode *N) {
1306 SDOperand N0 = N->getOperand(0);
1307 SDOperand N1 = N->getOperand(1);
1308 MVT::ValueType VT = N->getValueType(0);
1310 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1311 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1312 // fold floating point (frem c1, c2) -> fmod(c1, c2)
1313 return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()),
1314 N->getValueType(0));
1320 SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) {
1321 SDOperand N0 = N->getOperand(0);
1322 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1324 // fold (sint_to_fp c1) -> c1fp
1326 return DAG.getConstantFP(N0C->getSignExtended(), N->getValueType(0));
1330 SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) {
1331 SDOperand N0 = N->getOperand(0);
1332 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1334 // fold (uint_to_fp c1) -> c1fp
1336 return DAG.getConstantFP(N0C->getValue(), N->getValueType(0));
1340 SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) {
1341 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1343 // fold (fp_to_sint c1fp) -> c1
1345 return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0));
1349 SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) {
1350 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1352 // fold (fp_to_uint c1fp) -> c1
1354 return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0));
1358 SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) {
1359 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1361 // fold (fp_round c1fp) -> c1fp
1363 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0));
1367 SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) {
1368 SDOperand N0 = N->getOperand(0);
1369 MVT::ValueType VT = N->getValueType(0);
1370 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
1371 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
1373 // fold (fp_round_inreg c1fp) -> c1fp
1375 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
1376 return DAG.getNode(ISD::FP_EXTEND, VT, Round);
1381 SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) {
1382 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1384 // fold (fp_extend c1fp) -> c1fp
1386 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0));
1390 SDOperand DAGCombiner::visitFNEG(SDNode *N) {
1391 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1392 // fold (neg c1) -> -c1
1394 return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0));
1395 // fold (neg (sub x, y)) -> (sub y, x)
1396 if (N->getOperand(0).getOpcode() == ISD::SUB)
1397 return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1),
1399 // fold (neg (neg x)) -> x
1400 if (N->getOperand(0).getOpcode() == ISD::FNEG)
1401 return N->getOperand(0).getOperand(0);
1405 SDOperand DAGCombiner::visitFABS(SDNode *N) {
1406 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1407 // fold (fabs c1) -> fabs(c1)
1409 return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0));
1410 // fold (fabs (fabs x)) -> (fabs x)
1411 if (N->getOperand(0).getOpcode() == ISD::FABS)
1412 return N->getOperand(0);
1413 // fold (fabs (fneg x)) -> (fabs x)
1414 if (N->getOperand(0).getOpcode() == ISD::FNEG)
1415 return DAG.getNode(ISD::FABS, N->getValueType(0),
1416 N->getOperand(0).getOperand(0));
1420 SDOperand DAGCombiner::visitBRCOND(SDNode *N) {
1421 SDOperand Chain = N->getOperand(0);
1422 SDOperand N1 = N->getOperand(1);
1423 SDOperand N2 = N->getOperand(2);
1424 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1426 // never taken branch, fold to chain
1427 if (N1C && N1C->isNullValue())
1429 // unconditional branch
1430 if (N1C && N1C->getValue() == 1)
1431 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
1435 SDOperand DAGCombiner::visitBRCONDTWOWAY(SDNode *N) {
1436 SDOperand Chain = N->getOperand(0);
1437 SDOperand N1 = N->getOperand(1);
1438 SDOperand N2 = N->getOperand(2);
1439 SDOperand N3 = N->getOperand(3);
1440 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1442 // unconditional branch to true mbb
1443 if (N1C && N1C->getValue() == 1)
1444 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
1445 // unconditional branch to false mbb
1446 if (N1C && N1C->isNullValue())
1447 return DAG.getNode(ISD::BR, MVT::Other, Chain, N3);
1451 // Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB.
1453 SDOperand DAGCombiner::visitBR_CC(SDNode *N) {
1454 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1));
1455 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3);
1457 // Use SimplifySetCC to simplify SETCC's.
1458 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false);
1459 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val);
1461 // fold br_cc true, dest -> br dest (unconditional branch)
1462 if (SCCC && SCCC->getValue())
1463 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0),
1465 // fold br_cc false, dest -> unconditional fall through
1466 if (SCCC && SCCC->isNullValue())
1467 return N->getOperand(0);
1468 // fold to a simpler setcc
1469 if (Simp.Val && Simp.getOpcode() == ISD::SETCC)
1470 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0),
1471 Simp.getOperand(2), Simp.getOperand(0),
1472 Simp.getOperand(1), N->getOperand(4));
1476 SDOperand DAGCombiner::visitBRTWOWAY_CC(SDNode *N) {
1477 SDOperand Chain = N->getOperand(0);
1478 SDOperand CCN = N->getOperand(1);
1479 SDOperand LHS = N->getOperand(2);
1480 SDOperand RHS = N->getOperand(3);
1481 SDOperand N4 = N->getOperand(4);
1482 SDOperand N5 = N->getOperand(5);
1484 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), LHS, RHS,
1485 cast<CondCodeSDNode>(CCN)->get(), false);
1486 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1488 // fold select_cc lhs, rhs, x, x, cc -> x
1490 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4);
1491 // fold select_cc true, x, y -> x
1492 if (SCCC && SCCC->getValue())
1493 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4);
1494 // fold select_cc false, x, y -> y
1495 if (SCCC && SCCC->isNullValue())
1496 return DAG.getNode(ISD::BR, MVT::Other, Chain, N5);
1497 // fold to a simpler setcc
1498 if (SCC.Val && SCC.getOpcode() == ISD::SETCC)
1499 return DAG.getBR2Way_CC(Chain, SCC.getOperand(2), SCC.getOperand(0),
1500 SCC.getOperand(1), N4, N5);
1504 SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){
1505 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!");
1507 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2,
1508 cast<CondCodeSDNode>(N0.getOperand(2))->get());
1509 // If we got a simplified select_cc node back from SimplifySelectCC, then
1510 // break it down into a new SETCC node, and a new SELECT node, and then return
1511 // the SELECT node, since we were called with a SELECT node.
1513 // Check to see if we got a select_cc back (to turn into setcc/select).
1514 // Otherwise, just return whatever node we got back, like fabs.
1515 if (SCC.getOpcode() == ISD::SELECT_CC) {
1516 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(),
1517 SCC.getOperand(0), SCC.getOperand(1),
1519 WorkList.push_back(SETCC.Val);
1520 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2),
1521 SCC.getOperand(3), SETCC);
1528 SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1,
1529 SDOperand N2, SDOperand N3,
1532 MVT::ValueType VT = N2.getValueType();
1533 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
1534 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1535 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1536 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1538 // Determine if the condition we're dealing with is constant
1539 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
1540 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1542 // fold select_cc true, x, y -> x
1543 if (SCCC && SCCC->getValue())
1545 // fold select_cc false, x, y -> y
1546 if (SCCC && SCCC->getValue() == 0)
1549 // Check to see if we can simplify the select into an fabs node
1550 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1551 // Allow either -0.0 or 0.0
1552 if (CFP->getValue() == 0.0) {
1553 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
1554 if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
1555 N0 == N2 && N3.getOpcode() == ISD::FNEG &&
1556 N2 == N3.getOperand(0))
1557 return DAG.getNode(ISD::FABS, VT, N0);
1559 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs
1560 if ((CC == ISD::SETLT || CC == ISD::SETLE) &&
1561 N0 == N3 && N2.getOpcode() == ISD::FNEG &&
1562 N2.getOperand(0) == N3)
1563 return DAG.getNode(ISD::FABS, VT, N3);
1567 // Check to see if we can perform the "gzip trick", transforming
1568 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A
1569 if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() &&
1570 MVT::isInteger(N0.getValueType()) &&
1571 MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) {
1572 MVT::ValueType XType = N0.getValueType();
1573 MVT::ValueType AType = N2.getValueType();
1574 if (XType >= AType) {
1575 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a
1576 // single-bit constant. FIXME: remove once the dag combiner
1578 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) {
1579 unsigned ShCtV = Log2_64(N2C->getValue());
1580 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
1581 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy());
1582 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt);
1583 WorkList.push_back(Shift.Val);
1584 if (XType > AType) {
1585 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
1586 WorkList.push_back(Shift.Val);
1588 return DAG.getNode(ISD::AND, AType, Shift, N2);
1590 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
1591 DAG.getConstant(MVT::getSizeInBits(XType)-1,
1592 TLI.getShiftAmountTy()));
1593 WorkList.push_back(Shift.Val);
1594 if (XType > AType) {
1595 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
1596 WorkList.push_back(Shift.Val);
1598 return DAG.getNode(ISD::AND, AType, Shift, N2);
1602 // Check to see if this is the equivalent of setcc
1603 // FIXME: Turn all of these into setcc if setcc if setcc is legal
1604 // otherwise, go ahead with the folds.
1605 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) {
1606 MVT::ValueType XType = N0.getValueType();
1607 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) {
1608 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
1609 if (Res.getValueType() != VT)
1610 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res);
1614 // seteq X, 0 -> srl (ctlz X, log2(size(X)))
1615 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ &&
1616 TLI.isOperationLegal(ISD::CTLZ, XType)) {
1617 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0);
1618 return DAG.getNode(ISD::SRL, XType, Ctlz,
1619 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)),
1620 TLI.getShiftAmountTy()));
1622 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1)
1623 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) {
1624 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType),
1626 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0,
1627 DAG.getConstant(~0ULL, XType));
1628 return DAG.getNode(ISD::SRL, XType,
1629 DAG.getNode(ISD::AND, XType, NegN0, NotN0),
1630 DAG.getConstant(MVT::getSizeInBits(XType)-1,
1631 TLI.getShiftAmountTy()));
1633 // setgt X, -1 -> xor (srl (X, size(X)-1), 1)
1634 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) {
1635 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0,
1636 DAG.getConstant(MVT::getSizeInBits(XType)-1,
1637 TLI.getShiftAmountTy()));
1638 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType));
1642 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X ->
1643 // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
1644 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) &&
1645 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) {
1646 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) {
1647 MVT::ValueType XType = N0.getValueType();
1648 if (SubC->isNullValue() && MVT::isInteger(XType)) {
1649 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
1650 DAG.getConstant(MVT::getSizeInBits(XType)-1,
1651 TLI.getShiftAmountTy()));
1652 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
1653 WorkList.push_back(Shift.Val);
1654 WorkList.push_back(Add.Val);
1655 return DAG.getNode(ISD::XOR, XType, Add, Shift);
1663 SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0,
1664 SDOperand N1, ISD::CondCode Cond,
1665 bool foldBooleans) {
1666 // These setcc operations always fold.
1670 case ISD::SETFALSE2: return DAG.getConstant(0, VT);
1672 case ISD::SETTRUE2: return DAG.getConstant(1, VT);
1675 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
1676 uint64_t C1 = N1C->getValue();
1677 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) {
1678 uint64_t C0 = N0C->getValue();
1680 // Sign extend the operands if required
1681 if (ISD::isSignedIntSetCC(Cond)) {
1682 C0 = N0C->getSignExtended();
1683 C1 = N1C->getSignExtended();
1687 default: assert(0 && "Unknown integer setcc!");
1688 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT);
1689 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT);
1690 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT);
1691 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT);
1692 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT);
1693 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT);
1694 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT);
1695 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT);
1696 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT);
1697 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT);
1700 // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
1701 if (N0.getOpcode() == ISD::ZERO_EXTEND) {
1702 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
1704 // If the comparison constant has bits in the upper part, the
1705 // zero-extended value could never match.
1706 if (C1 & (~0ULL << InSize)) {
1707 unsigned VSize = MVT::getSizeInBits(N0.getValueType());
1711 case ISD::SETEQ: return DAG.getConstant(0, VT);
1714 case ISD::SETNE: return DAG.getConstant(1, VT);
1717 // True if the sign bit of C1 is set.
1718 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT);
1721 // True if the sign bit of C1 isn't set.
1722 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT);
1728 // Otherwise, we can perform the comparison with the low bits.
1736 return DAG.getSetCC(VT, N0.getOperand(0),
1737 DAG.getConstant(C1, N0.getOperand(0).getValueType()),
1740 break; // todo, be more careful with signed comparisons
1742 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1743 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1744 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
1745 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
1746 MVT::ValueType ExtDstTy = N0.getValueType();
1747 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
1749 // If the extended part has any inconsistent bits, it cannot ever
1750 // compare equal. In other words, they have to be all ones or all
1753 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
1754 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
1755 return DAG.getConstant(Cond == ISD::SETNE, VT);
1758 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
1759 if (Op0Ty == ExtSrcTy) {
1760 ZextOp = N0.getOperand(0);
1762 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
1763 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
1764 DAG.getConstant(Imm, Op0Ty));
1766 WorkList.push_back(ZextOp.Val);
1767 // Otherwise, make this a use of a zext.
1768 return DAG.getSetCC(VT, ZextOp,
1769 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)),
1774 uint64_t MinVal, MaxVal;
1775 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
1776 if (ISD::isSignedIntSetCC(Cond)) {
1777 MinVal = 1ULL << (OperandBitSize-1);
1778 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined.
1779 MaxVal = ~0ULL >> (65-OperandBitSize);
1784 MaxVal = ~0ULL >> (64-OperandBitSize);
1787 // Canonicalize GE/LE comparisons to use GT/LT comparisons.
1788 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
1789 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true
1790 --C1; // X >= C0 --> X > (C0-1)
1791 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1792 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
1795 if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
1796 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true
1797 ++C1; // X <= C0 --> X < (C0+1)
1798 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1799 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
1802 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
1803 return DAG.getConstant(0, VT); // X < MIN --> false
1805 // Canonicalize setgt X, Min --> setne X, Min
1806 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
1807 return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
1809 // If we have setult X, 1, turn it into seteq X, 0
1810 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
1811 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
1813 // If we have setugt X, Max-1, turn it into seteq X, Max
1814 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
1815 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
1818 // If we have "setcc X, C0", check to see if we can shrink the immediate
1821 // SETUGT X, SINTMAX -> SETLT X, 0
1822 if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
1823 C1 == (~0ULL >> (65-OperandBitSize)))
1824 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
1827 // FIXME: Implement the rest of these.
1829 // Fold bit comparisons when we can.
1830 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1831 VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
1832 if (ConstantSDNode *AndRHS =
1833 dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1834 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3
1835 // Perform the xform if the AND RHS is a single bit.
1836 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
1837 return DAG.getNode(ISD::SRL, VT, N0,
1838 DAG.getConstant(Log2_64(AndRHS->getValue()),
1839 TLI.getShiftAmountTy()));
1841 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
1842 // (X & 8) == 8 --> (X & 8) >> 3
1843 // Perform the xform if C1 is a single bit.
1844 if ((C1 & (C1-1)) == 0) {
1845 return DAG.getNode(ISD::SRL, VT, N0,
1846 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy()));
1851 } else if (isa<ConstantSDNode>(N0.Val)) {
1852 // Ensure that the constant occurs on the RHS.
1853 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
1856 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val))
1857 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
1858 double C0 = N0C->getValue(), C1 = N1C->getValue();
1861 default: break; // FIXME: Implement the rest of these!
1862 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT);
1863 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT);
1864 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT);
1865 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT);
1866 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT);
1867 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT);
1870 // Ensure that the constant occurs on the RHS.
1871 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
1875 // We can always fold X == Y for integer setcc's.
1876 if (MVT::isInteger(N0.getValueType()))
1877 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1878 unsigned UOF = ISD::getUnorderedFlavor(Cond);
1879 if (UOF == 2) // FP operators that are undefined on NaNs.
1880 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1881 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
1882 return DAG.getConstant(UOF, VT);
1883 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO
1884 // if it is not already.
1885 ISD::CondCode NewCond = UOF == 0 ? ISD::SETUO : ISD::SETO;
1886 if (NewCond != Cond)
1887 return DAG.getSetCC(VT, N0, N1, NewCond);
1890 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1891 MVT::isInteger(N0.getValueType())) {
1892 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
1893 N0.getOpcode() == ISD::XOR) {
1894 // Simplify (X+Y) == (X+Z) --> Y == Z
1895 if (N0.getOpcode() == N1.getOpcode()) {
1896 if (N0.getOperand(0) == N1.getOperand(0))
1897 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
1898 if (N0.getOperand(1) == N1.getOperand(1))
1899 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
1900 if (isCommutativeBinOp(N0.getOpcode())) {
1901 // If X op Y == Y op X, try other combinations.
1902 if (N0.getOperand(0) == N1.getOperand(1))
1903 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
1904 if (N0.getOperand(1) == N1.getOperand(0))
1905 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
1909 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. Common for condcodes.
1910 if (N0.getOpcode() == ISD::XOR)
1911 if (ConstantSDNode *XORC = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
1912 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
1913 // If we know that all of the inverted bits are zero, don't bother
1914 // performing the inversion.
1915 if (MaskedValueIsZero(N0.getOperand(0), ~XORC->getValue(), TLI))
1916 return DAG.getSetCC(VT, N0.getOperand(0),
1917 DAG.getConstant(XORC->getValue()^RHSC->getValue(),
1918 N0.getValueType()), Cond);
1921 // Simplify (X+Z) == X --> Z == 0
1922 if (N0.getOperand(0) == N1)
1923 return DAG.getSetCC(VT, N0.getOperand(1),
1924 DAG.getConstant(0, N0.getValueType()), Cond);
1925 if (N0.getOperand(1) == N1) {
1926 if (isCommutativeBinOp(N0.getOpcode()))
1927 return DAG.getSetCC(VT, N0.getOperand(0),
1928 DAG.getConstant(0, N0.getValueType()), Cond);
1930 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
1931 // (Z-X) == X --> Z == X<<1
1932 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
1934 DAG.getConstant(1,TLI.getShiftAmountTy()));
1935 WorkList.push_back(SH.Val);
1936 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
1941 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
1942 N1.getOpcode() == ISD::XOR) {
1943 // Simplify X == (X+Z) --> Z == 0
1944 if (N1.getOperand(0) == N0) {
1945 return DAG.getSetCC(VT, N1.getOperand(1),
1946 DAG.getConstant(0, N1.getValueType()), Cond);
1947 } else if (N1.getOperand(1) == N0) {
1948 if (isCommutativeBinOp(N1.getOpcode())) {
1949 return DAG.getSetCC(VT, N1.getOperand(0),
1950 DAG.getConstant(0, N1.getValueType()), Cond);
1952 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
1953 // X == (Z-X) --> X<<1 == Z
1954 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0,
1955 DAG.getConstant(1,TLI.getShiftAmountTy()));
1956 WorkList.push_back(SH.Val);
1957 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
1963 // Fold away ALL boolean setcc's.
1965 if (N0.getValueType() == MVT::i1 && foldBooleans) {
1967 default: assert(0 && "Unknown integer setcc!");
1968 case ISD::SETEQ: // X == Y -> (X^Y)^1
1969 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1970 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
1971 WorkList.push_back(Temp.Val);
1973 case ISD::SETNE: // X != Y --> (X^Y)
1974 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1976 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y
1977 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y
1978 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
1979 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
1980 WorkList.push_back(Temp.Val);
1982 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X
1983 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X
1984 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
1985 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
1986 WorkList.push_back(Temp.Val);
1988 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y
1989 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y
1990 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
1991 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
1992 WorkList.push_back(Temp.Val);
1994 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X
1995 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X
1996 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
1997 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
2000 if (VT != MVT::i1) {
2001 WorkList.push_back(N0.Val);
2002 // FIXME: If running after legalize, we probably can't do this.
2003 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
2008 // Could not fold it.
2012 // SelectionDAG::Combine - This is the entry point for the file.
2014 void SelectionDAG::Combine(bool RunningAfterLegalize) {
2015 /// run - This is the main entry point to this class.
2017 DAGCombiner(*this).Run(RunningAfterLegalize);