DAGCombiner.cpp revision 3577e38c2b34c7978b8a1b6047eed3e421559d28
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: select C, pow2, pow2 -> something smart 20// FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z) 21// FIXME: Dead stores -> nuke 22// FIXME: shr X, (and Y,31) -> shr X, Y (TRICKY!) 23// FIXME: mul (x, const) -> shifts + adds 24// FIXME: undef values 25// FIXME: make truncate see through SIGN_EXTEND and AND 26// FIXME: divide by zero is currently left unfolded. do we want to turn this 27// into an undef? 28// FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false 29// 30//===----------------------------------------------------------------------===// 31 32#define DEBUG_TYPE "dagcombine" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/CodeGen/SelectionDAG.h" 35#include "llvm/Support/Debug.h" 36#include "llvm/Support/MathExtras.h" 37#include "llvm/Target/TargetLowering.h" 38#include "llvm/Support/Visibility.h" 39#include <algorithm> 40#include <cmath> 41#include <iostream> 42using namespace llvm; 43 44namespace { 45 static Statistic<> NodesCombined ("dagcombiner", 46 "Number of dag nodes combined"); 47 48 class VISIBILITY_HIDDEN DAGCombiner { 49 SelectionDAG &DAG; 50 TargetLowering &TLI; 51 bool AfterLegalize; 52 53 // Worklist of all of the nodes that need to be simplified. 54 std::vector<SDNode*> WorkList; 55 56 /// AddUsersToWorkList - When an instruction is simplified, add all users of 57 /// the instruction to the work lists because they might get more simplified 58 /// now. 59 /// 60 void AddUsersToWorkList(SDNode *N) { 61 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 62 UI != UE; ++UI) 63 WorkList.push_back(*UI); 64 } 65 66 /// removeFromWorkList - remove all instances of N from the worklist. 67 /// 68 void removeFromWorkList(SDNode *N) { 69 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 70 WorkList.end()); 71 } 72 73 public: 74 void AddToWorkList(SDNode *N) { 75 WorkList.push_back(N); 76 } 77 78 SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo) { 79 assert(N->getNumValues() == NumTo && "Broken CombineTo call!"); 80 ++NodesCombined; 81 DEBUG(std::cerr << "\nReplacing "; N->dump(); 82 std::cerr << "\nWith: "; To[0].Val->dump(&DAG); 83 std::cerr << " and " << NumTo-1 << " other values\n"); 84 std::vector<SDNode*> NowDead; 85 DAG.ReplaceAllUsesWith(N, To, &NowDead); 86 87 // Push the new nodes and any users onto the worklist 88 for (unsigned i = 0, e = NumTo; i != e; ++i) { 89 WorkList.push_back(To[i].Val); 90 AddUsersToWorkList(To[i].Val); 91 } 92 93 // Nodes can end up on the worklist more than once. Make sure we do 94 // not process a node that has been replaced. 95 removeFromWorkList(N); 96 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 97 removeFromWorkList(NowDead[i]); 98 99 // Finally, since the node is now dead, remove it from the graph. 100 DAG.DeleteNode(N); 101 return SDOperand(N, 0); 102 } 103 104 SDOperand CombineTo(SDNode *N, SDOperand Res) { 105 return CombineTo(N, &Res, 1); 106 } 107 108 SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 109 SDOperand To[] = { Res0, Res1 }; 110 return CombineTo(N, To, 2); 111 } 112 private: 113 114 /// SimplifyDemandedBits - Check the specified integer node value to see if 115 /// it can be simplified or if things it uses can be simplified by bit 116 /// propagation. If so, return true. 117 bool SimplifyDemandedBits(SDOperand Op) { 118 TargetLowering::TargetLoweringOpt TLO(DAG); 119 uint64_t KnownZero, KnownOne; 120 uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType()); 121 if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO)) 122 return false; 123 124 // Revisit the node. 125 WorkList.push_back(Op.Val); 126 127 // Replace the old value with the new one. 128 ++NodesCombined; 129 DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump(); 130 std::cerr << "\nWith: "; TLO.New.Val->dump(&DAG)); 131 132 std::vector<SDNode*> NowDead; 133 DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead); 134 135 // Push the new node and any (possibly new) users onto the worklist. 136 WorkList.push_back(TLO.New.Val); 137 AddUsersToWorkList(TLO.New.Val); 138 139 // Nodes can end up on the worklist more than once. Make sure we do 140 // not process a node that has been replaced. 141 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 142 removeFromWorkList(NowDead[i]); 143 144 // Finally, if the node is now dead, remove it from the graph. The node 145 // may not be dead if the replacement process recursively simplified to 146 // something else needing this node. 147 if (TLO.Old.Val->use_empty()) { 148 removeFromWorkList(TLO.Old.Val); 149 DAG.DeleteNode(TLO.Old.Val); 150 } 151 return true; 152 } 153 154 /// visit - call the node-specific routine that knows how to fold each 155 /// particular type of node. 156 SDOperand visit(SDNode *N); 157 158 // Visitation implementation - Implement dag node combining for different 159 // node types. The semantics are as follows: 160 // Return Value: 161 // SDOperand.Val == 0 - No change was made 162 // SDOperand.Val == N - N was replaced, is dead, and is already handled. 163 // otherwise - N should be replaced by the returned Operand. 164 // 165 SDOperand visitTokenFactor(SDNode *N); 166 SDOperand visitADD(SDNode *N); 167 SDOperand visitSUB(SDNode *N); 168 SDOperand visitMUL(SDNode *N); 169 SDOperand visitSDIV(SDNode *N); 170 SDOperand visitUDIV(SDNode *N); 171 SDOperand visitSREM(SDNode *N); 172 SDOperand visitUREM(SDNode *N); 173 SDOperand visitMULHU(SDNode *N); 174 SDOperand visitMULHS(SDNode *N); 175 SDOperand visitAND(SDNode *N); 176 SDOperand visitOR(SDNode *N); 177 SDOperand visitXOR(SDNode *N); 178 SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp); 179 SDOperand visitSHL(SDNode *N); 180 SDOperand visitSRA(SDNode *N); 181 SDOperand visitSRL(SDNode *N); 182 SDOperand visitCTLZ(SDNode *N); 183 SDOperand visitCTTZ(SDNode *N); 184 SDOperand visitCTPOP(SDNode *N); 185 SDOperand visitSELECT(SDNode *N); 186 SDOperand visitSELECT_CC(SDNode *N); 187 SDOperand visitSETCC(SDNode *N); 188 SDOperand visitSIGN_EXTEND(SDNode *N); 189 SDOperand visitZERO_EXTEND(SDNode *N); 190 SDOperand visitANY_EXTEND(SDNode *N); 191 SDOperand visitSIGN_EXTEND_INREG(SDNode *N); 192 SDOperand visitTRUNCATE(SDNode *N); 193 SDOperand visitBIT_CONVERT(SDNode *N); 194 SDOperand visitVBIT_CONVERT(SDNode *N); 195 SDOperand visitFADD(SDNode *N); 196 SDOperand visitFSUB(SDNode *N); 197 SDOperand visitFMUL(SDNode *N); 198 SDOperand visitFDIV(SDNode *N); 199 SDOperand visitFREM(SDNode *N); 200 SDOperand visitFCOPYSIGN(SDNode *N); 201 SDOperand visitSINT_TO_FP(SDNode *N); 202 SDOperand visitUINT_TO_FP(SDNode *N); 203 SDOperand visitFP_TO_SINT(SDNode *N); 204 SDOperand visitFP_TO_UINT(SDNode *N); 205 SDOperand visitFP_ROUND(SDNode *N); 206 SDOperand visitFP_ROUND_INREG(SDNode *N); 207 SDOperand visitFP_EXTEND(SDNode *N); 208 SDOperand visitFNEG(SDNode *N); 209 SDOperand visitFABS(SDNode *N); 210 SDOperand visitBRCOND(SDNode *N); 211 SDOperand visitBR_CC(SDNode *N); 212 SDOperand visitLOAD(SDNode *N); 213 SDOperand visitXEXTLOAD(SDNode *N); 214 SDOperand visitSTORE(SDNode *N); 215 SDOperand visitINSERT_VECTOR_ELT(SDNode *N); 216 SDOperand visitVINSERT_VECTOR_ELT(SDNode *N); 217 SDOperand visitVBUILD_VECTOR(SDNode *N); 218 SDOperand visitVECTOR_SHUFFLE(SDNode *N); 219 SDOperand visitVVECTOR_SHUFFLE(SDNode *N); 220 221 SDOperand XformToShuffleWithZero(SDNode *N); 222 SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS); 223 224 bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS); 225 SDOperand SimplifyBinOpWithSameOpcodeHands(SDNode *N); 226 SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2); 227 SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2, 228 SDOperand N3, ISD::CondCode CC); 229 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 230 ISD::CondCode Cond, bool foldBooleans = true); 231 SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType); 232 SDOperand BuildSDIV(SDNode *N); 233 SDOperand BuildUDIV(SDNode *N); 234public: 235 DAGCombiner(SelectionDAG &D) 236 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {} 237 238 /// Run - runs the dag combiner on all nodes in the work list 239 void Run(bool RunningAfterLegalize); 240 }; 241} 242 243//===----------------------------------------------------------------------===// 244// TargetLowering::DAGCombinerInfo implementation 245//===----------------------------------------------------------------------===// 246 247void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) { 248 ((DAGCombiner*)DC)->AddToWorkList(N); 249} 250 251SDOperand TargetLowering::DAGCombinerInfo:: 252CombineTo(SDNode *N, const std::vector<SDOperand> &To) { 253 return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size()); 254} 255 256SDOperand TargetLowering::DAGCombinerInfo:: 257CombineTo(SDNode *N, SDOperand Res) { 258 return ((DAGCombiner*)DC)->CombineTo(N, Res); 259} 260 261 262SDOperand TargetLowering::DAGCombinerInfo:: 263CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 264 return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1); 265} 266 267 268 269 270//===----------------------------------------------------------------------===// 271 272 273// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 274// that selects between the values 1 and 0, making it equivalent to a setcc. 275// Also, set the incoming LHS, RHS, and CC references to the appropriate 276// nodes based on the type of node we are checking. This simplifies life a 277// bit for the callers. 278static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 279 SDOperand &CC) { 280 if (N.getOpcode() == ISD::SETCC) { 281 LHS = N.getOperand(0); 282 RHS = N.getOperand(1); 283 CC = N.getOperand(2); 284 return true; 285 } 286 if (N.getOpcode() == ISD::SELECT_CC && 287 N.getOperand(2).getOpcode() == ISD::Constant && 288 N.getOperand(3).getOpcode() == ISD::Constant && 289 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 290 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 291 LHS = N.getOperand(0); 292 RHS = N.getOperand(1); 293 CC = N.getOperand(4); 294 return true; 295 } 296 return false; 297} 298 299// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 300// one use. If this is true, it allows the users to invert the operation for 301// free when it is profitable to do so. 302static bool isOneUseSetCC(SDOperand N) { 303 SDOperand N0, N1, N2; 304 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 305 return true; 306 return false; 307} 308 309// FIXME: This should probably go in the ISD class rather than being duplicated 310// in several files. 311static bool isCommutativeBinOp(unsigned Opcode) { 312 switch (Opcode) { 313 case ISD::ADD: 314 case ISD::MUL: 315 case ISD::AND: 316 case ISD::OR: 317 case ISD::XOR: return true; 318 default: return false; // FIXME: Need commutative info for user ops! 319 } 320} 321 322SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){ 323 MVT::ValueType VT = N0.getValueType(); 324 // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use 325 // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2)) 326 if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) { 327 if (isa<ConstantSDNode>(N1)) { 328 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1); 329 AddToWorkList(OpNode.Val); 330 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0)); 331 } else if (N0.hasOneUse()) { 332 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1); 333 AddToWorkList(OpNode.Val); 334 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1)); 335 } 336 } 337 // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use 338 // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2)) 339 if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) { 340 if (isa<ConstantSDNode>(N0)) { 341 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0); 342 AddToWorkList(OpNode.Val); 343 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0)); 344 } else if (N1.hasOneUse()) { 345 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0); 346 AddToWorkList(OpNode.Val); 347 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1)); 348 } 349 } 350 return SDOperand(); 351} 352 353void DAGCombiner::Run(bool RunningAfterLegalize) { 354 // set the instance variable, so that the various visit routines may use it. 355 AfterLegalize = RunningAfterLegalize; 356 357 // Add all the dag nodes to the worklist. 358 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 359 E = DAG.allnodes_end(); I != E; ++I) 360 WorkList.push_back(I); 361 362 // Create a dummy node (which is not added to allnodes), that adds a reference 363 // to the root node, preventing it from being deleted, and tracking any 364 // changes of the root. 365 HandleSDNode Dummy(DAG.getRoot()); 366 367 368 /// DagCombineInfo - Expose the DAG combiner to the target combiner impls. 369 TargetLowering::DAGCombinerInfo 370 DagCombineInfo(DAG, !RunningAfterLegalize, this); 371 372 // while the worklist isn't empty, inspect the node on the end of it and 373 // try and combine it. 374 while (!WorkList.empty()) { 375 SDNode *N = WorkList.back(); 376 WorkList.pop_back(); 377 378 // If N has no uses, it is dead. Make sure to revisit all N's operands once 379 // N is deleted from the DAG, since they too may now be dead or may have a 380 // reduced number of uses, allowing other xforms. 381 if (N->use_empty() && N != &Dummy) { 382 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 383 WorkList.push_back(N->getOperand(i).Val); 384 385 removeFromWorkList(N); 386 DAG.DeleteNode(N); 387 continue; 388 } 389 390 SDOperand RV = visit(N); 391 392 // If nothing happened, try a target-specific DAG combine. 393 if (RV.Val == 0) { 394 assert(N->getOpcode() != ISD::DELETED_NODE && 395 "Node was deleted but visit returned NULL!"); 396 if (N->getOpcode() >= ISD::BUILTIN_OP_END || 397 TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) 398 RV = TLI.PerformDAGCombine(N, DagCombineInfo); 399 } 400 401 if (RV.Val) { 402 ++NodesCombined; 403 // If we get back the same node we passed in, rather than a new node or 404 // zero, we know that the node must have defined multiple values and 405 // CombineTo was used. Since CombineTo takes care of the worklist 406 // mechanics for us, we have no work to do in this case. 407 if (RV.Val != N) { 408 assert(N->getOpcode() != ISD::DELETED_NODE && 409 RV.Val->getOpcode() != ISD::DELETED_NODE && 410 "Node was deleted but visit returned new node!"); 411 412 DEBUG(std::cerr << "\nReplacing "; N->dump(); 413 std::cerr << "\nWith: "; RV.Val->dump(&DAG); 414 std::cerr << '\n'); 415 std::vector<SDNode*> NowDead; 416 SDOperand OpV = RV; 417 DAG.ReplaceAllUsesWith(N, &OpV, &NowDead); 418 419 // Push the new node and any users onto the worklist 420 WorkList.push_back(RV.Val); 421 AddUsersToWorkList(RV.Val); 422 423 // Nodes can end up on the worklist more than once. Make sure we do 424 // not process a node that has been replaced. 425 removeFromWorkList(N); 426 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 427 removeFromWorkList(NowDead[i]); 428 429 // Finally, since the node is now dead, remove it from the graph. 430 DAG.DeleteNode(N); 431 } 432 } 433 } 434 435 // If the root changed (e.g. it was a dead load, update the root). 436 DAG.setRoot(Dummy.getValue()); 437} 438 439SDOperand DAGCombiner::visit(SDNode *N) { 440 switch(N->getOpcode()) { 441 default: break; 442 case ISD::TokenFactor: return visitTokenFactor(N); 443 case ISD::ADD: return visitADD(N); 444 case ISD::SUB: return visitSUB(N); 445 case ISD::MUL: return visitMUL(N); 446 case ISD::SDIV: return visitSDIV(N); 447 case ISD::UDIV: return visitUDIV(N); 448 case ISD::SREM: return visitSREM(N); 449 case ISD::UREM: return visitUREM(N); 450 case ISD::MULHU: return visitMULHU(N); 451 case ISD::MULHS: return visitMULHS(N); 452 case ISD::AND: return visitAND(N); 453 case ISD::OR: return visitOR(N); 454 case ISD::XOR: return visitXOR(N); 455 case ISD::SHL: return visitSHL(N); 456 case ISD::SRA: return visitSRA(N); 457 case ISD::SRL: return visitSRL(N); 458 case ISD::CTLZ: return visitCTLZ(N); 459 case ISD::CTTZ: return visitCTTZ(N); 460 case ISD::CTPOP: return visitCTPOP(N); 461 case ISD::SELECT: return visitSELECT(N); 462 case ISD::SELECT_CC: return visitSELECT_CC(N); 463 case ISD::SETCC: return visitSETCC(N); 464 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 465 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 466 case ISD::ANY_EXTEND: return visitANY_EXTEND(N); 467 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 468 case ISD::TRUNCATE: return visitTRUNCATE(N); 469 case ISD::BIT_CONVERT: return visitBIT_CONVERT(N); 470 case ISD::VBIT_CONVERT: return visitVBIT_CONVERT(N); 471 case ISD::FADD: return visitFADD(N); 472 case ISD::FSUB: return visitFSUB(N); 473 case ISD::FMUL: return visitFMUL(N); 474 case ISD::FDIV: return visitFDIV(N); 475 case ISD::FREM: return visitFREM(N); 476 case ISD::FCOPYSIGN: return visitFCOPYSIGN(N); 477 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 478 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 479 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 480 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 481 case ISD::FP_ROUND: return visitFP_ROUND(N); 482 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 483 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 484 case ISD::FNEG: return visitFNEG(N); 485 case ISD::FABS: return visitFABS(N); 486 case ISD::BRCOND: return visitBRCOND(N); 487 case ISD::BR_CC: return visitBR_CC(N); 488 case ISD::LOAD: return visitLOAD(N); 489 case ISD::EXTLOAD: 490 case ISD::SEXTLOAD: 491 case ISD::ZEXTLOAD: return visitXEXTLOAD(N); 492 case ISD::STORE: return visitSTORE(N); 493 case ISD::INSERT_VECTOR_ELT: return visitINSERT_VECTOR_ELT(N); 494 case ISD::VINSERT_VECTOR_ELT: return visitVINSERT_VECTOR_ELT(N); 495 case ISD::VBUILD_VECTOR: return visitVBUILD_VECTOR(N); 496 case ISD::VECTOR_SHUFFLE: return visitVECTOR_SHUFFLE(N); 497 case ISD::VVECTOR_SHUFFLE: return visitVVECTOR_SHUFFLE(N); 498 case ISD::VADD: return visitVBinOp(N, ISD::ADD , ISD::FADD); 499 case ISD::VSUB: return visitVBinOp(N, ISD::SUB , ISD::FSUB); 500 case ISD::VMUL: return visitVBinOp(N, ISD::MUL , ISD::FMUL); 501 case ISD::VSDIV: return visitVBinOp(N, ISD::SDIV, ISD::FDIV); 502 case ISD::VUDIV: return visitVBinOp(N, ISD::UDIV, ISD::UDIV); 503 case ISD::VAND: return visitVBinOp(N, ISD::AND , ISD::AND); 504 case ISD::VOR: return visitVBinOp(N, ISD::OR , ISD::OR); 505 case ISD::VXOR: return visitVBinOp(N, ISD::XOR , ISD::XOR); 506 } 507 return SDOperand(); 508} 509 510SDOperand DAGCombiner::visitTokenFactor(SDNode *N) { 511 SmallVector<SDOperand, 8> Ops; 512 bool Changed = false; 513 514 // If the token factor has two operands and one is the entry token, replace 515 // the token factor with the other operand. 516 if (N->getNumOperands() == 2) { 517 if (N->getOperand(0).getOpcode() == ISD::EntryToken || 518 N->getOperand(0) == N->getOperand(1)) 519 return N->getOperand(1); 520 if (N->getOperand(1).getOpcode() == ISD::EntryToken) 521 return N->getOperand(0); 522 } 523 524 // fold (tokenfactor (tokenfactor)) -> tokenfactor 525 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 526 SDOperand Op = N->getOperand(i); 527 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { 528 AddToWorkList(Op.Val); // Remove dead node. 529 Changed = true; 530 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) 531 Ops.push_back(Op.getOperand(j)); 532 } else if (i == 0 || N->getOperand(i) != N->getOperand(i-1)) { 533 Ops.push_back(Op); 534 } else { 535 // Deleted an operand that was the same as the last one. 536 Changed = true; 537 } 538 } 539 if (Changed) 540 return DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size()); 541 return SDOperand(); 542} 543 544SDOperand DAGCombiner::visitADD(SDNode *N) { 545 SDOperand N0 = N->getOperand(0); 546 SDOperand N1 = N->getOperand(1); 547 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 548 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 549 MVT::ValueType VT = N0.getValueType(); 550 551 // fold (add c1, c2) -> c1+c2 552 if (N0C && N1C) 553 return DAG.getNode(ISD::ADD, VT, N0, N1); 554 // canonicalize constant to RHS 555 if (N0C && !N1C) 556 return DAG.getNode(ISD::ADD, VT, N1, N0); 557 // fold (add x, 0) -> x 558 if (N1C && N1C->isNullValue()) 559 return N0; 560 // fold ((c1-A)+c2) -> (c1+c2)-A 561 if (N1C && N0.getOpcode() == ISD::SUB) 562 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0))) 563 return DAG.getNode(ISD::SUB, VT, 564 DAG.getConstant(N1C->getValue()+N0C->getValue(), VT), 565 N0.getOperand(1)); 566 // reassociate add 567 SDOperand RADD = ReassociateOps(ISD::ADD, N0, N1); 568 if (RADD.Val != 0) 569 return RADD; 570 // fold ((0-A) + B) -> B-A 571 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 572 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 573 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 574 // fold (A + (0-B)) -> A-B 575 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 576 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 577 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 578 // fold (A+(B-A)) -> B 579 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1)) 580 return N1.getOperand(0); 581 582 if (!MVT::isVector(VT) && SimplifyDemandedBits(SDOperand(N, 0))) 583 return SDOperand(N, 0); 584 585 // fold (a+b) -> (a|b) iff a and b share no bits. 586 if (MVT::isInteger(VT) && !MVT::isVector(VT)) { 587 uint64_t LHSZero, LHSOne; 588 uint64_t RHSZero, RHSOne; 589 uint64_t Mask = MVT::getIntVTBitMask(VT); 590 TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); 591 if (LHSZero) { 592 TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); 593 594 // If all possibly-set bits on the LHS are clear on the RHS, return an OR. 595 // If all possibly-set bits on the RHS are clear on the LHS, return an OR. 596 if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) || 597 (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask)) 598 return DAG.getNode(ISD::OR, VT, N0, N1); 599 } 600 } 601 602 return SDOperand(); 603} 604 605SDOperand DAGCombiner::visitSUB(SDNode *N) { 606 SDOperand N0 = N->getOperand(0); 607 SDOperand N1 = N->getOperand(1); 608 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 609 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 610 MVT::ValueType VT = N0.getValueType(); 611 612 // fold (sub x, x) -> 0 613 if (N0 == N1) 614 return DAG.getConstant(0, N->getValueType(0)); 615 // fold (sub c1, c2) -> c1-c2 616 if (N0C && N1C) 617 return DAG.getNode(ISD::SUB, VT, N0, N1); 618 // fold (sub x, c) -> (add x, -c) 619 if (N1C) 620 return DAG.getNode(ISD::ADD, VT, N0, DAG.getConstant(-N1C->getValue(), VT)); 621 // fold (A+B)-A -> B 622 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1) 623 return N0.getOperand(1); 624 // fold (A+B)-B -> A 625 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1) 626 return N0.getOperand(0); 627 return SDOperand(); 628} 629 630SDOperand DAGCombiner::visitMUL(SDNode *N) { 631 SDOperand N0 = N->getOperand(0); 632 SDOperand N1 = N->getOperand(1); 633 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 634 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 635 MVT::ValueType VT = N0.getValueType(); 636 637 // fold (mul c1, c2) -> c1*c2 638 if (N0C && N1C) 639 return DAG.getNode(ISD::MUL, VT, N0, N1); 640 // canonicalize constant to RHS 641 if (N0C && !N1C) 642 return DAG.getNode(ISD::MUL, VT, N1, N0); 643 // fold (mul x, 0) -> 0 644 if (N1C && N1C->isNullValue()) 645 return N1; 646 // fold (mul x, -1) -> 0-x 647 if (N1C && N1C->isAllOnesValue()) 648 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 649 // fold (mul x, (1 << c)) -> x << c 650 if (N1C && isPowerOf2_64(N1C->getValue())) 651 return DAG.getNode(ISD::SHL, VT, N0, 652 DAG.getConstant(Log2_64(N1C->getValue()), 653 TLI.getShiftAmountTy())); 654 // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c 655 if (N1C && isPowerOf2_64(-N1C->getSignExtended())) { 656 // FIXME: If the input is something that is easily negated (e.g. a 657 // single-use add), we should put the negate there. 658 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), 659 DAG.getNode(ISD::SHL, VT, N0, 660 DAG.getConstant(Log2_64(-N1C->getSignExtended()), 661 TLI.getShiftAmountTy()))); 662 } 663 664 // (mul (shl X, c1), c2) -> (mul X, c2 << c1) 665 if (N1C && N0.getOpcode() == ISD::SHL && 666 isa<ConstantSDNode>(N0.getOperand(1))) { 667 SDOperand C3 = DAG.getNode(ISD::SHL, VT, N1, N0.getOperand(1)); 668 AddToWorkList(C3.Val); 669 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), C3); 670 } 671 672 // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one 673 // use. 674 { 675 SDOperand Sh(0,0), Y(0,0); 676 // Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)). 677 if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) && 678 N0.Val->hasOneUse()) { 679 Sh = N0; Y = N1; 680 } else if (N1.getOpcode() == ISD::SHL && 681 isa<ConstantSDNode>(N1.getOperand(1)) && N1.Val->hasOneUse()) { 682 Sh = N1; Y = N0; 683 } 684 if (Sh.Val) { 685 SDOperand Mul = DAG.getNode(ISD::MUL, VT, Sh.getOperand(0), Y); 686 return DAG.getNode(ISD::SHL, VT, Mul, Sh.getOperand(1)); 687 } 688 } 689 // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2) 690 if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 691 isa<ConstantSDNode>(N0.getOperand(1))) { 692 return DAG.getNode(ISD::ADD, VT, 693 DAG.getNode(ISD::MUL, VT, N0.getOperand(0), N1), 694 DAG.getNode(ISD::MUL, VT, N0.getOperand(1), N1)); 695 } 696 697 // reassociate mul 698 SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1); 699 if (RMUL.Val != 0) 700 return RMUL; 701 return SDOperand(); 702} 703 704SDOperand DAGCombiner::visitSDIV(SDNode *N) { 705 SDOperand N0 = N->getOperand(0); 706 SDOperand N1 = N->getOperand(1); 707 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 708 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 709 MVT::ValueType VT = N->getValueType(0); 710 711 // fold (sdiv c1, c2) -> c1/c2 712 if (N0C && N1C && !N1C->isNullValue()) 713 return DAG.getNode(ISD::SDIV, VT, N0, N1); 714 // fold (sdiv X, 1) -> X 715 if (N1C && N1C->getSignExtended() == 1LL) 716 return N0; 717 // fold (sdiv X, -1) -> 0-X 718 if (N1C && N1C->isAllOnesValue()) 719 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 720 // If we know the sign bits of both operands are zero, strength reduce to a 721 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 722 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 723 if (TLI.MaskedValueIsZero(N1, SignBit) && 724 TLI.MaskedValueIsZero(N0, SignBit)) 725 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 726 // fold (sdiv X, pow2) -> simple ops after legalize 727 if (N1C && N1C->getValue() && !TLI.isIntDivCheap() && 728 (isPowerOf2_64(N1C->getSignExtended()) || 729 isPowerOf2_64(-N1C->getSignExtended()))) { 730 // If dividing by powers of two is cheap, then don't perform the following 731 // fold. 732 if (TLI.isPow2DivCheap()) 733 return SDOperand(); 734 int64_t pow2 = N1C->getSignExtended(); 735 int64_t abs2 = pow2 > 0 ? pow2 : -pow2; 736 unsigned lg2 = Log2_64(abs2); 737 // Splat the sign bit into the register 738 SDOperand SGN = DAG.getNode(ISD::SRA, VT, N0, 739 DAG.getConstant(MVT::getSizeInBits(VT)-1, 740 TLI.getShiftAmountTy())); 741 AddToWorkList(SGN.Val); 742 // Add (N0 < 0) ? abs2 - 1 : 0; 743 SDOperand SRL = DAG.getNode(ISD::SRL, VT, SGN, 744 DAG.getConstant(MVT::getSizeInBits(VT)-lg2, 745 TLI.getShiftAmountTy())); 746 SDOperand ADD = DAG.getNode(ISD::ADD, VT, N0, SRL); 747 AddToWorkList(SRL.Val); 748 AddToWorkList(ADD.Val); // Divide by pow2 749 SDOperand SRA = DAG.getNode(ISD::SRA, VT, ADD, 750 DAG.getConstant(lg2, TLI.getShiftAmountTy())); 751 // If we're dividing by a positive value, we're done. Otherwise, we must 752 // negate the result. 753 if (pow2 > 0) 754 return SRA; 755 AddToWorkList(SRA.Val); 756 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA); 757 } 758 // if integer divide is expensive and we satisfy the requirements, emit an 759 // alternate sequence. 760 if (N1C && (N1C->getSignExtended() < -1 || N1C->getSignExtended() > 1) && 761 !TLI.isIntDivCheap()) { 762 SDOperand Op = BuildSDIV(N); 763 if (Op.Val) return Op; 764 } 765 return SDOperand(); 766} 767 768SDOperand DAGCombiner::visitUDIV(SDNode *N) { 769 SDOperand N0 = N->getOperand(0); 770 SDOperand N1 = N->getOperand(1); 771 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 772 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 773 MVT::ValueType VT = N->getValueType(0); 774 775 // fold (udiv c1, c2) -> c1/c2 776 if (N0C && N1C && !N1C->isNullValue()) 777 return DAG.getNode(ISD::UDIV, VT, N0, N1); 778 // fold (udiv x, (1 << c)) -> x >>u c 779 if (N1C && isPowerOf2_64(N1C->getValue())) 780 return DAG.getNode(ISD::SRL, VT, N0, 781 DAG.getConstant(Log2_64(N1C->getValue()), 782 TLI.getShiftAmountTy())); 783 // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2 784 if (N1.getOpcode() == ISD::SHL) { 785 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 786 if (isPowerOf2_64(SHC->getValue())) { 787 MVT::ValueType ADDVT = N1.getOperand(1).getValueType(); 788 SDOperand Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1), 789 DAG.getConstant(Log2_64(SHC->getValue()), 790 ADDVT)); 791 AddToWorkList(Add.Val); 792 return DAG.getNode(ISD::SRL, VT, N0, Add); 793 } 794 } 795 } 796 // fold (udiv x, c) -> alternate 797 if (N1C && N1C->getValue() && !TLI.isIntDivCheap()) { 798 SDOperand Op = BuildUDIV(N); 799 if (Op.Val) return Op; 800 } 801 return SDOperand(); 802} 803 804SDOperand DAGCombiner::visitSREM(SDNode *N) { 805 SDOperand N0 = N->getOperand(0); 806 SDOperand N1 = N->getOperand(1); 807 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 808 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 809 MVT::ValueType VT = N->getValueType(0); 810 811 // fold (srem c1, c2) -> c1%c2 812 if (N0C && N1C && !N1C->isNullValue()) 813 return DAG.getNode(ISD::SREM, VT, N0, N1); 814 // If we know the sign bits of both operands are zero, strength reduce to a 815 // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15 816 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 817 if (TLI.MaskedValueIsZero(N1, SignBit) && 818 TLI.MaskedValueIsZero(N0, SignBit)) 819 return DAG.getNode(ISD::UREM, VT, N0, N1); 820 return SDOperand(); 821} 822 823SDOperand DAGCombiner::visitUREM(SDNode *N) { 824 SDOperand N0 = N->getOperand(0); 825 SDOperand N1 = N->getOperand(1); 826 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 827 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 828 MVT::ValueType VT = N->getValueType(0); 829 830 // fold (urem c1, c2) -> c1%c2 831 if (N0C && N1C && !N1C->isNullValue()) 832 return DAG.getNode(ISD::UREM, VT, N0, N1); 833 // fold (urem x, pow2) -> (and x, pow2-1) 834 if (N1C && !N1C->isNullValue() && isPowerOf2_64(N1C->getValue())) 835 return DAG.getNode(ISD::AND, VT, N0, DAG.getConstant(N1C->getValue()-1,VT)); 836 // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1)) 837 if (N1.getOpcode() == ISD::SHL) { 838 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 839 if (isPowerOf2_64(SHC->getValue())) { 840 SDOperand Add = DAG.getNode(ISD::ADD, VT, N1,DAG.getConstant(~0ULL,VT)); 841 AddToWorkList(Add.Val); 842 return DAG.getNode(ISD::AND, VT, N0, Add); 843 } 844 } 845 } 846 return SDOperand(); 847} 848 849SDOperand DAGCombiner::visitMULHS(SDNode *N) { 850 SDOperand N0 = N->getOperand(0); 851 SDOperand N1 = N->getOperand(1); 852 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 853 854 // fold (mulhs x, 0) -> 0 855 if (N1C && N1C->isNullValue()) 856 return N1; 857 // fold (mulhs x, 1) -> (sra x, size(x)-1) 858 if (N1C && N1C->getValue() == 1) 859 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 860 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 861 TLI.getShiftAmountTy())); 862 return SDOperand(); 863} 864 865SDOperand DAGCombiner::visitMULHU(SDNode *N) { 866 SDOperand N0 = N->getOperand(0); 867 SDOperand N1 = N->getOperand(1); 868 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 869 870 // fold (mulhu x, 0) -> 0 871 if (N1C && N1C->isNullValue()) 872 return N1; 873 // fold (mulhu x, 1) -> 0 874 if (N1C && N1C->getValue() == 1) 875 return DAG.getConstant(0, N0.getValueType()); 876 return SDOperand(); 877} 878 879/// SimplifyBinOpWithSameOpcodeHands - If this is a binary operator with 880/// two operands of the same opcode, try to simplify it. 881SDOperand DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) { 882 SDOperand N0 = N->getOperand(0), N1 = N->getOperand(1); 883 MVT::ValueType VT = N0.getValueType(); 884 assert(N0.getOpcode() == N1.getOpcode() && "Bad input!"); 885 886 // For each of OP in AND/OR/XOR: 887 // fold (OP (zext x), (zext y)) -> (zext (OP x, y)) 888 // fold (OP (sext x), (sext y)) -> (sext (OP x, y)) 889 // fold (OP (aext x), (aext y)) -> (aext (OP x, y)) 890 // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y)) 891 if ((N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND|| 892 N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::TRUNCATE) && 893 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 894 SDOperand ORNode = DAG.getNode(N->getOpcode(), 895 N0.getOperand(0).getValueType(), 896 N0.getOperand(0), N1.getOperand(0)); 897 AddToWorkList(ORNode.Val); 898 return DAG.getNode(N0.getOpcode(), VT, ORNode); 899 } 900 901 // For each of OP in SHL/SRL/SRA/AND... 902 // fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z) 903 // fold (or (OP x, z), (OP y, z)) -> (OP (or x, y), z) 904 // fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z) 905 if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL || 906 N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) && 907 N0.getOperand(1) == N1.getOperand(1)) { 908 SDOperand ORNode = DAG.getNode(N->getOpcode(), 909 N0.getOperand(0).getValueType(), 910 N0.getOperand(0), N1.getOperand(0)); 911 AddToWorkList(ORNode.Val); 912 return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1)); 913 } 914 915 return SDOperand(); 916} 917 918SDOperand DAGCombiner::visitAND(SDNode *N) { 919 SDOperand N0 = N->getOperand(0); 920 SDOperand N1 = N->getOperand(1); 921 SDOperand LL, LR, RL, RR, CC0, CC1; 922 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 923 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 924 MVT::ValueType VT = N1.getValueType(); 925 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 926 927 // fold (and c1, c2) -> c1&c2 928 if (N0C && N1C) 929 return DAG.getNode(ISD::AND, VT, N0, N1); 930 // canonicalize constant to RHS 931 if (N0C && !N1C) 932 return DAG.getNode(ISD::AND, VT, N1, N0); 933 // fold (and x, -1) -> x 934 if (N1C && N1C->isAllOnesValue()) 935 return N0; 936 // if (and x, c) is known to be zero, return 0 937 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) 938 return DAG.getConstant(0, VT); 939 // reassociate and 940 SDOperand RAND = ReassociateOps(ISD::AND, N0, N1); 941 if (RAND.Val != 0) 942 return RAND; 943 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 944 if (N1C && N0.getOpcode() == ISD::OR) 945 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 946 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 947 return N1; 948 // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits. 949 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 950 unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType()); 951 if (TLI.MaskedValueIsZero(N0.getOperand(0), 952 ~N1C->getValue() & InMask)) { 953 SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(), 954 N0.getOperand(0)); 955 956 // Replace uses of the AND with uses of the Zero extend node. 957 CombineTo(N, Zext); 958 959 // We actually want to replace all uses of the any_extend with the 960 // zero_extend, to avoid duplicating things. This will later cause this 961 // AND to be folded. 962 CombineTo(N0.Val, Zext); 963 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 964 } 965 } 966 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 967 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 968 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 969 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 970 971 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 972 MVT::isInteger(LL.getValueType())) { 973 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 974 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 975 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 976 AddToWorkList(ORNode.Val); 977 return DAG.getSetCC(VT, ORNode, LR, Op1); 978 } 979 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 980 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 981 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 982 AddToWorkList(ANDNode.Val); 983 return DAG.getSetCC(VT, ANDNode, LR, Op1); 984 } 985 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 986 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 987 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 988 AddToWorkList(ORNode.Val); 989 return DAG.getSetCC(VT, ORNode, LR, Op1); 990 } 991 } 992 // canonicalize equivalent to ll == rl 993 if (LL == RR && LR == RL) { 994 Op1 = ISD::getSetCCSwappedOperands(Op1); 995 std::swap(RL, RR); 996 } 997 if (LL == RL && LR == RR) { 998 bool isInteger = MVT::isInteger(LL.getValueType()); 999 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 1000 if (Result != ISD::SETCC_INVALID) 1001 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1002 } 1003 } 1004 1005 // Simplify: and (op x...), (op y...) -> (op (and x, y)) 1006 if (N0.getOpcode() == N1.getOpcode()) { 1007 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1008 if (Tmp.Val) return Tmp; 1009 } 1010 1011 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 1012 // fold (and (sra)) -> (and (srl)) when possible. 1013 if (!MVT::isVector(VT) && 1014 SimplifyDemandedBits(SDOperand(N, 0))) 1015 return SDOperand(N, 0); 1016 // fold (zext_inreg (extload x)) -> (zextload x) 1017 if (N0.getOpcode() == ISD::EXTLOAD) { 1018 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1019 // If we zero all the possible extended bits, then we can turn this into 1020 // a zextload if we are running before legalize or the operation is legal. 1021 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1022 (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) { 1023 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1024 N0.getOperand(1), N0.getOperand(2), 1025 EVT); 1026 AddToWorkList(N); 1027 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1028 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1029 } 1030 } 1031 // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use 1032 if (N0.getOpcode() == ISD::SEXTLOAD && N0.hasOneUse()) { 1033 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1034 // If we zero all the possible extended bits, then we can turn this into 1035 // a zextload if we are running before legalize or the operation is legal. 1036 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1037 (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) { 1038 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1039 N0.getOperand(1), N0.getOperand(2), 1040 EVT); 1041 AddToWorkList(N); 1042 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1043 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1044 } 1045 } 1046 1047 // fold (and (load x), 255) -> (zextload x, i8) 1048 // fold (and (extload x, i16), 255) -> (zextload x, i8) 1049 if (N1C && 1050 (N0.getOpcode() == ISD::LOAD || N0.getOpcode() == ISD::EXTLOAD || 1051 N0.getOpcode() == ISD::ZEXTLOAD) && 1052 N0.hasOneUse()) { 1053 MVT::ValueType EVT, LoadedVT; 1054 if (N1C->getValue() == 255) 1055 EVT = MVT::i8; 1056 else if (N1C->getValue() == 65535) 1057 EVT = MVT::i16; 1058 else if (N1C->getValue() == ~0U) 1059 EVT = MVT::i32; 1060 else 1061 EVT = MVT::Other; 1062 1063 LoadedVT = N0.getOpcode() == ISD::LOAD ? VT : 1064 cast<VTSDNode>(N0.getOperand(3))->getVT(); 1065 if (EVT != MVT::Other && LoadedVT > EVT && 1066 (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) { 1067 MVT::ValueType PtrType = N0.getOperand(1).getValueType(); 1068 // For big endian targets, we need to add an offset to the pointer to load 1069 // the correct bytes. For little endian systems, we merely need to read 1070 // fewer bytes from the same pointer. 1071 unsigned PtrOff = 1072 (MVT::getSizeInBits(LoadedVT) - MVT::getSizeInBits(EVT)) / 8; 1073 SDOperand NewPtr = N0.getOperand(1); 1074 if (!TLI.isLittleEndian()) 1075 NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr, 1076 DAG.getConstant(PtrOff, PtrType)); 1077 AddToWorkList(NewPtr.Val); 1078 SDOperand Load = 1079 DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), NewPtr, 1080 N0.getOperand(2), EVT); 1081 AddToWorkList(N); 1082 CombineTo(N0.Val, Load, Load.getValue(1)); 1083 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1084 } 1085 } 1086 1087 return SDOperand(); 1088} 1089 1090SDOperand DAGCombiner::visitOR(SDNode *N) { 1091 SDOperand N0 = N->getOperand(0); 1092 SDOperand N1 = N->getOperand(1); 1093 SDOperand LL, LR, RL, RR, CC0, CC1; 1094 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1095 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1096 MVT::ValueType VT = N1.getValueType(); 1097 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1098 1099 // fold (or c1, c2) -> c1|c2 1100 if (N0C && N1C) 1101 return DAG.getNode(ISD::OR, VT, N0, N1); 1102 // canonicalize constant to RHS 1103 if (N0C && !N1C) 1104 return DAG.getNode(ISD::OR, VT, N1, N0); 1105 // fold (or x, 0) -> x 1106 if (N1C && N1C->isNullValue()) 1107 return N0; 1108 // fold (or x, -1) -> -1 1109 if (N1C && N1C->isAllOnesValue()) 1110 return N1; 1111 // fold (or x, c) -> c iff (x & ~c) == 0 1112 if (N1C && 1113 TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) 1114 return N1; 1115 // reassociate or 1116 SDOperand ROR = ReassociateOps(ISD::OR, N0, N1); 1117 if (ROR.Val != 0) 1118 return ROR; 1119 // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2) 1120 if (N1C && N0.getOpcode() == ISD::AND && N0.Val->hasOneUse() && 1121 isa<ConstantSDNode>(N0.getOperand(1))) { 1122 ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1)); 1123 return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0), 1124 N1), 1125 DAG.getConstant(N1C->getValue() | C1->getValue(), VT)); 1126 } 1127 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 1128 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1129 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1130 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1131 1132 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1133 MVT::isInteger(LL.getValueType())) { 1134 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 1135 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 1136 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 1137 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 1138 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1139 AddToWorkList(ORNode.Val); 1140 return DAG.getSetCC(VT, ORNode, LR, Op1); 1141 } 1142 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 1143 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 1144 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 1145 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 1146 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1147 AddToWorkList(ANDNode.Val); 1148 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1149 } 1150 } 1151 // canonicalize equivalent to ll == rl 1152 if (LL == RR && LR == RL) { 1153 Op1 = ISD::getSetCCSwappedOperands(Op1); 1154 std::swap(RL, RR); 1155 } 1156 if (LL == RL && LR == RR) { 1157 bool isInteger = MVT::isInteger(LL.getValueType()); 1158 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 1159 if (Result != ISD::SETCC_INVALID) 1160 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1161 } 1162 } 1163 1164 // Simplify: or (op x...), (op y...) -> (op (or x, y)) 1165 if (N0.getOpcode() == N1.getOpcode()) { 1166 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1167 if (Tmp.Val) return Tmp; 1168 } 1169 1170 // canonicalize shl to left side in a shl/srl pair, to match rotate 1171 if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL) 1172 std::swap(N0, N1); 1173 // check for rotl, rotr 1174 if (N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SRL && 1175 N0.getOperand(0) == N1.getOperand(0) && 1176 TLI.isOperationLegal(ISD::ROTL, VT) && TLI.isTypeLegal(VT)) { 1177 // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1) 1178 if (N0.getOperand(1).getOpcode() == ISD::Constant && 1179 N1.getOperand(1).getOpcode() == ISD::Constant) { 1180 uint64_t c1val = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1181 uint64_t c2val = cast<ConstantSDNode>(N1.getOperand(1))->getValue(); 1182 if ((c1val + c2val) == OpSizeInBits) 1183 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1)); 1184 } 1185 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y) 1186 if (N1.getOperand(1).getOpcode() == ISD::SUB && 1187 N0.getOperand(1) == N1.getOperand(1).getOperand(1)) 1188 if (ConstantSDNode *SUBC = 1189 dyn_cast<ConstantSDNode>(N1.getOperand(1).getOperand(0))) 1190 if (SUBC->getValue() == OpSizeInBits) 1191 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1)); 1192 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y) 1193 if (N0.getOperand(1).getOpcode() == ISD::SUB && 1194 N1.getOperand(1) == N0.getOperand(1).getOperand(1)) 1195 if (ConstantSDNode *SUBC = 1196 dyn_cast<ConstantSDNode>(N0.getOperand(1).getOperand(0))) 1197 if (SUBC->getValue() == OpSizeInBits) { 1198 if (TLI.isOperationLegal(ISD::ROTR, VT) && TLI.isTypeLegal(VT)) 1199 return DAG.getNode(ISD::ROTR, VT, N0.getOperand(0), 1200 N1.getOperand(1)); 1201 else 1202 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), 1203 N0.getOperand(1)); 1204 } 1205 } 1206 return SDOperand(); 1207} 1208 1209SDOperand DAGCombiner::visitXOR(SDNode *N) { 1210 SDOperand N0 = N->getOperand(0); 1211 SDOperand N1 = N->getOperand(1); 1212 SDOperand LHS, RHS, CC; 1213 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1214 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1215 MVT::ValueType VT = N0.getValueType(); 1216 1217 // fold (xor c1, c2) -> c1^c2 1218 if (N0C && N1C) 1219 return DAG.getNode(ISD::XOR, VT, N0, N1); 1220 // canonicalize constant to RHS 1221 if (N0C && !N1C) 1222 return DAG.getNode(ISD::XOR, VT, N1, N0); 1223 // fold (xor x, 0) -> x 1224 if (N1C && N1C->isNullValue()) 1225 return N0; 1226 // reassociate xor 1227 SDOperand RXOR = ReassociateOps(ISD::XOR, N0, N1); 1228 if (RXOR.Val != 0) 1229 return RXOR; 1230 // fold !(x cc y) -> (x !cc y) 1231 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 1232 bool isInt = MVT::isInteger(LHS.getValueType()); 1233 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 1234 isInt); 1235 if (N0.getOpcode() == ISD::SETCC) 1236 return DAG.getSetCC(VT, LHS, RHS, NotCC); 1237 if (N0.getOpcode() == ISD::SELECT_CC) 1238 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 1239 assert(0 && "Unhandled SetCC Equivalent!"); 1240 abort(); 1241 } 1242 // fold !(x or y) -> (!x and !y) iff x or y are setcc 1243 if (N1C && N1C->getValue() == 1 && 1244 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1245 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1246 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 1247 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1248 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1249 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1250 AddToWorkList(LHS.Val); AddToWorkList(RHS.Val); 1251 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1252 } 1253 } 1254 // fold !(x or y) -> (!x and !y) iff x or y are constants 1255 if (N1C && N1C->isAllOnesValue() && 1256 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1257 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1258 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 1259 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1260 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1261 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1262 AddToWorkList(LHS.Val); AddToWorkList(RHS.Val); 1263 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1264 } 1265 } 1266 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 1267 if (N1C && N0.getOpcode() == ISD::XOR) { 1268 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 1269 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 1270 if (N00C) 1271 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 1272 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 1273 if (N01C) 1274 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 1275 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 1276 } 1277 // fold (xor x, x) -> 0 1278 if (N0 == N1) { 1279 if (!MVT::isVector(VT)) { 1280 return DAG.getConstant(0, VT); 1281 } else if (!AfterLegalize || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)) { 1282 // Produce a vector of zeros. 1283 SDOperand El = DAG.getConstant(0, MVT::getVectorBaseType(VT)); 1284 std::vector<SDOperand> Ops(MVT::getVectorNumElements(VT), El); 1285 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 1286 } 1287 } 1288 1289 // Simplify: xor (op x...), (op y...) -> (op (xor x, y)) 1290 if (N0.getOpcode() == N1.getOpcode()) { 1291 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1292 if (Tmp.Val) return Tmp; 1293 } 1294 1295 // Simplify the expression using non-local knowledge. 1296 if (!MVT::isVector(VT) && 1297 SimplifyDemandedBits(SDOperand(N, 0))) 1298 return SDOperand(N, 0); 1299 1300 return SDOperand(); 1301} 1302 1303SDOperand DAGCombiner::visitSHL(SDNode *N) { 1304 SDOperand N0 = N->getOperand(0); 1305 SDOperand N1 = N->getOperand(1); 1306 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1307 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1308 MVT::ValueType VT = N0.getValueType(); 1309 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1310 1311 // fold (shl c1, c2) -> c1<<c2 1312 if (N0C && N1C) 1313 return DAG.getNode(ISD::SHL, VT, N0, N1); 1314 // fold (shl 0, x) -> 0 1315 if (N0C && N0C->isNullValue()) 1316 return N0; 1317 // fold (shl x, c >= size(x)) -> undef 1318 if (N1C && N1C->getValue() >= OpSizeInBits) 1319 return DAG.getNode(ISD::UNDEF, VT); 1320 // fold (shl x, 0) -> x 1321 if (N1C && N1C->isNullValue()) 1322 return N0; 1323 // if (shl x, c) is known to be zero, return 0 1324 if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) 1325 return DAG.getConstant(0, VT); 1326 if (SimplifyDemandedBits(SDOperand(N, 0))) 1327 return SDOperand(N, 0); 1328 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 1329 if (N1C && N0.getOpcode() == ISD::SHL && 1330 N0.getOperand(1).getOpcode() == ISD::Constant) { 1331 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1332 uint64_t c2 = N1C->getValue(); 1333 if (c1 + c2 > OpSizeInBits) 1334 return DAG.getConstant(0, VT); 1335 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 1336 DAG.getConstant(c1 + c2, N1.getValueType())); 1337 } 1338 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 1339 // (srl (and x, -1 << c1), c1-c2) 1340 if (N1C && N0.getOpcode() == ISD::SRL && 1341 N0.getOperand(1).getOpcode() == ISD::Constant) { 1342 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1343 uint64_t c2 = N1C->getValue(); 1344 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1345 DAG.getConstant(~0ULL << c1, VT)); 1346 if (c2 > c1) 1347 return DAG.getNode(ISD::SHL, VT, Mask, 1348 DAG.getConstant(c2-c1, N1.getValueType())); 1349 else 1350 return DAG.getNode(ISD::SRL, VT, Mask, 1351 DAG.getConstant(c1-c2, N1.getValueType())); 1352 } 1353 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 1354 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 1355 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1356 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 1357 // fold (shl (add x, c1), c2) -> (add (shl x, c2), c1<<c2) 1358 if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 1359 isa<ConstantSDNode>(N0.getOperand(1))) { 1360 return DAG.getNode(ISD::ADD, VT, 1361 DAG.getNode(ISD::SHL, VT, N0.getOperand(0), N1), 1362 DAG.getNode(ISD::SHL, VT, N0.getOperand(1), N1)); 1363 } 1364 return SDOperand(); 1365} 1366 1367SDOperand DAGCombiner::visitSRA(SDNode *N) { 1368 SDOperand N0 = N->getOperand(0); 1369 SDOperand N1 = N->getOperand(1); 1370 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1371 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1372 MVT::ValueType VT = N0.getValueType(); 1373 1374 // fold (sra c1, c2) -> c1>>c2 1375 if (N0C && N1C) 1376 return DAG.getNode(ISD::SRA, VT, N0, N1); 1377 // fold (sra 0, x) -> 0 1378 if (N0C && N0C->isNullValue()) 1379 return N0; 1380 // fold (sra -1, x) -> -1 1381 if (N0C && N0C->isAllOnesValue()) 1382 return N0; 1383 // fold (sra x, c >= size(x)) -> undef 1384 if (N1C && N1C->getValue() >= MVT::getSizeInBits(VT)) 1385 return DAG.getNode(ISD::UNDEF, VT); 1386 // fold (sra x, 0) -> x 1387 if (N1C && N1C->isNullValue()) 1388 return N0; 1389 // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports 1390 // sext_inreg. 1391 if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) { 1392 unsigned LowBits = MVT::getSizeInBits(VT) - (unsigned)N1C->getValue(); 1393 MVT::ValueType EVT; 1394 switch (LowBits) { 1395 default: EVT = MVT::Other; break; 1396 case 1: EVT = MVT::i1; break; 1397 case 8: EVT = MVT::i8; break; 1398 case 16: EVT = MVT::i16; break; 1399 case 32: EVT = MVT::i32; break; 1400 } 1401 if (EVT > MVT::Other && TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT)) 1402 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), 1403 DAG.getValueType(EVT)); 1404 } 1405 1406 // fold (sra (sra x, c1), c2) -> (sra x, c1+c2) 1407 if (N1C && N0.getOpcode() == ISD::SRA) { 1408 if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1409 unsigned Sum = N1C->getValue() + C1->getValue(); 1410 if (Sum >= MVT::getSizeInBits(VT)) Sum = MVT::getSizeInBits(VT)-1; 1411 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), 1412 DAG.getConstant(Sum, N1C->getValueType(0))); 1413 } 1414 } 1415 1416 // Simplify, based on bits shifted out of the LHS. 1417 if (N1C && SimplifyDemandedBits(SDOperand(N, 0))) 1418 return SDOperand(N, 0); 1419 1420 1421 // If the sign bit is known to be zero, switch this to a SRL. 1422 if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT))) 1423 return DAG.getNode(ISD::SRL, VT, N0, N1); 1424 return SDOperand(); 1425} 1426 1427SDOperand DAGCombiner::visitSRL(SDNode *N) { 1428 SDOperand N0 = N->getOperand(0); 1429 SDOperand N1 = N->getOperand(1); 1430 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1431 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1432 MVT::ValueType VT = N0.getValueType(); 1433 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1434 1435 // fold (srl c1, c2) -> c1 >>u c2 1436 if (N0C && N1C) 1437 return DAG.getNode(ISD::SRL, VT, N0, N1); 1438 // fold (srl 0, x) -> 0 1439 if (N0C && N0C->isNullValue()) 1440 return N0; 1441 // fold (srl x, c >= size(x)) -> undef 1442 if (N1C && N1C->getValue() >= OpSizeInBits) 1443 return DAG.getNode(ISD::UNDEF, VT); 1444 // fold (srl x, 0) -> x 1445 if (N1C && N1C->isNullValue()) 1446 return N0; 1447 // if (srl x, c) is known to be zero, return 0 1448 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) 1449 return DAG.getConstant(0, VT); 1450 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 1451 if (N1C && N0.getOpcode() == ISD::SRL && 1452 N0.getOperand(1).getOpcode() == ISD::Constant) { 1453 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1454 uint64_t c2 = N1C->getValue(); 1455 if (c1 + c2 > OpSizeInBits) 1456 return DAG.getConstant(0, VT); 1457 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 1458 DAG.getConstant(c1 + c2, N1.getValueType())); 1459 } 1460 1461 // fold (srl (anyextend x), c) -> (anyextend (srl x, c)) 1462 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 1463 // Shifting in all undef bits? 1464 MVT::ValueType SmallVT = N0.getOperand(0).getValueType(); 1465 if (N1C->getValue() >= MVT::getSizeInBits(SmallVT)) 1466 return DAG.getNode(ISD::UNDEF, VT); 1467 1468 SDOperand SmallShift = DAG.getNode(ISD::SRL, SmallVT, N0.getOperand(0), N1); 1469 AddToWorkList(SmallShift.Val); 1470 return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift); 1471 } 1472 1473 // fold (srl (ctlz x), "5") -> x iff x has one bit set (the low bit). 1474 if (N1C && N0.getOpcode() == ISD::CTLZ && 1475 N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) { 1476 uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT); 1477 TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne); 1478 1479 // If any of the input bits are KnownOne, then the input couldn't be all 1480 // zeros, thus the result of the srl will always be zero. 1481 if (KnownOne) return DAG.getConstant(0, VT); 1482 1483 // If all of the bits input the to ctlz node are known to be zero, then 1484 // the result of the ctlz is "32" and the result of the shift is one. 1485 uint64_t UnknownBits = ~KnownZero & Mask; 1486 if (UnknownBits == 0) return DAG.getConstant(1, VT); 1487 1488 // Otherwise, check to see if there is exactly one bit input to the ctlz. 1489 if ((UnknownBits & (UnknownBits-1)) == 0) { 1490 // Okay, we know that only that the single bit specified by UnknownBits 1491 // could be set on input to the CTLZ node. If this bit is set, the SRL 1492 // will return 0, if it is clear, it returns 1. Change the CTLZ/SRL pair 1493 // to an SRL,XOR pair, which is likely to simplify more. 1494 unsigned ShAmt = CountTrailingZeros_64(UnknownBits); 1495 SDOperand Op = N0.getOperand(0); 1496 if (ShAmt) { 1497 Op = DAG.getNode(ISD::SRL, VT, Op, 1498 DAG.getConstant(ShAmt, TLI.getShiftAmountTy())); 1499 AddToWorkList(Op.Val); 1500 } 1501 return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT)); 1502 } 1503 } 1504 1505 return SDOperand(); 1506} 1507 1508SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 1509 SDOperand N0 = N->getOperand(0); 1510 MVT::ValueType VT = N->getValueType(0); 1511 1512 // fold (ctlz c1) -> c2 1513 if (isa<ConstantSDNode>(N0)) 1514 return DAG.getNode(ISD::CTLZ, VT, N0); 1515 return SDOperand(); 1516} 1517 1518SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 1519 SDOperand N0 = N->getOperand(0); 1520 MVT::ValueType VT = N->getValueType(0); 1521 1522 // fold (cttz c1) -> c2 1523 if (isa<ConstantSDNode>(N0)) 1524 return DAG.getNode(ISD::CTTZ, VT, N0); 1525 return SDOperand(); 1526} 1527 1528SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 1529 SDOperand N0 = N->getOperand(0); 1530 MVT::ValueType VT = N->getValueType(0); 1531 1532 // fold (ctpop c1) -> c2 1533 if (isa<ConstantSDNode>(N0)) 1534 return DAG.getNode(ISD::CTPOP, VT, N0); 1535 return SDOperand(); 1536} 1537 1538SDOperand DAGCombiner::visitSELECT(SDNode *N) { 1539 SDOperand N0 = N->getOperand(0); 1540 SDOperand N1 = N->getOperand(1); 1541 SDOperand N2 = N->getOperand(2); 1542 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1543 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1544 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1545 MVT::ValueType VT = N->getValueType(0); 1546 1547 // fold select C, X, X -> X 1548 if (N1 == N2) 1549 return N1; 1550 // fold select true, X, Y -> X 1551 if (N0C && !N0C->isNullValue()) 1552 return N1; 1553 // fold select false, X, Y -> Y 1554 if (N0C && N0C->isNullValue()) 1555 return N2; 1556 // fold select C, 1, X -> C | X 1557 if (MVT::i1 == VT && N1C && N1C->getValue() == 1) 1558 return DAG.getNode(ISD::OR, VT, N0, N2); 1559 // fold select C, 0, X -> ~C & X 1560 // FIXME: this should check for C type == X type, not i1? 1561 if (MVT::i1 == VT && N1C && N1C->isNullValue()) { 1562 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1563 AddToWorkList(XORNode.Val); 1564 return DAG.getNode(ISD::AND, VT, XORNode, N2); 1565 } 1566 // fold select C, X, 1 -> ~C | X 1567 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) { 1568 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1569 AddToWorkList(XORNode.Val); 1570 return DAG.getNode(ISD::OR, VT, XORNode, N1); 1571 } 1572 // fold select C, X, 0 -> C & X 1573 // FIXME: this should check for C type == X type, not i1? 1574 if (MVT::i1 == VT && N2C && N2C->isNullValue()) 1575 return DAG.getNode(ISD::AND, VT, N0, N1); 1576 // fold X ? X : Y --> X ? 1 : Y --> X | Y 1577 if (MVT::i1 == VT && N0 == N1) 1578 return DAG.getNode(ISD::OR, VT, N0, N2); 1579 // fold X ? Y : X --> X ? Y : 0 --> X & Y 1580 if (MVT::i1 == VT && N0 == N2) 1581 return DAG.getNode(ISD::AND, VT, N0, N1); 1582 1583 // If we can fold this based on the true/false value, do so. 1584 if (SimplifySelectOps(N, N1, N2)) 1585 return SDOperand(N, 0); // Don't revisit N. 1586 1587 // fold selects based on a setcc into other things, such as min/max/abs 1588 if (N0.getOpcode() == ISD::SETCC) 1589 // FIXME: 1590 // Check against MVT::Other for SELECT_CC, which is a workaround for targets 1591 // having to say they don't support SELECT_CC on every type the DAG knows 1592 // about, since there is no way to mark an opcode illegal at all value types 1593 if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other)) 1594 return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1), 1595 N1, N2, N0.getOperand(2)); 1596 else 1597 return SimplifySelect(N0, N1, N2); 1598 return SDOperand(); 1599} 1600 1601SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) { 1602 SDOperand N0 = N->getOperand(0); 1603 SDOperand N1 = N->getOperand(1); 1604 SDOperand N2 = N->getOperand(2); 1605 SDOperand N3 = N->getOperand(3); 1606 SDOperand N4 = N->getOperand(4); 1607 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1608 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1609 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1610 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 1611 1612 // Determine if the condition we're dealing with is constant 1613 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1614 //ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1615 1616 // fold select_cc lhs, rhs, x, x, cc -> x 1617 if (N2 == N3) 1618 return N2; 1619 1620 // If we can fold this based on the true/false value, do so. 1621 if (SimplifySelectOps(N, N2, N3)) 1622 return SDOperand(N, 0); // Don't revisit N. 1623 1624 // fold select_cc into other things, such as min/max/abs 1625 return SimplifySelectCC(N0, N1, N2, N3, CC); 1626} 1627 1628SDOperand DAGCombiner::visitSETCC(SDNode *N) { 1629 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 1630 cast<CondCodeSDNode>(N->getOperand(2))->get()); 1631} 1632 1633SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 1634 SDOperand N0 = N->getOperand(0); 1635 MVT::ValueType VT = N->getValueType(0); 1636 1637 // fold (sext c1) -> c1 1638 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0)) 1639 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0); 1640 1641 // fold (sext (sext x)) -> (sext x) 1642 // fold (sext (aext x)) -> (sext x) 1643 if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 1644 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1645 1646 // fold (sext (truncate x)) -> (sextinreg x) iff x size == sext size. 1647 if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&& 1648 (!AfterLegalize || 1649 TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, N0.getValueType()))) 1650 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), 1651 DAG.getValueType(N0.getValueType())); 1652 1653 // fold (sext (load x)) -> (sext (truncate (sextload x))) 1654 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 1655 (!AfterLegalize||TLI.isOperationLegal(ISD::SEXTLOAD, N0.getValueType()))){ 1656 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1657 N0.getOperand(1), N0.getOperand(2), 1658 N0.getValueType()); 1659 CombineTo(N, ExtLoad); 1660 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1661 ExtLoad.getValue(1)); 1662 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1663 } 1664 1665 // fold (sext (sextload x)) -> (sext (truncate (sextload x))) 1666 // fold (sext ( extload x)) -> (sext (truncate (sextload x))) 1667 if ((N0.getOpcode() == ISD::SEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) && 1668 N0.hasOneUse()) { 1669 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1670 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1671 N0.getOperand(1), N0.getOperand(2), EVT); 1672 CombineTo(N, ExtLoad); 1673 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1674 ExtLoad.getValue(1)); 1675 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1676 } 1677 1678 return SDOperand(); 1679} 1680 1681SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1682 SDOperand N0 = N->getOperand(0); 1683 MVT::ValueType VT = N->getValueType(0); 1684 1685 // fold (zext c1) -> c1 1686 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0)) 1687 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 1688 // fold (zext (zext x)) -> (zext x) 1689 // fold (zext (aext x)) -> (zext x) 1690 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 1691 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1692 // fold (zext (truncate x)) -> (zextinreg x) iff x size == zext size. 1693 if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&& 1694 (!AfterLegalize || TLI.isOperationLegal(ISD::AND, N0.getValueType()))) 1695 return DAG.getZeroExtendInReg(N0.getOperand(0), N0.getValueType()); 1696 // fold (zext (load x)) -> (zext (truncate (zextload x))) 1697 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 1698 (!AfterLegalize||TLI.isOperationLegal(ISD::ZEXTLOAD, N0.getValueType()))){ 1699 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1700 N0.getOperand(1), N0.getOperand(2), 1701 N0.getValueType()); 1702 CombineTo(N, ExtLoad); 1703 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1704 ExtLoad.getValue(1)); 1705 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1706 } 1707 1708 // fold (zext (zextload x)) -> (zext (truncate (zextload x))) 1709 // fold (zext ( extload x)) -> (zext (truncate (zextload x))) 1710 if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) && 1711 N0.hasOneUse()) { 1712 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1713 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1714 N0.getOperand(1), N0.getOperand(2), EVT); 1715 CombineTo(N, ExtLoad); 1716 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1717 ExtLoad.getValue(1)); 1718 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1719 } 1720 return SDOperand(); 1721} 1722 1723SDOperand DAGCombiner::visitANY_EXTEND(SDNode *N) { 1724 SDOperand N0 = N->getOperand(0); 1725 MVT::ValueType VT = N->getValueType(0); 1726 1727 // fold (aext c1) -> c1 1728 if (isa<ConstantSDNode>(N0)) 1729 return DAG.getNode(ISD::ANY_EXTEND, VT, N0); 1730 // fold (aext (aext x)) -> (aext x) 1731 // fold (aext (zext x)) -> (zext x) 1732 // fold (aext (sext x)) -> (sext x) 1733 if (N0.getOpcode() == ISD::ANY_EXTEND || 1734 N0.getOpcode() == ISD::ZERO_EXTEND || 1735 N0.getOpcode() == ISD::SIGN_EXTEND) 1736 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1737 1738 // fold (aext (truncate x)) -> x iff x size == zext size. 1739 if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT) 1740 return N0.getOperand(0); 1741 // fold (aext (load x)) -> (aext (truncate (extload x))) 1742 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 1743 (!AfterLegalize||TLI.isOperationLegal(ISD::EXTLOAD, N0.getValueType()))) { 1744 SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, N0.getOperand(0), 1745 N0.getOperand(1), N0.getOperand(2), 1746 N0.getValueType()); 1747 CombineTo(N, ExtLoad); 1748 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1749 ExtLoad.getValue(1)); 1750 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1751 } 1752 1753 // fold (aext (zextload x)) -> (aext (truncate (zextload x))) 1754 // fold (aext (sextload x)) -> (aext (truncate (sextload x))) 1755 // fold (aext ( extload x)) -> (aext (truncate (extload x))) 1756 if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD || 1757 N0.getOpcode() == ISD::SEXTLOAD) && 1758 N0.hasOneUse()) { 1759 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1760 SDOperand ExtLoad = DAG.getExtLoad(N0.getOpcode(), VT, N0.getOperand(0), 1761 N0.getOperand(1), N0.getOperand(2), EVT); 1762 CombineTo(N, ExtLoad); 1763 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1764 ExtLoad.getValue(1)); 1765 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1766 } 1767 return SDOperand(); 1768} 1769 1770 1771SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 1772 SDOperand N0 = N->getOperand(0); 1773 SDOperand N1 = N->getOperand(1); 1774 MVT::ValueType VT = N->getValueType(0); 1775 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 1776 unsigned EVTBits = MVT::getSizeInBits(EVT); 1777 1778 // fold (sext_in_reg c1) -> c1 1779 if (isa<ConstantSDNode>(N0) || N0.getOpcode() == ISD::UNDEF) 1780 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1); 1781 1782 // If the input is already sign extended, just drop the extension. 1783 if (TLI.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1) 1784 return N0; 1785 1786 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 1787 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1788 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 1789 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 1790 } 1791 1792 // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero 1793 if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1))) 1794 return DAG.getZeroExtendInReg(N0, EVT); 1795 1796 // fold (sext_in_reg (srl X, 24), i8) -> sra X, 24 1797 // fold (sext_in_reg (srl X, 23), i8) -> sra X, 23 iff possible. 1798 // We already fold "(sext_in_reg (srl X, 25), i8) -> srl X, 25" above. 1799 if (N0.getOpcode() == ISD::SRL) { 1800 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 1801 if (ShAmt->getValue()+EVTBits <= MVT::getSizeInBits(VT)) { 1802 // We can turn this into an SRA iff the input to the SRL is already sign 1803 // extended enough. 1804 unsigned InSignBits = TLI.ComputeNumSignBits(N0.getOperand(0)); 1805 if (MVT::getSizeInBits(VT)-(ShAmt->getValue()+EVTBits) < InSignBits) 1806 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1)); 1807 } 1808 } 1809 1810 // fold (sext_inreg (extload x)) -> (sextload x) 1811 if (N0.getOpcode() == ISD::EXTLOAD && 1812 EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() && 1813 (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) { 1814 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1815 N0.getOperand(1), N0.getOperand(2), 1816 EVT); 1817 CombineTo(N, ExtLoad); 1818 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1819 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1820 } 1821 // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use 1822 if (N0.getOpcode() == ISD::ZEXTLOAD && N0.hasOneUse() && 1823 EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() && 1824 (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) { 1825 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1826 N0.getOperand(1), N0.getOperand(2), 1827 EVT); 1828 CombineTo(N, ExtLoad); 1829 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1830 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1831 } 1832 return SDOperand(); 1833} 1834 1835SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 1836 SDOperand N0 = N->getOperand(0); 1837 MVT::ValueType VT = N->getValueType(0); 1838 1839 // noop truncate 1840 if (N0.getValueType() == N->getValueType(0)) 1841 return N0; 1842 // fold (truncate c1) -> c1 1843 if (isa<ConstantSDNode>(N0)) 1844 return DAG.getNode(ISD::TRUNCATE, VT, N0); 1845 // fold (truncate (truncate x)) -> (truncate x) 1846 if (N0.getOpcode() == ISD::TRUNCATE) 1847 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1848 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 1849 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND|| 1850 N0.getOpcode() == ISD::ANY_EXTEND) { 1851 if (N0.getValueType() < VT) 1852 // if the source is smaller than the dest, we still need an extend 1853 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1854 else if (N0.getValueType() > VT) 1855 // if the source is larger than the dest, than we just need the truncate 1856 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1857 else 1858 // if the source and dest are the same type, we can drop both the extend 1859 // and the truncate 1860 return N0.getOperand(0); 1861 } 1862 // fold (truncate (load x)) -> (smaller load x) 1863 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) { 1864 assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) && 1865 "Cannot truncate to larger type!"); 1866 MVT::ValueType PtrType = N0.getOperand(1).getValueType(); 1867 // For big endian targets, we need to add an offset to the pointer to load 1868 // the correct bytes. For little endian systems, we merely need to read 1869 // fewer bytes from the same pointer. 1870 uint64_t PtrOff = 1871 (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8; 1872 SDOperand NewPtr = TLI.isLittleEndian() ? N0.getOperand(1) : 1873 DAG.getNode(ISD::ADD, PtrType, N0.getOperand(1), 1874 DAG.getConstant(PtrOff, PtrType)); 1875 AddToWorkList(NewPtr.Val); 1876 SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), NewPtr,N0.getOperand(2)); 1877 AddToWorkList(N); 1878 CombineTo(N0.Val, Load, Load.getValue(1)); 1879 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1880 } 1881 return SDOperand(); 1882} 1883 1884SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) { 1885 SDOperand N0 = N->getOperand(0); 1886 MVT::ValueType VT = N->getValueType(0); 1887 1888 // If the input is a constant, let getNode() fold it. 1889 if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) { 1890 SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0); 1891 if (Res.Val != N) return Res; 1892 } 1893 1894 if (N0.getOpcode() == ISD::BIT_CONVERT) // conv(conv(x,t1),t2) -> conv(x,t2) 1895 return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 1896 1897 // fold (conv (load x)) -> (load (conv*)x) 1898 // FIXME: These xforms need to know that the resultant load doesn't need a 1899 // higher alignment than the original! 1900 if (0 && N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) { 1901 SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), N0.getOperand(1), 1902 N0.getOperand(2)); 1903 AddToWorkList(N); 1904 CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load), 1905 Load.getValue(1)); 1906 return Load; 1907 } 1908 1909 return SDOperand(); 1910} 1911 1912SDOperand DAGCombiner::visitVBIT_CONVERT(SDNode *N) { 1913 SDOperand N0 = N->getOperand(0); 1914 MVT::ValueType VT = N->getValueType(0); 1915 1916 // If the input is a VBUILD_VECTOR with all constant elements, fold this now. 1917 // First check to see if this is all constant. 1918 if (N0.getOpcode() == ISD::VBUILD_VECTOR && N0.Val->hasOneUse() && 1919 VT == MVT::Vector) { 1920 bool isSimple = true; 1921 for (unsigned i = 0, e = N0.getNumOperands()-2; i != e; ++i) 1922 if (N0.getOperand(i).getOpcode() != ISD::UNDEF && 1923 N0.getOperand(i).getOpcode() != ISD::Constant && 1924 N0.getOperand(i).getOpcode() != ISD::ConstantFP) { 1925 isSimple = false; 1926 break; 1927 } 1928 1929 MVT::ValueType DestEltVT = cast<VTSDNode>(N->getOperand(2))->getVT(); 1930 if (isSimple && !MVT::isVector(DestEltVT)) { 1931 return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(N0.Val, DestEltVT); 1932 } 1933 } 1934 1935 return SDOperand(); 1936} 1937 1938/// ConstantFoldVBIT_CONVERTofVBUILD_VECTOR - We know that BV is a vbuild_vector 1939/// node with Constant, ConstantFP or Undef operands. DstEltVT indicates the 1940/// destination element value type. 1941SDOperand DAGCombiner:: 1942ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) { 1943 MVT::ValueType SrcEltVT = BV->getOperand(0).getValueType(); 1944 1945 // If this is already the right type, we're done. 1946 if (SrcEltVT == DstEltVT) return SDOperand(BV, 0); 1947 1948 unsigned SrcBitSize = MVT::getSizeInBits(SrcEltVT); 1949 unsigned DstBitSize = MVT::getSizeInBits(DstEltVT); 1950 1951 // If this is a conversion of N elements of one type to N elements of another 1952 // type, convert each element. This handles FP<->INT cases. 1953 if (SrcBitSize == DstBitSize) { 1954 SmallVector<SDOperand, 8> Ops; 1955 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) { 1956 Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i))); 1957 AddToWorkList(Ops.back().Val); 1958 } 1959 Ops.push_back(*(BV->op_end()-2)); // Add num elements. 1960 Ops.push_back(DAG.getValueType(DstEltVT)); 1961 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 1962 } 1963 1964 // Otherwise, we're growing or shrinking the elements. To avoid having to 1965 // handle annoying details of growing/shrinking FP values, we convert them to 1966 // int first. 1967 if (MVT::isFloatingPoint(SrcEltVT)) { 1968 // Convert the input float vector to a int vector where the elements are the 1969 // same sizes. 1970 assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!"); 1971 MVT::ValueType IntVT = SrcEltVT == MVT::f32 ? MVT::i32 : MVT::i64; 1972 BV = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, IntVT).Val; 1973 SrcEltVT = IntVT; 1974 } 1975 1976 // Now we know the input is an integer vector. If the output is a FP type, 1977 // convert to integer first, then to FP of the right size. 1978 if (MVT::isFloatingPoint(DstEltVT)) { 1979 assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!"); 1980 MVT::ValueType TmpVT = DstEltVT == MVT::f32 ? MVT::i32 : MVT::i64; 1981 SDNode *Tmp = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, TmpVT).Val; 1982 1983 // Next, convert to FP elements of the same size. 1984 return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(Tmp, DstEltVT); 1985 } 1986 1987 // Okay, we know the src/dst types are both integers of differing types. 1988 // Handling growing first. 1989 assert(MVT::isInteger(SrcEltVT) && MVT::isInteger(DstEltVT)); 1990 if (SrcBitSize < DstBitSize) { 1991 unsigned NumInputsPerOutput = DstBitSize/SrcBitSize; 1992 1993 SmallVector<SDOperand, 8> Ops; 1994 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; 1995 i += NumInputsPerOutput) { 1996 bool isLE = TLI.isLittleEndian(); 1997 uint64_t NewBits = 0; 1998 bool EltIsUndef = true; 1999 for (unsigned j = 0; j != NumInputsPerOutput; ++j) { 2000 // Shift the previously computed bits over. 2001 NewBits <<= SrcBitSize; 2002 SDOperand Op = BV->getOperand(i+ (isLE ? (NumInputsPerOutput-j-1) : j)); 2003 if (Op.getOpcode() == ISD::UNDEF) continue; 2004 EltIsUndef = false; 2005 2006 NewBits |= cast<ConstantSDNode>(Op)->getValue(); 2007 } 2008 2009 if (EltIsUndef) 2010 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 2011 else 2012 Ops.push_back(DAG.getConstant(NewBits, DstEltVT)); 2013 } 2014 2015 Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements. 2016 Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size. 2017 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2018 } 2019 2020 // Finally, this must be the case where we are shrinking elements: each input 2021 // turns into multiple outputs. 2022 unsigned NumOutputsPerInput = SrcBitSize/DstBitSize; 2023 SmallVector<SDOperand, 8> Ops; 2024 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) { 2025 if (BV->getOperand(i).getOpcode() == ISD::UNDEF) { 2026 for (unsigned j = 0; j != NumOutputsPerInput; ++j) 2027 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 2028 continue; 2029 } 2030 uint64_t OpVal = cast<ConstantSDNode>(BV->getOperand(i))->getValue(); 2031 2032 for (unsigned j = 0; j != NumOutputsPerInput; ++j) { 2033 unsigned ThisVal = OpVal & ((1ULL << DstBitSize)-1); 2034 OpVal >>= DstBitSize; 2035 Ops.push_back(DAG.getConstant(ThisVal, DstEltVT)); 2036 } 2037 2038 // For big endian targets, swap the order of the pieces of each element. 2039 if (!TLI.isLittleEndian()) 2040 std::reverse(Ops.end()-NumOutputsPerInput, Ops.end()); 2041 } 2042 Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements. 2043 Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size. 2044 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2045} 2046 2047 2048 2049SDOperand DAGCombiner::visitFADD(SDNode *N) { 2050 SDOperand N0 = N->getOperand(0); 2051 SDOperand N1 = N->getOperand(1); 2052 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2053 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2054 MVT::ValueType VT = N->getValueType(0); 2055 2056 // fold (fadd c1, c2) -> c1+c2 2057 if (N0CFP && N1CFP) 2058 return DAG.getNode(ISD::FADD, VT, N0, N1); 2059 // canonicalize constant to RHS 2060 if (N0CFP && !N1CFP) 2061 return DAG.getNode(ISD::FADD, VT, N1, N0); 2062 // fold (A + (-B)) -> A-B 2063 if (N1.getOpcode() == ISD::FNEG) 2064 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0)); 2065 // fold ((-A) + B) -> B-A 2066 if (N0.getOpcode() == ISD::FNEG) 2067 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0)); 2068 return SDOperand(); 2069} 2070 2071SDOperand DAGCombiner::visitFSUB(SDNode *N) { 2072 SDOperand N0 = N->getOperand(0); 2073 SDOperand N1 = N->getOperand(1); 2074 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2075 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2076 MVT::ValueType VT = N->getValueType(0); 2077 2078 // fold (fsub c1, c2) -> c1-c2 2079 if (N0CFP && N1CFP) 2080 return DAG.getNode(ISD::FSUB, VT, N0, N1); 2081 // fold (A-(-B)) -> A+B 2082 if (N1.getOpcode() == ISD::FNEG) 2083 return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0)); 2084 return SDOperand(); 2085} 2086 2087SDOperand DAGCombiner::visitFMUL(SDNode *N) { 2088 SDOperand N0 = N->getOperand(0); 2089 SDOperand N1 = N->getOperand(1); 2090 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2091 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2092 MVT::ValueType VT = N->getValueType(0); 2093 2094 // fold (fmul c1, c2) -> c1*c2 2095 if (N0CFP && N1CFP) 2096 return DAG.getNode(ISD::FMUL, VT, N0, N1); 2097 // canonicalize constant to RHS 2098 if (N0CFP && !N1CFP) 2099 return DAG.getNode(ISD::FMUL, VT, N1, N0); 2100 // fold (fmul X, 2.0) -> (fadd X, X) 2101 if (N1CFP && N1CFP->isExactlyValue(+2.0)) 2102 return DAG.getNode(ISD::FADD, VT, N0, N0); 2103 return SDOperand(); 2104} 2105 2106SDOperand DAGCombiner::visitFDIV(SDNode *N) { 2107 SDOperand N0 = N->getOperand(0); 2108 SDOperand N1 = N->getOperand(1); 2109 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2110 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2111 MVT::ValueType VT = N->getValueType(0); 2112 2113 // fold (fdiv c1, c2) -> c1/c2 2114 if (N0CFP && N1CFP) 2115 return DAG.getNode(ISD::FDIV, VT, N0, N1); 2116 return SDOperand(); 2117} 2118 2119SDOperand DAGCombiner::visitFREM(SDNode *N) { 2120 SDOperand N0 = N->getOperand(0); 2121 SDOperand N1 = N->getOperand(1); 2122 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2123 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2124 MVT::ValueType VT = N->getValueType(0); 2125 2126 // fold (frem c1, c2) -> fmod(c1,c2) 2127 if (N0CFP && N1CFP) 2128 return DAG.getNode(ISD::FREM, VT, N0, N1); 2129 return SDOperand(); 2130} 2131 2132SDOperand DAGCombiner::visitFCOPYSIGN(SDNode *N) { 2133 SDOperand N0 = N->getOperand(0); 2134 SDOperand N1 = N->getOperand(1); 2135 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2136 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2137 MVT::ValueType VT = N->getValueType(0); 2138 2139 if (N0CFP && N1CFP) // Constant fold 2140 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1); 2141 2142 if (N1CFP) { 2143 // copysign(x, c1) -> fabs(x) iff ispos(c1) 2144 // copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1) 2145 union { 2146 double d; 2147 int64_t i; 2148 } u; 2149 u.d = N1CFP->getValue(); 2150 if (u.i >= 0) 2151 return DAG.getNode(ISD::FABS, VT, N0); 2152 else 2153 return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0)); 2154 } 2155 2156 // copysign(fabs(x), y) -> copysign(x, y) 2157 // copysign(fneg(x), y) -> copysign(x, y) 2158 // copysign(copysign(x,z), y) -> copysign(x, y) 2159 if (N0.getOpcode() == ISD::FABS || N0.getOpcode() == ISD::FNEG || 2160 N0.getOpcode() == ISD::FCOPYSIGN) 2161 return DAG.getNode(ISD::FCOPYSIGN, VT, N0.getOperand(0), N1); 2162 2163 // copysign(x, abs(y)) -> abs(x) 2164 if (N1.getOpcode() == ISD::FABS) 2165 return DAG.getNode(ISD::FABS, VT, N0); 2166 2167 // copysign(x, copysign(y,z)) -> copysign(x, z) 2168 if (N1.getOpcode() == ISD::FCOPYSIGN) 2169 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(1)); 2170 2171 // copysign(x, fp_extend(y)) -> copysign(x, y) 2172 // copysign(x, fp_round(y)) -> copysign(x, y) 2173 if (N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND) 2174 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(0)); 2175 2176 return SDOperand(); 2177} 2178 2179 2180 2181SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 2182 SDOperand N0 = N->getOperand(0); 2183 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2184 MVT::ValueType VT = N->getValueType(0); 2185 2186 // fold (sint_to_fp c1) -> c1fp 2187 if (N0C) 2188 return DAG.getNode(ISD::SINT_TO_FP, VT, N0); 2189 return SDOperand(); 2190} 2191 2192SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 2193 SDOperand N0 = N->getOperand(0); 2194 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2195 MVT::ValueType VT = N->getValueType(0); 2196 2197 // fold (uint_to_fp c1) -> c1fp 2198 if (N0C) 2199 return DAG.getNode(ISD::UINT_TO_FP, VT, N0); 2200 return SDOperand(); 2201} 2202 2203SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 2204 SDOperand N0 = N->getOperand(0); 2205 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2206 MVT::ValueType VT = N->getValueType(0); 2207 2208 // fold (fp_to_sint c1fp) -> c1 2209 if (N0CFP) 2210 return DAG.getNode(ISD::FP_TO_SINT, VT, N0); 2211 return SDOperand(); 2212} 2213 2214SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 2215 SDOperand N0 = N->getOperand(0); 2216 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2217 MVT::ValueType VT = N->getValueType(0); 2218 2219 // fold (fp_to_uint c1fp) -> c1 2220 if (N0CFP) 2221 return DAG.getNode(ISD::FP_TO_UINT, VT, N0); 2222 return SDOperand(); 2223} 2224 2225SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 2226 SDOperand N0 = N->getOperand(0); 2227 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2228 MVT::ValueType VT = N->getValueType(0); 2229 2230 // fold (fp_round c1fp) -> c1fp 2231 if (N0CFP) 2232 return DAG.getNode(ISD::FP_ROUND, VT, N0); 2233 2234 // fold (fp_round (fp_extend x)) -> x 2235 if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType()) 2236 return N0.getOperand(0); 2237 2238 // fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y) 2239 if (N0.getOpcode() == ISD::FCOPYSIGN && N0.Val->hasOneUse()) { 2240 SDOperand Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0)); 2241 AddToWorkList(Tmp.Val); 2242 return DAG.getNode(ISD::FCOPYSIGN, VT, Tmp, N0.getOperand(1)); 2243 } 2244 2245 return SDOperand(); 2246} 2247 2248SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 2249 SDOperand N0 = N->getOperand(0); 2250 MVT::ValueType VT = N->getValueType(0); 2251 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 2252 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2253 2254 // fold (fp_round_inreg c1fp) -> c1fp 2255 if (N0CFP) { 2256 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 2257 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 2258 } 2259 return SDOperand(); 2260} 2261 2262SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 2263 SDOperand N0 = N->getOperand(0); 2264 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2265 MVT::ValueType VT = N->getValueType(0); 2266 2267 // fold (fp_extend c1fp) -> c1fp 2268 if (N0CFP) 2269 return DAG.getNode(ISD::FP_EXTEND, VT, N0); 2270 2271 // fold (fpext (load x)) -> (fpext (fpround (extload x))) 2272 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 2273 (!AfterLegalize||TLI.isOperationLegal(ISD::EXTLOAD, N0.getValueType()))) { 2274 SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, N0.getOperand(0), 2275 N0.getOperand(1), N0.getOperand(2), 2276 N0.getValueType()); 2277 CombineTo(N, ExtLoad); 2278 CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad), 2279 ExtLoad.getValue(1)); 2280 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2281 } 2282 2283 2284 return SDOperand(); 2285} 2286 2287SDOperand DAGCombiner::visitFNEG(SDNode *N) { 2288 SDOperand N0 = N->getOperand(0); 2289 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2290 MVT::ValueType VT = N->getValueType(0); 2291 2292 // fold (fneg c1) -> -c1 2293 if (N0CFP) 2294 return DAG.getNode(ISD::FNEG, VT, N0); 2295 // fold (fneg (sub x, y)) -> (sub y, x) 2296 if (N0.getOpcode() == ISD::SUB) 2297 return DAG.getNode(ISD::SUB, VT, N0.getOperand(1), N0.getOperand(0)); 2298 // fold (fneg (fneg x)) -> x 2299 if (N0.getOpcode() == ISD::FNEG) 2300 return N0.getOperand(0); 2301 return SDOperand(); 2302} 2303 2304SDOperand DAGCombiner::visitFABS(SDNode *N) { 2305 SDOperand N0 = N->getOperand(0); 2306 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2307 MVT::ValueType VT = N->getValueType(0); 2308 2309 // fold (fabs c1) -> fabs(c1) 2310 if (N0CFP) 2311 return DAG.getNode(ISD::FABS, VT, N0); 2312 // fold (fabs (fabs x)) -> (fabs x) 2313 if (N0.getOpcode() == ISD::FABS) 2314 return N->getOperand(0); 2315 // fold (fabs (fneg x)) -> (fabs x) 2316 // fold (fabs (fcopysign x, y)) -> (fabs x) 2317 if (N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FCOPYSIGN) 2318 return DAG.getNode(ISD::FABS, VT, N0.getOperand(0)); 2319 2320 return SDOperand(); 2321} 2322 2323SDOperand DAGCombiner::visitBRCOND(SDNode *N) { 2324 SDOperand Chain = N->getOperand(0); 2325 SDOperand N1 = N->getOperand(1); 2326 SDOperand N2 = N->getOperand(2); 2327 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2328 2329 // never taken branch, fold to chain 2330 if (N1C && N1C->isNullValue()) 2331 return Chain; 2332 // unconditional branch 2333 if (N1C && N1C->getValue() == 1) 2334 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 2335 // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal 2336 // on the target. 2337 if (N1.getOpcode() == ISD::SETCC && 2338 TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) { 2339 return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2), 2340 N1.getOperand(0), N1.getOperand(1), N2); 2341 } 2342 return SDOperand(); 2343} 2344 2345// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 2346// 2347SDOperand DAGCombiner::visitBR_CC(SDNode *N) { 2348 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 2349 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 2350 2351 // Use SimplifySetCC to simplify SETCC's. 2352 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false); 2353 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val); 2354 2355 // fold br_cc true, dest -> br dest (unconditional branch) 2356 if (SCCC && SCCC->getValue()) 2357 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 2358 N->getOperand(4)); 2359 // fold br_cc false, dest -> unconditional fall through 2360 if (SCCC && SCCC->isNullValue()) 2361 return N->getOperand(0); 2362 // fold to a simpler setcc 2363 if (Simp.Val && Simp.getOpcode() == ISD::SETCC) 2364 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 2365 Simp.getOperand(2), Simp.getOperand(0), 2366 Simp.getOperand(1), N->getOperand(4)); 2367 return SDOperand(); 2368} 2369 2370SDOperand DAGCombiner::visitLOAD(SDNode *N) { 2371 SDOperand Chain = N->getOperand(0); 2372 SDOperand Ptr = N->getOperand(1); 2373 SDOperand SrcValue = N->getOperand(2); 2374 2375 // If there are no uses of the loaded value, change uses of the chain value 2376 // into uses of the chain input (i.e. delete the dead load). 2377 if (N->hasNUsesOfValue(0, 0)) 2378 return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain); 2379 2380 // If this load is directly stored, replace the load value with the stored 2381 // value. 2382 // TODO: Handle store large -> read small portion. 2383 // TODO: Handle TRUNCSTORE/EXTLOAD 2384 if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr && 2385 Chain.getOperand(1).getValueType() == N->getValueType(0)) 2386 return CombineTo(N, Chain.getOperand(1), Chain); 2387 2388 return SDOperand(); 2389} 2390 2391/// visitXEXTLOAD - Handle EXTLOAD/ZEXTLOAD/SEXTLOAD. 2392SDOperand DAGCombiner::visitXEXTLOAD(SDNode *N) { 2393 SDOperand Chain = N->getOperand(0); 2394 SDOperand Ptr = N->getOperand(1); 2395 SDOperand SrcValue = N->getOperand(2); 2396 SDOperand EVT = N->getOperand(3); 2397 2398 // If there are no uses of the loaded value, change uses of the chain value 2399 // into uses of the chain input (i.e. delete the dead load). 2400 if (N->hasNUsesOfValue(0, 0)) 2401 return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain); 2402 2403 return SDOperand(); 2404} 2405 2406SDOperand DAGCombiner::visitSTORE(SDNode *N) { 2407 SDOperand Chain = N->getOperand(0); 2408 SDOperand Value = N->getOperand(1); 2409 SDOperand Ptr = N->getOperand(2); 2410 SDOperand SrcValue = N->getOperand(3); 2411 2412 // If this is a store that kills a previous store, remove the previous store. 2413 if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr && 2414 Chain.Val->hasOneUse() /* Avoid introducing DAG cycles */ && 2415 // Make sure that these stores are the same value type: 2416 // FIXME: we really care that the second store is >= size of the first. 2417 Value.getValueType() == Chain.getOperand(1).getValueType()) { 2418 // Create a new store of Value that replaces both stores. 2419 SDNode *PrevStore = Chain.Val; 2420 if (PrevStore->getOperand(1) == Value) // Same value multiply stored. 2421 return Chain; 2422 SDOperand NewStore = DAG.getNode(ISD::STORE, MVT::Other, 2423 PrevStore->getOperand(0), Value, Ptr, 2424 SrcValue); 2425 CombineTo(N, NewStore); // Nuke this store. 2426 CombineTo(PrevStore, NewStore); // Nuke the previous store. 2427 return SDOperand(N, 0); 2428 } 2429 2430 // If this is a store of a bit convert, store the input value. 2431 // FIXME: This needs to know that the resultant store does not need a 2432 // higher alignment than the original. 2433 if (0 && Value.getOpcode() == ISD::BIT_CONVERT) 2434 return DAG.getNode(ISD::STORE, MVT::Other, Chain, Value.getOperand(0), 2435 Ptr, SrcValue); 2436 2437 return SDOperand(); 2438} 2439 2440SDOperand DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) { 2441 SDOperand InVec = N->getOperand(0); 2442 SDOperand InVal = N->getOperand(1); 2443 SDOperand EltNo = N->getOperand(2); 2444 2445 // If the invec is a BUILD_VECTOR and if EltNo is a constant, build a new 2446 // vector with the inserted element. 2447 if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 2448 unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue(); 2449 SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end()); 2450 if (Elt < Ops.size()) 2451 Ops[Elt] = InVal; 2452 return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(), 2453 &Ops[0], Ops.size()); 2454 } 2455 2456 return SDOperand(); 2457} 2458 2459SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) { 2460 SDOperand InVec = N->getOperand(0); 2461 SDOperand InVal = N->getOperand(1); 2462 SDOperand EltNo = N->getOperand(2); 2463 SDOperand NumElts = N->getOperand(3); 2464 SDOperand EltType = N->getOperand(4); 2465 2466 // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new 2467 // vector with the inserted element. 2468 if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 2469 unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue(); 2470 SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end()); 2471 if (Elt < Ops.size()-2) 2472 Ops[Elt] = InVal; 2473 return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(), 2474 &Ops[0], Ops.size()); 2475 } 2476 2477 return SDOperand(); 2478} 2479 2480SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) { 2481 unsigned NumInScalars = N->getNumOperands()-2; 2482 SDOperand NumElts = N->getOperand(NumInScalars); 2483 SDOperand EltType = N->getOperand(NumInScalars+1); 2484 2485 // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT 2486 // operations. If so, and if the EXTRACT_ELT vector inputs come from at most 2487 // two distinct vectors, turn this into a shuffle node. 2488 SDOperand VecIn1, VecIn2; 2489 for (unsigned i = 0; i != NumInScalars; ++i) { 2490 // Ignore undef inputs. 2491 if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue; 2492 2493 // If this input is something other than a VEXTRACT_VECTOR_ELT with a 2494 // constant index, bail out. 2495 if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT || 2496 !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) { 2497 VecIn1 = VecIn2 = SDOperand(0, 0); 2498 break; 2499 } 2500 2501 // If the input vector type disagrees with the result of the vbuild_vector, 2502 // we can't make a shuffle. 2503 SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0); 2504 if (*(ExtractedFromVec.Val->op_end()-2) != NumElts || 2505 *(ExtractedFromVec.Val->op_end()-1) != EltType) { 2506 VecIn1 = VecIn2 = SDOperand(0, 0); 2507 break; 2508 } 2509 2510 // Otherwise, remember this. We allow up to two distinct input vectors. 2511 if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2) 2512 continue; 2513 2514 if (VecIn1.Val == 0) { 2515 VecIn1 = ExtractedFromVec; 2516 } else if (VecIn2.Val == 0) { 2517 VecIn2 = ExtractedFromVec; 2518 } else { 2519 // Too many inputs. 2520 VecIn1 = VecIn2 = SDOperand(0, 0); 2521 break; 2522 } 2523 } 2524 2525 // If everything is good, we can make a shuffle operation. 2526 if (VecIn1.Val) { 2527 SmallVector<SDOperand, 8> BuildVecIndices; 2528 for (unsigned i = 0; i != NumInScalars; ++i) { 2529 if (N->getOperand(i).getOpcode() == ISD::UNDEF) { 2530 BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, MVT::i32)); 2531 continue; 2532 } 2533 2534 SDOperand Extract = N->getOperand(i); 2535 2536 // If extracting from the first vector, just use the index directly. 2537 if (Extract.getOperand(0) == VecIn1) { 2538 BuildVecIndices.push_back(Extract.getOperand(1)); 2539 continue; 2540 } 2541 2542 // Otherwise, use InIdx + VecSize 2543 unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue(); 2544 BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, MVT::i32)); 2545 } 2546 2547 // Add count and size info. 2548 BuildVecIndices.push_back(NumElts); 2549 BuildVecIndices.push_back(DAG.getValueType(MVT::i32)); 2550 2551 // Return the new VVECTOR_SHUFFLE node. 2552 SDOperand Ops[5]; 2553 Ops[0] = VecIn1; 2554 if (VecIn2.Val) { 2555 Ops[1] = VecIn2; 2556 } else { 2557 // Use an undef vbuild_vector as input for the second operand. 2558 std::vector<SDOperand> UnOps(NumInScalars, 2559 DAG.getNode(ISD::UNDEF, 2560 cast<VTSDNode>(EltType)->getVT())); 2561 UnOps.push_back(NumElts); 2562 UnOps.push_back(EltType); 2563 Ops[1] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 2564 &UnOps[0], UnOps.size()); 2565 AddToWorkList(Ops[1].Val); 2566 } 2567 Ops[2] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 2568 &BuildVecIndices[0], BuildVecIndices.size()); 2569 Ops[3] = NumElts; 2570 Ops[4] = EltType; 2571 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops, 5); 2572 } 2573 2574 return SDOperand(); 2575} 2576 2577SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { 2578 SDOperand ShufMask = N->getOperand(2); 2579 unsigned NumElts = ShufMask.getNumOperands(); 2580 2581 // If the shuffle mask is an identity operation on the LHS, return the LHS. 2582 bool isIdentity = true; 2583 for (unsigned i = 0; i != NumElts; ++i) { 2584 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2585 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 2586 isIdentity = false; 2587 break; 2588 } 2589 } 2590 if (isIdentity) return N->getOperand(0); 2591 2592 // If the shuffle mask is an identity operation on the RHS, return the RHS. 2593 isIdentity = true; 2594 for (unsigned i = 0; i != NumElts; ++i) { 2595 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2596 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 2597 isIdentity = false; 2598 break; 2599 } 2600 } 2601 if (isIdentity) return N->getOperand(1); 2602 2603 // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not 2604 // needed at all. 2605 bool isUnary = true; 2606 bool isSplat = true; 2607 int VecNum = -1; 2608 unsigned BaseIdx = 0; 2609 for (unsigned i = 0; i != NumElts; ++i) 2610 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { 2611 unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue(); 2612 int V = (Idx < NumElts) ? 0 : 1; 2613 if (VecNum == -1) { 2614 VecNum = V; 2615 BaseIdx = Idx; 2616 } else { 2617 if (BaseIdx != Idx) 2618 isSplat = false; 2619 if (VecNum != V) { 2620 isUnary = false; 2621 break; 2622 } 2623 } 2624 } 2625 2626 SDOperand N0 = N->getOperand(0); 2627 SDOperand N1 = N->getOperand(1); 2628 // Normalize unary shuffle so the RHS is undef. 2629 if (isUnary && VecNum == 1) 2630 std::swap(N0, N1); 2631 2632 // If it is a splat, check if the argument vector is a build_vector with 2633 // all scalar elements the same. 2634 if (isSplat) { 2635 SDNode *V = N0.Val; 2636 if (V->getOpcode() == ISD::BIT_CONVERT) 2637 V = V->getOperand(0).Val; 2638 if (V->getOpcode() == ISD::BUILD_VECTOR) { 2639 unsigned NumElems = V->getNumOperands()-2; 2640 if (NumElems > BaseIdx) { 2641 SDOperand Base; 2642 bool AllSame = true; 2643 for (unsigned i = 0; i != NumElems; ++i) { 2644 if (V->getOperand(i).getOpcode() != ISD::UNDEF) { 2645 Base = V->getOperand(i); 2646 break; 2647 } 2648 } 2649 // Splat of <u, u, u, u>, return <u, u, u, u> 2650 if (!Base.Val) 2651 return N0; 2652 for (unsigned i = 0; i != NumElems; ++i) { 2653 if (V->getOperand(i).getOpcode() != ISD::UNDEF && 2654 V->getOperand(i) != Base) { 2655 AllSame = false; 2656 break; 2657 } 2658 } 2659 // Splat of <x, x, x, x>, return <x, x, x, x> 2660 if (AllSame) 2661 return N0; 2662 } 2663 } 2664 } 2665 2666 // If it is a unary or the LHS and the RHS are the same node, turn the RHS 2667 // into an undef. 2668 if (isUnary || N0 == N1) { 2669 if (N0.getOpcode() == ISD::UNDEF) 2670 return DAG.getNode(ISD::UNDEF, N->getValueType(0)); 2671 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 2672 // first operand. 2673 SmallVector<SDOperand, 8> MappedOps; 2674 for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) { 2675 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 2676 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 2677 MappedOps.push_back(ShufMask.getOperand(i)); 2678 } else { 2679 unsigned NewIdx = 2680 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 2681 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 2682 } 2683 } 2684 ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(), 2685 &MappedOps[0], MappedOps.size()); 2686 AddToWorkList(ShufMask.Val); 2687 return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0), 2688 N0, 2689 DAG.getNode(ISD::UNDEF, N->getValueType(0)), 2690 ShufMask); 2691 } 2692 2693 return SDOperand(); 2694} 2695 2696SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) { 2697 SDOperand ShufMask = N->getOperand(2); 2698 unsigned NumElts = ShufMask.getNumOperands()-2; 2699 2700 // If the shuffle mask is an identity operation on the LHS, return the LHS. 2701 bool isIdentity = true; 2702 for (unsigned i = 0; i != NumElts; ++i) { 2703 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2704 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 2705 isIdentity = false; 2706 break; 2707 } 2708 } 2709 if (isIdentity) return N->getOperand(0); 2710 2711 // If the shuffle mask is an identity operation on the RHS, return the RHS. 2712 isIdentity = true; 2713 for (unsigned i = 0; i != NumElts; ++i) { 2714 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2715 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 2716 isIdentity = false; 2717 break; 2718 } 2719 } 2720 if (isIdentity) return N->getOperand(1); 2721 2722 // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not 2723 // needed at all. 2724 bool isUnary = true; 2725 bool isSplat = true; 2726 int VecNum = -1; 2727 unsigned BaseIdx = 0; 2728 for (unsigned i = 0; i != NumElts; ++i) 2729 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { 2730 unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue(); 2731 int V = (Idx < NumElts) ? 0 : 1; 2732 if (VecNum == -1) { 2733 VecNum = V; 2734 BaseIdx = Idx; 2735 } else { 2736 if (BaseIdx != Idx) 2737 isSplat = false; 2738 if (VecNum != V) { 2739 isUnary = false; 2740 break; 2741 } 2742 } 2743 } 2744 2745 SDOperand N0 = N->getOperand(0); 2746 SDOperand N1 = N->getOperand(1); 2747 // Normalize unary shuffle so the RHS is undef. 2748 if (isUnary && VecNum == 1) 2749 std::swap(N0, N1); 2750 2751 // If it is a splat, check if the argument vector is a build_vector with 2752 // all scalar elements the same. 2753 if (isSplat) { 2754 SDNode *V = N0.Val; 2755 if (V->getOpcode() == ISD::VBIT_CONVERT) 2756 V = V->getOperand(0).Val; 2757 if (V->getOpcode() == ISD::VBUILD_VECTOR) { 2758 unsigned NumElems = V->getNumOperands()-2; 2759 if (NumElems > BaseIdx) { 2760 SDOperand Base; 2761 bool AllSame = true; 2762 for (unsigned i = 0; i != NumElems; ++i) { 2763 if (V->getOperand(i).getOpcode() != ISD::UNDEF) { 2764 Base = V->getOperand(i); 2765 break; 2766 } 2767 } 2768 // Splat of <u, u, u, u>, return <u, u, u, u> 2769 if (!Base.Val) 2770 return N0; 2771 for (unsigned i = 0; i != NumElems; ++i) { 2772 if (V->getOperand(i).getOpcode() != ISD::UNDEF && 2773 V->getOperand(i) != Base) { 2774 AllSame = false; 2775 break; 2776 } 2777 } 2778 // Splat of <x, x, x, x>, return <x, x, x, x> 2779 if (AllSame) 2780 return N0; 2781 } 2782 } 2783 } 2784 2785 // If it is a unary or the LHS and the RHS are the same node, turn the RHS 2786 // into an undef. 2787 if (isUnary || N0 == N1) { 2788 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 2789 // first operand. 2790 SmallVector<SDOperand, 8> MappedOps; 2791 for (unsigned i = 0; i != NumElts; ++i) { 2792 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 2793 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 2794 MappedOps.push_back(ShufMask.getOperand(i)); 2795 } else { 2796 unsigned NewIdx = 2797 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 2798 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 2799 } 2800 } 2801 // Add the type/#elts values. 2802 MappedOps.push_back(ShufMask.getOperand(NumElts)); 2803 MappedOps.push_back(ShufMask.getOperand(NumElts+1)); 2804 2805 ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(), 2806 &MappedOps[0], MappedOps.size()); 2807 AddToWorkList(ShufMask.Val); 2808 2809 // Build the undef vector. 2810 SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType()); 2811 for (unsigned i = 0; i != NumElts; ++i) 2812 MappedOps[i] = UDVal; 2813 MappedOps[NumElts ] = *(N0.Val->op_end()-2); 2814 MappedOps[NumElts+1] = *(N0.Val->op_end()-1); 2815 UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 2816 &MappedOps[0], MappedOps.size()); 2817 2818 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 2819 N0, UDVal, ShufMask, 2820 MappedOps[NumElts], MappedOps[NumElts+1]); 2821 } 2822 2823 return SDOperand(); 2824} 2825 2826/// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform 2827/// a VAND to a vector_shuffle with the destination vector and a zero vector. 2828/// e.g. VAND V, <0xffffffff, 0, 0xffffffff, 0>. ==> 2829/// vector_shuffle V, Zero, <0, 4, 2, 4> 2830SDOperand DAGCombiner::XformToShuffleWithZero(SDNode *N) { 2831 SDOperand LHS = N->getOperand(0); 2832 SDOperand RHS = N->getOperand(1); 2833 if (N->getOpcode() == ISD::VAND) { 2834 SDOperand DstVecSize = *(LHS.Val->op_end()-2); 2835 SDOperand DstVecEVT = *(LHS.Val->op_end()-1); 2836 if (RHS.getOpcode() == ISD::VBIT_CONVERT) 2837 RHS = RHS.getOperand(0); 2838 if (RHS.getOpcode() == ISD::VBUILD_VECTOR) { 2839 std::vector<SDOperand> IdxOps; 2840 unsigned NumOps = RHS.getNumOperands(); 2841 unsigned NumElts = NumOps-2; 2842 MVT::ValueType EVT = cast<VTSDNode>(RHS.getOperand(NumOps-1))->getVT(); 2843 for (unsigned i = 0; i != NumElts; ++i) { 2844 SDOperand Elt = RHS.getOperand(i); 2845 if (!isa<ConstantSDNode>(Elt)) 2846 return SDOperand(); 2847 else if (cast<ConstantSDNode>(Elt)->isAllOnesValue()) 2848 IdxOps.push_back(DAG.getConstant(i, EVT)); 2849 else if (cast<ConstantSDNode>(Elt)->isNullValue()) 2850 IdxOps.push_back(DAG.getConstant(NumElts, EVT)); 2851 else 2852 return SDOperand(); 2853 } 2854 2855 // Let's see if the target supports this vector_shuffle. 2856 if (!TLI.isVectorClearMaskLegal(IdxOps, EVT, DAG)) 2857 return SDOperand(); 2858 2859 // Return the new VVECTOR_SHUFFLE node. 2860 SDOperand NumEltsNode = DAG.getConstant(NumElts, MVT::i32); 2861 SDOperand EVTNode = DAG.getValueType(EVT); 2862 std::vector<SDOperand> Ops; 2863 LHS = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, LHS, NumEltsNode, EVTNode); 2864 Ops.push_back(LHS); 2865 AddToWorkList(LHS.Val); 2866 std::vector<SDOperand> ZeroOps(NumElts, DAG.getConstant(0, EVT)); 2867 ZeroOps.push_back(NumEltsNode); 2868 ZeroOps.push_back(EVTNode); 2869 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 2870 &ZeroOps[0], ZeroOps.size())); 2871 IdxOps.push_back(NumEltsNode); 2872 IdxOps.push_back(EVTNode); 2873 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 2874 &IdxOps[0], IdxOps.size())); 2875 Ops.push_back(NumEltsNode); 2876 Ops.push_back(EVTNode); 2877 SDOperand Result = DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 2878 &Ops[0], Ops.size()); 2879 if (NumEltsNode != DstVecSize || EVTNode != DstVecEVT) { 2880 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 2881 DstVecSize, DstVecEVT); 2882 } 2883 return Result; 2884 } 2885 } 2886 return SDOperand(); 2887} 2888 2889/// visitVBinOp - Visit a binary vector operation, like VADD. IntOp indicates 2890/// the scalar operation of the vop if it is operating on an integer vector 2891/// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD). 2892SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp, 2893 ISD::NodeType FPOp) { 2894 MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT(); 2895 ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp; 2896 SDOperand LHS = N->getOperand(0); 2897 SDOperand RHS = N->getOperand(1); 2898 SDOperand Shuffle = XformToShuffleWithZero(N); 2899 if (Shuffle.Val) return Shuffle; 2900 2901 // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold 2902 // this operation. 2903 if (LHS.getOpcode() == ISD::VBUILD_VECTOR && 2904 RHS.getOpcode() == ISD::VBUILD_VECTOR) { 2905 SmallVector<SDOperand, 8> Ops; 2906 for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) { 2907 SDOperand LHSOp = LHS.getOperand(i); 2908 SDOperand RHSOp = RHS.getOperand(i); 2909 // If these two elements can't be folded, bail out. 2910 if ((LHSOp.getOpcode() != ISD::UNDEF && 2911 LHSOp.getOpcode() != ISD::Constant && 2912 LHSOp.getOpcode() != ISD::ConstantFP) || 2913 (RHSOp.getOpcode() != ISD::UNDEF && 2914 RHSOp.getOpcode() != ISD::Constant && 2915 RHSOp.getOpcode() != ISD::ConstantFP)) 2916 break; 2917 // Can't fold divide by zero. 2918 if (N->getOpcode() == ISD::VSDIV || N->getOpcode() == ISD::VUDIV) { 2919 if ((RHSOp.getOpcode() == ISD::Constant && 2920 cast<ConstantSDNode>(RHSOp.Val)->isNullValue()) || 2921 (RHSOp.getOpcode() == ISD::ConstantFP && 2922 !cast<ConstantFPSDNode>(RHSOp.Val)->getValue())) 2923 break; 2924 } 2925 Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp)); 2926 AddToWorkList(Ops.back().Val); 2927 assert((Ops.back().getOpcode() == ISD::UNDEF || 2928 Ops.back().getOpcode() == ISD::Constant || 2929 Ops.back().getOpcode() == ISD::ConstantFP) && 2930 "Scalar binop didn't fold!"); 2931 } 2932 2933 if (Ops.size() == LHS.getNumOperands()-2) { 2934 Ops.push_back(*(LHS.Val->op_end()-2)); 2935 Ops.push_back(*(LHS.Val->op_end()-1)); 2936 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2937 } 2938 } 2939 2940 return SDOperand(); 2941} 2942 2943SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 2944 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 2945 2946 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 2947 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 2948 // If we got a simplified select_cc node back from SimplifySelectCC, then 2949 // break it down into a new SETCC node, and a new SELECT node, and then return 2950 // the SELECT node, since we were called with a SELECT node. 2951 if (SCC.Val) { 2952 // Check to see if we got a select_cc back (to turn into setcc/select). 2953 // Otherwise, just return whatever node we got back, like fabs. 2954 if (SCC.getOpcode() == ISD::SELECT_CC) { 2955 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 2956 SCC.getOperand(0), SCC.getOperand(1), 2957 SCC.getOperand(4)); 2958 AddToWorkList(SETCC.Val); 2959 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 2960 SCC.getOperand(3), SETCC); 2961 } 2962 return SCC; 2963 } 2964 return SDOperand(); 2965} 2966 2967/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS 2968/// are the two values being selected between, see if we can simplify the 2969/// select. Callers of this should assume that TheSelect is deleted if this 2970/// returns true. As such, they should return the appropriate thing (e.g. the 2971/// node) back to the top-level of the DAG combiner loop to avoid it being 2972/// looked at. 2973/// 2974bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS, 2975 SDOperand RHS) { 2976 2977 // If this is a select from two identical things, try to pull the operation 2978 // through the select. 2979 if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){ 2980#if 0 2981 std::cerr << "SELECT: ["; LHS.Val->dump(); 2982 std::cerr << "] ["; RHS.Val->dump(); 2983 std::cerr << "]\n"; 2984#endif 2985 2986 // If this is a load and the token chain is identical, replace the select 2987 // of two loads with a load through a select of the address to load from. 2988 // This triggers in things like "select bool X, 10.0, 123.0" after the FP 2989 // constants have been dropped into the constant pool. 2990 if ((LHS.getOpcode() == ISD::LOAD || 2991 LHS.getOpcode() == ISD::EXTLOAD || 2992 LHS.getOpcode() == ISD::ZEXTLOAD || 2993 LHS.getOpcode() == ISD::SEXTLOAD) && 2994 // Token chains must be identical. 2995 LHS.getOperand(0) == RHS.getOperand(0) && 2996 // If this is an EXTLOAD, the VT's must match. 2997 (LHS.getOpcode() == ISD::LOAD || 2998 LHS.getOperand(3) == RHS.getOperand(3))) { 2999 // FIXME: this conflates two src values, discarding one. This is not 3000 // the right thing to do, but nothing uses srcvalues now. When they do, 3001 // turn SrcValue into a list of locations. 3002 SDOperand Addr; 3003 if (TheSelect->getOpcode() == ISD::SELECT) 3004 Addr = DAG.getNode(ISD::SELECT, LHS.getOperand(1).getValueType(), 3005 TheSelect->getOperand(0), LHS.getOperand(1), 3006 RHS.getOperand(1)); 3007 else 3008 Addr = DAG.getNode(ISD::SELECT_CC, LHS.getOperand(1).getValueType(), 3009 TheSelect->getOperand(0), 3010 TheSelect->getOperand(1), 3011 LHS.getOperand(1), RHS.getOperand(1), 3012 TheSelect->getOperand(4)); 3013 3014 SDOperand Load; 3015 if (LHS.getOpcode() == ISD::LOAD) 3016 Load = DAG.getLoad(TheSelect->getValueType(0), LHS.getOperand(0), 3017 Addr, LHS.getOperand(2)); 3018 else 3019 Load = DAG.getExtLoad(LHS.getOpcode(), TheSelect->getValueType(0), 3020 LHS.getOperand(0), Addr, LHS.getOperand(2), 3021 cast<VTSDNode>(LHS.getOperand(3))->getVT()); 3022 // Users of the select now use the result of the load. 3023 CombineTo(TheSelect, Load); 3024 3025 // Users of the old loads now use the new load's chain. We know the 3026 // old-load value is dead now. 3027 CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1)); 3028 CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1)); 3029 return true; 3030 } 3031 } 3032 3033 return false; 3034} 3035 3036SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 3037 SDOperand N2, SDOperand N3, 3038 ISD::CondCode CC) { 3039 3040 MVT::ValueType VT = N2.getValueType(); 3041 //ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 3042 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 3043 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 3044 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 3045 3046 // Determine if the condition we're dealing with is constant 3047 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 3048 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 3049 3050 // fold select_cc true, x, y -> x 3051 if (SCCC && SCCC->getValue()) 3052 return N2; 3053 // fold select_cc false, x, y -> y 3054 if (SCCC && SCCC->getValue() == 0) 3055 return N3; 3056 3057 // Check to see if we can simplify the select into an fabs node 3058 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 3059 // Allow either -0.0 or 0.0 3060 if (CFP->getValue() == 0.0) { 3061 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 3062 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 3063 N0 == N2 && N3.getOpcode() == ISD::FNEG && 3064 N2 == N3.getOperand(0)) 3065 return DAG.getNode(ISD::FABS, VT, N0); 3066 3067 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 3068 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 3069 N0 == N3 && N2.getOpcode() == ISD::FNEG && 3070 N2.getOperand(0) == N3) 3071 return DAG.getNode(ISD::FABS, VT, N3); 3072 } 3073 } 3074 3075 // Check to see if we can perform the "gzip trick", transforming 3076 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 3077 if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() && 3078 MVT::isInteger(N0.getValueType()) && 3079 MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) { 3080 MVT::ValueType XType = N0.getValueType(); 3081 MVT::ValueType AType = N2.getValueType(); 3082 if (XType >= AType) { 3083 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 3084 // single-bit constant. 3085 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) { 3086 unsigned ShCtV = Log2_64(N2C->getValue()); 3087 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1; 3088 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 3089 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 3090 AddToWorkList(Shift.Val); 3091 if (XType > AType) { 3092 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 3093 AddToWorkList(Shift.Val); 3094 } 3095 return DAG.getNode(ISD::AND, AType, Shift, N2); 3096 } 3097 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 3098 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3099 TLI.getShiftAmountTy())); 3100 AddToWorkList(Shift.Val); 3101 if (XType > AType) { 3102 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 3103 AddToWorkList(Shift.Val); 3104 } 3105 return DAG.getNode(ISD::AND, AType, Shift, N2); 3106 } 3107 } 3108 3109 // fold select C, 16, 0 -> shl C, 4 3110 if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) && 3111 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) { 3112 // Get a SetCC of the condition 3113 // FIXME: Should probably make sure that setcc is legal if we ever have a 3114 // target where it isn't. 3115 SDOperand Temp, SCC; 3116 // cast from setcc result type to select result type 3117 if (AfterLegalize) { 3118 SCC = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 3119 Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType()); 3120 } else { 3121 SCC = DAG.getSetCC(MVT::i1, N0, N1, CC); 3122 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 3123 } 3124 AddToWorkList(SCC.Val); 3125 AddToWorkList(Temp.Val); 3126 // shl setcc result by log2 n2c 3127 return DAG.getNode(ISD::SHL, N2.getValueType(), Temp, 3128 DAG.getConstant(Log2_64(N2C->getValue()), 3129 TLI.getShiftAmountTy())); 3130 } 3131 3132 // Check to see if this is the equivalent of setcc 3133 // FIXME: Turn all of these into setcc if setcc if setcc is legal 3134 // otherwise, go ahead with the folds. 3135 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) { 3136 MVT::ValueType XType = N0.getValueType(); 3137 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) { 3138 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 3139 if (Res.getValueType() != VT) 3140 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 3141 return Res; 3142 } 3143 3144 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 3145 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 3146 TLI.isOperationLegal(ISD::CTLZ, XType)) { 3147 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 3148 return DAG.getNode(ISD::SRL, XType, Ctlz, 3149 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)), 3150 TLI.getShiftAmountTy())); 3151 } 3152 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 3153 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 3154 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 3155 N0); 3156 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 3157 DAG.getConstant(~0ULL, XType)); 3158 return DAG.getNode(ISD::SRL, XType, 3159 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 3160 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3161 TLI.getShiftAmountTy())); 3162 } 3163 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 3164 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 3165 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0, 3166 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3167 TLI.getShiftAmountTy())); 3168 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 3169 } 3170 } 3171 3172 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 3173 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 3174 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 3175 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) { 3176 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) { 3177 MVT::ValueType XType = N0.getValueType(); 3178 if (SubC->isNullValue() && MVT::isInteger(XType)) { 3179 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 3180 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3181 TLI.getShiftAmountTy())); 3182 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 3183 AddToWorkList(Shift.Val); 3184 AddToWorkList(Add.Val); 3185 return DAG.getNode(ISD::XOR, XType, Add, Shift); 3186 } 3187 } 3188 } 3189 3190 return SDOperand(); 3191} 3192 3193SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 3194 SDOperand N1, ISD::CondCode Cond, 3195 bool foldBooleans) { 3196 // These setcc operations always fold. 3197 switch (Cond) { 3198 default: break; 3199 case ISD::SETFALSE: 3200 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 3201 case ISD::SETTRUE: 3202 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 3203 } 3204 3205 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 3206 uint64_t C1 = N1C->getValue(); 3207 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) { 3208 uint64_t C0 = N0C->getValue(); 3209 3210 // Sign extend the operands if required 3211 if (ISD::isSignedIntSetCC(Cond)) { 3212 C0 = N0C->getSignExtended(); 3213 C1 = N1C->getSignExtended(); 3214 } 3215 3216 switch (Cond) { 3217 default: assert(0 && "Unknown integer setcc!"); 3218 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 3219 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 3220 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT); 3221 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT); 3222 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT); 3223 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT); 3224 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT); 3225 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT); 3226 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT); 3227 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT); 3228 } 3229 } else { 3230 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 3231 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 3232 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 3233 3234 // If the comparison constant has bits in the upper part, the 3235 // zero-extended value could never match. 3236 if (C1 & (~0ULL << InSize)) { 3237 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 3238 switch (Cond) { 3239 case ISD::SETUGT: 3240 case ISD::SETUGE: 3241 case ISD::SETEQ: return DAG.getConstant(0, VT); 3242 case ISD::SETULT: 3243 case ISD::SETULE: 3244 case ISD::SETNE: return DAG.getConstant(1, VT); 3245 case ISD::SETGT: 3246 case ISD::SETGE: 3247 // True if the sign bit of C1 is set. 3248 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 3249 case ISD::SETLT: 3250 case ISD::SETLE: 3251 // True if the sign bit of C1 isn't set. 3252 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 3253 default: 3254 break; 3255 } 3256 } 3257 3258 // Otherwise, we can perform the comparison with the low bits. 3259 switch (Cond) { 3260 case ISD::SETEQ: 3261 case ISD::SETNE: 3262 case ISD::SETUGT: 3263 case ISD::SETUGE: 3264 case ISD::SETULT: 3265 case ISD::SETULE: 3266 return DAG.getSetCC(VT, N0.getOperand(0), 3267 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 3268 Cond); 3269 default: 3270 break; // todo, be more careful with signed comparisons 3271 } 3272 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 3273 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 3274 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 3275 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 3276 MVT::ValueType ExtDstTy = N0.getValueType(); 3277 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 3278 3279 // If the extended part has any inconsistent bits, it cannot ever 3280 // compare equal. In other words, they have to be all ones or all 3281 // zeros. 3282 uint64_t ExtBits = 3283 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 3284 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 3285 return DAG.getConstant(Cond == ISD::SETNE, VT); 3286 3287 SDOperand ZextOp; 3288 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 3289 if (Op0Ty == ExtSrcTy) { 3290 ZextOp = N0.getOperand(0); 3291 } else { 3292 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 3293 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 3294 DAG.getConstant(Imm, Op0Ty)); 3295 } 3296 AddToWorkList(ZextOp.Val); 3297 // Otherwise, make this a use of a zext. 3298 return DAG.getSetCC(VT, ZextOp, 3299 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 3300 ExtDstTy), 3301 Cond); 3302 } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) && 3303 (Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3304 (N0.getOpcode() == ISD::XOR || 3305 (N0.getOpcode() == ISD::AND && 3306 N0.getOperand(0).getOpcode() == ISD::XOR && 3307 N0.getOperand(1) == N0.getOperand(0).getOperand(1))) && 3308 isa<ConstantSDNode>(N0.getOperand(1)) && 3309 cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) { 3310 // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We can 3311 // only do this if the top bits are known zero. 3312 if (TLI.MaskedValueIsZero(N1, 3313 MVT::getIntVTBitMask(N0.getValueType())-1)) { 3314 // Okay, get the un-inverted input value. 3315 SDOperand Val; 3316 if (N0.getOpcode() == ISD::XOR) 3317 Val = N0.getOperand(0); 3318 else { 3319 assert(N0.getOpcode() == ISD::AND && 3320 N0.getOperand(0).getOpcode() == ISD::XOR); 3321 // ((X^1)&1)^1 -> X & 1 3322 Val = DAG.getNode(ISD::AND, N0.getValueType(), 3323 N0.getOperand(0).getOperand(0), N0.getOperand(1)); 3324 } 3325 return DAG.getSetCC(VT, Val, N1, 3326 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ); 3327 } 3328 } 3329 3330 uint64_t MinVal, MaxVal; 3331 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 3332 if (ISD::isSignedIntSetCC(Cond)) { 3333 MinVal = 1ULL << (OperandBitSize-1); 3334 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 3335 MaxVal = ~0ULL >> (65-OperandBitSize); 3336 else 3337 MaxVal = 0; 3338 } else { 3339 MinVal = 0; 3340 MaxVal = ~0ULL >> (64-OperandBitSize); 3341 } 3342 3343 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 3344 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 3345 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 3346 --C1; // X >= C0 --> X > (C0-1) 3347 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 3348 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 3349 } 3350 3351 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 3352 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 3353 ++C1; // X <= C0 --> X < (C0+1) 3354 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 3355 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 3356 } 3357 3358 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 3359 return DAG.getConstant(0, VT); // X < MIN --> false 3360 3361 // Canonicalize setgt X, Min --> setne X, Min 3362 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 3363 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 3364 // Canonicalize setlt X, Max --> setne X, Max 3365 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal) 3366 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 3367 3368 // If we have setult X, 1, turn it into seteq X, 0 3369 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 3370 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 3371 ISD::SETEQ); 3372 // If we have setugt X, Max-1, turn it into seteq X, Max 3373 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 3374 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 3375 ISD::SETEQ); 3376 3377 // If we have "setcc X, C0", check to see if we can shrink the immediate 3378 // by changing cc. 3379 3380 // SETUGT X, SINTMAX -> SETLT X, 0 3381 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 3382 C1 == (~0ULL >> (65-OperandBitSize))) 3383 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 3384 ISD::SETLT); 3385 3386 // FIXME: Implement the rest of these. 3387 3388 // Fold bit comparisons when we can. 3389 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3390 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 3391 if (ConstantSDNode *AndRHS = 3392 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 3393 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 3394 // Perform the xform if the AND RHS is a single bit. 3395 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 3396 return DAG.getNode(ISD::SRL, VT, N0, 3397 DAG.getConstant(Log2_64(AndRHS->getValue()), 3398 TLI.getShiftAmountTy())); 3399 } 3400 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 3401 // (X & 8) == 8 --> (X & 8) >> 3 3402 // Perform the xform if C1 is a single bit. 3403 if ((C1 & (C1-1)) == 0) { 3404 return DAG.getNode(ISD::SRL, VT, N0, 3405 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 3406 } 3407 } 3408 } 3409 } 3410 } else if (isa<ConstantSDNode>(N0.Val)) { 3411 // Ensure that the constant occurs on the RHS. 3412 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 3413 } 3414 3415 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val)) 3416 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) { 3417 double C0 = N0C->getValue(), C1 = N1C->getValue(); 3418 3419 switch (Cond) { 3420 default: break; // FIXME: Implement the rest of these! 3421 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 3422 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 3423 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT); 3424 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT); 3425 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT); 3426 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT); 3427 } 3428 } else { 3429 // Ensure that the constant occurs on the RHS. 3430 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 3431 } 3432 3433 if (N0 == N1) { 3434 // We can always fold X == Y for integer setcc's. 3435 if (MVT::isInteger(N0.getValueType())) 3436 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 3437 unsigned UOF = ISD::getUnorderedFlavor(Cond); 3438 if (UOF == 2) // FP operators that are undefined on NaNs. 3439 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 3440 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 3441 return DAG.getConstant(UOF, VT); 3442 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 3443 // if it is not already. 3444 ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO; 3445 if (NewCond != Cond) 3446 return DAG.getSetCC(VT, N0, N1, NewCond); 3447 } 3448 3449 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3450 MVT::isInteger(N0.getValueType())) { 3451 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 3452 N0.getOpcode() == ISD::XOR) { 3453 // Simplify (X+Y) == (X+Z) --> Y == Z 3454 if (N0.getOpcode() == N1.getOpcode()) { 3455 if (N0.getOperand(0) == N1.getOperand(0)) 3456 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 3457 if (N0.getOperand(1) == N1.getOperand(1)) 3458 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 3459 if (isCommutativeBinOp(N0.getOpcode())) { 3460 // If X op Y == Y op X, try other combinations. 3461 if (N0.getOperand(0) == N1.getOperand(1)) 3462 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 3463 if (N0.getOperand(1) == N1.getOperand(0)) 3464 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond); 3465 } 3466 } 3467 3468 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 3469 if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 3470 // Turn (X+C1) == C2 --> X == C2-C1 3471 if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) { 3472 return DAG.getSetCC(VT, N0.getOperand(0), 3473 DAG.getConstant(RHSC->getValue()-LHSR->getValue(), 3474 N0.getValueType()), Cond); 3475 } 3476 3477 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. 3478 if (N0.getOpcode() == ISD::XOR) 3479 // If we know that all of the inverted bits are zero, don't bother 3480 // performing the inversion. 3481 if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue())) 3482 return DAG.getSetCC(VT, N0.getOperand(0), 3483 DAG.getConstant(LHSR->getValue()^RHSC->getValue(), 3484 N0.getValueType()), Cond); 3485 } 3486 3487 // Turn (C1-X) == C2 --> X == C1-C2 3488 if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) { 3489 if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) { 3490 return DAG.getSetCC(VT, N0.getOperand(1), 3491 DAG.getConstant(SUBC->getValue()-RHSC->getValue(), 3492 N0.getValueType()), Cond); 3493 } 3494 } 3495 } 3496 3497 // Simplify (X+Z) == X --> Z == 0 3498 if (N0.getOperand(0) == N1) 3499 return DAG.getSetCC(VT, N0.getOperand(1), 3500 DAG.getConstant(0, N0.getValueType()), Cond); 3501 if (N0.getOperand(1) == N1) { 3502 if (isCommutativeBinOp(N0.getOpcode())) 3503 return DAG.getSetCC(VT, N0.getOperand(0), 3504 DAG.getConstant(0, N0.getValueType()), Cond); 3505 else { 3506 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 3507 // (Z-X) == X --> Z == X<<1 3508 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 3509 N1, 3510 DAG.getConstant(1,TLI.getShiftAmountTy())); 3511 AddToWorkList(SH.Val); 3512 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 3513 } 3514 } 3515 } 3516 3517 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 3518 N1.getOpcode() == ISD::XOR) { 3519 // Simplify X == (X+Z) --> Z == 0 3520 if (N1.getOperand(0) == N0) { 3521 return DAG.getSetCC(VT, N1.getOperand(1), 3522 DAG.getConstant(0, N1.getValueType()), Cond); 3523 } else if (N1.getOperand(1) == N0) { 3524 if (isCommutativeBinOp(N1.getOpcode())) { 3525 return DAG.getSetCC(VT, N1.getOperand(0), 3526 DAG.getConstant(0, N1.getValueType()), Cond); 3527 } else { 3528 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 3529 // X == (Z-X) --> X<<1 == Z 3530 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 3531 DAG.getConstant(1,TLI.getShiftAmountTy())); 3532 AddToWorkList(SH.Val); 3533 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 3534 } 3535 } 3536 } 3537 } 3538 3539 // Fold away ALL boolean setcc's. 3540 SDOperand Temp; 3541 if (N0.getValueType() == MVT::i1 && foldBooleans) { 3542 switch (Cond) { 3543 default: assert(0 && "Unknown integer setcc!"); 3544 case ISD::SETEQ: // X == Y -> (X^Y)^1 3545 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 3546 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 3547 AddToWorkList(Temp.Val); 3548 break; 3549 case ISD::SETNE: // X != Y --> (X^Y) 3550 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 3551 break; 3552 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 3553 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 3554 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 3555 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 3556 AddToWorkList(Temp.Val); 3557 break; 3558 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 3559 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 3560 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 3561 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 3562 AddToWorkList(Temp.Val); 3563 break; 3564 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 3565 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 3566 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 3567 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 3568 AddToWorkList(Temp.Val); 3569 break; 3570 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 3571 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 3572 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 3573 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 3574 break; 3575 } 3576 if (VT != MVT::i1) { 3577 AddToWorkList(N0.Val); 3578 // FIXME: If running after legalize, we probably can't do this. 3579 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 3580 } 3581 return N0; 3582 } 3583 3584 // Could not fold it. 3585 return SDOperand(); 3586} 3587 3588/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 3589/// return a DAG expression to select that will generate the same value by 3590/// multiplying by a magic number. See: 3591/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 3592SDOperand DAGCombiner::BuildSDIV(SDNode *N) { 3593 std::vector<SDNode*> Built; 3594 SDOperand S = TLI.BuildSDIV(N, DAG, &Built); 3595 3596 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 3597 ii != ee; ++ii) 3598 AddToWorkList(*ii); 3599 return S; 3600} 3601 3602/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 3603/// return a DAG expression to select that will generate the same value by 3604/// multiplying by a magic number. See: 3605/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 3606SDOperand DAGCombiner::BuildUDIV(SDNode *N) { 3607 std::vector<SDNode*> Built; 3608 SDOperand S = TLI.BuildUDIV(N, DAG, &Built); 3609 3610 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 3611 ii != ee; ++ii) 3612 AddToWorkList(*ii); 3613 return S; 3614} 3615 3616// SelectionDAG::Combine - This is the entry point for the file. 3617// 3618void SelectionDAG::Combine(bool RunningAfterLegalize) { 3619 /// run - This is the main entry point to this class. 3620 /// 3621 DAGCombiner(*this).Run(RunningAfterLegalize); 3622} 3623