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