DAGCombiner.cpp revision 729c6d1da87ad5b3bf849c4102b255657f67276c
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 <algorithm> 39#include <cmath> 40#include <iostream> 41using namespace llvm; 42 43namespace { 44 Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined"); 45 46 class DAGCombiner { 47 SelectionDAG &DAG; 48 TargetLowering &TLI; 49 bool AfterLegalize; 50 51 // Worklist of all of the nodes that need to be simplified. 52 std::vector<SDNode*> WorkList; 53 54 /// AddUsersToWorkList - When an instruction is simplified, add all users of 55 /// the instruction to the work lists because they might get more simplified 56 /// now. 57 /// 58 void AddUsersToWorkList(SDNode *N) { 59 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 60 UI != UE; ++UI) 61 WorkList.push_back(*UI); 62 } 63 64 /// removeFromWorkList - remove all instances of N from the worklist. 65 /// 66 void removeFromWorkList(SDNode *N) { 67 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 68 WorkList.end()); 69 } 70 71 public: 72 void AddToWorkList(SDNode *N) { 73 WorkList.push_back(N); 74 } 75 76 SDOperand CombineTo(SDNode *N, const std::vector<SDOperand> &To) { 77 ++NodesCombined; 78 DEBUG(std::cerr << "\nReplacing "; N->dump(); 79 std::cerr << "\nWith: "; To[0].Val->dump(&DAG); 80 std::cerr << " and " << To.size()-1 << " other values\n"); 81 std::vector<SDNode*> NowDead; 82 DAG.ReplaceAllUsesWith(N, To, &NowDead); 83 84 // Push the new nodes and any users onto the worklist 85 for (unsigned i = 0, e = To.size(); i != e; ++i) { 86 WorkList.push_back(To[i].Val); 87 AddUsersToWorkList(To[i].Val); 88 } 89 90 // Nodes can end up on the worklist more than once. Make sure we do 91 // not process a node that has been replaced. 92 removeFromWorkList(N); 93 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 94 removeFromWorkList(NowDead[i]); 95 96 // Finally, since the node is now dead, remove it from the graph. 97 DAG.DeleteNode(N); 98 return SDOperand(N, 0); 99 } 100 101 SDOperand CombineTo(SDNode *N, SDOperand Res) { 102 std::vector<SDOperand> To; 103 To.push_back(Res); 104 return CombineTo(N, To); 105 } 106 107 SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 108 std::vector<SDOperand> To; 109 To.push_back(Res0); 110 To.push_back(Res1); 111 return CombineTo(N, To); 112 } 113 private: 114 115 /// SimplifyDemandedBits - Check the specified integer node value to see if 116 /// it can be simplified or if things it uses can be simplified by bit 117 /// propagation. If so, return true. 118 bool SimplifyDemandedBits(SDOperand Op) { 119 TargetLowering::TargetLoweringOpt TLO(DAG); 120 uint64_t KnownZero, KnownOne; 121 uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType()); 122 if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO)) 123 return false; 124 125 // Revisit the node. 126 WorkList.push_back(Op.Val); 127 128 // Replace the old value with the new one. 129 ++NodesCombined; 130 DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump(); 131 std::cerr << "\nWith: "; TLO.New.Val->dump(&DAG)); 132 133 std::vector<SDNode*> NowDead; 134 DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead); 135 136 // Push the new node and any (possibly new) users onto the worklist. 137 WorkList.push_back(TLO.New.Val); 138 AddUsersToWorkList(TLO.New.Val); 139 140 // Nodes can end up on the worklist more than once. Make sure we do 141 // not process a node that has been replaced. 142 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 143 removeFromWorkList(NowDead[i]); 144 145 // Finally, if the node is now dead, remove it from the graph. The node 146 // may not be dead if the replacement process recursively simplified to 147 // something else needing this node. 148 if (TLO.Old.Val->use_empty()) { 149 removeFromWorkList(TLO.Old.Val); 150 DAG.DeleteNode(TLO.Old.Val); 151 } 152 return true; 153 } 154 155 /// visit - call the node-specific routine that knows how to fold each 156 /// particular type of node. 157 SDOperand visit(SDNode *N); 158 159 // Visitation implementation - Implement dag node combining for different 160 // node types. The semantics are as follows: 161 // Return Value: 162 // SDOperand.Val == 0 - No change was made 163 // SDOperand.Val == N - N was replaced, is dead, and is already handled. 164 // otherwise - N should be replaced by the returned Operand. 165 // 166 SDOperand visitTokenFactor(SDNode *N); 167 SDOperand visitADD(SDNode *N); 168 SDOperand visitSUB(SDNode *N); 169 SDOperand visitMUL(SDNode *N); 170 SDOperand visitSDIV(SDNode *N); 171 SDOperand visitUDIV(SDNode *N); 172 SDOperand visitSREM(SDNode *N); 173 SDOperand visitUREM(SDNode *N); 174 SDOperand visitMULHU(SDNode *N); 175 SDOperand visitMULHS(SDNode *N); 176 SDOperand visitAND(SDNode *N); 177 SDOperand visitOR(SDNode *N); 178 SDOperand visitXOR(SDNode *N); 179 SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp); 180 SDOperand visitSHL(SDNode *N); 181 SDOperand visitSRA(SDNode *N); 182 SDOperand visitSRL(SDNode *N); 183 SDOperand visitCTLZ(SDNode *N); 184 SDOperand visitCTTZ(SDNode *N); 185 SDOperand visitCTPOP(SDNode *N); 186 SDOperand visitSELECT(SDNode *N); 187 SDOperand visitSELECT_CC(SDNode *N); 188 SDOperand visitSETCC(SDNode *N); 189 SDOperand visitSIGN_EXTEND(SDNode *N); 190 SDOperand visitZERO_EXTEND(SDNode *N); 191 SDOperand visitANY_EXTEND(SDNode *N); 192 SDOperand visitSIGN_EXTEND_INREG(SDNode *N); 193 SDOperand visitTRUNCATE(SDNode *N); 194 SDOperand visitBIT_CONVERT(SDNode *N); 195 SDOperand visitVBIT_CONVERT(SDNode *N); 196 SDOperand visitFADD(SDNode *N); 197 SDOperand visitFSUB(SDNode *N); 198 SDOperand visitFMUL(SDNode *N); 199 SDOperand visitFDIV(SDNode *N); 200 SDOperand visitFREM(SDNode *N); 201 SDOperand visitFCOPYSIGN(SDNode *N); 202 SDOperand visitSINT_TO_FP(SDNode *N); 203 SDOperand visitUINT_TO_FP(SDNode *N); 204 SDOperand visitFP_TO_SINT(SDNode *N); 205 SDOperand visitFP_TO_UINT(SDNode *N); 206 SDOperand visitFP_ROUND(SDNode *N); 207 SDOperand visitFP_ROUND_INREG(SDNode *N); 208 SDOperand visitFP_EXTEND(SDNode *N); 209 SDOperand visitFNEG(SDNode *N); 210 SDOperand visitFABS(SDNode *N); 211 SDOperand visitBRCOND(SDNode *N); 212 SDOperand visitBR_CC(SDNode *N); 213 SDOperand visitLOAD(SDNode *N); 214 SDOperand visitXEXTLOAD(SDNode *N); 215 SDOperand visitSTORE(SDNode *N); 216 SDOperand visitINSERT_VECTOR_ELT(SDNode *N); 217 SDOperand visitVINSERT_VECTOR_ELT(SDNode *N); 218 SDOperand visitVBUILD_VECTOR(SDNode *N); 219 SDOperand visitVECTOR_SHUFFLE(SDNode *N); 220 SDOperand visitVVECTOR_SHUFFLE(SDNode *N); 221 222 SDOperand XformToShuffleWithZero(SDNode *N); 223 SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS); 224 225 bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS); 226 SDOperand SimplifyBinOpWithSameOpcodeHands(SDNode *N); 227 SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2); 228 SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2, 229 SDOperand N3, ISD::CondCode CC); 230 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 231 ISD::CondCode Cond, bool foldBooleans = true); 232 SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType); 233 SDOperand BuildSDIV(SDNode *N); 234 SDOperand BuildUDIV(SDNode *N); 235public: 236 DAGCombiner(SelectionDAG &D) 237 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {} 238 239 /// Run - runs the dag combiner on all nodes in the work list 240 void Run(bool RunningAfterLegalize); 241 }; 242} 243 244//===----------------------------------------------------------------------===// 245// TargetLowering::DAGCombinerInfo implementation 246//===----------------------------------------------------------------------===// 247 248void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) { 249 ((DAGCombiner*)DC)->AddToWorkList(N); 250} 251 252SDOperand TargetLowering::DAGCombinerInfo:: 253CombineTo(SDNode *N, const std::vector<SDOperand> &To) { 254 return ((DAGCombiner*)DC)->CombineTo(N, To); 255} 256 257SDOperand TargetLowering::DAGCombinerInfo:: 258CombineTo(SDNode *N, SDOperand Res) { 259 return ((DAGCombiner*)DC)->CombineTo(N, Res); 260} 261 262 263SDOperand TargetLowering::DAGCombinerInfo:: 264CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 265 return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1); 266} 267 268 269 270 271//===----------------------------------------------------------------------===// 272 273 274// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 275// that selects between the values 1 and 0, making it equivalent to a setcc. 276// Also, set the incoming LHS, RHS, and CC references to the appropriate 277// nodes based on the type of node we are checking. This simplifies life a 278// bit for the callers. 279static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 280 SDOperand &CC) { 281 if (N.getOpcode() == ISD::SETCC) { 282 LHS = N.getOperand(0); 283 RHS = N.getOperand(1); 284 CC = N.getOperand(2); 285 return true; 286 } 287 if (N.getOpcode() == ISD::SELECT_CC && 288 N.getOperand(2).getOpcode() == ISD::Constant && 289 N.getOperand(3).getOpcode() == ISD::Constant && 290 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 291 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 292 LHS = N.getOperand(0); 293 RHS = N.getOperand(1); 294 CC = N.getOperand(4); 295 return true; 296 } 297 return false; 298} 299 300// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 301// one use. If this is true, it allows the users to invert the operation for 302// free when it is profitable to do so. 303static bool isOneUseSetCC(SDOperand N) { 304 SDOperand N0, N1, N2; 305 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 306 return true; 307 return false; 308} 309 310// FIXME: This should probably go in the ISD class rather than being duplicated 311// in several files. 312static bool isCommutativeBinOp(unsigned Opcode) { 313 switch (Opcode) { 314 case ISD::ADD: 315 case ISD::MUL: 316 case ISD::AND: 317 case ISD::OR: 318 case ISD::XOR: return true; 319 default: return false; // FIXME: Need commutative info for user ops! 320 } 321} 322 323SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){ 324 MVT::ValueType VT = N0.getValueType(); 325 // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use 326 // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2)) 327 if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) { 328 if (isa<ConstantSDNode>(N1)) { 329 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1); 330 AddToWorkList(OpNode.Val); 331 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0)); 332 } else if (N0.hasOneUse()) { 333 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1); 334 AddToWorkList(OpNode.Val); 335 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1)); 336 } 337 } 338 // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use 339 // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2)) 340 if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) { 341 if (isa<ConstantSDNode>(N0)) { 342 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0); 343 AddToWorkList(OpNode.Val); 344 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0)); 345 } else if (N1.hasOneUse()) { 346 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0); 347 AddToWorkList(OpNode.Val); 348 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1)); 349 } 350 } 351 return SDOperand(); 352} 353 354void DAGCombiner::Run(bool RunningAfterLegalize) { 355 // set the instance variable, so that the various visit routines may use it. 356 AfterLegalize = RunningAfterLegalize; 357 358 // Add all the dag nodes to the worklist. 359 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 360 E = DAG.allnodes_end(); I != E; ++I) 361 WorkList.push_back(I); 362 363 // Create a dummy node (which is not added to allnodes), that adds a reference 364 // to the root node, preventing it from being deleted, and tracking any 365 // changes of the root. 366 HandleSDNode Dummy(DAG.getRoot()); 367 368 369 /// DagCombineInfo - Expose the DAG combiner to the target combiner impls. 370 TargetLowering::DAGCombinerInfo 371 DagCombineInfo(DAG, !RunningAfterLegalize, this); 372 373 // while the worklist isn't empty, inspect the node on the end of it and 374 // try and combine it. 375 while (!WorkList.empty()) { 376 SDNode *N = WorkList.back(); 377 WorkList.pop_back(); 378 379 // If N has no uses, it is dead. Make sure to revisit all N's operands once 380 // N is deleted from the DAG, since they too may now be dead or may have a 381 // reduced number of uses, allowing other xforms. 382 if (N->use_empty() && N != &Dummy) { 383 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 384 WorkList.push_back(N->getOperand(i).Val); 385 386 removeFromWorkList(N); 387 DAG.DeleteNode(N); 388 continue; 389 } 390 391 SDOperand RV = visit(N); 392 393 // If nothing happened, try a target-specific DAG combine. 394 if (RV.Val == 0) { 395 assert(N->getOpcode() != ISD::DELETED_NODE && 396 "Node was deleted but visit returned NULL!"); 397 if (N->getOpcode() >= ISD::BUILTIN_OP_END || 398 TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) 399 RV = TLI.PerformDAGCombine(N, DagCombineInfo); 400 } 401 402 if (RV.Val) { 403 ++NodesCombined; 404 // If we get back the same node we passed in, rather than a new node or 405 // zero, we know that the node must have defined multiple values and 406 // CombineTo was used. Since CombineTo takes care of the worklist 407 // mechanics for us, we have no work to do in this case. 408 if (RV.Val != N) { 409 assert(N->getOpcode() != ISD::DELETED_NODE && 410 RV.Val->getOpcode() != ISD::DELETED_NODE && 411 "Node was deleted but visit returned new node!"); 412 413 DEBUG(std::cerr << "\nReplacing "; N->dump(); 414 std::cerr << "\nWith: "; RV.Val->dump(&DAG); 415 std::cerr << '\n'); 416 std::vector<SDNode*> NowDead; 417 DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV), &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 std::vector<SDOperand> 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); 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); 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 std::vector<SDOperand> 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); 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 std::vector<SDOperand> 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); 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 std::vector<SDOperand> 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); 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 std::vector<SDOperand> 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(), Ops); 2453 } 2454 2455 return SDOperand(); 2456} 2457 2458SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) { 2459 SDOperand InVec = N->getOperand(0); 2460 SDOperand InVal = N->getOperand(1); 2461 SDOperand EltNo = N->getOperand(2); 2462 SDOperand NumElts = N->getOperand(3); 2463 SDOperand EltType = N->getOperand(4); 2464 2465 // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new 2466 // vector with the inserted element. 2467 if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 2468 unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue(); 2469 std::vector<SDOperand> Ops(InVec.Val->op_begin(), InVec.Val->op_end()); 2470 if (Elt < Ops.size()-2) 2471 Ops[Elt] = InVal; 2472 return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(), Ops); 2473 } 2474 2475 return SDOperand(); 2476} 2477 2478SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) { 2479 unsigned NumInScalars = N->getNumOperands()-2; 2480 SDOperand NumElts = N->getOperand(NumInScalars); 2481 SDOperand EltType = N->getOperand(NumInScalars+1); 2482 2483 // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT 2484 // operations. If so, and if the EXTRACT_ELT vector inputs come from at most 2485 // two distinct vectors, turn this into a shuffle node. 2486 SDOperand VecIn1, VecIn2; 2487 for (unsigned i = 0; i != NumInScalars; ++i) { 2488 // Ignore undef inputs. 2489 if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue; 2490 2491 // If this input is something other than a VEXTRACT_VECTOR_ELT with a 2492 // constant index, bail out. 2493 if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT || 2494 !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) { 2495 VecIn1 = VecIn2 = SDOperand(0, 0); 2496 break; 2497 } 2498 2499 // If the input vector type disagrees with the result of the vbuild_vector, 2500 // we can't make a shuffle. 2501 SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0); 2502 if (*(ExtractedFromVec.Val->op_end()-2) != NumElts || 2503 *(ExtractedFromVec.Val->op_end()-1) != EltType) { 2504 VecIn1 = VecIn2 = SDOperand(0, 0); 2505 break; 2506 } 2507 2508 // Otherwise, remember this. We allow up to two distinct input vectors. 2509 if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2) 2510 continue; 2511 2512 if (VecIn1.Val == 0) { 2513 VecIn1 = ExtractedFromVec; 2514 } else if (VecIn2.Val == 0) { 2515 VecIn2 = ExtractedFromVec; 2516 } else { 2517 // Too many inputs. 2518 VecIn1 = VecIn2 = SDOperand(0, 0); 2519 break; 2520 } 2521 } 2522 2523 // If everything is good, we can make a shuffle operation. 2524 if (VecIn1.Val) { 2525 std::vector<SDOperand> BuildVecIndices; 2526 for (unsigned i = 0; i != NumInScalars; ++i) { 2527 if (N->getOperand(i).getOpcode() == ISD::UNDEF) { 2528 BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, MVT::i32)); 2529 continue; 2530 } 2531 2532 SDOperand Extract = N->getOperand(i); 2533 2534 // If extracting from the first vector, just use the index directly. 2535 if (Extract.getOperand(0) == VecIn1) { 2536 BuildVecIndices.push_back(Extract.getOperand(1)); 2537 continue; 2538 } 2539 2540 // Otherwise, use InIdx + VecSize 2541 unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue(); 2542 BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, MVT::i32)); 2543 } 2544 2545 // Add count and size info. 2546 BuildVecIndices.push_back(NumElts); 2547 BuildVecIndices.push_back(DAG.getValueType(MVT::i32)); 2548 2549 // Return the new VVECTOR_SHUFFLE node. 2550 std::vector<SDOperand> Ops; 2551 Ops.push_back(VecIn1); 2552 if (VecIn2.Val) { 2553 Ops.push_back(VecIn2); 2554 } else { 2555 // Use an undef vbuild_vector as input for the second operand. 2556 std::vector<SDOperand> UnOps(NumInScalars, 2557 DAG.getNode(ISD::UNDEF, 2558 cast<VTSDNode>(EltType)->getVT())); 2559 UnOps.push_back(NumElts); 2560 UnOps.push_back(EltType); 2561 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, UnOps)); 2562 AddToWorkList(Ops.back().Val); 2563 } 2564 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR,MVT::Vector, BuildVecIndices)); 2565 Ops.push_back(NumElts); 2566 Ops.push_back(EltType); 2567 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops); 2568 } 2569 2570 return SDOperand(); 2571} 2572 2573SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { 2574 SDOperand ShufMask = N->getOperand(2); 2575 unsigned NumElts = ShufMask.getNumOperands(); 2576 2577 // If the shuffle mask is an identity operation on the LHS, return the LHS. 2578 bool isIdentity = true; 2579 for (unsigned i = 0; i != NumElts; ++i) { 2580 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2581 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 2582 isIdentity = false; 2583 break; 2584 } 2585 } 2586 if (isIdentity) return N->getOperand(0); 2587 2588 // If the shuffle mask is an identity operation on the RHS, return the RHS. 2589 isIdentity = true; 2590 for (unsigned i = 0; i != NumElts; ++i) { 2591 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2592 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 2593 isIdentity = false; 2594 break; 2595 } 2596 } 2597 if (isIdentity) return N->getOperand(1); 2598 2599 // If the LHS and the RHS are the same node, turn the RHS into an undef. 2600 if (N->getOperand(0) == N->getOperand(1)) { 2601 if (N->getOperand(0).getOpcode() == ISD::UNDEF) 2602 return DAG.getNode(ISD::UNDEF, N->getValueType(0)); 2603 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 2604 // first operand. 2605 std::vector<SDOperand> MappedOps; 2606 for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) { 2607 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 2608 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 2609 MappedOps.push_back(ShufMask.getOperand(i)); 2610 } else { 2611 unsigned NewIdx = 2612 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 2613 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 2614 } 2615 } 2616 ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(), 2617 MappedOps); 2618 AddToWorkList(ShufMask.Val); 2619 return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0), 2620 N->getOperand(0), 2621 DAG.getNode(ISD::UNDEF, N->getValueType(0)), 2622 ShufMask); 2623 } 2624 2625 return SDOperand(); 2626} 2627 2628SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) { 2629 SDOperand ShufMask = N->getOperand(2); 2630 unsigned NumElts = ShufMask.getNumOperands()-2; 2631 2632 // If the shuffle mask is an identity operation on the LHS, return the LHS. 2633 bool isIdentity = true; 2634 for (unsigned i = 0; i != NumElts; ++i) { 2635 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2636 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 2637 isIdentity = false; 2638 break; 2639 } 2640 } 2641 if (isIdentity) return N->getOperand(0); 2642 2643 // If the shuffle mask is an identity operation on the RHS, return the RHS. 2644 isIdentity = true; 2645 for (unsigned i = 0; i != NumElts; ++i) { 2646 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 2647 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 2648 isIdentity = false; 2649 break; 2650 } 2651 } 2652 if (isIdentity) return N->getOperand(1); 2653 2654 // If the LHS and the RHS are the same node, turn the RHS into an undef. 2655 if (N->getOperand(0) == N->getOperand(1)) { 2656 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 2657 // first operand. 2658 std::vector<SDOperand> MappedOps; 2659 for (unsigned i = 0; i != NumElts; ++i) { 2660 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 2661 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 2662 MappedOps.push_back(ShufMask.getOperand(i)); 2663 } else { 2664 unsigned NewIdx = 2665 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 2666 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 2667 } 2668 } 2669 // Add the type/#elts values. 2670 MappedOps.push_back(ShufMask.getOperand(NumElts)); 2671 MappedOps.push_back(ShufMask.getOperand(NumElts+1)); 2672 2673 ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(), 2674 MappedOps); 2675 AddToWorkList(ShufMask.Val); 2676 2677 // Build the undef vector. 2678 SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType()); 2679 for (unsigned i = 0; i != NumElts; ++i) 2680 MappedOps[i] = UDVal; 2681 MappedOps[NumElts ] = *(N->getOperand(0).Val->op_end()-2); 2682 MappedOps[NumElts+1] = *(N->getOperand(0).Val->op_end()-1); 2683 UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, MappedOps); 2684 2685 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 2686 N->getOperand(0), UDVal, ShufMask, 2687 MappedOps[NumElts], MappedOps[NumElts+1]); 2688 } 2689 2690 return SDOperand(); 2691} 2692 2693/// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform 2694/// a VAND to a vector_shuffle with the destination vector and a zero vector. 2695/// e.g. VAND V, <0xffffffff, 0, 0xffffffff, 0>. ==> 2696/// vector_shuffle V, Zero, <0, 4, 2, 4> 2697SDOperand DAGCombiner::XformToShuffleWithZero(SDNode *N) { 2698 SDOperand LHS = N->getOperand(0); 2699 SDOperand RHS = N->getOperand(1); 2700 if (N->getOpcode() == ISD::VAND) { 2701 SDOperand DstVecSize = *(LHS.Val->op_end()-2); 2702 SDOperand DstVecEVT = *(LHS.Val->op_end()-1); 2703 if (RHS.getOpcode() == ISD::VBIT_CONVERT) 2704 RHS = RHS.getOperand(0); 2705 if (RHS.getOpcode() == ISD::VBUILD_VECTOR) { 2706 std::vector<SDOperand> IdxOps; 2707 unsigned NumOps = RHS.getNumOperands(); 2708 unsigned NumElts = NumOps-2; 2709 MVT::ValueType EVT = cast<VTSDNode>(RHS.getOperand(NumOps-1))->getVT(); 2710 for (unsigned i = 0; i != NumElts; ++i) { 2711 SDOperand Elt = RHS.getOperand(i); 2712 if (!isa<ConstantSDNode>(Elt)) 2713 return SDOperand(); 2714 else if (cast<ConstantSDNode>(Elt)->isAllOnesValue()) 2715 IdxOps.push_back(DAG.getConstant(i, EVT)); 2716 else if (cast<ConstantSDNode>(Elt)->isNullValue()) 2717 IdxOps.push_back(DAG.getConstant(NumElts, EVT)); 2718 else 2719 return SDOperand(); 2720 } 2721 2722 // Let's see if the target supports this vector_shuffle. 2723 if (!TLI.isVectorClearMaskLegal(IdxOps, EVT, DAG)) 2724 return SDOperand(); 2725 2726 // Return the new VVECTOR_SHUFFLE node. 2727 SDOperand NumEltsNode = DAG.getConstant(NumElts, MVT::i32); 2728 SDOperand EVTNode = DAG.getValueType(EVT); 2729 std::vector<SDOperand> Ops; 2730 LHS = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, LHS, NumEltsNode, EVTNode); 2731 Ops.push_back(LHS); 2732 AddToWorkList(LHS.Val); 2733 std::vector<SDOperand> ZeroOps(NumElts, DAG.getConstant(0, EVT)); 2734 ZeroOps.push_back(NumEltsNode); 2735 ZeroOps.push_back(EVTNode); 2736 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, ZeroOps)); 2737 IdxOps.push_back(NumEltsNode); 2738 IdxOps.push_back(EVTNode); 2739 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, IdxOps)); 2740 Ops.push_back(NumEltsNode); 2741 Ops.push_back(EVTNode); 2742 SDOperand Result = DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops); 2743 if (NumEltsNode != DstVecSize || EVTNode != DstVecEVT) { 2744 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 2745 DstVecSize, DstVecEVT); 2746 } 2747 return Result; 2748 } 2749 } 2750 return SDOperand(); 2751} 2752 2753/// visitVBinOp - Visit a binary vector operation, like VADD. IntOp indicates 2754/// the scalar operation of the vop if it is operating on an integer vector 2755/// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD). 2756SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp, 2757 ISD::NodeType FPOp) { 2758 MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT(); 2759 ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp; 2760 SDOperand LHS = N->getOperand(0); 2761 SDOperand RHS = N->getOperand(1); 2762 SDOperand Shuffle = XformToShuffleWithZero(N); 2763 if (Shuffle.Val) return Shuffle; 2764 2765 // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold 2766 // this operation. 2767 if (LHS.getOpcode() == ISD::VBUILD_VECTOR && 2768 RHS.getOpcode() == ISD::VBUILD_VECTOR) { 2769 std::vector<SDOperand> Ops; 2770 for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) { 2771 SDOperand LHSOp = LHS.getOperand(i); 2772 SDOperand RHSOp = RHS.getOperand(i); 2773 // If these two elements can't be folded, bail out. 2774 if ((LHSOp.getOpcode() != ISD::UNDEF && 2775 LHSOp.getOpcode() != ISD::Constant && 2776 LHSOp.getOpcode() != ISD::ConstantFP) || 2777 (RHSOp.getOpcode() != ISD::UNDEF && 2778 RHSOp.getOpcode() != ISD::Constant && 2779 RHSOp.getOpcode() != ISD::ConstantFP)) 2780 break; 2781 Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp)); 2782 AddToWorkList(Ops.back().Val); 2783 assert((Ops.back().getOpcode() == ISD::UNDEF || 2784 Ops.back().getOpcode() == ISD::Constant || 2785 Ops.back().getOpcode() == ISD::ConstantFP) && 2786 "Scalar binop didn't fold!"); 2787 } 2788 2789 if (Ops.size() == LHS.getNumOperands()-2) { 2790 Ops.push_back(*(LHS.Val->op_end()-2)); 2791 Ops.push_back(*(LHS.Val->op_end()-1)); 2792 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 2793 } 2794 } 2795 2796 return SDOperand(); 2797} 2798 2799SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 2800 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 2801 2802 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 2803 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 2804 // If we got a simplified select_cc node back from SimplifySelectCC, then 2805 // break it down into a new SETCC node, and a new SELECT node, and then return 2806 // the SELECT node, since we were called with a SELECT node. 2807 if (SCC.Val) { 2808 // Check to see if we got a select_cc back (to turn into setcc/select). 2809 // Otherwise, just return whatever node we got back, like fabs. 2810 if (SCC.getOpcode() == ISD::SELECT_CC) { 2811 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 2812 SCC.getOperand(0), SCC.getOperand(1), 2813 SCC.getOperand(4)); 2814 AddToWorkList(SETCC.Val); 2815 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 2816 SCC.getOperand(3), SETCC); 2817 } 2818 return SCC; 2819 } 2820 return SDOperand(); 2821} 2822 2823/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS 2824/// are the two values being selected between, see if we can simplify the 2825/// select. Callers of this should assume that TheSelect is deleted if this 2826/// returns true. As such, they should return the appropriate thing (e.g. the 2827/// node) back to the top-level of the DAG combiner loop to avoid it being 2828/// looked at. 2829/// 2830bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS, 2831 SDOperand RHS) { 2832 2833 // If this is a select from two identical things, try to pull the operation 2834 // through the select. 2835 if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){ 2836#if 0 2837 std::cerr << "SELECT: ["; LHS.Val->dump(); 2838 std::cerr << "] ["; RHS.Val->dump(); 2839 std::cerr << "]\n"; 2840#endif 2841 2842 // If this is a load and the token chain is identical, replace the select 2843 // of two loads with a load through a select of the address to load from. 2844 // This triggers in things like "select bool X, 10.0, 123.0" after the FP 2845 // constants have been dropped into the constant pool. 2846 if ((LHS.getOpcode() == ISD::LOAD || 2847 LHS.getOpcode() == ISD::EXTLOAD || 2848 LHS.getOpcode() == ISD::ZEXTLOAD || 2849 LHS.getOpcode() == ISD::SEXTLOAD) && 2850 // Token chains must be identical. 2851 LHS.getOperand(0) == RHS.getOperand(0) && 2852 // If this is an EXTLOAD, the VT's must match. 2853 (LHS.getOpcode() == ISD::LOAD || 2854 LHS.getOperand(3) == RHS.getOperand(3))) { 2855 // FIXME: this conflates two src values, discarding one. This is not 2856 // the right thing to do, but nothing uses srcvalues now. When they do, 2857 // turn SrcValue into a list of locations. 2858 SDOperand Addr; 2859 if (TheSelect->getOpcode() == ISD::SELECT) 2860 Addr = DAG.getNode(ISD::SELECT, LHS.getOperand(1).getValueType(), 2861 TheSelect->getOperand(0), LHS.getOperand(1), 2862 RHS.getOperand(1)); 2863 else 2864 Addr = DAG.getNode(ISD::SELECT_CC, LHS.getOperand(1).getValueType(), 2865 TheSelect->getOperand(0), 2866 TheSelect->getOperand(1), 2867 LHS.getOperand(1), RHS.getOperand(1), 2868 TheSelect->getOperand(4)); 2869 2870 SDOperand Load; 2871 if (LHS.getOpcode() == ISD::LOAD) 2872 Load = DAG.getLoad(TheSelect->getValueType(0), LHS.getOperand(0), 2873 Addr, LHS.getOperand(2)); 2874 else 2875 Load = DAG.getExtLoad(LHS.getOpcode(), TheSelect->getValueType(0), 2876 LHS.getOperand(0), Addr, LHS.getOperand(2), 2877 cast<VTSDNode>(LHS.getOperand(3))->getVT()); 2878 // Users of the select now use the result of the load. 2879 CombineTo(TheSelect, Load); 2880 2881 // Users of the old loads now use the new load's chain. We know the 2882 // old-load value is dead now. 2883 CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1)); 2884 CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1)); 2885 return true; 2886 } 2887 } 2888 2889 return false; 2890} 2891 2892SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 2893 SDOperand N2, SDOperand N3, 2894 ISD::CondCode CC) { 2895 2896 MVT::ValueType VT = N2.getValueType(); 2897 //ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 2898 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 2899 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 2900 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 2901 2902 // Determine if the condition we're dealing with is constant 2903 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 2904 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 2905 2906 // fold select_cc true, x, y -> x 2907 if (SCCC && SCCC->getValue()) 2908 return N2; 2909 // fold select_cc false, x, y -> y 2910 if (SCCC && SCCC->getValue() == 0) 2911 return N3; 2912 2913 // Check to see if we can simplify the select into an fabs node 2914 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 2915 // Allow either -0.0 or 0.0 2916 if (CFP->getValue() == 0.0) { 2917 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 2918 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 2919 N0 == N2 && N3.getOpcode() == ISD::FNEG && 2920 N2 == N3.getOperand(0)) 2921 return DAG.getNode(ISD::FABS, VT, N0); 2922 2923 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 2924 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 2925 N0 == N3 && N2.getOpcode() == ISD::FNEG && 2926 N2.getOperand(0) == N3) 2927 return DAG.getNode(ISD::FABS, VT, N3); 2928 } 2929 } 2930 2931 // Check to see if we can perform the "gzip trick", transforming 2932 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 2933 if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() && 2934 MVT::isInteger(N0.getValueType()) && 2935 MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) { 2936 MVT::ValueType XType = N0.getValueType(); 2937 MVT::ValueType AType = N2.getValueType(); 2938 if (XType >= AType) { 2939 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 2940 // single-bit constant. 2941 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) { 2942 unsigned ShCtV = Log2_64(N2C->getValue()); 2943 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1; 2944 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 2945 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 2946 AddToWorkList(Shift.Val); 2947 if (XType > AType) { 2948 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 2949 AddToWorkList(Shift.Val); 2950 } 2951 return DAG.getNode(ISD::AND, AType, Shift, N2); 2952 } 2953 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 2954 DAG.getConstant(MVT::getSizeInBits(XType)-1, 2955 TLI.getShiftAmountTy())); 2956 AddToWorkList(Shift.Val); 2957 if (XType > AType) { 2958 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 2959 AddToWorkList(Shift.Val); 2960 } 2961 return DAG.getNode(ISD::AND, AType, Shift, N2); 2962 } 2963 } 2964 2965 // fold select C, 16, 0 -> shl C, 4 2966 if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) && 2967 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) { 2968 // Get a SetCC of the condition 2969 // FIXME: Should probably make sure that setcc is legal if we ever have a 2970 // target where it isn't. 2971 SDOperand Temp, SCC; 2972 // cast from setcc result type to select result type 2973 if (AfterLegalize) { 2974 SCC = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 2975 Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType()); 2976 } else { 2977 SCC = DAG.getSetCC(MVT::i1, N0, N1, CC); 2978 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 2979 } 2980 AddToWorkList(SCC.Val); 2981 AddToWorkList(Temp.Val); 2982 // shl setcc result by log2 n2c 2983 return DAG.getNode(ISD::SHL, N2.getValueType(), Temp, 2984 DAG.getConstant(Log2_64(N2C->getValue()), 2985 TLI.getShiftAmountTy())); 2986 } 2987 2988 // Check to see if this is the equivalent of setcc 2989 // FIXME: Turn all of these into setcc if setcc if setcc is legal 2990 // otherwise, go ahead with the folds. 2991 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) { 2992 MVT::ValueType XType = N0.getValueType(); 2993 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) { 2994 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 2995 if (Res.getValueType() != VT) 2996 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 2997 return Res; 2998 } 2999 3000 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 3001 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 3002 TLI.isOperationLegal(ISD::CTLZ, XType)) { 3003 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 3004 return DAG.getNode(ISD::SRL, XType, Ctlz, 3005 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)), 3006 TLI.getShiftAmountTy())); 3007 } 3008 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 3009 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 3010 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 3011 N0); 3012 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 3013 DAG.getConstant(~0ULL, XType)); 3014 return DAG.getNode(ISD::SRL, XType, 3015 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 3016 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3017 TLI.getShiftAmountTy())); 3018 } 3019 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 3020 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 3021 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0, 3022 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3023 TLI.getShiftAmountTy())); 3024 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 3025 } 3026 } 3027 3028 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 3029 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 3030 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 3031 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) { 3032 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) { 3033 MVT::ValueType XType = N0.getValueType(); 3034 if (SubC->isNullValue() && MVT::isInteger(XType)) { 3035 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 3036 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3037 TLI.getShiftAmountTy())); 3038 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 3039 AddToWorkList(Shift.Val); 3040 AddToWorkList(Add.Val); 3041 return DAG.getNode(ISD::XOR, XType, Add, Shift); 3042 } 3043 } 3044 } 3045 3046 return SDOperand(); 3047} 3048 3049SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 3050 SDOperand N1, ISD::CondCode Cond, 3051 bool foldBooleans) { 3052 // These setcc operations always fold. 3053 switch (Cond) { 3054 default: break; 3055 case ISD::SETFALSE: 3056 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 3057 case ISD::SETTRUE: 3058 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 3059 } 3060 3061 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 3062 uint64_t C1 = N1C->getValue(); 3063 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) { 3064 uint64_t C0 = N0C->getValue(); 3065 3066 // Sign extend the operands if required 3067 if (ISD::isSignedIntSetCC(Cond)) { 3068 C0 = N0C->getSignExtended(); 3069 C1 = N1C->getSignExtended(); 3070 } 3071 3072 switch (Cond) { 3073 default: assert(0 && "Unknown integer setcc!"); 3074 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 3075 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 3076 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT); 3077 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT); 3078 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT); 3079 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT); 3080 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT); 3081 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT); 3082 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT); 3083 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT); 3084 } 3085 } else { 3086 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 3087 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 3088 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 3089 3090 // If the comparison constant has bits in the upper part, the 3091 // zero-extended value could never match. 3092 if (C1 & (~0ULL << InSize)) { 3093 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 3094 switch (Cond) { 3095 case ISD::SETUGT: 3096 case ISD::SETUGE: 3097 case ISD::SETEQ: return DAG.getConstant(0, VT); 3098 case ISD::SETULT: 3099 case ISD::SETULE: 3100 case ISD::SETNE: return DAG.getConstant(1, VT); 3101 case ISD::SETGT: 3102 case ISD::SETGE: 3103 // True if the sign bit of C1 is set. 3104 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 3105 case ISD::SETLT: 3106 case ISD::SETLE: 3107 // True if the sign bit of C1 isn't set. 3108 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 3109 default: 3110 break; 3111 } 3112 } 3113 3114 // Otherwise, we can perform the comparison with the low bits. 3115 switch (Cond) { 3116 case ISD::SETEQ: 3117 case ISD::SETNE: 3118 case ISD::SETUGT: 3119 case ISD::SETUGE: 3120 case ISD::SETULT: 3121 case ISD::SETULE: 3122 return DAG.getSetCC(VT, N0.getOperand(0), 3123 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 3124 Cond); 3125 default: 3126 break; // todo, be more careful with signed comparisons 3127 } 3128 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 3129 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 3130 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 3131 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 3132 MVT::ValueType ExtDstTy = N0.getValueType(); 3133 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 3134 3135 // If the extended part has any inconsistent bits, it cannot ever 3136 // compare equal. In other words, they have to be all ones or all 3137 // zeros. 3138 uint64_t ExtBits = 3139 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 3140 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 3141 return DAG.getConstant(Cond == ISD::SETNE, VT); 3142 3143 SDOperand ZextOp; 3144 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 3145 if (Op0Ty == ExtSrcTy) { 3146 ZextOp = N0.getOperand(0); 3147 } else { 3148 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 3149 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 3150 DAG.getConstant(Imm, Op0Ty)); 3151 } 3152 AddToWorkList(ZextOp.Val); 3153 // Otherwise, make this a use of a zext. 3154 return DAG.getSetCC(VT, ZextOp, 3155 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 3156 ExtDstTy), 3157 Cond); 3158 } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) && 3159 (Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3160 (N0.getOpcode() == ISD::XOR || 3161 (N0.getOpcode() == ISD::AND && 3162 N0.getOperand(0).getOpcode() == ISD::XOR && 3163 N0.getOperand(1) == N0.getOperand(0).getOperand(1))) && 3164 isa<ConstantSDNode>(N0.getOperand(1)) && 3165 cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) { 3166 // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We can 3167 // only do this if the top bits are known zero. 3168 if (TLI.MaskedValueIsZero(N1, 3169 MVT::getIntVTBitMask(N0.getValueType())-1)) { 3170 // Okay, get the un-inverted input value. 3171 SDOperand Val; 3172 if (N0.getOpcode() == ISD::XOR) 3173 Val = N0.getOperand(0); 3174 else { 3175 assert(N0.getOpcode() == ISD::AND && 3176 N0.getOperand(0).getOpcode() == ISD::XOR); 3177 // ((X^1)&1)^1 -> X & 1 3178 Val = DAG.getNode(ISD::AND, N0.getValueType(), 3179 N0.getOperand(0).getOperand(0), N0.getOperand(1)); 3180 } 3181 return DAG.getSetCC(VT, Val, N1, 3182 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ); 3183 } 3184 } 3185 3186 uint64_t MinVal, MaxVal; 3187 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 3188 if (ISD::isSignedIntSetCC(Cond)) { 3189 MinVal = 1ULL << (OperandBitSize-1); 3190 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 3191 MaxVal = ~0ULL >> (65-OperandBitSize); 3192 else 3193 MaxVal = 0; 3194 } else { 3195 MinVal = 0; 3196 MaxVal = ~0ULL >> (64-OperandBitSize); 3197 } 3198 3199 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 3200 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 3201 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 3202 --C1; // X >= C0 --> X > (C0-1) 3203 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 3204 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 3205 } 3206 3207 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 3208 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 3209 ++C1; // X <= C0 --> X < (C0+1) 3210 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 3211 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 3212 } 3213 3214 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 3215 return DAG.getConstant(0, VT); // X < MIN --> false 3216 3217 // Canonicalize setgt X, Min --> setne X, Min 3218 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 3219 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 3220 // Canonicalize setlt X, Max --> setne X, Max 3221 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal) 3222 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 3223 3224 // If we have setult X, 1, turn it into seteq X, 0 3225 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 3226 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 3227 ISD::SETEQ); 3228 // If we have setugt X, Max-1, turn it into seteq X, Max 3229 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 3230 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 3231 ISD::SETEQ); 3232 3233 // If we have "setcc X, C0", check to see if we can shrink the immediate 3234 // by changing cc. 3235 3236 // SETUGT X, SINTMAX -> SETLT X, 0 3237 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 3238 C1 == (~0ULL >> (65-OperandBitSize))) 3239 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 3240 ISD::SETLT); 3241 3242 // FIXME: Implement the rest of these. 3243 3244 // Fold bit comparisons when we can. 3245 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3246 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 3247 if (ConstantSDNode *AndRHS = 3248 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 3249 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 3250 // Perform the xform if the AND RHS is a single bit. 3251 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 3252 return DAG.getNode(ISD::SRL, VT, N0, 3253 DAG.getConstant(Log2_64(AndRHS->getValue()), 3254 TLI.getShiftAmountTy())); 3255 } 3256 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 3257 // (X & 8) == 8 --> (X & 8) >> 3 3258 // Perform the xform if C1 is a single bit. 3259 if ((C1 & (C1-1)) == 0) { 3260 return DAG.getNode(ISD::SRL, VT, N0, 3261 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 3262 } 3263 } 3264 } 3265 } 3266 } else if (isa<ConstantSDNode>(N0.Val)) { 3267 // Ensure that the constant occurs on the RHS. 3268 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 3269 } 3270 3271 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val)) 3272 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) { 3273 double C0 = N0C->getValue(), C1 = N1C->getValue(); 3274 3275 switch (Cond) { 3276 default: break; // FIXME: Implement the rest of these! 3277 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 3278 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 3279 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT); 3280 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT); 3281 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT); 3282 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT); 3283 } 3284 } else { 3285 // Ensure that the constant occurs on the RHS. 3286 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 3287 } 3288 3289 if (N0 == N1) { 3290 // We can always fold X == Y for integer setcc's. 3291 if (MVT::isInteger(N0.getValueType())) 3292 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 3293 unsigned UOF = ISD::getUnorderedFlavor(Cond); 3294 if (UOF == 2) // FP operators that are undefined on NaNs. 3295 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 3296 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 3297 return DAG.getConstant(UOF, VT); 3298 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 3299 // if it is not already. 3300 ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO; 3301 if (NewCond != Cond) 3302 return DAG.getSetCC(VT, N0, N1, NewCond); 3303 } 3304 3305 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3306 MVT::isInteger(N0.getValueType())) { 3307 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 3308 N0.getOpcode() == ISD::XOR) { 3309 // Simplify (X+Y) == (X+Z) --> Y == Z 3310 if (N0.getOpcode() == N1.getOpcode()) { 3311 if (N0.getOperand(0) == N1.getOperand(0)) 3312 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 3313 if (N0.getOperand(1) == N1.getOperand(1)) 3314 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 3315 if (isCommutativeBinOp(N0.getOpcode())) { 3316 // If X op Y == Y op X, try other combinations. 3317 if (N0.getOperand(0) == N1.getOperand(1)) 3318 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 3319 if (N0.getOperand(1) == N1.getOperand(0)) 3320 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond); 3321 } 3322 } 3323 3324 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 3325 if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 3326 // Turn (X+C1) == C2 --> X == C2-C1 3327 if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) { 3328 return DAG.getSetCC(VT, N0.getOperand(0), 3329 DAG.getConstant(RHSC->getValue()-LHSR->getValue(), 3330 N0.getValueType()), Cond); 3331 } 3332 3333 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. 3334 if (N0.getOpcode() == ISD::XOR) 3335 // If we know that all of the inverted bits are zero, don't bother 3336 // performing the inversion. 3337 if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue())) 3338 return DAG.getSetCC(VT, N0.getOperand(0), 3339 DAG.getConstant(LHSR->getValue()^RHSC->getValue(), 3340 N0.getValueType()), Cond); 3341 } 3342 3343 // Turn (C1-X) == C2 --> X == C1-C2 3344 if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) { 3345 if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) { 3346 return DAG.getSetCC(VT, N0.getOperand(1), 3347 DAG.getConstant(SUBC->getValue()-RHSC->getValue(), 3348 N0.getValueType()), Cond); 3349 } 3350 } 3351 } 3352 3353 // Simplify (X+Z) == X --> Z == 0 3354 if (N0.getOperand(0) == N1) 3355 return DAG.getSetCC(VT, N0.getOperand(1), 3356 DAG.getConstant(0, N0.getValueType()), Cond); 3357 if (N0.getOperand(1) == N1) { 3358 if (isCommutativeBinOp(N0.getOpcode())) 3359 return DAG.getSetCC(VT, N0.getOperand(0), 3360 DAG.getConstant(0, N0.getValueType()), Cond); 3361 else { 3362 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 3363 // (Z-X) == X --> Z == X<<1 3364 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 3365 N1, 3366 DAG.getConstant(1,TLI.getShiftAmountTy())); 3367 AddToWorkList(SH.Val); 3368 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 3369 } 3370 } 3371 } 3372 3373 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 3374 N1.getOpcode() == ISD::XOR) { 3375 // Simplify X == (X+Z) --> Z == 0 3376 if (N1.getOperand(0) == N0) { 3377 return DAG.getSetCC(VT, N1.getOperand(1), 3378 DAG.getConstant(0, N1.getValueType()), Cond); 3379 } else if (N1.getOperand(1) == N0) { 3380 if (isCommutativeBinOp(N1.getOpcode())) { 3381 return DAG.getSetCC(VT, N1.getOperand(0), 3382 DAG.getConstant(0, N1.getValueType()), Cond); 3383 } else { 3384 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 3385 // X == (Z-X) --> X<<1 == Z 3386 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 3387 DAG.getConstant(1,TLI.getShiftAmountTy())); 3388 AddToWorkList(SH.Val); 3389 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 3390 } 3391 } 3392 } 3393 } 3394 3395 // Fold away ALL boolean setcc's. 3396 SDOperand Temp; 3397 if (N0.getValueType() == MVT::i1 && foldBooleans) { 3398 switch (Cond) { 3399 default: assert(0 && "Unknown integer setcc!"); 3400 case ISD::SETEQ: // X == Y -> (X^Y)^1 3401 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 3402 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 3403 AddToWorkList(Temp.Val); 3404 break; 3405 case ISD::SETNE: // X != Y --> (X^Y) 3406 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 3407 break; 3408 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 3409 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 3410 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 3411 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 3412 AddToWorkList(Temp.Val); 3413 break; 3414 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 3415 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 3416 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 3417 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 3418 AddToWorkList(Temp.Val); 3419 break; 3420 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 3421 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 3422 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 3423 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 3424 AddToWorkList(Temp.Val); 3425 break; 3426 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 3427 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 3428 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 3429 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 3430 break; 3431 } 3432 if (VT != MVT::i1) { 3433 AddToWorkList(N0.Val); 3434 // FIXME: If running after legalize, we probably can't do this. 3435 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 3436 } 3437 return N0; 3438 } 3439 3440 // Could not fold it. 3441 return SDOperand(); 3442} 3443 3444/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 3445/// return a DAG expression to select that will generate the same value by 3446/// multiplying by a magic number. See: 3447/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 3448SDOperand DAGCombiner::BuildSDIV(SDNode *N) { 3449 std::list<SDNode*> Built; 3450 SDOperand S = TLI.BuildSDIV(N, DAG, &Built); 3451 3452 for (std::list<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 3453 ii != ee; ++ii) 3454 AddToWorkList(*ii); 3455 return S; 3456} 3457 3458/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 3459/// return a DAG expression to select that will generate the same value by 3460/// multiplying by a magic number. See: 3461/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 3462SDOperand DAGCombiner::BuildUDIV(SDNode *N) { 3463 std::list<SDNode*> Built; 3464 SDOperand S = TLI.BuildUDIV(N, DAG, &Built); 3465 3466 for (std::list<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 3467 ii != ee; ++ii) 3468 AddToWorkList(*ii); 3469 return S; 3470} 3471 3472// SelectionDAG::Combine - This is the entry point for the file. 3473// 3474void SelectionDAG::Combine(bool RunningAfterLegalize) { 3475 /// run - This is the main entry point to this class. 3476 /// 3477 DAGCombiner(*this).Run(RunningAfterLegalize); 3478} 3479