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