DAGCombiner.cpp revision 25cf2275ff7de3de3bc0e508abaf457413d74725
1//===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "dagcombine" 16#include "llvm/CodeGen/SelectionDAG.h" 17#include "llvm/CodeGen/MachineFunction.h" 18#include "llvm/CodeGen/MachineFrameInfo.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/Target/TargetData.h" 21#include "llvm/Target/TargetFrameInfo.h" 22#include "llvm/Target/TargetLowering.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/Target/TargetOptions.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/Support/Compiler.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/Support/MathExtras.h" 31#include <algorithm> 32#include <set> 33using namespace llvm; 34 35STATISTIC(NodesCombined , "Number of dag nodes combined"); 36STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created"); 37STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created"); 38 39namespace { 40 static cl::opt<bool> 41 CombinerAA("combiner-alias-analysis", cl::Hidden, 42 cl::desc("Turn on alias analysis during testing")); 43 44 static cl::opt<bool> 45 CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden, 46 cl::desc("Include global information in alias analysis")); 47 48//------------------------------ DAGCombiner ---------------------------------// 49 50 class VISIBILITY_HIDDEN DAGCombiner { 51 SelectionDAG &DAG; 52 TargetLowering &TLI; 53 CombineLevel Level; 54 bool LegalOperations; 55 bool LegalTypes; 56 bool Fast; 57 58 // Worklist of all of the nodes that need to be simplified. 59 std::vector<SDNode*> WorkList; 60 61 // AA - Used for DAG load/store alias analysis. 62 AliasAnalysis &AA; 63 64 /// AddUsersToWorkList - When an instruction is simplified, add all users of 65 /// the instruction to the work lists because they might get more simplified 66 /// now. 67 /// 68 void AddUsersToWorkList(SDNode *N) { 69 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 70 UI != UE; ++UI) 71 AddToWorkList(*UI); 72 } 73 74 /// visit - call the node-specific routine that knows how to fold each 75 /// particular type of node. 76 SDValue visit(SDNode *N); 77 78 public: 79 /// AddToWorkList - Add to the work list making sure it's instance is at the 80 /// the back (next to be processed.) 81 void AddToWorkList(SDNode *N) { 82 removeFromWorkList(N); 83 WorkList.push_back(N); 84 } 85 86 /// removeFromWorkList - remove all instances of N from the worklist. 87 /// 88 void removeFromWorkList(SDNode *N) { 89 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 90 WorkList.end()); 91 } 92 93 SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo, 94 bool AddTo = true); 95 96 SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) { 97 return CombineTo(N, &Res, 1, AddTo); 98 } 99 100 SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1, 101 bool AddTo = true) { 102 SDValue To[] = { Res0, Res1 }; 103 return CombineTo(N, To, 2, AddTo); 104 } 105 106 private: 107 108 /// SimplifyDemandedBits - Check the specified integer node value to see if 109 /// it can be simplified or if things it uses can be simplified by bit 110 /// propagation. If so, return true. 111 bool SimplifyDemandedBits(SDValue Op) { 112 APInt Demanded = APInt::getAllOnesValue(Op.getValueSizeInBits()); 113 return SimplifyDemandedBits(Op, Demanded); 114 } 115 116 bool SimplifyDemandedBits(SDValue Op, const APInt &Demanded); 117 118 bool CombineToPreIndexedLoadStore(SDNode *N); 119 bool CombineToPostIndexedLoadStore(SDNode *N); 120 121 122 /// combine - call the node-specific routine that knows how to fold each 123 /// particular type of node. If that doesn't do anything, try the 124 /// target-specific DAG combines. 125 SDValue combine(SDNode *N); 126 127 // Visitation implementation - Implement dag node combining for different 128 // node types. The semantics are as follows: 129 // Return Value: 130 // SDValue.getNode() == 0 - No change was made 131 // SDValue.getNode() == N - N was replaced, is dead and has been handled. 132 // otherwise - N should be replaced by the returned Operand. 133 // 134 SDValue visitTokenFactor(SDNode *N); 135 SDValue visitMERGE_VALUES(SDNode *N); 136 SDValue visitADD(SDNode *N); 137 SDValue visitSUB(SDNode *N); 138 SDValue visitADDC(SDNode *N); 139 SDValue visitADDE(SDNode *N); 140 SDValue visitMUL(SDNode *N); 141 SDValue visitSDIV(SDNode *N); 142 SDValue visitUDIV(SDNode *N); 143 SDValue visitSREM(SDNode *N); 144 SDValue visitUREM(SDNode *N); 145 SDValue visitMULHU(SDNode *N); 146 SDValue visitMULHS(SDNode *N); 147 SDValue visitSMUL_LOHI(SDNode *N); 148 SDValue visitUMUL_LOHI(SDNode *N); 149 SDValue visitSDIVREM(SDNode *N); 150 SDValue visitUDIVREM(SDNode *N); 151 SDValue visitAND(SDNode *N); 152 SDValue visitOR(SDNode *N); 153 SDValue visitXOR(SDNode *N); 154 SDValue SimplifyVBinOp(SDNode *N); 155 SDValue visitSHL(SDNode *N); 156 SDValue visitSRA(SDNode *N); 157 SDValue visitSRL(SDNode *N); 158 SDValue visitCTLZ(SDNode *N); 159 SDValue visitCTTZ(SDNode *N); 160 SDValue visitCTPOP(SDNode *N); 161 SDValue visitSELECT(SDNode *N); 162 SDValue visitSELECT_CC(SDNode *N); 163 SDValue visitSETCC(SDNode *N); 164 SDValue visitSIGN_EXTEND(SDNode *N); 165 SDValue visitZERO_EXTEND(SDNode *N); 166 SDValue visitANY_EXTEND(SDNode *N); 167 SDValue visitSIGN_EXTEND_INREG(SDNode *N); 168 SDValue visitTRUNCATE(SDNode *N); 169 SDValue visitBIT_CONVERT(SDNode *N); 170 SDValue visitBUILD_PAIR(SDNode *N); 171 SDValue visitFADD(SDNode *N); 172 SDValue visitFSUB(SDNode *N); 173 SDValue visitFMUL(SDNode *N); 174 SDValue visitFDIV(SDNode *N); 175 SDValue visitFREM(SDNode *N); 176 SDValue visitFCOPYSIGN(SDNode *N); 177 SDValue visitSINT_TO_FP(SDNode *N); 178 SDValue visitUINT_TO_FP(SDNode *N); 179 SDValue visitFP_TO_SINT(SDNode *N); 180 SDValue visitFP_TO_UINT(SDNode *N); 181 SDValue visitFP_ROUND(SDNode *N); 182 SDValue visitFP_ROUND_INREG(SDNode *N); 183 SDValue visitFP_EXTEND(SDNode *N); 184 SDValue visitFNEG(SDNode *N); 185 SDValue visitFABS(SDNode *N); 186 SDValue visitBRCOND(SDNode *N); 187 SDValue visitBR_CC(SDNode *N); 188 SDValue visitLOAD(SDNode *N); 189 SDValue visitSTORE(SDNode *N); 190 SDValue visitINSERT_VECTOR_ELT(SDNode *N); 191 SDValue visitEXTRACT_VECTOR_ELT(SDNode *N); 192 SDValue visitBUILD_VECTOR(SDNode *N); 193 SDValue visitCONCAT_VECTORS(SDNode *N); 194 SDValue visitVECTOR_SHUFFLE(SDNode *N); 195 196 SDValue XformToShuffleWithZero(SDNode *N); 197 SDValue ReassociateOps(unsigned Opc, SDValue LHS, SDValue RHS); 198 199 SDValue visitShiftByConstant(SDNode *N, unsigned Amt); 200 201 bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS); 202 SDValue SimplifyBinOpWithSameOpcodeHands(SDNode *N); 203 SDValue SimplifySelect(SDValue N0, SDValue N1, SDValue N2); 204 SDValue SimplifySelectCC(SDValue N0, SDValue N1, SDValue N2, 205 SDValue N3, ISD::CondCode CC, 206 bool NotExtCompare = false); 207 SDValue SimplifySetCC(MVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond, 208 bool foldBooleans = true); 209 SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp, 210 unsigned HiOp); 211 SDValue CombineConsecutiveLoads(SDNode *N, MVT VT); 212 SDValue ConstantFoldBIT_CONVERTofBUILD_VECTOR(SDNode *, MVT); 213 SDValue BuildSDIV(SDNode *N); 214 SDValue BuildUDIV(SDNode *N); 215 SDNode *MatchRotate(SDValue LHS, SDValue RHS); 216 SDValue ReduceLoadWidth(SDNode *N); 217 218 SDValue GetDemandedBits(SDValue V, const APInt &Mask); 219 220 /// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes, 221 /// looking for aliasing nodes and adding them to the Aliases vector. 222 void GatherAllAliases(SDNode *N, SDValue OriginalChain, 223 SmallVector<SDValue, 8> &Aliases); 224 225 /// isAlias - Return true if there is any possibility that the two addresses 226 /// overlap. 227 bool isAlias(SDValue Ptr1, int64_t Size1, 228 const Value *SrcValue1, int SrcValueOffset1, 229 SDValue Ptr2, int64_t Size2, 230 const Value *SrcValue2, int SrcValueOffset2); 231 232 /// FindAliasInfo - Extracts the relevant alias information from the memory 233 /// node. Returns true if the operand was a load. 234 bool FindAliasInfo(SDNode *N, 235 SDValue &Ptr, int64_t &Size, 236 const Value *&SrcValue, int &SrcValueOffset); 237 238 /// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, 239 /// looking for a better chain (aliasing node.) 240 SDValue FindBetterChain(SDNode *N, SDValue Chain); 241 242public: 243 DAGCombiner(SelectionDAG &D, AliasAnalysis &A, bool fast) 244 : DAG(D), 245 TLI(D.getTargetLoweringInfo()), 246 Level(Unrestricted), 247 LegalOperations(false), 248 LegalTypes(false), 249 Fast(fast), 250 AA(A) {} 251 252 /// Run - runs the dag combiner on all nodes in the work list 253 void Run(CombineLevel AtLevel); 254 }; 255} 256 257 258namespace { 259/// WorkListRemover - This class is a DAGUpdateListener that removes any deleted 260/// nodes from the worklist. 261class VISIBILITY_HIDDEN WorkListRemover : 262 public SelectionDAG::DAGUpdateListener { 263 DAGCombiner &DC; 264public: 265 explicit WorkListRemover(DAGCombiner &dc) : DC(dc) {} 266 267 virtual void NodeDeleted(SDNode *N, SDNode *E) { 268 DC.removeFromWorkList(N); 269 } 270 271 virtual void NodeUpdated(SDNode *N) { 272 // Ignore updates. 273 } 274}; 275} 276 277//===----------------------------------------------------------------------===// 278// TargetLowering::DAGCombinerInfo implementation 279//===----------------------------------------------------------------------===// 280 281void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) { 282 ((DAGCombiner*)DC)->AddToWorkList(N); 283} 284 285SDValue TargetLowering::DAGCombinerInfo:: 286CombineTo(SDNode *N, const std::vector<SDValue> &To) { 287 return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size()); 288} 289 290SDValue TargetLowering::DAGCombinerInfo:: 291CombineTo(SDNode *N, SDValue Res) { 292 return ((DAGCombiner*)DC)->CombineTo(N, Res); 293} 294 295 296SDValue TargetLowering::DAGCombinerInfo:: 297CombineTo(SDNode *N, SDValue Res0, SDValue Res1) { 298 return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1); 299} 300 301 302//===----------------------------------------------------------------------===// 303// Helper Functions 304//===----------------------------------------------------------------------===// 305 306/// isNegatibleForFree - Return 1 if we can compute the negated form of the 307/// specified expression for the same cost as the expression itself, or 2 if we 308/// can compute the negated form more cheaply than the expression itself. 309static char isNegatibleForFree(SDValue Op, bool LegalOperations, 310 unsigned Depth = 0) { 311 // No compile time optimizations on this type. 312 if (Op.getValueType() == MVT::ppcf128) 313 return 0; 314 315 // fneg is removable even if it has multiple uses. 316 if (Op.getOpcode() == ISD::FNEG) return 2; 317 318 // Don't allow anything with multiple uses. 319 if (!Op.hasOneUse()) return 0; 320 321 // Don't recurse exponentially. 322 if (Depth > 6) return 0; 323 324 switch (Op.getOpcode()) { 325 default: return false; 326 case ISD::ConstantFP: 327 // Don't invert constant FP values after legalize. The negated constant 328 // isn't necessarily legal. 329 return LegalOperations ? 0 : 1; 330 case ISD::FADD: 331 // FIXME: determine better conditions for this xform. 332 if (!UnsafeFPMath) return 0; 333 334 // -(A+B) -> -A - B 335 if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, Depth+1)) 336 return V; 337 // -(A+B) -> -B - A 338 return isNegatibleForFree(Op.getOperand(1), LegalOperations, Depth+1); 339 case ISD::FSUB: 340 // We can't turn -(A-B) into B-A when we honor signed zeros. 341 if (!UnsafeFPMath) return 0; 342 343 // -(A-B) -> B-A 344 return 1; 345 346 case ISD::FMUL: 347 case ISD::FDIV: 348 if (HonorSignDependentRoundingFPMath()) return 0; 349 350 // -(X*Y) -> (-X * Y) or (X*-Y) 351 if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, Depth+1)) 352 return V; 353 354 return isNegatibleForFree(Op.getOperand(1), LegalOperations, Depth+1); 355 356 case ISD::FP_EXTEND: 357 case ISD::FP_ROUND: 358 case ISD::FSIN: 359 return isNegatibleForFree(Op.getOperand(0), LegalOperations, Depth+1); 360 } 361} 362 363/// GetNegatedExpression - If isNegatibleForFree returns true, this function 364/// returns the newly negated expression. 365static SDValue GetNegatedExpression(SDValue Op, SelectionDAG &DAG, 366 bool LegalOperations, unsigned Depth = 0) { 367 // fneg is removable even if it has multiple uses. 368 if (Op.getOpcode() == ISD::FNEG) return Op.getOperand(0); 369 370 // Don't allow anything with multiple uses. 371 assert(Op.hasOneUse() && "Unknown reuse!"); 372 373 assert(Depth <= 6 && "GetNegatedExpression doesn't match isNegatibleForFree"); 374 switch (Op.getOpcode()) { 375 default: assert(0 && "Unknown code"); 376 case ISD::ConstantFP: { 377 APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF(); 378 V.changeSign(); 379 return DAG.getConstantFP(V, Op.getValueType()); 380 } 381 case ISD::FADD: 382 // FIXME: determine better conditions for this xform. 383 assert(UnsafeFPMath); 384 385 // -(A+B) -> -A - B 386 if (isNegatibleForFree(Op.getOperand(0), LegalOperations, Depth+1)) 387 return DAG.getNode(ISD::FSUB, Op.getValueType(), 388 GetNegatedExpression(Op.getOperand(0), DAG, 389 LegalOperations, Depth+1), 390 Op.getOperand(1)); 391 // -(A+B) -> -B - A 392 return DAG.getNode(ISD::FSUB, Op.getValueType(), 393 GetNegatedExpression(Op.getOperand(1), DAG, 394 LegalOperations, Depth+1), 395 Op.getOperand(0)); 396 case ISD::FSUB: 397 // We can't turn -(A-B) into B-A when we honor signed zeros. 398 assert(UnsafeFPMath); 399 400 // -(0-B) -> B 401 if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(Op.getOperand(0))) 402 if (N0CFP->getValueAPF().isZero()) 403 return Op.getOperand(1); 404 405 // -(A-B) -> B-A 406 return DAG.getNode(ISD::FSUB, Op.getValueType(), Op.getOperand(1), 407 Op.getOperand(0)); 408 409 case ISD::FMUL: 410 case ISD::FDIV: 411 assert(!HonorSignDependentRoundingFPMath()); 412 413 // -(X*Y) -> -X * Y 414 if (isNegatibleForFree(Op.getOperand(0), LegalOperations, Depth+1)) 415 return DAG.getNode(Op.getOpcode(), Op.getValueType(), 416 GetNegatedExpression(Op.getOperand(0), DAG, 417 LegalOperations, Depth+1), 418 Op.getOperand(1)); 419 420 // -(X*Y) -> X * -Y 421 return DAG.getNode(Op.getOpcode(), Op.getValueType(), 422 Op.getOperand(0), 423 GetNegatedExpression(Op.getOperand(1), DAG, 424 LegalOperations, Depth+1)); 425 426 case ISD::FP_EXTEND: 427 case ISD::FSIN: 428 return DAG.getNode(Op.getOpcode(), Op.getValueType(), 429 GetNegatedExpression(Op.getOperand(0), DAG, 430 LegalOperations, Depth+1)); 431 case ISD::FP_ROUND: 432 return DAG.getNode(ISD::FP_ROUND, Op.getValueType(), 433 GetNegatedExpression(Op.getOperand(0), DAG, 434 LegalOperations, Depth+1), 435 Op.getOperand(1)); 436 } 437} 438 439 440// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 441// that selects between the values 1 and 0, making it equivalent to a setcc. 442// Also, set the incoming LHS, RHS, and CC references to the appropriate 443// nodes based on the type of node we are checking. This simplifies life a 444// bit for the callers. 445static bool isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS, 446 SDValue &CC) { 447 if (N.getOpcode() == ISD::SETCC) { 448 LHS = N.getOperand(0); 449 RHS = N.getOperand(1); 450 CC = N.getOperand(2); 451 return true; 452 } 453 if (N.getOpcode() == ISD::SELECT_CC && 454 N.getOperand(2).getOpcode() == ISD::Constant && 455 N.getOperand(3).getOpcode() == ISD::Constant && 456 cast<ConstantSDNode>(N.getOperand(2))->getAPIntValue() == 1 && 457 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 458 LHS = N.getOperand(0); 459 RHS = N.getOperand(1); 460 CC = N.getOperand(4); 461 return true; 462 } 463 return false; 464} 465 466// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 467// one use. If this is true, it allows the users to invert the operation for 468// free when it is profitable to do so. 469static bool isOneUseSetCC(SDValue N) { 470 SDValue N0, N1, N2; 471 if (isSetCCEquivalent(N, N0, N1, N2) && N.getNode()->hasOneUse()) 472 return true; 473 return false; 474} 475 476SDValue DAGCombiner::ReassociateOps(unsigned Opc, SDValue N0, SDValue N1){ 477 MVT VT = N0.getValueType(); 478 // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use 479 // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2)) 480 if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) { 481 if (isa<ConstantSDNode>(N1)) { 482 SDValue OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1); 483 AddToWorkList(OpNode.getNode()); 484 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0)); 485 } else if (N0.hasOneUse()) { 486 SDValue OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1); 487 AddToWorkList(OpNode.getNode()); 488 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1)); 489 } 490 } 491 // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use 492 // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2)) 493 if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) { 494 if (isa<ConstantSDNode>(N0)) { 495 SDValue OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0); 496 AddToWorkList(OpNode.getNode()); 497 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0)); 498 } else if (N1.hasOneUse()) { 499 SDValue OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0); 500 AddToWorkList(OpNode.getNode()); 501 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1)); 502 } 503 } 504 return SDValue(); 505} 506 507SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo, 508 bool AddTo) { 509 assert(N->getNumValues() == NumTo && "Broken CombineTo call!"); 510 ++NodesCombined; 511 DOUT << "\nReplacing.1 "; DEBUG(N->dump(&DAG)); 512 DOUT << "\nWith: "; DEBUG(To[0].getNode()->dump(&DAG)); 513 DOUT << " and " << NumTo-1 << " other values\n"; 514 WorkListRemover DeadNodes(*this); 515 DAG.ReplaceAllUsesWith(N, To, &DeadNodes); 516 517 if (AddTo) { 518 // Push the new nodes and any users onto the worklist 519 for (unsigned i = 0, e = NumTo; i != e; ++i) { 520 AddToWorkList(To[i].getNode()); 521 AddUsersToWorkList(To[i].getNode()); 522 } 523 } 524 525 // Nodes can be reintroduced into the worklist. Make sure we do not 526 // process a node that has been replaced. 527 removeFromWorkList(N); 528 529 // Finally, since the node is now dead, remove it from the graph. 530 DAG.DeleteNode(N); 531 return SDValue(N, 0); 532} 533 534/// SimplifyDemandedBits - Check the specified integer node value to see if 535/// it can be simplified or if things it uses can be simplified by bit 536/// propagation. If so, return true. 537bool DAGCombiner::SimplifyDemandedBits(SDValue Op, const APInt &Demanded) { 538 TargetLowering::TargetLoweringOpt TLO(DAG); 539 APInt KnownZero, KnownOne; 540 if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO)) 541 return false; 542 543 // Revisit the node. 544 AddToWorkList(Op.getNode()); 545 546 // Replace the old value with the new one. 547 ++NodesCombined; 548 DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.getNode()->dump(&DAG)); 549 DOUT << "\nWith: "; DEBUG(TLO.New.getNode()->dump(&DAG)); 550 DOUT << '\n'; 551 552 // Replace all uses. If any nodes become isomorphic to other nodes and 553 // are deleted, make sure to remove them from our worklist. 554 WorkListRemover DeadNodes(*this); 555 DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &DeadNodes); 556 557 // Push the new node and any (possibly new) users onto the worklist. 558 AddToWorkList(TLO.New.getNode()); 559 AddUsersToWorkList(TLO.New.getNode()); 560 561 // Finally, if the node is now dead, remove it from the graph. The node 562 // may not be dead if the replacement process recursively simplified to 563 // something else needing this node. 564 if (TLO.Old.getNode()->use_empty()) { 565 removeFromWorkList(TLO.Old.getNode()); 566 567 // If the operands of this node are only used by the node, they will now 568 // be dead. Make sure to visit them first to delete dead nodes early. 569 for (unsigned i = 0, e = TLO.Old.getNode()->getNumOperands(); i != e; ++i) 570 if (TLO.Old.getNode()->getOperand(i).getNode()->hasOneUse()) 571 AddToWorkList(TLO.Old.getNode()->getOperand(i).getNode()); 572 573 DAG.DeleteNode(TLO.Old.getNode()); 574 } 575 return true; 576} 577 578//===----------------------------------------------------------------------===// 579// Main DAG Combiner implementation 580//===----------------------------------------------------------------------===// 581 582void DAGCombiner::Run(CombineLevel AtLevel) { 583 // set the instance variables, so that the various visit routines may use it. 584 Level = AtLevel; 585 LegalOperations = Level >= NoIllegalOperations; 586 LegalTypes = Level >= NoIllegalTypes; 587 588 // Add all the dag nodes to the worklist. 589 WorkList.reserve(DAG.allnodes_size()); 590 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 591 E = DAG.allnodes_end(); I != E; ++I) 592 WorkList.push_back(I); 593 594 // Create a dummy node (which is not added to allnodes), that adds a reference 595 // to the root node, preventing it from being deleted, and tracking any 596 // changes of the root. 597 HandleSDNode Dummy(DAG.getRoot()); 598 599 // The root of the dag may dangle to deleted nodes until the dag combiner is 600 // done. Set it to null to avoid confusion. 601 DAG.setRoot(SDValue()); 602 603 // while the worklist isn't empty, inspect the node on the end of it and 604 // try and combine it. 605 while (!WorkList.empty()) { 606 SDNode *N = WorkList.back(); 607 WorkList.pop_back(); 608 609 // If N has no uses, it is dead. Make sure to revisit all N's operands once 610 // N is deleted from the DAG, since they too may now be dead or may have a 611 // reduced number of uses, allowing other xforms. 612 if (N->use_empty() && N != &Dummy) { 613 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 614 AddToWorkList(N->getOperand(i).getNode()); 615 616 DAG.DeleteNode(N); 617 continue; 618 } 619 620 SDValue RV = combine(N); 621 622 if (RV.getNode() == 0) 623 continue; 624 625 ++NodesCombined; 626 627 // If we get back the same node we passed in, rather than a new node or 628 // zero, we know that the node must have defined multiple values and 629 // CombineTo was used. Since CombineTo takes care of the worklist 630 // mechanics for us, we have no work to do in this case. 631 if (RV.getNode() == N) 632 continue; 633 634 assert(N->getOpcode() != ISD::DELETED_NODE && 635 RV.getNode()->getOpcode() != ISD::DELETED_NODE && 636 "Node was deleted but visit returned new node!"); 637 638 DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG)); 639 DOUT << "\nWith: "; DEBUG(RV.getNode()->dump(&DAG)); 640 DOUT << '\n'; 641 WorkListRemover DeadNodes(*this); 642 if (N->getNumValues() == RV.getNode()->getNumValues()) 643 DAG.ReplaceAllUsesWith(N, RV.getNode(), &DeadNodes); 644 else { 645 assert(N->getValueType(0) == RV.getValueType() && 646 N->getNumValues() == 1 && "Type mismatch"); 647 SDValue OpV = RV; 648 DAG.ReplaceAllUsesWith(N, &OpV, &DeadNodes); 649 } 650 651 // Push the new node and any users onto the worklist 652 AddToWorkList(RV.getNode()); 653 AddUsersToWorkList(RV.getNode()); 654 655 // Add any uses of the old node to the worklist in case this node is the 656 // last one that uses them. They may become dead after this node is 657 // deleted. 658 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 659 AddToWorkList(N->getOperand(i).getNode()); 660 661 // Nodes can be reintroduced into the worklist. Make sure we do not 662 // process a node that has been replaced. 663 removeFromWorkList(N); 664 665 // Finally, since the node is now dead, remove it from the graph. 666 DAG.DeleteNode(N); 667 } 668 669 // If the root changed (e.g. it was a dead load, update the root). 670 DAG.setRoot(Dummy.getValue()); 671} 672 673SDValue DAGCombiner::visit(SDNode *N) { 674 switch(N->getOpcode()) { 675 default: break; 676 case ISD::TokenFactor: return visitTokenFactor(N); 677 case ISD::MERGE_VALUES: return visitMERGE_VALUES(N); 678 case ISD::ADD: return visitADD(N); 679 case ISD::SUB: return visitSUB(N); 680 case ISD::ADDC: return visitADDC(N); 681 case ISD::ADDE: return visitADDE(N); 682 case ISD::MUL: return visitMUL(N); 683 case ISD::SDIV: return visitSDIV(N); 684 case ISD::UDIV: return visitUDIV(N); 685 case ISD::SREM: return visitSREM(N); 686 case ISD::UREM: return visitUREM(N); 687 case ISD::MULHU: return visitMULHU(N); 688 case ISD::MULHS: return visitMULHS(N); 689 case ISD::SMUL_LOHI: return visitSMUL_LOHI(N); 690 case ISD::UMUL_LOHI: return visitUMUL_LOHI(N); 691 case ISD::SDIVREM: return visitSDIVREM(N); 692 case ISD::UDIVREM: return visitUDIVREM(N); 693 case ISD::AND: return visitAND(N); 694 case ISD::OR: return visitOR(N); 695 case ISD::XOR: return visitXOR(N); 696 case ISD::SHL: return visitSHL(N); 697 case ISD::SRA: return visitSRA(N); 698 case ISD::SRL: return visitSRL(N); 699 case ISD::CTLZ: return visitCTLZ(N); 700 case ISD::CTTZ: return visitCTTZ(N); 701 case ISD::CTPOP: return visitCTPOP(N); 702 case ISD::SELECT: return visitSELECT(N); 703 case ISD::SELECT_CC: return visitSELECT_CC(N); 704 case ISD::SETCC: return visitSETCC(N); 705 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 706 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 707 case ISD::ANY_EXTEND: return visitANY_EXTEND(N); 708 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 709 case ISD::TRUNCATE: return visitTRUNCATE(N); 710 case ISD::BIT_CONVERT: return visitBIT_CONVERT(N); 711 case ISD::BUILD_PAIR: return visitBUILD_PAIR(N); 712 case ISD::FADD: return visitFADD(N); 713 case ISD::FSUB: return visitFSUB(N); 714 case ISD::FMUL: return visitFMUL(N); 715 case ISD::FDIV: return visitFDIV(N); 716 case ISD::FREM: return visitFREM(N); 717 case ISD::FCOPYSIGN: return visitFCOPYSIGN(N); 718 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 719 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 720 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 721 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 722 case ISD::FP_ROUND: return visitFP_ROUND(N); 723 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 724 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 725 case ISD::FNEG: return visitFNEG(N); 726 case ISD::FABS: return visitFABS(N); 727 case ISD::BRCOND: return visitBRCOND(N); 728 case ISD::BR_CC: return visitBR_CC(N); 729 case ISD::LOAD: return visitLOAD(N); 730 case ISD::STORE: return visitSTORE(N); 731 case ISD::INSERT_VECTOR_ELT: return visitINSERT_VECTOR_ELT(N); 732 case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N); 733 case ISD::BUILD_VECTOR: return visitBUILD_VECTOR(N); 734 case ISD::CONCAT_VECTORS: return visitCONCAT_VECTORS(N); 735 case ISD::VECTOR_SHUFFLE: return visitVECTOR_SHUFFLE(N); 736 } 737 return SDValue(); 738} 739 740SDValue DAGCombiner::combine(SDNode *N) { 741 742 SDValue RV = visit(N); 743 744 // If nothing happened, try a target-specific DAG combine. 745 if (RV.getNode() == 0) { 746 assert(N->getOpcode() != ISD::DELETED_NODE && 747 "Node was deleted but visit returned NULL!"); 748 749 if (N->getOpcode() >= ISD::BUILTIN_OP_END || 750 TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) { 751 752 // Expose the DAG combiner to the target combiner impls. 753 TargetLowering::DAGCombinerInfo 754 DagCombineInfo(DAG, Level == Unrestricted, false, this); 755 756 RV = TLI.PerformDAGCombine(N, DagCombineInfo); 757 } 758 } 759 760 // If N is a commutative binary node, try commuting it to enable more 761 // sdisel CSE. 762 if (RV.getNode() == 0 && 763 SelectionDAG::isCommutativeBinOp(N->getOpcode()) && 764 N->getNumValues() == 1) { 765 SDValue N0 = N->getOperand(0); 766 SDValue N1 = N->getOperand(1); 767 // Constant operands are canonicalized to RHS. 768 if (isa<ConstantSDNode>(N0) || !isa<ConstantSDNode>(N1)) { 769 SDValue Ops[] = { N1, N0 }; 770 SDNode *CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), 771 Ops, 2); 772 if (CSENode) 773 return SDValue(CSENode, 0); 774 } 775 } 776 777 return RV; 778} 779 780/// getInputChainForNode - Given a node, return its input chain if it has one, 781/// otherwise return a null sd operand. 782static SDValue getInputChainForNode(SDNode *N) { 783 if (unsigned NumOps = N->getNumOperands()) { 784 if (N->getOperand(0).getValueType() == MVT::Other) 785 return N->getOperand(0); 786 else if (N->getOperand(NumOps-1).getValueType() == MVT::Other) 787 return N->getOperand(NumOps-1); 788 for (unsigned i = 1; i < NumOps-1; ++i) 789 if (N->getOperand(i).getValueType() == MVT::Other) 790 return N->getOperand(i); 791 } 792 return SDValue(0, 0); 793} 794 795SDValue DAGCombiner::visitTokenFactor(SDNode *N) { 796 // If N has two operands, where one has an input chain equal to the other, 797 // the 'other' chain is redundant. 798 if (N->getNumOperands() == 2) { 799 if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1)) 800 return N->getOperand(0); 801 if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0)) 802 return N->getOperand(1); 803 } 804 805 SmallVector<SDNode *, 8> TFs; // List of token factors to visit. 806 SmallVector<SDValue, 8> Ops; // Ops for replacing token factor. 807 SmallPtrSet<SDNode*, 16> SeenOps; 808 bool Changed = false; // If we should replace this token factor. 809 810 // Start out with this token factor. 811 TFs.push_back(N); 812 813 // Iterate through token factors. The TFs grows when new token factors are 814 // encountered. 815 for (unsigned i = 0; i < TFs.size(); ++i) { 816 SDNode *TF = TFs[i]; 817 818 // Check each of the operands. 819 for (unsigned i = 0, ie = TF->getNumOperands(); i != ie; ++i) { 820 SDValue Op = TF->getOperand(i); 821 822 switch (Op.getOpcode()) { 823 case ISD::EntryToken: 824 // Entry tokens don't need to be added to the list. They are 825 // rededundant. 826 Changed = true; 827 break; 828 829 case ISD::TokenFactor: 830 if ((CombinerAA || Op.hasOneUse()) && 831 std::find(TFs.begin(), TFs.end(), Op.getNode()) == TFs.end()) { 832 // Queue up for processing. 833 TFs.push_back(Op.getNode()); 834 // Clean up in case the token factor is removed. 835 AddToWorkList(Op.getNode()); 836 Changed = true; 837 break; 838 } 839 // Fall thru 840 841 default: 842 // Only add if it isn't already in the list. 843 if (SeenOps.insert(Op.getNode())) 844 Ops.push_back(Op); 845 else 846 Changed = true; 847 break; 848 } 849 } 850 } 851 852 SDValue Result; 853 854 // If we've change things around then replace token factor. 855 if (Changed) { 856 if (Ops.empty()) { 857 // The entry token is the only possible outcome. 858 Result = DAG.getEntryNode(); 859 } else { 860 // New and improved token factor. 861 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size()); 862 } 863 864 // Don't add users to work list. 865 return CombineTo(N, Result, false); 866 } 867 868 return Result; 869} 870 871/// MERGE_VALUES can always be eliminated. 872SDValue DAGCombiner::visitMERGE_VALUES(SDNode *N) { 873 WorkListRemover DeadNodes(*this); 874 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 875 DAG.ReplaceAllUsesOfValueWith(SDValue(N, i), N->getOperand(i), 876 &DeadNodes); 877 removeFromWorkList(N); 878 DAG.DeleteNode(N); 879 return SDValue(N, 0); // Return N so it doesn't get rechecked! 880} 881 882 883static 884SDValue combineShlAddConstant(SDValue N0, SDValue N1, SelectionDAG &DAG) { 885 MVT VT = N0.getValueType(); 886 SDValue N00 = N0.getOperand(0); 887 SDValue N01 = N0.getOperand(1); 888 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N01); 889 if (N01C && N00.getOpcode() == ISD::ADD && N00.getNode()->hasOneUse() && 890 isa<ConstantSDNode>(N00.getOperand(1))) { 891 N0 = DAG.getNode(ISD::ADD, VT, 892 DAG.getNode(ISD::SHL, VT, N00.getOperand(0), N01), 893 DAG.getNode(ISD::SHL, VT, N00.getOperand(1), N01)); 894 return DAG.getNode(ISD::ADD, VT, N0, N1); 895 } 896 return SDValue(); 897} 898 899static 900SDValue combineSelectAndUse(SDNode *N, SDValue Slct, SDValue OtherOp, 901 SelectionDAG &DAG, const TargetLowering &TLI, 902 bool LegalOperations) { 903 MVT VT = N->getValueType(0); 904 unsigned Opc = N->getOpcode(); 905 bool isSlctCC = Slct.getOpcode() == ISD::SELECT_CC; 906 SDValue LHS = isSlctCC ? Slct.getOperand(2) : Slct.getOperand(1); 907 SDValue RHS = isSlctCC ? Slct.getOperand(3) : Slct.getOperand(2); 908 ISD::CondCode CC = ISD::SETCC_INVALID; 909 910 if (isSlctCC) { 911 CC = cast<CondCodeSDNode>(Slct.getOperand(4))->get(); 912 } else { 913 SDValue CCOp = Slct.getOperand(0); 914 if (CCOp.getOpcode() == ISD::SETCC) 915 CC = cast<CondCodeSDNode>(CCOp.getOperand(2))->get(); 916 } 917 918 bool DoXform = false; 919 bool InvCC = false; 920 assert ((Opc == ISD::ADD || (Opc == ISD::SUB && Slct == N->getOperand(1))) && 921 "Bad input!"); 922 923 if (LHS.getOpcode() == ISD::Constant && 924 cast<ConstantSDNode>(LHS)->isNullValue()) { 925 DoXform = true; 926 } else if (CC != ISD::SETCC_INVALID && 927 RHS.getOpcode() == ISD::Constant && 928 cast<ConstantSDNode>(RHS)->isNullValue()) { 929 std::swap(LHS, RHS); 930 SDValue Op0 = Slct.getOperand(0); 931 MVT OpVT = isSlctCC ? Op0.getValueType() : 932 Op0.getOperand(0).getValueType(); 933 bool isInt = OpVT.isInteger(); 934 CC = ISD::getSetCCInverse(CC, isInt); 935 936 if (LegalOperations && !TLI.isCondCodeLegal(CC, OpVT)) 937 return SDValue(); // Inverse operator isn't legal. 938 939 DoXform = true; 940 InvCC = true; 941 } 942 943 if (DoXform) { 944 SDValue Result = DAG.getNode(Opc, VT, OtherOp, RHS); 945 if (isSlctCC) 946 return DAG.getSelectCC(OtherOp, Result, 947 Slct.getOperand(0), Slct.getOperand(1), CC); 948 SDValue CCOp = Slct.getOperand(0); 949 if (InvCC) 950 CCOp = DAG.getSetCC(CCOp.getValueType(), CCOp.getOperand(0), 951 CCOp.getOperand(1), CC); 952 return DAG.getNode(ISD::SELECT, VT, CCOp, OtherOp, Result); 953 } 954 return SDValue(); 955} 956 957SDValue DAGCombiner::visitADD(SDNode *N) { 958 SDValue N0 = N->getOperand(0); 959 SDValue N1 = N->getOperand(1); 960 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 961 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 962 MVT VT = N0.getValueType(); 963 964 // fold vector ops 965 if (VT.isVector()) { 966 SDValue FoldedVOp = SimplifyVBinOp(N); 967 if (FoldedVOp.getNode()) return FoldedVOp; 968 } 969 970 // fold (add x, undef) -> undef 971 if (N0.getOpcode() == ISD::UNDEF) 972 return N0; 973 if (N1.getOpcode() == ISD::UNDEF) 974 return N1; 975 // fold (add c1, c2) -> c1+c2 976 if (N0C && N1C) 977 return DAG.FoldConstantArithmetic(ISD::ADD, VT, N0C, N1C); 978 // canonicalize constant to RHS 979 if (N0C && !N1C) 980 return DAG.getNode(ISD::ADD, VT, N1, N0); 981 // fold (add x, 0) -> x 982 if (N1C && N1C->isNullValue()) 983 return N0; 984 // fold (add Sym, c) -> Sym+c 985 if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0)) 986 if (!LegalOperations && TLI.isOffsetFoldingLegal(GA) && N1C && 987 GA->getOpcode() == ISD::GlobalAddress) 988 return DAG.getGlobalAddress(GA->getGlobal(), VT, 989 GA->getOffset() + 990 (uint64_t)N1C->getSExtValue()); 991 // fold ((c1-A)+c2) -> (c1+c2)-A 992 if (N1C && N0.getOpcode() == ISD::SUB) 993 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0))) 994 return DAG.getNode(ISD::SUB, VT, 995 DAG.getConstant(N1C->getAPIntValue()+ 996 N0C->getAPIntValue(), VT), 997 N0.getOperand(1)); 998 // reassociate add 999 SDValue RADD = ReassociateOps(ISD::ADD, N0, N1); 1000 if (RADD.getNode() != 0) 1001 return RADD; 1002 // fold ((0-A) + B) -> B-A 1003 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 1004 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 1005 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 1006 // fold (A + (0-B)) -> A-B 1007 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 1008 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 1009 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 1010 // fold (A+(B-A)) -> B 1011 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1)) 1012 return N1.getOperand(0); 1013 1014 if (!VT.isVector() && SimplifyDemandedBits(SDValue(N, 0))) 1015 return SDValue(N, 0); 1016 1017 // fold (a+b) -> (a|b) iff a and b share no bits. 1018 if (VT.isInteger() && !VT.isVector()) { 1019 APInt LHSZero, LHSOne; 1020 APInt RHSZero, RHSOne; 1021 APInt Mask = APInt::getAllOnesValue(VT.getSizeInBits()); 1022 DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); 1023 if (LHSZero.getBoolValue()) { 1024 DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); 1025 1026 // If all possibly-set bits on the LHS are clear on the RHS, return an OR. 1027 // If all possibly-set bits on the RHS are clear on the LHS, return an OR. 1028 if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) || 1029 (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask)) 1030 return DAG.getNode(ISD::OR, VT, N0, N1); 1031 } 1032 } 1033 1034 // fold (add (shl (add x, c1), c2), ) -> (add (add (shl x, c2), c1<<c2), ) 1035 if (N0.getOpcode() == ISD::SHL && N0.getNode()->hasOneUse()) { 1036 SDValue Result = combineShlAddConstant(N0, N1, DAG); 1037 if (Result.getNode()) return Result; 1038 } 1039 if (N1.getOpcode() == ISD::SHL && N1.getNode()->hasOneUse()) { 1040 SDValue Result = combineShlAddConstant(N1, N0, DAG); 1041 if (Result.getNode()) return Result; 1042 } 1043 1044 // fold (add (select cc, 0, c), x) -> (select cc, x, (add, x, c)) 1045 if (N0.getOpcode() == ISD::SELECT && N0.getNode()->hasOneUse()) { 1046 SDValue Result = combineSelectAndUse(N, N0, N1, DAG, TLI, LegalOperations); 1047 if (Result.getNode()) return Result; 1048 } 1049 if (N1.getOpcode() == ISD::SELECT && N1.getNode()->hasOneUse()) { 1050 SDValue Result = combineSelectAndUse(N, N1, N0, DAG, TLI, LegalOperations); 1051 if (Result.getNode()) return Result; 1052 } 1053 1054 return SDValue(); 1055} 1056 1057SDValue DAGCombiner::visitADDC(SDNode *N) { 1058 SDValue N0 = N->getOperand(0); 1059 SDValue N1 = N->getOperand(1); 1060 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1061 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1062 MVT VT = N0.getValueType(); 1063 1064 // If the flag result is dead, turn this into an ADD. 1065 if (N->hasNUsesOfValue(0, 1)) 1066 return CombineTo(N, DAG.getNode(ISD::ADD, VT, N1, N0), 1067 DAG.getNode(ISD::CARRY_FALSE, MVT::Flag)); 1068 1069 // canonicalize constant to RHS. 1070 if (N0C && !N1C) 1071 return DAG.getNode(ISD::ADDC, N->getVTList(), N1, N0); 1072 1073 // fold (addc x, 0) -> x + no carry out 1074 if (N1C && N1C->isNullValue()) 1075 return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE, MVT::Flag)); 1076 1077 // fold (addc a, b) -> (or a, b), CARRY_FALSE iff a and b share no bits. 1078 APInt LHSZero, LHSOne; 1079 APInt RHSZero, RHSOne; 1080 APInt Mask = APInt::getAllOnesValue(VT.getSizeInBits()); 1081 DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne); 1082 if (LHSZero.getBoolValue()) { 1083 DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne); 1084 1085 // If all possibly-set bits on the LHS are clear on the RHS, return an OR. 1086 // If all possibly-set bits on the RHS are clear on the LHS, return an OR. 1087 if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) || 1088 (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask)) 1089 return CombineTo(N, DAG.getNode(ISD::OR, VT, N0, N1), 1090 DAG.getNode(ISD::CARRY_FALSE, MVT::Flag)); 1091 } 1092 1093 return SDValue(); 1094} 1095 1096SDValue DAGCombiner::visitADDE(SDNode *N) { 1097 SDValue N0 = N->getOperand(0); 1098 SDValue N1 = N->getOperand(1); 1099 SDValue CarryIn = N->getOperand(2); 1100 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1101 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1102 //MVT VT = N0.getValueType(); 1103 1104 // canonicalize constant to RHS 1105 if (N0C && !N1C) 1106 return DAG.getNode(ISD::ADDE, N->getVTList(), N1, N0, CarryIn); 1107 1108 // fold (adde x, y, false) -> (addc x, y) 1109 if (CarryIn.getOpcode() == ISD::CARRY_FALSE) 1110 return DAG.getNode(ISD::ADDC, N->getVTList(), N1, N0); 1111 1112 return SDValue(); 1113} 1114 1115 1116 1117SDValue DAGCombiner::visitSUB(SDNode *N) { 1118 SDValue N0 = N->getOperand(0); 1119 SDValue N1 = N->getOperand(1); 1120 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getNode()); 1121 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 1122 MVT VT = N0.getValueType(); 1123 1124 // fold vector ops 1125 if (VT.isVector()) { 1126 SDValue FoldedVOp = SimplifyVBinOp(N); 1127 if (FoldedVOp.getNode()) return FoldedVOp; 1128 } 1129 1130 // fold (sub x, x) -> 0 1131 if (N0 == N1) 1132 return DAG.getConstant(0, N->getValueType(0)); 1133 // fold (sub c1, c2) -> c1-c2 1134 if (N0C && N1C) 1135 return DAG.FoldConstantArithmetic(ISD::SUB, VT, N0C, N1C); 1136 // fold (sub x, c) -> (add x, -c) 1137 if (N1C) 1138 return DAG.getNode(ISD::ADD, VT, N0, 1139 DAG.getConstant(-N1C->getAPIntValue(), VT)); 1140 // fold (A+B)-A -> B 1141 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1) 1142 return N0.getOperand(1); 1143 // fold (A+B)-B -> A 1144 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1) 1145 return N0.getOperand(0); 1146 // fold (sub x, (select cc, 0, c)) -> (select cc, x, (sub, x, c)) 1147 if (N1.getOpcode() == ISD::SELECT && N1.getNode()->hasOneUse()) { 1148 SDValue Result = combineSelectAndUse(N, N1, N0, DAG, TLI, LegalOperations); 1149 if (Result.getNode()) return Result; 1150 } 1151 // If either operand of a sub is undef, the result is undef 1152 if (N0.getOpcode() == ISD::UNDEF) 1153 return N0; 1154 if (N1.getOpcode() == ISD::UNDEF) 1155 return N1; 1156 1157 // If the relocation model supports it, consider symbol offsets. 1158 if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0)) 1159 if (!LegalOperations && TLI.isOffsetFoldingLegal(GA)) { 1160 // fold (sub Sym, c) -> Sym-c 1161 if (N1C && GA->getOpcode() == ISD::GlobalAddress) 1162 return DAG.getGlobalAddress(GA->getGlobal(), VT, 1163 GA->getOffset() - 1164 (uint64_t)N1C->getSExtValue()); 1165 // fold (sub Sym+c1, Sym+c2) -> c1-c2 1166 if (GlobalAddressSDNode *GB = dyn_cast<GlobalAddressSDNode>(N1)) 1167 if (GA->getGlobal() == GB->getGlobal()) 1168 return DAG.getConstant((uint64_t)GA->getOffset() - GB->getOffset(), 1169 VT); 1170 } 1171 1172 return SDValue(); 1173} 1174 1175SDValue DAGCombiner::visitMUL(SDNode *N) { 1176 SDValue N0 = N->getOperand(0); 1177 SDValue N1 = N->getOperand(1); 1178 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1179 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1180 MVT VT = N0.getValueType(); 1181 1182 // fold vector ops 1183 if (VT.isVector()) { 1184 SDValue FoldedVOp = SimplifyVBinOp(N); 1185 if (FoldedVOp.getNode()) return FoldedVOp; 1186 } 1187 1188 // fold (mul x, undef) -> 0 1189 if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) 1190 return DAG.getConstant(0, VT); 1191 // fold (mul c1, c2) -> c1*c2 1192 if (N0C && N1C) 1193 return DAG.FoldConstantArithmetic(ISD::MUL, VT, N0C, N1C); 1194 // canonicalize constant to RHS 1195 if (N0C && !N1C) 1196 return DAG.getNode(ISD::MUL, VT, N1, N0); 1197 // fold (mul x, 0) -> 0 1198 if (N1C && N1C->isNullValue()) 1199 return N1; 1200 // fold (mul x, -1) -> 0-x 1201 if (N1C && N1C->isAllOnesValue()) 1202 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 1203 // fold (mul x, (1 << c)) -> x << c 1204 if (N1C && N1C->getAPIntValue().isPowerOf2()) 1205 return DAG.getNode(ISD::SHL, VT, N0, 1206 DAG.getConstant(N1C->getAPIntValue().logBase2(), 1207 TLI.getShiftAmountTy())); 1208 // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c 1209 if (N1C && isPowerOf2_64(-N1C->getSExtValue())) { 1210 // FIXME: If the input is something that is easily negated (e.g. a 1211 // single-use add), we should put the negate there. 1212 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), 1213 DAG.getNode(ISD::SHL, VT, N0, 1214 DAG.getConstant(Log2_64(-N1C->getSExtValue()), 1215 TLI.getShiftAmountTy()))); 1216 } 1217 1218 // (mul (shl X, c1), c2) -> (mul X, c2 << c1) 1219 if (N1C && N0.getOpcode() == ISD::SHL && 1220 isa<ConstantSDNode>(N0.getOperand(1))) { 1221 SDValue C3 = DAG.getNode(ISD::SHL, VT, N1, N0.getOperand(1)); 1222 AddToWorkList(C3.getNode()); 1223 return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), C3); 1224 } 1225 1226 // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one 1227 // use. 1228 { 1229 SDValue Sh(0,0), Y(0,0); 1230 // Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)). 1231 if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) && 1232 N0.getNode()->hasOneUse()) { 1233 Sh = N0; Y = N1; 1234 } else if (N1.getOpcode() == ISD::SHL && 1235 isa<ConstantSDNode>(N1.getOperand(1)) && 1236 N1.getNode()->hasOneUse()) { 1237 Sh = N1; Y = N0; 1238 } 1239 if (Sh.getNode()) { 1240 SDValue Mul = DAG.getNode(ISD::MUL, VT, Sh.getOperand(0), Y); 1241 return DAG.getNode(ISD::SHL, VT, Mul, Sh.getOperand(1)); 1242 } 1243 } 1244 // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2) 1245 if (N1C && N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() && 1246 isa<ConstantSDNode>(N0.getOperand(1))) { 1247 return DAG.getNode(ISD::ADD, VT, 1248 DAG.getNode(ISD::MUL, VT, N0.getOperand(0), N1), 1249 DAG.getNode(ISD::MUL, VT, N0.getOperand(1), N1)); 1250 } 1251 1252 // reassociate mul 1253 SDValue RMUL = ReassociateOps(ISD::MUL, N0, N1); 1254 if (RMUL.getNode() != 0) 1255 return RMUL; 1256 1257 return SDValue(); 1258} 1259 1260SDValue DAGCombiner::visitSDIV(SDNode *N) { 1261 SDValue N0 = N->getOperand(0); 1262 SDValue N1 = N->getOperand(1); 1263 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getNode()); 1264 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 1265 MVT VT = N->getValueType(0); 1266 1267 // fold vector ops 1268 if (VT.isVector()) { 1269 SDValue FoldedVOp = SimplifyVBinOp(N); 1270 if (FoldedVOp.getNode()) return FoldedVOp; 1271 } 1272 1273 // fold (sdiv c1, c2) -> c1/c2 1274 if (N0C && N1C && !N1C->isNullValue()) 1275 return DAG.FoldConstantArithmetic(ISD::SDIV, VT, N0C, N1C); 1276 // fold (sdiv X, 1) -> X 1277 if (N1C && N1C->getSExtValue() == 1LL) 1278 return N0; 1279 // fold (sdiv X, -1) -> 0-X 1280 if (N1C && N1C->isAllOnesValue()) 1281 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 1282 // If we know the sign bits of both operands are zero, strength reduce to a 1283 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 1284 if (!VT.isVector()) { 1285 if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0)) 1286 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 1287 } 1288 // fold (sdiv X, pow2) -> simple ops after legalize 1289 if (N1C && !N1C->isNullValue() && !TLI.isIntDivCheap() && 1290 (isPowerOf2_64(N1C->getSExtValue()) || 1291 isPowerOf2_64(-N1C->getSExtValue()))) { 1292 // If dividing by powers of two is cheap, then don't perform the following 1293 // fold. 1294 if (TLI.isPow2DivCheap()) 1295 return SDValue(); 1296 int64_t pow2 = N1C->getSExtValue(); 1297 int64_t abs2 = pow2 > 0 ? pow2 : -pow2; 1298 unsigned lg2 = Log2_64(abs2); 1299 // Splat the sign bit into the register 1300 SDValue SGN = DAG.getNode(ISD::SRA, VT, N0, 1301 DAG.getConstant(VT.getSizeInBits()-1, 1302 TLI.getShiftAmountTy())); 1303 AddToWorkList(SGN.getNode()); 1304 // Add (N0 < 0) ? abs2 - 1 : 0; 1305 SDValue SRL = DAG.getNode(ISD::SRL, VT, SGN, 1306 DAG.getConstant(VT.getSizeInBits()-lg2, 1307 TLI.getShiftAmountTy())); 1308 SDValue ADD = DAG.getNode(ISD::ADD, VT, N0, SRL); 1309 AddToWorkList(SRL.getNode()); 1310 AddToWorkList(ADD.getNode()); // Divide by pow2 1311 SDValue SRA = DAG.getNode(ISD::SRA, VT, ADD, 1312 DAG.getConstant(lg2, TLI.getShiftAmountTy())); 1313 // If we're dividing by a positive value, we're done. Otherwise, we must 1314 // negate the result. 1315 if (pow2 > 0) 1316 return SRA; 1317 AddToWorkList(SRA.getNode()); 1318 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA); 1319 } 1320 // if integer divide is expensive and we satisfy the requirements, emit an 1321 // alternate sequence. 1322 if (N1C && (N1C->getSExtValue() < -1 || N1C->getSExtValue() > 1) && 1323 !TLI.isIntDivCheap()) { 1324 SDValue Op = BuildSDIV(N); 1325 if (Op.getNode()) return Op; 1326 } 1327 1328 // undef / X -> 0 1329 if (N0.getOpcode() == ISD::UNDEF) 1330 return DAG.getConstant(0, VT); 1331 // X / undef -> undef 1332 if (N1.getOpcode() == ISD::UNDEF) 1333 return N1; 1334 1335 return SDValue(); 1336} 1337 1338SDValue DAGCombiner::visitUDIV(SDNode *N) { 1339 SDValue N0 = N->getOperand(0); 1340 SDValue N1 = N->getOperand(1); 1341 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getNode()); 1342 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 1343 MVT VT = N->getValueType(0); 1344 1345 // fold vector ops 1346 if (VT.isVector()) { 1347 SDValue FoldedVOp = SimplifyVBinOp(N); 1348 if (FoldedVOp.getNode()) return FoldedVOp; 1349 } 1350 1351 // fold (udiv c1, c2) -> c1/c2 1352 if (N0C && N1C && !N1C->isNullValue()) 1353 return DAG.FoldConstantArithmetic(ISD::UDIV, VT, N0C, N1C); 1354 // fold (udiv x, (1 << c)) -> x >>u c 1355 if (N1C && N1C->getAPIntValue().isPowerOf2()) 1356 return DAG.getNode(ISD::SRL, VT, N0, 1357 DAG.getConstant(N1C->getAPIntValue().logBase2(), 1358 TLI.getShiftAmountTy())); 1359 // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2 1360 if (N1.getOpcode() == ISD::SHL) { 1361 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 1362 if (SHC->getAPIntValue().isPowerOf2()) { 1363 MVT ADDVT = N1.getOperand(1).getValueType(); 1364 SDValue Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1), 1365 DAG.getConstant(SHC->getAPIntValue() 1366 .logBase2(), 1367 ADDVT)); 1368 AddToWorkList(Add.getNode()); 1369 return DAG.getNode(ISD::SRL, VT, N0, Add); 1370 } 1371 } 1372 } 1373 // fold (udiv x, c) -> alternate 1374 if (N1C && !N1C->isNullValue() && !TLI.isIntDivCheap()) { 1375 SDValue Op = BuildUDIV(N); 1376 if (Op.getNode()) return Op; 1377 } 1378 1379 // undef / X -> 0 1380 if (N0.getOpcode() == ISD::UNDEF) 1381 return DAG.getConstant(0, VT); 1382 // X / undef -> undef 1383 if (N1.getOpcode() == ISD::UNDEF) 1384 return N1; 1385 1386 return SDValue(); 1387} 1388 1389SDValue DAGCombiner::visitSREM(SDNode *N) { 1390 SDValue N0 = N->getOperand(0); 1391 SDValue N1 = N->getOperand(1); 1392 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1393 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1394 MVT VT = N->getValueType(0); 1395 1396 // fold (srem c1, c2) -> c1%c2 1397 if (N0C && N1C && !N1C->isNullValue()) 1398 return DAG.FoldConstantArithmetic(ISD::SREM, VT, N0C, N1C); 1399 // If we know the sign bits of both operands are zero, strength reduce to a 1400 // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15 1401 if (!VT.isVector()) { 1402 if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0)) 1403 return DAG.getNode(ISD::UREM, VT, N0, N1); 1404 } 1405 1406 // If X/C can be simplified by the division-by-constant logic, lower 1407 // X%C to the equivalent of X-X/C*C. 1408 if (N1C && !N1C->isNullValue()) { 1409 SDValue Div = DAG.getNode(ISD::SDIV, VT, N0, N1); 1410 AddToWorkList(Div.getNode()); 1411 SDValue OptimizedDiv = combine(Div.getNode()); 1412 if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) { 1413 SDValue Mul = DAG.getNode(ISD::MUL, VT, OptimizedDiv, N1); 1414 SDValue Sub = DAG.getNode(ISD::SUB, VT, N0, Mul); 1415 AddToWorkList(Mul.getNode()); 1416 return Sub; 1417 } 1418 } 1419 1420 // undef % X -> 0 1421 if (N0.getOpcode() == ISD::UNDEF) 1422 return DAG.getConstant(0, VT); 1423 // X % undef -> undef 1424 if (N1.getOpcode() == ISD::UNDEF) 1425 return N1; 1426 1427 return SDValue(); 1428} 1429 1430SDValue DAGCombiner::visitUREM(SDNode *N) { 1431 SDValue N0 = N->getOperand(0); 1432 SDValue N1 = N->getOperand(1); 1433 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1434 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1435 MVT VT = N->getValueType(0); 1436 1437 // fold (urem c1, c2) -> c1%c2 1438 if (N0C && N1C && !N1C->isNullValue()) 1439 return DAG.FoldConstantArithmetic(ISD::UREM, VT, N0C, N1C); 1440 // fold (urem x, pow2) -> (and x, pow2-1) 1441 if (N1C && !N1C->isNullValue() && N1C->getAPIntValue().isPowerOf2()) 1442 return DAG.getNode(ISD::AND, VT, N0, 1443 DAG.getConstant(N1C->getAPIntValue()-1,VT)); 1444 // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1)) 1445 if (N1.getOpcode() == ISD::SHL) { 1446 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 1447 if (SHC->getAPIntValue().isPowerOf2()) { 1448 SDValue Add = 1449 DAG.getNode(ISD::ADD, VT, N1, 1450 DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), 1451 VT)); 1452 AddToWorkList(Add.getNode()); 1453 return DAG.getNode(ISD::AND, VT, N0, Add); 1454 } 1455 } 1456 } 1457 1458 // If X/C can be simplified by the division-by-constant logic, lower 1459 // X%C to the equivalent of X-X/C*C. 1460 if (N1C && !N1C->isNullValue()) { 1461 SDValue Div = DAG.getNode(ISD::UDIV, VT, N0, N1); 1462 AddToWorkList(Div.getNode()); 1463 SDValue OptimizedDiv = combine(Div.getNode()); 1464 if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) { 1465 SDValue Mul = DAG.getNode(ISD::MUL, VT, OptimizedDiv, N1); 1466 SDValue Sub = DAG.getNode(ISD::SUB, VT, N0, Mul); 1467 AddToWorkList(Mul.getNode()); 1468 return Sub; 1469 } 1470 } 1471 1472 // undef % X -> 0 1473 if (N0.getOpcode() == ISD::UNDEF) 1474 return DAG.getConstant(0, VT); 1475 // X % undef -> undef 1476 if (N1.getOpcode() == ISD::UNDEF) 1477 return N1; 1478 1479 return SDValue(); 1480} 1481 1482SDValue DAGCombiner::visitMULHS(SDNode *N) { 1483 SDValue N0 = N->getOperand(0); 1484 SDValue N1 = N->getOperand(1); 1485 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1486 MVT VT = N->getValueType(0); 1487 1488 // fold (mulhs x, 0) -> 0 1489 if (N1C && N1C->isNullValue()) 1490 return N1; 1491 // fold (mulhs x, 1) -> (sra x, size(x)-1) 1492 if (N1C && N1C->getAPIntValue() == 1) 1493 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 1494 DAG.getConstant(N0.getValueType().getSizeInBits()-1, 1495 TLI.getShiftAmountTy())); 1496 // fold (mulhs x, undef) -> 0 1497 if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) 1498 return DAG.getConstant(0, VT); 1499 1500 return SDValue(); 1501} 1502 1503SDValue DAGCombiner::visitMULHU(SDNode *N) { 1504 SDValue N0 = N->getOperand(0); 1505 SDValue N1 = N->getOperand(1); 1506 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1507 MVT VT = N->getValueType(0); 1508 1509 // fold (mulhu x, 0) -> 0 1510 if (N1C && N1C->isNullValue()) 1511 return N1; 1512 // fold (mulhu x, 1) -> 0 1513 if (N1C && N1C->getAPIntValue() == 1) 1514 return DAG.getConstant(0, N0.getValueType()); 1515 // fold (mulhu x, undef) -> 0 1516 if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) 1517 return DAG.getConstant(0, VT); 1518 1519 return SDValue(); 1520} 1521 1522/// SimplifyNodeWithTwoResults - Perform optimizations common to nodes that 1523/// compute two values. LoOp and HiOp give the opcodes for the two computations 1524/// that are being performed. Return true if a simplification was made. 1525/// 1526SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp, 1527 unsigned HiOp) { 1528 // If the high half is not needed, just compute the low half. 1529 bool HiExists = N->hasAnyUseOfValue(1); 1530 if (!HiExists && 1531 (!LegalOperations || 1532 TLI.isOperationLegal(LoOp, N->getValueType(0)))) { 1533 SDValue Res = DAG.getNode(LoOp, N->getValueType(0), N->op_begin(), 1534 N->getNumOperands()); 1535 return CombineTo(N, Res, Res); 1536 } 1537 1538 // If the low half is not needed, just compute the high half. 1539 bool LoExists = N->hasAnyUseOfValue(0); 1540 if (!LoExists && 1541 (!LegalOperations || 1542 TLI.isOperationLegal(HiOp, N->getValueType(1)))) { 1543 SDValue Res = DAG.getNode(HiOp, N->getValueType(1), N->op_begin(), 1544 N->getNumOperands()); 1545 return CombineTo(N, Res, Res); 1546 } 1547 1548 // If both halves are used, return as it is. 1549 if (LoExists && HiExists) 1550 return SDValue(); 1551 1552 // If the two computed results can be simplified separately, separate them. 1553 if (LoExists) { 1554 SDValue Lo = DAG.getNode(LoOp, N->getValueType(0), 1555 N->op_begin(), N->getNumOperands()); 1556 AddToWorkList(Lo.getNode()); 1557 SDValue LoOpt = combine(Lo.getNode()); 1558 if (LoOpt.getNode() && LoOpt.getNode() != Lo.getNode() && 1559 (!LegalOperations || 1560 TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType()))) 1561 return CombineTo(N, LoOpt, LoOpt); 1562 } 1563 1564 if (HiExists) { 1565 SDValue Hi = DAG.getNode(HiOp, N->getValueType(1), 1566 N->op_begin(), N->getNumOperands()); 1567 AddToWorkList(Hi.getNode()); 1568 SDValue HiOpt = combine(Hi.getNode()); 1569 if (HiOpt.getNode() && HiOpt != Hi && 1570 (!LegalOperations || 1571 TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType()))) 1572 return CombineTo(N, HiOpt, HiOpt); 1573 } 1574 return SDValue(); 1575} 1576 1577SDValue DAGCombiner::visitSMUL_LOHI(SDNode *N) { 1578 SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS); 1579 if (Res.getNode()) return Res; 1580 1581 return SDValue(); 1582} 1583 1584SDValue DAGCombiner::visitUMUL_LOHI(SDNode *N) { 1585 SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU); 1586 if (Res.getNode()) return Res; 1587 1588 return SDValue(); 1589} 1590 1591SDValue DAGCombiner::visitSDIVREM(SDNode *N) { 1592 SDValue Res = SimplifyNodeWithTwoResults(N, ISD::SDIV, ISD::SREM); 1593 if (Res.getNode()) return Res; 1594 1595 return SDValue(); 1596} 1597 1598SDValue DAGCombiner::visitUDIVREM(SDNode *N) { 1599 SDValue Res = SimplifyNodeWithTwoResults(N, ISD::UDIV, ISD::UREM); 1600 if (Res.getNode()) return Res; 1601 1602 return SDValue(); 1603} 1604 1605/// SimplifyBinOpWithSameOpcodeHands - If this is a binary operator with 1606/// two operands of the same opcode, try to simplify it. 1607SDValue DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) { 1608 SDValue N0 = N->getOperand(0), N1 = N->getOperand(1); 1609 MVT VT = N0.getValueType(); 1610 assert(N0.getOpcode() == N1.getOpcode() && "Bad input!"); 1611 1612 // For each of OP in AND/OR/XOR: 1613 // fold (OP (zext x), (zext y)) -> (zext (OP x, y)) 1614 // fold (OP (sext x), (sext y)) -> (sext (OP x, y)) 1615 // fold (OP (aext x), (aext y)) -> (aext (OP x, y)) 1616 // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y)) 1617 if ((N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND|| 1618 N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::TRUNCATE) && 1619 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 1620 SDValue ORNode = DAG.getNode(N->getOpcode(), 1621 N0.getOperand(0).getValueType(), 1622 N0.getOperand(0), N1.getOperand(0)); 1623 AddToWorkList(ORNode.getNode()); 1624 return DAG.getNode(N0.getOpcode(), VT, ORNode); 1625 } 1626 1627 // For each of OP in SHL/SRL/SRA/AND... 1628 // fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z) 1629 // fold (or (OP x, z), (OP y, z)) -> (OP (or x, y), z) 1630 // fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z) 1631 if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL || 1632 N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) && 1633 N0.getOperand(1) == N1.getOperand(1)) { 1634 SDValue ORNode = DAG.getNode(N->getOpcode(), 1635 N0.getOperand(0).getValueType(), 1636 N0.getOperand(0), N1.getOperand(0)); 1637 AddToWorkList(ORNode.getNode()); 1638 return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1)); 1639 } 1640 1641 return SDValue(); 1642} 1643 1644SDValue DAGCombiner::visitAND(SDNode *N) { 1645 SDValue N0 = N->getOperand(0); 1646 SDValue N1 = N->getOperand(1); 1647 SDValue LL, LR, RL, RR, CC0, CC1; 1648 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1649 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1650 MVT VT = N1.getValueType(); 1651 unsigned BitWidth = VT.getSizeInBits(); 1652 1653 // fold vector ops 1654 if (VT.isVector()) { 1655 SDValue FoldedVOp = SimplifyVBinOp(N); 1656 if (FoldedVOp.getNode()) return FoldedVOp; 1657 } 1658 1659 // fold (and x, undef) -> 0 1660 if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) 1661 return DAG.getConstant(0, VT); 1662 // fold (and c1, c2) -> c1&c2 1663 if (N0C && N1C) 1664 return DAG.FoldConstantArithmetic(ISD::AND, VT, N0C, N1C); 1665 // canonicalize constant to RHS 1666 if (N0C && !N1C) 1667 return DAG.getNode(ISD::AND, VT, N1, N0); 1668 // fold (and x, -1) -> x 1669 if (N1C && N1C->isAllOnesValue()) 1670 return N0; 1671 // if (and x, c) is known to be zero, return 0 1672 if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0), 1673 APInt::getAllOnesValue(BitWidth))) 1674 return DAG.getConstant(0, VT); 1675 // reassociate and 1676 SDValue RAND = ReassociateOps(ISD::AND, N0, N1); 1677 if (RAND.getNode() != 0) 1678 return RAND; 1679 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 1680 if (N1C && N0.getOpcode() == ISD::OR) 1681 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 1682 if ((ORI->getAPIntValue() & N1C->getAPIntValue()) == N1C->getAPIntValue()) 1683 return N1; 1684 // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits. 1685 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 1686 SDValue N0Op0 = N0.getOperand(0); 1687 APInt Mask = ~N1C->getAPIntValue(); 1688 Mask.trunc(N0Op0.getValueSizeInBits()); 1689 if (DAG.MaskedValueIsZero(N0Op0, Mask)) { 1690 SDValue Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(), 1691 N0Op0); 1692 1693 // Replace uses of the AND with uses of the Zero extend node. 1694 CombineTo(N, Zext); 1695 1696 // We actually want to replace all uses of the any_extend with the 1697 // zero_extend, to avoid duplicating things. This will later cause this 1698 // AND to be folded. 1699 CombineTo(N0.getNode(), Zext); 1700 return SDValue(N, 0); // Return N so it doesn't get rechecked! 1701 } 1702 } 1703 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 1704 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1705 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1706 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1707 1708 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1709 LL.getValueType().isInteger()) { 1710 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 1711 if (cast<ConstantSDNode>(LR)->isNullValue() && Op1 == ISD::SETEQ) { 1712 SDValue ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1713 AddToWorkList(ORNode.getNode()); 1714 return DAG.getSetCC(VT, ORNode, LR, Op1); 1715 } 1716 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 1717 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 1718 SDValue ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1719 AddToWorkList(ANDNode.getNode()); 1720 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1721 } 1722 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 1723 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 1724 SDValue ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1725 AddToWorkList(ORNode.getNode()); 1726 return DAG.getSetCC(VT, ORNode, LR, Op1); 1727 } 1728 } 1729 // canonicalize equivalent to ll == rl 1730 if (LL == RR && LR == RL) { 1731 Op1 = ISD::getSetCCSwappedOperands(Op1); 1732 std::swap(RL, RR); 1733 } 1734 if (LL == RL && LR == RR) { 1735 bool isInteger = LL.getValueType().isInteger(); 1736 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 1737 if (Result != ISD::SETCC_INVALID && 1738 (!LegalOperations || TLI.isCondCodeLegal(Result, LL.getValueType()))) 1739 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1740 } 1741 } 1742 1743 // Simplify: and (op x...), (op y...) -> (op (and x, y)) 1744 if (N0.getOpcode() == N1.getOpcode()) { 1745 SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1746 if (Tmp.getNode()) return Tmp; 1747 } 1748 1749 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 1750 // fold (and (sra)) -> (and (srl)) when possible. 1751 if (!VT.isVector() && 1752 SimplifyDemandedBits(SDValue(N, 0))) 1753 return SDValue(N, 0); 1754 // fold (zext_inreg (extload x)) -> (zextload x) 1755 if (ISD::isEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode())) { 1756 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1757 MVT EVT = LN0->getMemoryVT(); 1758 // If we zero all the possible extended bits, then we can turn this into 1759 // a zextload if we are running before legalize or the operation is legal. 1760 unsigned BitWidth = N1.getValueSizeInBits(); 1761 if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth, 1762 BitWidth - EVT.getSizeInBits())) && 1763 ((!LegalOperations && !LN0->isVolatile()) || 1764 TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT))) { 1765 SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 1766 LN0->getBasePtr(), LN0->getSrcValue(), 1767 LN0->getSrcValueOffset(), EVT, 1768 LN0->isVolatile(), LN0->getAlignment()); 1769 AddToWorkList(N); 1770 CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1)); 1771 return SDValue(N, 0); // Return N so it doesn't get rechecked! 1772 } 1773 } 1774 // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use 1775 if (ISD::isSEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) && 1776 N0.hasOneUse()) { 1777 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1778 MVT EVT = LN0->getMemoryVT(); 1779 // If we zero all the possible extended bits, then we can turn this into 1780 // a zextload if we are running before legalize or the operation is legal. 1781 unsigned BitWidth = N1.getValueSizeInBits(); 1782 if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth, 1783 BitWidth - EVT.getSizeInBits())) && 1784 ((!LegalOperations && !LN0->isVolatile()) || 1785 TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT))) { 1786 SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 1787 LN0->getBasePtr(), LN0->getSrcValue(), 1788 LN0->getSrcValueOffset(), EVT, 1789 LN0->isVolatile(), LN0->getAlignment()); 1790 AddToWorkList(N); 1791 CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1)); 1792 return SDValue(N, 0); // Return N so it doesn't get rechecked! 1793 } 1794 } 1795 1796 // fold (and (load x), 255) -> (zextload x, i8) 1797 // fold (and (extload x, i16), 255) -> (zextload x, i8) 1798 if (N1C && N0.getOpcode() == ISD::LOAD) { 1799 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 1800 if (LN0->getExtensionType() != ISD::SEXTLOAD && 1801 LN0->isUnindexed() && N0.hasOneUse() && 1802 // Do not change the width of a volatile load. 1803 !LN0->isVolatile()) { 1804 MVT EVT = MVT::Other; 1805 uint32_t ActiveBits = N1C->getAPIntValue().getActiveBits(); 1806 if (ActiveBits > 0 && APIntOps::isMask(ActiveBits, N1C->getAPIntValue())) 1807 EVT = MVT::getIntegerVT(ActiveBits); 1808 1809 MVT LoadedVT = LN0->getMemoryVT(); 1810 // Do not generate loads of non-round integer types since these can 1811 // be expensive (and would be wrong if the type is not byte sized). 1812 if (EVT != MVT::Other && LoadedVT.bitsGT(EVT) && EVT.isRound() && 1813 (!LegalOperations || TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT))) { 1814 MVT PtrType = N0.getOperand(1).getValueType(); 1815 // For big endian targets, we need to add an offset to the pointer to 1816 // load the correct bytes. For little endian systems, we merely need to 1817 // read fewer bytes from the same pointer. 1818 unsigned LVTStoreBytes = LoadedVT.getStoreSizeInBits()/8; 1819 unsigned EVTStoreBytes = EVT.getStoreSizeInBits()/8; 1820 unsigned PtrOff = LVTStoreBytes - EVTStoreBytes; 1821 unsigned Alignment = LN0->getAlignment(); 1822 SDValue NewPtr = LN0->getBasePtr(); 1823 if (TLI.isBigEndian()) { 1824 NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr, 1825 DAG.getConstant(PtrOff, PtrType)); 1826 Alignment = MinAlign(Alignment, PtrOff); 1827 } 1828 AddToWorkList(NewPtr.getNode()); 1829 SDValue Load = 1830 DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), NewPtr, 1831 LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT, 1832 LN0->isVolatile(), Alignment); 1833 AddToWorkList(N); 1834 CombineTo(N0.getNode(), Load, Load.getValue(1)); 1835 return SDValue(N, 0); // Return N so it doesn't get rechecked! 1836 } 1837 } 1838 } 1839 1840 return SDValue(); 1841} 1842 1843SDValue DAGCombiner::visitOR(SDNode *N) { 1844 SDValue N0 = N->getOperand(0); 1845 SDValue N1 = N->getOperand(1); 1846 SDValue LL, LR, RL, RR, CC0, CC1; 1847 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1848 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1849 MVT VT = N1.getValueType(); 1850 1851 // fold vector ops 1852 if (VT.isVector()) { 1853 SDValue FoldedVOp = SimplifyVBinOp(N); 1854 if (FoldedVOp.getNode()) return FoldedVOp; 1855 } 1856 1857 // fold (or x, undef) -> -1 1858 if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) 1859 return DAG.getConstant(~0ULL, VT); 1860 // fold (or c1, c2) -> c1|c2 1861 if (N0C && N1C) 1862 return DAG.FoldConstantArithmetic(ISD::OR, VT, N0C, N1C); 1863 // canonicalize constant to RHS 1864 if (N0C && !N1C) 1865 return DAG.getNode(ISD::OR, VT, N1, N0); 1866 // fold (or x, 0) -> x 1867 if (N1C && N1C->isNullValue()) 1868 return N0; 1869 // fold (or x, -1) -> -1 1870 if (N1C && N1C->isAllOnesValue()) 1871 return N1; 1872 // fold (or x, c) -> c iff (x & ~c) == 0 1873 if (N1C && DAG.MaskedValueIsZero(N0, ~N1C->getAPIntValue())) 1874 return N1; 1875 // reassociate or 1876 SDValue ROR = ReassociateOps(ISD::OR, N0, N1); 1877 if (ROR.getNode() != 0) 1878 return ROR; 1879 // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2) 1880 if (N1C && N0.getOpcode() == ISD::AND && N0.getNode()->hasOneUse() && 1881 isa<ConstantSDNode>(N0.getOperand(1))) { 1882 ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1)); 1883 return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0), 1884 N1), 1885 DAG.getConstant(N1C->getAPIntValue() | 1886 C1->getAPIntValue(), VT)); 1887 } 1888 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 1889 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1890 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1891 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1892 1893 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1894 LL.getValueType().isInteger()) { 1895 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 1896 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 1897 if (cast<ConstantSDNode>(LR)->isNullValue() && 1898 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 1899 SDValue ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1900 AddToWorkList(ORNode.getNode()); 1901 return DAG.getSetCC(VT, ORNode, LR, Op1); 1902 } 1903 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 1904 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 1905 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 1906 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 1907 SDValue ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1908 AddToWorkList(ANDNode.getNode()); 1909 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1910 } 1911 } 1912 // canonicalize equivalent to ll == rl 1913 if (LL == RR && LR == RL) { 1914 Op1 = ISD::getSetCCSwappedOperands(Op1); 1915 std::swap(RL, RR); 1916 } 1917 if (LL == RL && LR == RR) { 1918 bool isInteger = LL.getValueType().isInteger(); 1919 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 1920 if (Result != ISD::SETCC_INVALID && 1921 (!LegalOperations || TLI.isCondCodeLegal(Result, LL.getValueType()))) 1922 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1923 } 1924 } 1925 1926 // Simplify: or (op x...), (op y...) -> (op (or x, y)) 1927 if (N0.getOpcode() == N1.getOpcode()) { 1928 SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N); 1929 if (Tmp.getNode()) return Tmp; 1930 } 1931 1932 // (X & C1) | (Y & C2) -> (X|Y) & C3 if possible. 1933 if (N0.getOpcode() == ISD::AND && 1934 N1.getOpcode() == ISD::AND && 1935 N0.getOperand(1).getOpcode() == ISD::Constant && 1936 N1.getOperand(1).getOpcode() == ISD::Constant && 1937 // Don't increase # computations. 1938 (N0.getNode()->hasOneUse() || N1.getNode()->hasOneUse())) { 1939 // We can only do this xform if we know that bits from X that are set in C2 1940 // but not in C1 are already zero. Likewise for Y. 1941 const APInt &LHSMask = 1942 cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue(); 1943 const APInt &RHSMask = 1944 cast<ConstantSDNode>(N1.getOperand(1))->getAPIntValue(); 1945 1946 if (DAG.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) && 1947 DAG.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) { 1948 SDValue X =DAG.getNode(ISD::OR, VT, N0.getOperand(0), N1.getOperand(0)); 1949 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(LHSMask|RHSMask, VT)); 1950 } 1951 } 1952 1953 1954 // See if this is some rotate idiom. 1955 if (SDNode *Rot = MatchRotate(N0, N1)) 1956 return SDValue(Rot, 0); 1957 1958 return SDValue(); 1959} 1960 1961 1962/// MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present. 1963static bool MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask) { 1964 if (Op.getOpcode() == ISD::AND) { 1965 if (isa<ConstantSDNode>(Op.getOperand(1))) { 1966 Mask = Op.getOperand(1); 1967 Op = Op.getOperand(0); 1968 } else { 1969 return false; 1970 } 1971 } 1972 1973 if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) { 1974 Shift = Op; 1975 return true; 1976 } 1977 return false; 1978} 1979 1980 1981// MatchRotate - Handle an 'or' of two operands. If this is one of the many 1982// idioms for rotate, and if the target supports rotation instructions, generate 1983// a rot[lr]. 1984SDNode *DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS) { 1985 // Must be a legal type. Expanded 'n promoted things won't work with rotates. 1986 MVT VT = LHS.getValueType(); 1987 if (!TLI.isTypeLegal(VT)) return 0; 1988 1989 // The target must have at least one rotate flavor. 1990 bool HasROTL = TLI.isOperationLegal(ISD::ROTL, VT); 1991 bool HasROTR = TLI.isOperationLegal(ISD::ROTR, VT); 1992 if (!HasROTL && !HasROTR) return 0; 1993 1994 // Match "(X shl/srl V1) & V2" where V2 may not be present. 1995 SDValue LHSShift; // The shift. 1996 SDValue LHSMask; // AND value if any. 1997 if (!MatchRotateHalf(LHS, LHSShift, LHSMask)) 1998 return 0; // Not part of a rotate. 1999 2000 SDValue RHSShift; // The shift. 2001 SDValue RHSMask; // AND value if any. 2002 if (!MatchRotateHalf(RHS, RHSShift, RHSMask)) 2003 return 0; // Not part of a rotate. 2004 2005 if (LHSShift.getOperand(0) != RHSShift.getOperand(0)) 2006 return 0; // Not shifting the same value. 2007 2008 if (LHSShift.getOpcode() == RHSShift.getOpcode()) 2009 return 0; // Shifts must disagree. 2010 2011 // Canonicalize shl to left side in a shl/srl pair. 2012 if (RHSShift.getOpcode() == ISD::SHL) { 2013 std::swap(LHS, RHS); 2014 std::swap(LHSShift, RHSShift); 2015 std::swap(LHSMask , RHSMask ); 2016 } 2017 2018 unsigned OpSizeInBits = VT.getSizeInBits(); 2019 SDValue LHSShiftArg = LHSShift.getOperand(0); 2020 SDValue LHSShiftAmt = LHSShift.getOperand(1); 2021 SDValue RHSShiftAmt = RHSShift.getOperand(1); 2022 2023 // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1) 2024 // fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2) 2025 if (LHSShiftAmt.getOpcode() == ISD::Constant && 2026 RHSShiftAmt.getOpcode() == ISD::Constant) { 2027 uint64_t LShVal = cast<ConstantSDNode>(LHSShiftAmt)->getZExtValue(); 2028 uint64_t RShVal = cast<ConstantSDNode>(RHSShiftAmt)->getZExtValue(); 2029 if ((LShVal + RShVal) != OpSizeInBits) 2030 return 0; 2031 2032 SDValue Rot; 2033 if (HasROTL) 2034 Rot = DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt); 2035 else 2036 Rot = DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt); 2037 2038 // If there is an AND of either shifted operand, apply it to the result. 2039 if (LHSMask.getNode() || RHSMask.getNode()) { 2040 APInt Mask = APInt::getAllOnesValue(OpSizeInBits); 2041 2042 if (LHSMask.getNode()) { 2043 APInt RHSBits = APInt::getLowBitsSet(OpSizeInBits, LShVal); 2044 Mask &= cast<ConstantSDNode>(LHSMask)->getAPIntValue() | RHSBits; 2045 } 2046 if (RHSMask.getNode()) { 2047 APInt LHSBits = APInt::getHighBitsSet(OpSizeInBits, RShVal); 2048 Mask &= cast<ConstantSDNode>(RHSMask)->getAPIntValue() | LHSBits; 2049 } 2050 2051 Rot = DAG.getNode(ISD::AND, VT, Rot, DAG.getConstant(Mask, VT)); 2052 } 2053 2054 return Rot.getNode(); 2055 } 2056 2057 // If there is a mask here, and we have a variable shift, we can't be sure 2058 // that we're masking out the right stuff. 2059 if (LHSMask.getNode() || RHSMask.getNode()) 2060 return 0; 2061 2062 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y) 2063 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotr x, (sub 32, y)) 2064 if (RHSShiftAmt.getOpcode() == ISD::SUB && 2065 LHSShiftAmt == RHSShiftAmt.getOperand(1)) { 2066 if (ConstantSDNode *SUBC = 2067 dyn_cast<ConstantSDNode>(RHSShiftAmt.getOperand(0))) { 2068 if (SUBC->getAPIntValue() == OpSizeInBits) { 2069 if (HasROTL) 2070 return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode(); 2071 else 2072 return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).getNode(); 2073 } 2074 } 2075 } 2076 2077 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y) 2078 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotl x, (sub 32, y)) 2079 if (LHSShiftAmt.getOpcode() == ISD::SUB && 2080 RHSShiftAmt == LHSShiftAmt.getOperand(1)) { 2081 if (ConstantSDNode *SUBC = 2082 dyn_cast<ConstantSDNode>(LHSShiftAmt.getOperand(0))) { 2083 if (SUBC->getAPIntValue() == OpSizeInBits) { 2084 if (HasROTR) 2085 return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).getNode(); 2086 else 2087 return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).getNode(); 2088 } 2089 } 2090 } 2091 2092 // Look for sign/zext/any-extended or truncate cases: 2093 if ((LHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND 2094 || LHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND 2095 || LHSShiftAmt.getOpcode() == ISD::ANY_EXTEND 2096 || LHSShiftAmt.getOpcode() == ISD::TRUNCATE) && 2097 (RHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND 2098 || RHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND 2099 || RHSShiftAmt.getOpcode() == ISD::ANY_EXTEND 2100 || RHSShiftAmt.getOpcode() == ISD::TRUNCATE)) { 2101 SDValue LExtOp0 = LHSShiftAmt.getOperand(0); 2102 SDValue RExtOp0 = RHSShiftAmt.getOperand(0); 2103 if (RExtOp0.getOpcode() == ISD::SUB && 2104 RExtOp0.getOperand(1) == LExtOp0) { 2105 // fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) -> 2106 // (rotl x, y) 2107 // fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) -> 2108 // (rotr x, (sub 32, y)) 2109 if (ConstantSDNode *SUBC = 2110 dyn_cast<ConstantSDNode>(RExtOp0.getOperand(0))) { 2111 if (SUBC->getAPIntValue() == OpSizeInBits) { 2112 return DAG.getNode(HasROTL ? ISD::ROTL : ISD::ROTR, VT, LHSShiftArg, 2113 HasROTL ? LHSShiftAmt : RHSShiftAmt).getNode(); 2114 } 2115 } 2116 } else if (LExtOp0.getOpcode() == ISD::SUB && 2117 RExtOp0 == LExtOp0.getOperand(1)) { 2118 // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext y))) -> 2119 // (rotr x, y) 2120 // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext y))) -> 2121 // (rotl x, (sub 32, y)) 2122 if (ConstantSDNode *SUBC = 2123 dyn_cast<ConstantSDNode>(LExtOp0.getOperand(0))) { 2124 if (SUBC->getAPIntValue() == OpSizeInBits) { 2125 return DAG.getNode(HasROTR ? ISD::ROTR : ISD::ROTL, VT, LHSShiftArg, 2126 HasROTR ? RHSShiftAmt : LHSShiftAmt).getNode(); 2127 } 2128 } 2129 } 2130 } 2131 2132 return 0; 2133} 2134 2135 2136SDValue DAGCombiner::visitXOR(SDNode *N) { 2137 SDValue N0 = N->getOperand(0); 2138 SDValue N1 = N->getOperand(1); 2139 SDValue LHS, RHS, CC; 2140 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2141 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2142 MVT VT = N0.getValueType(); 2143 2144 // fold vector ops 2145 if (VT.isVector()) { 2146 SDValue FoldedVOp = SimplifyVBinOp(N); 2147 if (FoldedVOp.getNode()) return FoldedVOp; 2148 } 2149 2150 // fold (xor undef, undef) -> 0. This is a common idiom (misuse). 2151 if (N0.getOpcode() == ISD::UNDEF && N1.getOpcode() == ISD::UNDEF) 2152 return DAG.getConstant(0, VT); 2153 // fold (xor x, undef) -> undef 2154 if (N0.getOpcode() == ISD::UNDEF) 2155 return N0; 2156 if (N1.getOpcode() == ISD::UNDEF) 2157 return N1; 2158 // fold (xor c1, c2) -> c1^c2 2159 if (N0C && N1C) 2160 return DAG.FoldConstantArithmetic(ISD::XOR, VT, N0C, N1C); 2161 // canonicalize constant to RHS 2162 if (N0C && !N1C) 2163 return DAG.getNode(ISD::XOR, VT, N1, N0); 2164 // fold (xor x, 0) -> x 2165 if (N1C && N1C->isNullValue()) 2166 return N0; 2167 // reassociate xor 2168 SDValue RXOR = ReassociateOps(ISD::XOR, N0, N1); 2169 if (RXOR.getNode() != 0) 2170 return RXOR; 2171 2172 // fold !(x cc y) -> (x !cc y) 2173 if (N1C && N1C->getAPIntValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 2174 bool isInt = LHS.getValueType().isInteger(); 2175 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 2176 isInt); 2177 2178 if (!LegalOperations || TLI.isCondCodeLegal(NotCC, LHS.getValueType())) { 2179 switch (N0.getOpcode()) { 2180 default: 2181 assert(0 && "Unhandled SetCC Equivalent!"); 2182 abort(); 2183 case ISD::SETCC: 2184 return DAG.getSetCC(VT, LHS, RHS, NotCC); 2185 case ISD::SELECT_CC: 2186 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2), 2187 N0.getOperand(3), NotCC); 2188 } 2189 } 2190 } 2191 2192 // fold (not (zext (setcc x, y))) -> (zext (not (setcc x, y))) 2193 if (N1C && N1C->getAPIntValue() == 1 && N0.getOpcode() == ISD::ZERO_EXTEND && 2194 N0.getNode()->hasOneUse() && 2195 isSetCCEquivalent(N0.getOperand(0), LHS, RHS, CC)){ 2196 SDValue V = N0.getOperand(0); 2197 V = DAG.getNode(ISD::XOR, V.getValueType(), V, 2198 DAG.getConstant(1, V.getValueType())); 2199 AddToWorkList(V.getNode()); 2200 return DAG.getNode(ISD::ZERO_EXTEND, VT, V); 2201 } 2202 2203 // fold !(x or y) -> (!x and !y) iff x or y are setcc 2204 if (N1C && N1C->getAPIntValue() == 1 && VT == MVT::i1 && 2205 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 2206 SDValue LHS = N0.getOperand(0), RHS = N0.getOperand(1); 2207 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 2208 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 2209 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 2210 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 2211 AddToWorkList(LHS.getNode()); AddToWorkList(RHS.getNode()); 2212 return DAG.getNode(NewOpcode, VT, LHS, RHS); 2213 } 2214 } 2215 // fold !(x or y) -> (!x and !y) iff x or y are constants 2216 if (N1C && N1C->isAllOnesValue() && 2217 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 2218 SDValue LHS = N0.getOperand(0), RHS = N0.getOperand(1); 2219 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 2220 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 2221 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 2222 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 2223 AddToWorkList(LHS.getNode()); AddToWorkList(RHS.getNode()); 2224 return DAG.getNode(NewOpcode, VT, LHS, RHS); 2225 } 2226 } 2227 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 2228 if (N1C && N0.getOpcode() == ISD::XOR) { 2229 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 2230 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 2231 if (N00C) 2232 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 2233 DAG.getConstant(N1C->getAPIntValue()^ 2234 N00C->getAPIntValue(), VT)); 2235 if (N01C) 2236 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 2237 DAG.getConstant(N1C->getAPIntValue()^ 2238 N01C->getAPIntValue(), VT)); 2239 } 2240 // fold (xor x, x) -> 0 2241 if (N0 == N1) { 2242 if (!VT.isVector()) { 2243 return DAG.getConstant(0, VT); 2244 } else if (!LegalOperations || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)){ 2245 // Produce a vector of zeros. 2246 SDValue El = DAG.getConstant(0, VT.getVectorElementType()); 2247 std::vector<SDValue> Ops(VT.getVectorNumElements(), El); 2248 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 2249 } 2250 } 2251 2252 // Simplify: xor (op x...), (op y...) -> (op (xor x, y)) 2253 if (N0.getOpcode() == N1.getOpcode()) { 2254 SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N); 2255 if (Tmp.getNode()) return Tmp; 2256 } 2257 2258 // Simplify the expression using non-local knowledge. 2259 if (!VT.isVector() && 2260 SimplifyDemandedBits(SDValue(N, 0))) 2261 return SDValue(N, 0); 2262 2263 return SDValue(); 2264} 2265 2266/// visitShiftByConstant - Handle transforms common to the three shifts, when 2267/// the shift amount is a constant. 2268SDValue DAGCombiner::visitShiftByConstant(SDNode *N, unsigned Amt) { 2269 SDNode *LHS = N->getOperand(0).getNode(); 2270 if (!LHS->hasOneUse()) return SDValue(); 2271 2272 // We want to pull some binops through shifts, so that we have (and (shift)) 2273 // instead of (shift (and)), likewise for add, or, xor, etc. This sort of 2274 // thing happens with address calculations, so it's important to canonicalize 2275 // it. 2276 bool HighBitSet = false; // Can we transform this if the high bit is set? 2277 2278 switch (LHS->getOpcode()) { 2279 default: return SDValue(); 2280 case ISD::OR: 2281 case ISD::XOR: 2282 HighBitSet = false; // We can only transform sra if the high bit is clear. 2283 break; 2284 case ISD::AND: 2285 HighBitSet = true; // We can only transform sra if the high bit is set. 2286 break; 2287 case ISD::ADD: 2288 if (N->getOpcode() != ISD::SHL) 2289 return SDValue(); // only shl(add) not sr[al](add). 2290 HighBitSet = false; // We can only transform sra if the high bit is clear. 2291 break; 2292 } 2293 2294 // We require the RHS of the binop to be a constant as well. 2295 ConstantSDNode *BinOpCst = dyn_cast<ConstantSDNode>(LHS->getOperand(1)); 2296 if (!BinOpCst) return SDValue(); 2297 2298 2299 // FIXME: disable this for unless the input to the binop is a shift by a 2300 // constant. If it is not a shift, it pessimizes some common cases like: 2301 // 2302 //void foo(int *X, int i) { X[i & 1235] = 1; } 2303 //int bar(int *X, int i) { return X[i & 255]; } 2304 SDNode *BinOpLHSVal = LHS->getOperand(0).getNode(); 2305 if ((BinOpLHSVal->getOpcode() != ISD::SHL && 2306 BinOpLHSVal->getOpcode() != ISD::SRA && 2307 BinOpLHSVal->getOpcode() != ISD::SRL) || 2308 !isa<ConstantSDNode>(BinOpLHSVal->getOperand(1))) 2309 return SDValue(); 2310 2311 MVT VT = N->getValueType(0); 2312 2313 // If this is a signed shift right, and the high bit is modified 2314 // by the logical operation, do not perform the transformation. 2315 // The highBitSet boolean indicates the value of the high bit of 2316 // the constant which would cause it to be modified for this 2317 // operation. 2318 if (N->getOpcode() == ISD::SRA) { 2319 bool BinOpRHSSignSet = BinOpCst->getAPIntValue().isNegative(); 2320 if (BinOpRHSSignSet != HighBitSet) 2321 return SDValue(); 2322 } 2323 2324 // Fold the constants, shifting the binop RHS by the shift amount. 2325 SDValue NewRHS = DAG.getNode(N->getOpcode(), N->getValueType(0), 2326 LHS->getOperand(1), N->getOperand(1)); 2327 2328 // Create the new shift. 2329 SDValue NewShift = DAG.getNode(N->getOpcode(), VT, LHS->getOperand(0), 2330 N->getOperand(1)); 2331 2332 // Create the new binop. 2333 return DAG.getNode(LHS->getOpcode(), VT, NewShift, NewRHS); 2334} 2335 2336 2337SDValue DAGCombiner::visitSHL(SDNode *N) { 2338 SDValue N0 = N->getOperand(0); 2339 SDValue N1 = N->getOperand(1); 2340 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2341 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2342 MVT VT = N0.getValueType(); 2343 unsigned OpSizeInBits = VT.getSizeInBits(); 2344 2345 // fold (shl c1, c2) -> c1<<c2 2346 if (N0C && N1C) 2347 return DAG.FoldConstantArithmetic(ISD::SHL, VT, N0C, N1C); 2348 // fold (shl 0, x) -> 0 2349 if (N0C && N0C->isNullValue()) 2350 return N0; 2351 // fold (shl x, c >= size(x)) -> undef 2352 if (N1C && N1C->getZExtValue() >= OpSizeInBits) 2353 return DAG.getNode(ISD::UNDEF, VT); 2354 // fold (shl x, 0) -> x 2355 if (N1C && N1C->isNullValue()) 2356 return N0; 2357 // if (shl x, c) is known to be zero, return 0 2358 if (DAG.MaskedValueIsZero(SDValue(N, 0), 2359 APInt::getAllOnesValue(VT.getSizeInBits()))) 2360 return DAG.getConstant(0, VT); 2361 // fold (shl x, (trunc (and y, c))) -> (shl x, (and (trunc y), c)) 2362 // iff (trunc c) == c 2363 if (N1.getOpcode() == ISD::TRUNCATE && 2364 N1.getOperand(0).getOpcode() == ISD::AND && 2365 N1.hasOneUse() && N1.getOperand(0).hasOneUse()) { 2366 SDValue N101 = N1.getOperand(0).getOperand(1); 2367 if (ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101)) { 2368 MVT TruncVT = N1.getValueType(); 2369 SDValue N100 = N1.getOperand(0).getOperand(0); 2370 return DAG.getNode(ISD::SHL, VT, N0, 2371 DAG.getNode(ISD::AND, TruncVT, 2372 DAG.getNode(ISD::TRUNCATE, TruncVT, N100), 2373 DAG.getConstant(N101C->getZExtValue(), 2374 TruncVT))); 2375 } 2376 } 2377 2378 if (N1C && SimplifyDemandedBits(SDValue(N, 0))) 2379 return SDValue(N, 0); 2380 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 2381 if (N1C && N0.getOpcode() == ISD::SHL && 2382 N0.getOperand(1).getOpcode() == ISD::Constant) { 2383 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue(); 2384 uint64_t c2 = N1C->getZExtValue(); 2385 if (c1 + c2 > OpSizeInBits) 2386 return DAG.getConstant(0, VT); 2387 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 2388 DAG.getConstant(c1 + c2, N1.getValueType())); 2389 } 2390 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 2391 // (srl (and x, -1 << c1), c1-c2) 2392 if (N1C && N0.getOpcode() == ISD::SRL && 2393 N0.getOperand(1).getOpcode() == ISD::Constant) { 2394 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue(); 2395 uint64_t c2 = N1C->getZExtValue(); 2396 SDValue Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 2397 DAG.getConstant(~0ULL << c1, VT)); 2398 if (c2 > c1) 2399 return DAG.getNode(ISD::SHL, VT, Mask, 2400 DAG.getConstant(c2-c1, N1.getValueType())); 2401 else 2402 return DAG.getNode(ISD::SRL, VT, Mask, 2403 DAG.getConstant(c1-c2, N1.getValueType())); 2404 } 2405 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 2406 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 2407 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 2408 DAG.getConstant(~0ULL << N1C->getZExtValue(), VT)); 2409 2410 return N1C ? visitShiftByConstant(N, N1C->getZExtValue()) : SDValue(); 2411} 2412 2413SDValue DAGCombiner::visitSRA(SDNode *N) { 2414 SDValue N0 = N->getOperand(0); 2415 SDValue N1 = N->getOperand(1); 2416 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2417 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2418 MVT VT = N0.getValueType(); 2419 2420 // fold (sra c1, c2) -> c1>>c2 2421 if (N0C && N1C) 2422 return DAG.FoldConstantArithmetic(ISD::SRA, VT, N0C, N1C); 2423 // fold (sra 0, x) -> 0 2424 if (N0C && N0C->isNullValue()) 2425 return N0; 2426 // fold (sra -1, x) -> -1 2427 if (N0C && N0C->isAllOnesValue()) 2428 return N0; 2429 // fold (sra x, c >= size(x)) -> undef 2430 if (N1C && N1C->getZExtValue() >= VT.getSizeInBits()) 2431 return DAG.getNode(ISD::UNDEF, VT); 2432 // fold (sra x, 0) -> x 2433 if (N1C && N1C->isNullValue()) 2434 return N0; 2435 // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports 2436 // sext_inreg. 2437 if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) { 2438 unsigned LowBits = VT.getSizeInBits() - (unsigned)N1C->getZExtValue(); 2439 MVT EVT = MVT::getIntegerVT(LowBits); 2440 if ((!LegalOperations || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT))) 2441 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), 2442 DAG.getValueType(EVT)); 2443 } 2444 2445 // fold (sra (sra x, c1), c2) -> (sra x, c1+c2) 2446 if (N1C && N0.getOpcode() == ISD::SRA) { 2447 if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 2448 unsigned Sum = N1C->getZExtValue() + C1->getZExtValue(); 2449 if (Sum >= VT.getSizeInBits()) Sum = VT.getSizeInBits()-1; 2450 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), 2451 DAG.getConstant(Sum, N1C->getValueType(0))); 2452 } 2453 } 2454 2455 // fold sra (shl X, m), result_size - n 2456 // -> (sign_extend (trunc (shl X, result_size - n - m))) for 2457 // result_size - n != m. 2458 // If truncate is free for the target sext(shl) is likely to result in better 2459 // code. 2460 if (N0.getOpcode() == ISD::SHL) { 2461 // Get the two constanst of the shifts, CN0 = m, CN = n. 2462 const ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 2463 if (N01C && N1C) { 2464 // Determine what the truncate's result bitsize and type would be. 2465 unsigned VTValSize = VT.getSizeInBits(); 2466 MVT TruncVT = 2467 MVT::getIntegerVT(VTValSize - N1C->getZExtValue()); 2468 // Determine the residual right-shift amount. 2469 unsigned ShiftAmt = N1C->getZExtValue() - N01C->getZExtValue(); 2470 2471 // If the shift is not a no-op (in which case this should be just a sign 2472 // extend already), the truncated to type is legal, sign_extend is legal 2473 // on that type, and the the truncate to that type is both legal and free, 2474 // perform the transform. 2475 if (ShiftAmt && 2476 TLI.isOperationLegal(ISD::SIGN_EXTEND, TruncVT) && 2477 TLI.isOperationLegal(ISD::TRUNCATE, VT) && 2478 TLI.isTruncateFree(VT, TruncVT)) { 2479 2480 SDValue Amt = DAG.getConstant(ShiftAmt, TLI.getShiftAmountTy()); 2481 SDValue Shift = DAG.getNode(ISD::SRL, VT, N0.getOperand(0), Amt); 2482 SDValue Trunc = DAG.getNode(ISD::TRUNCATE, TruncVT, Shift); 2483 return DAG.getNode(ISD::SIGN_EXTEND, N->getValueType(0), Trunc); 2484 } 2485 } 2486 } 2487 2488 // fold (sra x, (trunc (and y, c))) -> (sra x, (and (trunc y), c)) 2489 // iff (trunc c) == c 2490 if (N1.getOpcode() == ISD::TRUNCATE && 2491 N1.getOperand(0).getOpcode() == ISD::AND && 2492 N1.hasOneUse() && N1.getOperand(0).hasOneUse()) { 2493 SDValue N101 = N1.getOperand(0).getOperand(1); 2494 if (ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101)) { 2495 MVT TruncVT = N1.getValueType(); 2496 SDValue N100 = N1.getOperand(0).getOperand(0); 2497 return DAG.getNode(ISD::SRA, VT, N0, 2498 DAG.getNode(ISD::AND, TruncVT, 2499 DAG.getNode(ISD::TRUNCATE, TruncVT, N100), 2500 DAG.getConstant(N101C->getZExtValue(), 2501 TruncVT))); 2502 } 2503 } 2504 2505 // Simplify, based on bits shifted out of the LHS. 2506 if (N1C && SimplifyDemandedBits(SDValue(N, 0))) 2507 return SDValue(N, 0); 2508 2509 2510 // If the sign bit is known to be zero, switch this to a SRL. 2511 if (DAG.SignBitIsZero(N0)) 2512 return DAG.getNode(ISD::SRL, VT, N0, N1); 2513 2514 return N1C ? visitShiftByConstant(N, N1C->getZExtValue()) : SDValue(); 2515} 2516 2517SDValue DAGCombiner::visitSRL(SDNode *N) { 2518 SDValue N0 = N->getOperand(0); 2519 SDValue N1 = N->getOperand(1); 2520 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2521 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2522 MVT VT = N0.getValueType(); 2523 unsigned OpSizeInBits = VT.getSizeInBits(); 2524 2525 // fold (srl c1, c2) -> c1 >>u c2 2526 if (N0C && N1C) 2527 return DAG.FoldConstantArithmetic(ISD::SRL, VT, N0C, N1C); 2528 // fold (srl 0, x) -> 0 2529 if (N0C && N0C->isNullValue()) 2530 return N0; 2531 // fold (srl x, c >= size(x)) -> undef 2532 if (N1C && N1C->getZExtValue() >= OpSizeInBits) 2533 return DAG.getNode(ISD::UNDEF, VT); 2534 // fold (srl x, 0) -> x 2535 if (N1C && N1C->isNullValue()) 2536 return N0; 2537 // if (srl x, c) is known to be zero, return 0 2538 if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0), 2539 APInt::getAllOnesValue(OpSizeInBits))) 2540 return DAG.getConstant(0, VT); 2541 2542 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 2543 if (N1C && N0.getOpcode() == ISD::SRL && 2544 N0.getOperand(1).getOpcode() == ISD::Constant) { 2545 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue(); 2546 uint64_t c2 = N1C->getZExtValue(); 2547 if (c1 + c2 > OpSizeInBits) 2548 return DAG.getConstant(0, VT); 2549 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 2550 DAG.getConstant(c1 + c2, N1.getValueType())); 2551 } 2552 2553 // fold (srl (anyextend x), c) -> (anyextend (srl x, c)) 2554 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 2555 // Shifting in all undef bits? 2556 MVT SmallVT = N0.getOperand(0).getValueType(); 2557 if (N1C->getZExtValue() >= SmallVT.getSizeInBits()) 2558 return DAG.getNode(ISD::UNDEF, VT); 2559 2560 SDValue SmallShift = DAG.getNode(ISD::SRL, SmallVT, N0.getOperand(0), N1); 2561 AddToWorkList(SmallShift.getNode()); 2562 return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift); 2563 } 2564 2565 // fold (srl (sra X, Y), 31) -> (srl X, 31). This srl only looks at the sign 2566 // bit, which is unmodified by sra. 2567 if (N1C && N1C->getZExtValue()+1 == VT.getSizeInBits()) { 2568 if (N0.getOpcode() == ISD::SRA) 2569 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), N1); 2570 } 2571 2572 // fold (srl (ctlz x), "5") -> x iff x has one bit set (the low bit). 2573 if (N1C && N0.getOpcode() == ISD::CTLZ && 2574 N1C->getAPIntValue() == Log2_32(VT.getSizeInBits())) { 2575 APInt KnownZero, KnownOne; 2576 APInt Mask = APInt::getAllOnesValue(VT.getSizeInBits()); 2577 DAG.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne); 2578 2579 // If any of the input bits are KnownOne, then the input couldn't be all 2580 // zeros, thus the result of the srl will always be zero. 2581 if (KnownOne.getBoolValue()) return DAG.getConstant(0, VT); 2582 2583 // If all of the bits input the to ctlz node are known to be zero, then 2584 // the result of the ctlz is "32" and the result of the shift is one. 2585 APInt UnknownBits = ~KnownZero & Mask; 2586 if (UnknownBits == 0) return DAG.getConstant(1, VT); 2587 2588 // Otherwise, check to see if there is exactly one bit input to the ctlz. 2589 if ((UnknownBits & (UnknownBits-1)) == 0) { 2590 // Okay, we know that only that the single bit specified by UnknownBits 2591 // could be set on input to the CTLZ node. If this bit is set, the SRL 2592 // will return 0, if it is clear, it returns 1. Change the CTLZ/SRL pair 2593 // to an SRL,XOR pair, which is likely to simplify more. 2594 unsigned ShAmt = UnknownBits.countTrailingZeros(); 2595 SDValue Op = N0.getOperand(0); 2596 if (ShAmt) { 2597 Op = DAG.getNode(ISD::SRL, VT, Op, 2598 DAG.getConstant(ShAmt, TLI.getShiftAmountTy())); 2599 AddToWorkList(Op.getNode()); 2600 } 2601 return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT)); 2602 } 2603 } 2604 2605 // fold (srl x, (trunc (and y, c))) -> (srl x, (and (trunc y), c)) 2606 // iff (trunc c) == c 2607 if (N1.getOpcode() == ISD::TRUNCATE && 2608 N1.getOperand(0).getOpcode() == ISD::AND && 2609 N1.hasOneUse() && N1.getOperand(0).hasOneUse()) { 2610 SDValue N101 = N1.getOperand(0).getOperand(1); 2611 if (ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N101)) { 2612 MVT TruncVT = N1.getValueType(); 2613 SDValue N100 = N1.getOperand(0).getOperand(0); 2614 return DAG.getNode(ISD::SRL, VT, N0, 2615 DAG.getNode(ISD::AND, TruncVT, 2616 DAG.getNode(ISD::TRUNCATE, TruncVT, N100), 2617 DAG.getConstant(N101C->getZExtValue(), 2618 TruncVT))); 2619 } 2620 } 2621 2622 // fold operands of srl based on knowledge that the low bits are not 2623 // demanded. 2624 if (N1C && SimplifyDemandedBits(SDValue(N, 0))) 2625 return SDValue(N, 0); 2626 2627 return N1C ? visitShiftByConstant(N, N1C->getZExtValue()) : SDValue(); 2628} 2629 2630SDValue DAGCombiner::visitCTLZ(SDNode *N) { 2631 SDValue N0 = N->getOperand(0); 2632 MVT VT = N->getValueType(0); 2633 2634 // fold (ctlz c1) -> c2 2635 if (isa<ConstantSDNode>(N0)) 2636 return DAG.getNode(ISD::CTLZ, VT, N0); 2637 return SDValue(); 2638} 2639 2640SDValue DAGCombiner::visitCTTZ(SDNode *N) { 2641 SDValue N0 = N->getOperand(0); 2642 MVT VT = N->getValueType(0); 2643 2644 // fold (cttz c1) -> c2 2645 if (isa<ConstantSDNode>(N0)) 2646 return DAG.getNode(ISD::CTTZ, VT, N0); 2647 return SDValue(); 2648} 2649 2650SDValue DAGCombiner::visitCTPOP(SDNode *N) { 2651 SDValue N0 = N->getOperand(0); 2652 MVT VT = N->getValueType(0); 2653 2654 // fold (ctpop c1) -> c2 2655 if (isa<ConstantSDNode>(N0)) 2656 return DAG.getNode(ISD::CTPOP, VT, N0); 2657 return SDValue(); 2658} 2659 2660SDValue DAGCombiner::visitSELECT(SDNode *N) { 2661 SDValue N0 = N->getOperand(0); 2662 SDValue N1 = N->getOperand(1); 2663 SDValue N2 = N->getOperand(2); 2664 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 2665 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2666 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 2667 MVT VT = N->getValueType(0); 2668 MVT VT0 = N0.getValueType(); 2669 2670 // fold select C, X, X -> X 2671 if (N1 == N2) 2672 return N1; 2673 // fold select true, X, Y -> X 2674 if (N0C && !N0C->isNullValue()) 2675 return N1; 2676 // fold select false, X, Y -> Y 2677 if (N0C && N0C->isNullValue()) 2678 return N2; 2679 // fold select C, 1, X -> C | X 2680 if (VT == MVT::i1 && N1C && N1C->getAPIntValue() == 1) 2681 return DAG.getNode(ISD::OR, VT, N0, N2); 2682 // fold select C, 0, 1 -> ~C 2683 if (VT.isInteger() && VT0.isInteger() && 2684 N1C && N2C && N1C->isNullValue() && N2C->getAPIntValue() == 1) { 2685 SDValue XORNode = DAG.getNode(ISD::XOR, VT0, N0, DAG.getConstant(1, VT0)); 2686 if (VT == VT0) 2687 return XORNode; 2688 AddToWorkList(XORNode.getNode()); 2689 if (VT.bitsGT(VT0)) 2690 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode); 2691 return DAG.getNode(ISD::TRUNCATE, VT, XORNode); 2692 } 2693 // fold select C, 0, X -> ~C & X 2694 if (VT == VT0 && VT == MVT::i1 && N1C && N1C->isNullValue()) { 2695 SDValue XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 2696 AddToWorkList(XORNode.getNode()); 2697 return DAG.getNode(ISD::AND, VT, XORNode, N2); 2698 } 2699 // fold select C, X, 1 -> ~C | X 2700 if (VT == VT0 && VT == MVT::i1 && N2C && N2C->getAPIntValue() == 1) { 2701 SDValue XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 2702 AddToWorkList(XORNode.getNode()); 2703 return DAG.getNode(ISD::OR, VT, XORNode, N1); 2704 } 2705 // fold select C, X, 0 -> C & X 2706 // FIXME: this should check for C type == X type, not i1? 2707 if (VT == MVT::i1 && N2C && N2C->isNullValue()) 2708 return DAG.getNode(ISD::AND, VT, N0, N1); 2709 // fold X ? X : Y --> X ? 1 : Y --> X | Y 2710 if (VT == MVT::i1 && N0 == N1) 2711 return DAG.getNode(ISD::OR, VT, N0, N2); 2712 // fold X ? Y : X --> X ? Y : 0 --> X & Y 2713 if (VT == MVT::i1 && N0 == N2) 2714 return DAG.getNode(ISD::AND, VT, N0, N1); 2715 2716 // If we can fold this based on the true/false value, do so. 2717 if (SimplifySelectOps(N, N1, N2)) 2718 return SDValue(N, 0); // Don't revisit N. 2719 2720 // fold selects based on a setcc into other things, such as min/max/abs 2721 if (N0.getOpcode() == ISD::SETCC) { 2722 // FIXME: 2723 // Check against MVT::Other for SELECT_CC, which is a workaround for targets 2724 // having to say they don't support SELECT_CC on every type the DAG knows 2725 // about, since there is no way to mark an opcode illegal at all value types 2726 if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other)) 2727 return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1), 2728 N1, N2, N0.getOperand(2)); 2729 else 2730 return SimplifySelect(N0, N1, N2); 2731 } 2732 return SDValue(); 2733} 2734 2735SDValue DAGCombiner::visitSELECT_CC(SDNode *N) { 2736 SDValue N0 = N->getOperand(0); 2737 SDValue N1 = N->getOperand(1); 2738 SDValue N2 = N->getOperand(2); 2739 SDValue N3 = N->getOperand(3); 2740 SDValue N4 = N->getOperand(4); 2741 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 2742 2743 // fold select_cc lhs, rhs, x, x, cc -> x 2744 if (N2 == N3) 2745 return N2; 2746 2747 // Determine if the condition we're dealing with is constant 2748 SDValue SCC = SimplifySetCC(TLI.getSetCCResultType(N0), N0, N1, CC, false); 2749 if (SCC.getNode()) AddToWorkList(SCC.getNode()); 2750 2751 if (ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.getNode())) { 2752 if (!SCCC->isNullValue()) 2753 return N2; // cond always true -> true val 2754 else 2755 return N3; // cond always false -> false val 2756 } 2757 2758 // Fold to a simpler select_cc 2759 if (SCC.getNode() && SCC.getOpcode() == ISD::SETCC) 2760 return DAG.getNode(ISD::SELECT_CC, N2.getValueType(), 2761 SCC.getOperand(0), SCC.getOperand(1), N2, N3, 2762 SCC.getOperand(2)); 2763 2764 // If we can fold this based on the true/false value, do so. 2765 if (SimplifySelectOps(N, N2, N3)) 2766 return SDValue(N, 0); // Don't revisit N. 2767 2768 // fold select_cc into other things, such as min/max/abs 2769 return SimplifySelectCC(N0, N1, N2, N3, CC); 2770} 2771 2772SDValue DAGCombiner::visitSETCC(SDNode *N) { 2773 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 2774 cast<CondCodeSDNode>(N->getOperand(2))->get()); 2775} 2776 2777// ExtendUsesToFormExtLoad - Trying to extend uses of a load to enable this: 2778// "fold ({s|z}ext (load x)) -> ({s|z}ext (truncate ({s|z}extload x)))" 2779// transformation. Returns true if extension are possible and the above 2780// mentioned transformation is profitable. 2781static bool ExtendUsesToFormExtLoad(SDNode *N, SDValue N0, 2782 unsigned ExtOpc, 2783 SmallVector<SDNode*, 4> &ExtendNodes, 2784 TargetLowering &TLI) { 2785 bool HasCopyToRegUses = false; 2786 bool isTruncFree = TLI.isTruncateFree(N->getValueType(0), N0.getValueType()); 2787 for (SDNode::use_iterator UI = N0.getNode()->use_begin(), 2788 UE = N0.getNode()->use_end(); 2789 UI != UE; ++UI) { 2790 SDNode *User = *UI; 2791 if (User == N) 2792 continue; 2793 // FIXME: Only extend SETCC N, N and SETCC N, c for now. 2794 if (User->getOpcode() == ISD::SETCC) { 2795 ISD::CondCode CC = cast<CondCodeSDNode>(User->getOperand(2))->get(); 2796 if (ExtOpc == ISD::ZERO_EXTEND && ISD::isSignedIntSetCC(CC)) 2797 // Sign bits will be lost after a zext. 2798 return false; 2799 bool Add = false; 2800 for (unsigned i = 0; i != 2; ++i) { 2801 SDValue UseOp = User->getOperand(i); 2802 if (UseOp == N0) 2803 continue; 2804 if (!isa<ConstantSDNode>(UseOp)) 2805 return false; 2806 Add = true; 2807 } 2808 if (Add) 2809 ExtendNodes.push_back(User); 2810 } else { 2811 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) { 2812 SDValue UseOp = User->getOperand(i); 2813 if (UseOp == N0) { 2814 // If truncate from extended type to original load type is free 2815 // on this target, then it's ok to extend a CopyToReg. 2816 if (isTruncFree && User->getOpcode() == ISD::CopyToReg) 2817 HasCopyToRegUses = true; 2818 else 2819 return false; 2820 } 2821 } 2822 } 2823 } 2824 2825 if (HasCopyToRegUses) { 2826 bool BothLiveOut = false; 2827 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 2828 UI != UE; ++UI) { 2829 SDNode *User = *UI; 2830 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) { 2831 SDValue UseOp = User->getOperand(i); 2832 if (UseOp.getNode() == N && UseOp.getResNo() == 0) { 2833 BothLiveOut = true; 2834 break; 2835 } 2836 } 2837 } 2838 if (BothLiveOut) 2839 // Both unextended and extended values are live out. There had better be 2840 // good a reason for the transformation. 2841 return ExtendNodes.size(); 2842 } 2843 return true; 2844} 2845 2846SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 2847 SDValue N0 = N->getOperand(0); 2848 MVT VT = N->getValueType(0); 2849 2850 // fold (sext c1) -> c1 2851 if (isa<ConstantSDNode>(N0)) 2852 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0); 2853 2854 // fold (sext (sext x)) -> (sext x) 2855 // fold (sext (aext x)) -> (sext x) 2856 if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 2857 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 2858 2859 if (N0.getOpcode() == ISD::TRUNCATE) { 2860 // fold (sext (truncate (load x))) -> (sext (smaller load x)) 2861 // fold (sext (truncate (srl (load x), c))) -> (sext (smaller load (x+c/n))) 2862 SDValue NarrowLoad = ReduceLoadWidth(N0.getNode()); 2863 if (NarrowLoad.getNode()) { 2864 if (NarrowLoad.getNode() != N0.getNode()) 2865 CombineTo(N0.getNode(), NarrowLoad); 2866 return DAG.getNode(ISD::SIGN_EXTEND, VT, NarrowLoad); 2867 } 2868 2869 // See if the value being truncated is already sign extended. If so, just 2870 // eliminate the trunc/sext pair. 2871 SDValue Op = N0.getOperand(0); 2872 unsigned OpBits = Op.getValueType().getSizeInBits(); 2873 unsigned MidBits = N0.getValueType().getSizeInBits(); 2874 unsigned DestBits = VT.getSizeInBits(); 2875 unsigned NumSignBits = DAG.ComputeNumSignBits(Op); 2876 2877 if (OpBits == DestBits) { 2878 // Op is i32, Mid is i8, and Dest is i32. If Op has more than 24 sign 2879 // bits, it is already ready. 2880 if (NumSignBits > DestBits-MidBits) 2881 return Op; 2882 } else if (OpBits < DestBits) { 2883 // Op is i32, Mid is i8, and Dest is i64. If Op has more than 24 sign 2884 // bits, just sext from i32. 2885 if (NumSignBits > OpBits-MidBits) 2886 return DAG.getNode(ISD::SIGN_EXTEND, VT, Op); 2887 } else { 2888 // Op is i64, Mid is i8, and Dest is i32. If Op has more than 56 sign 2889 // bits, just truncate to i32. 2890 if (NumSignBits > OpBits-MidBits) 2891 return DAG.getNode(ISD::TRUNCATE, VT, Op); 2892 } 2893 2894 // fold (sext (truncate x)) -> (sextinreg x). 2895 if (!LegalOperations || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, 2896 N0.getValueType())) { 2897 if (Op.getValueType().bitsLT(VT)) 2898 Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op); 2899 else if (Op.getValueType().bitsGT(VT)) 2900 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 2901 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, Op, 2902 DAG.getValueType(N0.getValueType())); 2903 } 2904 } 2905 2906 // fold (sext (load x)) -> (sext (truncate (sextload x))) 2907 if (ISD::isNON_EXTLoad(N0.getNode()) && 2908 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 2909 TLI.isLoadExtLegal(ISD::SEXTLOAD, N0.getValueType()))) { 2910 bool DoXform = true; 2911 SmallVector<SDNode*, 4> SetCCs; 2912 if (!N0.hasOneUse()) 2913 DoXform = ExtendUsesToFormExtLoad(N, N0, ISD::SIGN_EXTEND, SetCCs, TLI); 2914 if (DoXform) { 2915 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2916 SDValue ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 2917 LN0->getBasePtr(), LN0->getSrcValue(), 2918 LN0->getSrcValueOffset(), 2919 N0.getValueType(), 2920 LN0->isVolatile(), LN0->getAlignment()); 2921 CombineTo(N, ExtLoad); 2922 SDValue Trunc = DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad); 2923 CombineTo(N0.getNode(), Trunc, ExtLoad.getValue(1)); 2924 // Extend SetCC uses if necessary. 2925 for (unsigned i = 0, e = SetCCs.size(); i != e; ++i) { 2926 SDNode *SetCC = SetCCs[i]; 2927 SmallVector<SDValue, 4> Ops; 2928 for (unsigned j = 0; j != 2; ++j) { 2929 SDValue SOp = SetCC->getOperand(j); 2930 if (SOp == Trunc) 2931 Ops.push_back(ExtLoad); 2932 else 2933 Ops.push_back(DAG.getNode(ISD::SIGN_EXTEND, VT, SOp)); 2934 } 2935 Ops.push_back(SetCC->getOperand(2)); 2936 CombineTo(SetCC, DAG.getNode(ISD::SETCC, SetCC->getValueType(0), 2937 &Ops[0], Ops.size())); 2938 } 2939 return SDValue(N, 0); // Return N so it doesn't get rechecked! 2940 } 2941 } 2942 2943 // fold (sext (sextload x)) -> (sext (truncate (sextload x))) 2944 // fold (sext ( extload x)) -> (sext (truncate (sextload x))) 2945 if ((ISD::isSEXTLoad(N0.getNode()) || ISD::isEXTLoad(N0.getNode())) && 2946 ISD::isUNINDEXEDLoad(N0.getNode()) && N0.hasOneUse()) { 2947 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 2948 MVT EVT = LN0->getMemoryVT(); 2949 if ((!LegalOperations && !LN0->isVolatile()) || 2950 TLI.isLoadExtLegal(ISD::SEXTLOAD, EVT)) { 2951 SDValue ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 2952 LN0->getBasePtr(), LN0->getSrcValue(), 2953 LN0->getSrcValueOffset(), EVT, 2954 LN0->isVolatile(), LN0->getAlignment()); 2955 CombineTo(N, ExtLoad); 2956 CombineTo(N0.getNode(), 2957 DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 2958 ExtLoad.getValue(1)); 2959 return SDValue(N, 0); // Return N so it doesn't get rechecked! 2960 } 2961 } 2962 2963 // sext(setcc x,y,cc) -> select_cc x, y, -1, 0, cc 2964 if (N0.getOpcode() == ISD::SETCC) { 2965 SDValue SCC = 2966 SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), 2967 DAG.getConstant(~0ULL, VT), DAG.getConstant(0, VT), 2968 cast<CondCodeSDNode>(N0.getOperand(2))->get(), true); 2969 if (SCC.getNode()) return SCC; 2970 } 2971 2972 // fold (sext x) -> (zext x) if the sign bit is known zero. 2973 if ((!LegalOperations || TLI.isOperationLegal(ISD::ZERO_EXTEND, VT)) && 2974 DAG.SignBitIsZero(N0)) 2975 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 2976 2977 return SDValue(); 2978} 2979 2980SDValue DAGCombiner::visitZERO_EXTEND(SDNode *N) { 2981 SDValue N0 = N->getOperand(0); 2982 MVT VT = N->getValueType(0); 2983 2984 // fold (zext c1) -> c1 2985 if (isa<ConstantSDNode>(N0)) 2986 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 2987 // fold (zext (zext x)) -> (zext x) 2988 // fold (zext (aext x)) -> (zext x) 2989 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) 2990 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 2991 2992 // fold (zext (truncate (load x))) -> (zext (smaller load x)) 2993 // fold (zext (truncate (srl (load x), c))) -> (zext (small load (x+c/n))) 2994 if (N0.getOpcode() == ISD::TRUNCATE) { 2995 SDValue NarrowLoad = ReduceLoadWidth(N0.getNode()); 2996 if (NarrowLoad.getNode()) { 2997 if (NarrowLoad.getNode() != N0.getNode()) 2998 CombineTo(N0.getNode(), NarrowLoad); 2999 return DAG.getNode(ISD::ZERO_EXTEND, VT, NarrowLoad); 3000 } 3001 } 3002 3003 // fold (zext (truncate x)) -> (and x, mask) 3004 if (N0.getOpcode() == ISD::TRUNCATE && 3005 (!LegalOperations || TLI.isOperationLegal(ISD::AND, VT))) { 3006 SDValue Op = N0.getOperand(0); 3007 if (Op.getValueType().bitsLT(VT)) { 3008 Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op); 3009 } else if (Op.getValueType().bitsGT(VT)) { 3010 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 3011 } 3012 return DAG.getZeroExtendInReg(Op, N0.getValueType()); 3013 } 3014 3015 // fold (zext (and (trunc x), cst)) -> (and x, cst). 3016 if (N0.getOpcode() == ISD::AND && 3017 N0.getOperand(0).getOpcode() == ISD::TRUNCATE && 3018 N0.getOperand(1).getOpcode() == ISD::Constant) { 3019 SDValue X = N0.getOperand(0).getOperand(0); 3020 if (X.getValueType().bitsLT(VT)) { 3021 X = DAG.getNode(ISD::ANY_EXTEND, VT, X); 3022 } else if (X.getValueType().bitsGT(VT)) { 3023 X = DAG.getNode(ISD::TRUNCATE, VT, X); 3024 } 3025 APInt Mask = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue(); 3026 Mask.zext(VT.getSizeInBits()); 3027 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT)); 3028 } 3029 3030 // fold (zext (load x)) -> (zext (truncate (zextload x))) 3031 if (ISD::isNON_EXTLoad(N0.getNode()) && 3032 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 3033 TLI.isLoadExtLegal(ISD::ZEXTLOAD, N0.getValueType()))) { 3034 bool DoXform = true; 3035 SmallVector<SDNode*, 4> SetCCs; 3036 if (!N0.hasOneUse()) 3037 DoXform = ExtendUsesToFormExtLoad(N, N0, ISD::ZERO_EXTEND, SetCCs, TLI); 3038 if (DoXform) { 3039 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3040 SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 3041 LN0->getBasePtr(), LN0->getSrcValue(), 3042 LN0->getSrcValueOffset(), 3043 N0.getValueType(), 3044 LN0->isVolatile(), LN0->getAlignment()); 3045 CombineTo(N, ExtLoad); 3046 SDValue Trunc = DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad); 3047 CombineTo(N0.getNode(), Trunc, ExtLoad.getValue(1)); 3048 // Extend SetCC uses if necessary. 3049 for (unsigned i = 0, e = SetCCs.size(); i != e; ++i) { 3050 SDNode *SetCC = SetCCs[i]; 3051 SmallVector<SDValue, 4> Ops; 3052 for (unsigned j = 0; j != 2; ++j) { 3053 SDValue SOp = SetCC->getOperand(j); 3054 if (SOp == Trunc) 3055 Ops.push_back(ExtLoad); 3056 else 3057 Ops.push_back(DAG.getNode(ISD::ZERO_EXTEND, VT, SOp)); 3058 } 3059 Ops.push_back(SetCC->getOperand(2)); 3060 CombineTo(SetCC, DAG.getNode(ISD::SETCC, SetCC->getValueType(0), 3061 &Ops[0], Ops.size())); 3062 } 3063 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3064 } 3065 } 3066 3067 // fold (zext (zextload x)) -> (zext (truncate (zextload x))) 3068 // fold (zext ( extload x)) -> (zext (truncate (zextload x))) 3069 if ((ISD::isZEXTLoad(N0.getNode()) || ISD::isEXTLoad(N0.getNode())) && 3070 ISD::isUNINDEXEDLoad(N0.getNode()) && N0.hasOneUse()) { 3071 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3072 MVT EVT = LN0->getMemoryVT(); 3073 if ((!LegalOperations && !LN0->isVolatile()) || 3074 TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT)) { 3075 SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), 3076 LN0->getBasePtr(), LN0->getSrcValue(), 3077 LN0->getSrcValueOffset(), EVT, 3078 LN0->isVolatile(), LN0->getAlignment()); 3079 CombineTo(N, ExtLoad); 3080 CombineTo(N0.getNode(), 3081 DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 3082 ExtLoad.getValue(1)); 3083 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3084 } 3085 } 3086 3087 // zext(setcc x,y,cc) -> select_cc x, y, 1, 0, cc 3088 if (N0.getOpcode() == ISD::SETCC) { 3089 SDValue SCC = 3090 SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), 3091 DAG.getConstant(1, VT), DAG.getConstant(0, VT), 3092 cast<CondCodeSDNode>(N0.getOperand(2))->get(), true); 3093 if (SCC.getNode()) return SCC; 3094 } 3095 3096 return SDValue(); 3097} 3098 3099SDValue DAGCombiner::visitANY_EXTEND(SDNode *N) { 3100 SDValue N0 = N->getOperand(0); 3101 MVT VT = N->getValueType(0); 3102 3103 // fold (aext c1) -> c1 3104 if (isa<ConstantSDNode>(N0)) 3105 return DAG.getNode(ISD::ANY_EXTEND, VT, N0); 3106 // fold (aext (aext x)) -> (aext x) 3107 // fold (aext (zext x)) -> (zext x) 3108 // fold (aext (sext x)) -> (sext x) 3109 if (N0.getOpcode() == ISD::ANY_EXTEND || 3110 N0.getOpcode() == ISD::ZERO_EXTEND || 3111 N0.getOpcode() == ISD::SIGN_EXTEND) 3112 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 3113 3114 // fold (aext (truncate (load x))) -> (aext (smaller load x)) 3115 // fold (aext (truncate (srl (load x), c))) -> (aext (small load (x+c/n))) 3116 if (N0.getOpcode() == ISD::TRUNCATE) { 3117 SDValue NarrowLoad = ReduceLoadWidth(N0.getNode()); 3118 if (NarrowLoad.getNode()) { 3119 if (NarrowLoad.getNode() != N0.getNode()) 3120 CombineTo(N0.getNode(), NarrowLoad); 3121 return DAG.getNode(ISD::ANY_EXTEND, VT, NarrowLoad); 3122 } 3123 } 3124 3125 // fold (aext (truncate x)) 3126 if (N0.getOpcode() == ISD::TRUNCATE) { 3127 SDValue TruncOp = N0.getOperand(0); 3128 if (TruncOp.getValueType() == VT) 3129 return TruncOp; // x iff x size == zext size. 3130 if (TruncOp.getValueType().bitsGT(VT)) 3131 return DAG.getNode(ISD::TRUNCATE, VT, TruncOp); 3132 return DAG.getNode(ISD::ANY_EXTEND, VT, TruncOp); 3133 } 3134 3135 // fold (aext (and (trunc x), cst)) -> (and x, cst). 3136 if (N0.getOpcode() == ISD::AND && 3137 N0.getOperand(0).getOpcode() == ISD::TRUNCATE && 3138 N0.getOperand(1).getOpcode() == ISD::Constant) { 3139 SDValue X = N0.getOperand(0).getOperand(0); 3140 if (X.getValueType().bitsLT(VT)) { 3141 X = DAG.getNode(ISD::ANY_EXTEND, VT, X); 3142 } else if (X.getValueType().bitsGT(VT)) { 3143 X = DAG.getNode(ISD::TRUNCATE, VT, X); 3144 } 3145 APInt Mask = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue(); 3146 Mask.zext(VT.getSizeInBits()); 3147 return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT)); 3148 } 3149 3150 // fold (aext (load x)) -> (aext (truncate (extload x))) 3151 if (ISD::isNON_EXTLoad(N0.getNode()) && N0.hasOneUse() && 3152 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 3153 TLI.isLoadExtLegal(ISD::EXTLOAD, N0.getValueType()))) { 3154 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3155 SDValue ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(), 3156 LN0->getBasePtr(), LN0->getSrcValue(), 3157 LN0->getSrcValueOffset(), 3158 N0.getValueType(), 3159 LN0->isVolatile(), LN0->getAlignment()); 3160 CombineTo(N, ExtLoad); 3161 // Redirect any chain users to the new load. 3162 DAG.ReplaceAllUsesOfValueWith(SDValue(LN0, 1), 3163 SDValue(ExtLoad.getNode(), 1)); 3164 // If any node needs the original loaded value, recompute it. 3165 if (!LN0->use_empty()) 3166 CombineTo(LN0, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 3167 ExtLoad.getValue(1)); 3168 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3169 } 3170 3171 // fold (aext (zextload x)) -> (aext (truncate (zextload x))) 3172 // fold (aext (sextload x)) -> (aext (truncate (sextload x))) 3173 // fold (aext ( extload x)) -> (aext (truncate (extload x))) 3174 if (N0.getOpcode() == ISD::LOAD && 3175 !ISD::isNON_EXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) && 3176 N0.hasOneUse()) { 3177 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3178 MVT EVT = LN0->getMemoryVT(); 3179 SDValue ExtLoad = DAG.getExtLoad(LN0->getExtensionType(), VT, 3180 LN0->getChain(), LN0->getBasePtr(), 3181 LN0->getSrcValue(), 3182 LN0->getSrcValueOffset(), EVT, 3183 LN0->isVolatile(), LN0->getAlignment()); 3184 CombineTo(N, ExtLoad); 3185 CombineTo(N0.getNode(), 3186 DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 3187 ExtLoad.getValue(1)); 3188 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3189 } 3190 3191 // aext(setcc x,y,cc) -> select_cc x, y, 1, 0, cc 3192 if (N0.getOpcode() == ISD::SETCC) { 3193 SDValue SCC = 3194 SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), 3195 DAG.getConstant(1, VT), DAG.getConstant(0, VT), 3196 cast<CondCodeSDNode>(N0.getOperand(2))->get(), true); 3197 if (SCC.getNode()) 3198 return SCC; 3199 } 3200 3201 return SDValue(); 3202} 3203 3204/// GetDemandedBits - See if the specified operand can be simplified with the 3205/// knowledge that only the bits specified by Mask are used. If so, return the 3206/// simpler operand, otherwise return a null SDValue. 3207SDValue DAGCombiner::GetDemandedBits(SDValue V, const APInt &Mask) { 3208 switch (V.getOpcode()) { 3209 default: break; 3210 case ISD::OR: 3211 case ISD::XOR: 3212 // If the LHS or RHS don't contribute bits to the or, drop them. 3213 if (DAG.MaskedValueIsZero(V.getOperand(0), Mask)) 3214 return V.getOperand(1); 3215 if (DAG.MaskedValueIsZero(V.getOperand(1), Mask)) 3216 return V.getOperand(0); 3217 break; 3218 case ISD::SRL: 3219 // Only look at single-use SRLs. 3220 if (!V.getNode()->hasOneUse()) 3221 break; 3222 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(V.getOperand(1))) { 3223 // See if we can recursively simplify the LHS. 3224 unsigned Amt = RHSC->getZExtValue(); 3225 APInt NewMask = Mask << Amt; 3226 SDValue SimplifyLHS = GetDemandedBits(V.getOperand(0), NewMask); 3227 if (SimplifyLHS.getNode()) { 3228 return DAG.getNode(ISD::SRL, V.getValueType(), 3229 SimplifyLHS, V.getOperand(1)); 3230 } 3231 } 3232 } 3233 return SDValue(); 3234} 3235 3236/// ReduceLoadWidth - If the result of a wider load is shifted to right of N 3237/// bits and then truncated to a narrower type and where N is a multiple 3238/// of number of bits of the narrower type, transform it to a narrower load 3239/// from address + N / num of bits of new type. If the result is to be 3240/// extended, also fold the extension to form a extending load. 3241SDValue DAGCombiner::ReduceLoadWidth(SDNode *N) { 3242 unsigned Opc = N->getOpcode(); 3243 ISD::LoadExtType ExtType = ISD::NON_EXTLOAD; 3244 SDValue N0 = N->getOperand(0); 3245 MVT VT = N->getValueType(0); 3246 MVT EVT = N->getValueType(0); 3247 3248 // This transformation isn't valid for vector loads. 3249 if (VT.isVector()) 3250 return SDValue(); 3251 3252 // Special case: SIGN_EXTEND_INREG is basically truncating to EVT then 3253 // extended to VT. 3254 if (Opc == ISD::SIGN_EXTEND_INREG) { 3255 ExtType = ISD::SEXTLOAD; 3256 EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 3257 if (LegalOperations && !TLI.isLoadExtLegal(ISD::SEXTLOAD, EVT)) 3258 return SDValue(); 3259 } 3260 3261 unsigned EVTBits = EVT.getSizeInBits(); 3262 unsigned ShAmt = 0; 3263 bool CombineSRL = false; 3264 if (N0.getOpcode() == ISD::SRL && N0.hasOneUse()) { 3265 if (ConstantSDNode *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 3266 ShAmt = N01->getZExtValue(); 3267 // Is the shift amount a multiple of size of VT? 3268 if ((ShAmt & (EVTBits-1)) == 0) { 3269 N0 = N0.getOperand(0); 3270 if (N0.getValueType().getSizeInBits() <= EVTBits) 3271 return SDValue(); 3272 CombineSRL = true; 3273 } 3274 } 3275 } 3276 3277 // Do not generate loads of non-round integer types since these can 3278 // be expensive (and would be wrong if the type is not byte sized). 3279 if (isa<LoadSDNode>(N0) && N0.hasOneUse() && VT.isRound() && 3280 cast<LoadSDNode>(N0)->getMemoryVT().getSizeInBits() > EVTBits && 3281 // Do not change the width of a volatile load. 3282 !cast<LoadSDNode>(N0)->isVolatile()) { 3283 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3284 MVT PtrType = N0.getOperand(1).getValueType(); 3285 // For big endian targets, we need to adjust the offset to the pointer to 3286 // load the correct bytes. 3287 if (TLI.isBigEndian()) { 3288 unsigned LVTStoreBits = LN0->getMemoryVT().getStoreSizeInBits(); 3289 unsigned EVTStoreBits = EVT.getStoreSizeInBits(); 3290 ShAmt = LVTStoreBits - EVTStoreBits - ShAmt; 3291 } 3292 uint64_t PtrOff = ShAmt / 8; 3293 unsigned NewAlign = MinAlign(LN0->getAlignment(), PtrOff); 3294 SDValue NewPtr = DAG.getNode(ISD::ADD, PtrType, LN0->getBasePtr(), 3295 DAG.getConstant(PtrOff, PtrType)); 3296 AddToWorkList(NewPtr.getNode()); 3297 SDValue Load = (ExtType == ISD::NON_EXTLOAD) 3298 ? DAG.getLoad(VT, LN0->getChain(), NewPtr, 3299 LN0->getSrcValue(), LN0->getSrcValueOffset() + PtrOff, 3300 LN0->isVolatile(), NewAlign) 3301 : DAG.getExtLoad(ExtType, VT, LN0->getChain(), NewPtr, 3302 LN0->getSrcValue(), LN0->getSrcValueOffset() + PtrOff, 3303 EVT, LN0->isVolatile(), NewAlign); 3304 AddToWorkList(N); 3305 if (CombineSRL) { 3306 WorkListRemover DeadNodes(*this); 3307 DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1), 3308 &DeadNodes); 3309 CombineTo(N->getOperand(0).getNode(), Load); 3310 } else 3311 CombineTo(N0.getNode(), Load, Load.getValue(1)); 3312 if (ShAmt) { 3313 if (Opc == ISD::SIGN_EXTEND_INREG) 3314 return DAG.getNode(Opc, VT, Load, N->getOperand(1)); 3315 else 3316 return DAG.getNode(Opc, VT, Load); 3317 } 3318 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3319 } 3320 3321 return SDValue(); 3322} 3323 3324 3325SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 3326 SDValue N0 = N->getOperand(0); 3327 SDValue N1 = N->getOperand(1); 3328 MVT VT = N->getValueType(0); 3329 MVT EVT = cast<VTSDNode>(N1)->getVT(); 3330 unsigned VTBits = VT.getSizeInBits(); 3331 unsigned EVTBits = EVT.getSizeInBits(); 3332 3333 // fold (sext_in_reg c1) -> c1 3334 if (isa<ConstantSDNode>(N0) || N0.getOpcode() == ISD::UNDEF) 3335 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1); 3336 3337 // If the input is already sign extended, just drop the extension. 3338 if (DAG.ComputeNumSignBits(N0) >= VT.getSizeInBits()-EVTBits+1) 3339 return N0; 3340 3341 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 3342 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 3343 EVT.bitsLT(cast<VTSDNode>(N0.getOperand(1))->getVT())) { 3344 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 3345 } 3346 3347 // fold (sext_in_reg (sext x)) -> (sext x) 3348 // fold (sext_in_reg (aext x)) -> (sext x) 3349 // if x is small enough. 3350 if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND) { 3351 SDValue N00 = N0.getOperand(0); 3352 if (N00.getValueType().getSizeInBits() < EVTBits) 3353 return DAG.getNode(ISD::SIGN_EXTEND, VT, N00, N1); 3354 } 3355 3356 // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is known zero. 3357 if (DAG.MaskedValueIsZero(N0, APInt::getBitsSet(VTBits, EVTBits-1, EVTBits))) 3358 return DAG.getZeroExtendInReg(N0, EVT); 3359 3360 // fold operands of sext_in_reg based on knowledge that the top bits are not 3361 // demanded. 3362 if (SimplifyDemandedBits(SDValue(N, 0))) 3363 return SDValue(N, 0); 3364 3365 // fold (sext_in_reg (load x)) -> (smaller sextload x) 3366 // fold (sext_in_reg (srl (load x), c)) -> (smaller sextload (x+c/evtbits)) 3367 SDValue NarrowLoad = ReduceLoadWidth(N); 3368 if (NarrowLoad.getNode()) 3369 return NarrowLoad; 3370 3371 // fold (sext_in_reg (srl X, 24), i8) -> sra X, 24 3372 // fold (sext_in_reg (srl X, 23), i8) -> sra X, 23 iff possible. 3373 // We already fold "(sext_in_reg (srl X, 25), i8) -> srl X, 25" above. 3374 if (N0.getOpcode() == ISD::SRL) { 3375 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 3376 if (ShAmt->getZExtValue()+EVTBits <= VT.getSizeInBits()) { 3377 // We can turn this into an SRA iff the input to the SRL is already sign 3378 // extended enough. 3379 unsigned InSignBits = DAG.ComputeNumSignBits(N0.getOperand(0)); 3380 if (VT.getSizeInBits()-(ShAmt->getZExtValue()+EVTBits) < InSignBits) 3381 return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1)); 3382 } 3383 } 3384 3385 // fold (sext_inreg (extload x)) -> (sextload x) 3386 if (ISD::isEXTLoad(N0.getNode()) && 3387 ISD::isUNINDEXEDLoad(N0.getNode()) && 3388 EVT == cast<LoadSDNode>(N0)->getMemoryVT() && 3389 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 3390 TLI.isLoadExtLegal(ISD::SEXTLOAD, EVT))) { 3391 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3392 SDValue ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 3393 LN0->getBasePtr(), LN0->getSrcValue(), 3394 LN0->getSrcValueOffset(), EVT, 3395 LN0->isVolatile(), LN0->getAlignment()); 3396 CombineTo(N, ExtLoad); 3397 CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1)); 3398 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3399 } 3400 // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use 3401 if (ISD::isZEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) && 3402 N0.hasOneUse() && 3403 EVT == cast<LoadSDNode>(N0)->getMemoryVT() && 3404 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 3405 TLI.isLoadExtLegal(ISD::SEXTLOAD, EVT))) { 3406 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3407 SDValue ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(), 3408 LN0->getBasePtr(), LN0->getSrcValue(), 3409 LN0->getSrcValueOffset(), EVT, 3410 LN0->isVolatile(), LN0->getAlignment()); 3411 CombineTo(N, ExtLoad); 3412 CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1)); 3413 return SDValue(N, 0); // Return N so it doesn't get rechecked! 3414 } 3415 return SDValue(); 3416} 3417 3418SDValue DAGCombiner::visitTRUNCATE(SDNode *N) { 3419 SDValue N0 = N->getOperand(0); 3420 MVT VT = N->getValueType(0); 3421 3422 // noop truncate 3423 if (N0.getValueType() == N->getValueType(0)) 3424 return N0; 3425 // fold (truncate c1) -> c1 3426 if (isa<ConstantSDNode>(N0)) 3427 return DAG.getNode(ISD::TRUNCATE, VT, N0); 3428 // fold (truncate (truncate x)) -> (truncate x) 3429 if (N0.getOpcode() == ISD::TRUNCATE) 3430 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 3431 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 3432 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND|| 3433 N0.getOpcode() == ISD::ANY_EXTEND) { 3434 if (N0.getOperand(0).getValueType().bitsLT(VT)) 3435 // if the source is smaller than the dest, we still need an extend 3436 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 3437 else if (N0.getOperand(0).getValueType().bitsGT(VT)) 3438 // if the source is larger than the dest, than we just need the truncate 3439 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 3440 else 3441 // if the source and dest are the same type, we can drop both the extend 3442 // and the truncate 3443 return N0.getOperand(0); 3444 } 3445 3446 // See if we can simplify the input to this truncate through knowledge that 3447 // only the low bits are being used. For example "trunc (or (shl x, 8), y)" 3448 // -> trunc y 3449 SDValue Shorter = 3450 GetDemandedBits(N0, APInt::getLowBitsSet(N0.getValueSizeInBits(), 3451 VT.getSizeInBits())); 3452 if (Shorter.getNode()) 3453 return DAG.getNode(ISD::TRUNCATE, VT, Shorter); 3454 3455 // fold (truncate (load x)) -> (smaller load x) 3456 // fold (truncate (srl (load x), c)) -> (smaller load (x+c/evtbits)) 3457 return ReduceLoadWidth(N); 3458} 3459 3460static SDNode *getBuildPairElt(SDNode *N, unsigned i) { 3461 SDValue Elt = N->getOperand(i); 3462 if (Elt.getOpcode() != ISD::MERGE_VALUES) 3463 return Elt.getNode(); 3464 return Elt.getOperand(Elt.getResNo()).getNode(); 3465} 3466 3467/// CombineConsecutiveLoads - build_pair (load, load) -> load 3468/// if load locations are consecutive. 3469SDValue DAGCombiner::CombineConsecutiveLoads(SDNode *N, MVT VT) { 3470 assert(N->getOpcode() == ISD::BUILD_PAIR); 3471 3472 SDNode *LD1 = getBuildPairElt(N, 0); 3473 if (!ISD::isNON_EXTLoad(LD1) || !LD1->hasOneUse()) 3474 return SDValue(); 3475 MVT LD1VT = LD1->getValueType(0); 3476 SDNode *LD2 = getBuildPairElt(N, 1); 3477 const MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo(); 3478 if (ISD::isNON_EXTLoad(LD2) && 3479 LD2->hasOneUse() && 3480 // If both are volatile this would reduce the number of volatile loads. 3481 // If one is volatile it might be ok, but play conservative and bail out. 3482 !cast<LoadSDNode>(LD1)->isVolatile() && 3483 !cast<LoadSDNode>(LD2)->isVolatile() && 3484 TLI.isConsecutiveLoad(LD2, LD1, LD1VT.getSizeInBits()/8, 1, MFI)) { 3485 LoadSDNode *LD = cast<LoadSDNode>(LD1); 3486 unsigned Align = LD->getAlignment(); 3487 unsigned NewAlign = TLI.getTargetData()-> 3488 getABITypeAlignment(VT.getTypeForMVT()); 3489 if (NewAlign <= Align && 3490 (!LegalOperations || TLI.isOperationLegal(ISD::LOAD, VT))) 3491 return DAG.getLoad(VT, LD->getChain(), LD->getBasePtr(), 3492 LD->getSrcValue(), LD->getSrcValueOffset(), 3493 false, Align); 3494 } 3495 return SDValue(); 3496} 3497 3498SDValue DAGCombiner::visitBIT_CONVERT(SDNode *N) { 3499 SDValue N0 = N->getOperand(0); 3500 MVT VT = N->getValueType(0); 3501 3502 // If the input is a BUILD_VECTOR with all constant elements, fold this now. 3503 // Only do this before legalize, since afterward the target may be depending 3504 // on the bitconvert. 3505 // First check to see if this is all constant. 3506 if (!LegalTypes && 3507 N0.getOpcode() == ISD::BUILD_VECTOR && N0.getNode()->hasOneUse() && 3508 VT.isVector()) { 3509 bool isSimple = true; 3510 for (unsigned i = 0, e = N0.getNumOperands(); i != e; ++i) 3511 if (N0.getOperand(i).getOpcode() != ISD::UNDEF && 3512 N0.getOperand(i).getOpcode() != ISD::Constant && 3513 N0.getOperand(i).getOpcode() != ISD::ConstantFP) { 3514 isSimple = false; 3515 break; 3516 } 3517 3518 MVT DestEltVT = N->getValueType(0).getVectorElementType(); 3519 assert(!DestEltVT.isVector() && 3520 "Element type of vector ValueType must not be vector!"); 3521 if (isSimple) { 3522 return ConstantFoldBIT_CONVERTofBUILD_VECTOR(N0.getNode(), DestEltVT); 3523 } 3524 } 3525 3526 // If the input is a constant, let getNode fold it. 3527 if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) { 3528 SDValue Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0); 3529 if (Res.getNode() != N) return Res; 3530 } 3531 3532 if (N0.getOpcode() == ISD::BIT_CONVERT) // conv(conv(x,t1),t2) -> conv(x,t2) 3533 return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 3534 3535 // fold (conv (load x)) -> (load (conv*)x) 3536 // If the resultant load doesn't need a higher alignment than the original! 3537 if (ISD::isNormalLoad(N0.getNode()) && N0.hasOneUse() && 3538 // Do not change the width of a volatile load. 3539 !cast<LoadSDNode>(N0)->isVolatile() && 3540 (!LegalOperations || TLI.isOperationLegal(ISD::LOAD, VT))) { 3541 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 3542 unsigned Align = TLI.getTargetData()-> 3543 getABITypeAlignment(VT.getTypeForMVT()); 3544 unsigned OrigAlign = LN0->getAlignment(); 3545 if (Align <= OrigAlign) { 3546 SDValue Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(), 3547 LN0->getSrcValue(), LN0->getSrcValueOffset(), 3548 LN0->isVolatile(), OrigAlign); 3549 AddToWorkList(N); 3550 CombineTo(N0.getNode(), 3551 DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load), 3552 Load.getValue(1)); 3553 return Load; 3554 } 3555 } 3556 3557 // Fold bitconvert(fneg(x)) -> xor(bitconvert(x), signbit) 3558 // Fold bitconvert(fabs(x)) -> and(bitconvert(x), ~signbit) 3559 // This often reduces constant pool loads. 3560 if ((N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FABS) && 3561 N0.getNode()->hasOneUse() && VT.isInteger() && !VT.isVector()) { 3562 SDValue NewConv = DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 3563 AddToWorkList(NewConv.getNode()); 3564 3565 APInt SignBit = APInt::getSignBit(VT.getSizeInBits()); 3566 if (N0.getOpcode() == ISD::FNEG) 3567 return DAG.getNode(ISD::XOR, VT, NewConv, DAG.getConstant(SignBit, VT)); 3568 assert(N0.getOpcode() == ISD::FABS); 3569 return DAG.getNode(ISD::AND, VT, NewConv, DAG.getConstant(~SignBit, VT)); 3570 } 3571 3572 // Fold bitconvert(fcopysign(cst, x)) -> bitconvert(x)&sign | cst&~sign' 3573 // Note that we don't handle copysign(x,cst) because this can always be folded 3574 // to an fneg or fabs. 3575 if (N0.getOpcode() == ISD::FCOPYSIGN && N0.getNode()->hasOneUse() && 3576 isa<ConstantFPSDNode>(N0.getOperand(0)) && 3577 VT.isInteger() && !VT.isVector()) { 3578 unsigned OrigXWidth = N0.getOperand(1).getValueType().getSizeInBits(); 3579 MVT IntXVT = MVT::getIntegerVT(OrigXWidth); 3580 if (TLI.isTypeLegal(IntXVT) || !LegalTypes) { 3581 SDValue X = DAG.getNode(ISD::BIT_CONVERT, IntXVT, N0.getOperand(1)); 3582 AddToWorkList(X.getNode()); 3583 3584 // If X has a different width than the result/lhs, sext it or truncate it. 3585 unsigned VTWidth = VT.getSizeInBits(); 3586 if (OrigXWidth < VTWidth) { 3587 X = DAG.getNode(ISD::SIGN_EXTEND, VT, X); 3588 AddToWorkList(X.getNode()); 3589 } else if (OrigXWidth > VTWidth) { 3590 // To get the sign bit in the right place, we have to shift it right 3591 // before truncating. 3592 X = DAG.getNode(ISD::SRL, X.getValueType(), X, 3593 DAG.getConstant(OrigXWidth-VTWidth, X.getValueType())); 3594 AddToWorkList(X.getNode()); 3595 X = DAG.getNode(ISD::TRUNCATE, VT, X); 3596 AddToWorkList(X.getNode()); 3597 } 3598 3599 APInt SignBit = APInt::getSignBit(VT.getSizeInBits()); 3600 X = DAG.getNode(ISD::AND, VT, X, DAG.getConstant(SignBit, VT)); 3601 AddToWorkList(X.getNode()); 3602 3603 SDValue Cst = DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 3604 Cst = DAG.getNode(ISD::AND, VT, Cst, DAG.getConstant(~SignBit, VT)); 3605 AddToWorkList(Cst.getNode()); 3606 3607 return DAG.getNode(ISD::OR, VT, X, Cst); 3608 } 3609 } 3610 3611 // bitconvert(build_pair(ld, ld)) -> ld iff load locations are consecutive. 3612 if (N0.getOpcode() == ISD::BUILD_PAIR) { 3613 SDValue CombineLD = CombineConsecutiveLoads(N0.getNode(), VT); 3614 if (CombineLD.getNode()) 3615 return CombineLD; 3616 } 3617 3618 return SDValue(); 3619} 3620 3621SDValue DAGCombiner::visitBUILD_PAIR(SDNode *N) { 3622 MVT VT = N->getValueType(0); 3623 return CombineConsecutiveLoads(N, VT); 3624} 3625 3626/// ConstantFoldBIT_CONVERTofBUILD_VECTOR - We know that BV is a build_vector 3627/// node with Constant, ConstantFP or Undef operands. DstEltVT indicates the 3628/// destination element value type. 3629SDValue DAGCombiner:: 3630ConstantFoldBIT_CONVERTofBUILD_VECTOR(SDNode *BV, MVT DstEltVT) { 3631 MVT SrcEltVT = BV->getOperand(0).getValueType(); 3632 3633 // If this is already the right type, we're done. 3634 if (SrcEltVT == DstEltVT) return SDValue(BV, 0); 3635 3636 unsigned SrcBitSize = SrcEltVT.getSizeInBits(); 3637 unsigned DstBitSize = DstEltVT.getSizeInBits(); 3638 3639 // If this is a conversion of N elements of one type to N elements of another 3640 // type, convert each element. This handles FP<->INT cases. 3641 if (SrcBitSize == DstBitSize) { 3642 SmallVector<SDValue, 8> Ops; 3643 for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) { 3644 Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i))); 3645 AddToWorkList(Ops.back().getNode()); 3646 } 3647 MVT VT = MVT::getVectorVT(DstEltVT, 3648 BV->getValueType(0).getVectorNumElements()); 3649 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 3650 } 3651 3652 // Otherwise, we're growing or shrinking the elements. To avoid having to 3653 // handle annoying details of growing/shrinking FP values, we convert them to 3654 // int first. 3655 if (SrcEltVT.isFloatingPoint()) { 3656 // Convert the input float vector to a int vector where the elements are the 3657 // same sizes. 3658 assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!"); 3659 MVT IntVT = MVT::getIntegerVT(SrcEltVT.getSizeInBits()); 3660 BV = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, IntVT).getNode(); 3661 SrcEltVT = IntVT; 3662 } 3663 3664 // Now we know the input is an integer vector. If the output is a FP type, 3665 // convert to integer first, then to FP of the right size. 3666 if (DstEltVT.isFloatingPoint()) { 3667 assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!"); 3668 MVT TmpVT = MVT::getIntegerVT(DstEltVT.getSizeInBits()); 3669 SDNode *Tmp = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, TmpVT).getNode(); 3670 3671 // Next, convert to FP elements of the same size. 3672 return ConstantFoldBIT_CONVERTofBUILD_VECTOR(Tmp, DstEltVT); 3673 } 3674 3675 // Okay, we know the src/dst types are both integers of differing types. 3676 // Handling growing first. 3677 assert(SrcEltVT.isInteger() && DstEltVT.isInteger()); 3678 if (SrcBitSize < DstBitSize) { 3679 unsigned NumInputsPerOutput = DstBitSize/SrcBitSize; 3680 3681 SmallVector<SDValue, 8> Ops; 3682 for (unsigned i = 0, e = BV->getNumOperands(); i != e; 3683 i += NumInputsPerOutput) { 3684 bool isLE = TLI.isLittleEndian(); 3685 APInt NewBits = APInt(DstBitSize, 0); 3686 bool EltIsUndef = true; 3687 for (unsigned j = 0; j != NumInputsPerOutput; ++j) { 3688 // Shift the previously computed bits over. 3689 NewBits <<= SrcBitSize; 3690 SDValue Op = BV->getOperand(i+ (isLE ? (NumInputsPerOutput-j-1) : j)); 3691 if (Op.getOpcode() == ISD::UNDEF) continue; 3692 EltIsUndef = false; 3693 3694 NewBits |= 3695 APInt(cast<ConstantSDNode>(Op)->getAPIntValue()).zext(DstBitSize); 3696 } 3697 3698 if (EltIsUndef) 3699 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 3700 else 3701 Ops.push_back(DAG.getConstant(NewBits, DstEltVT)); 3702 } 3703 3704 MVT VT = MVT::getVectorVT(DstEltVT, Ops.size()); 3705 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 3706 } 3707 3708 // Finally, this must be the case where we are shrinking elements: each input 3709 // turns into multiple outputs. 3710 bool isS2V = ISD::isScalarToVector(BV); 3711 unsigned NumOutputsPerInput = SrcBitSize/DstBitSize; 3712 MVT VT = MVT::getVectorVT(DstEltVT, NumOutputsPerInput*BV->getNumOperands()); 3713 SmallVector<SDValue, 8> Ops; 3714 for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) { 3715 if (BV->getOperand(i).getOpcode() == ISD::UNDEF) { 3716 for (unsigned j = 0; j != NumOutputsPerInput; ++j) 3717 Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT)); 3718 continue; 3719 } 3720 APInt OpVal = cast<ConstantSDNode>(BV->getOperand(i))->getAPIntValue(); 3721 for (unsigned j = 0; j != NumOutputsPerInput; ++j) { 3722 APInt ThisVal = APInt(OpVal).trunc(DstBitSize); 3723 Ops.push_back(DAG.getConstant(ThisVal, DstEltVT)); 3724 if (isS2V && i == 0 && j == 0 && APInt(ThisVal).zext(SrcBitSize) == OpVal) 3725 // Simply turn this into a SCALAR_TO_VECTOR of the new type. 3726 return DAG.getNode(ISD::SCALAR_TO_VECTOR, VT, Ops[0]); 3727 OpVal = OpVal.lshr(DstBitSize); 3728 } 3729 3730 // For big endian targets, swap the order of the pieces of each element. 3731 if (TLI.isBigEndian()) 3732 std::reverse(Ops.end()-NumOutputsPerInput, Ops.end()); 3733 } 3734 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 3735} 3736 3737 3738 3739SDValue DAGCombiner::visitFADD(SDNode *N) { 3740 SDValue N0 = N->getOperand(0); 3741 SDValue N1 = N->getOperand(1); 3742 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3743 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3744 MVT VT = N->getValueType(0); 3745 3746 // fold vector ops 3747 if (VT.isVector()) { 3748 SDValue FoldedVOp = SimplifyVBinOp(N); 3749 if (FoldedVOp.getNode()) return FoldedVOp; 3750 } 3751 3752 // fold (fadd c1, c2) -> c1+c2 3753 if (N0CFP && N1CFP && VT != MVT::ppcf128) 3754 return DAG.getNode(ISD::FADD, VT, N0, N1); 3755 // canonicalize constant to RHS 3756 if (N0CFP && !N1CFP) 3757 return DAG.getNode(ISD::FADD, VT, N1, N0); 3758 // fold (A + (-B)) -> A-B 3759 if (isNegatibleForFree(N1, LegalOperations) == 2) 3760 return DAG.getNode(ISD::FSUB, VT, N0, 3761 GetNegatedExpression(N1, DAG, LegalOperations)); 3762 // fold ((-A) + B) -> B-A 3763 if (isNegatibleForFree(N0, LegalOperations) == 2) 3764 return DAG.getNode(ISD::FSUB, VT, N1, 3765 GetNegatedExpression(N0, DAG, LegalOperations)); 3766 3767 // If allowed, fold (fadd (fadd x, c1), c2) -> (fadd x, (fadd c1, c2)) 3768 if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FADD && 3769 N0.getNode()->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1))) 3770 return DAG.getNode(ISD::FADD, VT, N0.getOperand(0), 3771 DAG.getNode(ISD::FADD, VT, N0.getOperand(1), N1)); 3772 3773 return SDValue(); 3774} 3775 3776SDValue DAGCombiner::visitFSUB(SDNode *N) { 3777 SDValue N0 = N->getOperand(0); 3778 SDValue N1 = N->getOperand(1); 3779 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3780 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3781 MVT VT = N->getValueType(0); 3782 3783 // fold vector ops 3784 if (VT.isVector()) { 3785 SDValue FoldedVOp = SimplifyVBinOp(N); 3786 if (FoldedVOp.getNode()) return FoldedVOp; 3787 } 3788 3789 // fold (fsub c1, c2) -> c1-c2 3790 if (N0CFP && N1CFP && VT != MVT::ppcf128) 3791 return DAG.getNode(ISD::FSUB, VT, N0, N1); 3792 // fold (0-B) -> -B 3793 if (UnsafeFPMath && N0CFP && N0CFP->getValueAPF().isZero()) { 3794 if (isNegatibleForFree(N1, LegalOperations)) 3795 return GetNegatedExpression(N1, DAG, LegalOperations); 3796 return DAG.getNode(ISD::FNEG, VT, N1); 3797 } 3798 // fold (A-(-B)) -> A+B 3799 if (isNegatibleForFree(N1, LegalOperations)) 3800 return DAG.getNode(ISD::FADD, VT, N0, 3801 GetNegatedExpression(N1, DAG, LegalOperations)); 3802 3803 return SDValue(); 3804} 3805 3806SDValue DAGCombiner::visitFMUL(SDNode *N) { 3807 SDValue N0 = N->getOperand(0); 3808 SDValue N1 = N->getOperand(1); 3809 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3810 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3811 MVT VT = N->getValueType(0); 3812 3813 // fold vector ops 3814 if (VT.isVector()) { 3815 SDValue FoldedVOp = SimplifyVBinOp(N); 3816 if (FoldedVOp.getNode()) return FoldedVOp; 3817 } 3818 3819 // fold (fmul c1, c2) -> c1*c2 3820 if (N0CFP && N1CFP && VT != MVT::ppcf128) 3821 return DAG.getNode(ISD::FMUL, VT, N0, N1); 3822 // canonicalize constant to RHS 3823 if (N0CFP && !N1CFP) 3824 return DAG.getNode(ISD::FMUL, VT, N1, N0); 3825 // fold (fmul X, 2.0) -> (fadd X, X) 3826 if (N1CFP && N1CFP->isExactlyValue(+2.0)) 3827 return DAG.getNode(ISD::FADD, VT, N0, N0); 3828 // fold (fmul X, -1.0) -> (fneg X) 3829 if (N1CFP && N1CFP->isExactlyValue(-1.0)) 3830 return DAG.getNode(ISD::FNEG, VT, N0); 3831 3832 // -X * -Y -> X*Y 3833 if (char LHSNeg = isNegatibleForFree(N0, LegalOperations)) { 3834 if (char RHSNeg = isNegatibleForFree(N1, LegalOperations)) { 3835 // Both can be negated for free, check to see if at least one is cheaper 3836 // negated. 3837 if (LHSNeg == 2 || RHSNeg == 2) 3838 return DAG.getNode(ISD::FMUL, VT, 3839 GetNegatedExpression(N0, DAG, LegalOperations), 3840 GetNegatedExpression(N1, DAG, LegalOperations)); 3841 } 3842 } 3843 3844 // If allowed, fold (fmul (fmul x, c1), c2) -> (fmul x, (fmul c1, c2)) 3845 if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FMUL && 3846 N0.getNode()->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1))) 3847 return DAG.getNode(ISD::FMUL, VT, N0.getOperand(0), 3848 DAG.getNode(ISD::FMUL, VT, N0.getOperand(1), N1)); 3849 3850 return SDValue(); 3851} 3852 3853SDValue DAGCombiner::visitFDIV(SDNode *N) { 3854 SDValue N0 = N->getOperand(0); 3855 SDValue N1 = N->getOperand(1); 3856 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3857 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3858 MVT VT = N->getValueType(0); 3859 3860 // fold vector ops 3861 if (VT.isVector()) { 3862 SDValue FoldedVOp = SimplifyVBinOp(N); 3863 if (FoldedVOp.getNode()) return FoldedVOp; 3864 } 3865 3866 // fold (fdiv c1, c2) -> c1/c2 3867 if (N0CFP && N1CFP && VT != MVT::ppcf128) 3868 return DAG.getNode(ISD::FDIV, VT, N0, N1); 3869 3870 3871 // -X / -Y -> X*Y 3872 if (char LHSNeg = isNegatibleForFree(N0, LegalOperations)) { 3873 if (char RHSNeg = isNegatibleForFree(N1, LegalOperations)) { 3874 // Both can be negated for free, check to see if at least one is cheaper 3875 // negated. 3876 if (LHSNeg == 2 || RHSNeg == 2) 3877 return DAG.getNode(ISD::FDIV, VT, 3878 GetNegatedExpression(N0, DAG, LegalOperations), 3879 GetNegatedExpression(N1, DAG, LegalOperations)); 3880 } 3881 } 3882 3883 return SDValue(); 3884} 3885 3886SDValue DAGCombiner::visitFREM(SDNode *N) { 3887 SDValue N0 = N->getOperand(0); 3888 SDValue N1 = N->getOperand(1); 3889 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3890 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3891 MVT VT = N->getValueType(0); 3892 3893 // fold (frem c1, c2) -> fmod(c1,c2) 3894 if (N0CFP && N1CFP && VT != MVT::ppcf128) 3895 return DAG.getNode(ISD::FREM, VT, N0, N1); 3896 3897 return SDValue(); 3898} 3899 3900SDValue DAGCombiner::visitFCOPYSIGN(SDNode *N) { 3901 SDValue N0 = N->getOperand(0); 3902 SDValue N1 = N->getOperand(1); 3903 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3904 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 3905 MVT VT = N->getValueType(0); 3906 3907 if (N0CFP && N1CFP && VT != MVT::ppcf128) // Constant fold 3908 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1); 3909 3910 if (N1CFP) { 3911 const APFloat& V = N1CFP->getValueAPF(); 3912 // copysign(x, c1) -> fabs(x) iff ispos(c1) 3913 // copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1) 3914 if (!V.isNegative()) 3915 return DAG.getNode(ISD::FABS, VT, N0); 3916 else 3917 return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0)); 3918 } 3919 3920 // copysign(fabs(x), y) -> copysign(x, y) 3921 // copysign(fneg(x), y) -> copysign(x, y) 3922 // copysign(copysign(x,z), y) -> copysign(x, y) 3923 if (N0.getOpcode() == ISD::FABS || N0.getOpcode() == ISD::FNEG || 3924 N0.getOpcode() == ISD::FCOPYSIGN) 3925 return DAG.getNode(ISD::FCOPYSIGN, VT, N0.getOperand(0), N1); 3926 3927 // copysign(x, abs(y)) -> abs(x) 3928 if (N1.getOpcode() == ISD::FABS) 3929 return DAG.getNode(ISD::FABS, VT, N0); 3930 3931 // copysign(x, copysign(y,z)) -> copysign(x, z) 3932 if (N1.getOpcode() == ISD::FCOPYSIGN) 3933 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(1)); 3934 3935 // copysign(x, fp_extend(y)) -> copysign(x, y) 3936 // copysign(x, fp_round(y)) -> copysign(x, y) 3937 if (N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND) 3938 return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(0)); 3939 3940 return SDValue(); 3941} 3942 3943 3944 3945SDValue DAGCombiner::visitSINT_TO_FP(SDNode *N) { 3946 SDValue N0 = N->getOperand(0); 3947 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 3948 MVT VT = N->getValueType(0); 3949 MVT OpVT = N0.getValueType(); 3950 3951 // fold (sint_to_fp c1) -> c1fp 3952 if (N0C && OpVT != MVT::ppcf128) 3953 return DAG.getNode(ISD::SINT_TO_FP, VT, N0); 3954 3955 // If the input is a legal type, and SINT_TO_FP is not legal on this target, 3956 // but UINT_TO_FP is legal on this target, try to convert. 3957 if (!TLI.isOperationLegal(ISD::SINT_TO_FP, OpVT) && 3958 TLI.isOperationLegal(ISD::UINT_TO_FP, OpVT)) { 3959 // If the sign bit is known to be zero, we can change this to UINT_TO_FP. 3960 if (DAG.SignBitIsZero(N0)) 3961 return DAG.getNode(ISD::UINT_TO_FP, VT, N0); 3962 } 3963 3964 3965 return SDValue(); 3966} 3967 3968SDValue DAGCombiner::visitUINT_TO_FP(SDNode *N) { 3969 SDValue N0 = N->getOperand(0); 3970 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 3971 MVT VT = N->getValueType(0); 3972 MVT OpVT = N0.getValueType(); 3973 3974 // fold (uint_to_fp c1) -> c1fp 3975 if (N0C && OpVT != MVT::ppcf128) 3976 return DAG.getNode(ISD::UINT_TO_FP, VT, N0); 3977 3978 // If the input is a legal type, and UINT_TO_FP is not legal on this target, 3979 // but SINT_TO_FP is legal on this target, try to convert. 3980 if (!TLI.isOperationLegal(ISD::UINT_TO_FP, OpVT) && 3981 TLI.isOperationLegal(ISD::SINT_TO_FP, OpVT)) { 3982 // If the sign bit is known to be zero, we can change this to SINT_TO_FP. 3983 if (DAG.SignBitIsZero(N0)) 3984 return DAG.getNode(ISD::SINT_TO_FP, VT, N0); 3985 } 3986 3987 return SDValue(); 3988} 3989 3990SDValue DAGCombiner::visitFP_TO_SINT(SDNode *N) { 3991 SDValue N0 = N->getOperand(0); 3992 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 3993 MVT VT = N->getValueType(0); 3994 3995 // fold (fp_to_sint c1fp) -> c1 3996 if (N0CFP) 3997 return DAG.getNode(ISD::FP_TO_SINT, VT, N0); 3998 return SDValue(); 3999} 4000 4001SDValue DAGCombiner::visitFP_TO_UINT(SDNode *N) { 4002 SDValue N0 = N->getOperand(0); 4003 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 4004 MVT VT = N->getValueType(0); 4005 4006 // fold (fp_to_uint c1fp) -> c1 4007 if (N0CFP && VT != MVT::ppcf128) 4008 return DAG.getNode(ISD::FP_TO_UINT, VT, N0); 4009 return SDValue(); 4010} 4011 4012SDValue DAGCombiner::visitFP_ROUND(SDNode *N) { 4013 SDValue N0 = N->getOperand(0); 4014 SDValue N1 = N->getOperand(1); 4015 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 4016 MVT VT = N->getValueType(0); 4017 4018 // fold (fp_round c1fp) -> c1fp 4019 if (N0CFP && N0.getValueType() != MVT::ppcf128) 4020 return DAG.getNode(ISD::FP_ROUND, VT, N0, N1); 4021 4022 // fold (fp_round (fp_extend x)) -> x 4023 if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType()) 4024 return N0.getOperand(0); 4025 4026 // fold (fp_round (fp_round x)) -> (fp_round x) 4027 if (N0.getOpcode() == ISD::FP_ROUND) { 4028 // This is a value preserving truncation if both round's are. 4029 bool IsTrunc = N->getConstantOperandVal(1) == 1 && 4030 N0.getNode()->getConstantOperandVal(1) == 1; 4031 return DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0), 4032 DAG.getIntPtrConstant(IsTrunc)); 4033 } 4034 4035 // fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y) 4036 if (N0.getOpcode() == ISD::FCOPYSIGN && N0.getNode()->hasOneUse()) { 4037 SDValue Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0), N1); 4038 AddToWorkList(Tmp.getNode()); 4039 return DAG.getNode(ISD::FCOPYSIGN, VT, Tmp, N0.getOperand(1)); 4040 } 4041 4042 return SDValue(); 4043} 4044 4045SDValue DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 4046 SDValue N0 = N->getOperand(0); 4047 MVT VT = N->getValueType(0); 4048 MVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 4049 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 4050 4051 // fold (fp_round_inreg c1fp) -> c1fp 4052 if (N0CFP && (TLI.isTypeLegal(EVT) || !LegalTypes)) { 4053 SDValue Round = DAG.getConstantFP(*N0CFP->getConstantFPValue(), EVT); 4054 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 4055 } 4056 return SDValue(); 4057} 4058 4059SDValue DAGCombiner::visitFP_EXTEND(SDNode *N) { 4060 SDValue N0 = N->getOperand(0); 4061 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 4062 MVT VT = N->getValueType(0); 4063 4064 // If this is fp_round(fpextend), don't fold it, allow ourselves to be folded. 4065 if (N->hasOneUse() && 4066 N->use_begin().getUse().getSDValue().getOpcode() == ISD::FP_ROUND) 4067 return SDValue(); 4068 4069 // fold (fp_extend c1fp) -> c1fp 4070 if (N0CFP && VT != MVT::ppcf128) 4071 return DAG.getNode(ISD::FP_EXTEND, VT, N0); 4072 4073 // Turn fp_extend(fp_round(X, 1)) -> x since the fp_round doesn't affect the 4074 // value of X. 4075 if (N0.getOpcode() == ISD::FP_ROUND 4076 && N0.getNode()->getConstantOperandVal(1) == 1) { 4077 SDValue In = N0.getOperand(0); 4078 if (In.getValueType() == VT) return In; 4079 if (VT.bitsLT(In.getValueType())) 4080 return DAG.getNode(ISD::FP_ROUND, VT, In, N0.getOperand(1)); 4081 return DAG.getNode(ISD::FP_EXTEND, VT, In); 4082 } 4083 4084 // fold (fpext (load x)) -> (fpext (fptrunc (extload x))) 4085 if (ISD::isNON_EXTLoad(N0.getNode()) && N0.hasOneUse() && 4086 ((!LegalOperations && !cast<LoadSDNode>(N0)->isVolatile()) || 4087 TLI.isLoadExtLegal(ISD::EXTLOAD, N0.getValueType()))) { 4088 LoadSDNode *LN0 = cast<LoadSDNode>(N0); 4089 SDValue ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(), 4090 LN0->getBasePtr(), LN0->getSrcValue(), 4091 LN0->getSrcValueOffset(), 4092 N0.getValueType(), 4093 LN0->isVolatile(), LN0->getAlignment()); 4094 CombineTo(N, ExtLoad); 4095 CombineTo(N0.getNode(), DAG.getNode(ISD::FP_ROUND, N0.getValueType(), 4096 ExtLoad, DAG.getIntPtrConstant(1)), 4097 ExtLoad.getValue(1)); 4098 return SDValue(N, 0); // Return N so it doesn't get rechecked! 4099 } 4100 4101 return SDValue(); 4102} 4103 4104SDValue DAGCombiner::visitFNEG(SDNode *N) { 4105 SDValue N0 = N->getOperand(0); 4106 4107 if (isNegatibleForFree(N0, LegalOperations)) 4108 return GetNegatedExpression(N0, DAG, LegalOperations); 4109 4110 // Transform fneg(bitconvert(x)) -> bitconvert(x^sign) to avoid loading 4111 // constant pool values. 4112 if (N0.getOpcode() == ISD::BIT_CONVERT && N0.getNode()->hasOneUse() && 4113 N0.getOperand(0).getValueType().isInteger() && 4114 !N0.getOperand(0).getValueType().isVector()) { 4115 SDValue Int = N0.getOperand(0); 4116 MVT IntVT = Int.getValueType(); 4117 if (IntVT.isInteger() && !IntVT.isVector()) { 4118 Int = DAG.getNode(ISD::XOR, IntVT, Int, 4119 DAG.getConstant(IntVT.getIntegerVTSignBit(), IntVT)); 4120 AddToWorkList(Int.getNode()); 4121 return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0), Int); 4122 } 4123 } 4124 4125 return SDValue(); 4126} 4127 4128SDValue DAGCombiner::visitFABS(SDNode *N) { 4129 SDValue N0 = N->getOperand(0); 4130 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 4131 MVT VT = N->getValueType(0); 4132 4133 // fold (fabs c1) -> fabs(c1) 4134 if (N0CFP && VT != MVT::ppcf128) 4135 return DAG.getNode(ISD::FABS, VT, N0); 4136 // fold (fabs (fabs x)) -> (fabs x) 4137 if (N0.getOpcode() == ISD::FABS) 4138 return N->getOperand(0); 4139 // fold (fabs (fneg x)) -> (fabs x) 4140 // fold (fabs (fcopysign x, y)) -> (fabs x) 4141 if (N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FCOPYSIGN) 4142 return DAG.getNode(ISD::FABS, VT, N0.getOperand(0)); 4143 4144 // Transform fabs(bitconvert(x)) -> bitconvert(x&~sign) to avoid loading 4145 // constant pool values. 4146 if (N0.getOpcode() == ISD::BIT_CONVERT && N0.getNode()->hasOneUse() && 4147 N0.getOperand(0).getValueType().isInteger() && 4148 !N0.getOperand(0).getValueType().isVector()) { 4149 SDValue Int = N0.getOperand(0); 4150 MVT IntVT = Int.getValueType(); 4151 if (IntVT.isInteger() && !IntVT.isVector()) { 4152 Int = DAG.getNode(ISD::AND, IntVT, Int, 4153 DAG.getConstant(~IntVT.getIntegerVTSignBit(), IntVT)); 4154 AddToWorkList(Int.getNode()); 4155 return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0), Int); 4156 } 4157 } 4158 4159 return SDValue(); 4160} 4161 4162SDValue DAGCombiner::visitBRCOND(SDNode *N) { 4163 SDValue Chain = N->getOperand(0); 4164 SDValue N1 = N->getOperand(1); 4165 SDValue N2 = N->getOperand(2); 4166 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 4167 4168 // never taken branch, fold to chain 4169 if (N1C && N1C->isNullValue()) 4170 return Chain; 4171 // unconditional branch 4172 if (N1C && N1C->getAPIntValue() == 1) 4173 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 4174 // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal 4175 // on the target. 4176 if (N1.getOpcode() == ISD::SETCC && 4177 TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) { 4178 return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2), 4179 N1.getOperand(0), N1.getOperand(1), N2); 4180 } 4181 return SDValue(); 4182} 4183 4184// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 4185// 4186SDValue DAGCombiner::visitBR_CC(SDNode *N) { 4187 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 4188 SDValue CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 4189 4190 // Use SimplifySetCC to simplify SETCC's. 4191 SDValue Simp = SimplifySetCC(TLI.getSetCCResultType(CondLHS), 4192 CondLHS, CondRHS, CC->get(), false); 4193 if (Simp.getNode()) AddToWorkList(Simp.getNode()); 4194 4195 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.getNode()); 4196 4197 // fold br_cc true, dest -> br dest (unconditional branch) 4198 if (SCCC && !SCCC->isNullValue()) 4199 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 4200 N->getOperand(4)); 4201 // fold br_cc false, dest -> unconditional fall through 4202 if (SCCC && SCCC->isNullValue()) 4203 return N->getOperand(0); 4204 4205 // fold to a simpler setcc 4206 if (Simp.getNode() && Simp.getOpcode() == ISD::SETCC) 4207 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 4208 Simp.getOperand(2), Simp.getOperand(0), 4209 Simp.getOperand(1), N->getOperand(4)); 4210 return SDValue(); 4211} 4212 4213 4214/// CombineToPreIndexedLoadStore - Try turning a load / store into a 4215/// pre-indexed load / store when the base pointer is an add or subtract 4216/// and it has other uses besides the load / store. After the 4217/// transformation, the new indexed load / store has effectively folded 4218/// the add / subtract in and all of its other uses are redirected to the 4219/// new load / store. 4220bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { 4221 if (!LegalOperations) 4222 return false; 4223 4224 bool isLoad = true; 4225 SDValue Ptr; 4226 MVT VT; 4227 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 4228 if (LD->isIndexed()) 4229 return false; 4230 VT = LD->getMemoryVT(); 4231 if (!TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) && 4232 !TLI.isIndexedLoadLegal(ISD::PRE_DEC, VT)) 4233 return false; 4234 Ptr = LD->getBasePtr(); 4235 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 4236 if (ST->isIndexed()) 4237 return false; 4238 VT = ST->getMemoryVT(); 4239 if (!TLI.isIndexedStoreLegal(ISD::PRE_INC, VT) && 4240 !TLI.isIndexedStoreLegal(ISD::PRE_DEC, VT)) 4241 return false; 4242 Ptr = ST->getBasePtr(); 4243 isLoad = false; 4244 } else 4245 return false; 4246 4247 // If the pointer is not an add/sub, or if it doesn't have multiple uses, bail 4248 // out. There is no reason to make this a preinc/predec. 4249 if ((Ptr.getOpcode() != ISD::ADD && Ptr.getOpcode() != ISD::SUB) || 4250 Ptr.getNode()->hasOneUse()) 4251 return false; 4252 4253 // Ask the target to do addressing mode selection. 4254 SDValue BasePtr; 4255 SDValue Offset; 4256 ISD::MemIndexedMode AM = ISD::UNINDEXED; 4257 if (!TLI.getPreIndexedAddressParts(N, BasePtr, Offset, AM, DAG)) 4258 return false; 4259 // Don't create a indexed load / store with zero offset. 4260 if (isa<ConstantSDNode>(Offset) && 4261 cast<ConstantSDNode>(Offset)->isNullValue()) 4262 return false; 4263 4264 // Try turning it into a pre-indexed load / store except when: 4265 // 1) The new base ptr is a frame index. 4266 // 2) If N is a store and the new base ptr is either the same as or is a 4267 // predecessor of the value being stored. 4268 // 3) Another use of old base ptr is a predecessor of N. If ptr is folded 4269 // that would create a cycle. 4270 // 4) All uses are load / store ops that use it as old base ptr. 4271 4272 // Check #1. Preinc'ing a frame index would require copying the stack pointer 4273 // (plus the implicit offset) to a register to preinc anyway. 4274 if (isa<FrameIndexSDNode>(BasePtr)) 4275 return false; 4276 4277 // Check #2. 4278 if (!isLoad) { 4279 SDValue Val = cast<StoreSDNode>(N)->getValue(); 4280 if (Val == BasePtr || BasePtr.getNode()->isPredecessorOf(Val.getNode())) 4281 return false; 4282 } 4283 4284 // Now check for #3 and #4. 4285 bool RealUse = false; 4286 for (SDNode::use_iterator I = Ptr.getNode()->use_begin(), 4287 E = Ptr.getNode()->use_end(); I != E; ++I) { 4288 SDNode *Use = *I; 4289 if (Use == N) 4290 continue; 4291 if (Use->isPredecessorOf(N)) 4292 return false; 4293 4294 if (!((Use->getOpcode() == ISD::LOAD && 4295 cast<LoadSDNode>(Use)->getBasePtr() == Ptr) || 4296 (Use->getOpcode() == ISD::STORE && 4297 cast<StoreSDNode>(Use)->getBasePtr() == Ptr))) 4298 RealUse = true; 4299 } 4300 if (!RealUse) 4301 return false; 4302 4303 SDValue Result; 4304 if (isLoad) 4305 Result = DAG.getIndexedLoad(SDValue(N,0), BasePtr, Offset, AM); 4306 else 4307 Result = DAG.getIndexedStore(SDValue(N,0), BasePtr, Offset, AM); 4308 ++PreIndexedNodes; 4309 ++NodesCombined; 4310 DOUT << "\nReplacing.4 "; DEBUG(N->dump(&DAG)); 4311 DOUT << "\nWith: "; DEBUG(Result.getNode()->dump(&DAG)); 4312 DOUT << '\n'; 4313 WorkListRemover DeadNodes(*this); 4314 if (isLoad) { 4315 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(0), 4316 &DeadNodes); 4317 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), Result.getValue(2), 4318 &DeadNodes); 4319 } else { 4320 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(1), 4321 &DeadNodes); 4322 } 4323 4324 // Finally, since the node is now dead, remove it from the graph. 4325 DAG.DeleteNode(N); 4326 4327 // Replace the uses of Ptr with uses of the updated base value. 4328 DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0), 4329 &DeadNodes); 4330 removeFromWorkList(Ptr.getNode()); 4331 DAG.DeleteNode(Ptr.getNode()); 4332 4333 return true; 4334} 4335 4336/// CombineToPostIndexedLoadStore - Try to combine a load / store with a 4337/// add / sub of the base pointer node into a post-indexed load / store. 4338/// The transformation folded the add / subtract into the new indexed 4339/// load / store effectively and all of its uses are redirected to the 4340/// new load / store. 4341bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) { 4342 if (!LegalOperations) 4343 return false; 4344 4345 bool isLoad = true; 4346 SDValue Ptr; 4347 MVT VT; 4348 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 4349 if (LD->isIndexed()) 4350 return false; 4351 VT = LD->getMemoryVT(); 4352 if (!TLI.isIndexedLoadLegal(ISD::POST_INC, VT) && 4353 !TLI.isIndexedLoadLegal(ISD::POST_DEC, VT)) 4354 return false; 4355 Ptr = LD->getBasePtr(); 4356 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 4357 if (ST->isIndexed()) 4358 return false; 4359 VT = ST->getMemoryVT(); 4360 if (!TLI.isIndexedStoreLegal(ISD::POST_INC, VT) && 4361 !TLI.isIndexedStoreLegal(ISD::POST_DEC, VT)) 4362 return false; 4363 Ptr = ST->getBasePtr(); 4364 isLoad = false; 4365 } else 4366 return false; 4367 4368 if (Ptr.getNode()->hasOneUse()) 4369 return false; 4370 4371 for (SDNode::use_iterator I = Ptr.getNode()->use_begin(), 4372 E = Ptr.getNode()->use_end(); I != E; ++I) { 4373 SDNode *Op = *I; 4374 if (Op == N || 4375 (Op->getOpcode() != ISD::ADD && Op->getOpcode() != ISD::SUB)) 4376 continue; 4377 4378 SDValue BasePtr; 4379 SDValue Offset; 4380 ISD::MemIndexedMode AM = ISD::UNINDEXED; 4381 if (TLI.getPostIndexedAddressParts(N, Op, BasePtr, Offset, AM, DAG)) { 4382 if (Ptr == Offset) 4383 std::swap(BasePtr, Offset); 4384 if (Ptr != BasePtr) 4385 continue; 4386 // Don't create a indexed load / store with zero offset. 4387 if (isa<ConstantSDNode>(Offset) && 4388 cast<ConstantSDNode>(Offset)->isNullValue()) 4389 continue; 4390 4391 // Try turning it into a post-indexed load / store except when 4392 // 1) All uses are load / store ops that use it as base ptr. 4393 // 2) Op must be independent of N, i.e. Op is neither a predecessor 4394 // nor a successor of N. Otherwise, if Op is folded that would 4395 // create a cycle. 4396 4397 // Check for #1. 4398 bool TryNext = false; 4399 for (SDNode::use_iterator II = BasePtr.getNode()->use_begin(), 4400 EE = BasePtr.getNode()->use_end(); II != EE; ++II) { 4401 SDNode *Use = *II; 4402 if (Use == Ptr.getNode()) 4403 continue; 4404 4405 // If all the uses are load / store addresses, then don't do the 4406 // transformation. 4407 if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB){ 4408 bool RealUse = false; 4409 for (SDNode::use_iterator III = Use->use_begin(), 4410 EEE = Use->use_end(); III != EEE; ++III) { 4411 SDNode *UseUse = *III; 4412 if (!((UseUse->getOpcode() == ISD::LOAD && 4413 cast<LoadSDNode>(UseUse)->getBasePtr().getNode() == Use) || 4414 (UseUse->getOpcode() == ISD::STORE && 4415 cast<StoreSDNode>(UseUse)->getBasePtr().getNode() == Use))) 4416 RealUse = true; 4417 } 4418 4419 if (!RealUse) { 4420 TryNext = true; 4421 break; 4422 } 4423 } 4424 } 4425 if (TryNext) 4426 continue; 4427 4428 // Check for #2 4429 if (!Op->isPredecessorOf(N) && !N->isPredecessorOf(Op)) { 4430 SDValue Result = isLoad 4431 ? DAG.getIndexedLoad(SDValue(N,0), BasePtr, Offset, AM) 4432 : DAG.getIndexedStore(SDValue(N,0), BasePtr, Offset, AM); 4433 ++PostIndexedNodes; 4434 ++NodesCombined; 4435 DOUT << "\nReplacing.5 "; DEBUG(N->dump(&DAG)); 4436 DOUT << "\nWith: "; DEBUG(Result.getNode()->dump(&DAG)); 4437 DOUT << '\n'; 4438 WorkListRemover DeadNodes(*this); 4439 if (isLoad) { 4440 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(0), 4441 &DeadNodes); 4442 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), Result.getValue(2), 4443 &DeadNodes); 4444 } else { 4445 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(1), 4446 &DeadNodes); 4447 } 4448 4449 // Finally, since the node is now dead, remove it from the graph. 4450 DAG.DeleteNode(N); 4451 4452 // Replace the uses of Use with uses of the updated base value. 4453 DAG.ReplaceAllUsesOfValueWith(SDValue(Op, 0), 4454 Result.getValue(isLoad ? 1 : 0), 4455 &DeadNodes); 4456 removeFromWorkList(Op); 4457 DAG.DeleteNode(Op); 4458 return true; 4459 } 4460 } 4461 } 4462 return false; 4463} 4464 4465/// InferAlignment - If we can infer some alignment information from this 4466/// pointer, return it. 4467static unsigned InferAlignment(SDValue Ptr, SelectionDAG &DAG) { 4468 // If this is a direct reference to a stack slot, use information about the 4469 // stack slot's alignment. 4470 int FrameIdx = 1 << 31; 4471 int64_t FrameOffset = 0; 4472 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) { 4473 FrameIdx = FI->getIndex(); 4474 } else if (Ptr.getOpcode() == ISD::ADD && 4475 isa<ConstantSDNode>(Ptr.getOperand(1)) && 4476 isa<FrameIndexSDNode>(Ptr.getOperand(0))) { 4477 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex(); 4478 FrameOffset = Ptr.getConstantOperandVal(1); 4479 } 4480 4481 if (FrameIdx != (1 << 31)) { 4482 // FIXME: Handle FI+CST. 4483 const MachineFrameInfo &MFI = *DAG.getMachineFunction().getFrameInfo(); 4484 if (MFI.isFixedObjectIndex(FrameIdx)) { 4485 int64_t ObjectOffset = MFI.getObjectOffset(FrameIdx) + FrameOffset; 4486 4487 // The alignment of the frame index can be determined from its offset from 4488 // the incoming frame position. If the frame object is at offset 32 and 4489 // the stack is guaranteed to be 16-byte aligned, then we know that the 4490 // object is 16-byte aligned. 4491 unsigned StackAlign = DAG.getTarget().getFrameInfo()->getStackAlignment(); 4492 unsigned Align = MinAlign(ObjectOffset, StackAlign); 4493 4494 // Finally, the frame object itself may have a known alignment. Factor 4495 // the alignment + offset into a new alignment. For example, if we know 4496 // the FI is 8 byte aligned, but the pointer is 4 off, we really have a 4497 // 4-byte alignment of the resultant pointer. Likewise align 4 + 4-byte 4498 // offset = 4-byte alignment, align 4 + 1-byte offset = align 1, etc. 4499 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx), 4500 FrameOffset); 4501 return std::max(Align, FIInfoAlign); 4502 } 4503 } 4504 4505 return 0; 4506} 4507 4508SDValue DAGCombiner::visitLOAD(SDNode *N) { 4509 LoadSDNode *LD = cast<LoadSDNode>(N); 4510 SDValue Chain = LD->getChain(); 4511 SDValue Ptr = LD->getBasePtr(); 4512 4513 // Try to infer better alignment information than the load already has. 4514 if (!Fast && LD->isUnindexed()) { 4515 if (unsigned Align = InferAlignment(Ptr, DAG)) { 4516 if (Align > LD->getAlignment()) 4517 return DAG.getExtLoad(LD->getExtensionType(), LD->getValueType(0), 4518 Chain, Ptr, LD->getSrcValue(), 4519 LD->getSrcValueOffset(), LD->getMemoryVT(), 4520 LD->isVolatile(), Align); 4521 } 4522 } 4523 4524 4525 // If load is not volatile and there are no uses of the loaded value (and 4526 // the updated indexed value in case of indexed loads), change uses of the 4527 // chain value into uses of the chain input (i.e. delete the dead load). 4528 if (!LD->isVolatile()) { 4529 if (N->getValueType(1) == MVT::Other) { 4530 // Unindexed loads. 4531 if (N->hasNUsesOfValue(0, 0)) { 4532 // It's not safe to use the two value CombineTo variant here. e.g. 4533 // v1, chain2 = load chain1, loc 4534 // v2, chain3 = load chain2, loc 4535 // v3 = add v2, c 4536 // Now we replace use of chain2 with chain1. This makes the second load 4537 // isomorphic to the one we are deleting, and thus makes this load live. 4538 DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG)); 4539 DOUT << "\nWith chain: "; DEBUG(Chain.getNode()->dump(&DAG)); 4540 DOUT << "\n"; 4541 WorkListRemover DeadNodes(*this); 4542 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), Chain, &DeadNodes); 4543 if (N->use_empty()) { 4544 removeFromWorkList(N); 4545 DAG.DeleteNode(N); 4546 } 4547 return SDValue(N, 0); // Return N so it doesn't get rechecked! 4548 } 4549 } else { 4550 // Indexed loads. 4551 assert(N->getValueType(2) == MVT::Other && "Malformed indexed loads?"); 4552 if (N->hasNUsesOfValue(0, 0) && N->hasNUsesOfValue(0, 1)) { 4553 SDValue Undef = DAG.getNode(ISD::UNDEF, N->getValueType(0)); 4554 DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG)); 4555 DOUT << "\nWith: "; DEBUG(Undef.getNode()->dump(&DAG)); 4556 DOUT << " and 2 other values\n"; 4557 WorkListRemover DeadNodes(*this); 4558 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Undef, &DeadNodes); 4559 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), 4560 DAG.getNode(ISD::UNDEF, N->getValueType(1)), 4561 &DeadNodes); 4562 DAG.ReplaceAllUsesOfValueWith(SDValue(N, 2), Chain, &DeadNodes); 4563 removeFromWorkList(N); 4564 DAG.DeleteNode(N); 4565 return SDValue(N, 0); // Return N so it doesn't get rechecked! 4566 } 4567 } 4568 } 4569 4570 // If this load is directly stored, replace the load value with the stored 4571 // value. 4572 // TODO: Handle store large -> read small portion. 4573 // TODO: Handle TRUNCSTORE/LOADEXT 4574 if (LD->getExtensionType() == ISD::NON_EXTLOAD && 4575 !LD->isVolatile()) { 4576 if (ISD::isNON_TRUNCStore(Chain.getNode())) { 4577 StoreSDNode *PrevST = cast<StoreSDNode>(Chain); 4578 if (PrevST->getBasePtr() == Ptr && 4579 PrevST->getValue().getValueType() == N->getValueType(0)) 4580 return CombineTo(N, Chain.getOperand(1), Chain); 4581 } 4582 } 4583 4584 if (CombinerAA) { 4585 // Walk up chain skipping non-aliasing memory nodes. 4586 SDValue BetterChain = FindBetterChain(N, Chain); 4587 4588 // If there is a better chain. 4589 if (Chain != BetterChain) { 4590 SDValue ReplLoad; 4591 4592 // Replace the chain to void dependency. 4593 if (LD->getExtensionType() == ISD::NON_EXTLOAD) { 4594 ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr, 4595 LD->getSrcValue(), LD->getSrcValueOffset(), 4596 LD->isVolatile(), LD->getAlignment()); 4597 } else { 4598 ReplLoad = DAG.getExtLoad(LD->getExtensionType(), 4599 LD->getValueType(0), 4600 BetterChain, Ptr, LD->getSrcValue(), 4601 LD->getSrcValueOffset(), 4602 LD->getMemoryVT(), 4603 LD->isVolatile(), 4604 LD->getAlignment()); 4605 } 4606 4607 // Create token factor to keep old chain connected. 4608 SDValue Token = DAG.getNode(ISD::TokenFactor, MVT::Other, 4609 Chain, ReplLoad.getValue(1)); 4610 4611 // Replace uses with load result and token factor. Don't add users 4612 // to work list. 4613 return CombineTo(N, ReplLoad.getValue(0), Token, false); 4614 } 4615 } 4616 4617 // Try transforming N to an indexed load. 4618 if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N)) 4619 return SDValue(N, 0); 4620 4621 return SDValue(); 4622} 4623 4624 4625SDValue DAGCombiner::visitSTORE(SDNode *N) { 4626 StoreSDNode *ST = cast<StoreSDNode>(N); 4627 SDValue Chain = ST->getChain(); 4628 SDValue Value = ST->getValue(); 4629 SDValue Ptr = ST->getBasePtr(); 4630 4631 // Try to infer better alignment information than the store already has. 4632 if (!Fast && ST->isUnindexed()) { 4633 if (unsigned Align = InferAlignment(Ptr, DAG)) { 4634 if (Align > ST->getAlignment()) 4635 return DAG.getTruncStore(Chain, Value, Ptr, ST->getSrcValue(), 4636 ST->getSrcValueOffset(), ST->getMemoryVT(), 4637 ST->isVolatile(), Align); 4638 } 4639 } 4640 4641 // If this is a store of a bit convert, store the input value if the 4642 // resultant store does not need a higher alignment than the original. 4643 if (Value.getOpcode() == ISD::BIT_CONVERT && !ST->isTruncatingStore() && 4644 ST->isUnindexed()) { 4645 unsigned Align = ST->getAlignment(); 4646 MVT SVT = Value.getOperand(0).getValueType(); 4647 unsigned OrigAlign = TLI.getTargetData()-> 4648 getABITypeAlignment(SVT.getTypeForMVT()); 4649 if (Align <= OrigAlign && 4650 ((!LegalOperations && !ST->isVolatile()) || 4651 TLI.isOperationLegal(ISD::STORE, SVT))) 4652 return DAG.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(), 4653 ST->getSrcValueOffset(), ST->isVolatile(), OrigAlign); 4654 } 4655 4656 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 4657 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(Value)) { 4658 // NOTE: If the original store is volatile, this transform must not increase 4659 // the number of stores. For example, on x86-32 an f64 can be stored in one 4660 // processor operation but an i64 (which is not legal) requires two. So the 4661 // transform should not be done in this case. 4662 if (Value.getOpcode() != ISD::TargetConstantFP) { 4663 SDValue Tmp; 4664 switch (CFP->getValueType(0).getSimpleVT()) { 4665 default: assert(0 && "Unknown FP type"); 4666 case MVT::f80: // We don't do this for these yet. 4667 case MVT::f128: 4668 case MVT::ppcf128: 4669 break; 4670 case MVT::f32: 4671 if (((TLI.isTypeLegal(MVT::i32) || !LegalTypes) && !LegalOperations && 4672 !ST->isVolatile()) || TLI.isOperationLegal(ISD::STORE, MVT::i32)) { 4673 Tmp = DAG.getConstant((uint32_t)CFP->getValueAPF(). 4674 bitcastToAPInt().getZExtValue(), MVT::i32); 4675 return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(), 4676 ST->getSrcValueOffset(), ST->isVolatile(), 4677 ST->getAlignment()); 4678 } 4679 break; 4680 case MVT::f64: 4681 if (((TLI.isTypeLegal(MVT::i64) || !LegalTypes) && !LegalOperations && 4682 !ST->isVolatile()) || TLI.isOperationLegal(ISD::STORE, MVT::i64)) { 4683 Tmp = DAG.getConstant(CFP->getValueAPF().bitcastToAPInt(). 4684 getZExtValue(), MVT::i64); 4685 return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(), 4686 ST->getSrcValueOffset(), ST->isVolatile(), 4687 ST->getAlignment()); 4688 } else if (!ST->isVolatile() && 4689 TLI.isOperationLegal(ISD::STORE, MVT::i32)) { 4690 // Many FP stores are not made apparent until after legalize, e.g. for 4691 // argument passing. Since this is so common, custom legalize the 4692 // 64-bit integer store into two 32-bit stores. 4693 uint64_t Val = CFP->getValueAPF().bitcastToAPInt().getZExtValue(); 4694 SDValue Lo = DAG.getConstant(Val & 0xFFFFFFFF, MVT::i32); 4695 SDValue Hi = DAG.getConstant(Val >> 32, MVT::i32); 4696 if (TLI.isBigEndian()) std::swap(Lo, Hi); 4697 4698 int SVOffset = ST->getSrcValueOffset(); 4699 unsigned Alignment = ST->getAlignment(); 4700 bool isVolatile = ST->isVolatile(); 4701 4702 SDValue St0 = DAG.getStore(Chain, Lo, Ptr, ST->getSrcValue(), 4703 ST->getSrcValueOffset(), 4704 isVolatile, ST->getAlignment()); 4705 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 4706 DAG.getConstant(4, Ptr.getValueType())); 4707 SVOffset += 4; 4708 Alignment = MinAlign(Alignment, 4U); 4709 SDValue St1 = DAG.getStore(Chain, Hi, Ptr, ST->getSrcValue(), 4710 SVOffset, isVolatile, Alignment); 4711 return DAG.getNode(ISD::TokenFactor, MVT::Other, St0, St1); 4712 } 4713 break; 4714 } 4715 } 4716 } 4717 4718 if (CombinerAA) { 4719 // Walk up chain skipping non-aliasing memory nodes. 4720 SDValue BetterChain = FindBetterChain(N, Chain); 4721 4722 // If there is a better chain. 4723 if (Chain != BetterChain) { 4724 // Replace the chain to avoid dependency. 4725 SDValue ReplStore; 4726 if (ST->isTruncatingStore()) { 4727 ReplStore = DAG.getTruncStore(BetterChain, Value, Ptr, 4728 ST->getSrcValue(),ST->getSrcValueOffset(), 4729 ST->getMemoryVT(), 4730 ST->isVolatile(), ST->getAlignment()); 4731 } else { 4732 ReplStore = DAG.getStore(BetterChain, Value, Ptr, 4733 ST->getSrcValue(), ST->getSrcValueOffset(), 4734 ST->isVolatile(), ST->getAlignment()); 4735 } 4736 4737 // Create token to keep both nodes around. 4738 SDValue Token = 4739 DAG.getNode(ISD::TokenFactor, MVT::Other, Chain, ReplStore); 4740 4741 // Don't add users to work list. 4742 return CombineTo(N, Token, false); 4743 } 4744 } 4745 4746 // Try transforming N to an indexed store. 4747 if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N)) 4748 return SDValue(N, 0); 4749 4750 // FIXME: is there such a thing as a truncating indexed store? 4751 if (ST->isTruncatingStore() && ST->isUnindexed() && 4752 Value.getValueType().isInteger()) { 4753 // See if we can simplify the input to this truncstore with knowledge that 4754 // only the low bits are being used. For example: 4755 // "truncstore (or (shl x, 8), y), i8" -> "truncstore y, i8" 4756 SDValue Shorter = 4757 GetDemandedBits(Value, 4758 APInt::getLowBitsSet(Value.getValueSizeInBits(), 4759 ST->getMemoryVT().getSizeInBits())); 4760 AddToWorkList(Value.getNode()); 4761 if (Shorter.getNode()) 4762 return DAG.getTruncStore(Chain, Shorter, Ptr, ST->getSrcValue(), 4763 ST->getSrcValueOffset(), ST->getMemoryVT(), 4764 ST->isVolatile(), ST->getAlignment()); 4765 4766 // Otherwise, see if we can simplify the operation with 4767 // SimplifyDemandedBits, which only works if the value has a single use. 4768 if (SimplifyDemandedBits(Value, 4769 APInt::getLowBitsSet( 4770 Value.getValueSizeInBits(), 4771 ST->getMemoryVT().getSizeInBits()))) 4772 return SDValue(N, 0); 4773 } 4774 4775 // If this is a load followed by a store to the same location, then the store 4776 // is dead/noop. 4777 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) { 4778 if (Ld->getBasePtr() == Ptr && ST->getMemoryVT() == Ld->getMemoryVT() && 4779 ST->isUnindexed() && !ST->isVolatile() && 4780 // There can't be any side effects between the load and store, such as 4781 // a call or store. 4782 Chain.reachesChainWithoutSideEffects(SDValue(Ld, 1))) { 4783 // The store is dead, remove it. 4784 return Chain; 4785 } 4786 } 4787 4788 // If this is an FP_ROUND or TRUNC followed by a store, fold this into a 4789 // truncating store. We can do this even if this is already a truncstore. 4790 if ((Value.getOpcode() == ISD::FP_ROUND || Value.getOpcode() == ISD::TRUNCATE) 4791 && Value.getNode()->hasOneUse() && ST->isUnindexed() && 4792 TLI.isTruncStoreLegal(Value.getOperand(0).getValueType(), 4793 ST->getMemoryVT())) { 4794 return DAG.getTruncStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(), 4795 ST->getSrcValueOffset(), ST->getMemoryVT(), 4796 ST->isVolatile(), ST->getAlignment()); 4797 } 4798 4799 return SDValue(); 4800} 4801 4802SDValue DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) { 4803 SDValue InVec = N->getOperand(0); 4804 SDValue InVal = N->getOperand(1); 4805 SDValue EltNo = N->getOperand(2); 4806 4807 // If the invec is a BUILD_VECTOR and if EltNo is a constant, build a new 4808 // vector with the inserted element. 4809 if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) { 4810 unsigned Elt = cast<ConstantSDNode>(EltNo)->getZExtValue(); 4811 SmallVector<SDValue, 8> Ops(InVec.getNode()->op_begin(), 4812 InVec.getNode()->op_end()); 4813 if (Elt < Ops.size()) 4814 Ops[Elt] = InVal; 4815 return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(), 4816 &Ops[0], Ops.size()); 4817 } 4818 4819 return SDValue(); 4820} 4821 4822SDValue DAGCombiner::visitEXTRACT_VECTOR_ELT(SDNode *N) { 4823 // (vextract (v4f32 load $addr), c) -> (f32 load $addr+c*size) 4824 // (vextract (v4f32 s2v (f32 load $addr)), c) -> (f32 load $addr+c*size) 4825 // (vextract (v4f32 shuffle (load $addr), <1,u,u,u>), 0) -> (f32 load $addr) 4826 4827 // Perform only after legalization to ensure build_vector / vector_shuffle 4828 // optimizations have already been done. 4829 if (!LegalOperations) return SDValue(); 4830 4831 SDValue InVec = N->getOperand(0); 4832 SDValue EltNo = N->getOperand(1); 4833 4834 if (isa<ConstantSDNode>(EltNo)) { 4835 unsigned Elt = cast<ConstantSDNode>(EltNo)->getZExtValue(); 4836 bool NewLoad = false; 4837 MVT VT = InVec.getValueType(); 4838 MVT EVT = VT.getVectorElementType(); 4839 MVT LVT = EVT; 4840 if (InVec.getOpcode() == ISD::BIT_CONVERT) { 4841 MVT BCVT = InVec.getOperand(0).getValueType(); 4842 if (!BCVT.isVector() || EVT.bitsGT(BCVT.getVectorElementType())) 4843 return SDValue(); 4844 InVec = InVec.getOperand(0); 4845 EVT = BCVT.getVectorElementType(); 4846 NewLoad = true; 4847 } 4848 4849 LoadSDNode *LN0 = NULL; 4850 if (ISD::isNormalLoad(InVec.getNode())) 4851 LN0 = cast<LoadSDNode>(InVec); 4852 else if (InVec.getOpcode() == ISD::SCALAR_TO_VECTOR && 4853 InVec.getOperand(0).getValueType() == EVT && 4854 ISD::isNormalLoad(InVec.getOperand(0).getNode())) { 4855 LN0 = cast<LoadSDNode>(InVec.getOperand(0)); 4856 } else if (InVec.getOpcode() == ISD::VECTOR_SHUFFLE) { 4857 // (vextract (vector_shuffle (load $addr), v2, <1, u, u, u>), 1) 4858 // => 4859 // (load $addr+1*size) 4860 unsigned Idx = cast<ConstantSDNode>(InVec.getOperand(2). 4861 getOperand(Elt))->getZExtValue(); 4862 unsigned NumElems = InVec.getOperand(2).getNumOperands(); 4863 InVec = (Idx < NumElems) ? InVec.getOperand(0) : InVec.getOperand(1); 4864 if (InVec.getOpcode() == ISD::BIT_CONVERT) 4865 InVec = InVec.getOperand(0); 4866 if (ISD::isNormalLoad(InVec.getNode())) { 4867 LN0 = cast<LoadSDNode>(InVec); 4868 Elt = (Idx < NumElems) ? Idx : Idx - NumElems; 4869 } 4870 } 4871 if (!LN0 || !LN0->hasOneUse() || LN0->isVolatile()) 4872 return SDValue(); 4873 4874 unsigned Align = LN0->getAlignment(); 4875 if (NewLoad) { 4876 // Check the resultant load doesn't need a higher alignment than the 4877 // original load. 4878 unsigned NewAlign = TLI.getTargetData()-> 4879 getABITypeAlignment(LVT.getTypeForMVT()); 4880 if (NewAlign > Align || !TLI.isOperationLegal(ISD::LOAD, LVT)) 4881 return SDValue(); 4882 Align = NewAlign; 4883 } 4884 4885 SDValue NewPtr = LN0->getBasePtr(); 4886 if (Elt) { 4887 unsigned PtrOff = LVT.getSizeInBits() * Elt / 8; 4888 MVT PtrType = NewPtr.getValueType(); 4889 if (TLI.isBigEndian()) 4890 PtrOff = VT.getSizeInBits() / 8 - PtrOff; 4891 NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr, 4892 DAG.getConstant(PtrOff, PtrType)); 4893 } 4894 return DAG.getLoad(LVT, LN0->getChain(), NewPtr, 4895 LN0->getSrcValue(), LN0->getSrcValueOffset(), 4896 LN0->isVolatile(), Align); 4897 } 4898 return SDValue(); 4899} 4900 4901 4902SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) { 4903 unsigned NumInScalars = N->getNumOperands(); 4904 MVT VT = N->getValueType(0); 4905 unsigned NumElts = VT.getVectorNumElements(); 4906 MVT EltType = VT.getVectorElementType(); 4907 4908 // Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT 4909 // operations. If so, and if the EXTRACT_VECTOR_ELT vector inputs come from 4910 // at most two distinct vectors, turn this into a shuffle node. 4911 SDValue VecIn1, VecIn2; 4912 for (unsigned i = 0; i != NumInScalars; ++i) { 4913 // Ignore undef inputs. 4914 if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue; 4915 4916 // If this input is something other than a EXTRACT_VECTOR_ELT with a 4917 // constant index, bail out. 4918 if (N->getOperand(i).getOpcode() != ISD::EXTRACT_VECTOR_ELT || 4919 !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) { 4920 VecIn1 = VecIn2 = SDValue(0, 0); 4921 break; 4922 } 4923 4924 // If the input vector type disagrees with the result of the build_vector, 4925 // we can't make a shuffle. 4926 SDValue ExtractedFromVec = N->getOperand(i).getOperand(0); 4927 if (ExtractedFromVec.getValueType() != VT) { 4928 VecIn1 = VecIn2 = SDValue(0, 0); 4929 break; 4930 } 4931 4932 // Otherwise, remember this. We allow up to two distinct input vectors. 4933 if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2) 4934 continue; 4935 4936 if (VecIn1.getNode() == 0) { 4937 VecIn1 = ExtractedFromVec; 4938 } else if (VecIn2.getNode() == 0) { 4939 VecIn2 = ExtractedFromVec; 4940 } else { 4941 // Too many inputs. 4942 VecIn1 = VecIn2 = SDValue(0, 0); 4943 break; 4944 } 4945 } 4946 4947 // If everything is good, we can make a shuffle operation. 4948 if (VecIn1.getNode()) { 4949 SmallVector<SDValue, 8> BuildVecIndices; 4950 for (unsigned i = 0; i != NumInScalars; ++i) { 4951 if (N->getOperand(i).getOpcode() == ISD::UNDEF) { 4952 BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, TLI.getPointerTy())); 4953 continue; 4954 } 4955 4956 SDValue Extract = N->getOperand(i); 4957 4958 // If extracting from the first vector, just use the index directly. 4959 if (Extract.getOperand(0) == VecIn1) { 4960 BuildVecIndices.push_back(Extract.getOperand(1)); 4961 continue; 4962 } 4963 4964 // Otherwise, use InIdx + VecSize 4965 unsigned Idx = 4966 cast<ConstantSDNode>(Extract.getOperand(1))->getZExtValue(); 4967 BuildVecIndices.push_back(DAG.getIntPtrConstant(Idx+NumInScalars)); 4968 } 4969 4970 // Add count and size info. 4971 MVT BuildVecVT = MVT::getVectorVT(TLI.getPointerTy(), NumElts); 4972 if (!TLI.isTypeLegal(BuildVecVT) && LegalTypes) 4973 return SDValue(); 4974 4975 // Return the new VECTOR_SHUFFLE node. 4976 SDValue Ops[5]; 4977 Ops[0] = VecIn1; 4978 if (VecIn2.getNode()) { 4979 Ops[1] = VecIn2; 4980 } else { 4981 // Use an undef build_vector as input for the second operand. 4982 std::vector<SDValue> UnOps(NumInScalars, 4983 DAG.getNode(ISD::UNDEF, 4984 EltType)); 4985 Ops[1] = DAG.getNode(ISD::BUILD_VECTOR, VT, 4986 &UnOps[0], UnOps.size()); 4987 AddToWorkList(Ops[1].getNode()); 4988 } 4989 Ops[2] = DAG.getNode(ISD::BUILD_VECTOR, BuildVecVT, 4990 &BuildVecIndices[0], BuildVecIndices.size()); 4991 return DAG.getNode(ISD::VECTOR_SHUFFLE, VT, Ops, 3); 4992 } 4993 4994 return SDValue(); 4995} 4996 4997SDValue DAGCombiner::visitCONCAT_VECTORS(SDNode *N) { 4998 // TODO: Check to see if this is a CONCAT_VECTORS of a bunch of 4999 // EXTRACT_SUBVECTOR operations. If so, and if the EXTRACT_SUBVECTOR vector 5000 // inputs come from at most two distinct vectors, turn this into a shuffle 5001 // node. 5002 5003 // If we only have one input vector, we don't need to do any concatenation. 5004 if (N->getNumOperands() == 1) { 5005 return N->getOperand(0); 5006 } 5007 5008 return SDValue(); 5009} 5010 5011SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { 5012 SDValue ShufMask = N->getOperand(2); 5013 unsigned NumElts = ShufMask.getNumOperands(); 5014 5015 SDValue N0 = N->getOperand(0); 5016 SDValue N1 = N->getOperand(1); 5017 5018 assert(N0.getValueType().getVectorNumElements() == NumElts && 5019 "Vector shuffle must be normalized in DAG"); 5020 5021 // If the shuffle mask is an identity operation on the LHS, return the LHS. 5022 bool isIdentity = true; 5023 for (unsigned i = 0; i != NumElts; ++i) { 5024 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 5025 cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() != i) { 5026 isIdentity = false; 5027 break; 5028 } 5029 } 5030 if (isIdentity) return N->getOperand(0); 5031 5032 // If the shuffle mask is an identity operation on the RHS, return the RHS. 5033 isIdentity = true; 5034 for (unsigned i = 0; i != NumElts; ++i) { 5035 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && 5036 cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() != 5037 i+NumElts) { 5038 isIdentity = false; 5039 break; 5040 } 5041 } 5042 if (isIdentity) return N->getOperand(1); 5043 5044 // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not 5045 // needed at all. 5046 bool isUnary = true; 5047 bool isSplat = true; 5048 int VecNum = -1; 5049 unsigned BaseIdx = 0; 5050 for (unsigned i = 0; i != NumElts; ++i) 5051 if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { 5052 unsigned Idx=cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue(); 5053 int V = (Idx < NumElts) ? 0 : 1; 5054 if (VecNum == -1) { 5055 VecNum = V; 5056 BaseIdx = Idx; 5057 } else { 5058 if (BaseIdx != Idx) 5059 isSplat = false; 5060 if (VecNum != V) { 5061 isUnary = false; 5062 break; 5063 } 5064 } 5065 } 5066 5067 // Normalize unary shuffle so the RHS is undef. 5068 if (isUnary && VecNum == 1) 5069 std::swap(N0, N1); 5070 5071 // If it is a splat, check if the argument vector is a build_vector with 5072 // all scalar elements the same. 5073 if (isSplat) { 5074 SDNode *V = N0.getNode(); 5075 5076 // If this is a bit convert that changes the element type of the vector but 5077 // not the number of vector elements, look through it. Be careful not to 5078 // look though conversions that change things like v4f32 to v2f64. 5079 if (V->getOpcode() == ISD::BIT_CONVERT) { 5080 SDValue ConvInput = V->getOperand(0); 5081 if (ConvInput.getValueType().isVector() && 5082 ConvInput.getValueType().getVectorNumElements() == NumElts) 5083 V = ConvInput.getNode(); 5084 } 5085 5086 if (V->getOpcode() == ISD::BUILD_VECTOR) { 5087 unsigned NumElems = V->getNumOperands(); 5088 if (NumElems > BaseIdx) { 5089 SDValue Base; 5090 bool AllSame = true; 5091 for (unsigned i = 0; i != NumElems; ++i) { 5092 if (V->getOperand(i).getOpcode() != ISD::UNDEF) { 5093 Base = V->getOperand(i); 5094 break; 5095 } 5096 } 5097 // Splat of <u, u, u, u>, return <u, u, u, u> 5098 if (!Base.getNode()) 5099 return N0; 5100 for (unsigned i = 0; i != NumElems; ++i) { 5101 if (V->getOperand(i) != Base) { 5102 AllSame = false; 5103 break; 5104 } 5105 } 5106 // Splat of <x, x, x, x>, return <x, x, x, x> 5107 if (AllSame) 5108 return N0; 5109 } 5110 } 5111 } 5112 5113 // If it is a unary or the LHS and the RHS are the same node, turn the RHS 5114 // into an undef. 5115 if (isUnary || N0 == N1) { 5116 // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the 5117 // first operand. 5118 SmallVector<SDValue, 8> MappedOps; 5119 for (unsigned i = 0; i != NumElts; ++i) { 5120 if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || 5121 cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() < 5122 NumElts) { 5123 MappedOps.push_back(ShufMask.getOperand(i)); 5124 } else { 5125 unsigned NewIdx = 5126 cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() - 5127 NumElts; 5128 MappedOps.push_back(DAG.getConstant(NewIdx, 5129 ShufMask.getOperand(i).getValueType())); 5130 } 5131 } 5132 ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(), 5133 &MappedOps[0], MappedOps.size()); 5134 AddToWorkList(ShufMask.getNode()); 5135 return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0), 5136 N0, 5137 DAG.getNode(ISD::UNDEF, N->getValueType(0)), 5138 ShufMask); 5139 } 5140 5141 return SDValue(); 5142} 5143 5144/// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform 5145/// an AND to a vector_shuffle with the destination vector and a zero vector. 5146/// e.g. AND V, <0xffffffff, 0, 0xffffffff, 0>. ==> 5147/// vector_shuffle V, Zero, <0, 4, 2, 4> 5148SDValue DAGCombiner::XformToShuffleWithZero(SDNode *N) { 5149 SDValue LHS = N->getOperand(0); 5150 SDValue RHS = N->getOperand(1); 5151 if (N->getOpcode() == ISD::AND) { 5152 if (RHS.getOpcode() == ISD::BIT_CONVERT) 5153 RHS = RHS.getOperand(0); 5154 if (RHS.getOpcode() == ISD::BUILD_VECTOR) { 5155 std::vector<SDValue> IdxOps; 5156 unsigned NumOps = RHS.getNumOperands(); 5157 unsigned NumElts = NumOps; 5158 for (unsigned i = 0; i != NumElts; ++i) { 5159 SDValue Elt = RHS.getOperand(i); 5160 if (!isa<ConstantSDNode>(Elt)) 5161 return SDValue(); 5162 else if (cast<ConstantSDNode>(Elt)->isAllOnesValue()) 5163 IdxOps.push_back(DAG.getIntPtrConstant(i)); 5164 else if (cast<ConstantSDNode>(Elt)->isNullValue()) 5165 IdxOps.push_back(DAG.getIntPtrConstant(NumElts)); 5166 else 5167 return SDValue(); 5168 } 5169 5170 // Let's see if the target supports this vector_shuffle. 5171 if (!TLI.isVectorClearMaskLegal(IdxOps, TLI.getPointerTy(), DAG)) 5172 return SDValue(); 5173 5174 // Return the new VECTOR_SHUFFLE node. 5175 MVT EVT = RHS.getValueType().getVectorElementType(); 5176 MVT VT = MVT::getVectorVT(EVT, NumElts); 5177 MVT MaskVT = MVT::getVectorVT(TLI.getPointerTy(), NumElts); 5178 std::vector<SDValue> Ops; 5179 LHS = DAG.getNode(ISD::BIT_CONVERT, VT, LHS); 5180 Ops.push_back(LHS); 5181 AddToWorkList(LHS.getNode()); 5182 std::vector<SDValue> ZeroOps(NumElts, DAG.getConstant(0, EVT)); 5183 Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, VT, 5184 &ZeroOps[0], ZeroOps.size())); 5185 Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, MaskVT, 5186 &IdxOps[0], IdxOps.size())); 5187 SDValue Result = DAG.getNode(ISD::VECTOR_SHUFFLE, VT, 5188 &Ops[0], Ops.size()); 5189 if (VT != N->getValueType(0)) 5190 Result = DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0), Result); 5191 return Result; 5192 } 5193 } 5194 return SDValue(); 5195} 5196 5197/// SimplifyVBinOp - Visit a binary vector operation, like ADD. 5198SDValue DAGCombiner::SimplifyVBinOp(SDNode *N) { 5199 // After legalize, the target may be depending on adds and other 5200 // binary ops to provide legal ways to construct constants or other 5201 // things. Simplifying them may result in a loss of legality. 5202 if (LegalOperations) return SDValue(); 5203 5204 MVT VT = N->getValueType(0); 5205 assert(VT.isVector() && "SimplifyVBinOp only works on vectors!"); 5206 5207 MVT EltType = VT.getVectorElementType(); 5208 SDValue LHS = N->getOperand(0); 5209 SDValue RHS = N->getOperand(1); 5210 SDValue Shuffle = XformToShuffleWithZero(N); 5211 if (Shuffle.getNode()) return Shuffle; 5212 5213 // If the LHS and RHS are BUILD_VECTOR nodes, see if we can constant fold 5214 // this operation. 5215 if (LHS.getOpcode() == ISD::BUILD_VECTOR && 5216 RHS.getOpcode() == ISD::BUILD_VECTOR) { 5217 SmallVector<SDValue, 8> Ops; 5218 for (unsigned i = 0, e = LHS.getNumOperands(); i != e; ++i) { 5219 SDValue LHSOp = LHS.getOperand(i); 5220 SDValue RHSOp = RHS.getOperand(i); 5221 // If these two elements can't be folded, bail out. 5222 if ((LHSOp.getOpcode() != ISD::UNDEF && 5223 LHSOp.getOpcode() != ISD::Constant && 5224 LHSOp.getOpcode() != ISD::ConstantFP) || 5225 (RHSOp.getOpcode() != ISD::UNDEF && 5226 RHSOp.getOpcode() != ISD::Constant && 5227 RHSOp.getOpcode() != ISD::ConstantFP)) 5228 break; 5229 // Can't fold divide by zero. 5230 if (N->getOpcode() == ISD::SDIV || N->getOpcode() == ISD::UDIV || 5231 N->getOpcode() == ISD::FDIV) { 5232 if ((RHSOp.getOpcode() == ISD::Constant && 5233 cast<ConstantSDNode>(RHSOp.getNode())->isNullValue()) || 5234 (RHSOp.getOpcode() == ISD::ConstantFP && 5235 cast<ConstantFPSDNode>(RHSOp.getNode())->getValueAPF().isZero())) 5236 break; 5237 } 5238 Ops.push_back(DAG.getNode(N->getOpcode(), EltType, LHSOp, RHSOp)); 5239 AddToWorkList(Ops.back().getNode()); 5240 assert((Ops.back().getOpcode() == ISD::UNDEF || 5241 Ops.back().getOpcode() == ISD::Constant || 5242 Ops.back().getOpcode() == ISD::ConstantFP) && 5243 "Scalar binop didn't fold!"); 5244 } 5245 5246 if (Ops.size() == LHS.getNumOperands()) { 5247 MVT VT = LHS.getValueType(); 5248 return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 5249 } 5250 } 5251 5252 return SDValue(); 5253} 5254 5255SDValue DAGCombiner::SimplifySelect(SDValue N0, SDValue N1, SDValue N2){ 5256 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 5257 5258 SDValue SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 5259 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 5260 // If we got a simplified select_cc node back from SimplifySelectCC, then 5261 // break it down into a new SETCC node, and a new SELECT node, and then return 5262 // the SELECT node, since we were called with a SELECT node. 5263 if (SCC.getNode()) { 5264 // Check to see if we got a select_cc back (to turn into setcc/select). 5265 // Otherwise, just return whatever node we got back, like fabs. 5266 if (SCC.getOpcode() == ISD::SELECT_CC) { 5267 SDValue SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 5268 SCC.getOperand(0), SCC.getOperand(1), 5269 SCC.getOperand(4)); 5270 AddToWorkList(SETCC.getNode()); 5271 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 5272 SCC.getOperand(3), SETCC); 5273 } 5274 return SCC; 5275 } 5276 return SDValue(); 5277} 5278 5279/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS 5280/// are the two values being selected between, see if we can simplify the 5281/// select. Callers of this should assume that TheSelect is deleted if this 5282/// returns true. As such, they should return the appropriate thing (e.g. the 5283/// node) back to the top-level of the DAG combiner loop to avoid it being 5284/// looked at. 5285/// 5286bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDValue LHS, 5287 SDValue RHS) { 5288 5289 // If this is a select from two identical things, try to pull the operation 5290 // through the select. 5291 if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){ 5292 // If this is a load and the token chain is identical, replace the select 5293 // of two loads with a load through a select of the address to load from. 5294 // This triggers in things like "select bool X, 10.0, 123.0" after the FP 5295 // constants have been dropped into the constant pool. 5296 if (LHS.getOpcode() == ISD::LOAD && 5297 // Do not let this transformation reduce the number of volatile loads. 5298 !cast<LoadSDNode>(LHS)->isVolatile() && 5299 !cast<LoadSDNode>(RHS)->isVolatile() && 5300 // Token chains must be identical. 5301 LHS.getOperand(0) == RHS.getOperand(0)) { 5302 LoadSDNode *LLD = cast<LoadSDNode>(LHS); 5303 LoadSDNode *RLD = cast<LoadSDNode>(RHS); 5304 5305 // If this is an EXTLOAD, the VT's must match. 5306 if (LLD->getMemoryVT() == RLD->getMemoryVT()) { 5307 // FIXME: this conflates two src values, discarding one. This is not 5308 // the right thing to do, but nothing uses srcvalues now. When they do, 5309 // turn SrcValue into a list of locations. 5310 SDValue Addr; 5311 if (TheSelect->getOpcode() == ISD::SELECT) { 5312 // Check that the condition doesn't reach either load. If so, folding 5313 // this will induce a cycle into the DAG. 5314 if (!LLD->isPredecessorOf(TheSelect->getOperand(0).getNode()) && 5315 !RLD->isPredecessorOf(TheSelect->getOperand(0).getNode())) { 5316 Addr = DAG.getNode(ISD::SELECT, LLD->getBasePtr().getValueType(), 5317 TheSelect->getOperand(0), LLD->getBasePtr(), 5318 RLD->getBasePtr()); 5319 } 5320 } else { 5321 // Check that the condition doesn't reach either load. If so, folding 5322 // this will induce a cycle into the DAG. 5323 if (!LLD->isPredecessorOf(TheSelect->getOperand(0).getNode()) && 5324 !RLD->isPredecessorOf(TheSelect->getOperand(0).getNode()) && 5325 !LLD->isPredecessorOf(TheSelect->getOperand(1).getNode()) && 5326 !RLD->isPredecessorOf(TheSelect->getOperand(1).getNode())) { 5327 Addr = DAG.getNode(ISD::SELECT_CC, LLD->getBasePtr().getValueType(), 5328 TheSelect->getOperand(0), 5329 TheSelect->getOperand(1), 5330 LLD->getBasePtr(), RLD->getBasePtr(), 5331 TheSelect->getOperand(4)); 5332 } 5333 } 5334 5335 if (Addr.getNode()) { 5336 SDValue Load; 5337 if (LLD->getExtensionType() == ISD::NON_EXTLOAD) 5338 Load = DAG.getLoad(TheSelect->getValueType(0), LLD->getChain(), 5339 Addr,LLD->getSrcValue(), 5340 LLD->getSrcValueOffset(), 5341 LLD->isVolatile(), 5342 LLD->getAlignment()); 5343 else { 5344 Load = DAG.getExtLoad(LLD->getExtensionType(), 5345 TheSelect->getValueType(0), 5346 LLD->getChain(), Addr, LLD->getSrcValue(), 5347 LLD->getSrcValueOffset(), 5348 LLD->getMemoryVT(), 5349 LLD->isVolatile(), 5350 LLD->getAlignment()); 5351 } 5352 // Users of the select now use the result of the load. 5353 CombineTo(TheSelect, Load); 5354 5355 // Users of the old loads now use the new load's chain. We know the 5356 // old-load value is dead now. 5357 CombineTo(LHS.getNode(), Load.getValue(0), Load.getValue(1)); 5358 CombineTo(RHS.getNode(), Load.getValue(0), Load.getValue(1)); 5359 return true; 5360 } 5361 } 5362 } 5363 } 5364 5365 return false; 5366} 5367 5368SDValue DAGCombiner::SimplifySelectCC(SDValue N0, SDValue N1, 5369 SDValue N2, SDValue N3, 5370 ISD::CondCode CC, bool NotExtCompare) { 5371 5372 MVT VT = N2.getValueType(); 5373 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 5374 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 5375 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.getNode()); 5376 5377 // Determine if the condition we're dealing with is constant 5378 SDValue SCC = SimplifySetCC(TLI.getSetCCResultType(N0), N0, N1, CC, false); 5379 if (SCC.getNode()) AddToWorkList(SCC.getNode()); 5380 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.getNode()); 5381 5382 // fold select_cc true, x, y -> x 5383 if (SCCC && !SCCC->isNullValue()) 5384 return N2; 5385 // fold select_cc false, x, y -> y 5386 if (SCCC && SCCC->isNullValue()) 5387 return N3; 5388 5389 // Check to see if we can simplify the select into an fabs node 5390 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 5391 // Allow either -0.0 or 0.0 5392 if (CFP->getValueAPF().isZero()) { 5393 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 5394 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 5395 N0 == N2 && N3.getOpcode() == ISD::FNEG && 5396 N2 == N3.getOperand(0)) 5397 return DAG.getNode(ISD::FABS, VT, N0); 5398 5399 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 5400 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 5401 N0 == N3 && N2.getOpcode() == ISD::FNEG && 5402 N2.getOperand(0) == N3) 5403 return DAG.getNode(ISD::FABS, VT, N3); 5404 } 5405 } 5406 5407 // Check to see if we can perform the "gzip trick", transforming 5408 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 5409 if (N1C && N3C && N3C->isNullValue() && CC == ISD::SETLT && 5410 N0.getValueType().isInteger() && 5411 N2.getValueType().isInteger() && 5412 (N1C->isNullValue() || // (a < 0) ? b : 0 5413 (N1C->getAPIntValue() == 1 && N0 == N2))) { // (a < 1) ? a : 0 5414 MVT XType = N0.getValueType(); 5415 MVT AType = N2.getValueType(); 5416 if (XType.bitsGE(AType)) { 5417 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 5418 // single-bit constant. 5419 if (N2C && ((N2C->getAPIntValue() & (N2C->getAPIntValue()-1)) == 0)) { 5420 unsigned ShCtV = N2C->getAPIntValue().logBase2(); 5421 ShCtV = XType.getSizeInBits()-ShCtV-1; 5422 SDValue ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 5423 SDValue Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 5424 AddToWorkList(Shift.getNode()); 5425 if (XType.bitsGT(AType)) { 5426 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 5427 AddToWorkList(Shift.getNode()); 5428 } 5429 return DAG.getNode(ISD::AND, AType, Shift, N2); 5430 } 5431 SDValue Shift = DAG.getNode(ISD::SRA, XType, N0, 5432 DAG.getConstant(XType.getSizeInBits()-1, 5433 TLI.getShiftAmountTy())); 5434 AddToWorkList(Shift.getNode()); 5435 if (XType.bitsGT(AType)) { 5436 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 5437 AddToWorkList(Shift.getNode()); 5438 } 5439 return DAG.getNode(ISD::AND, AType, Shift, N2); 5440 } 5441 } 5442 5443 // fold select C, 16, 0 -> shl C, 4 5444 if (N2C && N3C && N3C->isNullValue() && N2C->getAPIntValue().isPowerOf2() && 5445 TLI.getBooleanContents() == TargetLowering::ZeroOrOneBooleanContent) { 5446 5447 // If the caller doesn't want us to simplify this into a zext of a compare, 5448 // don't do it. 5449 if (NotExtCompare && N2C->getAPIntValue() == 1) 5450 return SDValue(); 5451 5452 // Get a SetCC of the condition 5453 // FIXME: Should probably make sure that setcc is legal if we ever have a 5454 // target where it isn't. 5455 SDValue Temp, SCC; 5456 // cast from setcc result type to select result type 5457 if (LegalTypes) { 5458 SCC = DAG.getSetCC(TLI.getSetCCResultType(N0), N0, N1, CC); 5459 if (N2.getValueType().bitsLT(SCC.getValueType())) 5460 Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType()); 5461 else 5462 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 5463 } else { 5464 SCC = DAG.getSetCC(MVT::i1, N0, N1, CC); 5465 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 5466 } 5467 AddToWorkList(SCC.getNode()); 5468 AddToWorkList(Temp.getNode()); 5469 5470 if (N2C->getAPIntValue() == 1) 5471 return Temp; 5472 // shl setcc result by log2 n2c 5473 return DAG.getNode(ISD::SHL, N2.getValueType(), Temp, 5474 DAG.getConstant(N2C->getAPIntValue().logBase2(), 5475 TLI.getShiftAmountTy())); 5476 } 5477 5478 // Check to see if this is the equivalent of setcc 5479 // FIXME: Turn all of these into setcc if setcc if setcc is legal 5480 // otherwise, go ahead with the folds. 5481 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getAPIntValue() == 1ULL)) { 5482 MVT XType = N0.getValueType(); 5483 if (!LegalOperations || 5484 TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultType(N0))) { 5485 SDValue Res = DAG.getSetCC(TLI.getSetCCResultType(N0), N0, N1, CC); 5486 if (Res.getValueType() != VT) 5487 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 5488 return Res; 5489 } 5490 5491 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 5492 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 5493 (!LegalOperations || 5494 TLI.isOperationLegal(ISD::CTLZ, XType))) { 5495 SDValue Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 5496 return DAG.getNode(ISD::SRL, XType, Ctlz, 5497 DAG.getConstant(Log2_32(XType.getSizeInBits()), 5498 TLI.getShiftAmountTy())); 5499 } 5500 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 5501 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 5502 SDValue NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 5503 N0); 5504 SDValue NotN0 = DAG.getNode(ISD::XOR, XType, N0, 5505 DAG.getConstant(~0ULL, XType)); 5506 return DAG.getNode(ISD::SRL, XType, 5507 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 5508 DAG.getConstant(XType.getSizeInBits()-1, 5509 TLI.getShiftAmountTy())); 5510 } 5511 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 5512 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 5513 SDValue Sign = DAG.getNode(ISD::SRL, XType, N0, 5514 DAG.getConstant(XType.getSizeInBits()-1, 5515 TLI.getShiftAmountTy())); 5516 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 5517 } 5518 } 5519 5520 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 5521 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 5522 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 5523 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1) && 5524 N2.getOperand(0) == N1 && N0.getValueType().isInteger()) { 5525 MVT XType = N0.getValueType(); 5526 SDValue Shift = DAG.getNode(ISD::SRA, XType, N0, 5527 DAG.getConstant(XType.getSizeInBits()-1, 5528 TLI.getShiftAmountTy())); 5529 SDValue Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 5530 AddToWorkList(Shift.getNode()); 5531 AddToWorkList(Add.getNode()); 5532 return DAG.getNode(ISD::XOR, XType, Add, Shift); 5533 } 5534 // Check to see if this is an integer abs. select_cc setgt X, -1, X, -X -> 5535 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 5536 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT && 5537 N0 == N2 && N3.getOpcode() == ISD::SUB && N0 == N3.getOperand(1)) { 5538 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N3.getOperand(0))) { 5539 MVT XType = N0.getValueType(); 5540 if (SubC->isNullValue() && XType.isInteger()) { 5541 SDValue Shift = DAG.getNode(ISD::SRA, XType, N0, 5542 DAG.getConstant(XType.getSizeInBits()-1, 5543 TLI.getShiftAmountTy())); 5544 SDValue Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 5545 AddToWorkList(Shift.getNode()); 5546 AddToWorkList(Add.getNode()); 5547 return DAG.getNode(ISD::XOR, XType, Add, Shift); 5548 } 5549 } 5550 } 5551 5552 return SDValue(); 5553} 5554 5555/// SimplifySetCC - This is a stub for TargetLowering::SimplifySetCC. 5556SDValue DAGCombiner::SimplifySetCC(MVT VT, SDValue N0, 5557 SDValue N1, ISD::CondCode Cond, 5558 bool foldBooleans) { 5559 TargetLowering::DAGCombinerInfo 5560 DagCombineInfo(DAG, Level == Unrestricted, false, this); 5561 return TLI.SimplifySetCC(VT, N0, N1, Cond, foldBooleans, DagCombineInfo); 5562} 5563 5564/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 5565/// return a DAG expression to select that will generate the same value by 5566/// multiplying by a magic number. See: 5567/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 5568SDValue DAGCombiner::BuildSDIV(SDNode *N) { 5569 std::vector<SDNode*> Built; 5570 SDValue S = TLI.BuildSDIV(N, DAG, &Built); 5571 5572 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 5573 ii != ee; ++ii) 5574 AddToWorkList(*ii); 5575 return S; 5576} 5577 5578/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 5579/// return a DAG expression to select that will generate the same value by 5580/// multiplying by a magic number. See: 5581/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 5582SDValue DAGCombiner::BuildUDIV(SDNode *N) { 5583 std::vector<SDNode*> Built; 5584 SDValue S = TLI.BuildUDIV(N, DAG, &Built); 5585 5586 for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end(); 5587 ii != ee; ++ii) 5588 AddToWorkList(*ii); 5589 return S; 5590} 5591 5592/// FindBaseOffset - Return true if base is known not to alias with anything 5593/// but itself. Provides base object and offset as results. 5594static bool FindBaseOffset(SDValue Ptr, SDValue &Base, int64_t &Offset) { 5595 // Assume it is a primitive operation. 5596 Base = Ptr; Offset = 0; 5597 5598 // If it's an adding a simple constant then integrate the offset. 5599 if (Base.getOpcode() == ISD::ADD) { 5600 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Base.getOperand(1))) { 5601 Base = Base.getOperand(0); 5602 Offset += C->getZExtValue(); 5603 } 5604 } 5605 5606 // If it's any of the following then it can't alias with anything but itself. 5607 return isa<FrameIndexSDNode>(Base) || 5608 isa<ConstantPoolSDNode>(Base) || 5609 isa<GlobalAddressSDNode>(Base); 5610} 5611 5612/// isAlias - Return true if there is any possibility that the two addresses 5613/// overlap. 5614bool DAGCombiner::isAlias(SDValue Ptr1, int64_t Size1, 5615 const Value *SrcValue1, int SrcValueOffset1, 5616 SDValue Ptr2, int64_t Size2, 5617 const Value *SrcValue2, int SrcValueOffset2) 5618{ 5619 // If they are the same then they must be aliases. 5620 if (Ptr1 == Ptr2) return true; 5621 5622 // Gather base node and offset information. 5623 SDValue Base1, Base2; 5624 int64_t Offset1, Offset2; 5625 bool KnownBase1 = FindBaseOffset(Ptr1, Base1, Offset1); 5626 bool KnownBase2 = FindBaseOffset(Ptr2, Base2, Offset2); 5627 5628 // If they have a same base address then... 5629 if (Base1 == Base2) { 5630 // Check to see if the addresses overlap. 5631 return!((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1); 5632 } 5633 5634 // If we know both bases then they can't alias. 5635 if (KnownBase1 && KnownBase2) return false; 5636 5637 if (CombinerGlobalAA) { 5638 // Use alias analysis information. 5639 int64_t MinOffset = std::min(SrcValueOffset1, SrcValueOffset2); 5640 int64_t Overlap1 = Size1 + SrcValueOffset1 - MinOffset; 5641 int64_t Overlap2 = Size2 + SrcValueOffset2 - MinOffset; 5642 AliasAnalysis::AliasResult AAResult = 5643 AA.alias(SrcValue1, Overlap1, SrcValue2, Overlap2); 5644 if (AAResult == AliasAnalysis::NoAlias) 5645 return false; 5646 } 5647 5648 // Otherwise we have to assume they alias. 5649 return true; 5650} 5651 5652/// FindAliasInfo - Extracts the relevant alias information from the memory 5653/// node. Returns true if the operand was a load. 5654bool DAGCombiner::FindAliasInfo(SDNode *N, 5655 SDValue &Ptr, int64_t &Size, 5656 const Value *&SrcValue, int &SrcValueOffset) { 5657 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 5658 Ptr = LD->getBasePtr(); 5659 Size = LD->getMemoryVT().getSizeInBits() >> 3; 5660 SrcValue = LD->getSrcValue(); 5661 SrcValueOffset = LD->getSrcValueOffset(); 5662 return true; 5663 } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 5664 Ptr = ST->getBasePtr(); 5665 Size = ST->getMemoryVT().getSizeInBits() >> 3; 5666 SrcValue = ST->getSrcValue(); 5667 SrcValueOffset = ST->getSrcValueOffset(); 5668 } else { 5669 assert(0 && "FindAliasInfo expected a memory operand"); 5670 } 5671 5672 return false; 5673} 5674 5675/// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes, 5676/// looking for aliasing nodes and adding them to the Aliases vector. 5677void DAGCombiner::GatherAllAliases(SDNode *N, SDValue OriginalChain, 5678 SmallVector<SDValue, 8> &Aliases) { 5679 SmallVector<SDValue, 8> Chains; // List of chains to visit. 5680 std::set<SDNode *> Visited; // Visited node set. 5681 5682 // Get alias information for node. 5683 SDValue Ptr; 5684 int64_t Size; 5685 const Value *SrcValue; 5686 int SrcValueOffset; 5687 bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset); 5688 5689 // Starting off. 5690 Chains.push_back(OriginalChain); 5691 5692 // Look at each chain and determine if it is an alias. If so, add it to the 5693 // aliases list. If not, then continue up the chain looking for the next 5694 // candidate. 5695 while (!Chains.empty()) { 5696 SDValue Chain = Chains.back(); 5697 Chains.pop_back(); 5698 5699 // Don't bother if we've been before. 5700 if (Visited.find(Chain.getNode()) != Visited.end()) continue; 5701 Visited.insert(Chain.getNode()); 5702 5703 switch (Chain.getOpcode()) { 5704 case ISD::EntryToken: 5705 // Entry token is ideal chain operand, but handled in FindBetterChain. 5706 break; 5707 5708 case ISD::LOAD: 5709 case ISD::STORE: { 5710 // Get alias information for Chain. 5711 SDValue OpPtr; 5712 int64_t OpSize; 5713 const Value *OpSrcValue; 5714 int OpSrcValueOffset; 5715 bool IsOpLoad = FindAliasInfo(Chain.getNode(), OpPtr, OpSize, 5716 OpSrcValue, OpSrcValueOffset); 5717 5718 // If chain is alias then stop here. 5719 if (!(IsLoad && IsOpLoad) && 5720 isAlias(Ptr, Size, SrcValue, SrcValueOffset, 5721 OpPtr, OpSize, OpSrcValue, OpSrcValueOffset)) { 5722 Aliases.push_back(Chain); 5723 } else { 5724 // Look further up the chain. 5725 Chains.push_back(Chain.getOperand(0)); 5726 // Clean up old chain. 5727 AddToWorkList(Chain.getNode()); 5728 } 5729 break; 5730 } 5731 5732 case ISD::TokenFactor: 5733 // We have to check each of the operands of the token factor, so we queue 5734 // then up. Adding the operands to the queue (stack) in reverse order 5735 // maintains the original order and increases the likelihood that getNode 5736 // will find a matching token factor (CSE.) 5737 for (unsigned n = Chain.getNumOperands(); n;) 5738 Chains.push_back(Chain.getOperand(--n)); 5739 // Eliminate the token factor if we can. 5740 AddToWorkList(Chain.getNode()); 5741 break; 5742 5743 default: 5744 // For all other instructions we will just have to take what we can get. 5745 Aliases.push_back(Chain); 5746 break; 5747 } 5748 } 5749} 5750 5751/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, looking 5752/// for a better chain (aliasing node.) 5753SDValue DAGCombiner::FindBetterChain(SDNode *N, SDValue OldChain) { 5754 SmallVector<SDValue, 8> Aliases; // Ops for replacing token factor. 5755 5756 // Accumulate all the aliases to this node. 5757 GatherAllAliases(N, OldChain, Aliases); 5758 5759 if (Aliases.size() == 0) { 5760 // If no operands then chain to entry token. 5761 return DAG.getEntryNode(); 5762 } else if (Aliases.size() == 1) { 5763 // If a single operand then chain to it. We don't need to revisit it. 5764 return Aliases[0]; 5765 } 5766 5767 // Construct a custom tailored token factor. 5768 SDValue NewChain = DAG.getNode(ISD::TokenFactor, MVT::Other, 5769 &Aliases[0], Aliases.size()); 5770 5771 // Make sure the old chain gets cleaned up. 5772 if (NewChain != OldChain) AddToWorkList(OldChain.getNode()); 5773 5774 return NewChain; 5775} 5776 5777// SelectionDAG::Combine - This is the entry point for the file. 5778// 5779void SelectionDAG::Combine(CombineLevel Level, AliasAnalysis &AA, bool Fast) { 5780 /// run - This is the main entry point to this class. 5781 /// 5782 DAGCombiner(*this, AA, Fast).Run(Level); 5783} 5784