DAGCombiner.cpp revision ddae4bd68358df7415d532e6930c0ba9c60f6cb5
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: divide by zero is currently left unfolded. do we want to turn this 26// into an undef? 27// FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false 28// 29//===----------------------------------------------------------------------===// 30 31#define DEBUG_TYPE "dagcombine" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/Analysis/AliasAnalysis.h" 34#include "llvm/CodeGen/SelectionDAG.h" 35#include "llvm/Support/Debug.h" 36#include "llvm/Support/MathExtras.h" 37#include "llvm/Target/TargetLowering.h" 38#include "llvm/Target/TargetOptions.h" 39#include "llvm/Support/Compiler.h" 40#include "llvm/Support/CommandLine.h" 41#include <algorithm> 42using namespace llvm; 43 44STATISTIC(NodesCombined , "Number of dag nodes combined"); 45STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created"); 46STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created"); 47 48namespace { 49 static cl::opt<bool> 50 CombinerAA("combiner-alias-analysis", cl::Hidden, 51 cl::desc("Turn on alias analysis during testing")); 52 53 static cl::opt<bool> 54 CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden, 55 cl::desc("Include global information in alias analysis")); 56 57//------------------------------ DAGCombiner ---------------------------------// 58 59 class VISIBILITY_HIDDEN DAGCombiner { 60 SelectionDAG &DAG; 61 TargetLowering &TLI; 62 bool AfterLegalize; 63 64 // Worklist of all of the nodes that need to be simplified. 65 std::vector<SDNode*> WorkList; 66 67 // AA - Used for DAG load/store alias analysis. 68 AliasAnalysis &AA; 69 70 /// AddUsersToWorkList - When an instruction is simplified, add all users of 71 /// the instruction to the work lists because they might get more simplified 72 /// now. 73 /// 74 void AddUsersToWorkList(SDNode *N) { 75 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 76 UI != UE; ++UI) 77 AddToWorkList(*UI); 78 } 79 80 /// removeFromWorkList - remove all instances of N from the worklist. 81 /// 82 void removeFromWorkList(SDNode *N) { 83 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 84 WorkList.end()); 85 } 86 87 public: 88 /// AddToWorkList - Add to the work list making sure it's instance is at the 89 /// the back (next to be processed.) 90 void AddToWorkList(SDNode *N) { 91 removeFromWorkList(N); 92 WorkList.push_back(N); 93 } 94 95 SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo, 96 bool AddTo = true) { 97 assert(N->getNumValues() == NumTo && "Broken CombineTo call!"); 98 ++NodesCombined; 99 DOUT << "\nReplacing.1 "; DEBUG(N->dump()); 100 DOUT << "\nWith: "; DEBUG(To[0].Val->dump(&DAG)); 101 DOUT << " and " << NumTo-1 << " other values\n"; 102 std::vector<SDNode*> NowDead; 103 DAG.ReplaceAllUsesWith(N, To, &NowDead); 104 105 if (AddTo) { 106 // Push the new nodes and any users onto the worklist 107 for (unsigned i = 0, e = NumTo; i != e; ++i) { 108 AddToWorkList(To[i].Val); 109 AddUsersToWorkList(To[i].Val); 110 } 111 } 112 113 // Nodes can be reintroduced into the worklist. Make sure we do not 114 // process a node that has been replaced. 115 removeFromWorkList(N); 116 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 117 removeFromWorkList(NowDead[i]); 118 119 // Finally, since the node is now dead, remove it from the graph. 120 DAG.DeleteNode(N); 121 return SDOperand(N, 0); 122 } 123 124 SDOperand CombineTo(SDNode *N, SDOperand Res, bool AddTo = true) { 125 return CombineTo(N, &Res, 1, AddTo); 126 } 127 128 SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1, 129 bool AddTo = true) { 130 SDOperand To[] = { Res0, Res1 }; 131 return CombineTo(N, To, 2, AddTo); 132 } 133 private: 134 135 /// SimplifyDemandedBits - Check the specified integer node value to see if 136 /// it can be simplified or if things it uses can be simplified by bit 137 /// propagation. If so, return true. 138 bool SimplifyDemandedBits(SDOperand Op) { 139 TargetLowering::TargetLoweringOpt TLO(DAG); 140 uint64_t KnownZero, KnownOne; 141 uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType()); 142 if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO)) 143 return false; 144 145 // Revisit the node. 146 AddToWorkList(Op.Val); 147 148 // Replace the old value with the new one. 149 ++NodesCombined; 150 DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.Val->dump()); 151 DOUT << "\nWith: "; DEBUG(TLO.New.Val->dump(&DAG)); 152 DOUT << '\n'; 153 154 std::vector<SDNode*> NowDead; 155 DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead); 156 157 // Push the new node and any (possibly new) users onto the worklist. 158 AddToWorkList(TLO.New.Val); 159 AddUsersToWorkList(TLO.New.Val); 160 161 // Nodes can end up on the worklist more than once. Make sure we do 162 // not process a node that has been replaced. 163 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 164 removeFromWorkList(NowDead[i]); 165 166 // Finally, if the node is now dead, remove it from the graph. The node 167 // may not be dead if the replacement process recursively simplified to 168 // something else needing this node. 169 if (TLO.Old.Val->use_empty()) { 170 removeFromWorkList(TLO.Old.Val); 171 DAG.DeleteNode(TLO.Old.Val); 172 } 173 return true; 174 } 175 176 bool CombineToPreIndexedLoadStore(SDNode *N); 177 bool CombineToPostIndexedLoadStore(SDNode *N); 178 179 180 /// visit - call the node-specific routine that knows how to fold each 181 /// particular type of node. 182 SDOperand visit(SDNode *N); 183 184 // Visitation implementation - Implement dag node combining for different 185 // node types. The semantics are as follows: 186 // Return Value: 187 // SDOperand.Val == 0 - No change was made 188 // SDOperand.Val == N - N was replaced, is dead, and is already handled. 189 // otherwise - N should be replaced by the returned Operand. 190 // 191 SDOperand visitTokenFactor(SDNode *N); 192 SDOperand visitADD(SDNode *N); 193 SDOperand visitSUB(SDNode *N); 194 SDOperand visitMUL(SDNode *N); 195 SDOperand visitSDIV(SDNode *N); 196 SDOperand visitUDIV(SDNode *N); 197 SDOperand visitSREM(SDNode *N); 198 SDOperand visitUREM(SDNode *N); 199 SDOperand visitMULHU(SDNode *N); 200 SDOperand visitMULHS(SDNode *N); 201 SDOperand visitAND(SDNode *N); 202 SDOperand visitOR(SDNode *N); 203 SDOperand visitXOR(SDNode *N); 204 SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp); 205 SDOperand visitSHL(SDNode *N); 206 SDOperand visitSRA(SDNode *N); 207 SDOperand visitSRL(SDNode *N); 208 SDOperand visitCTLZ(SDNode *N); 209 SDOperand visitCTTZ(SDNode *N); 210 SDOperand visitCTPOP(SDNode *N); 211 SDOperand visitSELECT(SDNode *N); 212 SDOperand visitSELECT_CC(SDNode *N); 213 SDOperand visitSETCC(SDNode *N); 214 SDOperand visitSIGN_EXTEND(SDNode *N); 215 SDOperand visitZERO_EXTEND(SDNode *N); 216 SDOperand visitANY_EXTEND(SDNode *N); 217 SDOperand visitSIGN_EXTEND_INREG(SDNode *N); 218 SDOperand visitTRUNCATE(SDNode *N); 219 SDOperand visitBIT_CONVERT(SDNode *N); 220 SDOperand visitVBIT_CONVERT(SDNode *N); 221 SDOperand visitFADD(SDNode *N); 222 SDOperand visitFSUB(SDNode *N); 223 SDOperand visitFMUL(SDNode *N); 224 SDOperand visitFDIV(SDNode *N); 225 SDOperand visitFREM(SDNode *N); 226 SDOperand visitFCOPYSIGN(SDNode *N); 227 SDOperand visitSINT_TO_FP(SDNode *N); 228 SDOperand visitUINT_TO_FP(SDNode *N); 229 SDOperand visitFP_TO_SINT(SDNode *N); 230 SDOperand visitFP_TO_UINT(SDNode *N); 231 SDOperand visitFP_ROUND(SDNode *N); 232 SDOperand visitFP_ROUND_INREG(SDNode *N); 233 SDOperand visitFP_EXTEND(SDNode *N); 234 SDOperand visitFNEG(SDNode *N); 235 SDOperand visitFABS(SDNode *N); 236 SDOperand visitBRCOND(SDNode *N); 237 SDOperand visitBR_CC(SDNode *N); 238 SDOperand visitLOAD(SDNode *N); 239 SDOperand visitSTORE(SDNode *N); 240 SDOperand visitINSERT_VECTOR_ELT(SDNode *N); 241 SDOperand visitVINSERT_VECTOR_ELT(SDNode *N); 242 SDOperand visitVBUILD_VECTOR(SDNode *N); 243 SDOperand visitVECTOR_SHUFFLE(SDNode *N); 244 SDOperand visitVVECTOR_SHUFFLE(SDNode *N); 245 246 SDOperand XformToShuffleWithZero(SDNode *N); 247 SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS); 248 249 bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS); 250 SDOperand SimplifyBinOpWithSameOpcodeHands(SDNode *N); 251 SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2); 252 SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2, 253 SDOperand N3, ISD::CondCode CC); 254 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 255 ISD::CondCode Cond, bool foldBooleans = true); 256 SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType); 257 SDOperand BuildSDIV(SDNode *N); 258 SDOperand BuildUDIV(SDNode *N); 259 SDNode *MatchRotate(SDOperand LHS, SDOperand RHS); 260 261 /// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes, 262 /// looking for aliasing nodes and adding them to the Aliases vector. 263 void GatherAllAliases(SDNode *N, SDOperand OriginalChain, 264 SmallVector<SDOperand, 8> &Aliases); 265 266 /// isAlias - Return true if there is any possibility that the two addresses 267 /// overlap. 268 bool isAlias(SDOperand Ptr1, int64_t Size1, 269 const Value *SrcValue1, int SrcValueOffset1, 270 SDOperand Ptr2, int64_t Size2, 271 const Value *SrcValue2, int SrcValueOffset2); 272 273 /// FindAliasInfo - Extracts the relevant alias information from the memory 274 /// node. Returns true if the operand was a load. 275 bool FindAliasInfo(SDNode *N, 276 SDOperand &Ptr, int64_t &Size, 277 const Value *&SrcValue, int &SrcValueOffset); 278 279 /// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, 280 /// looking for a better chain (aliasing node.) 281 SDOperand FindBetterChain(SDNode *N, SDOperand Chain); 282 283public: 284 DAGCombiner(SelectionDAG &D, AliasAnalysis &A) 285 : DAG(D), 286 TLI(D.getTargetLoweringInfo()), 287 AfterLegalize(false), 288 AA(A) {} 289 290 /// Run - runs the dag combiner on all nodes in the work list 291 void Run(bool RunningAfterLegalize); 292 }; 293} 294 295//===----------------------------------------------------------------------===// 296// TargetLowering::DAGCombinerInfo implementation 297//===----------------------------------------------------------------------===// 298 299void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) { 300 ((DAGCombiner*)DC)->AddToWorkList(N); 301} 302 303SDOperand TargetLowering::DAGCombinerInfo:: 304CombineTo(SDNode *N, const std::vector<SDOperand> &To) { 305 return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size()); 306} 307 308SDOperand TargetLowering::DAGCombinerInfo:: 309CombineTo(SDNode *N, SDOperand Res) { 310 return ((DAGCombiner*)DC)->CombineTo(N, Res); 311} 312 313 314SDOperand TargetLowering::DAGCombinerInfo:: 315CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 316 return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1); 317} 318 319 320 321 322//===----------------------------------------------------------------------===// 323 324 325// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 326// that selects between the values 1 and 0, making it equivalent to a setcc. 327// Also, set the incoming LHS, RHS, and CC references to the appropriate 328// nodes based on the type of node we are checking. This simplifies life a 329// bit for the callers. 330static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 331 SDOperand &CC) { 332 if (N.getOpcode() == ISD::SETCC) { 333 LHS = N.getOperand(0); 334 RHS = N.getOperand(1); 335 CC = N.getOperand(2); 336 return true; 337 } 338 if (N.getOpcode() == ISD::SELECT_CC && 339 N.getOperand(2).getOpcode() == ISD::Constant && 340 N.getOperand(3).getOpcode() == ISD::Constant && 341 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 342 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 343 LHS = N.getOperand(0); 344 RHS = N.getOperand(1); 345 CC = N.getOperand(4); 346 return true; 347 } 348 return false; 349} 350 351// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 352// one use. If this is true, it allows the users to invert the operation for 353// free when it is profitable to do so. 354static bool isOneUseSetCC(SDOperand N) { 355 SDOperand N0, N1, N2; 356 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 357 return true; 358 return false; 359} 360 361SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){ 362 MVT::ValueType VT = N0.getValueType(); 363 // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use 364 // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2)) 365 if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) { 366 if (isa<ConstantSDNode>(N1)) { 367 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1); 368 AddToWorkList(OpNode.Val); 369 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0)); 370 } else if (N0.hasOneUse()) { 371 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1); 372 AddToWorkList(OpNode.Val); 373 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1)); 374 } 375 } 376 // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use 377 // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2)) 378 if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) { 379 if (isa<ConstantSDNode>(N0)) { 380 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0); 381 AddToWorkList(OpNode.Val); 382 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0)); 383 } else if (N1.hasOneUse()) { 384 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0); 385 AddToWorkList(OpNode.Val); 386 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1)); 387 } 388 } 389 return SDOperand(); 390} 391 392void DAGCombiner::Run(bool RunningAfterLegalize) { 393 // set the instance variable, so that the various visit routines may use it. 394 AfterLegalize = RunningAfterLegalize; 395 396 // Add all the dag nodes to the worklist. 397 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 398 E = DAG.allnodes_end(); I != E; ++I) 399 WorkList.push_back(I); 400 401 // Create a dummy node (which is not added to allnodes), that adds a reference 402 // to the root node, preventing it from being deleted, and tracking any 403 // changes of the root. 404 HandleSDNode Dummy(DAG.getRoot()); 405 406 // The root of the dag may dangle to deleted nodes until the dag combiner is 407 // done. Set it to null to avoid confusion. 408 DAG.setRoot(SDOperand()); 409 410 /// DagCombineInfo - Expose the DAG combiner to the target combiner impls. 411 TargetLowering::DAGCombinerInfo 412 DagCombineInfo(DAG, !RunningAfterLegalize, this); 413 414 // while the worklist isn't empty, inspect the node on the end of it and 415 // try and combine it. 416 while (!WorkList.empty()) { 417 SDNode *N = WorkList.back(); 418 WorkList.pop_back(); 419 420 // If N has no uses, it is dead. Make sure to revisit all N's operands once 421 // N is deleted from the DAG, since they too may now be dead or may have a 422 // reduced number of uses, allowing other xforms. 423 if (N->use_empty() && N != &Dummy) { 424 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 425 AddToWorkList(N->getOperand(i).Val); 426 427 DAG.DeleteNode(N); 428 continue; 429 } 430 431 SDOperand RV = visit(N); 432 433 // If nothing happened, try a target-specific DAG combine. 434 if (RV.Val == 0) { 435 assert(N->getOpcode() != ISD::DELETED_NODE && 436 "Node was deleted but visit returned NULL!"); 437 if (N->getOpcode() >= ISD::BUILTIN_OP_END || 438 TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) 439 RV = TLI.PerformDAGCombine(N, DagCombineInfo); 440 } 441 442 if (RV.Val) { 443 ++NodesCombined; 444 // If we get back the same node we passed in, rather than a new node or 445 // zero, we know that the node must have defined multiple values and 446 // CombineTo was used. Since CombineTo takes care of the worklist 447 // mechanics for us, we have no work to do in this case. 448 if (RV.Val != N) { 449 assert(N->getOpcode() != ISD::DELETED_NODE && 450 RV.Val->getOpcode() != ISD::DELETED_NODE && 451 "Node was deleted but visit returned new node!"); 452 453 DOUT << "\nReplacing.3 "; DEBUG(N->dump()); 454 DOUT << "\nWith: "; DEBUG(RV.Val->dump(&DAG)); 455 DOUT << '\n'; 456 std::vector<SDNode*> NowDead; 457 if (N->getNumValues() == RV.Val->getNumValues()) 458 DAG.ReplaceAllUsesWith(N, RV.Val, &NowDead); 459 else { 460 assert(N->getValueType(0) == RV.getValueType() && "Type mismatch"); 461 SDOperand OpV = RV; 462 DAG.ReplaceAllUsesWith(N, &OpV, &NowDead); 463 } 464 465 // Push the new node and any users onto the worklist 466 AddToWorkList(RV.Val); 467 AddUsersToWorkList(RV.Val); 468 469 // Nodes can be reintroduced into the worklist. Make sure we do not 470 // process a node that has been replaced. 471 removeFromWorkList(N); 472 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 473 removeFromWorkList(NowDead[i]); 474 475 // Finally, since the node is now dead, remove it from the graph. 476 DAG.DeleteNode(N); 477 } 478 } 479 } 480 481 // If the root changed (e.g. it was a dead load, update the root). 482 DAG.setRoot(Dummy.getValue()); 483} 484 485SDOperand DAGCombiner::visit(SDNode *N) { 486 switch(N->getOpcode()) { 487 default: break; 488 case ISD::TokenFactor: return visitTokenFactor(N); 489 case ISD::ADD: return visitADD(N); 490 case ISD::SUB: return visitSUB(N); 491 case ISD::MUL: return visitMUL(N); 492 case ISD::SDIV: return visitSDIV(N); 493 case ISD::UDIV: return visitUDIV(N); 494 case ISD::SREM: return visitSREM(N); 495 case ISD::UREM: return visitUREM(N); 496 case ISD::MULHU: return visitMULHU(N); 497 case ISD::MULHS: return visitMULHS(N); 498 case ISD::AND: return visitAND(N); 499 case ISD::OR: return visitOR(N); 500 case ISD::XOR: return visitXOR(N); 501 case ISD::SHL: return visitSHL(N); 502 case ISD::SRA: return visitSRA(N); 503 case ISD::SRL: return visitSRL(N); 504 case ISD::CTLZ: return visitCTLZ(N); 505 case ISD::CTTZ: return visitCTTZ(N); 506 case ISD::CTPOP: return visitCTPOP(N); 507 case ISD::SELECT: return visitSELECT(N); 508 case ISD::SELECT_CC: return visitSELECT_CC(N); 509 case ISD::SETCC: return visitSETCC(N); 510 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 511 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 512 case ISD::ANY_EXTEND: return visitANY_EXTEND(N); 513 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 514 case ISD::TRUNCATE: return visitTRUNCATE(N); 515 case ISD::BIT_CONVERT: return visitBIT_CONVERT(N); 516 case ISD::VBIT_CONVERT: return visitVBIT_CONVERT(N); 517 case ISD::FADD: return visitFADD(N); 518 case ISD::FSUB: return visitFSUB(N); 519 case ISD::FMUL: return visitFMUL(N); 520 case ISD::FDIV: return visitFDIV(N); 521 case ISD::FREM: return visitFREM(N); 522 case ISD::FCOPYSIGN: return visitFCOPYSIGN(N); 523 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 524 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 525 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 526 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 527 case ISD::FP_ROUND: return visitFP_ROUND(N); 528 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 529 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 530 case ISD::FNEG: return visitFNEG(N); 531 case ISD::FABS: return visitFABS(N); 532 case ISD::BRCOND: return visitBRCOND(N); 533 case ISD::BR_CC: return visitBR_CC(N); 534 case ISD::LOAD: return visitLOAD(N); 535 case ISD::STORE: return visitSTORE(N); 536 case ISD::INSERT_VECTOR_ELT: return visitINSERT_VECTOR_ELT(N); 537 case ISD::VINSERT_VECTOR_ELT: return visitVINSERT_VECTOR_ELT(N); 538 case ISD::VBUILD_VECTOR: return visitVBUILD_VECTOR(N); 539 case ISD::VECTOR_SHUFFLE: return visitVECTOR_SHUFFLE(N); 540 case ISD::VVECTOR_SHUFFLE: return visitVVECTOR_SHUFFLE(N); 541 case ISD::VADD: return visitVBinOp(N, ISD::ADD , ISD::FADD); 542 case ISD::VSUB: return visitVBinOp(N, ISD::SUB , ISD::FSUB); 543 case ISD::VMUL: return visitVBinOp(N, ISD::MUL , ISD::FMUL); 544 case ISD::VSDIV: return visitVBinOp(N, ISD::SDIV, ISD::FDIV); 545 case ISD::VUDIV: return visitVBinOp(N, ISD::UDIV, ISD::UDIV); 546 case ISD::VAND: return visitVBinOp(N, ISD::AND , ISD::AND); 547 case ISD::VOR: return visitVBinOp(N, ISD::OR , ISD::OR); 548 case ISD::VXOR: return visitVBinOp(N, ISD::XOR , ISD::XOR); 549 } 550 return SDOperand(); 551} 552 553/// getInputChainForNode - Given a node, return its input chain if it has one, 554/// otherwise return a null sd operand. 555static SDOperand getInputChainForNode(SDNode *N) { 556 if (unsigned NumOps = N->getNumOperands()) { 557 if (N->getOperand(0).getValueType() == MVT::Other) 558 return N->getOperand(0); 559 else if (N->getOperand(NumOps-1).getValueType() == MVT::Other) 560 return N->getOperand(NumOps-1); 561 for (unsigned i = 1; i < NumOps-1; ++i) 562 if (N->getOperand(i).getValueType() == MVT::Other) 563 return N->getOperand(i); 564 } 565 return SDOperand(0, 0); 566} 567 568SDOperand DAGCombiner::visitTokenFactor(SDNode *N) { 569 // If N has two operands, where one has an input chain equal to the other, 570 // the 'other' chain is redundant. 571 if (N->getNumOperands() == 2) { 572 if (getInputChainForNode(N->getOperand(0).Val) == N->getOperand(1)) 573 return N->getOperand(0); 574 if (getInputChainForNode(N->getOperand(1).Val) == N->getOperand(0)) 575 return N->getOperand(1); 576 } 577 578 579 SmallVector<SDNode *, 8> TFs; // List of token factors to visit. 580 SmallVector<SDOperand, 8> Ops; // Ops for replacing token factor. 581 bool Changed = false; // If we should replace this token factor. 582 583 // Start out with this token factor. 584 TFs.push_back(N); 585 586 // Iterate through token factors. The TFs grows when new token factors are 587 // encountered. 588 for (unsigned i = 0; i < TFs.size(); ++i) { 589 SDNode *TF = TFs[i]; 590 591 // Check each of the operands. 592 for (unsigned i = 0, ie = TF->getNumOperands(); i != ie; ++i) { 593 SDOperand Op = TF->getOperand(i); 594 595 switch (Op.getOpcode()) { 596 case ISD::EntryToken: 597 // Entry tokens don't need to be added to the list. They are 598 // rededundant. 599 Changed = true; 600 break; 601 602 case ISD::TokenFactor: 603 if ((CombinerAA || Op.hasOneUse()) && 604 std::find(TFs.begin(), TFs.end(), Op.Val) == TFs.end()) { 605 // Queue up for processing. 606 TFs.push_back(Op.Val); 607 // Clean up in case the token factor is removed. 608 AddToWorkList(Op.Val); 609 Changed = true; 610 break; 611 } 612 // Fall thru 613 614 default: 615 // Only add if not there prior. 616 if (std::find(Ops.begin(), Ops.end(), Op) == Ops.end()) 617 Ops.push_back(Op); 618 break; 619 } 620 } 621 } 622 623 SDOperand Result; 624 625 // If we've change things around then replace token factor. 626 if (Changed) { 627 if (Ops.size() == 0) { 628 // The entry token is the only possible outcome. 629 Result = DAG.getEntryNode(); 630 } else { 631 // New and improved token factor. 632 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size()); 633 } 634 635 // Don't add users to work list. 636 return CombineTo(N, Result, false); 637 } 638 639 return Result; 640} 641 642SDOperand DAGCombiner::visitADD(SDNode *N) { 643 SDOperand N0 = N->getOperand(0); 644 SDOperand N1 = N->getOperand(1); 645 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 646 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 647 MVT::ValueType VT = N0.getValueType(); 648 649 // fold (add c1, c2) -> c1+c2 650 if (N0C && N1C) 651 return DAG.getNode(ISD::ADD, VT, N0, N1); 652 // canonicalize constant to RHS 653 if (N0C && !N1C) 654 return DAG.getNode(ISD::ADD, VT, N1, N0); 655 // fold (add x, 0) -> x 656 if (N1C && N1C->isNullValue()) 657 return N0; 658 // fold ((c1-A)+c2) -> (c1+c2)-A 659 if (N1C && N0.getOpcode() == ISD::SUB) 660 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0))) 661 return DAG.getNode(ISD::SUB, VT, 662 DAG.getConstant(N1C->getValue()+N0C->getValue(), VT), 663 N0.getOperand(1)); 664 // reassociate add 665 SDOperand RADD = ReassociateOps(ISD::ADD, N0, N1); 666 if (RADD.Val != 0) 667 return RADD; 668 // fold ((0-A) + B) -> B-A 669 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 670 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 671 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 672 // fold (A + (0-B)) -> A-B 673 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 674 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 675 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 676 // fold (A+(B-A)) -> B 677 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1)) 678 return N1.getOperand(0); 679 680 if (!MVT::isVector(VT) && SimplifyDemandedBits(SDOperand(N, 0))) 681 return SDOperand(N, 0); 682 683 // fold (a+b) -> (a|b) iff a and b share no bits. 684 if (MVT::isInteger(VT) && !MVT::isVector(VT)) { 685 uint64_t LHSZero, LHSOne; 686 uint64_t RHSZero, RHSOne; 687 uint64_t Mask = MVT::getIntVTBitMask(VT); 688 TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); 689 if (LHSZero) { 690 TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); 691 692 // If all possibly-set bits on the LHS are clear on the RHS, return an OR. 693 // If all possibly-set bits on the RHS are clear on the LHS, return an OR. 694 if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) || 695 (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask)) 696 return DAG.getNode(ISD::OR, VT, N0, N1); 697 } 698 } 699 700 return SDOperand(); 701} 702 703SDOperand DAGCombiner::visitSUB(SDNode *N) { 704 SDOperand N0 = N->getOperand(0); 705 SDOperand N1 = N->getOperand(1); 706 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 707 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 708 MVT::ValueType VT = N0.getValueType(); 709 710 // fold (sub x, x) -> 0 711 if (N0 == N1) 712 return DAG.getConstant(0, N->getValueType(0)); 713 // fold (sub c1, c2) -> c1-c2 714 if (N0C && N1C) 715 return DAG.getNode(ISD::SUB, VT, N0, N1); 716 // fold (sub x, c) -> (add x, -c) 717 if (N1C) 718 return DAG.getNode(ISD::ADD, VT, N0, DAG.getConstant(-N1C->getValue(), VT)); 719 // fold (A+B)-A -> B 720 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1) 721 return N0.getOperand(1); 722 // fold (A+B)-B -> A 723 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1) 724 return N0.getOperand(0); 725 return SDOperand(); 726} 727 728SDOperand DAGCombiner::visitMUL(SDNode *N) { 729 SDOperand N0 = N->getOperand(0); 730 SDOperand N1 = N->getOperand(1); 731 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 732 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 733 MVT::ValueType VT = N0.getValueType(); 734 735 // fold (mul c1, c2) -> c1*c2 736 if (N0C && N1C) 737 return DAG.getNode(ISD::MUL, VT, N0, N1); 738 // canonicalize constant to RHS 739 if (N0C && !N1C) 740 return DAG.getNode(ISD::MUL, VT, N1, N0); 741 // fold (mul x, 0) -> 0 742 if (N1C && N1C->isNullValue()) 743 return N1; 744 // fold (mul x, -1) -> 0-x 745 if (N1C && N1C->isAllOnesValue()) 746 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 747 // fold (mul x, (1 << c)) -> x << c 748 if (N1C && isPowerOf2_64(N1C->getValue())) 749 return DAG.getNode(ISD::SHL, VT, N0, 750 DAG.getConstant(Log2_64(N1C->getValue()), 751 TLI.getShiftAmountTy())); 752 // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c 753 if (N1C && isPowerOf2_64(-N1C->getSignExtended())) { 754 // FIXME: If the input is something that is easily negated (e.g. a 755 // single-use add), we should put the negate there. 756 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), 757 DAG.getNode(ISD::SHL, VT, N0, 758 DAG.getConstant(Log2_64(-N1C->getSignExtended()), 759 TLI.getShiftAmountTy()))); 760 } 761 762 // (mul (shl X, c1), c2) -> (mul X, c2 << c1) 763 if (N1C && N0.getOpcode() == ISD::SHL && 764 isa<ConstantSDNode>(N0.getOperand(1))) { 765 SDOperand C3 = DAG.getNode(ISD::SHL, VT, N1, N0.getOperand(1)); 766 AddToWorkList(C3.Val); 767 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), C3); 768 } 769 770 // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one 771 // use. 772 { 773 SDOperand Sh(0,0), Y(0,0); 774 // Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)). 775 if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) && 776 N0.Val->hasOneUse()) { 777 Sh = N0; Y = N1; 778 } else if (N1.getOpcode() == ISD::SHL && 779 isa<ConstantSDNode>(N1.getOperand(1)) && N1.Val->hasOneUse()) { 780 Sh = N1; Y = N0; 781 } 782 if (Sh.Val) { 783 SDOperand Mul = DAG.getNode(ISD::MUL, VT, Sh.getOperand(0), Y); 784 return DAG.getNode(ISD::SHL, VT, Mul, Sh.getOperand(1)); 785 } 786 } 787 // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2) 788 if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 789 isa<ConstantSDNode>(N0.getOperand(1))) { 790 return DAG.getNode(ISD::ADD, VT, 791 DAG.getNode(ISD::MUL, VT, N0.getOperand(0), N1), 792 DAG.getNode(ISD::MUL, VT, N0.getOperand(1), N1)); 793 } 794 795 // reassociate mul 796 SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1); 797 if (RMUL.Val != 0) 798 return RMUL; 799 return SDOperand(); 800} 801 802SDOperand DAGCombiner::visitSDIV(SDNode *N) { 803 SDOperand N0 = N->getOperand(0); 804 SDOperand N1 = N->getOperand(1); 805 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 806 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 807 MVT::ValueType VT = N->getValueType(0); 808 809 // fold (sdiv c1, c2) -> c1/c2 810 if (N0C && N1C && !N1C->isNullValue()) 811 return DAG.getNode(ISD::SDIV, VT, N0, N1); 812 // fold (sdiv X, 1) -> X 813 if (N1C && N1C->getSignExtended() == 1LL) 814 return N0; 815 // fold (sdiv X, -1) -> 0-X 816 if (N1C && N1C->isAllOnesValue()) 817 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 818 // If we know the sign bits of both operands are zero, strength reduce to a 819 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 820 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 821 if (TLI.MaskedValueIsZero(N1, SignBit) && 822 TLI.MaskedValueIsZero(N0, SignBit)) 823 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 824 // fold (sdiv X, pow2) -> simple ops after legalize 825 if (N1C && N1C->getValue() && !TLI.isIntDivCheap() && 826 (isPowerOf2_64(N1C->getSignExtended()) || 827 isPowerOf2_64(-N1C->getSignExtended()))) { 828 // If dividing by powers of two is cheap, then don't perform the following 829 // fold. 830 if (TLI.isPow2DivCheap()) 831 return SDOperand(); 832 int64_t pow2 = N1C->getSignExtended(); 833 int64_t abs2 = pow2 > 0 ? pow2 : -pow2; 834 unsigned lg2 = Log2_64(abs2); 835 // Splat the sign bit into the register 836 SDOperand SGN = DAG.getNode(ISD::SRA, VT, N0, 837 DAG.getConstant(MVT::getSizeInBits(VT)-1, 838 TLI.getShiftAmountTy())); 839 AddToWorkList(SGN.Val); 840 // Add (N0 < 0) ? abs2 - 1 : 0; 841 SDOperand SRL = DAG.getNode(ISD::SRL, VT, SGN, 842 DAG.getConstant(MVT::getSizeInBits(VT)-lg2, 843 TLI.getShiftAmountTy())); 844 SDOperand ADD = DAG.getNode(ISD::ADD, VT, N0, SRL); 845 AddToWorkList(SRL.Val); 846 AddToWorkList(ADD.Val); // Divide by pow2 847 SDOperand SRA = DAG.getNode(ISD::SRA, VT, ADD, 848 DAG.getConstant(lg2, TLI.getShiftAmountTy())); 849 // If we're dividing by a positive value, we're done. Otherwise, we must 850 // negate the result. 851 if (pow2 > 0) 852 return SRA; 853 AddToWorkList(SRA.Val); 854 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA); 855 } 856 // if integer divide is expensive and we satisfy the requirements, emit an 857 // alternate sequence. 858 if (N1C && (N1C->getSignExtended() < -1 || N1C->getSignExtended() > 1) && 859 !TLI.isIntDivCheap()) { 860 SDOperand Op = BuildSDIV(N); 861 if (Op.Val) return Op; 862 } 863 return SDOperand(); 864} 865 866SDOperand DAGCombiner::visitUDIV(SDNode *N) { 867 SDOperand N0 = N->getOperand(0); 868 SDOperand N1 = N->getOperand(1); 869 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 870 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 871 MVT::ValueType VT = N->getValueType(0); 872 873 // fold (udiv c1, c2) -> c1/c2 874 if (N0C && N1C && !N1C->isNullValue()) 875 return DAG.getNode(ISD::UDIV, VT, N0, N1); 876 // fold (udiv x, (1 << c)) -> x >>u c 877 if (N1C && isPowerOf2_64(N1C->getValue())) 878 return DAG.getNode(ISD::SRL, VT, N0, 879 DAG.getConstant(Log2_64(N1C->getValue()), 880 TLI.getShiftAmountTy())); 881 // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2 882 if (N1.getOpcode() == ISD::SHL) { 883 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 884 if (isPowerOf2_64(SHC->getValue())) { 885 MVT::ValueType ADDVT = N1.getOperand(1).getValueType(); 886 SDOperand Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1), 887 DAG.getConstant(Log2_64(SHC->getValue()), 888 ADDVT)); 889 AddToWorkList(Add.Val); 890 return DAG.getNode(ISD::SRL, VT, N0, Add); 891 } 892 } 893 } 894 // fold (udiv x, c) -> alternate 895 if (N1C && N1C->getValue() && !TLI.isIntDivCheap()) { 896 SDOperand Op = BuildUDIV(N); 897 if (Op.Val) return Op; 898 } 899 return SDOperand(); 900} 901 902SDOperand DAGCombiner::visitSREM(SDNode *N) { 903 SDOperand N0 = N->getOperand(0); 904 SDOperand N1 = N->getOperand(1); 905 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 906 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 907 MVT::ValueType VT = N->getValueType(0); 908 909 // fold (srem c1, c2) -> c1%c2 910 if (N0C && N1C && !N1C->isNullValue()) 911 return DAG.getNode(ISD::SREM, VT, N0, N1); 912 // If we know the sign bits of both operands are zero, strength reduce to a 913 // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15 914 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 915 if (TLI.MaskedValueIsZero(N1, SignBit) && 916 TLI.MaskedValueIsZero(N0, SignBit)) 917 return DAG.getNode(ISD::UREM, VT, N0, N1); 918 919 // Unconditionally lower X%C -> X-X/C*C. This allows the X/C logic to hack on 920 // the remainder operation. 921 if (N1C && !N1C->isNullValue()) { 922 SDOperand Div = DAG.getNode(ISD::SDIV, VT, N0, N1); 923 SDOperand Mul = DAG.getNode(ISD::MUL, VT, Div, N1); 924 SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul); 925 AddToWorkList(Div.Val); 926 AddToWorkList(Mul.Val); 927 return Sub; 928 } 929 930 return SDOperand(); 931} 932 933SDOperand DAGCombiner::visitUREM(SDNode *N) { 934 SDOperand N0 = N->getOperand(0); 935 SDOperand N1 = N->getOperand(1); 936 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 937 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 938 MVT::ValueType VT = N->getValueType(0); 939 940 // fold (urem c1, c2) -> c1%c2 941 if (N0C && N1C && !N1C->isNullValue()) 942 return DAG.getNode(ISD::UREM, VT, N0, N1); 943 // fold (urem x, pow2) -> (and x, pow2-1) 944 if (N1C && !N1C->isNullValue() && isPowerOf2_64(N1C->getValue())) 945 return DAG.getNode(ISD::AND, VT, N0, DAG.getConstant(N1C->getValue()-1,VT)); 946 // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1)) 947 if (N1.getOpcode() == ISD::SHL) { 948 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 949 if (isPowerOf2_64(SHC->getValue())) { 950 SDOperand Add = DAG.getNode(ISD::ADD, VT, N1,DAG.getConstant(~0ULL,VT)); 951 AddToWorkList(Add.Val); 952 return DAG.getNode(ISD::AND, VT, N0, Add); 953 } 954 } 955 } 956 957 // Unconditionally lower X%C -> X-X/C*C. This allows the X/C logic to hack on 958 // the remainder operation. 959 if (N1C && !N1C->isNullValue()) { 960 SDOperand Div = DAG.getNode(ISD::UDIV, VT, N0, N1); 961 SDOperand Mul = DAG.getNode(ISD::MUL, VT, Div, N1); 962 SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul); 963 AddToWorkList(Div.Val); 964 AddToWorkList(Mul.Val); 965 return Sub; 966 } 967 968 return SDOperand(); 969} 970 971SDOperand DAGCombiner::visitMULHS(SDNode *N) { 972 SDOperand N0 = N->getOperand(0); 973 SDOperand N1 = N->getOperand(1); 974 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 975 976 // fold (mulhs x, 0) -> 0 977 if (N1C && N1C->isNullValue()) 978 return N1; 979 // fold (mulhs x, 1) -> (sra x, size(x)-1) 980 if (N1C && N1C->getValue() == 1) 981 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 982 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 983 TLI.getShiftAmountTy())); 984 return SDOperand(); 985} 986 987SDOperand DAGCombiner::visitMULHU(SDNode *N) { 988 SDOperand N0 = N->getOperand(0); 989 SDOperand N1 = N->getOperand(1); 990 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 991 992 // fold (mulhu x, 0) -> 0 993 if (N1C && N1C->isNullValue()) 994 return N1; 995 // fold (mulhu x, 1) -> 0 996 if (N1C && N1C->getValue() == 1) 997 return DAG.getConstant(0, N0.getValueType()); 998 return SDOperand(); 999} 1000 1001/// SimplifyBinOpWithSameOpcodeHands - If this is a binary operator with 1002/// two operands of the same opcode, try to simplify it. 1003SDOperand DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) { 1004 SDOperand N0 = N->getOperand(0), N1 = N->getOperand(1); 1005 MVT::ValueType VT = N0.getValueType(); 1006 assert(N0.getOpcode() == N1.getOpcode() && "Bad input!"); 1007 1008 // For each of OP in AND/OR/XOR: 1009 // fold (OP (zext x), (zext y)) -> (zext (OP x, y)) 1010 // fold (OP (sext x), (sext y)) -> (sext (OP x, y)) 1011 // fold (OP (aext x), (aext y)) -> (aext (OP x, y)) 1012 // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y)) 1013 if ((N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND|| 1014 N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::TRUNCATE) && 1015 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 1016 SDOperand ORNode = DAG.getNode(N->getOpcode(), 1017 N0.getOperand(0).getValueType(), 1018 N0.getOperand(0), N1.getOperand(0)); 1019 AddToWorkList(ORNode.Val); 1020 return DAG.getNode(N0.getOpcode(), VT, ORNode); 1021 } 1022 1023 // For each of OP in SHL/SRL/SRA/AND... 1024 // fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z) 1025 // fold (or (OP x, z), (OP y, z)) -> (OP (or x, y), z) 1026 // fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z) 1027 if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL || 1028 N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) && 1029 N0.getOperand(1) == N1.getOperand(1)) { 1030 SDOperand ORNode = DAG.getNode(N->getOpcode(), 1031 N0.getOperand(0).getValueType(), 1032 N0.getOperand(0), N1.getOperand(0)); 1033 AddToWorkList(ORNode.Val); 1034 return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1)); 1035 } 1036 1037 return SDOperand(); 1038} 1039 1040SDOperand DAGCombiner::visitAND(SDNode *N) { 1041 SDOperand N0 = N->getOperand(0); 1042 SDOperand N1 = N->getOperand(1); 1043 SDOperand LL, LR, RL, RR, CC0, CC1; 1044 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1045 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1046 MVT::ValueType VT = N1.getValueType(); 1047 1048 // fold (and c1, c2) -> c1&c2 1049 if (N0C && N1C) 1050 return DAG.getNode(ISD::AND, VT, N0, N1); 1051 // canonicalize constant to RHS 1052 if (N0C && !N1C) 1053 return DAG.getNode(ISD::AND, VT, N1, N0); 1054 // fold (and x, -1) -> x 1055 if (N1C && N1C->isAllOnesValue()) 1056 return N0; 1057 // if (and x, c) is known to be zero, return 0 1058 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) 1059 return DAG.getConstant(0, VT); 1060 // reassociate and 1061 SDOperand RAND = ReassociateOps(ISD::AND, N0, N1); 1062 if (RAND.Val != 0) 1063 return RAND; 1064 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 1065 if (N1C && N0.getOpcode() == ISD::OR) 1066 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 1067 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 1068 return N1; 1069 // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits. 1070 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 1071 unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType()); 1072 if (TLI.MaskedValueIsZero(N0.getOperand(0), 1073 ~N1C->getValue() & InMask)) { 1074 SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(), 1075 N0.getOperand(0)); 1076 1077 // Replace uses of the AND with uses of the Zero extend node. 1078 CombineTo(N, Zext); 1079 1080 // We actually want to replace all uses of the any_extend with the 1081 // zero_extend, to avoid duplicating things. This will later cause this 1082 // AND to be folded. 1083 CombineTo(N0.Val, Zext); 1084 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1085 } 1086 } 1087 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 1088 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1089 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1090 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1091 1092 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1093 MVT::isInteger(LL.getValueType())) { 1094 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 1095 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 1096 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1097 AddToWorkList(ORNode.Val); 1098 return DAG.getSetCC(VT, ORNode, LR, Op1); 1099 } 1100 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 1101 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 1102 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1103 AddToWorkList(ANDNode.Val); 1104 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1105 } 1106 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 1107 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 1108 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1109 AddToWorkList(ORNode.Val); 1110 return DAG.getSetCC(VT, ORNode, LR, Op1); 1111 } 1112 } 1113 // canonicalize equivalent to ll == rl 1114 if (LL == RR && LR == RL) { 1115 Op1 = ISD::getSetCCSwappedOperands(Op1); 1116 std::swap(RL, RR); 1117 } 1118 if (LL == RL && LR == RR) { 1119 bool isInteger = MVT::isInteger(LL.getValueType()); 1120 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 1121 if (Result != ISD::SETCC_INVALID) 1122 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1123 } 1124 } 1125 1126 // Simplify: and (op x...), (op y...) -> (op (and x, y)) 1127 if (N0.getOpcode() == N1.getOpcode()) { 1128 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1129 if (Tmp.Val) return Tmp; 1130 } 1131 1132 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 1133 // fold (and (sra)) -> (and (srl)) when possible. 1134 if (!MVT::isVector(VT) && 1135 SimplifyDemandedBits(SDOperand(N, 0))) 1136 return SDOperand(N, 0); 1137 // fold (zext_inreg (extload x)) -> (zextload x) 1138 if (ISD::isEXTLoad(N0.Val)) { 1139 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1140 MVT::ValueType EVT = LN0->getLoadedVT(); 1141 // If we zero all the possible extended bits, then we can turn this into 1142 // a zextload if we are running before legalize or the operation is legal. 1143 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1144 (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) { 1145 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 1146 LN0->getBasePtr(), LN0->getSrcValue(), 1147 LN0->getSrcValueOffset(), EVT); 1148 AddToWorkList(N); 1149 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1150 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1151 } 1152 } 1153 // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use 1154 if (ISD::isSEXTLoad(N0.Val) && N0.hasOneUse()) { 1155 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1156 MVT::ValueType EVT = LN0->getLoadedVT(); 1157 // If we zero all the possible extended bits, then we can turn this into 1158 // a zextload if we are running before legalize or the operation is legal. 1159 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1160 (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) { 1161 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 1162 LN0->getBasePtr(), LN0->getSrcValue(), 1163 LN0->getSrcValueOffset(), EVT); 1164 AddToWorkList(N); 1165 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1166 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1167 } 1168 } 1169 1170 // fold (and (load x), 255) -> (zextload x, i8) 1171 // fold (and (extload x, i16), 255) -> (zextload x, i8) 1172 if (N1C && N0.getOpcode() == ISD::LOAD) { 1173 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1174 if (LN0->getExtensionType() != ISD::SEXTLOAD && 1175 N0.hasOneUse()) { 1176 MVT::ValueType EVT, LoadedVT; 1177 if (N1C->getValue() == 255) 1178 EVT = MVT::i8; 1179 else if (N1C->getValue() == 65535) 1180 EVT = MVT::i16; 1181 else if (N1C->getValue() == ~0U) 1182 EVT = MVT::i32; 1183 else 1184 EVT = MVT::Other; 1185 1186 LoadedVT = LN0->getLoadedVT(); 1187 if (EVT != MVT::Other && LoadedVT > EVT && 1188 (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) { 1189 MVT::ValueType PtrType = N0.getOperand(1).getValueType(); 1190 // For big endian targets, we need to add an offset to the pointer to 1191 // load the correct bytes. For little endian systems, we merely need to 1192 // read fewer bytes from the same pointer. 1193 unsigned PtrOff = 1194 (MVT::getSizeInBits(LoadedVT) - MVT::getSizeInBits(EVT)) / 8; 1195 SDOperand NewPtr = LN0->getBasePtr(); 1196 if (!TLI.isLittleEndian()) 1197 NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr, 1198 DAG.getConstant(PtrOff, PtrType)); 1199 AddToWorkList(NewPtr.Val); 1200 SDOperand Load = 1201 DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), NewPtr, 1202 LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT); 1203 AddToWorkList(N); 1204 CombineTo(N0.Val, Load, Load.getValue(1)); 1205 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1206 } 1207 } 1208 } 1209 1210 return SDOperand(); 1211} 1212 1213SDOperand DAGCombiner::visitOR(SDNode *N) { 1214 SDOperand N0 = N->getOperand(0); 1215 SDOperand N1 = N->getOperand(1); 1216 SDOperand LL, LR, RL, RR, CC0, CC1; 1217 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1218 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1219 MVT::ValueType VT = N1.getValueType(); 1220 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1221 1222 // fold (or c1, c2) -> c1|c2 1223 if (N0C && N1C) 1224 return DAG.getNode(ISD::OR, VT, N0, N1); 1225 // canonicalize constant to RHS 1226 if (N0C && !N1C) 1227 return DAG.getNode(ISD::OR, VT, N1, N0); 1228 // fold (or x, 0) -> x 1229 if (N1C && N1C->isNullValue()) 1230 return N0; 1231 // fold (or x, -1) -> -1 1232 if (N1C && N1C->isAllOnesValue()) 1233 return N1; 1234 // fold (or x, c) -> c iff (x & ~c) == 0 1235 if (N1C && 1236 TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) 1237 return N1; 1238 // reassociate or 1239 SDOperand ROR = ReassociateOps(ISD::OR, N0, N1); 1240 if (ROR.Val != 0) 1241 return ROR; 1242 // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2) 1243 if (N1C && N0.getOpcode() == ISD::AND && N0.Val->hasOneUse() && 1244 isa<ConstantSDNode>(N0.getOperand(1))) { 1245 ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1)); 1246 return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0), 1247 N1), 1248 DAG.getConstant(N1C->getValue() | C1->getValue(), VT)); 1249 } 1250 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 1251 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1252 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1253 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1254 1255 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1256 MVT::isInteger(LL.getValueType())) { 1257 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 1258 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 1259 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 1260 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 1261 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1262 AddToWorkList(ORNode.Val); 1263 return DAG.getSetCC(VT, ORNode, LR, Op1); 1264 } 1265 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 1266 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 1267 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 1268 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 1269 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1270 AddToWorkList(ANDNode.Val); 1271 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1272 } 1273 } 1274 // canonicalize equivalent to ll == rl 1275 if (LL == RR && LR == RL) { 1276 Op1 = ISD::getSetCCSwappedOperands(Op1); 1277 std::swap(RL, RR); 1278 } 1279 if (LL == RL && LR == RR) { 1280 bool isInteger = MVT::isInteger(LL.getValueType()); 1281 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 1282 if (Result != ISD::SETCC_INVALID) 1283 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1284 } 1285 } 1286 1287 // Simplify: or (op x...), (op y...) -> (op (or x, y)) 1288 if (N0.getOpcode() == N1.getOpcode()) { 1289 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1290 if (Tmp.Val) return Tmp; 1291 } 1292 1293 // (X & C1) | (Y & C2) -> (X|Y) & C3 if possible. 1294 if (N0.getOpcode() == ISD::AND && 1295 N1.getOpcode() == ISD::AND && 1296 N0.getOperand(1).getOpcode() == ISD::Constant && 1297 N1.getOperand(1).getOpcode() == ISD::Constant && 1298 // Don't increase # computations. 1299 (N0.Val->hasOneUse() || N1.Val->hasOneUse())) { 1300 // We can only do this xform if we know that bits from X that are set in C2 1301 // but not in C1 are already zero. Likewise for Y. 1302 uint64_t LHSMask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1303 uint64_t RHSMask = cast<ConstantSDNode>(N1.getOperand(1))->getValue(); 1304 1305 if (TLI.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) && 1306 TLI.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) { 1307 SDOperand X =DAG.getNode(ISD::OR, VT, N0.getOperand(0), N1.getOperand(0)); 1308 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(LHSMask|RHSMask, VT)); 1309 } 1310 } 1311 1312 1313 // See if this is some rotate idiom. 1314 if (SDNode *Rot = MatchRotate(N0, N1)) 1315 return SDOperand(Rot, 0); 1316 1317 return SDOperand(); 1318} 1319 1320 1321/// MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present. 1322static bool MatchRotateHalf(SDOperand Op, SDOperand &Shift, SDOperand &Mask) { 1323 if (Op.getOpcode() == ISD::AND) { 1324 if (isa<ConstantSDNode>(Op.getOperand(1))) { 1325 Mask = Op.getOperand(1); 1326 Op = Op.getOperand(0); 1327 } else { 1328 return false; 1329 } 1330 } 1331 1332 if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) { 1333 Shift = Op; 1334 return true; 1335 } 1336 return false; 1337} 1338 1339 1340// MatchRotate - Handle an 'or' of two operands. If this is one of the many 1341// idioms for rotate, and if the target supports rotation instructions, generate 1342// a rot[lr]. 1343SDNode *DAGCombiner::MatchRotate(SDOperand LHS, SDOperand RHS) { 1344 // Must be a legal type. Expanded an promoted things won't work with rotates. 1345 MVT::ValueType VT = LHS.getValueType(); 1346 if (!TLI.isTypeLegal(VT)) return 0; 1347 1348 // The target must have at least one rotate flavor. 1349 bool HasROTL = TLI.isOperationLegal(ISD::ROTL, VT); 1350 bool HasROTR = TLI.isOperationLegal(ISD::ROTR, VT); 1351 if (!HasROTL && !HasROTR) return 0; 1352 1353 // Match "(X shl/srl V1) & V2" where V2 may not be present. 1354 SDOperand LHSShift; // The shift. 1355 SDOperand LHSMask; // AND value if any. 1356 if (!MatchRotateHalf(LHS, LHSShift, LHSMask)) 1357 return 0; // Not part of a rotate. 1358 1359 SDOperand RHSShift; // The shift. 1360 SDOperand RHSMask; // AND value if any. 1361 if (!MatchRotateHalf(RHS, RHSShift, RHSMask)) 1362 return 0; // Not part of a rotate. 1363 1364 if (LHSShift.getOperand(0) != RHSShift.getOperand(0)) 1365 return 0; // Not shifting the same value. 1366 1367 if (LHSShift.getOpcode() == RHSShift.getOpcode()) 1368 return 0; // Shifts must disagree. 1369 1370 // Canonicalize shl to left side in a shl/srl pair. 1371 if (RHSShift.getOpcode() == ISD::SHL) { 1372 std::swap(LHS, RHS); 1373 std::swap(LHSShift, RHSShift); 1374 std::swap(LHSMask , RHSMask ); 1375 } 1376 1377 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1378 1379 // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1) 1380 // fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2) 1381 if (LHSShift.getOperand(1).getOpcode() == ISD::Constant && 1382 RHSShift.getOperand(1).getOpcode() == ISD::Constant) { 1383 uint64_t LShVal = cast<ConstantSDNode>(LHSShift.getOperand(1))->getValue(); 1384 uint64_t RShVal = cast<ConstantSDNode>(RHSShift.getOperand(1))->getValue(); 1385 if ((LShVal + RShVal) != OpSizeInBits) 1386 return 0; 1387 1388 SDOperand Rot; 1389 if (HasROTL) 1390 Rot = DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0), 1391 LHSShift.getOperand(1)); 1392 else 1393 Rot = DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0), 1394 RHSShift.getOperand(1)); 1395 1396 // If there is an AND of either shifted operand, apply it to the result. 1397 if (LHSMask.Val || RHSMask.Val) { 1398 uint64_t Mask = MVT::getIntVTBitMask(VT); 1399 1400 if (LHSMask.Val) { 1401 uint64_t RHSBits = (1ULL << LShVal)-1; 1402 Mask &= cast<ConstantSDNode>(LHSMask)->getValue() | RHSBits; 1403 } 1404 if (RHSMask.Val) { 1405 uint64_t LHSBits = ~((1ULL << (OpSizeInBits-RShVal))-1); 1406 Mask &= cast<ConstantSDNode>(RHSMask)->getValue() | LHSBits; 1407 } 1408 1409 Rot = DAG.getNode(ISD::AND, VT, Rot, DAG.getConstant(Mask, VT)); 1410 } 1411 1412 return Rot.Val; 1413 } 1414 1415 // If there is a mask here, and we have a variable shift, we can't be sure 1416 // that we're masking out the right stuff. 1417 if (LHSMask.Val || RHSMask.Val) 1418 return 0; 1419 1420 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y) 1421 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotr x, (sub 32, y)) 1422 if (RHSShift.getOperand(1).getOpcode() == ISD::SUB && 1423 LHSShift.getOperand(1) == RHSShift.getOperand(1).getOperand(1)) { 1424 if (ConstantSDNode *SUBC = 1425 dyn_cast<ConstantSDNode>(RHSShift.getOperand(1).getOperand(0))) { 1426 if (SUBC->getValue() == OpSizeInBits) 1427 if (HasROTL) 1428 return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0), 1429 LHSShift.getOperand(1)).Val; 1430 else 1431 return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0), 1432 LHSShift.getOperand(1)).Val; 1433 } 1434 } 1435 1436 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y) 1437 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotl x, (sub 32, y)) 1438 if (LHSShift.getOperand(1).getOpcode() == ISD::SUB && 1439 RHSShift.getOperand(1) == LHSShift.getOperand(1).getOperand(1)) { 1440 if (ConstantSDNode *SUBC = 1441 dyn_cast<ConstantSDNode>(LHSShift.getOperand(1).getOperand(0))) { 1442 if (SUBC->getValue() == OpSizeInBits) 1443 if (HasROTL) 1444 return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0), 1445 LHSShift.getOperand(1)).Val; 1446 else 1447 return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0), 1448 RHSShift.getOperand(1)).Val; 1449 } 1450 } 1451 1452 return 0; 1453} 1454 1455 1456SDOperand DAGCombiner::visitXOR(SDNode *N) { 1457 SDOperand N0 = N->getOperand(0); 1458 SDOperand N1 = N->getOperand(1); 1459 SDOperand LHS, RHS, CC; 1460 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1461 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1462 MVT::ValueType VT = N0.getValueType(); 1463 1464 // fold (xor c1, c2) -> c1^c2 1465 if (N0C && N1C) 1466 return DAG.getNode(ISD::XOR, VT, N0, N1); 1467 // canonicalize constant to RHS 1468 if (N0C && !N1C) 1469 return DAG.getNode(ISD::XOR, VT, N1, N0); 1470 // fold (xor x, 0) -> x 1471 if (N1C && N1C->isNullValue()) 1472 return N0; 1473 // reassociate xor 1474 SDOperand RXOR = ReassociateOps(ISD::XOR, N0, N1); 1475 if (RXOR.Val != 0) 1476 return RXOR; 1477 // fold !(x cc y) -> (x !cc y) 1478 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 1479 bool isInt = MVT::isInteger(LHS.getValueType()); 1480 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 1481 isInt); 1482 if (N0.getOpcode() == ISD::SETCC) 1483 return DAG.getSetCC(VT, LHS, RHS, NotCC); 1484 if (N0.getOpcode() == ISD::SELECT_CC) 1485 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 1486 assert(0 && "Unhandled SetCC Equivalent!"); 1487 abort(); 1488 } 1489 // fold !(x or y) -> (!x and !y) iff x or y are setcc 1490 if (N1C && N1C->getValue() == 1 && VT == MVT::i1 && 1491 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1492 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1493 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 1494 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1495 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1496 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1497 AddToWorkList(LHS.Val); AddToWorkList(RHS.Val); 1498 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1499 } 1500 } 1501 // fold !(x or y) -> (!x and !y) iff x or y are constants 1502 if (N1C && N1C->isAllOnesValue() && 1503 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1504 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1505 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 1506 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1507 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1508 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1509 AddToWorkList(LHS.Val); AddToWorkList(RHS.Val); 1510 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1511 } 1512 } 1513 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 1514 if (N1C && N0.getOpcode() == ISD::XOR) { 1515 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 1516 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 1517 if (N00C) 1518 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 1519 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 1520 if (N01C) 1521 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 1522 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 1523 } 1524 // fold (xor x, x) -> 0 1525 if (N0 == N1) { 1526 if (!MVT::isVector(VT)) { 1527 return DAG.getConstant(0, VT); 1528 } else if (!AfterLegalize || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)) { 1529 // Produce a vector of zeros. 1530 SDOperand El = DAG.getConstant(0, MVT::getVectorBaseType(VT)); 1531 std::vector<SDOperand> Ops(MVT::getVectorNumElements(VT), El); 1532 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 1533 } 1534 } 1535 1536 // Simplify: xor (op x...), (op y...) -> (op (xor x, y)) 1537 if (N0.getOpcode() == N1.getOpcode()) { 1538 SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1539 if (Tmp.Val) return Tmp; 1540 } 1541 1542 // Simplify the expression using non-local knowledge. 1543 if (!MVT::isVector(VT) && 1544 SimplifyDemandedBits(SDOperand(N, 0))) 1545 return SDOperand(N, 0); 1546 1547 return SDOperand(); 1548} 1549 1550SDOperand DAGCombiner::visitSHL(SDNode *N) { 1551 SDOperand N0 = N->getOperand(0); 1552 SDOperand N1 = N->getOperand(1); 1553 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1554 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1555 MVT::ValueType VT = N0.getValueType(); 1556 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1557 1558 // fold (shl c1, c2) -> c1<<c2 1559 if (N0C && N1C) 1560 return DAG.getNode(ISD::SHL, VT, N0, N1); 1561 // fold (shl 0, x) -> 0 1562 if (N0C && N0C->isNullValue()) 1563 return N0; 1564 // fold (shl x, c >= size(x)) -> undef 1565 if (N1C && N1C->getValue() >= OpSizeInBits) 1566 return DAG.getNode(ISD::UNDEF, VT); 1567 // fold (shl x, 0) -> x 1568 if (N1C && N1C->isNullValue()) 1569 return N0; 1570 // if (shl x, c) is known to be zero, return 0 1571 if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT))) 1572 return DAG.getConstant(0, VT); 1573 if (SimplifyDemandedBits(SDOperand(N, 0))) 1574 return SDOperand(N, 0); 1575 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 1576 if (N1C && N0.getOpcode() == ISD::SHL && 1577 N0.getOperand(1).getOpcode() == ISD::Constant) { 1578 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1579 uint64_t c2 = N1C->getValue(); 1580 if (c1 + c2 > OpSizeInBits) 1581 return DAG.getConstant(0, VT); 1582 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 1583 DAG.getConstant(c1 + c2, N1.getValueType())); 1584 } 1585 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 1586 // (srl (and x, -1 << c1), c1-c2) 1587 if (N1C && N0.getOpcode() == ISD::SRL && 1588 N0.getOperand(1).getOpcode() == ISD::Constant) { 1589 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1590 uint64_t c2 = N1C->getValue(); 1591 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1592 DAG.getConstant(~0ULL << c1, VT)); 1593 if (c2 > c1) 1594 return DAG.getNode(ISD::SHL, VT, Mask, 1595 DAG.getConstant(c2-c1, N1.getValueType())); 1596 else 1597 return DAG.getNode(ISD::SRL, VT, Mask, 1598 DAG.getConstant(c1-c2, N1.getValueType())); 1599 } 1600 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 1601 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 1602 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1603 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 1604 // fold (shl (add x, c1), c2) -> (add (shl x, c2), c1<<c2) 1605 if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 1606 isa<ConstantSDNode>(N0.getOperand(1))) { 1607 return DAG.getNode(ISD::ADD, VT, 1608 DAG.getNode(ISD::SHL, VT, N0.getOperand(0), N1), 1609 DAG.getNode(ISD::SHL, VT, N0.getOperand(1), N1)); 1610 } 1611 return SDOperand(); 1612} 1613 1614SDOperand DAGCombiner::visitSRA(SDNode *N) { 1615 SDOperand N0 = N->getOperand(0); 1616 SDOperand N1 = N->getOperand(1); 1617 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1618 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1619 MVT::ValueType VT = N0.getValueType(); 1620 1621 // fold (sra c1, c2) -> c1>>c2 1622 if (N0C && N1C) 1623 return DAG.getNode(ISD::SRA, VT, N0, N1); 1624 // fold (sra 0, x) -> 0 1625 if (N0C && N0C->isNullValue()) 1626 return N0; 1627 // fold (sra -1, x) -> -1 1628 if (N0C && N0C->isAllOnesValue()) 1629 return N0; 1630 // fold (sra x, c >= size(x)) -> undef 1631 if (N1C && N1C->getValue() >= MVT::getSizeInBits(VT)) 1632 return DAG.getNode(ISD::UNDEF, VT); 1633 // fold (sra x, 0) -> x 1634 if (N1C && N1C->isNullValue()) 1635 return N0; 1636 // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports 1637 // sext_inreg. 1638 if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) { 1639 unsigned LowBits = MVT::getSizeInBits(VT) - (unsigned)N1C->getValue(); 1640 MVT::ValueType EVT; 1641 switch (LowBits) { 1642 default: EVT = MVT::Other; break; 1643 case 1: EVT = MVT::i1; break; 1644 case 8: EVT = MVT::i8; break; 1645 case 16: EVT = MVT::i16; break; 1646 case 32: EVT = MVT::i32; break; 1647 } 1648 if (EVT > MVT::Other && TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT)) 1649 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), 1650 DAG.getValueType(EVT)); 1651 } 1652 1653 // fold (sra (sra x, c1), c2) -> (sra x, c1+c2) 1654 if (N1C && N0.getOpcode() == ISD::SRA) { 1655 if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1656 unsigned Sum = N1C->getValue() + C1->getValue(); 1657 if (Sum >= MVT::getSizeInBits(VT)) Sum = MVT::getSizeInBits(VT)-1; 1658 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), 1659 DAG.getConstant(Sum, N1C->getValueType(0))); 1660 } 1661 } 1662 1663 // Simplify, based on bits shifted out of the LHS. 1664 if (N1C && SimplifyDemandedBits(SDOperand(N, 0))) 1665 return SDOperand(N, 0); 1666 1667 1668 // If the sign bit is known to be zero, switch this to a SRL. 1669 if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT))) 1670 return DAG.getNode(ISD::SRL, VT, N0, N1); 1671 return SDOperand(); 1672} 1673 1674SDOperand DAGCombiner::visitSRL(SDNode *N) { 1675 SDOperand N0 = N->getOperand(0); 1676 SDOperand N1 = N->getOperand(1); 1677 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1678 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1679 MVT::ValueType VT = N0.getValueType(); 1680 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1681 1682 // fold (srl c1, c2) -> c1 >>u c2 1683 if (N0C && N1C) 1684 return DAG.getNode(ISD::SRL, VT, N0, N1); 1685 // fold (srl 0, x) -> 0 1686 if (N0C && N0C->isNullValue()) 1687 return N0; 1688 // fold (srl x, c >= size(x)) -> undef 1689 if (N1C && N1C->getValue() >= OpSizeInBits) 1690 return DAG.getNode(ISD::UNDEF, VT); 1691 // fold (srl x, 0) -> x 1692 if (N1C && N1C->isNullValue()) 1693 return N0; 1694 // if (srl x, c) is known to be zero, return 0 1695 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) 1696 return DAG.getConstant(0, VT); 1697 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 1698 if (N1C && N0.getOpcode() == ISD::SRL && 1699 N0.getOperand(1).getOpcode() == ISD::Constant) { 1700 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1701 uint64_t c2 = N1C->getValue(); 1702 if (c1 + c2 > OpSizeInBits) 1703 return DAG.getConstant(0, VT); 1704 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 1705 DAG.getConstant(c1 + c2, N1.getValueType())); 1706 } 1707 1708 // fold (srl (anyextend x), c) -> (anyextend (srl x, c)) 1709 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 1710 // Shifting in all undef bits? 1711 MVT::ValueType SmallVT = N0.getOperand(0).getValueType(); 1712 if (N1C->getValue() >= MVT::getSizeInBits(SmallVT)) 1713 return DAG.getNode(ISD::UNDEF, VT); 1714 1715 SDOperand SmallShift = DAG.getNode(ISD::SRL, SmallVT, N0.getOperand(0), N1); 1716 AddToWorkList(SmallShift.Val); 1717 return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift); 1718 } 1719 1720 // fold (srl (sra X, Y), 31) -> (srl X, 31). This srl only looks at the sign 1721 // bit, which is unmodified by sra. 1722 if (N1C && N1C->getValue()+1 == MVT::getSizeInBits(VT)) { 1723 if (N0.getOpcode() == ISD::SRA) 1724 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), N1); 1725 } 1726 1727 // fold (srl (ctlz x), "5") -> x iff x has one bit set (the low bit). 1728 if (N1C && N0.getOpcode() == ISD::CTLZ && 1729 N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) { 1730 uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT); 1731 TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne); 1732 1733 // If any of the input bits are KnownOne, then the input couldn't be all 1734 // zeros, thus the result of the srl will always be zero. 1735 if (KnownOne) return DAG.getConstant(0, VT); 1736 1737 // If all of the bits input the to ctlz node are known to be zero, then 1738 // the result of the ctlz is "32" and the result of the shift is one. 1739 uint64_t UnknownBits = ~KnownZero & Mask; 1740 if (UnknownBits == 0) return DAG.getConstant(1, VT); 1741 1742 // Otherwise, check to see if there is exactly one bit input to the ctlz. 1743 if ((UnknownBits & (UnknownBits-1)) == 0) { 1744 // Okay, we know that only that the single bit specified by UnknownBits 1745 // could be set on input to the CTLZ node. If this bit is set, the SRL 1746 // will return 0, if it is clear, it returns 1. Change the CTLZ/SRL pair 1747 // to an SRL,XOR pair, which is likely to simplify more. 1748 unsigned ShAmt = CountTrailingZeros_64(UnknownBits); 1749 SDOperand Op = N0.getOperand(0); 1750 if (ShAmt) { 1751 Op = DAG.getNode(ISD::SRL, VT, Op, 1752 DAG.getConstant(ShAmt, TLI.getShiftAmountTy())); 1753 AddToWorkList(Op.Val); 1754 } 1755 return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT)); 1756 } 1757 } 1758 1759 return SDOperand(); 1760} 1761 1762SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 1763 SDOperand N0 = N->getOperand(0); 1764 MVT::ValueType VT = N->getValueType(0); 1765 1766 // fold (ctlz c1) -> c2 1767 if (isa<ConstantSDNode>(N0)) 1768 return DAG.getNode(ISD::CTLZ, VT, N0); 1769 return SDOperand(); 1770} 1771 1772SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 1773 SDOperand N0 = N->getOperand(0); 1774 MVT::ValueType VT = N->getValueType(0); 1775 1776 // fold (cttz c1) -> c2 1777 if (isa<ConstantSDNode>(N0)) 1778 return DAG.getNode(ISD::CTTZ, VT, N0); 1779 return SDOperand(); 1780} 1781 1782SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 1783 SDOperand N0 = N->getOperand(0); 1784 MVT::ValueType VT = N->getValueType(0); 1785 1786 // fold (ctpop c1) -> c2 1787 if (isa<ConstantSDNode>(N0)) 1788 return DAG.getNode(ISD::CTPOP, VT, N0); 1789 return SDOperand(); 1790} 1791 1792SDOperand DAGCombiner::visitSELECT(SDNode *N) { 1793 SDOperand N0 = N->getOperand(0); 1794 SDOperand N1 = N->getOperand(1); 1795 SDOperand N2 = N->getOperand(2); 1796 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1797 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1798 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1799 MVT::ValueType VT = N->getValueType(0); 1800 1801 // fold select C, X, X -> X 1802 if (N1 == N2) 1803 return N1; 1804 // fold select true, X, Y -> X 1805 if (N0C && !N0C->isNullValue()) 1806 return N1; 1807 // fold select false, X, Y -> Y 1808 if (N0C && N0C->isNullValue()) 1809 return N2; 1810 // fold select C, 1, X -> C | X 1811 if (MVT::i1 == VT && N1C && N1C->getValue() == 1) 1812 return DAG.getNode(ISD::OR, VT, N0, N2); 1813 // fold select C, 0, X -> ~C & X 1814 // FIXME: this should check for C type == X type, not i1? 1815 if (MVT::i1 == VT && N1C && N1C->isNullValue()) { 1816 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1817 AddToWorkList(XORNode.Val); 1818 return DAG.getNode(ISD::AND, VT, XORNode, N2); 1819 } 1820 // fold select C, X, 1 -> ~C | X 1821 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) { 1822 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1823 AddToWorkList(XORNode.Val); 1824 return DAG.getNode(ISD::OR, VT, XORNode, N1); 1825 } 1826 // fold select C, X, 0 -> C & X 1827 // FIXME: this should check for C type == X type, not i1? 1828 if (MVT::i1 == VT && N2C && N2C->isNullValue()) 1829 return DAG.getNode(ISD::AND, VT, N0, N1); 1830 // fold X ? X : Y --> X ? 1 : Y --> X | Y 1831 if (MVT::i1 == VT && N0 == N1) 1832 return DAG.getNode(ISD::OR, VT, N0, N2); 1833 // fold X ? Y : X --> X ? Y : 0 --> X & Y 1834 if (MVT::i1 == VT && N0 == N2) 1835 return DAG.getNode(ISD::AND, VT, N0, N1); 1836 1837 // If we can fold this based on the true/false value, do so. 1838 if (SimplifySelectOps(N, N1, N2)) 1839 return SDOperand(N, 0); // Don't revisit N. 1840 1841 // fold selects based on a setcc into other things, such as min/max/abs 1842 if (N0.getOpcode() == ISD::SETCC) 1843 // FIXME: 1844 // Check against MVT::Other for SELECT_CC, which is a workaround for targets 1845 // having to say they don't support SELECT_CC on every type the DAG knows 1846 // about, since there is no way to mark an opcode illegal at all value types 1847 if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other)) 1848 return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1), 1849 N1, N2, N0.getOperand(2)); 1850 else 1851 return SimplifySelect(N0, N1, N2); 1852 return SDOperand(); 1853} 1854 1855SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) { 1856 SDOperand N0 = N->getOperand(0); 1857 SDOperand N1 = N->getOperand(1); 1858 SDOperand N2 = N->getOperand(2); 1859 SDOperand N3 = N->getOperand(3); 1860 SDOperand N4 = N->getOperand(4); 1861 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 1862 1863 // fold select_cc lhs, rhs, x, x, cc -> x 1864 if (N2 == N3) 1865 return N2; 1866 1867 // Determine if the condition we're dealing with is constant 1868 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1869 if (SCC.Val) AddToWorkList(SCC.Val); 1870 1871 if (ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val)) { 1872 if (SCCC->getValue()) 1873 return N2; // cond always true -> true val 1874 else 1875 return N3; // cond always false -> false val 1876 } 1877 1878 // Fold to a simpler select_cc 1879 if (SCC.Val && SCC.getOpcode() == ISD::SETCC) 1880 return DAG.getNode(ISD::SELECT_CC, N2.getValueType(), 1881 SCC.getOperand(0), SCC.getOperand(1), N2, N3, 1882 SCC.getOperand(2)); 1883 1884 // If we can fold this based on the true/false value, do so. 1885 if (SimplifySelectOps(N, N2, N3)) 1886 return SDOperand(N, 0); // Don't revisit N. 1887 1888 // fold select_cc into other things, such as min/max/abs 1889 return SimplifySelectCC(N0, N1, N2, N3, CC); 1890} 1891 1892SDOperand DAGCombiner::visitSETCC(SDNode *N) { 1893 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 1894 cast<CondCodeSDNode>(N->getOperand(2))->get()); 1895} 1896 1897SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 1898 SDOperand N0 = N->getOperand(0); 1899 MVT::ValueType VT = N->getValueType(0); 1900 1901 // fold (sext c1) -> c1 1902 if (isa<ConstantSDNode>(N0)) 1903 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0); 1904 1905 // fold (sext (sext x)) -> (sext x) 1906 // fold (sext (aext x)) -> (sext x) 1907 if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 1908 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1909 1910 // fold (sext (truncate x)) -> (sextinreg x). 1911 if (N0.getOpcode() == ISD::TRUNCATE && 1912 (!AfterLegalize || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, 1913 N0.getValueType()))) { 1914 SDOperand Op = N0.getOperand(0); 1915 if (Op.getValueType() < VT) { 1916 Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op); 1917 } else if (Op.getValueType() > VT) { 1918 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 1919 } 1920 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, Op, 1921 DAG.getValueType(N0.getValueType())); 1922 } 1923 1924 // fold (sext (load x)) -> (sext (truncate (sextload x))) 1925 if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() && 1926 (!AfterLegalize||TLI.isLoadXLegal(ISD::SEXTLOAD, N0.getValueType()))){ 1927 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1928 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 1929 LN0->getBasePtr(), LN0->getSrcValue(), 1930 LN0->getSrcValueOffset(), 1931 N0.getValueType()); 1932 CombineTo(N, ExtLoad); 1933 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1934 ExtLoad.getValue(1)); 1935 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1936 } 1937 1938 // fold (sext (sextload x)) -> (sext (truncate (sextload x))) 1939 // fold (sext ( extload x)) -> (sext (truncate (sextload x))) 1940 if ((ISD::isSEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) { 1941 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1942 MVT::ValueType EVT = LN0->getLoadedVT(); 1943 if (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT)) { 1944 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 1945 LN0->getBasePtr(), LN0->getSrcValue(), 1946 LN0->getSrcValueOffset(), EVT); 1947 CombineTo(N, ExtLoad); 1948 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1949 ExtLoad.getValue(1)); 1950 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 1951 } 1952 } 1953 1954 return SDOperand(); 1955} 1956 1957SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1958 SDOperand N0 = N->getOperand(0); 1959 MVT::ValueType VT = N->getValueType(0); 1960 1961 // fold (zext c1) -> c1 1962 if (isa<ConstantSDNode>(N0)) 1963 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 1964 // fold (zext (zext x)) -> (zext x) 1965 // fold (zext (aext x)) -> (zext x) 1966 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 1967 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1968 1969 // fold (zext (truncate x)) -> (and x, mask) 1970 if (N0.getOpcode() == ISD::TRUNCATE && 1971 (!AfterLegalize || TLI.isOperationLegal(ISD::AND, VT))) { 1972 SDOperand Op = N0.getOperand(0); 1973 if (Op.getValueType() < VT) { 1974 Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op); 1975 } else if (Op.getValueType() > VT) { 1976 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 1977 } 1978 return DAG.getZeroExtendInReg(Op, N0.getValueType()); 1979 } 1980 1981 // fold (zext (and (trunc x), cst)) -> (and x, cst). 1982 if (N0.getOpcode() == ISD::AND && 1983 N0.getOperand(0).getOpcode() == ISD::TRUNCATE && 1984 N0.getOperand(1).getOpcode() == ISD::Constant) { 1985 SDOperand X = N0.getOperand(0).getOperand(0); 1986 if (X.getValueType() < VT) { 1987 X = DAG.getNode(ISD::ANY_EXTEND, VT, X); 1988 } else if (X.getValueType() > VT) { 1989 X = DAG.getNode(ISD::TRUNCATE, VT, X); 1990 } 1991 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1992 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT)); 1993 } 1994 1995 // fold (zext (load x)) -> (zext (truncate (zextload x))) 1996 if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() && 1997 (!AfterLegalize||TLI.isLoadXLegal(ISD::ZEXTLOAD, N0.getValueType()))) { 1998 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1999 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 2000 LN0->getBasePtr(), LN0->getSrcValue(), 2001 LN0->getSrcValueOffset(), 2002 N0.getValueType()); 2003 CombineTo(N, ExtLoad); 2004 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 2005 ExtLoad.getValue(1)); 2006 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2007 } 2008 2009 // fold (zext (zextload x)) -> (zext (truncate (zextload x))) 2010 // fold (zext ( extload x)) -> (zext (truncate (zextload x))) 2011 if ((ISD::isZEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) { 2012 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2013 MVT::ValueType EVT = LN0->getLoadedVT(); 2014 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 2015 LN0->getBasePtr(), LN0->getSrcValue(), 2016 LN0->getSrcValueOffset(), EVT); 2017 CombineTo(N, ExtLoad); 2018 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 2019 ExtLoad.getValue(1)); 2020 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2021 } 2022 return SDOperand(); 2023} 2024 2025SDOperand DAGCombiner::visitANY_EXTEND(SDNode *N) { 2026 SDOperand N0 = N->getOperand(0); 2027 MVT::ValueType VT = N->getValueType(0); 2028 2029 // fold (aext c1) -> c1 2030 if (isa<ConstantSDNode>(N0)) 2031 return DAG.getNode(ISD::ANY_EXTEND, VT, N0); 2032 // fold (aext (aext x)) -> (aext x) 2033 // fold (aext (zext x)) -> (zext x) 2034 // fold (aext (sext x)) -> (sext x) 2035 if (N0.getOpcode() == ISD::ANY_EXTEND || 2036 N0.getOpcode() == ISD::ZERO_EXTEND || 2037 N0.getOpcode() == ISD::SIGN_EXTEND) 2038 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 2039 2040 // fold (aext (truncate x)) 2041 if (N0.getOpcode() == ISD::TRUNCATE) { 2042 SDOperand TruncOp = N0.getOperand(0); 2043 if (TruncOp.getValueType() == VT) 2044 return TruncOp; // x iff x size == zext size. 2045 if (TruncOp.getValueType() > VT) 2046 return DAG.getNode(ISD::TRUNCATE, VT, TruncOp); 2047 return DAG.getNode(ISD::ANY_EXTEND, VT, TruncOp); 2048 } 2049 2050 // fold (aext (and (trunc x), cst)) -> (and x, cst). 2051 if (N0.getOpcode() == ISD::AND && 2052 N0.getOperand(0).getOpcode() == ISD::TRUNCATE && 2053 N0.getOperand(1).getOpcode() == ISD::Constant) { 2054 SDOperand X = N0.getOperand(0).getOperand(0); 2055 if (X.getValueType() < VT) { 2056 X = DAG.getNode(ISD::ANY_EXTEND, VT, X); 2057 } else if (X.getValueType() > VT) { 2058 X = DAG.getNode(ISD::TRUNCATE, VT, X); 2059 } 2060 uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 2061 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT)); 2062 } 2063 2064 // fold (aext (load x)) -> (aext (truncate (extload x))) 2065 if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() && 2066 (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) { 2067 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2068 SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(), 2069 LN0->getBasePtr(), LN0->getSrcValue(), 2070 LN0->getSrcValueOffset(), 2071 N0.getValueType()); 2072 CombineTo(N, ExtLoad); 2073 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 2074 ExtLoad.getValue(1)); 2075 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2076 } 2077 2078 // fold (aext (zextload x)) -> (aext (truncate (zextload x))) 2079 // fold (aext (sextload x)) -> (aext (truncate (sextload x))) 2080 // fold (aext ( extload x)) -> (aext (truncate (extload x))) 2081 if (N0.getOpcode() == ISD::LOAD && !ISD::isNON_EXTLoad(N0.Val) && 2082 N0.hasOneUse()) { 2083 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2084 MVT::ValueType EVT = LN0->getLoadedVT(); 2085 SDOperand ExtLoad = DAG.getExtLoad(LN0->getExtensionType(), VT, 2086 LN0->getChain(), LN0->getBasePtr(), 2087 LN0->getSrcValue(), 2088 LN0->getSrcValueOffset(), EVT); 2089 CombineTo(N, ExtLoad); 2090 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 2091 ExtLoad.getValue(1)); 2092 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2093 } 2094 return SDOperand(); 2095} 2096 2097 2098SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 2099 SDOperand N0 = N->getOperand(0); 2100 SDOperand N1 = N->getOperand(1); 2101 MVT::ValueType VT = N->getValueType(0); 2102 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 2103 unsigned EVTBits = MVT::getSizeInBits(EVT); 2104 2105 // fold (sext_in_reg c1) -> c1 2106 if (isa<ConstantSDNode>(N0) || N0.getOpcode() == ISD::UNDEF) 2107 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1); 2108 2109 // If the input is already sign extended, just drop the extension. 2110 if (TLI.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1) 2111 return N0; 2112 2113 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 2114 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 2115 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 2116 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 2117 } 2118 2119 // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero 2120 if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1))) 2121 return DAG.getZeroExtendInReg(N0, EVT); 2122 2123 // fold (sext_in_reg (srl X, 24), i8) -> sra X, 24 2124 // fold (sext_in_reg (srl X, 23), i8) -> sra X, 23 iff possible. 2125 // We already fold "(sext_in_reg (srl X, 25), i8) -> srl X, 25" above. 2126 if (N0.getOpcode() == ISD::SRL) { 2127 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 2128 if (ShAmt->getValue()+EVTBits <= MVT::getSizeInBits(VT)) { 2129 // We can turn this into an SRA iff the input to the SRL is already sign 2130 // extended enough. 2131 unsigned InSignBits = TLI.ComputeNumSignBits(N0.getOperand(0)); 2132 if (MVT::getSizeInBits(VT)-(ShAmt->getValue()+EVTBits) < InSignBits) 2133 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1)); 2134 } 2135 } 2136 2137 // fold (sext_inreg (extload x)) -> (sextload x) 2138 if (ISD::isEXTLoad(N0.Val) && 2139 EVT == cast<LoadSDNode>(N0)->getLoadedVT() && 2140 (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) { 2141 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2142 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 2143 LN0->getBasePtr(), LN0->getSrcValue(), 2144 LN0->getSrcValueOffset(), EVT); 2145 CombineTo(N, ExtLoad); 2146 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 2147 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2148 } 2149 // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use 2150 if (ISD::isZEXTLoad(N0.Val) && N0.hasOneUse() && 2151 EVT == cast<LoadSDNode>(N0)->getLoadedVT() && 2152 (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) { 2153 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2154 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 2155 LN0->getBasePtr(), LN0->getSrcValue(), 2156 LN0->getSrcValueOffset(), EVT); 2157 CombineTo(N, ExtLoad); 2158 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 2159 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2160 } 2161 return SDOperand(); 2162} 2163 2164SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 2165 SDOperand N0 = N->getOperand(0); 2166 MVT::ValueType VT = N->getValueType(0); 2167 2168 // noop truncate 2169 if (N0.getValueType() == N->getValueType(0)) 2170 return N0; 2171 // fold (truncate c1) -> c1 2172 if (isa<ConstantSDNode>(N0)) 2173 return DAG.getNode(ISD::TRUNCATE, VT, N0); 2174 // fold (truncate (truncate x)) -> (truncate x) 2175 if (N0.getOpcode() == ISD::TRUNCATE) 2176 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 2177 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 2178 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND|| 2179 N0.getOpcode() == ISD::ANY_EXTEND) { 2180 if (N0.getOperand(0).getValueType() < VT) 2181 // if the source is smaller than the dest, we still need an extend 2182 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 2183 else if (N0.getOperand(0).getValueType() > VT) 2184 // if the source is larger than the dest, than we just need the truncate 2185 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 2186 else 2187 // if the source and dest are the same type, we can drop both the extend 2188 // and the truncate 2189 return N0.getOperand(0); 2190 } 2191 // fold (truncate (load x)) -> (smaller load x) 2192 if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() && 2193 // Do not allow folding to i1 here. i1 is implicitly stored in memory in 2194 // zero extended form: by shrinking the load, we lose track of the fact 2195 // that it is already zero extended. 2196 // FIXME: This should be reevaluated. 2197 VT != MVT::i1) { 2198 assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) && 2199 "Cannot truncate to larger type!"); 2200 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2201 MVT::ValueType PtrType = N0.getOperand(1).getValueType(); 2202 // For big endian targets, we need to add an offset to the pointer to load 2203 // the correct bytes. For little endian systems, we merely need to read 2204 // fewer bytes from the same pointer. 2205 uint64_t PtrOff = 2206 (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8; 2207 SDOperand NewPtr = TLI.isLittleEndian() ? LN0->getBasePtr() : 2208 DAG.getNode(ISD::ADD, PtrType, LN0->getBasePtr(), 2209 DAG.getConstant(PtrOff, PtrType)); 2210 AddToWorkList(NewPtr.Val); 2211 SDOperand Load = DAG.getLoad(VT, LN0->getChain(), NewPtr, 2212 LN0->getSrcValue(), LN0->getSrcValueOffset()); 2213 AddToWorkList(N); 2214 CombineTo(N0.Val, Load, Load.getValue(1)); 2215 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2216 } 2217 return SDOperand(); 2218} 2219 2220SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) { 2221 SDOperand N0 = N->getOperand(0); 2222 MVT::ValueType VT = N->getValueType(0); 2223 2224 // If the input is a constant, let getNode() fold it. 2225 if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) { 2226 SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0); 2227 if (Res.Val != N) return Res; 2228 } 2229 2230 if (N0.getOpcode() == ISD::BIT_CONVERT) // conv(conv(x,t1),t2) -> conv(x,t2) 2231 return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 2232 2233 // fold (conv (load x)) -> (load (conv*)x) 2234 // FIXME: These xforms need to know that the resultant load doesn't need a 2235 // higher alignment than the original! 2236 if (0 && ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse()) { 2237 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2238 SDOperand Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(), 2239 LN0->getSrcValue(), LN0->getSrcValueOffset()); 2240 AddToWorkList(N); 2241 CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load), 2242 Load.getValue(1)); 2243 return Load; 2244 } 2245 2246 return SDOperand(); 2247} 2248 2249SDOperand DAGCombiner::visitVBIT_CONVERT(SDNode *N) { 2250 SDOperand N0 = N->getOperand(0); 2251 MVT::ValueType VT = N->getValueType(0); 2252 2253 // If the input is a VBUILD_VECTOR with all constant elements, fold this now. 2254 // First check to see if this is all constant. 2255 if (N0.getOpcode() == ISD::VBUILD_VECTOR && N0.Val->hasOneUse() && 2256 VT == MVT::Vector) { 2257 bool isSimple = true; 2258 for (unsigned i = 0, e = N0.getNumOperands()-2; i != e; ++i) 2259 if (N0.getOperand(i).getOpcode() != ISD::UNDEF && 2260 N0.getOperand(i).getOpcode() != ISD::Constant && 2261 N0.getOperand(i).getOpcode() != ISD::ConstantFP) { 2262 isSimple = false; 2263 break; 2264 } 2265 2266 MVT::ValueType DestEltVT = cast<VTSDNode>(N->getOperand(2))->getVT(); 2267 if (isSimple && !MVT::isVector(DestEltVT)) { 2268 return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(N0.Val, DestEltVT); 2269 } 2270 } 2271 2272 return SDOperand(); 2273} 2274 2275/// ConstantFoldVBIT_CONVERTofVBUILD_VECTOR - We know that BV is a vbuild_vector 2276/// node with Constant, ConstantFP or Undef operands. DstEltVT indicates the 2277/// destination element value type. 2278SDOperand DAGCombiner:: 2279ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) { 2280 MVT::ValueType SrcEltVT = BV->getOperand(0).getValueType(); 2281 2282 // If this is already the right type, we're done. 2283 if (SrcEltVT == DstEltVT) return SDOperand(BV, 0); 2284 2285 unsigned SrcBitSize = MVT::getSizeInBits(SrcEltVT); 2286 unsigned DstBitSize = MVT::getSizeInBits(DstEltVT); 2287 2288 // If this is a conversion of N elements of one type to N elements of another 2289 // type, convert each element. This handles FP<->INT cases. 2290 if (SrcBitSize == DstBitSize) { 2291 SmallVector<SDOperand, 8> Ops; 2292 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) { 2293 Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i))); 2294 AddToWorkList(Ops.back().Val); 2295 } 2296 Ops.push_back(*(BV->op_end()-2)); // Add num elements. 2297 Ops.push_back(DAG.getValueType(DstEltVT)); 2298 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2299 } 2300 2301 // Otherwise, we're growing or shrinking the elements. To avoid having to 2302 // handle annoying details of growing/shrinking FP values, we convert them to 2303 // int first. 2304 if (MVT::isFloatingPoint(SrcEltVT)) { 2305 // Convert the input float vector to a int vector where the elements are the 2306 // same sizes. 2307 assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!"); 2308 MVT::ValueType IntVT = SrcEltVT == MVT::f32 ? MVT::i32 : MVT::i64; 2309 BV = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, IntVT).Val; 2310 SrcEltVT = IntVT; 2311 } 2312 2313 // Now we know the input is an integer vector. If the output is a FP type, 2314 // convert to integer first, then to FP of the right size. 2315 if (MVT::isFloatingPoint(DstEltVT)) { 2316 assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!"); 2317 MVT::ValueType TmpVT = DstEltVT == MVT::f32 ? MVT::i32 : MVT::i64; 2318 SDNode *Tmp = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, TmpVT).Val; 2319 2320 // Next, convert to FP elements of the same size. 2321 return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(Tmp, DstEltVT); 2322 } 2323 2324 // Okay, we know the src/dst types are both integers of differing types. 2325 // Handling growing first. 2326 assert(MVT::isInteger(SrcEltVT) && MVT::isInteger(DstEltVT)); 2327 if (SrcBitSize < DstBitSize) { 2328 unsigned NumInputsPerOutput = DstBitSize/SrcBitSize; 2329 2330 SmallVector<SDOperand, 8> Ops; 2331 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; 2332 i += NumInputsPerOutput) { 2333 bool isLE = TLI.isLittleEndian(); 2334 uint64_t NewBits = 0; 2335 bool EltIsUndef = true; 2336 for (unsigned j = 0; j != NumInputsPerOutput; ++j) { 2337 // Shift the previously computed bits over. 2338 NewBits <<= SrcBitSize; 2339 SDOperand Op = BV->getOperand(i+ (isLE ? (NumInputsPerOutput-j-1) : j)); 2340 if (Op.getOpcode() == ISD::UNDEF) continue; 2341 EltIsUndef = false; 2342 2343 NewBits |= cast<ConstantSDNode>(Op)->getValue(); 2344 } 2345 2346 if (EltIsUndef) 2347 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 2348 else 2349 Ops.push_back(DAG.getConstant(NewBits, DstEltVT)); 2350 } 2351 2352 Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements. 2353 Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size. 2354 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2355 } 2356 2357 // Finally, this must be the case where we are shrinking elements: each input 2358 // turns into multiple outputs. 2359 unsigned NumOutputsPerInput = SrcBitSize/DstBitSize; 2360 SmallVector<SDOperand, 8> Ops; 2361 for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) { 2362 if (BV->getOperand(i).getOpcode() == ISD::UNDEF) { 2363 for (unsigned j = 0; j != NumOutputsPerInput; ++j) 2364 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 2365 continue; 2366 } 2367 uint64_t OpVal = cast<ConstantSDNode>(BV->getOperand(i))->getValue(); 2368 2369 for (unsigned j = 0; j != NumOutputsPerInput; ++j) { 2370 unsigned ThisVal = OpVal & ((1ULL << DstBitSize)-1); 2371 OpVal >>= DstBitSize; 2372 Ops.push_back(DAG.getConstant(ThisVal, DstEltVT)); 2373 } 2374 2375 // For big endian targets, swap the order of the pieces of each element. 2376 if (!TLI.isLittleEndian()) 2377 std::reverse(Ops.end()-NumOutputsPerInput, Ops.end()); 2378 } 2379 Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements. 2380 Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size. 2381 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 2382} 2383 2384 2385 2386SDOperand DAGCombiner::visitFADD(SDNode *N) { 2387 SDOperand N0 = N->getOperand(0); 2388 SDOperand N1 = N->getOperand(1); 2389 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2390 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2391 MVT::ValueType VT = N->getValueType(0); 2392 2393 // fold (fadd c1, c2) -> c1+c2 2394 if (N0CFP && N1CFP) 2395 return DAG.getNode(ISD::FADD, VT, N0, N1); 2396 // canonicalize constant to RHS 2397 if (N0CFP && !N1CFP) 2398 return DAG.getNode(ISD::FADD, VT, N1, N0); 2399 // fold (A + (-B)) -> A-B 2400 if (N1.getOpcode() == ISD::FNEG) 2401 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0)); 2402 // fold ((-A) + B) -> B-A 2403 if (N0.getOpcode() == ISD::FNEG) 2404 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0)); 2405 2406 // If allowed, fold (fadd (fadd x, c1), c2) -> (fadd x, (fadd c1, c2)) 2407 if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FADD && 2408 N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1))) 2409 return DAG.getNode(ISD::FADD, VT, N0.getOperand(0), 2410 DAG.getNode(ISD::FADD, VT, N0.getOperand(1), N1)); 2411 2412 return SDOperand(); 2413} 2414 2415SDOperand DAGCombiner::visitFSUB(SDNode *N) { 2416 SDOperand N0 = N->getOperand(0); 2417 SDOperand N1 = N->getOperand(1); 2418 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2419 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2420 MVT::ValueType VT = N->getValueType(0); 2421 2422 // fold (fsub c1, c2) -> c1-c2 2423 if (N0CFP && N1CFP) 2424 return DAG.getNode(ISD::FSUB, VT, N0, N1); 2425 // fold (A-(-B)) -> A+B 2426 if (N1.getOpcode() == ISD::FNEG) 2427 return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0)); 2428 return SDOperand(); 2429} 2430 2431SDOperand DAGCombiner::visitFMUL(SDNode *N) { 2432 SDOperand N0 = N->getOperand(0); 2433 SDOperand N1 = N->getOperand(1); 2434 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2435 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2436 MVT::ValueType VT = N->getValueType(0); 2437 2438 // fold (fmul c1, c2) -> c1*c2 2439 if (N0CFP && N1CFP) 2440 return DAG.getNode(ISD::FMUL, VT, N0, N1); 2441 // canonicalize constant to RHS 2442 if (N0CFP && !N1CFP) 2443 return DAG.getNode(ISD::FMUL, VT, N1, N0); 2444 // fold (fmul X, 2.0) -> (fadd X, X) 2445 if (N1CFP && N1CFP->isExactlyValue(+2.0)) 2446 return DAG.getNode(ISD::FADD, VT, N0, N0); 2447 2448 // If allowed, fold (fmul (fmul x, c1), c2) -> (fmul x, (fmul c1, c2)) 2449 if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FMUL && 2450 N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1))) 2451 return DAG.getNode(ISD::FMUL, VT, N0.getOperand(0), 2452 DAG.getNode(ISD::FMUL, VT, N0.getOperand(1), N1)); 2453 2454 return SDOperand(); 2455} 2456 2457SDOperand DAGCombiner::visitFDIV(SDNode *N) { 2458 SDOperand N0 = N->getOperand(0); 2459 SDOperand N1 = N->getOperand(1); 2460 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2461 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2462 MVT::ValueType VT = N->getValueType(0); 2463 2464 // fold (fdiv c1, c2) -> c1/c2 2465 if (N0CFP && N1CFP) 2466 return DAG.getNode(ISD::FDIV, VT, N0, N1); 2467 return SDOperand(); 2468} 2469 2470SDOperand DAGCombiner::visitFREM(SDNode *N) { 2471 SDOperand N0 = N->getOperand(0); 2472 SDOperand N1 = N->getOperand(1); 2473 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2474 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2475 MVT::ValueType VT = N->getValueType(0); 2476 2477 // fold (frem c1, c2) -> fmod(c1,c2) 2478 if (N0CFP && N1CFP) 2479 return DAG.getNode(ISD::FREM, VT, N0, N1); 2480 return SDOperand(); 2481} 2482 2483SDOperand DAGCombiner::visitFCOPYSIGN(SDNode *N) { 2484 SDOperand N0 = N->getOperand(0); 2485 SDOperand N1 = N->getOperand(1); 2486 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2487 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 2488 MVT::ValueType VT = N->getValueType(0); 2489 2490 if (N0CFP && N1CFP) // Constant fold 2491 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1); 2492 2493 if (N1CFP) { 2494 // copysign(x, c1) -> fabs(x) iff ispos(c1) 2495 // copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1) 2496 union { 2497 double d; 2498 int64_t i; 2499 } u; 2500 u.d = N1CFP->getValue(); 2501 if (u.i >= 0) 2502 return DAG.getNode(ISD::FABS, VT, N0); 2503 else 2504 return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0)); 2505 } 2506 2507 // copysign(fabs(x), y) -> copysign(x, y) 2508 // copysign(fneg(x), y) -> copysign(x, y) 2509 // copysign(copysign(x,z), y) -> copysign(x, y) 2510 if (N0.getOpcode() == ISD::FABS || N0.getOpcode() == ISD::FNEG || 2511 N0.getOpcode() == ISD::FCOPYSIGN) 2512 return DAG.getNode(ISD::FCOPYSIGN, VT, N0.getOperand(0), N1); 2513 2514 // copysign(x, abs(y)) -> abs(x) 2515 if (N1.getOpcode() == ISD::FABS) 2516 return DAG.getNode(ISD::FABS, VT, N0); 2517 2518 // copysign(x, copysign(y,z)) -> copysign(x, z) 2519 if (N1.getOpcode() == ISD::FCOPYSIGN) 2520 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(1)); 2521 2522 // copysign(x, fp_extend(y)) -> copysign(x, y) 2523 // copysign(x, fp_round(y)) -> copysign(x, y) 2524 if (N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND) 2525 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(0)); 2526 2527 return SDOperand(); 2528} 2529 2530 2531 2532SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 2533 SDOperand N0 = N->getOperand(0); 2534 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2535 MVT::ValueType VT = N->getValueType(0); 2536 2537 // fold (sint_to_fp c1) -> c1fp 2538 if (N0C) 2539 return DAG.getNode(ISD::SINT_TO_FP, VT, N0); 2540 return SDOperand(); 2541} 2542 2543SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 2544 SDOperand N0 = N->getOperand(0); 2545 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2546 MVT::ValueType VT = N->getValueType(0); 2547 2548 // fold (uint_to_fp c1) -> c1fp 2549 if (N0C) 2550 return DAG.getNode(ISD::UINT_TO_FP, VT, N0); 2551 return SDOperand(); 2552} 2553 2554SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 2555 SDOperand N0 = N->getOperand(0); 2556 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2557 MVT::ValueType VT = N->getValueType(0); 2558 2559 // fold (fp_to_sint c1fp) -> c1 2560 if (N0CFP) 2561 return DAG.getNode(ISD::FP_TO_SINT, VT, N0); 2562 return SDOperand(); 2563} 2564 2565SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 2566 SDOperand N0 = N->getOperand(0); 2567 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2568 MVT::ValueType VT = N->getValueType(0); 2569 2570 // fold (fp_to_uint c1fp) -> c1 2571 if (N0CFP) 2572 return DAG.getNode(ISD::FP_TO_UINT, VT, N0); 2573 return SDOperand(); 2574} 2575 2576SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 2577 SDOperand N0 = N->getOperand(0); 2578 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2579 MVT::ValueType VT = N->getValueType(0); 2580 2581 // fold (fp_round c1fp) -> c1fp 2582 if (N0CFP) 2583 return DAG.getNode(ISD::FP_ROUND, VT, N0); 2584 2585 // fold (fp_round (fp_extend x)) -> x 2586 if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType()) 2587 return N0.getOperand(0); 2588 2589 // fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y) 2590 if (N0.getOpcode() == ISD::FCOPYSIGN && N0.Val->hasOneUse()) { 2591 SDOperand Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0)); 2592 AddToWorkList(Tmp.Val); 2593 return DAG.getNode(ISD::FCOPYSIGN, VT, Tmp, N0.getOperand(1)); 2594 } 2595 2596 return SDOperand(); 2597} 2598 2599SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 2600 SDOperand N0 = N->getOperand(0); 2601 MVT::ValueType VT = N->getValueType(0); 2602 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 2603 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2604 2605 // fold (fp_round_inreg c1fp) -> c1fp 2606 if (N0CFP) { 2607 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 2608 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 2609 } 2610 return SDOperand(); 2611} 2612 2613SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 2614 SDOperand N0 = N->getOperand(0); 2615 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2616 MVT::ValueType VT = N->getValueType(0); 2617 2618 // fold (fp_extend c1fp) -> c1fp 2619 if (N0CFP) 2620 return DAG.getNode(ISD::FP_EXTEND, VT, N0); 2621 2622 // fold (fpext (load x)) -> (fpext (fpround (extload x))) 2623 if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() && 2624 (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) { 2625 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2626 SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(), 2627 LN0->getBasePtr(), LN0->getSrcValue(), 2628 LN0->getSrcValueOffset(), 2629 N0.getValueType()); 2630 CombineTo(N, ExtLoad); 2631 CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad), 2632 ExtLoad.getValue(1)); 2633 return SDOperand(N, 0); // Return N so it doesn't get rechecked! 2634 } 2635 2636 2637 return SDOperand(); 2638} 2639 2640SDOperand DAGCombiner::visitFNEG(SDNode *N) { 2641 SDOperand N0 = N->getOperand(0); 2642 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2643 MVT::ValueType VT = N->getValueType(0); 2644 2645 // fold (fneg c1) -> -c1 2646 if (N0CFP) 2647 return DAG.getNode(ISD::FNEG, VT, N0); 2648 // fold (fneg (sub x, y)) -> (sub y, x) 2649 if (N0.getOpcode() == ISD::SUB) 2650 return DAG.getNode(ISD::SUB, VT, N0.getOperand(1), N0.getOperand(0)); 2651 // fold (fneg (fneg x)) -> x 2652 if (N0.getOpcode() == ISD::FNEG) 2653 return N0.getOperand(0); 2654 return SDOperand(); 2655} 2656 2657SDOperand DAGCombiner::visitFABS(SDNode *N) { 2658 SDOperand N0 = N->getOperand(0); 2659 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 2660 MVT::ValueType VT = N->getValueType(0); 2661 2662 // fold (fabs c1) -> fabs(c1) 2663 if (N0CFP) 2664 return DAG.getNode(ISD::FABS, VT, N0); 2665 // fold (fabs (fabs x)) -> (fabs x) 2666 if (N0.getOpcode() == ISD::FABS) 2667 return N->getOperand(0); 2668 // fold (fabs (fneg x)) -> (fabs x) 2669 // fold (fabs (fcopysign x, y)) -> (fabs x) 2670 if (N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FCOPYSIGN) 2671 return DAG.getNode(ISD::FABS, VT, N0.getOperand(0)); 2672 2673 return SDOperand(); 2674} 2675 2676SDOperand DAGCombiner::visitBRCOND(SDNode *N) { 2677 SDOperand Chain = N->getOperand(0); 2678 SDOperand N1 = N->getOperand(1); 2679 SDOperand N2 = N->getOperand(2); 2680 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2681 2682 // never taken branch, fold to chain 2683 if (N1C && N1C->isNullValue()) 2684 return Chain; 2685 // unconditional branch 2686 if (N1C && N1C->getValue() == 1) 2687 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 2688 // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal 2689 // on the target. 2690 if (N1.getOpcode() == ISD::SETCC && 2691 TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) { 2692 return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2), 2693 N1.getOperand(0), N1.getOperand(1), N2); 2694 } 2695 return SDOperand(); 2696} 2697 2698// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 2699// 2700SDOperand DAGCombiner::visitBR_CC(SDNode *N) { 2701 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 2702 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 2703 2704 // Use SimplifySetCC to simplify SETCC's. 2705 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false); 2706 if (Simp.Val) AddToWorkList(Simp.Val); 2707 2708 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val); 2709 2710 // fold br_cc true, dest -> br dest (unconditional branch) 2711 if (SCCC && SCCC->getValue()) 2712 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 2713 N->getOperand(4)); 2714 // fold br_cc false, dest -> unconditional fall through 2715 if (SCCC && SCCC->isNullValue()) 2716 return N->getOperand(0); 2717 2718 // fold to a simpler setcc 2719 if (Simp.Val && Simp.getOpcode() == ISD::SETCC) 2720 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 2721 Simp.getOperand(2), Simp.getOperand(0), 2722 Simp.getOperand(1), N->getOperand(4)); 2723 return SDOperand(); 2724} 2725 2726 2727/// CombineToPreIndexedLoadStore - Try turning a load / store and a 2728/// pre-indexed load / store when the base pointer is a add or subtract 2729/// and it has other uses besides the load / store. After the 2730/// transformation, the new indexed load / store has effectively folded 2731/// the add / subtract in and all of its other uses are redirected to the 2732/// new load / store. 2733bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { 2734 if (!AfterLegalize) 2735 return false; 2736 2737 bool isLoad = true; 2738 SDOperand Ptr; 2739 MVT::ValueType VT; 2740 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 2741 if (LD->getAddressingMode() != ISD::UNINDEXED) 2742 return false; 2743 VT = LD->getLoadedVT(); 2744 if (LD->getAddressingMode() != ISD::UNINDEXED && 2745 !TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) && 2746 !TLI.isIndexedLoadLegal(ISD::PRE_DEC, VT)) 2747 return false; 2748 Ptr = LD->getBasePtr(); 2749 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 2750 if (ST->getAddressingMode() != ISD::UNINDEXED) 2751 return false; 2752 VT = ST->getStoredVT(); 2753 if (!TLI.isIndexedStoreLegal(ISD::PRE_INC, VT) && 2754 !TLI.isIndexedStoreLegal(ISD::PRE_DEC, VT)) 2755 return false; 2756 Ptr = ST->getBasePtr(); 2757 isLoad = false; 2758 } else 2759 return false; 2760 2761 // If the pointer is not an add/sub, or if it doesn't have multiple uses, bail 2762 // out. There is no reason to make this a preinc/predec. 2763 if ((Ptr.getOpcode() != ISD::ADD && Ptr.getOpcode() != ISD::SUB) || 2764 Ptr.Val->hasOneUse()) 2765 return false; 2766 2767 // Ask the target to do addressing mode selection. 2768 SDOperand BasePtr; 2769 SDOperand Offset; 2770 ISD::MemIndexedMode AM = ISD::UNINDEXED; 2771 if (!TLI.getPreIndexedAddressParts(N, BasePtr, Offset, AM, DAG)) 2772 return false; 2773 2774 // Try turning it into a pre-indexed load / store except when: 2775 // 1) The base is a frame index. 2776 // 2) If N is a store and the ptr is either the same as or is a 2777 // predecessor of the value being stored. 2778 // 3) Another use of base ptr is a predecessor of N. If ptr is folded 2779 // that would create a cycle. 2780 // 4) All uses are load / store ops that use it as base ptr. 2781 2782 // Check #1. Preinc'ing a frame index would require copying the stack pointer 2783 // (plus the implicit offset) to a register to preinc anyway. 2784 if (isa<FrameIndexSDNode>(BasePtr)) 2785 return false; 2786 2787 // Check #2. 2788 if (!isLoad) { 2789 SDOperand Val = cast<StoreSDNode>(N)->getValue(); 2790 if (Val == Ptr || Ptr.Val->isPredecessor(Val.Val)) 2791 return false; 2792 } 2793 2794 // Now check for #2 and #3. 2795 bool RealUse = false; 2796 for (SDNode::use_iterator I = Ptr.Val->use_begin(), 2797 E = Ptr.Val->use_end(); I != E; ++I) { 2798 SDNode *Use = *I; 2799 if (Use == N) 2800 continue; 2801 if (Use->isPredecessor(N)) 2802 return false; 2803 2804 if (!((Use->getOpcode() == ISD::LOAD && 2805 cast<LoadSDNode>(Use)->getBasePtr() == Ptr) || 2806 (Use->getOpcode() == ISD::STORE) && 2807 cast<StoreSDNode>(Use)->getBasePtr() == Ptr)) 2808 RealUse = true; 2809 } 2810 if (!RealUse) 2811 return false; 2812 2813 SDOperand Result; 2814 if (isLoad) 2815 Result = DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM); 2816 else 2817 Result = DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM); 2818 ++PreIndexedNodes; 2819 ++NodesCombined; 2820 DOUT << "\nReplacing.4 "; DEBUG(N->dump()); 2821 DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG)); 2822 DOUT << '\n'; 2823 std::vector<SDNode*> NowDead; 2824 if (isLoad) { 2825 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0), 2826 NowDead); 2827 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2), 2828 NowDead); 2829 } else { 2830 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1), 2831 NowDead); 2832 } 2833 2834 // Nodes can end up on the worklist more than once. Make sure we do 2835 // not process a node that has been replaced. 2836 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 2837 removeFromWorkList(NowDead[i]); 2838 // Finally, since the node is now dead, remove it from the graph. 2839 DAG.DeleteNode(N); 2840 2841 // Replace the uses of Ptr with uses of the updated base value. 2842 DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0), 2843 NowDead); 2844 removeFromWorkList(Ptr.Val); 2845 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 2846 removeFromWorkList(NowDead[i]); 2847 DAG.DeleteNode(Ptr.Val); 2848 2849 return true; 2850} 2851 2852/// CombineToPostIndexedLoadStore - Try combine a load / store with a 2853/// add / sub of the base pointer node into a post-indexed load / store. 2854/// The transformation folded the add / subtract into the new indexed 2855/// load / store effectively and all of its uses are redirected to the 2856/// new load / store. 2857bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) { 2858 if (!AfterLegalize) 2859 return false; 2860 2861 bool isLoad = true; 2862 SDOperand Ptr; 2863 MVT::ValueType VT; 2864 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 2865 if (LD->getAddressingMode() != ISD::UNINDEXED) 2866 return false; 2867 VT = LD->getLoadedVT(); 2868 if (!TLI.isIndexedLoadLegal(ISD::POST_INC, VT) && 2869 !TLI.isIndexedLoadLegal(ISD::POST_DEC, VT)) 2870 return false; 2871 Ptr = LD->getBasePtr(); 2872 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 2873 if (ST->getAddressingMode() != ISD::UNINDEXED) 2874 return false; 2875 VT = ST->getStoredVT(); 2876 if (!TLI.isIndexedStoreLegal(ISD::POST_INC, VT) && 2877 !TLI.isIndexedStoreLegal(ISD::POST_DEC, VT)) 2878 return false; 2879 Ptr = ST->getBasePtr(); 2880 isLoad = false; 2881 } else 2882 return false; 2883 2884 if (Ptr.Val->hasOneUse()) 2885 return false; 2886 2887 for (SDNode::use_iterator I = Ptr.Val->use_begin(), 2888 E = Ptr.Val->use_end(); I != E; ++I) { 2889 SDNode *Op = *I; 2890 if (Op == N || 2891 (Op->getOpcode() != ISD::ADD && Op->getOpcode() != ISD::SUB)) 2892 continue; 2893 2894 SDOperand BasePtr; 2895 SDOperand Offset; 2896 ISD::MemIndexedMode AM = ISD::UNINDEXED; 2897 if (TLI.getPostIndexedAddressParts(N, Op, BasePtr, Offset, AM, DAG)) { 2898 if (Ptr == Offset) 2899 std::swap(BasePtr, Offset); 2900 if (Ptr != BasePtr) 2901 continue; 2902 2903 // Try turning it into a post-indexed load / store except when 2904 // 1) All uses are load / store ops that use it as base ptr. 2905 // 2) Op must be independent of N, i.e. Op is neither a predecessor 2906 // nor a successor of N. Otherwise, if Op is folded that would 2907 // create a cycle. 2908 2909 // Check for #1. 2910 bool TryNext = false; 2911 for (SDNode::use_iterator II = BasePtr.Val->use_begin(), 2912 EE = BasePtr.Val->use_end(); II != EE; ++II) { 2913 SDNode *Use = *II; 2914 if (Use == Ptr.Val) 2915 continue; 2916 2917 // If all the uses are load / store addresses, then don't do the 2918 // transformation. 2919 if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB){ 2920 bool RealUse = false; 2921 for (SDNode::use_iterator III = Use->use_begin(), 2922 EEE = Use->use_end(); III != EEE; ++III) { 2923 SDNode *UseUse = *III; 2924 if (!((UseUse->getOpcode() == ISD::LOAD && 2925 cast<LoadSDNode>(UseUse)->getBasePtr().Val == Use) || 2926 (UseUse->getOpcode() == ISD::STORE) && 2927 cast<StoreSDNode>(UseUse)->getBasePtr().Val == Use)) 2928 RealUse = true; 2929 } 2930 2931 if (!RealUse) { 2932 TryNext = true; 2933 break; 2934 } 2935 } 2936 } 2937 if (TryNext) 2938 continue; 2939 2940 // Check for #2 2941 if (!Op->isPredecessor(N) && !N->isPredecessor(Op)) { 2942 SDOperand Result = isLoad 2943 ? DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM) 2944 : DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM); 2945 ++PostIndexedNodes; 2946 ++NodesCombined; 2947 DOUT << "\nReplacing.5 "; DEBUG(N->dump()); 2948 DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG)); 2949 DOUT << '\n'; 2950 std::vector<SDNode*> NowDead; 2951 if (isLoad) { 2952 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0), 2953 NowDead); 2954 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2), 2955 NowDead); 2956 } else { 2957 DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1), 2958 NowDead); 2959 } 2960 2961 // Nodes can end up on the worklist more than once. Make sure we do 2962 // not process a node that has been replaced. 2963 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 2964 removeFromWorkList(NowDead[i]); 2965 // Finally, since the node is now dead, remove it from the graph. 2966 DAG.DeleteNode(N); 2967 2968 // Replace the uses of Use with uses of the updated base value. 2969 DAG.ReplaceAllUsesOfValueWith(SDOperand(Op, 0), 2970 Result.getValue(isLoad ? 1 : 0), 2971 NowDead); 2972 removeFromWorkList(Op); 2973 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 2974 removeFromWorkList(NowDead[i]); 2975 DAG.DeleteNode(Op); 2976 2977 return true; 2978 } 2979 } 2980 } 2981 return false; 2982} 2983 2984 2985SDOperand DAGCombiner::visitLOAD(SDNode *N) { 2986 LoadSDNode *LD = cast<LoadSDNode>(N); 2987 SDOperand Chain = LD->getChain(); 2988 SDOperand Ptr = LD->getBasePtr(); 2989 2990 // If there are no uses of the loaded value, change uses of the chain value 2991 // into uses of the chain input (i.e. delete the dead load). 2992 if (N->hasNUsesOfValue(0, 0)) 2993 return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain); 2994 2995 // If this load is directly stored, replace the load value with the stored 2996 // value. 2997 // TODO: Handle store large -> read small portion. 2998 // TODO: Handle TRUNCSTORE/LOADEXT 2999 if (LD->getExtensionType() == ISD::NON_EXTLOAD) { 3000 if (ISD::isNON_TRUNCStore(Chain.Val)) { 3001 StoreSDNode *PrevST = cast<StoreSDNode>(Chain); 3002 if (PrevST->getBasePtr() == Ptr && 3003 PrevST->getValue().getValueType() == N->getValueType(0)) 3004 return CombineTo(N, Chain.getOperand(1), Chain); 3005 } 3006 } 3007 3008 if (CombinerAA) { 3009 // Walk up chain skipping non-aliasing memory nodes. 3010 SDOperand BetterChain = FindBetterChain(N, Chain); 3011 3012 // If there is a better chain. 3013 if (Chain != BetterChain) { 3014 SDOperand ReplLoad; 3015 3016 // Replace the chain to void dependency. 3017 if (LD->getExtensionType() == ISD::NON_EXTLOAD) { 3018 ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr, 3019 LD->getSrcValue(), LD->getSrcValueOffset()); 3020 } else { 3021 ReplLoad = DAG.getExtLoad(LD->getExtensionType(), 3022 LD->getValueType(0), 3023 BetterChain, Ptr, LD->getSrcValue(), 3024 LD->getSrcValueOffset(), 3025 LD->getLoadedVT()); 3026 } 3027 3028 // Create token factor to keep old chain connected. 3029 SDOperand Token = DAG.getNode(ISD::TokenFactor, MVT::Other, 3030 Chain, ReplLoad.getValue(1)); 3031 3032 // Replace uses with load result and token factor. Don't add users 3033 // to work list. 3034 return CombineTo(N, ReplLoad.getValue(0), Token, false); 3035 } 3036 } 3037 3038 // Try transforming N to an indexed load. 3039 if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N)) 3040 return SDOperand(N, 0); 3041 3042 return SDOperand(); 3043} 3044 3045SDOperand DAGCombiner::visitSTORE(SDNode *N) { 3046 StoreSDNode *ST = cast<StoreSDNode>(N); 3047 SDOperand Chain = ST->getChain(); 3048 SDOperand Value = ST->getValue(); 3049 SDOperand Ptr = ST->getBasePtr(); 3050 3051 // If this is a store of a bit convert, store the input value. 3052 // FIXME: This needs to know that the resultant store does not need a 3053 // higher alignment than the original. 3054 if (0 && Value.getOpcode() == ISD::BIT_CONVERT) { 3055 return DAG.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(), 3056 ST->getSrcValueOffset()); 3057 } 3058 3059 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 3060 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(Value)) { 3061 if (Value.getOpcode() != ISD::TargetConstantFP) { 3062 SDOperand Tmp; 3063 switch (CFP->getValueType(0)) { 3064 default: assert(0 && "Unknown FP type"); 3065 case MVT::f32: 3066 if (!AfterLegalize || TLI.isTypeLegal(MVT::i32)) { 3067 Tmp = DAG.getConstant(FloatToBits(CFP->getValue()), MVT::i32); 3068 return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(), 3069 ST->getSrcValueOffset()); 3070 } 3071 break; 3072 case MVT::f64: 3073 if (!AfterLegalize || TLI.isTypeLegal(MVT::i64)) { 3074 Tmp = DAG.getConstant(DoubleToBits(CFP->getValue()), MVT::i64); 3075 return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(), 3076 ST->getSrcValueOffset()); 3077 } else if (TLI.isTypeLegal(MVT::i32)) { 3078 // Many FP stores are not make apparent until after legalize, e.g. for 3079 // argument passing. Since this is so common, custom legalize the 3080 // 64-bit integer store into two 32-bit stores. 3081 uint64_t Val = DoubleToBits(CFP->getValue()); 3082 SDOperand Lo = DAG.getConstant(Val & 0xFFFFFFFF, MVT::i32); 3083 SDOperand Hi = DAG.getConstant(Val >> 32, MVT::i32); 3084 if (!TLI.isLittleEndian()) std::swap(Lo, Hi); 3085 3086 SDOperand St0 = DAG.getStore(Chain, Lo, Ptr, ST->getSrcValue(), 3087 ST->getSrcValueOffset()); 3088 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 3089 DAG.getConstant(4, Ptr.getValueType())); 3090 SDOperand St1 = DAG.getStore(Chain, Hi, Ptr, ST->getSrcValue(), 3091 ST->getSrcValueOffset()+4); 3092 return DAG.getNode(ISD::TokenFactor, MVT::Other, St0, St1); 3093 } 3094 break; 3095 } 3096 } 3097 } 3098 3099 if (CombinerAA) { 3100 // Walk up chain skipping non-aliasing memory nodes. 3101 SDOperand BetterChain = FindBetterChain(N, Chain); 3102 3103 // If there is a better chain. 3104 if (Chain != BetterChain) { 3105 // Replace the chain to avoid dependency. 3106 SDOperand ReplStore; 3107 if (ST->isTruncatingStore()) { 3108 ReplStore = DAG.getTruncStore(BetterChain, Value, Ptr, 3109 ST->getSrcValue(),ST->getSrcValueOffset(), ST->getStoredVT()); 3110 } else { 3111 ReplStore = DAG.getStore(BetterChain, Value, Ptr, 3112 ST->getSrcValue(), ST->getSrcValueOffset()); 3113 } 3114 3115 // Create token to keep both nodes around. 3116 SDOperand Token = 3117 DAG.getNode(ISD::TokenFactor, MVT::Other, Chain, ReplStore); 3118 3119 // Don't add users to work list. 3120 return CombineTo(N, Token, false); 3121 } 3122 } 3123 3124 // Try transforming N to an indexed store. 3125 if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N)) 3126 return SDOperand(N, 0); 3127 3128 return SDOperand(); 3129} 3130 3131SDOperand DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) { 3132 SDOperand InVec = N->getOperand(0); 3133 SDOperand InVal = N->getOperand(1); 3134 SDOperand EltNo = N->getOperand(2); 3135 3136 // If the invec is a BUILD_VECTOR and if EltNo is a constant, build a new 3137 // vector with the inserted element. 3138 if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 3139 unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue(); 3140 SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end()); 3141 if (Elt < Ops.size()) 3142 Ops[Elt] = InVal; 3143 return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(), 3144 &Ops[0], Ops.size()); 3145 } 3146 3147 return SDOperand(); 3148} 3149 3150SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) { 3151 SDOperand InVec = N->getOperand(0); 3152 SDOperand InVal = N->getOperand(1); 3153 SDOperand EltNo = N->getOperand(2); 3154 SDOperand NumElts = N->getOperand(3); 3155 SDOperand EltType = N->getOperand(4); 3156 3157 // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new 3158 // vector with the inserted element. 3159 if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 3160 unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue(); 3161 SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end()); 3162 if (Elt < Ops.size()-2) 3163 Ops[Elt] = InVal; 3164 return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(), 3165 &Ops[0], Ops.size()); 3166 } 3167 3168 return SDOperand(); 3169} 3170 3171SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) { 3172 unsigned NumInScalars = N->getNumOperands()-2; 3173 SDOperand NumElts = N->getOperand(NumInScalars); 3174 SDOperand EltType = N->getOperand(NumInScalars+1); 3175 3176 // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT 3177 // operations. If so, and if the EXTRACT_ELT vector inputs come from at most 3178 // two distinct vectors, turn this into a shuffle node. 3179 SDOperand VecIn1, VecIn2; 3180 for (unsigned i = 0; i != NumInScalars; ++i) { 3181 // Ignore undef inputs. 3182 if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue; 3183 3184 // If this input is something other than a VEXTRACT_VECTOR_ELT with a 3185 // constant index, bail out. 3186 if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT || 3187 !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) { 3188 VecIn1 = VecIn2 = SDOperand(0, 0); 3189 break; 3190 } 3191 3192 // If the input vector type disagrees with the result of the vbuild_vector, 3193 // we can't make a shuffle. 3194 SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0); 3195 if (*(ExtractedFromVec.Val->op_end()-2) != NumElts || 3196 *(ExtractedFromVec.Val->op_end()-1) != EltType) { 3197 VecIn1 = VecIn2 = SDOperand(0, 0); 3198 break; 3199 } 3200 3201 // Otherwise, remember this. We allow up to two distinct input vectors. 3202 if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2) 3203 continue; 3204 3205 if (VecIn1.Val == 0) { 3206 VecIn1 = ExtractedFromVec; 3207 } else if (VecIn2.Val == 0) { 3208 VecIn2 = ExtractedFromVec; 3209 } else { 3210 // Too many inputs. 3211 VecIn1 = VecIn2 = SDOperand(0, 0); 3212 break; 3213 } 3214 } 3215 3216 // If everything is good, we can make a shuffle operation. 3217 if (VecIn1.Val) { 3218 SmallVector<SDOperand, 8> BuildVecIndices; 3219 for (unsigned i = 0; i != NumInScalars; ++i) { 3220 if (N->getOperand(i).getOpcode() == ISD::UNDEF) { 3221 BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, MVT::i32)); 3222 continue; 3223 } 3224 3225 SDOperand Extract = N->getOperand(i); 3226 3227 // If extracting from the first vector, just use the index directly. 3228 if (Extract.getOperand(0) == VecIn1) { 3229 BuildVecIndices.push_back(Extract.getOperand(1)); 3230 continue; 3231 } 3232 3233 // Otherwise, use InIdx + VecSize 3234 unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue(); 3235 BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, MVT::i32)); 3236 } 3237 3238 // Add count and size info. 3239 BuildVecIndices.push_back(NumElts); 3240 BuildVecIndices.push_back(DAG.getValueType(MVT::i32)); 3241 3242 // Return the new VVECTOR_SHUFFLE node. 3243 SDOperand Ops[5]; 3244 Ops[0] = VecIn1; 3245 if (VecIn2.Val) { 3246 Ops[1] = VecIn2; 3247 } else { 3248 // Use an undef vbuild_vector as input for the second operand. 3249 std::vector<SDOperand> UnOps(NumInScalars, 3250 DAG.getNode(ISD::UNDEF, 3251 cast<VTSDNode>(EltType)->getVT())); 3252 UnOps.push_back(NumElts); 3253 UnOps.push_back(EltType); 3254 Ops[1] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 3255 &UnOps[0], UnOps.size()); 3256 AddToWorkList(Ops[1].Val); 3257 } 3258 Ops[2] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 3259 &BuildVecIndices[0], BuildVecIndices.size()); 3260 Ops[3] = NumElts; 3261 Ops[4] = EltType; 3262 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops, 5); 3263 } 3264 3265 return SDOperand(); 3266} 3267 3268SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { 3269 SDOperand ShufMask = N->getOperand(2); 3270 unsigned NumElts = ShufMask.getNumOperands(); 3271 3272 // If the shuffle mask is an identity operation on the LHS, return the LHS. 3273 bool isIdentity = true; 3274 for (unsigned i = 0; i != NumElts; ++i) { 3275 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 3276 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 3277 isIdentity = false; 3278 break; 3279 } 3280 } 3281 if (isIdentity) return N->getOperand(0); 3282 3283 // If the shuffle mask is an identity operation on the RHS, return the RHS. 3284 isIdentity = true; 3285 for (unsigned i = 0; i != NumElts; ++i) { 3286 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 3287 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 3288 isIdentity = false; 3289 break; 3290 } 3291 } 3292 if (isIdentity) return N->getOperand(1); 3293 3294 // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not 3295 // needed at all. 3296 bool isUnary = true; 3297 bool isSplat = true; 3298 int VecNum = -1; 3299 unsigned BaseIdx = 0; 3300 for (unsigned i = 0; i != NumElts; ++i) 3301 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { 3302 unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue(); 3303 int V = (Idx < NumElts) ? 0 : 1; 3304 if (VecNum == -1) { 3305 VecNum = V; 3306 BaseIdx = Idx; 3307 } else { 3308 if (BaseIdx != Idx) 3309 isSplat = false; 3310 if (VecNum != V) { 3311 isUnary = false; 3312 break; 3313 } 3314 } 3315 } 3316 3317 SDOperand N0 = N->getOperand(0); 3318 SDOperand N1 = N->getOperand(1); 3319 // Normalize unary shuffle so the RHS is undef. 3320 if (isUnary && VecNum == 1) 3321 std::swap(N0, N1); 3322 3323 // If it is a splat, check if the argument vector is a build_vector with 3324 // all scalar elements the same. 3325 if (isSplat) { 3326 SDNode *V = N0.Val; 3327 if (V->getOpcode() == ISD::BIT_CONVERT) 3328 V = V->getOperand(0).Val; 3329 if (V->getOpcode() == ISD::BUILD_VECTOR) { 3330 unsigned NumElems = V->getNumOperands()-2; 3331 if (NumElems > BaseIdx) { 3332 SDOperand Base; 3333 bool AllSame = true; 3334 for (unsigned i = 0; i != NumElems; ++i) { 3335 if (V->getOperand(i).getOpcode() != ISD::UNDEF) { 3336 Base = V->getOperand(i); 3337 break; 3338 } 3339 } 3340 // Splat of <u, u, u, u>, return <u, u, u, u> 3341 if (!Base.Val) 3342 return N0; 3343 for (unsigned i = 0; i != NumElems; ++i) { 3344 if (V->getOperand(i).getOpcode() != ISD::UNDEF && 3345 V->getOperand(i) != Base) { 3346 AllSame = false; 3347 break; 3348 } 3349 } 3350 // Splat of <x, x, x, x>, return <x, x, x, x> 3351 if (AllSame) 3352 return N0; 3353 } 3354 } 3355 } 3356 3357 // If it is a unary or the LHS and the RHS are the same node, turn the RHS 3358 // into an undef. 3359 if (isUnary || N0 == N1) { 3360 if (N0.getOpcode() == ISD::UNDEF) 3361 return DAG.getNode(ISD::UNDEF, N->getValueType(0)); 3362 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 3363 // first operand. 3364 SmallVector<SDOperand, 8> MappedOps; 3365 for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) { 3366 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 3367 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 3368 MappedOps.push_back(ShufMask.getOperand(i)); 3369 } else { 3370 unsigned NewIdx = 3371 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 3372 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 3373 } 3374 } 3375 ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(), 3376 &MappedOps[0], MappedOps.size()); 3377 AddToWorkList(ShufMask.Val); 3378 return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0), 3379 N0, 3380 DAG.getNode(ISD::UNDEF, N->getValueType(0)), 3381 ShufMask); 3382 } 3383 3384 return SDOperand(); 3385} 3386 3387SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) { 3388 SDOperand ShufMask = N->getOperand(2); 3389 unsigned NumElts = ShufMask.getNumOperands()-2; 3390 3391 // If the shuffle mask is an identity operation on the LHS, return the LHS. 3392 bool isIdentity = true; 3393 for (unsigned i = 0; i != NumElts; ++i) { 3394 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 3395 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) { 3396 isIdentity = false; 3397 break; 3398 } 3399 } 3400 if (isIdentity) return N->getOperand(0); 3401 3402 // If the shuffle mask is an identity operation on the RHS, return the RHS. 3403 isIdentity = true; 3404 for (unsigned i = 0; i != NumElts; ++i) { 3405 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 3406 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) { 3407 isIdentity = false; 3408 break; 3409 } 3410 } 3411 if (isIdentity) return N->getOperand(1); 3412 3413 // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not 3414 // needed at all. 3415 bool isUnary = true; 3416 bool isSplat = true; 3417 int VecNum = -1; 3418 unsigned BaseIdx = 0; 3419 for (unsigned i = 0; i != NumElts; ++i) 3420 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { 3421 unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue(); 3422 int V = (Idx < NumElts) ? 0 : 1; 3423 if (VecNum == -1) { 3424 VecNum = V; 3425 BaseIdx = Idx; 3426 } else { 3427 if (BaseIdx != Idx) 3428 isSplat = false; 3429 if (VecNum != V) { 3430 isUnary = false; 3431 break; 3432 } 3433 } 3434 } 3435 3436 SDOperand N0 = N->getOperand(0); 3437 SDOperand N1 = N->getOperand(1); 3438 // Normalize unary shuffle so the RHS is undef. 3439 if (isUnary && VecNum == 1) 3440 std::swap(N0, N1); 3441 3442 // If it is a splat, check if the argument vector is a build_vector with 3443 // all scalar elements the same. 3444 if (isSplat) { 3445 SDNode *V = N0.Val; 3446 3447 // If this is a vbit convert that changes the element type of the vector but 3448 // not the number of vector elements, look through it. Be careful not to 3449 // look though conversions that change things like v4f32 to v2f64. 3450 if (V->getOpcode() == ISD::VBIT_CONVERT) { 3451 SDOperand ConvInput = V->getOperand(0); 3452 if (ConvInput.getValueType() == MVT::Vector && 3453 NumElts == 3454 ConvInput.getConstantOperandVal(ConvInput.getNumOperands()-2)) 3455 V = ConvInput.Val; 3456 } 3457 3458 if (V->getOpcode() == ISD::VBUILD_VECTOR) { 3459 unsigned NumElems = V->getNumOperands()-2; 3460 if (NumElems > BaseIdx) { 3461 SDOperand Base; 3462 bool AllSame = true; 3463 for (unsigned i = 0; i != NumElems; ++i) { 3464 if (V->getOperand(i).getOpcode() != ISD::UNDEF) { 3465 Base = V->getOperand(i); 3466 break; 3467 } 3468 } 3469 // Splat of <u, u, u, u>, return <u, u, u, u> 3470 if (!Base.Val) 3471 return N0; 3472 for (unsigned i = 0; i != NumElems; ++i) { 3473 if (V->getOperand(i).getOpcode() != ISD::UNDEF && 3474 V->getOperand(i) != Base) { 3475 AllSame = false; 3476 break; 3477 } 3478 } 3479 // Splat of <x, x, x, x>, return <x, x, x, x> 3480 if (AllSame) 3481 return N0; 3482 } 3483 } 3484 } 3485 3486 // If it is a unary or the LHS and the RHS are the same node, turn the RHS 3487 // into an undef. 3488 if (isUnary || N0 == N1) { 3489 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 3490 // first operand. 3491 SmallVector<SDOperand, 8> MappedOps; 3492 for (unsigned i = 0; i != NumElts; ++i) { 3493 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 3494 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) { 3495 MappedOps.push_back(ShufMask.getOperand(i)); 3496 } else { 3497 unsigned NewIdx = 3498 cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts; 3499 MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32)); 3500 } 3501 } 3502 // Add the type/#elts values. 3503 MappedOps.push_back(ShufMask.getOperand(NumElts)); 3504 MappedOps.push_back(ShufMask.getOperand(NumElts+1)); 3505 3506 ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(), 3507 &MappedOps[0], MappedOps.size()); 3508 AddToWorkList(ShufMask.Val); 3509 3510 // Build the undef vector. 3511 SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType()); 3512 for (unsigned i = 0; i != NumElts; ++i) 3513 MappedOps[i] = UDVal; 3514 MappedOps[NumElts ] = *(N0.Val->op_end()-2); 3515 MappedOps[NumElts+1] = *(N0.Val->op_end()-1); 3516 UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 3517 &MappedOps[0], MappedOps.size()); 3518 3519 return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 3520 N0, UDVal, ShufMask, 3521 MappedOps[NumElts], MappedOps[NumElts+1]); 3522 } 3523 3524 return SDOperand(); 3525} 3526 3527/// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform 3528/// a VAND to a vector_shuffle with the destination vector and a zero vector. 3529/// e.g. VAND V, <0xffffffff, 0, 0xffffffff, 0>. ==> 3530/// vector_shuffle V, Zero, <0, 4, 2, 4> 3531SDOperand DAGCombiner::XformToShuffleWithZero(SDNode *N) { 3532 SDOperand LHS = N->getOperand(0); 3533 SDOperand RHS = N->getOperand(1); 3534 if (N->getOpcode() == ISD::VAND) { 3535 SDOperand DstVecSize = *(LHS.Val->op_end()-2); 3536 SDOperand DstVecEVT = *(LHS.Val->op_end()-1); 3537 if (RHS.getOpcode() == ISD::VBIT_CONVERT) 3538 RHS = RHS.getOperand(0); 3539 if (RHS.getOpcode() == ISD::VBUILD_VECTOR) { 3540 std::vector<SDOperand> IdxOps; 3541 unsigned NumOps = RHS.getNumOperands(); 3542 unsigned NumElts = NumOps-2; 3543 MVT::ValueType EVT = cast<VTSDNode>(RHS.getOperand(NumOps-1))->getVT(); 3544 for (unsigned i = 0; i != NumElts; ++i) { 3545 SDOperand Elt = RHS.getOperand(i); 3546 if (!isa<ConstantSDNode>(Elt)) 3547 return SDOperand(); 3548 else if (cast<ConstantSDNode>(Elt)->isAllOnesValue()) 3549 IdxOps.push_back(DAG.getConstant(i, EVT)); 3550 else if (cast<ConstantSDNode>(Elt)->isNullValue()) 3551 IdxOps.push_back(DAG.getConstant(NumElts, EVT)); 3552 else 3553 return SDOperand(); 3554 } 3555 3556 // Let's see if the target supports this vector_shuffle. 3557 if (!TLI.isVectorClearMaskLegal(IdxOps, EVT, DAG)) 3558 return SDOperand(); 3559 3560 // Return the new VVECTOR_SHUFFLE node. 3561 SDOperand NumEltsNode = DAG.getConstant(NumElts, MVT::i32); 3562 SDOperand EVTNode = DAG.getValueType(EVT); 3563 std::vector<SDOperand> Ops; 3564 LHS = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, LHS, NumEltsNode, 3565 EVTNode); 3566 Ops.push_back(LHS); 3567 AddToWorkList(LHS.Val); 3568 std::vector<SDOperand> ZeroOps(NumElts, DAG.getConstant(0, EVT)); 3569 ZeroOps.push_back(NumEltsNode); 3570 ZeroOps.push_back(EVTNode); 3571 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 3572 &ZeroOps[0], ZeroOps.size())); 3573 IdxOps.push_back(NumEltsNode); 3574 IdxOps.push_back(EVTNode); 3575 Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 3576 &IdxOps[0], IdxOps.size())); 3577 Ops.push_back(NumEltsNode); 3578 Ops.push_back(EVTNode); 3579 SDOperand Result = DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 3580 &Ops[0], Ops.size()); 3581 if (NumEltsNode != DstVecSize || EVTNode != DstVecEVT) { 3582 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 3583 DstVecSize, DstVecEVT); 3584 } 3585 return Result; 3586 } 3587 } 3588 return SDOperand(); 3589} 3590 3591/// visitVBinOp - Visit a binary vector operation, like VADD. IntOp indicates 3592/// the scalar operation of the vop if it is operating on an integer vector 3593/// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD). 3594SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp, 3595 ISD::NodeType FPOp) { 3596 MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT(); 3597 ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp; 3598 SDOperand LHS = N->getOperand(0); 3599 SDOperand RHS = N->getOperand(1); 3600 SDOperand Shuffle = XformToShuffleWithZero(N); 3601 if (Shuffle.Val) return Shuffle; 3602 3603 // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold 3604 // this operation. 3605 if (LHS.getOpcode() == ISD::VBUILD_VECTOR && 3606 RHS.getOpcode() == ISD::VBUILD_VECTOR) { 3607 SmallVector<SDOperand, 8> Ops; 3608 for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) { 3609 SDOperand LHSOp = LHS.getOperand(i); 3610 SDOperand RHSOp = RHS.getOperand(i); 3611 // If these two elements can't be folded, bail out. 3612 if ((LHSOp.getOpcode() != ISD::UNDEF && 3613 LHSOp.getOpcode() != ISD::Constant && 3614 LHSOp.getOpcode() != ISD::ConstantFP) || 3615 (RHSOp.getOpcode() != ISD::UNDEF && 3616 RHSOp.getOpcode() != ISD::Constant && 3617 RHSOp.getOpcode() != ISD::ConstantFP)) 3618 break; 3619 // Can't fold divide by zero. 3620 if (N->getOpcode() == ISD::VSDIV || N->getOpcode() == ISD::VUDIV) { 3621 if ((RHSOp.getOpcode() == ISD::Constant && 3622 cast<ConstantSDNode>(RHSOp.Val)->isNullValue()) || 3623 (RHSOp.getOpcode() == ISD::ConstantFP && 3624 !cast<ConstantFPSDNode>(RHSOp.Val)->getValue())) 3625 break; 3626 } 3627 Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp)); 3628 AddToWorkList(Ops.back().Val); 3629 assert((Ops.back().getOpcode() == ISD::UNDEF || 3630 Ops.back().getOpcode() == ISD::Constant || 3631 Ops.back().getOpcode() == ISD::ConstantFP) && 3632 "Scalar binop didn't fold!"); 3633 } 3634 3635 if (Ops.size() == LHS.getNumOperands()-2) { 3636 Ops.push_back(*(LHS.Val->op_end()-2)); 3637 Ops.push_back(*(LHS.Val->op_end()-1)); 3638 return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 3639 } 3640 } 3641 3642 return SDOperand(); 3643} 3644 3645SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 3646 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 3647 3648 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 3649 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 3650 // If we got a simplified select_cc node back from SimplifySelectCC, then 3651 // break it down into a new SETCC node, and a new SELECT node, and then return 3652 // the SELECT node, since we were called with a SELECT node. 3653 if (SCC.Val) { 3654 // Check to see if we got a select_cc back (to turn into setcc/select). 3655 // Otherwise, just return whatever node we got back, like fabs. 3656 if (SCC.getOpcode() == ISD::SELECT_CC) { 3657 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 3658 SCC.getOperand(0), SCC.getOperand(1), 3659 SCC.getOperand(4)); 3660 AddToWorkList(SETCC.Val); 3661 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 3662 SCC.getOperand(3), SETCC); 3663 } 3664 return SCC; 3665 } 3666 return SDOperand(); 3667} 3668 3669/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS 3670/// are the two values being selected between, see if we can simplify the 3671/// select. Callers of this should assume that TheSelect is deleted if this 3672/// returns true. As such, they should return the appropriate thing (e.g. the 3673/// node) back to the top-level of the DAG combiner loop to avoid it being 3674/// looked at. 3675/// 3676bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS, 3677 SDOperand RHS) { 3678 3679 // If this is a select from two identical things, try to pull the operation 3680 // through the select. 3681 if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){ 3682 // If this is a load and the token chain is identical, replace the select 3683 // of two loads with a load through a select of the address to load from. 3684 // This triggers in things like "select bool X, 10.0, 123.0" after the FP 3685 // constants have been dropped into the constant pool. 3686 if (LHS.getOpcode() == ISD::LOAD && 3687 // Token chains must be identical. 3688 LHS.getOperand(0) == RHS.getOperand(0)) { 3689 LoadSDNode *LLD = cast<LoadSDNode>(LHS); 3690 LoadSDNode *RLD = cast<LoadSDNode>(RHS); 3691 3692 // If this is an EXTLOAD, the VT's must match. 3693 if (LLD->getLoadedVT() == RLD->getLoadedVT()) { 3694 // FIXME: this conflates two src values, discarding one. This is not 3695 // the right thing to do, but nothing uses srcvalues now. When they do, 3696 // turn SrcValue into a list of locations. 3697 SDOperand Addr; 3698 if (TheSelect->getOpcode() == ISD::SELECT) 3699 Addr = DAG.getNode(ISD::SELECT, LLD->getBasePtr().getValueType(), 3700 TheSelect->getOperand(0), LLD->getBasePtr(), 3701 RLD->getBasePtr()); 3702 else 3703 Addr = DAG.getNode(ISD::SELECT_CC, LLD->getBasePtr().getValueType(), 3704 TheSelect->getOperand(0), 3705 TheSelect->getOperand(1), 3706 LLD->getBasePtr(), RLD->getBasePtr(), 3707 TheSelect->getOperand(4)); 3708 3709 SDOperand Load; 3710 if (LLD->getExtensionType() == ISD::NON_EXTLOAD) 3711 Load = DAG.getLoad(TheSelect->getValueType(0), LLD->getChain(), 3712 Addr,LLD->getSrcValue(), LLD->getSrcValueOffset()); 3713 else { 3714 Load = DAG.getExtLoad(LLD->getExtensionType(), 3715 TheSelect->getValueType(0), 3716 LLD->getChain(), Addr, LLD->getSrcValue(), 3717 LLD->getSrcValueOffset(), 3718 LLD->getLoadedVT()); 3719 } 3720 // Users of the select now use the result of the load. 3721 CombineTo(TheSelect, Load); 3722 3723 // Users of the old loads now use the new load's chain. We know the 3724 // old-load value is dead now. 3725 CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1)); 3726 CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1)); 3727 return true; 3728 } 3729 } 3730 } 3731 3732 return false; 3733} 3734 3735SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 3736 SDOperand N2, SDOperand N3, 3737 ISD::CondCode CC) { 3738 3739 MVT::ValueType VT = N2.getValueType(); 3740 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 3741 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 3742 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 3743 3744 // Determine if the condition we're dealing with is constant 3745 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 3746 if (SCC.Val) AddToWorkList(SCC.Val); 3747 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 3748 3749 // fold select_cc true, x, y -> x 3750 if (SCCC && SCCC->getValue()) 3751 return N2; 3752 // fold select_cc false, x, y -> y 3753 if (SCCC && SCCC->getValue() == 0) 3754 return N3; 3755 3756 // Check to see if we can simplify the select into an fabs node 3757 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 3758 // Allow either -0.0 or 0.0 3759 if (CFP->getValue() == 0.0) { 3760 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 3761 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 3762 N0 == N2 && N3.getOpcode() == ISD::FNEG && 3763 N2 == N3.getOperand(0)) 3764 return DAG.getNode(ISD::FABS, VT, N0); 3765 3766 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 3767 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 3768 N0 == N3 && N2.getOpcode() == ISD::FNEG && 3769 N2.getOperand(0) == N3) 3770 return DAG.getNode(ISD::FABS, VT, N3); 3771 } 3772 } 3773 3774 // Check to see if we can perform the "gzip trick", transforming 3775 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 3776 if (N1C && N3C && N3C->isNullValue() && CC == ISD::SETLT && 3777 MVT::isInteger(N0.getValueType()) && 3778 MVT::isInteger(N2.getValueType()) && 3779 (N1C->isNullValue() || // (a < 0) ? b : 0 3780 (N1C->getValue() == 1 && N0 == N2))) { // (a < 1) ? a : 0 3781 MVT::ValueType XType = N0.getValueType(); 3782 MVT::ValueType AType = N2.getValueType(); 3783 if (XType >= AType) { 3784 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 3785 // single-bit constant. 3786 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) { 3787 unsigned ShCtV = Log2_64(N2C->getValue()); 3788 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1; 3789 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 3790 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 3791 AddToWorkList(Shift.Val); 3792 if (XType > AType) { 3793 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 3794 AddToWorkList(Shift.Val); 3795 } 3796 return DAG.getNode(ISD::AND, AType, Shift, N2); 3797 } 3798 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 3799 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3800 TLI.getShiftAmountTy())); 3801 AddToWorkList(Shift.Val); 3802 if (XType > AType) { 3803 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 3804 AddToWorkList(Shift.Val); 3805 } 3806 return DAG.getNode(ISD::AND, AType, Shift, N2); 3807 } 3808 } 3809 3810 // fold select C, 16, 0 -> shl C, 4 3811 if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) && 3812 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) { 3813 // Get a SetCC of the condition 3814 // FIXME: Should probably make sure that setcc is legal if we ever have a 3815 // target where it isn't. 3816 SDOperand Temp, SCC; 3817 // cast from setcc result type to select result type 3818 if (AfterLegalize) { 3819 SCC = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 3820 if (N2.getValueType() < SCC.getValueType()) 3821 Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType()); 3822 else 3823 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 3824 } else { 3825 SCC = DAG.getSetCC(MVT::i1, N0, N1, CC); 3826 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 3827 } 3828 AddToWorkList(SCC.Val); 3829 AddToWorkList(Temp.Val); 3830 // shl setcc result by log2 n2c 3831 return DAG.getNode(ISD::SHL, N2.getValueType(), Temp, 3832 DAG.getConstant(Log2_64(N2C->getValue()), 3833 TLI.getShiftAmountTy())); 3834 } 3835 3836 // Check to see if this is the equivalent of setcc 3837 // FIXME: Turn all of these into setcc if setcc if setcc is legal 3838 // otherwise, go ahead with the folds. 3839 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) { 3840 MVT::ValueType XType = N0.getValueType(); 3841 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) { 3842 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 3843 if (Res.getValueType() != VT) 3844 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 3845 return Res; 3846 } 3847 3848 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 3849 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 3850 TLI.isOperationLegal(ISD::CTLZ, XType)) { 3851 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 3852 return DAG.getNode(ISD::SRL, XType, Ctlz, 3853 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)), 3854 TLI.getShiftAmountTy())); 3855 } 3856 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 3857 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 3858 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 3859 N0); 3860 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 3861 DAG.getConstant(~0ULL, XType)); 3862 return DAG.getNode(ISD::SRL, XType, 3863 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 3864 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3865 TLI.getShiftAmountTy())); 3866 } 3867 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 3868 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 3869 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0, 3870 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3871 TLI.getShiftAmountTy())); 3872 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 3873 } 3874 } 3875 3876 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 3877 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 3878 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 3879 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) { 3880 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) { 3881 MVT::ValueType XType = N0.getValueType(); 3882 if (SubC->isNullValue() && MVT::isInteger(XType)) { 3883 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 3884 DAG.getConstant(MVT::getSizeInBits(XType)-1, 3885 TLI.getShiftAmountTy())); 3886 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 3887 AddToWorkList(Shift.Val); 3888 AddToWorkList(Add.Val); 3889 return DAG.getNode(ISD::XOR, XType, Add, Shift); 3890 } 3891 } 3892 } 3893 3894 return SDOperand(); 3895} 3896 3897SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 3898 SDOperand N1, ISD::CondCode Cond, 3899 bool foldBooleans) { 3900 // These setcc operations always fold. 3901 switch (Cond) { 3902 default: break; 3903 case ISD::SETFALSE: 3904 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 3905 case ISD::SETTRUE: 3906 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 3907 } 3908 3909 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 3910 uint64_t C1 = N1C->getValue(); 3911 if (isa<ConstantSDNode>(N0.Val)) { 3912 return DAG.FoldSetCC(VT, N0, N1, Cond); 3913 } else { 3914 // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an 3915 // equality comparison, then we're just comparing whether X itself is 3916 // zero. 3917 if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) && 3918 N0.getOperand(0).getOpcode() == ISD::CTLZ && 3919 N0.getOperand(1).getOpcode() == ISD::Constant) { 3920 unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 3921 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 3922 ShAmt == Log2_32(MVT::getSizeInBits(N0.getValueType()))) { 3923 if ((C1 == 0) == (Cond == ISD::SETEQ)) { 3924 // (srl (ctlz x), 5) == 0 -> X != 0 3925 // (srl (ctlz x), 5) != 1 -> X != 0 3926 Cond = ISD::SETNE; 3927 } else { 3928 // (srl (ctlz x), 5) != 0 -> X == 0 3929 // (srl (ctlz x), 5) == 1 -> X == 0 3930 Cond = ISD::SETEQ; 3931 } 3932 SDOperand Zero = DAG.getConstant(0, N0.getValueType()); 3933 return DAG.getSetCC(VT, N0.getOperand(0).getOperand(0), 3934 Zero, Cond); 3935 } 3936 } 3937 3938 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 3939 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 3940 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 3941 3942 // If the comparison constant has bits in the upper part, the 3943 // zero-extended value could never match. 3944 if (C1 & (~0ULL << InSize)) { 3945 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 3946 switch (Cond) { 3947 case ISD::SETUGT: 3948 case ISD::SETUGE: 3949 case ISD::SETEQ: return DAG.getConstant(0, VT); 3950 case ISD::SETULT: 3951 case ISD::SETULE: 3952 case ISD::SETNE: return DAG.getConstant(1, VT); 3953 case ISD::SETGT: 3954 case ISD::SETGE: 3955 // True if the sign bit of C1 is set. 3956 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 3957 case ISD::SETLT: 3958 case ISD::SETLE: 3959 // True if the sign bit of C1 isn't set. 3960 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 3961 default: 3962 break; 3963 } 3964 } 3965 3966 // Otherwise, we can perform the comparison with the low bits. 3967 switch (Cond) { 3968 case ISD::SETEQ: 3969 case ISD::SETNE: 3970 case ISD::SETUGT: 3971 case ISD::SETUGE: 3972 case ISD::SETULT: 3973 case ISD::SETULE: 3974 return DAG.getSetCC(VT, N0.getOperand(0), 3975 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 3976 Cond); 3977 default: 3978 break; // todo, be more careful with signed comparisons 3979 } 3980 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 3981 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 3982 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 3983 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 3984 MVT::ValueType ExtDstTy = N0.getValueType(); 3985 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 3986 3987 // If the extended part has any inconsistent bits, it cannot ever 3988 // compare equal. In other words, they have to be all ones or all 3989 // zeros. 3990 uint64_t ExtBits = 3991 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 3992 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 3993 return DAG.getConstant(Cond == ISD::SETNE, VT); 3994 3995 SDOperand ZextOp; 3996 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 3997 if (Op0Ty == ExtSrcTy) { 3998 ZextOp = N0.getOperand(0); 3999 } else { 4000 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 4001 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 4002 DAG.getConstant(Imm, Op0Ty)); 4003 } 4004 AddToWorkList(ZextOp.Val); 4005 // Otherwise, make this a use of a zext. 4006 return DAG.getSetCC(VT, ZextOp, 4007 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 4008 ExtDstTy), 4009 Cond); 4010 } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) && 4011 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 4012 4013 // SETCC (SETCC), [0|1], [EQ|NE] -> SETCC 4014 if (N0.getOpcode() == ISD::SETCC) { 4015 bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getValue() != 1); 4016 if (TrueWhenTrue) 4017 return N0; 4018 4019 // Invert the condition. 4020 ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get(); 4021 CC = ISD::getSetCCInverse(CC, 4022 MVT::isInteger(N0.getOperand(0).getValueType())); 4023 return DAG.getSetCC(VT, N0.getOperand(0), N0.getOperand(1), CC); 4024 } 4025 4026 if ((N0.getOpcode() == ISD::XOR || 4027 (N0.getOpcode() == ISD::AND && 4028 N0.getOperand(0).getOpcode() == ISD::XOR && 4029 N0.getOperand(1) == N0.getOperand(0).getOperand(1))) && 4030 isa<ConstantSDNode>(N0.getOperand(1)) && 4031 cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) { 4032 // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We 4033 // can only do this if the top bits are known zero. 4034 if (TLI.MaskedValueIsZero(N0, 4035 MVT::getIntVTBitMask(N0.getValueType())-1)){ 4036 // Okay, get the un-inverted input value. 4037 SDOperand Val; 4038 if (N0.getOpcode() == ISD::XOR) 4039 Val = N0.getOperand(0); 4040 else { 4041 assert(N0.getOpcode() == ISD::AND && 4042 N0.getOperand(0).getOpcode() == ISD::XOR); 4043 // ((X^1)&1)^1 -> X & 1 4044 Val = DAG.getNode(ISD::AND, N0.getValueType(), 4045 N0.getOperand(0).getOperand(0), 4046 N0.getOperand(1)); 4047 } 4048 return DAG.getSetCC(VT, Val, N1, 4049 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ); 4050 } 4051 } 4052 } 4053 4054 uint64_t MinVal, MaxVal; 4055 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 4056 if (ISD::isSignedIntSetCC(Cond)) { 4057 MinVal = 1ULL << (OperandBitSize-1); 4058 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 4059 MaxVal = ~0ULL >> (65-OperandBitSize); 4060 else 4061 MaxVal = 0; 4062 } else { 4063 MinVal = 0; 4064 MaxVal = ~0ULL >> (64-OperandBitSize); 4065 } 4066 4067 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 4068 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 4069 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 4070 --C1; // X >= C0 --> X > (C0-1) 4071 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 4072 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 4073 } 4074 4075 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 4076 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 4077 ++C1; // X <= C0 --> X < (C0+1) 4078 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 4079 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 4080 } 4081 4082 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 4083 return DAG.getConstant(0, VT); // X < MIN --> false 4084 4085 // Canonicalize setgt X, Min --> setne X, Min 4086 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 4087 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 4088 // Canonicalize setlt X, Max --> setne X, Max 4089 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal) 4090 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 4091 4092 // If we have setult X, 1, turn it into seteq X, 0 4093 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 4094 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 4095 ISD::SETEQ); 4096 // If we have setugt X, Max-1, turn it into seteq X, Max 4097 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 4098 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 4099 ISD::SETEQ); 4100 4101 // If we have "setcc X, C0", check to see if we can shrink the immediate 4102 // by changing cc. 4103 4104 // SETUGT X, SINTMAX -> SETLT X, 0 4105 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 4106 C1 == (~0ULL >> (65-OperandBitSize))) 4107 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 4108 ISD::SETLT); 4109 4110 // FIXME: Implement the rest of these. 4111 4112 // Fold bit comparisons when we can. 4113 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 4114 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 4115 if (ConstantSDNode *AndRHS = 4116 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 4117 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 4118 // Perform the xform if the AND RHS is a single bit. 4119 if (isPowerOf2_64(AndRHS->getValue())) { 4120 return DAG.getNode(ISD::SRL, VT, N0, 4121 DAG.getConstant(Log2_64(AndRHS->getValue()), 4122 TLI.getShiftAmountTy())); 4123 } 4124 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 4125 // (X & 8) == 8 --> (X & 8) >> 3 4126 // Perform the xform if C1 is a single bit. 4127 if (isPowerOf2_64(C1)) { 4128 return DAG.getNode(ISD::SRL, VT, N0, 4129 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 4130 } 4131 } 4132 } 4133 } 4134 } else if (isa<ConstantSDNode>(N0.Val)) { 4135 // Ensure that the constant occurs on the RHS. 4136 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 4137 } 4138 4139 if (isa<ConstantFPSDNode>(N0.Val)) { 4140 // Constant fold or commute setcc. 4141 SDOperand O = DAG.FoldSetCC(VT, N0, N1, Cond); 4142 if (O.Val) return O; 4143 } 4144 4145 if (N0 == N1) { 4146 // We can always fold X == X for integer setcc's. 4147 if (MVT::isInteger(N0.getValueType())) 4148 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 4149 unsigned UOF = ISD::getUnorderedFlavor(Cond); 4150 if (UOF == 2) // FP operators that are undefined on NaNs. 4151 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 4152 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 4153 return DAG.getConstant(UOF, VT); 4154 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 4155 // if it is not already. 4156 ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO; 4157 if (NewCond != Cond) 4158 return DAG.getSetCC(VT, N0, N1, NewCond); 4159 } 4160 4161 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 4162 MVT::isInteger(N0.getValueType())) { 4163 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 4164 N0.getOpcode() == ISD::XOR) { 4165 // Simplify (X+Y) == (X+Z) --> Y == Z 4166 if (N0.getOpcode() == N1.getOpcode()) { 4167 if (N0.getOperand(0) == N1.getOperand(0)) 4168 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 4169 if (N0.getOperand(1) == N1.getOperand(1)) 4170 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 4171 if (DAG.isCommutativeBinOp(N0.getOpcode())) { 4172 // If X op Y == Y op X, try other combinations. 4173 if (N0.getOperand(0) == N1.getOperand(1)) 4174 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 4175 if (N0.getOperand(1) == N1.getOperand(0)) 4176 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond); 4177 } 4178 } 4179 4180 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 4181 if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 4182 // Turn (X+C1) == C2 --> X == C2-C1 4183 if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) { 4184 return DAG.getSetCC(VT, N0.getOperand(0), 4185 DAG.getConstant(RHSC->getValue()-LHSR->getValue(), 4186 N0.getValueType()), Cond); 4187 } 4188 4189 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. 4190 if (N0.getOpcode() == ISD::XOR) 4191 // If we know that all of the inverted bits are zero, don't bother 4192 // performing the inversion. 4193 if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue())) 4194 return DAG.getSetCC(VT, N0.getOperand(0), 4195 DAG.getConstant(LHSR->getValue()^RHSC->getValue(), 4196 N0.getValueType()), Cond); 4197 } 4198 4199 // Turn (C1-X) == C2 --> X == C1-C2 4200 if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) { 4201 if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) { 4202 return DAG.getSetCC(VT, N0.getOperand(1), 4203 DAG.getConstant(SUBC->getValue()-RHSC->getValue(), 4204 N0.getValueType()), Cond); 4205 } 4206 } 4207 } 4208 4209 // Simplify (X+Z) == X --> Z == 0 4210 if (N0.getOperand(0) == N1) 4211 return DAG.getSetCC(VT, N0.getOperand(1), 4212 DAG.getConstant(0, N0.getValueType()), Cond); 4213 if (N0.getOperand(1) == N1) { 4214 if (DAG.isCommutativeBinOp(N0.getOpcode())) 4215 return DAG.getSetCC(VT, N0.getOperand(0), 4216 DAG.getConstant(0, N0.getValueType()), Cond); 4217 else { 4218 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 4219 // (Z-X) == X --> Z == X<<1 4220 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 4221 N1, 4222 DAG.getConstant(1,TLI.getShiftAmountTy())); 4223 AddToWorkList(SH.Val); 4224 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 4225 } 4226 } 4227 } 4228 4229 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 4230 N1.getOpcode() == ISD::XOR) { 4231 // Simplify X == (X+Z) --> Z == 0 4232 if (N1.getOperand(0) == N0) { 4233 return DAG.getSetCC(VT, N1.getOperand(1), 4234 DAG.getConstant(0, N1.getValueType()), Cond); 4235 } else if (N1.getOperand(1) == N0) { 4236 if (DAG.isCommutativeBinOp(N1.getOpcode())) { 4237 return DAG.getSetCC(VT, N1.getOperand(0), 4238 DAG.getConstant(0, N1.getValueType()), Cond); 4239 } else { 4240 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 4241 // X == (Z-X) --> X<<1 == Z 4242 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 4243 DAG.getConstant(1,TLI.getShiftAmountTy())); 4244 AddToWorkList(SH.Val); 4245 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 4246 } 4247 } 4248 } 4249 } 4250 4251 // Fold away ALL boolean setcc's. 4252 SDOperand Temp; 4253 if (N0.getValueType() == MVT::i1 && foldBooleans) { 4254 switch (Cond) { 4255 default: assert(0 && "Unknown integer setcc!"); 4256 case ISD::SETEQ: // X == Y -> (X^Y)^1 4257 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 4258 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 4259 AddToWorkList(Temp.Val); 4260 break; 4261 case ISD::SETNE: // X != Y --> (X^Y) 4262 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 4263 break; 4264 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 4265 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 4266 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 4267 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 4268 AddToWorkList(Temp.Val); 4269 break; 4270 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 4271 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 4272 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 4273 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 4274 AddToWorkList(Temp.Val); 4275 break; 4276 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 4277 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 4278 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 4279 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 4280 AddToWorkList(Temp.Val); 4281 break; 4282 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 4283 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 4284 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 4285 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 4286 break; 4287 } 4288 if (VT != MVT::i1) { 4289 AddToWorkList(N0.Val); 4290 // FIXME: If running after legalize, we probably can't do this. 4291 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 4292 } 4293 return N0; 4294 } 4295 4296 // Could not fold it. 4297 return SDOperand(); 4298} 4299 4300/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 4301/// return a DAG expression to select that will generate the same value by 4302/// multiplying by a magic number. See: 4303/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 4304SDOperand DAGCombiner::BuildSDIV(SDNode *N) { 4305 std::vector<SDNode*> Built; 4306 SDOperand S = TLI.BuildSDIV(N, DAG, &Built); 4307 4308 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 4309 ii != ee; ++ii) 4310 AddToWorkList(*ii); 4311 return S; 4312} 4313 4314/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 4315/// return a DAG expression to select that will generate the same value by 4316/// multiplying by a magic number. See: 4317/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 4318SDOperand DAGCombiner::BuildUDIV(SDNode *N) { 4319 std::vector<SDNode*> Built; 4320 SDOperand S = TLI.BuildUDIV(N, DAG, &Built); 4321 4322 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 4323 ii != ee; ++ii) 4324 AddToWorkList(*ii); 4325 return S; 4326} 4327 4328/// FindBaseOffset - Return true if base is known not to alias with anything 4329/// but itself. Provides base object and offset as results. 4330static bool FindBaseOffset(SDOperand Ptr, SDOperand &Base, int64_t &Offset) { 4331 // Assume it is a primitive operation. 4332 Base = Ptr; Offset = 0; 4333 4334 // If it's an adding a simple constant then integrate the offset. 4335 if (Base.getOpcode() == ISD::ADD) { 4336 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Base.getOperand(1))) { 4337 Base = Base.getOperand(0); 4338 Offset += C->getValue(); 4339 } 4340 } 4341 4342 // If it's any of the following then it can't alias with anything but itself. 4343 return isa<FrameIndexSDNode>(Base) || 4344 isa<ConstantPoolSDNode>(Base) || 4345 isa<GlobalAddressSDNode>(Base); 4346} 4347 4348/// isAlias - Return true if there is any possibility that the two addresses 4349/// overlap. 4350bool DAGCombiner::isAlias(SDOperand Ptr1, int64_t Size1, 4351 const Value *SrcValue1, int SrcValueOffset1, 4352 SDOperand Ptr2, int64_t Size2, 4353 const Value *SrcValue2, int SrcValueOffset2) 4354{ 4355 // If they are the same then they must be aliases. 4356 if (Ptr1 == Ptr2) return true; 4357 4358 // Gather base node and offset information. 4359 SDOperand Base1, Base2; 4360 int64_t Offset1, Offset2; 4361 bool KnownBase1 = FindBaseOffset(Ptr1, Base1, Offset1); 4362 bool KnownBase2 = FindBaseOffset(Ptr2, Base2, Offset2); 4363 4364 // If they have a same base address then... 4365 if (Base1 == Base2) { 4366 // Check to see if the addresses overlap. 4367 return!((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1); 4368 } 4369 4370 // If we know both bases then they can't alias. 4371 if (KnownBase1 && KnownBase2) return false; 4372 4373 if (CombinerGlobalAA) { 4374 // Use alias analysis information. 4375 int Overlap1 = Size1 + SrcValueOffset1 + Offset1; 4376 int Overlap2 = Size2 + SrcValueOffset2 + Offset2; 4377 AliasAnalysis::AliasResult AAResult = 4378 AA.alias(SrcValue1, Overlap1, SrcValue2, Overlap2); 4379 if (AAResult == AliasAnalysis::NoAlias) 4380 return false; 4381 } 4382 4383 // Otherwise we have to assume they alias. 4384 return true; 4385} 4386 4387/// FindAliasInfo - Extracts the relevant alias information from the memory 4388/// node. Returns true if the operand was a load. 4389bool DAGCombiner::FindAliasInfo(SDNode *N, 4390 SDOperand &Ptr, int64_t &Size, 4391 const Value *&SrcValue, int &SrcValueOffset) { 4392 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 4393 Ptr = LD->getBasePtr(); 4394 Size = MVT::getSizeInBits(LD->getLoadedVT()) >> 3; 4395 SrcValue = LD->getSrcValue(); 4396 SrcValueOffset = LD->getSrcValueOffset(); 4397 return true; 4398 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 4399 Ptr = ST->getBasePtr(); 4400 Size = MVT::getSizeInBits(ST->getStoredVT()) >> 3; 4401 SrcValue = ST->getSrcValue(); 4402 SrcValueOffset = ST->getSrcValueOffset(); 4403 } else { 4404 assert(0 && "FindAliasInfo expected a memory operand"); 4405 } 4406 4407 return false; 4408} 4409 4410/// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes, 4411/// looking for aliasing nodes and adding them to the Aliases vector. 4412void DAGCombiner::GatherAllAliases(SDNode *N, SDOperand OriginalChain, 4413 SmallVector<SDOperand, 8> &Aliases) { 4414 SmallVector<SDOperand, 8> Chains; // List of chains to visit. 4415 std::set<SDNode *> Visited; // Visited node set. 4416 4417 // Get alias information for node. 4418 SDOperand Ptr; 4419 int64_t Size; 4420 const Value *SrcValue; 4421 int SrcValueOffset; 4422 bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset); 4423 4424 // Starting off. 4425 Chains.push_back(OriginalChain); 4426 4427 // Look at each chain and determine if it is an alias. If so, add it to the 4428 // aliases list. If not, then continue up the chain looking for the next 4429 // candidate. 4430 while (!Chains.empty()) { 4431 SDOperand Chain = Chains.back(); 4432 Chains.pop_back(); 4433 4434 // Don't bother if we've been before. 4435 if (Visited.find(Chain.Val) != Visited.end()) continue; 4436 Visited.insert(Chain.Val); 4437 4438 switch (Chain.getOpcode()) { 4439 case ISD::EntryToken: 4440 // Entry token is ideal chain operand, but handled in FindBetterChain. 4441 break; 4442 4443 case ISD::LOAD: 4444 case ISD::STORE: { 4445 // Get alias information for Chain. 4446 SDOperand OpPtr; 4447 int64_t OpSize; 4448 const Value *OpSrcValue; 4449 int OpSrcValueOffset; 4450 bool IsOpLoad = FindAliasInfo(Chain.Val, OpPtr, OpSize, 4451 OpSrcValue, OpSrcValueOffset); 4452 4453 // If chain is alias then stop here. 4454 if (!(IsLoad && IsOpLoad) && 4455 isAlias(Ptr, Size, SrcValue, SrcValueOffset, 4456 OpPtr, OpSize, OpSrcValue, OpSrcValueOffset)) { 4457 Aliases.push_back(Chain); 4458 } else { 4459 // Look further up the chain. 4460 Chains.push_back(Chain.getOperand(0)); 4461 // Clean up old chain. 4462 AddToWorkList(Chain.Val); 4463 } 4464 break; 4465 } 4466 4467 case ISD::TokenFactor: 4468 // We have to check each of the operands of the token factor, so we queue 4469 // then up. Adding the operands to the queue (stack) in reverse order 4470 // maintains the original order and increases the likelihood that getNode 4471 // will find a matching token factor (CSE.) 4472 for (unsigned n = Chain.getNumOperands(); n;) 4473 Chains.push_back(Chain.getOperand(--n)); 4474 // Eliminate the token factor if we can. 4475 AddToWorkList(Chain.Val); 4476 break; 4477 4478 default: 4479 // For all other instructions we will just have to take what we can get. 4480 Aliases.push_back(Chain); 4481 break; 4482 } 4483 } 4484} 4485 4486/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, looking 4487/// for a better chain (aliasing node.) 4488SDOperand DAGCombiner::FindBetterChain(SDNode *N, SDOperand OldChain) { 4489 SmallVector<SDOperand, 8> Aliases; // Ops for replacing token factor. 4490 4491 // Accumulate all the aliases to this node. 4492 GatherAllAliases(N, OldChain, Aliases); 4493 4494 if (Aliases.size() == 0) { 4495 // If no operands then chain to entry token. 4496 return DAG.getEntryNode(); 4497 } else if (Aliases.size() == 1) { 4498 // If a single operand then chain to it. We don't need to revisit it. 4499 return Aliases[0]; 4500 } 4501 4502 // Construct a custom tailored token factor. 4503 SDOperand NewChain = DAG.getNode(ISD::TokenFactor, MVT::Other, 4504 &Aliases[0], Aliases.size()); 4505 4506 // Make sure the old chain gets cleaned up. 4507 if (NewChain != OldChain) AddToWorkList(OldChain.Val); 4508 4509 return NewChain; 4510} 4511 4512// SelectionDAG::Combine - This is the entry point for the file. 4513// 4514void SelectionDAG::Combine(bool RunningAfterLegalize, AliasAnalysis &AA) { 4515 /// run - This is the main entry point to this class. 4516 /// 4517 DAGCombiner(*this, AA).Run(RunningAfterLegalize); 4518} 4519