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