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