DAGCombiner.cpp revision a500fc681de6329194e9755e051422d621387aa3
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: mul (x, const) -> shifts + adds 24// FIXME: undef values 25// FIXME: zero extend when top bits are 0 -> drop it ? 26// FIXME: make truncate see through SIGN_EXTEND and AND 27// FIXME: sext_in_reg(setcc) on targets that return zero or one, and where 28// EVT != MVT::i1 can drop the sext. 29// FIXME: (sra (sra x, c1), c2) -> (sra x, c1+c2) 30// FIXME: verify that getNode can't return extends with an operand whose type 31// is >= to that of the extend. 32// FIXME: divide by zero is currently left unfolded. do we want to turn this 33// into an undef? 34// 35//===----------------------------------------------------------------------===// 36 37#define DEBUG_TYPE "dagcombine" 38#include "llvm/ADT/Statistic.h" 39#include "llvm/CodeGen/SelectionDAG.h" 40#include "llvm/Support/Debug.h" 41#include "llvm/Support/MathExtras.h" 42#include "llvm/Target/TargetLowering.h" 43#include <algorithm> 44#include <cmath> 45using namespace llvm; 46 47namespace { 48 Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined"); 49 50 class DAGCombiner { 51 SelectionDAG &DAG; 52 TargetLowering &TLI; 53 bool AfterLegalize; 54 55 // Worklist of all of the nodes that need to be simplified. 56 std::vector<SDNode*> WorkList; 57 58 /// AddUsersToWorkList - When an instruction is simplified, add all users of 59 /// the instruction to the work lists because they might get more simplified 60 /// now. 61 /// 62 void AddUsersToWorkList(SDNode *N) { 63 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 64 UI != UE; ++UI) 65 WorkList.push_back(*UI); 66 } 67 68 /// removeFromWorkList - remove all instances of N from the worklist. 69 void removeFromWorkList(SDNode *N) { 70 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 71 WorkList.end()); 72 } 73 74 /// visit - call the node-specific routine that knows how to fold each 75 /// particular type of node. 76 SDOperand visit(SDNode *N); 77 78 // Visitation implementation - Implement dag node combining for different 79 // node types. The semantics are as follows: 80 // Return Value: 81 // SDOperand.Val == 0 - No change was made 82 // otherwise - N should be replaced by the returned Operand. 83 // 84 SDOperand visitTokenFactor(SDNode *N); 85 SDOperand visitADD(SDNode *N); 86 SDOperand visitSUB(SDNode *N); 87 SDOperand visitMUL(SDNode *N); 88 SDOperand visitSDIV(SDNode *N); 89 SDOperand visitUDIV(SDNode *N); 90 SDOperand visitSREM(SDNode *N); 91 SDOperand visitUREM(SDNode *N); 92 SDOperand visitMULHU(SDNode *N); 93 SDOperand visitMULHS(SDNode *N); 94 SDOperand visitAND(SDNode *N); 95 SDOperand visitOR(SDNode *N); 96 SDOperand visitXOR(SDNode *N); 97 SDOperand visitSHL(SDNode *N); 98 SDOperand visitSRA(SDNode *N); 99 SDOperand visitSRL(SDNode *N); 100 SDOperand visitCTLZ(SDNode *N); 101 SDOperand visitCTTZ(SDNode *N); 102 SDOperand visitCTPOP(SDNode *N); 103 // select 104 // select_cc 105 // setcc 106 SDOperand visitSIGN_EXTEND(SDNode *N); 107 SDOperand visitZERO_EXTEND(SDNode *N); 108 SDOperand visitSIGN_EXTEND_INREG(SDNode *N); 109 SDOperand visitTRUNCATE(SDNode *N); 110 SDOperand visitSINT_TO_FP(SDNode *N); 111 SDOperand visitUINT_TO_FP(SDNode *N); 112 SDOperand visitFP_TO_SINT(SDNode *N); 113 SDOperand visitFP_TO_UINT(SDNode *N); 114 SDOperand visitFP_ROUND(SDNode *N); 115 SDOperand visitFP_ROUND_INREG(SDNode *N); 116 SDOperand visitFP_EXTEND(SDNode *N); 117 SDOperand visitFNEG(SDNode *N); 118 SDOperand visitFABS(SDNode *N); 119 // brcond 120 // brcondtwoway 121 // br_cc 122 // brtwoway_cc 123public: 124 DAGCombiner(SelectionDAG &D) 125 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {} 126 127 /// Run - runs the dag combiner on all nodes in the work list 128 void Run(bool RunningAfterLegalize); 129 }; 130} 131 132/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 133/// this predicate to simplify operations downstream. V and Mask are known to 134/// be the same type. 135static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask, 136 const TargetLowering &TLI) { 137 unsigned SrcBits; 138 if (Mask == 0) return true; 139 140 // If we know the result of a setcc has the top bits zero, use this info. 141 switch (Op.getOpcode()) { 142 case ISD::Constant: 143 return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0; 144 case ISD::SETCC: 145 // FIXME: teach this about non ZeroOrOne values, such as 0 or -1 146 return ((Mask & 1) == 0) && 147 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult; 148 case ISD::ZEXTLOAD: 149 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 150 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits. 151 case ISD::ZERO_EXTEND: 152 SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType()); 153 return MaskedValueIsZero(Op.getOperand(0),Mask & ((1ULL << SrcBits)-1),TLI); 154 case ISD::AssertZext: 155 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 156 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits. 157 case ISD::AND: 158 // (X & C1) & C2 == 0 iff C1 & C2 == 0. 159 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 160 return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI); 161 // FALL THROUGH 162 case ISD::OR: 163 case ISD::XOR: 164 return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) && 165 MaskedValueIsZero(Op.getOperand(1), Mask, TLI); 166 case ISD::SELECT: 167 return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) && 168 MaskedValueIsZero(Op.getOperand(2), Mask, TLI); 169 case ISD::SELECT_CC: 170 return MaskedValueIsZero(Op.getOperand(2), Mask, TLI) && 171 MaskedValueIsZero(Op.getOperand(3), Mask, TLI); 172 case ISD::SRL: 173 // (ushr X, C1) & C2 == 0 iff X & (C2 << C1) == 0 174 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 175 uint64_t NewVal = Mask << ShAmt->getValue(); 176 SrcBits = MVT::getSizeInBits(Op.getValueType()); 177 if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1; 178 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI); 179 } 180 return false; 181 case ISD::SHL: 182 // (ushl X, C1) & C2 == 0 iff X & (C2 >> C1) == 0 183 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 184 uint64_t NewVal = Mask >> ShAmt->getValue(); 185 return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI); 186 } 187 return false; 188 case ISD::CTTZ: 189 case ISD::CTLZ: 190 case ISD::CTPOP: 191 // Bit counting instructions can not set the high bits of the result 192 // register. The max number of bits sets depends on the input. 193 return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0; 194 195 // TODO we could handle some SRA cases here. 196 default: break; 197 } 198 return false; 199} 200 201// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 202// that selects between the values 1 and 0, making it equivalent to a setcc. 203// Also, set the incoming LHS, RHS, and CC references to the appropriate 204// nodes based on the type of node we are checking. This simplifies life a 205// bit for the callers. 206static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 207 SDOperand &CC) { 208 if (N.getOpcode() == ISD::SETCC) { 209 LHS = N.getOperand(0); 210 RHS = N.getOperand(1); 211 CC = N.getOperand(2); 212 return true; 213 } 214 if (N.getOpcode() == ISD::SELECT_CC && 215 N.getOperand(2).getOpcode() == ISD::Constant && 216 N.getOperand(3).getOpcode() == ISD::Constant && 217 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 218 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 219 LHS = N.getOperand(0); 220 RHS = N.getOperand(1); 221 CC = N.getOperand(4); 222 return true; 223 } 224 return false; 225} 226 227// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 228// one use. If this is true, it allows the users to invert the operation for 229// free when it is profitable to do so. 230static bool isOneUseSetCC(SDOperand N) { 231 SDOperand N0, N1, N2; 232 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 233 return true; 234 return false; 235} 236 237void DAGCombiner::Run(bool RunningAfterLegalize) { 238 // set the instance variable, so that the various visit routines may use it. 239 AfterLegalize = RunningAfterLegalize; 240 241 // Add all the dag nodes to the worklist. 242 WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end()); 243 244 // while the worklist isn't empty, inspect the node on the end of it and 245 // try and combine it. 246 while (!WorkList.empty()) { 247 SDNode *N = WorkList.back(); 248 WorkList.pop_back(); 249 250 // If N has no uses, it is dead. Make sure to revisit all N's operands once 251 // N is deleted from the DAG, since they too may now be dead. 252 // FIXME: is there a better way to keep from deleting the dag root because 253 // we think it has no uses? This works for now... 254 if (N->use_empty() && N != DAG.getRoot().Val) { 255 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 256 WorkList.push_back(N->getOperand(i).Val); 257 258 DAG.DeleteNode(N); 259 removeFromWorkList(N); 260 continue; 261 } 262 263 SDOperand RV = visit(N); 264 if (RV.Val) { 265 ++NodesCombined; 266 // If we get back the same node we passed in, rather than a new node or 267 // zero, we know that the node must have defined multiple values and 268 // CombineTo was used. Since CombineTo takes care of the worklist 269 // mechanics for us, we have no work to do in this case. 270 if (RV.Val != N) { 271 DEBUG(std::cerr << "\nReplacing "; N->dump(); 272 std::cerr << "\nWith: "; RV.Val->dump(); 273 std::cerr << '\n'); 274 DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV)); 275 276 // Push the new node and any users onto the worklist 277 WorkList.push_back(RV.Val); 278 AddUsersToWorkList(RV.Val); 279 280 // Nodes can end up on the worklist more than once. Make sure we do 281 // not process a node that has been replaced. 282 removeFromWorkList(N); 283 } 284 } 285 } 286} 287 288SDOperand DAGCombiner::visit(SDNode *N) { 289 switch(N->getOpcode()) { 290 default: break; 291 case ISD::TokenFactor: return visitTokenFactor(N); 292 case ISD::ADD: return visitADD(N); 293 case ISD::SUB: return visitSUB(N); 294 case ISD::MUL: return visitMUL(N); 295 case ISD::SDIV: return visitSDIV(N); 296 case ISD::UDIV: return visitUDIV(N); 297 case ISD::SREM: return visitSREM(N); 298 case ISD::UREM: return visitUREM(N); 299 case ISD::MULHU: return visitMULHU(N); 300 case ISD::MULHS: return visitMULHS(N); 301 case ISD::AND: return visitAND(N); 302 case ISD::OR: return visitOR(N); 303 case ISD::XOR: return visitXOR(N); 304 case ISD::SHL: return visitSHL(N); 305 case ISD::SRA: return visitSRA(N); 306 case ISD::SRL: return visitSRL(N); 307 case ISD::CTLZ: return visitCTLZ(N); 308 case ISD::CTTZ: return visitCTTZ(N); 309 case ISD::CTPOP: return visitCTPOP(N); 310 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 311 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 312 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 313 case ISD::TRUNCATE: return visitTRUNCATE(N); 314 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 315 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 316 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 317 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 318 case ISD::FP_ROUND: return visitFP_ROUND(N); 319 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 320 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 321 case ISD::FNEG: return visitFNEG(N); 322 case ISD::FABS: return visitFABS(N); 323 } 324 return SDOperand(); 325} 326 327SDOperand DAGCombiner::visitTokenFactor(SDNode *N) { 328 // If the token factor has two operands and one is the entry token, replace 329 // the token factor with the other operand. 330 if (N->getNumOperands() == 2) { 331 if (N->getOperand(0).getOpcode() == ISD::EntryToken) 332 return N->getOperand(1); 333 if (N->getOperand(1).getOpcode() == ISD::EntryToken) 334 return N->getOperand(0); 335 } 336 return SDOperand(); 337} 338 339SDOperand DAGCombiner::visitADD(SDNode *N) { 340 SDOperand N0 = N->getOperand(0); 341 SDOperand N1 = N->getOperand(1); 342 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 343 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 344 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 345 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 346 MVT::ValueType VT = N0.getValueType(); 347 348 // fold (add c1, c2) -> c1+c2 349 if (N0C && N1C) 350 return DAG.getConstant(N0C->getValue() + N1C->getValue(), VT); 351 // canonicalize constant to RHS 352 if (N0C && !N1C) { 353 std::swap(N0, N1); 354 std::swap(N0C, N1C); 355 } 356 // fold (add x, 0) -> x 357 if (N1C && N1C->isNullValue()) 358 return N0; 359 // fold floating point (add c1, c2) -> c1+c2 360 if (N0CFP && N1CFP) 361 return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(), VT); 362 // fold (add (add x, c1), c2) -> (add x, c1+c2) 363 if (N1C && N0.getOpcode() == ISD::ADD) { 364 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 365 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 366 if (N00C) 367 return DAG.getNode(ISD::ADD, VT, N0.getOperand(1), 368 DAG.getConstant(N1C->getValue()+N00C->getValue(), VT)); 369 if (N01C) 370 return DAG.getNode(ISD::ADD, VT, N0.getOperand(0), 371 DAG.getConstant(N1C->getValue()+N01C->getValue(), VT)); 372 } 373 // fold (A + (-B)) -> A-B 374 if (N1.getOpcode() == ISD::FNEG) 375 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(0)); 376 // fold ((-A) + B) -> B-A 377 if (N0.getOpcode() == ISD::FNEG) 378 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(0)); 379 // fold ((0-A) + B) -> B-A 380 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 381 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 382 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 383 // fold (A + (0-B)) -> A-B 384 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 385 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 386 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 387 // fold (A+(B-A)) -> B for non-fp types 388 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1) && 389 !MVT::isFloatingPoint(N1.getValueType())) 390 return N1.getOperand(0); 391 return SDOperand(); 392} 393 394SDOperand DAGCombiner::visitSUB(SDNode *N) { 395 SDOperand N0 = N->getOperand(0); 396 SDOperand N1 = N->getOperand(1); 397 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 398 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 399 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0.Val); 400 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 401 402 // fold (sub c1, c2) -> c1-c2 403 if (N0C && N1C) 404 return DAG.getConstant(N0C->getValue() - N1C->getValue(), 405 N->getValueType(0)); 406 // fold (sub x, 0) -> x 407 if (N1C && N1C->isNullValue()) 408 return N0; 409 // fold floating point (sub c1, c2) -> c1-c2 410 if (N0CFP && N1CFP) 411 return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(), 412 N->getValueType(0)); 413 // fold (A+B)-A -> B 414 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1 && 415 !MVT::isFloatingPoint(N1.getValueType())) 416 return N0.getOperand(1); 417 // fold (A+B)-B -> A 418 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1 && 419 !MVT::isFloatingPoint(N1.getValueType())) 420 return N0.getOperand(0); 421 // fold (A-(-B)) -> A+B 422 if (N1.getOpcode() == ISD::FNEG) 423 return DAG.getNode(ISD::ADD, N0.getValueType(), N0, N1.getOperand(0)); 424 return SDOperand(); 425} 426 427SDOperand DAGCombiner::visitMUL(SDNode *N) { 428 SDOperand N0 = N->getOperand(0); 429 SDOperand N1 = N->getOperand(1); 430 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 431 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 432 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 433 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 434 MVT::ValueType VT = N0.getValueType(); 435 436 // fold (mul c1, c2) -> c1*c2 437 if (N0C && N1C) 438 return DAG.getConstant(N0C->getValue() * N1C->getValue(), 439 N->getValueType(0)); 440 // canonicalize constant to RHS 441 if (N0C && !N1C) { 442 std::swap(N0, N1); 443 std::swap(N0C, N1C); 444 } 445 // fold (mul x, 0) -> 0 446 if (N1C && N1C->isNullValue()) 447 return N1; 448 // fold (mul x, -1) -> 0-x 449 if (N1C && N1C->isAllOnesValue()) 450 return DAG.getNode(ISD::SUB, N->getValueType(0), 451 DAG.getConstant(0, N->getValueType(0)), N0); 452 // fold (mul x, (1 << c)) -> x << c 453 if (N1C && isPowerOf2_64(N1C->getValue())) 454 return DAG.getNode(ISD::SHL, N->getValueType(0), N0, 455 DAG.getConstant(Log2_64(N1C->getValue()), 456 TLI.getShiftAmountTy())); 457 // fold (mul (mul x, c1), c2) -> (mul x, c1*c2) 458 if (N1C && N0.getOpcode() == ISD::MUL) { 459 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 460 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 461 if (N00C) 462 return DAG.getNode(ISD::MUL, VT, N0.getOperand(1), 463 DAG.getConstant(N1C->getValue()*N00C->getValue(), VT)); 464 if (N01C) 465 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), 466 DAG.getConstant(N1C->getValue()*N01C->getValue(), VT)); 467 } 468 // fold floating point (mul c1, c2) -> c1*c2 469 if (N0CFP && N1CFP) 470 return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(), 471 N->getValueType(0)); 472 return SDOperand(); 473} 474 475SDOperand DAGCombiner::visitSDIV(SDNode *N) { 476 SDOperand N0 = N->getOperand(0); 477 SDOperand N1 = N->getOperand(1); 478 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 479 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 480 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0.Val); 481 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 482 483 // fold (sdiv c1, c2) -> c1/c2 484 if (N0C && N1C && !N1C->isNullValue()) 485 return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(), 486 N->getValueType(0)); 487 // fold floating point (sdiv c1, c2) -> c1/c2 488 if (N0CFP && N1CFP) 489 return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(), 490 N->getValueType(0)); 491 return SDOperand(); 492} 493 494SDOperand DAGCombiner::visitUDIV(SDNode *N) { 495 SDOperand N0 = N->getOperand(0); 496 SDOperand N1 = N->getOperand(1); 497 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 498 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 499 500 // fold (udiv c1, c2) -> c1/c2 501 if (N0C && N1C && !N1C->isNullValue()) 502 return DAG.getConstant(N0C->getValue() / N1C->getValue(), 503 N->getValueType(0)); 504 // fold (udiv x, (1 << c)) -> x >>u c 505 if (N1C && isPowerOf2_64(N1C->getValue())) 506 return DAG.getNode(ISD::SRL, N->getValueType(0), N0, 507 DAG.getConstant(Log2_64(N1C->getValue()), 508 TLI.getShiftAmountTy())); 509 return SDOperand(); 510} 511 512SDOperand DAGCombiner::visitSREM(SDNode *N) { 513 SDOperand N0 = N->getOperand(0); 514 SDOperand N1 = N->getOperand(1); 515 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 516 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 517 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 518 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 519 520 // fold (srem c1, c2) -> c1%c2 521 if (N0C && N1C && !N1C->isNullValue()) 522 return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(), 523 N->getValueType(0)); 524 // fold floating point (srem c1, c2) -> fmod(c1, c2) 525 if (N0CFP && N1CFP) 526 return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()), 527 N->getValueType(0)); 528 return SDOperand(); 529} 530 531SDOperand DAGCombiner::visitUREM(SDNode *N) { 532 SDOperand N0 = N->getOperand(0); 533 SDOperand N1 = N->getOperand(1); 534 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 535 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 536 537 // fold (urem c1, c2) -> c1%c2 538 if (N0C && N1C && !N1C->isNullValue()) 539 return DAG.getConstant(N0C->getValue() % N1C->getValue(), 540 N->getValueType(0)); 541 // FIXME: c2 power of 2 -> mask? 542 return SDOperand(); 543} 544 545SDOperand DAGCombiner::visitMULHS(SDNode *N) { 546 SDOperand N0 = N->getOperand(0); 547 SDOperand N1 = N->getOperand(1); 548 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 549 550 // fold (mulhs x, 0) -> 0 551 if (N1C && N1C->isNullValue()) 552 return N1; 553 // fold (mulhs x, 1) -> (sra x, size(x)-1) 554 if (N1C && N1C->getValue() == 1) 555 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 556 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 557 TLI.getShiftAmountTy())); 558 return SDOperand(); 559} 560 561SDOperand DAGCombiner::visitMULHU(SDNode *N) { 562 SDOperand N0 = N->getOperand(0); 563 SDOperand N1 = N->getOperand(1); 564 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 565 566 // fold (mulhu x, 0) -> 0 567 if (N1C && N1C->isNullValue()) 568 return N1; 569 // fold (mulhu x, 1) -> 0 570 if (N1C && N1C->getValue() == 1) 571 return DAG.getConstant(0, N0.getValueType()); 572 return SDOperand(); 573} 574 575SDOperand DAGCombiner::visitAND(SDNode *N) { 576 SDOperand N0 = N->getOperand(0); 577 SDOperand N1 = N->getOperand(1); 578 SDOperand LL, LR, RL, RR, CC0, CC1; 579 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 580 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 581 MVT::ValueType VT = N1.getValueType(); 582 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 583 584 // fold (and c1, c2) -> c1&c2 585 if (N0C && N1C) 586 return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT); 587 // canonicalize constant to RHS 588 if (N0C && !N1C) { 589 std::swap(N0, N1); 590 std::swap(N0C, N1C); 591 } 592 // fold (and x, -1) -> x 593 if (N1C && N1C->isAllOnesValue()) 594 return N0; 595 // if (and x, c) is known to be zero, return 0 596 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 597 return DAG.getConstant(0, VT); 598 // fold (and x, c) -> x iff (x & ~c) == 0 599 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 600 TLI)) 601 return N0; 602 // fold (and (and x, c1), c2) -> (and x, c1^c2) 603 if (N1C && N0.getOpcode() == ISD::AND) { 604 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 605 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 606 if (N00C) 607 return DAG.getNode(ISD::AND, VT, N0.getOperand(1), 608 DAG.getConstant(N1C->getValue()&N00C->getValue(), VT)); 609 if (N01C) 610 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 611 DAG.getConstant(N1C->getValue()&N01C->getValue(), VT)); 612 } 613 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 614 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) { 615 unsigned ExtendBits = 616 MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT()); 617 if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0) 618 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1); 619 } 620 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 621 if (N0.getOpcode() == ISD::OR) 622 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 623 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 624 return N1; 625 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 626 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 627 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 628 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 629 630 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 631 MVT::isInteger(LL.getValueType())) { 632 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 633 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 634 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 635 WorkList.push_back(ORNode.Val); 636 return DAG.getSetCC(VT, ORNode, LR, Op1); 637 } 638 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 639 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 640 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 641 WorkList.push_back(ANDNode.Val); 642 return DAG.getSetCC(VT, ANDNode, LR, Op1); 643 } 644 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 645 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 646 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 647 WorkList.push_back(ORNode.Val); 648 return DAG.getSetCC(VT, ORNode, LR, Op1); 649 } 650 } 651 // canonicalize equivalent to ll == rl 652 if (LL == RR && LR == RL) { 653 Op1 = ISD::getSetCCSwappedOperands(Op1); 654 std::swap(RL, RR); 655 } 656 if (LL == RL && LR == RR) { 657 bool isInteger = MVT::isInteger(LL.getValueType()); 658 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 659 if (Result != ISD::SETCC_INVALID) 660 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 661 } 662 } 663 // fold (and (zext x), (zext y)) -> (zext (and x, y)) 664 if (N0.getOpcode() == ISD::ZERO_EXTEND && 665 N1.getOpcode() == ISD::ZERO_EXTEND && 666 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 667 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 668 N0.getOperand(0), N1.getOperand(0)); 669 WorkList.push_back(ANDNode.Val); 670 return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode); 671 } 672 return SDOperand(); 673} 674 675SDOperand DAGCombiner::visitOR(SDNode *N) { 676 SDOperand N0 = N->getOperand(0); 677 SDOperand N1 = N->getOperand(1); 678 SDOperand LL, LR, RL, RR, CC0, CC1; 679 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 680 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 681 MVT::ValueType VT = N1.getValueType(); 682 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 683 684 // fold (or c1, c2) -> c1|c2 685 if (N0C && N1C) 686 return DAG.getConstant(N0C->getValue() | N1C->getValue(), 687 N->getValueType(0)); 688 // canonicalize constant to RHS 689 if (N0C && !N1C) { 690 std::swap(N0, N1); 691 std::swap(N0C, N1C); 692 } 693 // fold (or x, 0) -> x 694 if (N1C && N1C->isNullValue()) 695 return N0; 696 // fold (or x, -1) -> -1 697 if (N1C && N1C->isAllOnesValue()) 698 return N1; 699 // fold (or x, c) -> c iff (x & ~c) == 0 700 if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)), 701 TLI)) 702 return N1; 703 // fold (or (or x, c1), c2) -> (or x, c1|c2) 704 if (N1C && N0.getOpcode() == ISD::OR) { 705 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 706 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 707 if (N00C) 708 return DAG.getNode(ISD::OR, VT, N0.getOperand(1), 709 DAG.getConstant(N1C->getValue()|N00C->getValue(), VT)); 710 if (N01C) 711 return DAG.getNode(ISD::OR, VT, N0.getOperand(0), 712 DAG.getConstant(N1C->getValue()|N01C->getValue(), VT)); 713 } 714 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 715 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 716 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 717 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 718 719 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 720 MVT::isInteger(LL.getValueType())) { 721 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 722 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 723 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 724 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 725 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 726 WorkList.push_back(ORNode.Val); 727 return DAG.getSetCC(VT, ORNode, LR, Op1); 728 } 729 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 730 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 731 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 732 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 733 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 734 WorkList.push_back(ANDNode.Val); 735 return DAG.getSetCC(VT, ANDNode, LR, Op1); 736 } 737 } 738 // canonicalize equivalent to ll == rl 739 if (LL == RR && LR == RL) { 740 Op1 = ISD::getSetCCSwappedOperands(Op1); 741 std::swap(RL, RR); 742 } 743 if (LL == RL && LR == RR) { 744 bool isInteger = MVT::isInteger(LL.getValueType()); 745 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 746 if (Result != ISD::SETCC_INVALID) 747 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 748 } 749 } 750 // fold (or (zext x), (zext y)) -> (zext (or x, y)) 751 if (N0.getOpcode() == ISD::ZERO_EXTEND && 752 N1.getOpcode() == ISD::ZERO_EXTEND && 753 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 754 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(), 755 N0.getOperand(0), N1.getOperand(0)); 756 WorkList.push_back(ORNode.Val); 757 return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode); 758 } 759 return SDOperand(); 760} 761 762SDOperand DAGCombiner::visitXOR(SDNode *N) { 763 SDOperand N0 = N->getOperand(0); 764 SDOperand N1 = N->getOperand(1); 765 SDOperand LHS, RHS, CC; 766 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 767 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 768 MVT::ValueType VT = N0.getValueType(); 769 770 // fold (xor c1, c2) -> c1^c2 771 if (N0C && N1C) 772 return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT); 773 // canonicalize constant to RHS 774 if (N0C && !N1C) { 775 std::swap(N0, N1); 776 std::swap(N0C, N1C); 777 } 778 // fold (xor x, 0) -> x 779 if (N1C && N1C->isNullValue()) 780 return N0; 781 // fold !(x cc y) -> (x !cc y) 782 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 783 bool isInt = MVT::isInteger(LHS.getValueType()); 784 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 785 isInt); 786 if (N0.getOpcode() == ISD::SETCC) 787 return DAG.getSetCC(VT, LHS, RHS, NotCC); 788 if (N0.getOpcode() == ISD::SELECT_CC) 789 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 790 assert(0 && "Unhandled SetCC Equivalent!"); 791 abort(); 792 } 793 // fold !(x or y) -> (!x and !y) iff x or y are setcc 794 if (N1C && N1C->getValue() == 1 && 795 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 796 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 797 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 798 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 799 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 800 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 801 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 802 return DAG.getNode(NewOpcode, VT, LHS, RHS); 803 } 804 } 805 // fold !(x or y) -> (!x and !y) iff x or y are constants 806 if (N1C && N1C->isAllOnesValue() && 807 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 808 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 809 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 810 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 811 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 812 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 813 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 814 return DAG.getNode(NewOpcode, VT, LHS, RHS); 815 } 816 } 817 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 818 if (N1C && N0.getOpcode() == ISD::XOR) { 819 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 820 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 821 if (N00C) 822 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 823 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 824 if (N01C) 825 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 826 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 827 } 828 // fold (xor x, x) -> 0 829 if (N0 == N1) 830 return DAG.getConstant(0, VT); 831 // fold (xor (zext x), (zext y)) -> (zext (xor x, y)) 832 if (N0.getOpcode() == ISD::ZERO_EXTEND && 833 N1.getOpcode() == ISD::ZERO_EXTEND && 834 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 835 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(), 836 N0.getOperand(0), N1.getOperand(0)); 837 WorkList.push_back(XORNode.Val); 838 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode); 839 } 840 return SDOperand(); 841} 842 843SDOperand DAGCombiner::visitSHL(SDNode *N) { 844 SDOperand N0 = N->getOperand(0); 845 SDOperand N1 = N->getOperand(1); 846 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 847 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 848 MVT::ValueType VT = N0.getValueType(); 849 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 850 851 // fold (shl c1, c2) -> c1<<c2 852 if (N0C && N1C) 853 return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT); 854 // fold (shl 0, x) -> 0 855 if (N0C && N0C->isNullValue()) 856 return N0; 857 // fold (shl x, c >= size(x)) -> undef 858 if (N1C && N1C->getValue() >= OpSizeInBits) 859 return DAG.getNode(ISD::UNDEF, VT); 860 // fold (shl x, 0) -> x 861 if (N1C && N1C->isNullValue()) 862 return N0; 863 // if (shl x, c) is known to be zero, return 0 864 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 865 return DAG.getConstant(0, VT); 866 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 867 if (N1C && N0.getOpcode() == ISD::SHL && 868 N0.getOperand(1).getOpcode() == ISD::Constant) { 869 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 870 uint64_t c2 = N1C->getValue(); 871 if (c1 + c2 > OpSizeInBits) 872 return DAG.getConstant(0, VT); 873 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 874 DAG.getConstant(c1 + c2, N1.getValueType())); 875 } 876 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 877 // (srl (and x, -1 << c1), c1-c2) 878 if (N1C && N0.getOpcode() == ISD::SRL && 879 N0.getOperand(1).getOpcode() == ISD::Constant) { 880 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 881 uint64_t c2 = N1C->getValue(); 882 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 883 DAG.getConstant(~0ULL << c1, VT)); 884 if (c2 > c1) 885 return DAG.getNode(ISD::SHL, VT, Mask, 886 DAG.getConstant(c2-c1, N1.getValueType())); 887 else 888 return DAG.getNode(ISD::SRL, VT, Mask, 889 DAG.getConstant(c1-c2, N1.getValueType())); 890 } 891 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 892 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 893 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 894 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 895 return SDOperand(); 896} 897 898SDOperand DAGCombiner::visitSRA(SDNode *N) { 899 SDOperand N0 = N->getOperand(0); 900 SDOperand N1 = N->getOperand(1); 901 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 902 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 903 MVT::ValueType VT = N0.getValueType(); 904 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 905 906 // fold (sra c1, c2) -> c1>>c2 907 if (N0C && N1C) 908 return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT); 909 // fold (sra 0, x) -> 0 910 if (N0C && N0C->isNullValue()) 911 return N0; 912 // fold (sra -1, x) -> -1 913 if (N0C && N0C->isAllOnesValue()) 914 return N0; 915 // fold (sra x, c >= size(x)) -> undef 916 if (N1C && N1C->getValue() >= OpSizeInBits) 917 return DAG.getNode(ISD::UNDEF, VT); 918 // fold (sra x, 0) -> x 919 if (N1C && N1C->isNullValue()) 920 return N0; 921 // If the sign bit is known to be zero, switch this to a SRL. 922 if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI)) 923 return DAG.getNode(ISD::SRL, VT, N0, N1); 924 return SDOperand(); 925} 926 927SDOperand DAGCombiner::visitSRL(SDNode *N) { 928 SDOperand N0 = N->getOperand(0); 929 SDOperand N1 = N->getOperand(1); 930 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 931 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 932 MVT::ValueType VT = N0.getValueType(); 933 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 934 935 // fold (srl c1, c2) -> c1 >>u c2 936 if (N0C && N1C) 937 return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT); 938 // fold (srl 0, x) -> 0 939 if (N0C && N0C->isNullValue()) 940 return N0; 941 // fold (srl x, c >= size(x)) -> undef 942 if (N1C && N1C->getValue() >= OpSizeInBits) 943 return DAG.getNode(ISD::UNDEF, VT); 944 // fold (srl x, 0) -> x 945 if (N1C && N1C->isNullValue()) 946 return N0; 947 // if (srl x, c) is known to be zero, return 0 948 if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI)) 949 return DAG.getConstant(0, VT); 950 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 951 if (N1C && N0.getOpcode() == ISD::SRL && 952 N0.getOperand(1).getOpcode() == ISD::Constant) { 953 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 954 uint64_t c2 = N1C->getValue(); 955 if (c1 + c2 > OpSizeInBits) 956 return DAG.getConstant(0, VT); 957 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 958 DAG.getConstant(c1 + c2, N1.getValueType())); 959 } 960 return SDOperand(); 961} 962 963SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 964 SDOperand N0 = N->getOperand(0); 965 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 966 967 // fold (ctlz c1) -> c2 968 if (N0C) 969 return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()), 970 N0.getValueType()); 971 return SDOperand(); 972} 973 974SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 975 SDOperand N0 = N->getOperand(0); 976 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 977 978 // fold (cttz c1) -> c2 979 if (N0C) 980 return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()), 981 N0.getValueType()); 982 return SDOperand(); 983} 984 985SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 986 SDOperand N0 = N->getOperand(0); 987 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 988 989 // fold (ctpop c1) -> c2 990 if (N0C) 991 return DAG.getConstant(CountPopulation_64(N0C->getValue()), 992 N0.getValueType()); 993 return SDOperand(); 994} 995 996SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 997 SDOperand N0 = N->getOperand(0); 998 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 999 MVT::ValueType VT = N->getValueType(0); 1000 1001 // fold (sext c1) -> c1 1002 if (N0C) 1003 return DAG.getConstant(N0C->getSignExtended(), VT); 1004 // fold (sext (sext x)) -> (sext x) 1005 if (N0.getOpcode() == ISD::SIGN_EXTEND) 1006 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1007 return SDOperand(); 1008} 1009 1010SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1011 SDOperand N0 = N->getOperand(0); 1012 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1013 MVT::ValueType VT = N->getValueType(0); 1014 1015 // fold (zext c1) -> c1 1016 if (N0C) 1017 return DAG.getConstant(N0C->getValue(), VT); 1018 // fold (zext (zext x)) -> (zext x) 1019 if (N0.getOpcode() == ISD::ZERO_EXTEND) 1020 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1021 return SDOperand(); 1022} 1023 1024SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 1025 SDOperand N0 = N->getOperand(0); 1026 SDOperand N1 = N->getOperand(1); 1027 SDOperand LHS, RHS, CC; 1028 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1029 MVT::ValueType VT = N->getValueType(0); 1030 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 1031 1032 // fold (sext_in_reg c1) -> c1 1033 if (N0C) { 1034 SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT); 1035 return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate); 1036 } 1037 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1 1038 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1039 cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) { 1040 return N0; 1041 } 1042 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 1043 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1044 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 1045 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 1046 } 1047 // fold (sext_in_reg (assert_sext x)) -> (assert_sext x) 1048 if (N0.getOpcode() == ISD::AssertSext && 1049 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) { 1050 return N0; 1051 } 1052 // fold (sext_in_reg (sextload x)) -> (sextload x) 1053 if (N0.getOpcode() == ISD::SEXTLOAD && 1054 cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) { 1055 return N0; 1056 } 1057 // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1 1058 // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here 1059 if (N0.getOpcode() == ISD::SETCC && 1060 TLI.getSetCCResultContents() == 1061 TargetLowering::ZeroOrNegativeOneSetCCResult) 1062 return N0; 1063 // FIXME: this code is currently just ported over from SelectionDAG.cpp 1064 // we probably actually want to handle this in two pieces. Rather than 1065 // checking all the top bits for zero, just check the sign bit here and turn 1066 // it into a zero extend inreg (AND with constant). 1067 // then, let the code for AND figure out if the mask is superfluous rather 1068 // than doing so here. 1069 if (N0.getOpcode() == ISD::AND && 1070 N0.getOperand(1).getOpcode() == ISD::Constant) { 1071 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1072 unsigned NumBits = MVT::getSizeInBits(EVT); 1073 if ((Mask & (~0ULL << (NumBits-1))) == 0) 1074 return N0; 1075 } 1076 return SDOperand(); 1077} 1078 1079SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 1080 SDOperand N0 = N->getOperand(0); 1081 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1082 MVT::ValueType VT = N->getValueType(0); 1083 1084 // noop truncate 1085 if (N0.getValueType() == N->getValueType(0)) 1086 return N0; 1087 // fold (truncate c1) -> c1 1088 if (N0C) 1089 return DAG.getConstant(N0C->getValue(), VT); 1090 // fold (truncate (truncate x)) -> (truncate x) 1091 if (N0.getOpcode() == ISD::TRUNCATE) 1092 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1093 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 1094 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){ 1095 if (N0.getValueType() < VT) 1096 // if the source is smaller than the dest, we still need an extend 1097 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1098 else if (N0.getValueType() > VT) 1099 // if the source is larger than the dest, than we just need the truncate 1100 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1101 else 1102 // if the source and dest are the same type, we can drop both the extend 1103 // and the truncate 1104 return N0.getOperand(0); 1105 } 1106 return SDOperand(); 1107} 1108 1109SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 1110 SDOperand N0 = N->getOperand(0); 1111 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1112 1113 // fold (sint_to_fp c1) -> c1fp 1114 if (N0C) 1115 return DAG.getConstantFP(N0C->getSignExtended(), N->getValueType(0)); 1116 return SDOperand(); 1117} 1118 1119SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 1120 SDOperand N0 = N->getOperand(0); 1121 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1122 1123 // fold (uint_to_fp c1) -> c1fp 1124 if (N0C) 1125 return DAG.getConstantFP(N0C->getValue(), N->getValueType(0)); 1126 return SDOperand(); 1127} 1128 1129SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 1130 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1131 1132 // fold (fp_to_sint c1fp) -> c1 1133 if (N0CFP) 1134 return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0)); 1135 return SDOperand(); 1136} 1137 1138SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 1139 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1140 1141 // fold (fp_to_uint c1fp) -> c1 1142 if (N0CFP) 1143 return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0)); 1144 return SDOperand(); 1145} 1146 1147SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 1148 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1149 1150 // fold (fp_round c1fp) -> c1fp 1151 if (N0CFP) 1152 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1153 return SDOperand(); 1154} 1155 1156SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 1157 SDOperand N0 = N->getOperand(0); 1158 MVT::ValueType VT = N->getValueType(0); 1159 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 1160 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1161 1162 // fold (fp_round_inreg c1fp) -> c1fp 1163 if (N0CFP) { 1164 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 1165 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 1166 } 1167 return SDOperand(); 1168} 1169 1170SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 1171 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1172 1173 // fold (fp_extend c1fp) -> c1fp 1174 if (N0CFP) 1175 return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)); 1176 return SDOperand(); 1177} 1178 1179SDOperand DAGCombiner::visitFNEG(SDNode *N) { 1180 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1181 // fold (neg c1) -> -c1 1182 if (N0CFP) 1183 return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0)); 1184 // fold (neg (sub x, y)) -> (sub y, x) 1185 if (N->getOperand(0).getOpcode() == ISD::SUB) 1186 return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1), 1187 N->getOperand(0)); 1188 // fold (neg (neg x)) -> x 1189 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1190 return N->getOperand(0).getOperand(0); 1191 return SDOperand(); 1192} 1193 1194SDOperand DAGCombiner::visitFABS(SDNode *N) { 1195 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0)); 1196 // fold (fabs c1) -> fabs(c1) 1197 if (N0CFP) 1198 return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0)); 1199 // fold (fabs (fabs x)) -> (fabs x) 1200 if (N->getOperand(0).getOpcode() == ISD::FABS) 1201 return N->getOperand(0); 1202 // fold (fabs (fneg x)) -> (fabs x) 1203 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1204 return DAG.getNode(ISD::FABS, N->getValueType(0), 1205 N->getOperand(0).getOperand(0)); 1206 return SDOperand(); 1207} 1208 1209// SelectionDAG::Combine - This is the entry point for the file. 1210// 1211void SelectionDAG::Combine(bool RunningAfterLegalize) { 1212 /// run - This is the main entry point to this class. 1213 /// 1214 DAGCombiner(*this).Run(RunningAfterLegalize); 1215} 1216