DAGCombiner.cpp revision ee899e6bfc854adefdbfd6631e206d18fd43ab81
1//===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 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. 7// 8//===----------------------------------------------------------------------===// 9// 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. 12// 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. 18// 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 21// we don't have yet. 22// 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 41// into an undef? 42// FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false 43// 44//===----------------------------------------------------------------------===// 45 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" 52#include <algorithm> 53#include <cmath> 54using namespace llvm; 55 56namespace { 57 Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined"); 58 59 class DAGCombiner { 60 SelectionDAG &DAG; 61 TargetLowering &TLI; 62 bool AfterLegalize; 63 64 // Worklist of all of the nodes that need to be simplified. 65 std::vector<SDNode*> WorkList; 66 67 /// AddUsersToWorkList - When an instruction is simplified, add all users of 68 /// the instruction to the work lists because they might get more simplified 69 /// now. 70 /// 71 void AddUsersToWorkList(SDNode *N) { 72 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 73 UI != UE; ++UI) 74 WorkList.push_back(*UI); 75 } 76 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), 80 WorkList.end()); 81 } 82 83 /// visit - call the node-specific routine that knows how to fold each 84 /// particular type of node. 85 SDOperand visit(SDNode *N); 86 87 // Visitation implementation - Implement dag node combining for different 88 // node types. The semantics are as follows: 89 // Return Value: 90 // SDOperand.Val == 0 - No change was made 91 // otherwise - N should be replaced by the returned Operand. 92 // 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); 119 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); 138 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); 144public: 145 DAGCombiner(SelectionDAG &D) 146 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {} 147 148 /// Run - runs the dag combiner on all nodes in the work list 149 void Run(bool RunningAfterLegalize); 150 }; 151} 152 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. 156static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask, 157 const TargetLowering &TLI) { 158 unsigned SrcBits; 159 if (Mask == 0) return true; 160 161 // If we know the result of a setcc has the top bits zero, use this info. 162 switch (Op.getOpcode()) { 163 case ISD::Constant: 164 return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0; 165 case ISD::SETCC: 166 // FIXME: teach this about non ZeroOrOne values, such as 0 or -1 167 return ((Mask & 1) == 0) && 168 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult; 169 case ISD::ZEXTLOAD: 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. 178 case ISD::AND: 179 // If either of the operands has zero bits, the result will too. 180 if (MaskedValueIsZero(Op.getOperand(1), Mask, TLI) || 181 MaskedValueIsZero(Op.getOperand(0), Mask, TLI)) 182 return true; 183 184 // (X & C1) & C2 == 0 iff C1 & C2 == 0. 185 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 186 return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI); 187 return false; 188 case ISD::OR: 189 case ISD::XOR: 190 return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) && 191 MaskedValueIsZero(Op.getOperand(1), Mask, TLI); 192 case ISD::SELECT: 193 return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) && 194 MaskedValueIsZero(Op.getOperand(2), Mask, TLI); 195 case ISD::SELECT_CC: 196 return MaskedValueIsZero(Op.getOperand(2), Mask, TLI) && 197 MaskedValueIsZero(Op.getOperand(3), Mask, TLI); 198 case ISD::SRL: 199 // (ushr X, C1) & C2 == 0 iff X & (C2 << C1) == 0 200 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 201 uint64_t NewVal = Mask << ShAmt->getValue(); 202 SrcBits = MVT::getSizeInBits(Op.getValueType()); 203 if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1; 204 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI); 205 } 206 return false; 207 case ISD::SHL: 208 // (ushl X, C1) & C2 == 0 iff X & (C2 >> C1) == 0 209 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 210 uint64_t NewVal = Mask >> ShAmt->getValue(); 211 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI); 212 } 213 return false; 214 case ISD::SUB: 215 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) { 216 // We know that the top bits of C-X are clear if X contains less bits 217 // than C (i.e. no wrap-around can happen). For example, 20-X is 218 // positive if we can prove that X is >= 0 and < 16. 219 unsigned Bits = MVT::getSizeInBits(CLHS->getValueType(0)); 220 if ((CLHS->getValue() & (1 << (Bits-1))) == 0) { // sign bit clear 221 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 222 uint64_t MaskV = (1ULL << (63-NLZ))-1; 223 if (MaskedValueIsZero(Op.getOperand(1), ~MaskV, TLI)) { 224 // High bits are clear this value is known to be >= C. 225 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 226 if ((Mask & ((1ULL << (64-NLZ2))-1)) == 0) 227 return true; 228 } 229 } 230 } 231 break; 232 case ISD::CTTZ: 233 case ISD::CTLZ: 234 case ISD::CTPOP: 235 // Bit counting instructions can not set the high bits of the result 236 // register. The max number of bits sets depends on the input. 237 return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0; 238 239 // TODO we could handle some SRA cases here. 240 default: break; 241 } 242 return false; 243} 244 245// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 246// that selects between the values 1 and 0, making it equivalent to a setcc. 247// Also, set the incoming LHS, RHS, and CC references to the appropriate 248// nodes based on the type of node we are checking. This simplifies life a 249// bit for the callers. 250static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 251 SDOperand &CC) { 252 if (N.getOpcode() == ISD::SETCC) { 253 LHS = N.getOperand(0); 254 RHS = N.getOperand(1); 255 CC = N.getOperand(2); 256 return true; 257 } 258 if (N.getOpcode() == ISD::SELECT_CC && 259 N.getOperand(2).getOpcode() == ISD::Constant && 260 N.getOperand(3).getOpcode() == ISD::Constant && 261 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 262 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 263 LHS = N.getOperand(0); 264 RHS = N.getOperand(1); 265 CC = N.getOperand(4); 266 return true; 267 } 268 return false; 269} 270 271// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 272// one use. If this is true, it allows the users to invert the operation for 273// free when it is profitable to do so. 274static bool isOneUseSetCC(SDOperand N) { 275 SDOperand N0, N1, N2; 276 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 277 return true; 278 return false; 279} 280 281// FIXME: This should probably go in the ISD class rather than being duplicated 282// in several files. 283static bool isCommutativeBinOp(unsigned Opcode) { 284 switch (Opcode) { 285 case ISD::ADD: 286 case ISD::MUL: 287 case ISD::AND: 288 case ISD::OR: 289 case ISD::XOR: return true; 290 default: return false; // FIXME: Need commutative info for user ops! 291 } 292} 293 294void DAGCombiner::Run(bool RunningAfterLegalize) { 295 // set the instance variable, so that the various visit routines may use it. 296 AfterLegalize = RunningAfterLegalize; 297 298 // Add all the dag nodes to the worklist. 299 WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end()); 300 301 // Create a dummy node (which is not added to allnodes), that adds a reference 302 // to the root node, preventing it from being deleted, and tracking any 303 // changes of the root. 304 HandleSDNode Dummy(DAG.getRoot()); 305 306 // while the worklist isn't empty, inspect the node on the end of it and 307 // try and combine it. 308 while (!WorkList.empty()) { 309 SDNode *N = WorkList.back(); 310 WorkList.pop_back(); 311 312 // If N has no uses, it is dead. Make sure to revisit all N's operands once 313 // N is deleted from the DAG, since they too may now be dead or may have a 314 // reduced number of uses, allowing other xforms. 315 if (N->use_empty() && N != &Dummy) { 316 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 317 WorkList.push_back(N->getOperand(i).Val); 318 319 removeFromWorkList(N); 320 DAG.DeleteNode(N); 321 continue; 322 } 323 324 SDOperand RV = visit(N); 325 if (RV.Val) { 326 ++NodesCombined; 327 // If we get back the same node we passed in, rather than a new node or 328 // zero, we know that the node must have defined multiple values and 329 // CombineTo was used. Since CombineTo takes care of the worklist 330 // mechanics for us, we have no work to do in this case. 331 if (RV.Val != N) { 332 DEBUG(std::cerr << "\nReplacing "; N->dump(); 333 std::cerr << "\nWith: "; RV.Val->dump(); 334 std::cerr << '\n'); 335 DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV)); 336 337 // Push the new node and any users onto the worklist 338 WorkList.push_back(RV.Val); 339 AddUsersToWorkList(RV.Val); 340 341 // Nodes can end up on the worklist more than once. Make sure we do 342 // not process a node that has been replaced. 343 removeFromWorkList(N); 344 345 // Finally, since the node is now dead, remove it from the graph. 346 DAG.DeleteNode(N); 347 } 348 } 349 } 350 351 // If the root changed (e.g. it was a dead load, update the root). 352 DAG.setRoot(Dummy.getValue()); 353} 354 355SDOperand DAGCombiner::visit(SDNode *N) { 356 switch(N->getOpcode()) { 357 default: break; 358 case ISD::TokenFactor: return visitTokenFactor(N); 359 case ISD::ADD: return visitADD(N); 360 case ISD::SUB: return visitSUB(N); 361 case ISD::MUL: return visitMUL(N); 362 case ISD::SDIV: return visitSDIV(N); 363 case ISD::UDIV: return visitUDIV(N); 364 case ISD::SREM: return visitSREM(N); 365 case ISD::UREM: return visitUREM(N); 366 case ISD::MULHU: return visitMULHU(N); 367 case ISD::MULHS: return visitMULHS(N); 368 case ISD::AND: return visitAND(N); 369 case ISD::OR: return visitOR(N); 370 case ISD::XOR: return visitXOR(N); 371 case ISD::SHL: return visitSHL(N); 372 case ISD::SRA: return visitSRA(N); 373 case ISD::SRL: return visitSRL(N); 374 case ISD::CTLZ: return visitCTLZ(N); 375 case ISD::CTTZ: return visitCTTZ(N); 376 case ISD::CTPOP: return visitCTPOP(N); 377 case ISD::SELECT: return visitSELECT(N); 378 case ISD::SELECT_CC: return visitSELECT_CC(N); 379 case ISD::SETCC: return visitSETCC(N); 380 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 381 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 382 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 383 case ISD::TRUNCATE: return visitTRUNCATE(N); 384 case ISD::FADD: return visitFADD(N); 385 case ISD::FSUB: return visitFSUB(N); 386 case ISD::FMUL: return visitFMUL(N); 387 case ISD::FDIV: return visitFDIV(N); 388 case ISD::FREM: return visitFREM(N); 389 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 390 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 391 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 392 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 393 case ISD::FP_ROUND: return visitFP_ROUND(N); 394 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 395 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 396 case ISD::FNEG: return visitFNEG(N); 397 case ISD::FABS: return visitFABS(N); 398 case ISD::BRCOND: return visitBRCOND(N); 399 case ISD::BRCONDTWOWAY: return visitBRCONDTWOWAY(N); 400 case ISD::BR_CC: return visitBR_CC(N); 401 case ISD::BRTWOWAY_CC: return visitBRTWOWAY_CC(N); 402 } 403 return SDOperand(); 404} 405 406SDOperand DAGCombiner::visitTokenFactor(SDNode *N) { 407 // If the token factor has two operands and one is the entry token, replace 408 // the token factor with the other operand. 409 if (N->getNumOperands() == 2) { 410 if (N->getOperand(0).getOpcode() == ISD::EntryToken) 411 return N->getOperand(1); 412 if (N->getOperand(1).getOpcode() == ISD::EntryToken) 413 return N->getOperand(0); 414 } 415 return SDOperand(); 416} 417 418SDOperand DAGCombiner::visitADD(SDNode *N) { 419 SDOperand N0 = N->getOperand(0); 420 SDOperand N1 = N->getOperand(1); 421 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 422 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 423 MVT::ValueType VT = N0.getValueType(); 424 425 // fold (add c1, c2) -> c1+c2 426 if (N0C && N1C) 427 return DAG.getConstant(N0C->getValue() + N1C->getValue(), VT); 428 // canonicalize constant to RHS 429 if (N0C && !N1C) { 430 std::swap(N0, N1); 431 std::swap(N0C, N1C); 432 } 433 // fold (add x, 0) -> x 434 if (N1C && N1C->isNullValue()) 435 return N0; 436 // fold (add (add x, c1), c2) -> (add x, c1+c2) 437 if (N1C && N0.getOpcode() == ISD::ADD) { 438 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 439 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 440 if (N00C) 441 return DAG.getNode(ISD::ADD, VT, N0.getOperand(1), 442 DAG.getConstant(N1C->getValue()+N00C->getValue(), VT)); 443 if (N01C) 444 return DAG.getNode(ISD::ADD, VT, N0.getOperand(0), 445 DAG.getConstant(N1C->getValue()+N01C->getValue(), VT)); 446 } 447 // fold ((0-A) + B) -> B-A 448 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 449 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 450 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 451 // fold (A + (0-B)) -> A-B 452 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 453 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 454 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 455 // fold (A+(B-A)) -> B 456 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1)) 457 return N1.getOperand(0); 458 return SDOperand(); 459} 460 461SDOperand DAGCombiner::visitSUB(SDNode *N) { 462 SDOperand N0 = N->getOperand(0); 463 SDOperand N1 = N->getOperand(1); 464 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 465 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 466 467 // fold (sub c1, c2) -> c1-c2 468 if (N0C && N1C) 469 return DAG.getConstant(N0C->getValue() - N1C->getValue(), 470 N->getValueType(0)); 471 // fold (sub x, 0) -> x 472 if (N1C && N1C->isNullValue()) 473 return N0; 474 // fold (A+B)-A -> B 475 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1) 476 return N0.getOperand(1); 477 // fold (A+B)-B -> A 478 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1) 479 return N0.getOperand(0); 480 return SDOperand(); 481} 482 483SDOperand DAGCombiner::visitMUL(SDNode *N) { 484 SDOperand N0 = N->getOperand(0); 485 SDOperand N1 = N->getOperand(1); 486 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 487 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 488 MVT::ValueType VT = N0.getValueType(); 489 490 // fold (mul c1, c2) -> c1*c2 491 if (N0C && N1C) 492 return DAG.getConstant(N0C->getValue() * N1C->getValue(), 493 N->getValueType(0)); 494 // canonicalize constant to RHS 495 if (N0C && !N1C) { 496 std::swap(N0, N1); 497 std::swap(N0C, N1C); 498 } 499 // fold (mul x, 0) -> 0 500 if (N1C && N1C->isNullValue()) 501 return N1; 502 // fold (mul x, -1) -> 0-x 503 if (N1C && N1C->isAllOnesValue()) 504 return DAG.getNode(ISD::SUB, N->getValueType(0), 505 DAG.getConstant(0, N->getValueType(0)), N0); 506 // fold (mul x, (1 << c)) -> x << c 507 if (N1C && isPowerOf2_64(N1C->getValue())) 508 return DAG.getNode(ISD::SHL, N->getValueType(0), N0, 509 DAG.getConstant(Log2_64(N1C->getValue()), 510 TLI.getShiftAmountTy())); 511 // fold (mul (mul x, c1), c2) -> (mul x, c1*c2) 512 if (N1C && N0.getOpcode() == ISD::MUL) { 513 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 514 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 515 if (N00C) 516 return DAG.getNode(ISD::MUL, VT, N0.getOperand(1), 517 DAG.getConstant(N1C->getValue()*N00C->getValue(), VT)); 518 if (N01C) 519 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), 520 DAG.getConstant(N1C->getValue()*N01C->getValue(), VT)); 521 } 522 return SDOperand(); 523} 524 525SDOperand DAGCombiner::visitSDIV(SDNode *N) { 526 SDOperand N0 = N->getOperand(0); 527 SDOperand N1 = N->getOperand(1); 528 MVT::ValueType VT = N->getValueType(0); 529 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 530 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 531 532 // fold (sdiv c1, c2) -> c1/c2 533 if (N0C && N1C && !N1C->isNullValue()) 534 return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(), 535 N->getValueType(0)); 536 537 // If we know the sign bits of both operands are zero, strength reduce to a 538 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 539 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 540 if (MaskedValueIsZero(N1, SignBit, TLI) && 541 MaskedValueIsZero(N0, SignBit, TLI)) 542 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 543 544 545 return SDOperand(); 546} 547 548SDOperand DAGCombiner::visitUDIV(SDNode *N) { 549 SDOperand N0 = N->getOperand(0); 550 SDOperand N1 = N->getOperand(1); 551 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 552 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 553 554 // fold (udiv c1, c2) -> c1/c2 555 if (N0C && N1C && !N1C->isNullValue()) 556 return DAG.getConstant(N0C->getValue() / N1C->getValue(), 557 N->getValueType(0)); 558 // fold (udiv x, (1 << c)) -> x >>u c 559 if (N1C && isPowerOf2_64(N1C->getValue())) 560 return DAG.getNode(ISD::SRL, N->getValueType(0), N0, 561 DAG.getConstant(Log2_64(N1C->getValue()), 562 TLI.getShiftAmountTy())); 563 return SDOperand(); 564} 565 566SDOperand DAGCombiner::visitSREM(SDNode *N) { 567 SDOperand N0 = N->getOperand(0); 568 SDOperand N1 = N->getOperand(1); 569 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 570 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 571 572 // fold (srem c1, c2) -> c1%c2 573 if (N0C && N1C && !N1C->isNullValue()) 574 return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(), 575 N->getValueType(0)); 576 return SDOperand(); 577} 578 579SDOperand DAGCombiner::visitUREM(SDNode *N) { 580 SDOperand N0 = N->getOperand(0); 581 SDOperand N1 = N->getOperand(1); 582 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 583 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 584 585 // fold (urem c1, c2) -> c1%c2 586 if (N0C && N1C && !N1C->isNullValue()) 587 return DAG.getConstant(N0C->getValue() % N1C->getValue(), 588 N->getValueType(0)); 589 // FIXME: c2 power of 2 -> mask? 590 return SDOperand(); 591} 592 593SDOperand DAGCombiner::visitMULHS(SDNode *N) { 594 SDOperand N0 = N->getOperand(0); 595 SDOperand N1 = N->getOperand(1); 596 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 597 598 // fold (mulhs x, 0) -> 0 599 if (N1C && N1C->isNullValue()) 600 return N1; 601 // fold (mulhs x, 1) -> (sra x, size(x)-1) 602 if (N1C && N1C->getValue() == 1) 603 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 604 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 605 TLI.getShiftAmountTy())); 606 return SDOperand(); 607} 608 609SDOperand DAGCombiner::visitMULHU(SDNode *N) { 610 SDOperand N0 = N->getOperand(0); 611 SDOperand N1 = N->getOperand(1); 612 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 613 614 // fold (mulhu x, 0) -> 0 615 if (N1C && N1C->isNullValue()) 616 return N1; 617 // fold (mulhu x, 1) -> 0 618 if (N1C && N1C->getValue() == 1) 619 return DAG.getConstant(0, N0.getValueType()); 620 return SDOperand(); 621} 622 623SDOperand DAGCombiner::visitAND(SDNode *N) { 624 SDOperand N0 = N->getOperand(0); 625 SDOperand N1 = N->getOperand(1); 626 SDOperand LL, LR, RL, RR, CC0, CC1; 627 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 628 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 629 MVT::ValueType VT = N1.getValueType(); 630 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 631 632 // fold (and c1, c2) -> c1&c2 633 if (N0C && N1C) 634 return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT); 635 // canonicalize constant to RHS 636 if (N0C && !N1C) { 637 std::swap(N0, N1); 638 std::swap(N0C, N1C); 639 } 640 // fold (and x, -1) -> x 641 if (N1C && N1C->isAllOnesValue()) 642 return N0; 643 // if (and x, c) is known to be zero, return 0 644 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 645 return DAG.getConstant(0, VT); 646 // fold (and x, c) -> x iff (x & ~c) == 0 647 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 648 TLI)) 649 return N0; 650 // fold (and (and x, c1), c2) -> (and x, c1^c2) 651 if (N1C && N0.getOpcode() == ISD::AND) { 652 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 653 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 654 if (N00C) 655 return DAG.getNode(ISD::AND, VT, N0.getOperand(1), 656 DAG.getConstant(N1C->getValue()&N00C->getValue(), VT)); 657 if (N01C) 658 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 659 DAG.getConstant(N1C->getValue()&N01C->getValue(), VT)); 660 } 661 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 662 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) { 663 unsigned ExtendBits = 664 MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT()); 665 if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0) 666 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1); 667 } 668 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 669 if (N0.getOpcode() == ISD::OR) 670 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 671 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 672 return N1; 673 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 674 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 675 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 676 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 677 678 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 679 MVT::isInteger(LL.getValueType())) { 680 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 681 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 682 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 683 WorkList.push_back(ORNode.Val); 684 return DAG.getSetCC(VT, ORNode, LR, Op1); 685 } 686 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 687 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 688 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 689 WorkList.push_back(ANDNode.Val); 690 return DAG.getSetCC(VT, ANDNode, LR, Op1); 691 } 692 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 693 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 694 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 695 WorkList.push_back(ORNode.Val); 696 return DAG.getSetCC(VT, ORNode, LR, Op1); 697 } 698 } 699 // canonicalize equivalent to ll == rl 700 if (LL == RR && LR == RL) { 701 Op1 = ISD::getSetCCSwappedOperands(Op1); 702 std::swap(RL, RR); 703 } 704 if (LL == RL && LR == RR) { 705 bool isInteger = MVT::isInteger(LL.getValueType()); 706 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 707 if (Result != ISD::SETCC_INVALID) 708 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 709 } 710 } 711 // fold (and (zext x), (zext y)) -> (zext (and x, y)) 712 if (N0.getOpcode() == ISD::ZERO_EXTEND && 713 N1.getOpcode() == ISD::ZERO_EXTEND && 714 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 715 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 716 N0.getOperand(0), N1.getOperand(0)); 717 WorkList.push_back(ANDNode.Val); 718 return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode); 719 } 720 // fold (and (shl/srl x), (shl/srl y)) -> (shl/srl (and x, y)) 721 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) || 722 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL)) && 723 N0.getOperand(1) == N1.getOperand(1)) { 724 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 725 N0.getOperand(0), N1.getOperand(0)); 726 WorkList.push_back(ANDNode.Val); 727 return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1)); 728 } 729 return SDOperand(); 730} 731 732SDOperand DAGCombiner::visitOR(SDNode *N) { 733 SDOperand N0 = N->getOperand(0); 734 SDOperand N1 = N->getOperand(1); 735 SDOperand LL, LR, RL, RR, CC0, CC1; 736 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 737 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 738 MVT::ValueType VT = N1.getValueType(); 739 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 740 741 // fold (or c1, c2) -> c1|c2 742 if (N0C && N1C) 743 return DAG.getConstant(N0C->getValue() | N1C->getValue(), 744 N->getValueType(0)); 745 // canonicalize constant to RHS 746 if (N0C && !N1C) { 747 std::swap(N0, N1); 748 std::swap(N0C, N1C); 749 } 750 // fold (or x, 0) -> x 751 if (N1C && N1C->isNullValue()) 752 return N0; 753 // fold (or x, -1) -> -1 754 if (N1C && N1C->isAllOnesValue()) 755 return N1; 756 // fold (or x, c) -> c iff (x & ~c) == 0 757 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 758 TLI)) 759 return N1; 760 // fold (or (or x, c1), c2) -> (or x, c1|c2) 761 if (N1C && N0.getOpcode() == ISD::OR) { 762 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 763 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 764 if (N00C) 765 return DAG.getNode(ISD::OR, VT, N0.getOperand(1), 766 DAG.getConstant(N1C->getValue()|N00C->getValue(), VT)); 767 if (N01C) 768 return DAG.getNode(ISD::OR, VT, N0.getOperand(0), 769 DAG.getConstant(N1C->getValue()|N01C->getValue(), VT)); 770 } 771 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 772 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 773 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 774 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 775 776 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 777 MVT::isInteger(LL.getValueType())) { 778 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 779 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 780 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 781 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 782 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 783 WorkList.push_back(ORNode.Val); 784 return DAG.getSetCC(VT, ORNode, LR, Op1); 785 } 786 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 787 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 788 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 789 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 790 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 791 WorkList.push_back(ANDNode.Val); 792 return DAG.getSetCC(VT, ANDNode, LR, Op1); 793 } 794 } 795 // canonicalize equivalent to ll == rl 796 if (LL == RR && LR == RL) { 797 Op1 = ISD::getSetCCSwappedOperands(Op1); 798 std::swap(RL, RR); 799 } 800 if (LL == RL && LR == RR) { 801 bool isInteger = MVT::isInteger(LL.getValueType()); 802 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 803 if (Result != ISD::SETCC_INVALID) 804 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 805 } 806 } 807 // fold (or (zext x), (zext y)) -> (zext (or x, y)) 808 if (N0.getOpcode() == ISD::ZERO_EXTEND && 809 N1.getOpcode() == ISD::ZERO_EXTEND && 810 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 811 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(), 812 N0.getOperand(0), N1.getOperand(0)); 813 WorkList.push_back(ORNode.Val); 814 return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode); 815 } 816 return SDOperand(); 817} 818 819SDOperand DAGCombiner::visitXOR(SDNode *N) { 820 SDOperand N0 = N->getOperand(0); 821 SDOperand N1 = N->getOperand(1); 822 SDOperand LHS, RHS, CC; 823 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 824 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 825 MVT::ValueType VT = N0.getValueType(); 826 827 // fold (xor c1, c2) -> c1^c2 828 if (N0C && N1C) 829 return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT); 830 // canonicalize constant to RHS 831 if (N0C && !N1C) { 832 std::swap(N0, N1); 833 std::swap(N0C, N1C); 834 } 835 // fold (xor x, 0) -> x 836 if (N1C && N1C->isNullValue()) 837 return N0; 838 // fold !(x cc y) -> (x !cc y) 839 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 840 bool isInt = MVT::isInteger(LHS.getValueType()); 841 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 842 isInt); 843 if (N0.getOpcode() == ISD::SETCC) 844 return DAG.getSetCC(VT, LHS, RHS, NotCC); 845 if (N0.getOpcode() == ISD::SELECT_CC) 846 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 847 assert(0 && "Unhandled SetCC Equivalent!"); 848 abort(); 849 } 850 // fold !(x or y) -> (!x and !y) iff x or y are setcc 851 if (N1C && N1C->getValue() == 1 && 852 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 853 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 854 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 855 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 856 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 857 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 858 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 859 return DAG.getNode(NewOpcode, VT, LHS, RHS); 860 } 861 } 862 // fold !(x or y) -> (!x and !y) iff x or y are constants 863 if (N1C && N1C->isAllOnesValue() && 864 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 865 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 866 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 867 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 868 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 869 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 870 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 871 return DAG.getNode(NewOpcode, VT, LHS, RHS); 872 } 873 } 874 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 875 if (N1C && N0.getOpcode() == ISD::XOR) { 876 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 877 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 878 if (N00C) 879 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 880 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 881 if (N01C) 882 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 883 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 884 } 885 // fold (xor x, x) -> 0 886 if (N0 == N1) 887 return DAG.getConstant(0, VT); 888 // fold (xor (zext x), (zext y)) -> (zext (xor x, y)) 889 if (N0.getOpcode() == ISD::ZERO_EXTEND && 890 N1.getOpcode() == ISD::ZERO_EXTEND && 891 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 892 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(), 893 N0.getOperand(0), N1.getOperand(0)); 894 WorkList.push_back(XORNode.Val); 895 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode); 896 } 897 return SDOperand(); 898} 899 900SDOperand DAGCombiner::visitSHL(SDNode *N) { 901 SDOperand N0 = N->getOperand(0); 902 SDOperand N1 = N->getOperand(1); 903 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 904 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 905 MVT::ValueType VT = N0.getValueType(); 906 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 907 908 // fold (shl c1, c2) -> c1<<c2 909 if (N0C && N1C) 910 return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT); 911 // fold (shl 0, x) -> 0 912 if (N0C && N0C->isNullValue()) 913 return N0; 914 // fold (shl x, c >= size(x)) -> undef 915 if (N1C && N1C->getValue() >= OpSizeInBits) 916 return DAG.getNode(ISD::UNDEF, VT); 917 // fold (shl x, 0) -> x 918 if (N1C && N1C->isNullValue()) 919 return N0; 920 // if (shl x, c) is known to be zero, return 0 921 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 922 return DAG.getConstant(0, VT); 923 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 924 if (N1C && N0.getOpcode() == ISD::SHL && 925 N0.getOperand(1).getOpcode() == ISD::Constant) { 926 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 927 uint64_t c2 = N1C->getValue(); 928 if (c1 + c2 > OpSizeInBits) 929 return DAG.getConstant(0, VT); 930 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 931 DAG.getConstant(c1 + c2, N1.getValueType())); 932 } 933 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 934 // (srl (and x, -1 << c1), c1-c2) 935 if (N1C && N0.getOpcode() == ISD::SRL && 936 N0.getOperand(1).getOpcode() == ISD::Constant) { 937 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 938 uint64_t c2 = N1C->getValue(); 939 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 940 DAG.getConstant(~0ULL << c1, VT)); 941 if (c2 > c1) 942 return DAG.getNode(ISD::SHL, VT, Mask, 943 DAG.getConstant(c2-c1, N1.getValueType())); 944 else 945 return DAG.getNode(ISD::SRL, VT, Mask, 946 DAG.getConstant(c1-c2, N1.getValueType())); 947 } 948 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 949 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 950 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 951 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 952 return SDOperand(); 953} 954 955SDOperand DAGCombiner::visitSRA(SDNode *N) { 956 SDOperand N0 = N->getOperand(0); 957 SDOperand N1 = N->getOperand(1); 958 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 959 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 960 MVT::ValueType VT = N0.getValueType(); 961 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 962 963 // fold (sra c1, c2) -> c1>>c2 964 if (N0C && N1C) 965 return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT); 966 // fold (sra 0, x) -> 0 967 if (N0C && N0C->isNullValue()) 968 return N0; 969 // fold (sra -1, x) -> -1 970 if (N0C && N0C->isAllOnesValue()) 971 return N0; 972 // fold (sra x, c >= size(x)) -> undef 973 if (N1C && N1C->getValue() >= OpSizeInBits) 974 return DAG.getNode(ISD::UNDEF, VT); 975 // fold (sra x, 0) -> x 976 if (N1C && N1C->isNullValue()) 977 return N0; 978 // If the sign bit is known to be zero, switch this to a SRL. 979 if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI)) 980 return DAG.getNode(ISD::SRL, VT, N0, N1); 981 return SDOperand(); 982} 983 984SDOperand DAGCombiner::visitSRL(SDNode *N) { 985 SDOperand N0 = N->getOperand(0); 986 SDOperand N1 = N->getOperand(1); 987 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 988 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 989 MVT::ValueType VT = N0.getValueType(); 990 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 991 992 // fold (srl c1, c2) -> c1 >>u c2 993 if (N0C && N1C) 994 return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT); 995 // fold (srl 0, x) -> 0 996 if (N0C && N0C->isNullValue()) 997 return N0; 998 // fold (srl x, c >= size(x)) -> undef 999 if (N1C && N1C->getValue() >= OpSizeInBits) 1000 return DAG.getNode(ISD::UNDEF, VT); 1001 // fold (srl x, 0) -> x 1002 if (N1C && N1C->isNullValue()) 1003 return N0; 1004 // if (srl x, c) is known to be zero, return 0 1005 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 1006 return DAG.getConstant(0, VT); 1007 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 1008 if (N1C && N0.getOpcode() == ISD::SRL && 1009 N0.getOperand(1).getOpcode() == ISD::Constant) { 1010 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1011 uint64_t c2 = N1C->getValue(); 1012 if (c1 + c2 > OpSizeInBits) 1013 return DAG.getConstant(0, VT); 1014 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 1015 DAG.getConstant(c1 + c2, N1.getValueType())); 1016 } 1017 return SDOperand(); 1018} 1019 1020SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 1021 SDOperand N0 = N->getOperand(0); 1022 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1023 1024 // fold (ctlz c1) -> c2 1025 if (N0C) 1026 return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()), 1027 N0.getValueType()); 1028 return SDOperand(); 1029} 1030 1031SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 1032 SDOperand N0 = N->getOperand(0); 1033 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1034 1035 // fold (cttz c1) -> c2 1036 if (N0C) 1037 return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()), 1038 N0.getValueType()); 1039 return SDOperand(); 1040} 1041 1042SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 1043 SDOperand N0 = N->getOperand(0); 1044 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1045 1046 // fold (ctpop c1) -> c2 1047 if (N0C) 1048 return DAG.getConstant(CountPopulation_64(N0C->getValue()), 1049 N0.getValueType()); 1050 return SDOperand(); 1051} 1052 1053SDOperand DAGCombiner::visitSELECT(SDNode *N) { 1054 SDOperand N0 = N->getOperand(0); 1055 SDOperand N1 = N->getOperand(1); 1056 SDOperand N2 = N->getOperand(2); 1057 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1058 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1059 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1060 MVT::ValueType VT = N->getValueType(0); 1061 1062 // fold select C, X, X -> X 1063 if (N1 == N2) 1064 return N1; 1065 // fold select true, X, Y -> X 1066 if (N0C && !N0C->isNullValue()) 1067 return N1; 1068 // fold select false, X, Y -> Y 1069 if (N0C && N0C->isNullValue()) 1070 return N2; 1071 // fold select C, 1, X -> C | X 1072 if (MVT::i1 == VT && N1C && N1C->getValue() == 1) 1073 return DAG.getNode(ISD::OR, VT, N0, N2); 1074 // fold select C, 0, X -> ~C & X 1075 // FIXME: this should check for C type == X type, not i1? 1076 if (MVT::i1 == VT && N1C && N1C->isNullValue()) { 1077 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1078 WorkList.push_back(XORNode.Val); 1079 return DAG.getNode(ISD::AND, VT, XORNode, N2); 1080 } 1081 // fold select C, X, 1 -> ~C | X 1082 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) { 1083 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1084 WorkList.push_back(XORNode.Val); 1085 return DAG.getNode(ISD::OR, VT, XORNode, N1); 1086 } 1087 // fold select C, X, 0 -> C & X 1088 // FIXME: this should check for C type == X type, not i1? 1089 if (MVT::i1 == VT && N2C && N2C->isNullValue()) 1090 return DAG.getNode(ISD::AND, VT, N0, N1); 1091 // fold X ? X : Y --> X ? 1 : Y --> X | Y 1092 if (MVT::i1 == VT && N0 == N1) 1093 return DAG.getNode(ISD::OR, VT, N0, N2); 1094 // fold X ? Y : X --> X ? Y : 0 --> X & Y 1095 if (MVT::i1 == VT && N0 == N2) 1096 return DAG.getNode(ISD::AND, VT, N0, N1); 1097 // fold selects based on a setcc into other things, such as min/max/abs 1098 if (N0.getOpcode() == ISD::SETCC) 1099 return SimplifySelect(N0, N1, N2); 1100 return SDOperand(); 1101} 1102 1103SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) { 1104 SDOperand N0 = N->getOperand(0); 1105 SDOperand N1 = N->getOperand(1); 1106 SDOperand N2 = N->getOperand(2); 1107 SDOperand N3 = N->getOperand(3); 1108 SDOperand N4 = N->getOperand(4); 1109 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1110 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1111 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1112 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 1113 1114 // Determine if the condition we're dealing with is constant 1115 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1116 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1117 1118 // fold select_cc lhs, rhs, x, x, cc -> x 1119 if (N2 == N3) 1120 return N2; 1121 // fold select_cc into other things, such as min/max/abs 1122 return SimplifySelectCC(N0, N1, N2, N3, CC); 1123} 1124 1125SDOperand DAGCombiner::visitSETCC(SDNode *N) { 1126 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 1127 cast<CondCodeSDNode>(N->getOperand(2))->get()); 1128} 1129 1130SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 1131 SDOperand N0 = N->getOperand(0); 1132 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1133 MVT::ValueType VT = N->getValueType(0); 1134 1135 // fold (sext c1) -> c1 1136 if (N0C) 1137 return DAG.getConstant(N0C->getSignExtended(), VT); 1138 // fold (sext (sext x)) -> (sext x) 1139 if (N0.getOpcode() == ISD::SIGN_EXTEND) 1140 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1141 return SDOperand(); 1142} 1143 1144SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1145 SDOperand N0 = N->getOperand(0); 1146 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1147 MVT::ValueType VT = N->getValueType(0); 1148 1149 // fold (zext c1) -> c1 1150 if (N0C) 1151 return DAG.getConstant(N0C->getValue(), VT); 1152 // fold (zext (zext x)) -> (zext x) 1153 if (N0.getOpcode() == ISD::ZERO_EXTEND) 1154 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1155 return SDOperand(); 1156} 1157 1158SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 1159 SDOperand N0 = N->getOperand(0); 1160 SDOperand N1 = N->getOperand(1); 1161 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1162 MVT::ValueType VT = N->getValueType(0); 1163 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 1164 1165 // fold (sext_in_reg c1) -> c1 1166 if (N0C) { 1167 SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT); 1168 return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate); 1169 } 1170 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1 1171 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1172 cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) { 1173 return N0; 1174 } 1175 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 1176 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1177 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 1178 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 1179 } 1180 // fold (sext_in_reg (assert_sext x)) -> (assert_sext x) 1181 if (N0.getOpcode() == ISD::AssertSext && 1182 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) { 1183 return N0; 1184 } 1185 // fold (sext_in_reg (sextload x)) -> (sextload x) 1186 if (N0.getOpcode() == ISD::SEXTLOAD && 1187 cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) { 1188 return N0; 1189 } 1190 // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1 1191 // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here 1192 if (N0.getOpcode() == ISD::SETCC && 1193 TLI.getSetCCResultContents() == 1194 TargetLowering::ZeroOrNegativeOneSetCCResult) 1195 return N0; 1196 // FIXME: this code is currently just ported over from SelectionDAG.cpp 1197 // we probably actually want to handle this in two pieces. Rather than 1198 // checking all the top bits for zero, just check the sign bit here and turn 1199 // it into a zero extend inreg (AND with constant). 1200 // then, let the code for AND figure out if the mask is superfluous rather 1201 // than doing so here. 1202 if (N0.getOpcode() == ISD::AND && 1203 N0.getOperand(1).getOpcode() == ISD::Constant) { 1204 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1205 unsigned NumBits = MVT::getSizeInBits(EVT); 1206 if ((Mask & (~0ULL << (NumBits-1))) == 0) 1207 return N0; 1208 } 1209 return SDOperand(); 1210} 1211 1212SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 1213 SDOperand N0 = N->getOperand(0); 1214 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1215 MVT::ValueType VT = N->getValueType(0); 1216 1217 // noop truncate 1218 if (N0.getValueType() == N->getValueType(0)) 1219 return N0; 1220 // fold (truncate c1) -> c1 1221 if (N0C) 1222 return DAG.getConstant(N0C->getValue(), VT); 1223 // fold (truncate (truncate x)) -> (truncate x) 1224 if (N0.getOpcode() == ISD::TRUNCATE) 1225 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1226 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 1227 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){ 1228 if (N0.getValueType() < VT) 1229 // if the source is smaller than the dest, we still need an extend 1230 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1231 else if (N0.getValueType() > VT) 1232 // if the source is larger than the dest, than we just need the truncate 1233 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1234 else 1235 // if the source and dest are the same type, we can drop both the extend 1236 // and the truncate 1237 return N0.getOperand(0); 1238 } 1239 return SDOperand(); 1240} 1241 1242SDOperand DAGCombiner::visitFADD(SDNode *N) { 1243 SDOperand N0 = N->getOperand(0); 1244 SDOperand N1 = N->getOperand(1); 1245 MVT::ValueType VT = N->getValueType(0); 1246 1247 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1248 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1249 // fold floating point (fadd c1, c2) 1250 return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(), 1251 N->getValueType(0)); 1252 } 1253 // fold (A + (-B)) -> A-B 1254 if (N1.getOpcode() == ISD::FNEG) 1255 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0)); 1256 1257 // fold ((-A) + B) -> B-A 1258 if (N0.getOpcode() == ISD::FNEG) 1259 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0)); 1260 1261 return SDOperand(); 1262} 1263 1264SDOperand DAGCombiner::visitFSUB(SDNode *N) { 1265 SDOperand N0 = N->getOperand(0); 1266 SDOperand N1 = N->getOperand(1); 1267 MVT::ValueType VT = N->getValueType(0); 1268 1269 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1270 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1271 // fold floating point (fsub c1, c2) 1272 return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(), 1273 N->getValueType(0)); 1274 } 1275 // fold (A-(-B)) -> A+B 1276 if (N1.getOpcode() == ISD::FNEG) 1277 return DAG.getNode(ISD::FADD, N0.getValueType(), N0, N1.getOperand(0)); 1278 1279 return SDOperand(); 1280} 1281 1282SDOperand DAGCombiner::visitFMUL(SDNode *N) { 1283 SDOperand N0 = N->getOperand(0); 1284 SDOperand N1 = N->getOperand(1); 1285 MVT::ValueType VT = N->getValueType(0); 1286 1287 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1288 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1289 // fold floating point (fmul c1, c2) 1290 return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(), 1291 N->getValueType(0)); 1292 } 1293 return SDOperand(); 1294} 1295 1296SDOperand DAGCombiner::visitFDIV(SDNode *N) { 1297 SDOperand N0 = N->getOperand(0); 1298 SDOperand N1 = N->getOperand(1); 1299 MVT::ValueType VT = N->getValueType(0); 1300 1301 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1302 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1303 // fold floating point (fdiv c1, c2) 1304 return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(), 1305 N->getValueType(0)); 1306 } 1307 return SDOperand(); 1308} 1309 1310SDOperand DAGCombiner::visitFREM(SDNode *N) { 1311 SDOperand N0 = N->getOperand(0); 1312 SDOperand N1 = N->getOperand(1); 1313 MVT::ValueType VT = N->getValueType(0); 1314 1315 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1316 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1317 // fold floating point (frem c1, c2) -> fmod(c1, c2) 1318 return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()), 1319 N->getValueType(0)); 1320 } 1321 return SDOperand(); 1322} 1323 1324 1325SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 1326 SDOperand N0 = N->getOperand(0); 1327 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1328 1329 // fold (sint_to_fp c1) -> c1fp 1330 if (N0C) 1331 return DAG.getConstantFP(N0C->getSignExtended(), N->getValueType(0)); 1332 return SDOperand(); 1333} 1334 1335SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 1336 SDOperand N0 = N->getOperand(0); 1337 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1338 1339 // fold (uint_to_fp c1) -> c1fp 1340 if (N0C) 1341 return DAG.getConstantFP(N0C->getValue(), N->getValueType(0)); 1342 return SDOperand(); 1343} 1344 1345SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 1346 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1347 1348 // fold (fp_to_sint c1fp) -> c1 1349 if (N0CFP) 1350 return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0)); 1351 return SDOperand(); 1352} 1353 1354SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 1355 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1356 1357 // fold (fp_to_uint c1fp) -> c1 1358 if (N0CFP) 1359 return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0)); 1360 return SDOperand(); 1361} 1362 1363SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 1364 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1365 1366 // fold (fp_round c1fp) -> c1fp 1367 if (N0CFP) 1368 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1369 return SDOperand(); 1370} 1371 1372SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 1373 SDOperand N0 = N->getOperand(0); 1374 MVT::ValueType VT = N->getValueType(0); 1375 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 1376 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1377 1378 // fold (fp_round_inreg c1fp) -> c1fp 1379 if (N0CFP) { 1380 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 1381 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 1382 } 1383 return SDOperand(); 1384} 1385 1386SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 1387 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1388 1389 // fold (fp_extend c1fp) -> c1fp 1390 if (N0CFP) 1391 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1392 return SDOperand(); 1393} 1394 1395SDOperand DAGCombiner::visitFNEG(SDNode *N) { 1396 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1397 // fold (neg c1) -> -c1 1398 if (N0CFP) 1399 return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0)); 1400 // fold (neg (sub x, y)) -> (sub y, x) 1401 if (N->getOperand(0).getOpcode() == ISD::SUB) 1402 return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1), 1403 N->getOperand(0)); 1404 // fold (neg (neg x)) -> x 1405 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1406 return N->getOperand(0).getOperand(0); 1407 return SDOperand(); 1408} 1409 1410SDOperand DAGCombiner::visitFABS(SDNode *N) { 1411 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1412 // fold (fabs c1) -> fabs(c1) 1413 if (N0CFP) 1414 return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0)); 1415 // fold (fabs (fabs x)) -> (fabs x) 1416 if (N->getOperand(0).getOpcode() == ISD::FABS) 1417 return N->getOperand(0); 1418 // fold (fabs (fneg x)) -> (fabs x) 1419 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1420 return DAG.getNode(ISD::FABS, N->getValueType(0), 1421 N->getOperand(0).getOperand(0)); 1422 return SDOperand(); 1423} 1424 1425SDOperand DAGCombiner::visitBRCOND(SDNode *N) { 1426 SDOperand Chain = N->getOperand(0); 1427 SDOperand N1 = N->getOperand(1); 1428 SDOperand N2 = N->getOperand(2); 1429 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1430 1431 // never taken branch, fold to chain 1432 if (N1C && N1C->isNullValue()) 1433 return Chain; 1434 // unconditional branch 1435 if (N1C && N1C->getValue() == 1) 1436 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 1437 return SDOperand(); 1438} 1439 1440SDOperand DAGCombiner::visitBRCONDTWOWAY(SDNode *N) { 1441 SDOperand Chain = N->getOperand(0); 1442 SDOperand N1 = N->getOperand(1); 1443 SDOperand N2 = N->getOperand(2); 1444 SDOperand N3 = N->getOperand(3); 1445 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1446 1447 // unconditional branch to true mbb 1448 if (N1C && N1C->getValue() == 1) 1449 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 1450 // unconditional branch to false mbb 1451 if (N1C && N1C->isNullValue()) 1452 return DAG.getNode(ISD::BR, MVT::Other, Chain, N3); 1453 return SDOperand(); 1454} 1455 1456// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 1457// 1458SDOperand DAGCombiner::visitBR_CC(SDNode *N) { 1459 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 1460 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 1461 1462 // Use SimplifySetCC to simplify SETCC's. 1463 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false); 1464 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val); 1465 1466 // fold br_cc true, dest -> br dest (unconditional branch) 1467 if (SCCC && SCCC->getValue()) 1468 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 1469 N->getOperand(4)); 1470 // fold br_cc false, dest -> unconditional fall through 1471 if (SCCC && SCCC->isNullValue()) 1472 return N->getOperand(0); 1473 // fold to a simpler setcc 1474 if (Simp.Val && Simp.getOpcode() == ISD::SETCC) 1475 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 1476 Simp.getOperand(2), Simp.getOperand(0), 1477 Simp.getOperand(1), N->getOperand(4)); 1478 return SDOperand(); 1479} 1480 1481SDOperand DAGCombiner::visitBRTWOWAY_CC(SDNode *N) { 1482 SDOperand Chain = N->getOperand(0); 1483 SDOperand CCN = N->getOperand(1); 1484 SDOperand LHS = N->getOperand(2); 1485 SDOperand RHS = N->getOperand(3); 1486 SDOperand N4 = N->getOperand(4); 1487 SDOperand N5 = N->getOperand(5); 1488 1489 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), LHS, RHS, 1490 cast<CondCodeSDNode>(CCN)->get(), false); 1491 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1492 1493 // fold select_cc lhs, rhs, x, x, cc -> x 1494 if (N4 == N5) 1495 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 1496 // fold select_cc true, x, y -> x 1497 if (SCCC && SCCC->getValue()) 1498 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 1499 // fold select_cc false, x, y -> y 1500 if (SCCC && SCCC->isNullValue()) 1501 return DAG.getNode(ISD::BR, MVT::Other, Chain, N5); 1502 // fold to a simpler setcc 1503 if (SCC.Val && SCC.getOpcode() == ISD::SETCC) 1504 return DAG.getBR2Way_CC(Chain, SCC.getOperand(2), SCC.getOperand(0), 1505 SCC.getOperand(1), N4, N5); 1506 return SDOperand(); 1507} 1508 1509SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 1510 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 1511 1512 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 1513 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 1514 // If we got a simplified select_cc node back from SimplifySelectCC, then 1515 // break it down into a new SETCC node, and a new SELECT node, and then return 1516 // the SELECT node, since we were called with a SELECT node. 1517 if (SCC.Val) { 1518 // Check to see if we got a select_cc back (to turn into setcc/select). 1519 // Otherwise, just return whatever node we got back, like fabs. 1520 if (SCC.getOpcode() == ISD::SELECT_CC) { 1521 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 1522 SCC.getOperand(0), SCC.getOperand(1), 1523 SCC.getOperand(4)); 1524 WorkList.push_back(SETCC.Val); 1525 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 1526 SCC.getOperand(3), SETCC); 1527 } 1528 return SCC; 1529 } 1530 return SDOperand(); 1531} 1532 1533SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 1534 SDOperand N2, SDOperand N3, 1535 ISD::CondCode CC) { 1536 1537 MVT::ValueType VT = N2.getValueType(); 1538 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 1539 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1540 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1541 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 1542 1543 // Determine if the condition we're dealing with is constant 1544 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1545 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1546 1547 // fold select_cc true, x, y -> x 1548 if (SCCC && SCCC->getValue()) 1549 return N2; 1550 // fold select_cc false, x, y -> y 1551 if (SCCC && SCCC->getValue() == 0) 1552 return N3; 1553 1554 // Check to see if we can simplify the select into an fabs node 1555 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1556 // Allow either -0.0 or 0.0 1557 if (CFP->getValue() == 0.0) { 1558 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 1559 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 1560 N0 == N2 && N3.getOpcode() == ISD::FNEG && 1561 N2 == N3.getOperand(0)) 1562 return DAG.getNode(ISD::FABS, VT, N0); 1563 1564 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 1565 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 1566 N0 == N3 && N2.getOpcode() == ISD::FNEG && 1567 N2.getOperand(0) == N3) 1568 return DAG.getNode(ISD::FABS, VT, N3); 1569 } 1570 } 1571 1572 // Check to see if we can perform the "gzip trick", transforming 1573 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 1574 if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() && 1575 MVT::isInteger(N0.getValueType()) && 1576 MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) { 1577 MVT::ValueType XType = N0.getValueType(); 1578 MVT::ValueType AType = N2.getValueType(); 1579 if (XType >= AType) { 1580 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 1581 // single-bit constant. FIXME: remove once the dag combiner 1582 // exists. 1583 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) { 1584 unsigned ShCtV = Log2_64(N2C->getValue()); 1585 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1; 1586 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 1587 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 1588 WorkList.push_back(Shift.Val); 1589 if (XType > AType) { 1590 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 1591 WorkList.push_back(Shift.Val); 1592 } 1593 return DAG.getNode(ISD::AND, AType, Shift, N2); 1594 } 1595 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 1596 DAG.getConstant(MVT::getSizeInBits(XType)-1, 1597 TLI.getShiftAmountTy())); 1598 WorkList.push_back(Shift.Val); 1599 if (XType > AType) { 1600 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 1601 WorkList.push_back(Shift.Val); 1602 } 1603 return DAG.getNode(ISD::AND, AType, Shift, N2); 1604 } 1605 } 1606 1607 // Check to see if this is the equivalent of setcc 1608 // FIXME: Turn all of these into setcc if setcc if setcc is legal 1609 // otherwise, go ahead with the folds. 1610 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) { 1611 MVT::ValueType XType = N0.getValueType(); 1612 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) { 1613 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 1614 if (Res.getValueType() != VT) 1615 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 1616 return Res; 1617 } 1618 1619 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 1620 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 1621 TLI.isOperationLegal(ISD::CTLZ, XType)) { 1622 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 1623 return DAG.getNode(ISD::SRL, XType, Ctlz, 1624 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)), 1625 TLI.getShiftAmountTy())); 1626 } 1627 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 1628 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 1629 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 1630 N0); 1631 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 1632 DAG.getConstant(~0ULL, XType)); 1633 return DAG.getNode(ISD::SRL, XType, 1634 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 1635 DAG.getConstant(MVT::getSizeInBits(XType)-1, 1636 TLI.getShiftAmountTy())); 1637 } 1638 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 1639 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 1640 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0, 1641 DAG.getConstant(MVT::getSizeInBits(XType)-1, 1642 TLI.getShiftAmountTy())); 1643 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 1644 } 1645 } 1646 1647 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 1648 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 1649 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 1650 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) { 1651 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) { 1652 MVT::ValueType XType = N0.getValueType(); 1653 if (SubC->isNullValue() && MVT::isInteger(XType)) { 1654 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 1655 DAG.getConstant(MVT::getSizeInBits(XType)-1, 1656 TLI.getShiftAmountTy())); 1657 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 1658 WorkList.push_back(Shift.Val); 1659 WorkList.push_back(Add.Val); 1660 return DAG.getNode(ISD::XOR, XType, Add, Shift); 1661 } 1662 } 1663 } 1664 1665 return SDOperand(); 1666} 1667 1668SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 1669 SDOperand N1, ISD::CondCode Cond, 1670 bool foldBooleans) { 1671 // These setcc operations always fold. 1672 switch (Cond) { 1673 default: break; 1674 case ISD::SETFALSE: 1675 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 1676 case ISD::SETTRUE: 1677 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 1678 } 1679 1680 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 1681 uint64_t C1 = N1C->getValue(); 1682 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) { 1683 uint64_t C0 = N0C->getValue(); 1684 1685 // Sign extend the operands if required 1686 if (ISD::isSignedIntSetCC(Cond)) { 1687 C0 = N0C->getSignExtended(); 1688 C1 = N1C->getSignExtended(); 1689 } 1690 1691 switch (Cond) { 1692 default: assert(0 && "Unknown integer setcc!"); 1693 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 1694 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 1695 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT); 1696 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT); 1697 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT); 1698 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT); 1699 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT); 1700 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT); 1701 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT); 1702 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT); 1703 } 1704 } else { 1705 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 1706 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 1707 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 1708 1709 // If the comparison constant has bits in the upper part, the 1710 // zero-extended value could never match. 1711 if (C1 & (~0ULL << InSize)) { 1712 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 1713 switch (Cond) { 1714 case ISD::SETUGT: 1715 case ISD::SETUGE: 1716 case ISD::SETEQ: return DAG.getConstant(0, VT); 1717 case ISD::SETULT: 1718 case ISD::SETULE: 1719 case ISD::SETNE: return DAG.getConstant(1, VT); 1720 case ISD::SETGT: 1721 case ISD::SETGE: 1722 // True if the sign bit of C1 is set. 1723 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 1724 case ISD::SETLT: 1725 case ISD::SETLE: 1726 // True if the sign bit of C1 isn't set. 1727 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 1728 default: 1729 break; 1730 } 1731 } 1732 1733 // Otherwise, we can perform the comparison with the low bits. 1734 switch (Cond) { 1735 case ISD::SETEQ: 1736 case ISD::SETNE: 1737 case ISD::SETUGT: 1738 case ISD::SETUGE: 1739 case ISD::SETULT: 1740 case ISD::SETULE: 1741 return DAG.getSetCC(VT, N0.getOperand(0), 1742 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 1743 Cond); 1744 default: 1745 break; // todo, be more careful with signed comparisons 1746 } 1747 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1748 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 1749 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 1750 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 1751 MVT::ValueType ExtDstTy = N0.getValueType(); 1752 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 1753 1754 // If the extended part has any inconsistent bits, it cannot ever 1755 // compare equal. In other words, they have to be all ones or all 1756 // zeros. 1757 uint64_t ExtBits = 1758 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 1759 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 1760 return DAG.getConstant(Cond == ISD::SETNE, VT); 1761 1762 SDOperand ZextOp; 1763 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 1764 if (Op0Ty == ExtSrcTy) { 1765 ZextOp = N0.getOperand(0); 1766 } else { 1767 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 1768 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 1769 DAG.getConstant(Imm, Op0Ty)); 1770 } 1771 WorkList.push_back(ZextOp.Val); 1772 // Otherwise, make this a use of a zext. 1773 return DAG.getSetCC(VT, ZextOp, 1774 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 1775 ExtDstTy), 1776 Cond); 1777 } 1778 1779 uint64_t MinVal, MaxVal; 1780 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 1781 if (ISD::isSignedIntSetCC(Cond)) { 1782 MinVal = 1ULL << (OperandBitSize-1); 1783 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 1784 MaxVal = ~0ULL >> (65-OperandBitSize); 1785 else 1786 MaxVal = 0; 1787 } else { 1788 MinVal = 0; 1789 MaxVal = ~0ULL >> (64-OperandBitSize); 1790 } 1791 1792 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 1793 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 1794 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 1795 --C1; // X >= C0 --> X > (C0-1) 1796 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 1797 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 1798 } 1799 1800 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 1801 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 1802 ++C1; // X <= C0 --> X < (C0+1) 1803 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 1804 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 1805 } 1806 1807 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 1808 return DAG.getConstant(0, VT); // X < MIN --> false 1809 1810 // Canonicalize setgt X, Min --> setne X, Min 1811 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 1812 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 1813 1814 // If we have setult X, 1, turn it into seteq X, 0 1815 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 1816 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 1817 ISD::SETEQ); 1818 // If we have setugt X, Max-1, turn it into seteq X, Max 1819 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 1820 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 1821 ISD::SETEQ); 1822 1823 // If we have "setcc X, C0", check to see if we can shrink the immediate 1824 // by changing cc. 1825 1826 // SETUGT X, SINTMAX -> SETLT X, 0 1827 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 1828 C1 == (~0ULL >> (65-OperandBitSize))) 1829 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 1830 ISD::SETLT); 1831 1832 // FIXME: Implement the rest of these. 1833 1834 // Fold bit comparisons when we can. 1835 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1836 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 1837 if (ConstantSDNode *AndRHS = 1838 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1839 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 1840 // Perform the xform if the AND RHS is a single bit. 1841 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 1842 return DAG.getNode(ISD::SRL, VT, N0, 1843 DAG.getConstant(Log2_64(AndRHS->getValue()), 1844 TLI.getShiftAmountTy())); 1845 } 1846 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 1847 // (X & 8) == 8 --> (X & 8) >> 3 1848 // Perform the xform if C1 is a single bit. 1849 if ((C1 & (C1-1)) == 0) { 1850 return DAG.getNode(ISD::SRL, VT, N0, 1851 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 1852 } 1853 } 1854 } 1855 } 1856 } else if (isa<ConstantSDNode>(N0.Val)) { 1857 // Ensure that the constant occurs on the RHS. 1858 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 1859 } 1860 1861 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val)) 1862 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) { 1863 double C0 = N0C->getValue(), C1 = N1C->getValue(); 1864 1865 switch (Cond) { 1866 default: break; // FIXME: Implement the rest of these! 1867 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 1868 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 1869 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT); 1870 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT); 1871 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT); 1872 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT); 1873 } 1874 } else { 1875 // Ensure that the constant occurs on the RHS. 1876 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 1877 } 1878 1879 if (N0 == N1) { 1880 // We can always fold X == Y for integer setcc's. 1881 if (MVT::isInteger(N0.getValueType())) 1882 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1883 unsigned UOF = ISD::getUnorderedFlavor(Cond); 1884 if (UOF == 2) // FP operators that are undefined on NaNs. 1885 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1886 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 1887 return DAG.getConstant(UOF, VT); 1888 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 1889 // if it is not already. 1890 ISD::CondCode NewCond = UOF == 0 ? ISD::SETUO : ISD::SETO; 1891 if (NewCond != Cond) 1892 return DAG.getSetCC(VT, N0, N1, NewCond); 1893 } 1894 1895 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1896 MVT::isInteger(N0.getValueType())) { 1897 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 1898 N0.getOpcode() == ISD::XOR) { 1899 // Simplify (X+Y) == (X+Z) --> Y == Z 1900 if (N0.getOpcode() == N1.getOpcode()) { 1901 if (N0.getOperand(0) == N1.getOperand(0)) 1902 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 1903 if (N0.getOperand(1) == N1.getOperand(1)) 1904 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 1905 if (isCommutativeBinOp(N0.getOpcode())) { 1906 // If X op Y == Y op X, try other combinations. 1907 if (N0.getOperand(0) == N1.getOperand(1)) 1908 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 1909 if (N0.getOperand(1) == N1.getOperand(0)) 1910 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 1911 } 1912 } 1913 1914 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. Common for condcodes. 1915 if (N0.getOpcode() == ISD::XOR) 1916 if (ConstantSDNode *XORC = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 1917 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 1918 // If we know that all of the inverted bits are zero, don't bother 1919 // performing the inversion. 1920 if (MaskedValueIsZero(N0.getOperand(0), ~XORC->getValue(), TLI)) 1921 return DAG.getSetCC(VT, N0.getOperand(0), 1922 DAG.getConstant(XORC->getValue()^RHSC->getValue(), 1923 N0.getValueType()), Cond); 1924 } 1925 1926 // Simplify (X+Z) == X --> Z == 0 1927 if (N0.getOperand(0) == N1) 1928 return DAG.getSetCC(VT, N0.getOperand(1), 1929 DAG.getConstant(0, N0.getValueType()), Cond); 1930 if (N0.getOperand(1) == N1) { 1931 if (isCommutativeBinOp(N0.getOpcode())) 1932 return DAG.getSetCC(VT, N0.getOperand(0), 1933 DAG.getConstant(0, N0.getValueType()), Cond); 1934 else { 1935 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 1936 // (Z-X) == X --> Z == X<<1 1937 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 1938 N1, 1939 DAG.getConstant(1,TLI.getShiftAmountTy())); 1940 WorkList.push_back(SH.Val); 1941 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 1942 } 1943 } 1944 } 1945 1946 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 1947 N1.getOpcode() == ISD::XOR) { 1948 // Simplify X == (X+Z) --> Z == 0 1949 if (N1.getOperand(0) == N0) { 1950 return DAG.getSetCC(VT, N1.getOperand(1), 1951 DAG.getConstant(0, N1.getValueType()), Cond); 1952 } else if (N1.getOperand(1) == N0) { 1953 if (isCommutativeBinOp(N1.getOpcode())) { 1954 return DAG.getSetCC(VT, N1.getOperand(0), 1955 DAG.getConstant(0, N1.getValueType()), Cond); 1956 } else { 1957 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 1958 // X == (Z-X) --> X<<1 == Z 1959 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 1960 DAG.getConstant(1,TLI.getShiftAmountTy())); 1961 WorkList.push_back(SH.Val); 1962 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 1963 } 1964 } 1965 } 1966 } 1967 1968 // Fold away ALL boolean setcc's. 1969 SDOperand Temp; 1970 if (N0.getValueType() == MVT::i1 && foldBooleans) { 1971 switch (Cond) { 1972 default: assert(0 && "Unknown integer setcc!"); 1973 case ISD::SETEQ: // X == Y -> (X^Y)^1 1974 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1975 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 1976 WorkList.push_back(Temp.Val); 1977 break; 1978 case ISD::SETNE: // X != Y --> (X^Y) 1979 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1980 break; 1981 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 1982 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 1983 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1984 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 1985 WorkList.push_back(Temp.Val); 1986 break; 1987 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 1988 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 1989 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 1990 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 1991 WorkList.push_back(Temp.Val); 1992 break; 1993 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 1994 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 1995 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1996 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 1997 WorkList.push_back(Temp.Val); 1998 break; 1999 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 2000 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 2001 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 2002 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 2003 break; 2004 } 2005 if (VT != MVT::i1) { 2006 WorkList.push_back(N0.Val); 2007 // FIXME: If running after legalize, we probably can't do this. 2008 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 2009 } 2010 return N0; 2011 } 2012 2013 // Could not fold it. 2014 return SDOperand(); 2015} 2016 2017// SelectionDAG::Combine - This is the entry point for the file. 2018// 2019void SelectionDAG::Combine(bool RunningAfterLegalize) { 2020 /// run - This is the main entry point to this class. 2021 /// 2022 DAGCombiner(*this).Run(RunningAfterLegalize); 2023} 2024