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