DAGCombiner.cpp revision 094c8fcd14a04a3bac12eb17e7e04276ce594e11
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, bool foldBooleans = true); 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 MVT::ValueType VT = N->getValueType(0); 505 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 506 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 507 508 // fold (sdiv c1, c2) -> c1/c2 509 if (N0C && N1C && !N1C->isNullValue()) 510 return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(), 511 N->getValueType(0)); 512 513 // If we know the sign bits of both operands are zero, strength reduce to a 514 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 515 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 516 if (MaskedValueIsZero(N1, SignBit, TLI) && 517 MaskedValueIsZero(N0, SignBit, TLI)) 518 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 519 520 521 return SDOperand(); 522} 523 524SDOperand DAGCombiner::visitUDIV(SDNode *N) { 525 SDOperand N0 = N->getOperand(0); 526 SDOperand N1 = N->getOperand(1); 527 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 528 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 529 530 // fold (udiv c1, c2) -> c1/c2 531 if (N0C && N1C && !N1C->isNullValue()) 532 return DAG.getConstant(N0C->getValue() / N1C->getValue(), 533 N->getValueType(0)); 534 // fold (udiv x, (1 << c)) -> x >>u c 535 if (N1C && isPowerOf2_64(N1C->getValue())) 536 return DAG.getNode(ISD::SRL, N->getValueType(0), N0, 537 DAG.getConstant(Log2_64(N1C->getValue()), 538 TLI.getShiftAmountTy())); 539 return SDOperand(); 540} 541 542SDOperand DAGCombiner::visitSREM(SDNode *N) { 543 SDOperand N0 = N->getOperand(0); 544 SDOperand N1 = N->getOperand(1); 545 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 546 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 547 548 // fold (srem c1, c2) -> c1%c2 549 if (N0C && N1C && !N1C->isNullValue()) 550 return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(), 551 N->getValueType(0)); 552 return SDOperand(); 553} 554 555SDOperand DAGCombiner::visitUREM(SDNode *N) { 556 SDOperand N0 = N->getOperand(0); 557 SDOperand N1 = N->getOperand(1); 558 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 559 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 560 561 // fold (urem c1, c2) -> c1%c2 562 if (N0C && N1C && !N1C->isNullValue()) 563 return DAG.getConstant(N0C->getValue() % N1C->getValue(), 564 N->getValueType(0)); 565 // FIXME: c2 power of 2 -> mask? 566 return SDOperand(); 567} 568 569SDOperand DAGCombiner::visitMULHS(SDNode *N) { 570 SDOperand N0 = N->getOperand(0); 571 SDOperand N1 = N->getOperand(1); 572 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 573 574 // fold (mulhs x, 0) -> 0 575 if (N1C && N1C->isNullValue()) 576 return N1; 577 // fold (mulhs x, 1) -> (sra x, size(x)-1) 578 if (N1C && N1C->getValue() == 1) 579 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 580 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 581 TLI.getShiftAmountTy())); 582 return SDOperand(); 583} 584 585SDOperand DAGCombiner::visitMULHU(SDNode *N) { 586 SDOperand N0 = N->getOperand(0); 587 SDOperand N1 = N->getOperand(1); 588 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 589 590 // fold (mulhu x, 0) -> 0 591 if (N1C && N1C->isNullValue()) 592 return N1; 593 // fold (mulhu x, 1) -> 0 594 if (N1C && N1C->getValue() == 1) 595 return DAG.getConstant(0, N0.getValueType()); 596 return SDOperand(); 597} 598 599SDOperand DAGCombiner::visitAND(SDNode *N) { 600 SDOperand N0 = N->getOperand(0); 601 SDOperand N1 = N->getOperand(1); 602 SDOperand LL, LR, RL, RR, CC0, CC1; 603 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 604 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 605 MVT::ValueType VT = N1.getValueType(); 606 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 607 608 // fold (and c1, c2) -> c1&c2 609 if (N0C && N1C) 610 return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT); 611 // canonicalize constant to RHS 612 if (N0C && !N1C) { 613 std::swap(N0, N1); 614 std::swap(N0C, N1C); 615 } 616 // fold (and x, -1) -> x 617 if (N1C && N1C->isAllOnesValue()) 618 return N0; 619 // if (and x, c) is known to be zero, return 0 620 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 621 return DAG.getConstant(0, VT); 622 // fold (and x, c) -> x iff (x & ~c) == 0 623 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 624 TLI)) 625 return N0; 626 // fold (and (and x, c1), c2) -> (and x, c1^c2) 627 if (N1C && N0.getOpcode() == ISD::AND) { 628 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 629 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 630 if (N00C) 631 return DAG.getNode(ISD::AND, VT, N0.getOperand(1), 632 DAG.getConstant(N1C->getValue()&N00C->getValue(), VT)); 633 if (N01C) 634 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 635 DAG.getConstant(N1C->getValue()&N01C->getValue(), VT)); 636 } 637 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 638 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) { 639 unsigned ExtendBits = 640 MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT()); 641 if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0) 642 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1); 643 } 644 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 645 if (N0.getOpcode() == ISD::OR) 646 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 647 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 648 return N1; 649 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 650 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 651 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 652 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 653 654 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 655 MVT::isInteger(LL.getValueType())) { 656 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 657 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 658 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 659 WorkList.push_back(ORNode.Val); 660 return DAG.getSetCC(VT, ORNode, LR, Op1); 661 } 662 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 663 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 664 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 665 WorkList.push_back(ANDNode.Val); 666 return DAG.getSetCC(VT, ANDNode, LR, Op1); 667 } 668 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 669 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 670 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 671 WorkList.push_back(ORNode.Val); 672 return DAG.getSetCC(VT, ORNode, LR, Op1); 673 } 674 } 675 // canonicalize equivalent to ll == rl 676 if (LL == RR && LR == RL) { 677 Op1 = ISD::getSetCCSwappedOperands(Op1); 678 std::swap(RL, RR); 679 } 680 if (LL == RL && LR == RR) { 681 bool isInteger = MVT::isInteger(LL.getValueType()); 682 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 683 if (Result != ISD::SETCC_INVALID) 684 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 685 } 686 } 687 // fold (and (zext x), (zext y)) -> (zext (and x, y)) 688 if (N0.getOpcode() == ISD::ZERO_EXTEND && 689 N1.getOpcode() == ISD::ZERO_EXTEND && 690 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 691 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 692 N0.getOperand(0), N1.getOperand(0)); 693 WorkList.push_back(ANDNode.Val); 694 return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode); 695 } 696 // fold (and (shl/srl x), (shl/srl y)) -> (shl/srl (and x, y)) 697 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) || 698 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL)) && 699 N0.getOperand(1) == N1.getOperand(1)) { 700 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 701 N0.getOperand(0), N1.getOperand(0)); 702 WorkList.push_back(ANDNode.Val); 703 return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1)); 704 } 705 return SDOperand(); 706} 707 708SDOperand DAGCombiner::visitOR(SDNode *N) { 709 SDOperand N0 = N->getOperand(0); 710 SDOperand N1 = N->getOperand(1); 711 SDOperand LL, LR, RL, RR, CC0, CC1; 712 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 713 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 714 MVT::ValueType VT = N1.getValueType(); 715 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 716 717 // fold (or c1, c2) -> c1|c2 718 if (N0C && N1C) 719 return DAG.getConstant(N0C->getValue() | N1C->getValue(), 720 N->getValueType(0)); 721 // canonicalize constant to RHS 722 if (N0C && !N1C) { 723 std::swap(N0, N1); 724 std::swap(N0C, N1C); 725 } 726 // fold (or x, 0) -> x 727 if (N1C && N1C->isNullValue()) 728 return N0; 729 // fold (or x, -1) -> -1 730 if (N1C && N1C->isAllOnesValue()) 731 return N1; 732 // fold (or x, c) -> c iff (x & ~c) == 0 733 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 734 TLI)) 735 return N1; 736 // fold (or (or x, c1), c2) -> (or x, c1|c2) 737 if (N1C && N0.getOpcode() == ISD::OR) { 738 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 739 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 740 if (N00C) 741 return DAG.getNode(ISD::OR, VT, N0.getOperand(1), 742 DAG.getConstant(N1C->getValue()|N00C->getValue(), VT)); 743 if (N01C) 744 return DAG.getNode(ISD::OR, VT, N0.getOperand(0), 745 DAG.getConstant(N1C->getValue()|N01C->getValue(), VT)); 746 } 747 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 748 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 749 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 750 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 751 752 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 753 MVT::isInteger(LL.getValueType())) { 754 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 755 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 756 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 757 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 758 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 759 WorkList.push_back(ORNode.Val); 760 return DAG.getSetCC(VT, ORNode, LR, Op1); 761 } 762 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 763 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 764 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 765 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 766 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 767 WorkList.push_back(ANDNode.Val); 768 return DAG.getSetCC(VT, ANDNode, LR, Op1); 769 } 770 } 771 // canonicalize equivalent to ll == rl 772 if (LL == RR && LR == RL) { 773 Op1 = ISD::getSetCCSwappedOperands(Op1); 774 std::swap(RL, RR); 775 } 776 if (LL == RL && LR == RR) { 777 bool isInteger = MVT::isInteger(LL.getValueType()); 778 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 779 if (Result != ISD::SETCC_INVALID) 780 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 781 } 782 } 783 // fold (or (zext x), (zext y)) -> (zext (or x, y)) 784 if (N0.getOpcode() == ISD::ZERO_EXTEND && 785 N1.getOpcode() == ISD::ZERO_EXTEND && 786 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 787 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(), 788 N0.getOperand(0), N1.getOperand(0)); 789 WorkList.push_back(ORNode.Val); 790 return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode); 791 } 792 return SDOperand(); 793} 794 795SDOperand DAGCombiner::visitXOR(SDNode *N) { 796 SDOperand N0 = N->getOperand(0); 797 SDOperand N1 = N->getOperand(1); 798 SDOperand LHS, RHS, CC; 799 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 800 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 801 MVT::ValueType VT = N0.getValueType(); 802 803 // fold (xor c1, c2) -> c1^c2 804 if (N0C && N1C) 805 return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT); 806 // canonicalize constant to RHS 807 if (N0C && !N1C) { 808 std::swap(N0, N1); 809 std::swap(N0C, N1C); 810 } 811 // fold (xor x, 0) -> x 812 if (N1C && N1C->isNullValue()) 813 return N0; 814 // fold !(x cc y) -> (x !cc y) 815 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 816 bool isInt = MVT::isInteger(LHS.getValueType()); 817 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 818 isInt); 819 if (N0.getOpcode() == ISD::SETCC) 820 return DAG.getSetCC(VT, LHS, RHS, NotCC); 821 if (N0.getOpcode() == ISD::SELECT_CC) 822 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 823 assert(0 && "Unhandled SetCC Equivalent!"); 824 abort(); 825 } 826 // fold !(x or y) -> (!x and !y) iff x or y are setcc 827 if (N1C && N1C->getValue() == 1 && 828 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 829 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 830 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 831 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 832 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 833 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 834 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 835 return DAG.getNode(NewOpcode, VT, LHS, RHS); 836 } 837 } 838 // fold !(x or y) -> (!x and !y) iff x or y are constants 839 if (N1C && N1C->isAllOnesValue() && 840 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 841 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 842 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 843 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 844 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 845 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 846 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 847 return DAG.getNode(NewOpcode, VT, LHS, RHS); 848 } 849 } 850 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 851 if (N1C && N0.getOpcode() == ISD::XOR) { 852 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 853 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 854 if (N00C) 855 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 856 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 857 if (N01C) 858 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 859 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 860 } 861 // fold (xor x, x) -> 0 862 if (N0 == N1) 863 return DAG.getConstant(0, VT); 864 // fold (xor (zext x), (zext y)) -> (zext (xor x, y)) 865 if (N0.getOpcode() == ISD::ZERO_EXTEND && 866 N1.getOpcode() == ISD::ZERO_EXTEND && 867 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 868 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(), 869 N0.getOperand(0), N1.getOperand(0)); 870 WorkList.push_back(XORNode.Val); 871 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode); 872 } 873 return SDOperand(); 874} 875 876SDOperand DAGCombiner::visitSHL(SDNode *N) { 877 SDOperand N0 = N->getOperand(0); 878 SDOperand N1 = N->getOperand(1); 879 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 880 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 881 MVT::ValueType VT = N0.getValueType(); 882 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 883 884 // fold (shl c1, c2) -> c1<<c2 885 if (N0C && N1C) 886 return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT); 887 // fold (shl 0, x) -> 0 888 if (N0C && N0C->isNullValue()) 889 return N0; 890 // fold (shl x, c >= size(x)) -> undef 891 if (N1C && N1C->getValue() >= OpSizeInBits) 892 return DAG.getNode(ISD::UNDEF, VT); 893 // fold (shl x, 0) -> x 894 if (N1C && N1C->isNullValue()) 895 return N0; 896 // if (shl x, c) is known to be zero, return 0 897 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 898 return DAG.getConstant(0, VT); 899 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 900 if (N1C && N0.getOpcode() == ISD::SHL && 901 N0.getOperand(1).getOpcode() == ISD::Constant) { 902 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 903 uint64_t c2 = N1C->getValue(); 904 if (c1 + c2 > OpSizeInBits) 905 return DAG.getConstant(0, VT); 906 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 907 DAG.getConstant(c1 + c2, N1.getValueType())); 908 } 909 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 910 // (srl (and x, -1 << c1), c1-c2) 911 if (N1C && N0.getOpcode() == ISD::SRL && 912 N0.getOperand(1).getOpcode() == ISD::Constant) { 913 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 914 uint64_t c2 = N1C->getValue(); 915 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 916 DAG.getConstant(~0ULL << c1, VT)); 917 if (c2 > c1) 918 return DAG.getNode(ISD::SHL, VT, Mask, 919 DAG.getConstant(c2-c1, N1.getValueType())); 920 else 921 return DAG.getNode(ISD::SRL, VT, Mask, 922 DAG.getConstant(c1-c2, N1.getValueType())); 923 } 924 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 925 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 926 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 927 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 928 return SDOperand(); 929} 930 931SDOperand DAGCombiner::visitSRA(SDNode *N) { 932 SDOperand N0 = N->getOperand(0); 933 SDOperand N1 = N->getOperand(1); 934 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 935 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 936 MVT::ValueType VT = N0.getValueType(); 937 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 938 939 // fold (sra c1, c2) -> c1>>c2 940 if (N0C && N1C) 941 return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT); 942 // fold (sra 0, x) -> 0 943 if (N0C && N0C->isNullValue()) 944 return N0; 945 // fold (sra -1, x) -> -1 946 if (N0C && N0C->isAllOnesValue()) 947 return N0; 948 // fold (sra x, c >= size(x)) -> undef 949 if (N1C && N1C->getValue() >= OpSizeInBits) 950 return DAG.getNode(ISD::UNDEF, VT); 951 // fold (sra x, 0) -> x 952 if (N1C && N1C->isNullValue()) 953 return N0; 954 // If the sign bit is known to be zero, switch this to a SRL. 955 if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI)) 956 return DAG.getNode(ISD::SRL, VT, N0, N1); 957 return SDOperand(); 958} 959 960SDOperand DAGCombiner::visitSRL(SDNode *N) { 961 SDOperand N0 = N->getOperand(0); 962 SDOperand N1 = N->getOperand(1); 963 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 964 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 965 MVT::ValueType VT = N0.getValueType(); 966 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 967 968 // fold (srl c1, c2) -> c1 >>u c2 969 if (N0C && N1C) 970 return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT); 971 // fold (srl 0, x) -> 0 972 if (N0C && N0C->isNullValue()) 973 return N0; 974 // fold (srl x, c >= size(x)) -> undef 975 if (N1C && N1C->getValue() >= OpSizeInBits) 976 return DAG.getNode(ISD::UNDEF, VT); 977 // fold (srl x, 0) -> x 978 if (N1C && N1C->isNullValue()) 979 return N0; 980 // if (srl x, c) is known to be zero, return 0 981 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 982 return DAG.getConstant(0, VT); 983 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 984 if (N1C && N0.getOpcode() == ISD::SRL && 985 N0.getOperand(1).getOpcode() == ISD::Constant) { 986 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 987 uint64_t c2 = N1C->getValue(); 988 if (c1 + c2 > OpSizeInBits) 989 return DAG.getConstant(0, VT); 990 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 991 DAG.getConstant(c1 + c2, N1.getValueType())); 992 } 993 return SDOperand(); 994} 995 996SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 997 SDOperand N0 = N->getOperand(0); 998 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 999 1000 // fold (ctlz c1) -> c2 1001 if (N0C) 1002 return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()), 1003 N0.getValueType()); 1004 return SDOperand(); 1005} 1006 1007SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 1008 SDOperand N0 = N->getOperand(0); 1009 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1010 1011 // fold (cttz c1) -> c2 1012 if (N0C) 1013 return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()), 1014 N0.getValueType()); 1015 return SDOperand(); 1016} 1017 1018SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 1019 SDOperand N0 = N->getOperand(0); 1020 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1021 1022 // fold (ctpop c1) -> c2 1023 if (N0C) 1024 return DAG.getConstant(CountPopulation_64(N0C->getValue()), 1025 N0.getValueType()); 1026 return SDOperand(); 1027} 1028 1029SDOperand DAGCombiner::visitSELECT(SDNode *N) { 1030 SDOperand N0 = N->getOperand(0); 1031 SDOperand N1 = N->getOperand(1); 1032 SDOperand N2 = N->getOperand(2); 1033 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1034 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1035 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1036 MVT::ValueType VT = N->getValueType(0); 1037 1038 // fold select C, X, X -> X 1039 if (N1 == N2) 1040 return N1; 1041 // fold select true, X, Y -> X 1042 if (N0C && !N0C->isNullValue()) 1043 return N1; 1044 // fold select false, X, Y -> Y 1045 if (N0C && N0C->isNullValue()) 1046 return N2; 1047 // fold select C, 1, X -> C | X 1048 if (MVT::i1 == VT && N1C && N1C->getValue() == 1) 1049 return DAG.getNode(ISD::OR, VT, N0, N2); 1050 // fold select C, 0, X -> ~C & X 1051 // FIXME: this should check for C type == X type, not i1? 1052 if (MVT::i1 == VT && N1C && N1C->isNullValue()) { 1053 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1054 WorkList.push_back(XORNode.Val); 1055 return DAG.getNode(ISD::AND, VT, XORNode, N2); 1056 } 1057 // fold select C, X, 1 -> ~C | X 1058 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) { 1059 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1060 WorkList.push_back(XORNode.Val); 1061 return DAG.getNode(ISD::OR, VT, XORNode, N1); 1062 } 1063 // fold select C, X, 0 -> C & X 1064 // FIXME: this should check for C type == X type, not i1? 1065 if (MVT::i1 == VT && N2C && N2C->isNullValue()) 1066 return DAG.getNode(ISD::AND, VT, N0, N1); 1067 // fold X ? X : Y --> X ? 1 : Y --> X | Y 1068 if (MVT::i1 == VT && N0 == N1) 1069 return DAG.getNode(ISD::OR, VT, N0, N2); 1070 // fold X ? Y : X --> X ? Y : 0 --> X & Y 1071 if (MVT::i1 == VT && N0 == N2) 1072 return DAG.getNode(ISD::AND, VT, N0, N1); 1073 // fold selects based on a setcc into other things, such as min/max/abs 1074 if (N0.getOpcode() == ISD::SETCC) 1075 return SimplifySelect(N0, N1, N2); 1076 return SDOperand(); 1077} 1078 1079SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) { 1080 SDOperand N0 = N->getOperand(0); 1081 SDOperand N1 = N->getOperand(1); 1082 SDOperand N2 = N->getOperand(2); 1083 SDOperand N3 = N->getOperand(3); 1084 SDOperand N4 = N->getOperand(4); 1085 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1086 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1087 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1088 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 1089 1090 // Determine if the condition we're dealing with is constant 1091 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1092 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1093 1094 // fold select_cc lhs, rhs, x, x, cc -> x 1095 if (N2 == N3) 1096 return N2; 1097 // fold select_cc true, x, y -> x 1098 if (SCCC && SCCC->getValue()) 1099 return N2; 1100 // fold select_cc false, x, y -> y 1101 if (SCCC && SCCC->getValue() == 0) 1102 return N3; 1103 // fold select_cc into other things, such as min/max/abs 1104 return SimplifySelectCC(N0, N1, N2, N3, CC); 1105} 1106 1107SDOperand DAGCombiner::visitSETCC(SDNode *N) { 1108 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 1109 cast<CondCodeSDNode>(N->getOperand(2))->get()); 1110} 1111 1112SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 1113 SDOperand N0 = N->getOperand(0); 1114 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1115 MVT::ValueType VT = N->getValueType(0); 1116 1117 // fold (sext c1) -> c1 1118 if (N0C) 1119 return DAG.getConstant(N0C->getSignExtended(), VT); 1120 // fold (sext (sext x)) -> (sext x) 1121 if (N0.getOpcode() == ISD::SIGN_EXTEND) 1122 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1123 return SDOperand(); 1124} 1125 1126SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1127 SDOperand N0 = N->getOperand(0); 1128 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1129 MVT::ValueType VT = N->getValueType(0); 1130 1131 // fold (zext c1) -> c1 1132 if (N0C) 1133 return DAG.getConstant(N0C->getValue(), VT); 1134 // fold (zext (zext x)) -> (zext x) 1135 if (N0.getOpcode() == ISD::ZERO_EXTEND) 1136 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1137 return SDOperand(); 1138} 1139 1140SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 1141 SDOperand N0 = N->getOperand(0); 1142 SDOperand N1 = N->getOperand(1); 1143 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1144 MVT::ValueType VT = N->getValueType(0); 1145 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 1146 1147 // fold (sext_in_reg c1) -> c1 1148 if (N0C) { 1149 SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT); 1150 return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate); 1151 } 1152 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1 1153 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1154 cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) { 1155 return N0; 1156 } 1157 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 1158 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1159 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 1160 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 1161 } 1162 // fold (sext_in_reg (assert_sext x)) -> (assert_sext x) 1163 if (N0.getOpcode() == ISD::AssertSext && 1164 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) { 1165 return N0; 1166 } 1167 // fold (sext_in_reg (sextload x)) -> (sextload x) 1168 if (N0.getOpcode() == ISD::SEXTLOAD && 1169 cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) { 1170 return N0; 1171 } 1172 // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1 1173 // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here 1174 if (N0.getOpcode() == ISD::SETCC && 1175 TLI.getSetCCResultContents() == 1176 TargetLowering::ZeroOrNegativeOneSetCCResult) 1177 return N0; 1178 // FIXME: this code is currently just ported over from SelectionDAG.cpp 1179 // we probably actually want to handle this in two pieces. Rather than 1180 // checking all the top bits for zero, just check the sign bit here and turn 1181 // it into a zero extend inreg (AND with constant). 1182 // then, let the code for AND figure out if the mask is superfluous rather 1183 // than doing so here. 1184 if (N0.getOpcode() == ISD::AND && 1185 N0.getOperand(1).getOpcode() == ISD::Constant) { 1186 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1187 unsigned NumBits = MVT::getSizeInBits(EVT); 1188 if ((Mask & (~0ULL << (NumBits-1))) == 0) 1189 return N0; 1190 } 1191 return SDOperand(); 1192} 1193 1194SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 1195 SDOperand N0 = N->getOperand(0); 1196 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1197 MVT::ValueType VT = N->getValueType(0); 1198 1199 // noop truncate 1200 if (N0.getValueType() == N->getValueType(0)) 1201 return N0; 1202 // fold (truncate c1) -> c1 1203 if (N0C) 1204 return DAG.getConstant(N0C->getValue(), VT); 1205 // fold (truncate (truncate x)) -> (truncate x) 1206 if (N0.getOpcode() == ISD::TRUNCATE) 1207 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1208 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 1209 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){ 1210 if (N0.getValueType() < VT) 1211 // if the source is smaller than the dest, we still need an extend 1212 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1213 else if (N0.getValueType() > VT) 1214 // if the source is larger than the dest, than we just need the truncate 1215 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1216 else 1217 // if the source and dest are the same type, we can drop both the extend 1218 // and the truncate 1219 return N0.getOperand(0); 1220 } 1221 return SDOperand(); 1222} 1223 1224SDOperand DAGCombiner::visitFADD(SDNode *N) { 1225 SDOperand N0 = N->getOperand(0); 1226 SDOperand N1 = N->getOperand(1); 1227 MVT::ValueType VT = N->getValueType(0); 1228 1229 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1230 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1231 // fold floating point (fadd c1, c2) 1232 return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(), 1233 N->getValueType(0)); 1234 } 1235 // fold (A + (-B)) -> A-B 1236 if (N1.getOpcode() == ISD::FNEG) 1237 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0)); 1238 1239 // fold ((-A) + B) -> B-A 1240 if (N0.getOpcode() == ISD::FNEG) 1241 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0)); 1242 1243 return SDOperand(); 1244} 1245 1246SDOperand DAGCombiner::visitFSUB(SDNode *N) { 1247 SDOperand N0 = N->getOperand(0); 1248 SDOperand N1 = N->getOperand(1); 1249 MVT::ValueType VT = N->getValueType(0); 1250 1251 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1252 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1253 // fold floating point (fsub c1, c2) 1254 return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(), 1255 N->getValueType(0)); 1256 } 1257 // fold (A-(-B)) -> A+B 1258 if (N1.getOpcode() == ISD::FNEG) 1259 return DAG.getNode(ISD::FADD, N0.getValueType(), N0, N1.getOperand(0)); 1260 1261 return SDOperand(); 1262} 1263 1264SDOperand DAGCombiner::visitFMUL(SDNode *N) { 1265 SDOperand N0 = N->getOperand(0); 1266 SDOperand N1 = N->getOperand(1); 1267 MVT::ValueType VT = N->getValueType(0); 1268 1269 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1270 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1271 // fold floating point (fmul c1, c2) 1272 return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(), 1273 N->getValueType(0)); 1274 } 1275 return SDOperand(); 1276} 1277 1278SDOperand DAGCombiner::visitFDIV(SDNode *N) { 1279 SDOperand N0 = N->getOperand(0); 1280 SDOperand N1 = N->getOperand(1); 1281 MVT::ValueType VT = N->getValueType(0); 1282 1283 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1284 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1285 // fold floating point (fdiv c1, c2) 1286 return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(), 1287 N->getValueType(0)); 1288 } 1289 return SDOperand(); 1290} 1291 1292SDOperand DAGCombiner::visitFREM(SDNode *N) { 1293 SDOperand N0 = N->getOperand(0); 1294 SDOperand N1 = N->getOperand(1); 1295 MVT::ValueType VT = N->getValueType(0); 1296 1297 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0)) 1298 if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) { 1299 // fold floating point (frem c1, c2) -> fmod(c1, c2) 1300 return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()), 1301 N->getValueType(0)); 1302 } 1303 return SDOperand(); 1304} 1305 1306 1307SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 1308 SDOperand N0 = N->getOperand(0); 1309 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1310 1311 // fold (sint_to_fp c1) -> c1fp 1312 if (N0C) 1313 return DAG.getConstantFP(N0C->getSignExtended(), N->getValueType(0)); 1314 return SDOperand(); 1315} 1316 1317SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 1318 SDOperand N0 = N->getOperand(0); 1319 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1320 1321 // fold (uint_to_fp c1) -> c1fp 1322 if (N0C) 1323 return DAG.getConstantFP(N0C->getValue(), N->getValueType(0)); 1324 return SDOperand(); 1325} 1326 1327SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 1328 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1329 1330 // fold (fp_to_sint c1fp) -> c1 1331 if (N0CFP) 1332 return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0)); 1333 return SDOperand(); 1334} 1335 1336SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 1337 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1338 1339 // fold (fp_to_uint c1fp) -> c1 1340 if (N0CFP) 1341 return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0)); 1342 return SDOperand(); 1343} 1344 1345SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 1346 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1347 1348 // fold (fp_round c1fp) -> c1fp 1349 if (N0CFP) 1350 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1351 return SDOperand(); 1352} 1353 1354SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 1355 SDOperand N0 = N->getOperand(0); 1356 MVT::ValueType VT = N->getValueType(0); 1357 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 1358 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1359 1360 // fold (fp_round_inreg c1fp) -> c1fp 1361 if (N0CFP) { 1362 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 1363 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 1364 } 1365 return SDOperand(); 1366} 1367 1368SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 1369 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1370 1371 // fold (fp_extend c1fp) -> c1fp 1372 if (N0CFP) 1373 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1374 return SDOperand(); 1375} 1376 1377SDOperand DAGCombiner::visitFNEG(SDNode *N) { 1378 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1379 // fold (neg c1) -> -c1 1380 if (N0CFP) 1381 return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0)); 1382 // fold (neg (sub x, y)) -> (sub y, x) 1383 if (N->getOperand(0).getOpcode() == ISD::SUB) 1384 return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1), 1385 N->getOperand(0)); 1386 // fold (neg (neg x)) -> x 1387 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1388 return N->getOperand(0).getOperand(0); 1389 return SDOperand(); 1390} 1391 1392SDOperand DAGCombiner::visitFABS(SDNode *N) { 1393 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1394 // fold (fabs c1) -> fabs(c1) 1395 if (N0CFP) 1396 return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0)); 1397 // fold (fabs (fabs x)) -> (fabs x) 1398 if (N->getOperand(0).getOpcode() == ISD::FABS) 1399 return N->getOperand(0); 1400 // fold (fabs (fneg x)) -> (fabs x) 1401 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1402 return DAG.getNode(ISD::FABS, N->getValueType(0), 1403 N->getOperand(0).getOperand(0)); 1404 return SDOperand(); 1405} 1406 1407SDOperand DAGCombiner::visitBRCOND(SDNode *N) { 1408 SDOperand Chain = N->getOperand(0); 1409 SDOperand N1 = N->getOperand(1); 1410 SDOperand N2 = N->getOperand(2); 1411 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1412 1413 // never taken branch, fold to chain 1414 if (N1C && N1C->isNullValue()) 1415 return Chain; 1416 // unconditional branch 1417 if (N1C && N1C->getValue() == 1) 1418 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 1419 return SDOperand(); 1420} 1421 1422SDOperand DAGCombiner::visitBRCONDTWOWAY(SDNode *N) { 1423 SDOperand Chain = N->getOperand(0); 1424 SDOperand N1 = N->getOperand(1); 1425 SDOperand N2 = N->getOperand(2); 1426 SDOperand N3 = N->getOperand(3); 1427 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1428 1429 // unconditional branch to true mbb 1430 if (N1C && N1C->getValue() == 1) 1431 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 1432 // unconditional branch to false mbb 1433 if (N1C && N1C->isNullValue()) 1434 return DAG.getNode(ISD::BR, MVT::Other, Chain, N3); 1435 return SDOperand(); 1436} 1437 1438// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 1439// 1440SDOperand DAGCombiner::visitBR_CC(SDNode *N) { 1441 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 1442 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 1443 1444 // Use SimplifySetCC to simplify SETCC's. 1445 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false); 1446 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val); 1447 1448 // fold br_cc true, dest -> br dest (unconditional branch) 1449 if (SCCC && SCCC->getValue()) 1450 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 1451 N->getOperand(4)); 1452 // fold br_cc false, dest -> unconditional fall through 1453 if (SCCC && SCCC->isNullValue()) 1454 return N->getOperand(0); 1455 // fold to a simpler setcc 1456 if (Simp.Val && Simp.getOpcode() == ISD::SETCC) 1457 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 1458 Simp.getOperand(2), Simp.getOperand(0), 1459 Simp.getOperand(1), N->getOperand(4)); 1460 return SDOperand(); 1461} 1462 1463SDOperand DAGCombiner::visitBRTWOWAY_CC(SDNode *N) { 1464 SDOperand Chain = N->getOperand(0); 1465 SDOperand CCN = N->getOperand(1); 1466 SDOperand LHS = N->getOperand(2); 1467 SDOperand RHS = N->getOperand(3); 1468 SDOperand N4 = N->getOperand(4); 1469 SDOperand N5 = N->getOperand(5); 1470 1471 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), LHS, RHS, 1472 cast<CondCodeSDNode>(CCN)->get(), false); 1473 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1474 1475 // fold select_cc lhs, rhs, x, x, cc -> x 1476 if (N4 == N5) 1477 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 1478 // fold select_cc true, x, y -> x 1479 if (SCCC && SCCC->getValue()) 1480 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 1481 // fold select_cc false, x, y -> y 1482 if (SCCC && SCCC->isNullValue()) 1483 return DAG.getNode(ISD::BR, MVT::Other, Chain, N5); 1484 // fold to a simpler setcc 1485 if (SCC.Val && SCC.getOpcode() == ISD::SETCC) 1486 return DAG.getBR2Way_CC(Chain, SCC.getOperand(2), SCC.getOperand(0), 1487 SCC.getOperand(1), N4, N5); 1488 return SDOperand(); 1489} 1490 1491SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 1492 return SDOperand(); 1493} 1494 1495SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 1496 SDOperand N2, SDOperand N3, 1497 ISD::CondCode CC) { 1498 return SDOperand(); 1499} 1500 1501SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 1502 SDOperand N1, ISD::CondCode Cond, 1503 bool foldBooleans) { 1504 // These setcc operations always fold. 1505 switch (Cond) { 1506 default: break; 1507 case ISD::SETFALSE: 1508 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 1509 case ISD::SETTRUE: 1510 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 1511 } 1512 1513 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 1514 uint64_t C1 = N1C->getValue(); 1515 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) { 1516 uint64_t C0 = N0C->getValue(); 1517 1518 // Sign extend the operands if required 1519 if (ISD::isSignedIntSetCC(Cond)) { 1520 C0 = N0C->getSignExtended(); 1521 C1 = N1C->getSignExtended(); 1522 } 1523 1524 switch (Cond) { 1525 default: assert(0 && "Unknown integer setcc!"); 1526 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 1527 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 1528 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT); 1529 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT); 1530 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT); 1531 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT); 1532 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT); 1533 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT); 1534 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT); 1535 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT); 1536 } 1537 } else { 1538 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 1539 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 1540 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 1541 1542 // If the comparison constant has bits in the upper part, the 1543 // zero-extended value could never match. 1544 if (C1 & (~0ULL << InSize)) { 1545 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 1546 switch (Cond) { 1547 case ISD::SETUGT: 1548 case ISD::SETUGE: 1549 case ISD::SETEQ: return DAG.getConstant(0, VT); 1550 case ISD::SETULT: 1551 case ISD::SETULE: 1552 case ISD::SETNE: return DAG.getConstant(1, VT); 1553 case ISD::SETGT: 1554 case ISD::SETGE: 1555 // True if the sign bit of C1 is set. 1556 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 1557 case ISD::SETLT: 1558 case ISD::SETLE: 1559 // True if the sign bit of C1 isn't set. 1560 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 1561 default: 1562 break; 1563 } 1564 } 1565 1566 // Otherwise, we can perform the comparison with the low bits. 1567 switch (Cond) { 1568 case ISD::SETEQ: 1569 case ISD::SETNE: 1570 case ISD::SETUGT: 1571 case ISD::SETUGE: 1572 case ISD::SETULT: 1573 case ISD::SETULE: 1574 return DAG.getSetCC(VT, N0.getOperand(0), 1575 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 1576 Cond); 1577 default: 1578 break; // todo, be more careful with signed comparisons 1579 } 1580 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1581 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 1582 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 1583 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 1584 MVT::ValueType ExtDstTy = N0.getValueType(); 1585 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 1586 1587 // If the extended part has any inconsistent bits, it cannot ever 1588 // compare equal. In other words, they have to be all ones or all 1589 // zeros. 1590 uint64_t ExtBits = 1591 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 1592 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 1593 return DAG.getConstant(Cond == ISD::SETNE, VT); 1594 1595 SDOperand ZextOp; 1596 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 1597 if (Op0Ty == ExtSrcTy) { 1598 ZextOp = N0.getOperand(0); 1599 } else { 1600 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 1601 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 1602 DAG.getConstant(Imm, Op0Ty)); 1603 } 1604 WorkList.push_back(ZextOp.Val); 1605 // Otherwise, make this a use of a zext. 1606 return DAG.getSetCC(VT, ZextOp, 1607 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 1608 ExtDstTy), 1609 Cond); 1610 } 1611 1612 uint64_t MinVal, MaxVal; 1613 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 1614 if (ISD::isSignedIntSetCC(Cond)) { 1615 MinVal = 1ULL << (OperandBitSize-1); 1616 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 1617 MaxVal = ~0ULL >> (65-OperandBitSize); 1618 else 1619 MaxVal = 0; 1620 } else { 1621 MinVal = 0; 1622 MaxVal = ~0ULL >> (64-OperandBitSize); 1623 } 1624 1625 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 1626 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 1627 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 1628 --C1; // X >= C0 --> X > (C0-1) 1629 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 1630 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 1631 } 1632 1633 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 1634 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 1635 ++C1; // X <= C0 --> X < (C0+1) 1636 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 1637 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 1638 } 1639 1640 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 1641 return DAG.getConstant(0, VT); // X < MIN --> false 1642 1643 // Canonicalize setgt X, Min --> setne X, Min 1644 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 1645 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 1646 1647 // If we have setult X, 1, turn it into seteq X, 0 1648 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 1649 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 1650 ISD::SETEQ); 1651 // If we have setugt X, Max-1, turn it into seteq X, Max 1652 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 1653 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 1654 ISD::SETEQ); 1655 1656 // If we have "setcc X, C0", check to see if we can shrink the immediate 1657 // by changing cc. 1658 1659 // SETUGT X, SINTMAX -> SETLT X, 0 1660 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 1661 C1 == (~0ULL >> (65-OperandBitSize))) 1662 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 1663 ISD::SETLT); 1664 1665 // FIXME: Implement the rest of these. 1666 1667 // Fold bit comparisons when we can. 1668 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1669 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 1670 if (ConstantSDNode *AndRHS = 1671 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1672 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 1673 // Perform the xform if the AND RHS is a single bit. 1674 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 1675 return DAG.getNode(ISD::SRL, VT, N0, 1676 DAG.getConstant(Log2_64(AndRHS->getValue()), 1677 TLI.getShiftAmountTy())); 1678 } 1679 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 1680 // (X & 8) == 8 --> (X & 8) >> 3 1681 // Perform the xform if C1 is a single bit. 1682 if ((C1 & (C1-1)) == 0) { 1683 return DAG.getNode(ISD::SRL, VT, N0, 1684 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 1685 } 1686 } 1687 } 1688 } 1689 } else if (isa<ConstantSDNode>(N0.Val)) { 1690 // Ensure that the constant occurs on the RHS. 1691 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 1692 } 1693 1694 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val)) 1695 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) { 1696 double C0 = N0C->getValue(), C1 = N1C->getValue(); 1697 1698 switch (Cond) { 1699 default: break; // FIXME: Implement the rest of these! 1700 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 1701 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 1702 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT); 1703 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT); 1704 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT); 1705 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT); 1706 } 1707 } else { 1708 // Ensure that the constant occurs on the RHS. 1709 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 1710 } 1711 1712 if (N0 == N1) { 1713 // We can always fold X == Y for integer setcc's. 1714 if (MVT::isInteger(N0.getValueType())) 1715 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1716 unsigned UOF = ISD::getUnorderedFlavor(Cond); 1717 if (UOF == 2) // FP operators that are undefined on NaNs. 1718 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 1719 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 1720 return DAG.getConstant(UOF, VT); 1721 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 1722 // if it is not already. 1723 ISD::CondCode NewCond = UOF == 0 ? ISD::SETUO : ISD::SETO; 1724 if (NewCond != Cond) 1725 return DAG.getSetCC(VT, N0, N1, NewCond); 1726 } 1727 1728 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1729 MVT::isInteger(N0.getValueType())) { 1730 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 1731 N0.getOpcode() == ISD::XOR) { 1732 // Simplify (X+Y) == (X+Z) --> Y == Z 1733 if (N0.getOpcode() == N1.getOpcode()) { 1734 if (N0.getOperand(0) == N1.getOperand(0)) 1735 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 1736 if (N0.getOperand(1) == N1.getOperand(1)) 1737 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 1738 if (isCommutativeBinOp(N0.getOpcode())) { 1739 // If X op Y == Y op X, try other combinations. 1740 if (N0.getOperand(0) == N1.getOperand(1)) 1741 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 1742 if (N0.getOperand(1) == N1.getOperand(0)) 1743 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 1744 } 1745 } 1746 1747 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. Common for condcodes. 1748 if (N0.getOpcode() == ISD::XOR) 1749 if (ConstantSDNode *XORC = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 1750 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 1751 // If we know that all of the inverted bits are zero, don't bother 1752 // performing the inversion. 1753 if (MaskedValueIsZero(N0.getOperand(0), ~XORC->getValue(), TLI)) 1754 return DAG.getSetCC(VT, N0.getOperand(0), 1755 DAG.getConstant(XORC->getValue()^RHSC->getValue(), 1756 N0.getValueType()), Cond); 1757 } 1758 1759 // Simplify (X+Z) == X --> Z == 0 1760 if (N0.getOperand(0) == N1) 1761 return DAG.getSetCC(VT, N0.getOperand(1), 1762 DAG.getConstant(0, N0.getValueType()), Cond); 1763 if (N0.getOperand(1) == N1) { 1764 if (isCommutativeBinOp(N0.getOpcode())) 1765 return DAG.getSetCC(VT, N0.getOperand(0), 1766 DAG.getConstant(0, N0.getValueType()), Cond); 1767 else { 1768 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 1769 // (Z-X) == X --> Z == X<<1 1770 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 1771 N1, 1772 DAG.getConstant(1,TLI.getShiftAmountTy())); 1773 WorkList.push_back(SH.Val); 1774 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 1775 } 1776 } 1777 } 1778 1779 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 1780 N1.getOpcode() == ISD::XOR) { 1781 // Simplify X == (X+Z) --> Z == 0 1782 if (N1.getOperand(0) == N0) { 1783 return DAG.getSetCC(VT, N1.getOperand(1), 1784 DAG.getConstant(0, N1.getValueType()), Cond); 1785 } else if (N1.getOperand(1) == N0) { 1786 if (isCommutativeBinOp(N1.getOpcode())) { 1787 return DAG.getSetCC(VT, N1.getOperand(0), 1788 DAG.getConstant(0, N1.getValueType()), Cond); 1789 } else { 1790 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 1791 // X == (Z-X) --> X<<1 == Z 1792 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 1793 DAG.getConstant(1,TLI.getShiftAmountTy())); 1794 WorkList.push_back(SH.Val); 1795 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 1796 } 1797 } 1798 } 1799 } 1800 1801 // Fold away ALL boolean setcc's. 1802 SDOperand Temp; 1803 if (N0.getValueType() == MVT::i1 && foldBooleans) { 1804 switch (Cond) { 1805 default: assert(0 && "Unknown integer setcc!"); 1806 case ISD::SETEQ: // X == Y -> (X^Y)^1 1807 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1808 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 1809 WorkList.push_back(Temp.Val); 1810 break; 1811 case ISD::SETNE: // X != Y --> (X^Y) 1812 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 1813 break; 1814 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 1815 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 1816 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1817 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 1818 WorkList.push_back(Temp.Val); 1819 break; 1820 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 1821 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 1822 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 1823 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 1824 WorkList.push_back(Temp.Val); 1825 break; 1826 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 1827 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 1828 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 1829 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 1830 WorkList.push_back(Temp.Val); 1831 break; 1832 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 1833 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 1834 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 1835 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 1836 break; 1837 } 1838 if (VT != MVT::i1) { 1839 WorkList.push_back(N0.Val); 1840 // FIXME: If running after legalize, we probably can't do this. 1841 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 1842 } 1843 return N0; 1844 } 1845 1846 // Could not fold it. 1847 return SDOperand(); 1848} 1849 1850// SelectionDAG::Combine - This is the entry point for the file. 1851// 1852void SelectionDAG::Combine(bool RunningAfterLegalize) { 1853 /// run - This is the main entry point to this class. 1854 /// 1855 DAGCombiner(*this).Run(RunningAfterLegalize); 1856} 1857