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