DAGCombiner.cpp revision d0e58e36a9857c45ecdc910ec8db04c21e143db5
1//===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Nate Begeman and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass combines dag nodes to form fewer, simpler DAG nodes. It can be run 11// both before and after the DAG is legalized. 12// 13// FIXME: Missing folds 14// sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into 15// a sequence of multiplies, shifts, and adds. This should be controlled by 16// some kind of hint from the target that int div is expensive. 17// various folds of mulh[s,u] by constants such as -1, powers of 2, etc. 18// 19// FIXME: Should add a corresponding version of fold AND with 20// ZERO_EXTEND/SIGN_EXTEND by converting them to an ANY_EXTEND node which 21// we don't have yet. 22// 23// FIXME: select C, pow2, pow2 -> something smart 24// FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z) 25// FIXME: Dead stores -> nuke 26// FIXME: shr X, (and Y,31) -> shr X, Y (TRICKY!) 27// FIXME: mul (x, const) -> shifts + adds 28// FIXME: undef values 29// FIXME: make truncate see through SIGN_EXTEND and AND 30// FIXME: (sra (sra x, c1), c2) -> (sra x, c1+c2) 31// FIXME: verify that getNode can't return extends with an operand whose type 32// is >= to that of the extend. 33// FIXME: divide by zero is currently left unfolded. do we want to turn this 34// into an undef? 35// FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false 36// 37//===----------------------------------------------------------------------===// 38 39#define DEBUG_TYPE "dagcombine" 40#include "llvm/ADT/Statistic.h" 41#include "llvm/CodeGen/SelectionDAG.h" 42#include "llvm/Support/Debug.h" 43#include "llvm/Support/MathExtras.h" 44#include "llvm/Target/TargetLowering.h" 45#include <algorithm> 46#include <cmath> 47#include <iostream> 48using namespace llvm; 49 50namespace { 51 Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined"); 52 53 class DAGCombiner { 54 SelectionDAG &DAG; 55 TargetLowering &TLI; 56 bool AfterLegalize; 57 58 // Worklist of all of the nodes that need to be simplified. 59 std::vector<SDNode*> WorkList; 60 61 /// AddUsersToWorkList - When an instruction is simplified, add all users of 62 /// the instruction to the work lists because they might get more simplified 63 /// now. 64 /// 65 void AddUsersToWorkList(SDNode *N) { 66 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 67 UI != UE; ++UI) 68 WorkList.push_back(*UI); 69 } 70 71 /// removeFromWorkList - remove all instances of N from the worklist. 72 void removeFromWorkList(SDNode *N) { 73 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N), 74 WorkList.end()); 75 } 76 77 SDOperand CombineTo(SDNode *N, const std::vector<SDOperand> &To) { 78 ++NodesCombined; 79 DEBUG(std::cerr << "\nReplacing "; N->dump(); 80 std::cerr << "\nWith: "; To[0].Val->dump(); 81 std::cerr << " and " << To.size()-1 << " other values\n"); 82 std::vector<SDNode*> NowDead; 83 DAG.ReplaceAllUsesWith(N, To, &NowDead); 84 85 // Push the new nodes and any users onto the worklist 86 for (unsigned i = 0, e = To.size(); i != e; ++i) { 87 WorkList.push_back(To[i].Val); 88 AddUsersToWorkList(To[i].Val); 89 } 90 91 // Nodes can end up on the worklist more than once. Make sure we do 92 // not process a node that has been replaced. 93 removeFromWorkList(N); 94 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 95 removeFromWorkList(NowDead[i]); 96 97 // Finally, since the node is now dead, remove it from the graph. 98 DAG.DeleteNode(N); 99 return SDOperand(N, 0); 100 } 101 102 SDOperand CombineTo(SDNode *N, SDOperand Res) { 103 std::vector<SDOperand> To; 104 To.push_back(Res); 105 return CombineTo(N, To); 106 } 107 108 SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) { 109 std::vector<SDOperand> To; 110 To.push_back(Res0); 111 To.push_back(Res1); 112 return CombineTo(N, To); 113 } 114 115 /// visit - call the node-specific routine that knows how to fold each 116 /// particular type of node. 117 SDOperand visit(SDNode *N); 118 119 // Visitation implementation - Implement dag node combining for different 120 // node types. The semantics are as follows: 121 // Return Value: 122 // SDOperand.Val == 0 - No change was made 123 // SDOperand.Val == N - N was replaced, is dead, and is already handled. 124 // otherwise - N should be replaced by the returned Operand. 125 // 126 SDOperand visitTokenFactor(SDNode *N); 127 SDOperand visitADD(SDNode *N); 128 SDOperand visitSUB(SDNode *N); 129 SDOperand visitMUL(SDNode *N); 130 SDOperand visitSDIV(SDNode *N); 131 SDOperand visitUDIV(SDNode *N); 132 SDOperand visitSREM(SDNode *N); 133 SDOperand visitUREM(SDNode *N); 134 SDOperand visitMULHU(SDNode *N); 135 SDOperand visitMULHS(SDNode *N); 136 SDOperand visitAND(SDNode *N); 137 SDOperand visitOR(SDNode *N); 138 SDOperand visitXOR(SDNode *N); 139 SDOperand visitSHL(SDNode *N); 140 SDOperand visitSRA(SDNode *N); 141 SDOperand visitSRL(SDNode *N); 142 SDOperand visitCTLZ(SDNode *N); 143 SDOperand visitCTTZ(SDNode *N); 144 SDOperand visitCTPOP(SDNode *N); 145 SDOperand visitSELECT(SDNode *N); 146 SDOperand visitSELECT_CC(SDNode *N); 147 SDOperand visitSETCC(SDNode *N); 148 SDOperand visitADD_PARTS(SDNode *N); 149 SDOperand visitSUB_PARTS(SDNode *N); 150 SDOperand visitSIGN_EXTEND(SDNode *N); 151 SDOperand visitZERO_EXTEND(SDNode *N); 152 SDOperand visitSIGN_EXTEND_INREG(SDNode *N); 153 SDOperand visitTRUNCATE(SDNode *N); 154 SDOperand visitBIT_CONVERT(SDNode *N); 155 156 SDOperand visitFADD(SDNode *N); 157 SDOperand visitFSUB(SDNode *N); 158 SDOperand visitFMUL(SDNode *N); 159 SDOperand visitFDIV(SDNode *N); 160 SDOperand visitFREM(SDNode *N); 161 SDOperand visitSINT_TO_FP(SDNode *N); 162 SDOperand visitUINT_TO_FP(SDNode *N); 163 SDOperand visitFP_TO_SINT(SDNode *N); 164 SDOperand visitFP_TO_UINT(SDNode *N); 165 SDOperand visitFP_ROUND(SDNode *N); 166 SDOperand visitFP_ROUND_INREG(SDNode *N); 167 SDOperand visitFP_EXTEND(SDNode *N); 168 SDOperand visitFNEG(SDNode *N); 169 SDOperand visitFABS(SDNode *N); 170 SDOperand visitBRCOND(SDNode *N); 171 SDOperand visitBRCONDTWOWAY(SDNode *N); 172 SDOperand visitBR_CC(SDNode *N); 173 SDOperand visitBRTWOWAY_CC(SDNode *N); 174 175 SDOperand visitLOAD(SDNode *N); 176 SDOperand visitSTORE(SDNode *N); 177 178 SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS); 179 180 bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS); 181 SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2); 182 SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2, 183 SDOperand N3, ISD::CondCode CC); 184 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1, 185 ISD::CondCode Cond, bool foldBooleans = true); 186 187 SDOperand BuildSDIV(SDNode *N); 188 SDOperand BuildUDIV(SDNode *N); 189public: 190 DAGCombiner(SelectionDAG &D) 191 : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {} 192 193 /// Run - runs the dag combiner on all nodes in the work list 194 void Run(bool RunningAfterLegalize); 195 }; 196} 197 198struct ms { 199 int64_t m; // magic number 200 int64_t s; // shift amount 201}; 202 203struct mu { 204 uint64_t m; // magic number 205 int64_t a; // add indicator 206 int64_t s; // shift amount 207}; 208 209/// magic - calculate the magic numbers required to codegen an integer sdiv as 210/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 211/// or -1. 212static ms magic32(int32_t d) { 213 int32_t p; 214 uint32_t ad, anc, delta, q1, r1, q2, r2, t; 215 const uint32_t two31 = 0x80000000U; 216 struct ms mag; 217 218 ad = abs(d); 219 t = two31 + ((uint32_t)d >> 31); 220 anc = t - 1 - t%ad; // absolute value of nc 221 p = 31; // initialize p 222 q1 = two31/anc; // initialize q1 = 2p/abs(nc) 223 r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 224 q2 = two31/ad; // initialize q2 = 2p/abs(d) 225 r2 = two31 - q2*ad; // initialize r2 = rem(2p,abs(d)) 226 do { 227 p = p + 1; 228 q1 = 2*q1; // update q1 = 2p/abs(nc) 229 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 230 if (r1 >= anc) { // must be unsigned comparison 231 q1 = q1 + 1; 232 r1 = r1 - anc; 233 } 234 q2 = 2*q2; // update q2 = 2p/abs(d) 235 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 236 if (r2 >= ad) { // must be unsigned comparison 237 q2 = q2 + 1; 238 r2 = r2 - ad; 239 } 240 delta = ad - r2; 241 } while (q1 < delta || (q1 == delta && r1 == 0)); 242 243 mag.m = (int32_t)(q2 + 1); // make sure to sign extend 244 if (d < 0) mag.m = -mag.m; // resulting magic number 245 mag.s = p - 32; // resulting shift 246 return mag; 247} 248 249/// magicu - calculate the magic numbers required to codegen an integer udiv as 250/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 251static mu magicu32(uint32_t d) { 252 int32_t p; 253 uint32_t nc, delta, q1, r1, q2, r2; 254 struct mu magu; 255 magu.a = 0; // initialize "add" indicator 256 nc = - 1 - (-d)%d; 257 p = 31; // initialize p 258 q1 = 0x80000000/nc; // initialize q1 = 2p/nc 259 r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc) 260 q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d 261 r2 = 0x7FFFFFFF - q2*d; // initialize r2 = rem((2p-1),d) 262 do { 263 p = p + 1; 264 if (r1 >= nc - r1 ) { 265 q1 = 2*q1 + 1; // update q1 266 r1 = 2*r1 - nc; // update r1 267 } 268 else { 269 q1 = 2*q1; // update q1 270 r1 = 2*r1; // update r1 271 } 272 if (r2 + 1 >= d - r2) { 273 if (q2 >= 0x7FFFFFFF) magu.a = 1; 274 q2 = 2*q2 + 1; // update q2 275 r2 = 2*r2 + 1 - d; // update r2 276 } 277 else { 278 if (q2 >= 0x80000000) magu.a = 1; 279 q2 = 2*q2; // update q2 280 r2 = 2*r2 + 1; // update r2 281 } 282 delta = d - 1 - r2; 283 } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0))); 284 magu.m = q2 + 1; // resulting magic number 285 magu.s = p - 32; // resulting shift 286 return magu; 287} 288 289/// magic - calculate the magic numbers required to codegen an integer sdiv as 290/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 291/// or -1. 292static ms magic64(int64_t d) { 293 int64_t p; 294 uint64_t ad, anc, delta, q1, r1, q2, r2, t; 295 const uint64_t two63 = 9223372036854775808ULL; // 2^63 296 struct ms mag; 297 298 ad = d >= 0 ? d : -d; 299 t = two63 + ((uint64_t)d >> 63); 300 anc = t - 1 - t%ad; // absolute value of nc 301 p = 63; // initialize p 302 q1 = two63/anc; // initialize q1 = 2p/abs(nc) 303 r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 304 q2 = two63/ad; // initialize q2 = 2p/abs(d) 305 r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d)) 306 do { 307 p = p + 1; 308 q1 = 2*q1; // update q1 = 2p/abs(nc) 309 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 310 if (r1 >= anc) { // must be unsigned comparison 311 q1 = q1 + 1; 312 r1 = r1 - anc; 313 } 314 q2 = 2*q2; // update q2 = 2p/abs(d) 315 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 316 if (r2 >= ad) { // must be unsigned comparison 317 q2 = q2 + 1; 318 r2 = r2 - ad; 319 } 320 delta = ad - r2; 321 } while (q1 < delta || (q1 == delta && r1 == 0)); 322 323 mag.m = q2 + 1; 324 if (d < 0) mag.m = -mag.m; // resulting magic number 325 mag.s = p - 64; // resulting shift 326 return mag; 327} 328 329/// magicu - calculate the magic numbers required to codegen an integer udiv as 330/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 331static mu magicu64(uint64_t d) 332{ 333 int64_t p; 334 uint64_t nc, delta, q1, r1, q2, r2; 335 struct mu magu; 336 magu.a = 0; // initialize "add" indicator 337 nc = - 1 - (-d)%d; 338 p = 63; // initialize p 339 q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc 340 r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc) 341 q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d 342 r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d) 343 do { 344 p = p + 1; 345 if (r1 >= nc - r1 ) { 346 q1 = 2*q1 + 1; // update q1 347 r1 = 2*r1 - nc; // update r1 348 } 349 else { 350 q1 = 2*q1; // update q1 351 r1 = 2*r1; // update r1 352 } 353 if (r2 + 1 >= d - r2) { 354 if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1; 355 q2 = 2*q2 + 1; // update q2 356 r2 = 2*r2 + 1 - d; // update r2 357 } 358 else { 359 if (q2 >= 0x8000000000000000ull) magu.a = 1; 360 q2 = 2*q2; // update q2 361 r2 = 2*r2 + 1; // update r2 362 } 363 delta = d - 1 - r2; 364 } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0))); 365 magu.m = q2 + 1; // resulting magic number 366 magu.s = p - 64; // resulting shift 367 return magu; 368} 369 370// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc 371// that selects between the values 1 and 0, making it equivalent to a setcc. 372// Also, set the incoming LHS, RHS, and CC references to the appropriate 373// nodes based on the type of node we are checking. This simplifies life a 374// bit for the callers. 375static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS, 376 SDOperand &CC) { 377 if (N.getOpcode() == ISD::SETCC) { 378 LHS = N.getOperand(0); 379 RHS = N.getOperand(1); 380 CC = N.getOperand(2); 381 return true; 382 } 383 if (N.getOpcode() == ISD::SELECT_CC && 384 N.getOperand(2).getOpcode() == ISD::Constant && 385 N.getOperand(3).getOpcode() == ISD::Constant && 386 cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 && 387 cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) { 388 LHS = N.getOperand(0); 389 RHS = N.getOperand(1); 390 CC = N.getOperand(4); 391 return true; 392 } 393 return false; 394} 395 396// isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only 397// one use. If this is true, it allows the users to invert the operation for 398// free when it is profitable to do so. 399static bool isOneUseSetCC(SDOperand N) { 400 SDOperand N0, N1, N2; 401 if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse()) 402 return true; 403 return false; 404} 405 406// FIXME: This should probably go in the ISD class rather than being duplicated 407// in several files. 408static bool isCommutativeBinOp(unsigned Opcode) { 409 switch (Opcode) { 410 case ISD::ADD: 411 case ISD::MUL: 412 case ISD::AND: 413 case ISD::OR: 414 case ISD::XOR: return true; 415 default: return false; // FIXME: Need commutative info for user ops! 416 } 417} 418 419SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){ 420 MVT::ValueType VT = N0.getValueType(); 421 // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use 422 // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2)) 423 if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) { 424 if (isa<ConstantSDNode>(N1)) { 425 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1); 426 WorkList.push_back(OpNode.Val); 427 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0)); 428 } else if (N0.hasOneUse()) { 429 SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1); 430 WorkList.push_back(OpNode.Val); 431 return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1)); 432 } 433 } 434 // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use 435 // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2)) 436 if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) { 437 if (isa<ConstantSDNode>(N0)) { 438 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0); 439 WorkList.push_back(OpNode.Val); 440 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0)); 441 } else if (N1.hasOneUse()) { 442 SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0); 443 WorkList.push_back(OpNode.Val); 444 return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1)); 445 } 446 } 447 return SDOperand(); 448} 449 450void DAGCombiner::Run(bool RunningAfterLegalize) { 451 // set the instance variable, so that the various visit routines may use it. 452 AfterLegalize = RunningAfterLegalize; 453 454 // Add all the dag nodes to the worklist. 455 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 456 E = DAG.allnodes_end(); I != E; ++I) 457 WorkList.push_back(I); 458 459 // Create a dummy node (which is not added to allnodes), that adds a reference 460 // to the root node, preventing it from being deleted, and tracking any 461 // changes of the root. 462 HandleSDNode Dummy(DAG.getRoot()); 463 464 // while the worklist isn't empty, inspect the node on the end of it and 465 // try and combine it. 466 while (!WorkList.empty()) { 467 SDNode *N = WorkList.back(); 468 WorkList.pop_back(); 469 470 // If N has no uses, it is dead. Make sure to revisit all N's operands once 471 // N is deleted from the DAG, since they too may now be dead or may have a 472 // reduced number of uses, allowing other xforms. 473 if (N->use_empty() && N != &Dummy) { 474 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 475 WorkList.push_back(N->getOperand(i).Val); 476 477 removeFromWorkList(N); 478 DAG.DeleteNode(N); 479 continue; 480 } 481 482 SDOperand RV = visit(N); 483 if (RV.Val) { 484 ++NodesCombined; 485 // If we get back the same node we passed in, rather than a new node or 486 // zero, we know that the node must have defined multiple values and 487 // CombineTo was used. Since CombineTo takes care of the worklist 488 // mechanics for us, we have no work to do in this case. 489 if (RV.Val != N) { 490 DEBUG(std::cerr << "\nReplacing "; N->dump(); 491 std::cerr << "\nWith: "; RV.Val->dump(); 492 std::cerr << '\n'); 493 std::vector<SDNode*> NowDead; 494 DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV), &NowDead); 495 496 // Push the new node and any users onto the worklist 497 WorkList.push_back(RV.Val); 498 AddUsersToWorkList(RV.Val); 499 500 // Nodes can end up on the worklist more than once. Make sure we do 501 // not process a node that has been replaced. 502 removeFromWorkList(N); 503 for (unsigned i = 0, e = NowDead.size(); i != e; ++i) 504 removeFromWorkList(NowDead[i]); 505 506 // Finally, since the node is now dead, remove it from the graph. 507 DAG.DeleteNode(N); 508 } 509 } 510 } 511 512 // If the root changed (e.g. it was a dead load, update the root). 513 DAG.setRoot(Dummy.getValue()); 514} 515 516SDOperand DAGCombiner::visit(SDNode *N) { 517 switch(N->getOpcode()) { 518 default: break; 519 case ISD::TokenFactor: return visitTokenFactor(N); 520 case ISD::ADD: return visitADD(N); 521 case ISD::SUB: return visitSUB(N); 522 case ISD::MUL: return visitMUL(N); 523 case ISD::SDIV: return visitSDIV(N); 524 case ISD::UDIV: return visitUDIV(N); 525 case ISD::SREM: return visitSREM(N); 526 case ISD::UREM: return visitUREM(N); 527 case ISD::MULHU: return visitMULHU(N); 528 case ISD::MULHS: return visitMULHS(N); 529 case ISD::AND: return visitAND(N); 530 case ISD::OR: return visitOR(N); 531 case ISD::XOR: return visitXOR(N); 532 case ISD::SHL: return visitSHL(N); 533 case ISD::SRA: return visitSRA(N); 534 case ISD::SRL: return visitSRL(N); 535 case ISD::CTLZ: return visitCTLZ(N); 536 case ISD::CTTZ: return visitCTTZ(N); 537 case ISD::CTPOP: return visitCTPOP(N); 538 case ISD::SELECT: return visitSELECT(N); 539 case ISD::SELECT_CC: return visitSELECT_CC(N); 540 case ISD::SETCC: return visitSETCC(N); 541 case ISD::ADD_PARTS: return visitADD_PARTS(N); 542 case ISD::SUB_PARTS: return visitSUB_PARTS(N); 543 case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N); 544 case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N); 545 case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); 546 case ISD::TRUNCATE: return visitTRUNCATE(N); 547 case ISD::BIT_CONVERT: return visitBIT_CONVERT(N); 548 case ISD::FADD: return visitFADD(N); 549 case ISD::FSUB: return visitFSUB(N); 550 case ISD::FMUL: return visitFMUL(N); 551 case ISD::FDIV: return visitFDIV(N); 552 case ISD::FREM: return visitFREM(N); 553 case ISD::SINT_TO_FP: return visitSINT_TO_FP(N); 554 case ISD::UINT_TO_FP: return visitUINT_TO_FP(N); 555 case ISD::FP_TO_SINT: return visitFP_TO_SINT(N); 556 case ISD::FP_TO_UINT: return visitFP_TO_UINT(N); 557 case ISD::FP_ROUND: return visitFP_ROUND(N); 558 case ISD::FP_ROUND_INREG: return visitFP_ROUND_INREG(N); 559 case ISD::FP_EXTEND: return visitFP_EXTEND(N); 560 case ISD::FNEG: return visitFNEG(N); 561 case ISD::FABS: return visitFABS(N); 562 case ISD::BRCOND: return visitBRCOND(N); 563 case ISD::BRCONDTWOWAY: return visitBRCONDTWOWAY(N); 564 case ISD::BR_CC: return visitBR_CC(N); 565 case ISD::BRTWOWAY_CC: return visitBRTWOWAY_CC(N); 566 case ISD::LOAD: return visitLOAD(N); 567 case ISD::STORE: return visitSTORE(N); 568 } 569 return SDOperand(); 570} 571 572SDOperand DAGCombiner::visitTokenFactor(SDNode *N) { 573 std::vector<SDOperand> Ops; 574 bool Changed = false; 575 576 // If the token factor has two operands and one is the entry token, replace 577 // the token factor with the other operand. 578 if (N->getNumOperands() == 2) { 579 if (N->getOperand(0).getOpcode() == ISD::EntryToken) 580 return N->getOperand(1); 581 if (N->getOperand(1).getOpcode() == ISD::EntryToken) 582 return N->getOperand(0); 583 } 584 585 // fold (tokenfactor (tokenfactor)) -> tokenfactor 586 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 587 SDOperand Op = N->getOperand(i); 588 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { 589 Changed = true; 590 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) 591 Ops.push_back(Op.getOperand(j)); 592 } else { 593 Ops.push_back(Op); 594 } 595 } 596 if (Changed) 597 return DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 598 return SDOperand(); 599} 600 601SDOperand DAGCombiner::visitADD(SDNode *N) { 602 SDOperand N0 = N->getOperand(0); 603 SDOperand N1 = N->getOperand(1); 604 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 605 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 606 MVT::ValueType VT = N0.getValueType(); 607 608 // fold (add c1, c2) -> c1+c2 609 if (N0C && N1C) 610 return DAG.getNode(ISD::ADD, VT, N0, N1); 611 // canonicalize constant to RHS 612 if (N0C && !N1C) 613 return DAG.getNode(ISD::ADD, VT, N1, N0); 614 // fold (add x, 0) -> x 615 if (N1C && N1C->isNullValue()) 616 return N0; 617 // fold ((c1-A)+c2) -> (c1+c2)-A 618 if (N1C && N0.getOpcode() == ISD::SUB) 619 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0))) 620 return DAG.getNode(ISD::SUB, VT, 621 DAG.getConstant(N1C->getValue()+N0C->getValue(), VT), 622 N0.getOperand(1)); 623 // reassociate add 624 SDOperand RADD = ReassociateOps(ISD::ADD, N0, N1); 625 if (RADD.Val != 0) 626 return RADD; 627 // fold ((0-A) + B) -> B-A 628 if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) && 629 cast<ConstantSDNode>(N0.getOperand(0))->isNullValue()) 630 return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1)); 631 // fold (A + (0-B)) -> A-B 632 if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) && 633 cast<ConstantSDNode>(N1.getOperand(0))->isNullValue()) 634 return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1)); 635 // fold (A+(B-A)) -> B 636 if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1)) 637 return N1.getOperand(0); 638 return SDOperand(); 639} 640 641SDOperand DAGCombiner::visitSUB(SDNode *N) { 642 SDOperand N0 = N->getOperand(0); 643 SDOperand N1 = N->getOperand(1); 644 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 645 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 646 MVT::ValueType VT = N0.getValueType(); 647 648 // fold (sub x, x) -> 0 649 if (N0 == N1) 650 return DAG.getConstant(0, N->getValueType(0)); 651 // fold (sub c1, c2) -> c1-c2 652 if (N0C && N1C) 653 return DAG.getNode(ISD::SUB, VT, N0, N1); 654 // fold (sub x, c) -> (add x, -c) 655 if (N1C) 656 return DAG.getNode(ISD::ADD, VT, N0, DAG.getConstant(-N1C->getValue(), VT)); 657 // fold (A+B)-A -> B 658 if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1) 659 return N0.getOperand(1); 660 // fold (A+B)-B -> A 661 if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1) 662 return N0.getOperand(0); 663 return SDOperand(); 664} 665 666SDOperand DAGCombiner::visitMUL(SDNode *N) { 667 SDOperand N0 = N->getOperand(0); 668 SDOperand N1 = N->getOperand(1); 669 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 670 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 671 MVT::ValueType VT = N0.getValueType(); 672 673 // fold (mul c1, c2) -> c1*c2 674 if (N0C && N1C) 675 return DAG.getNode(ISD::MUL, VT, N0, N1); 676 // canonicalize constant to RHS 677 if (N0C && !N1C) 678 return DAG.getNode(ISD::MUL, VT, N1, N0); 679 // fold (mul x, 0) -> 0 680 if (N1C && N1C->isNullValue()) 681 return N1; 682 // fold (mul x, -1) -> 0-x 683 if (N1C && N1C->isAllOnesValue()) 684 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 685 // fold (mul x, (1 << c)) -> x << c 686 if (N1C && isPowerOf2_64(N1C->getValue())) 687 return DAG.getNode(ISD::SHL, VT, N0, 688 DAG.getConstant(Log2_64(N1C->getValue()), 689 TLI.getShiftAmountTy())); 690 // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c 691 if (N1C && isPowerOf2_64(-N1C->getSignExtended())) { 692 // FIXME: If the input is something that is easily negated (e.g. a 693 // single-use add), we should put the negate there. 694 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), 695 DAG.getNode(ISD::SHL, VT, N0, 696 DAG.getConstant(Log2_64(-N1C->getSignExtended()), 697 TLI.getShiftAmountTy()))); 698 } 699 // reassociate mul 700 SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1); 701 if (RMUL.Val != 0) 702 return RMUL; 703 return SDOperand(); 704} 705 706SDOperand DAGCombiner::visitSDIV(SDNode *N) { 707 SDOperand N0 = N->getOperand(0); 708 SDOperand N1 = N->getOperand(1); 709 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 710 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 711 MVT::ValueType VT = N->getValueType(0); 712 713 // fold (sdiv c1, c2) -> c1/c2 714 if (N0C && N1C && !N1C->isNullValue()) 715 return DAG.getNode(ISD::SDIV, VT, N0, N1); 716 // fold (sdiv X, 1) -> X 717 if (N1C && N1C->getSignExtended() == 1LL) 718 return N0; 719 // fold (sdiv X, -1) -> 0-X 720 if (N1C && N1C->isAllOnesValue()) 721 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0); 722 // If we know the sign bits of both operands are zero, strength reduce to a 723 // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2 724 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 725 if (TLI.MaskedValueIsZero(N1, SignBit) && 726 TLI.MaskedValueIsZero(N0, SignBit)) 727 return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1); 728 // fold (sdiv X, pow2) -> (add (sra X, log(pow2)), (srl X, sizeof(X)-1)) 729 if (N1C && N1C->getValue() && !TLI.isIntDivCheap() && 730 (isPowerOf2_64(N1C->getSignExtended()) || 731 isPowerOf2_64(-N1C->getSignExtended()))) { 732 // If dividing by powers of two is cheap, then don't perform the following 733 // fold. 734 if (TLI.isPow2DivCheap()) 735 return SDOperand(); 736 int64_t pow2 = N1C->getSignExtended(); 737 int64_t abs2 = pow2 > 0 ? pow2 : -pow2; 738 SDOperand SRL = DAG.getNode(ISD::SRL, VT, N0, 739 DAG.getConstant(MVT::getSizeInBits(VT)-1, 740 TLI.getShiftAmountTy())); 741 WorkList.push_back(SRL.Val); 742 SDOperand SGN = DAG.getNode(ISD::ADD, VT, N0, SRL); 743 WorkList.push_back(SGN.Val); 744 SDOperand SRA = DAG.getNode(ISD::SRA, VT, SGN, 745 DAG.getConstant(Log2_64(abs2), 746 TLI.getShiftAmountTy())); 747 // If we're dividing by a positive value, we're done. Otherwise, we must 748 // negate the result. 749 if (pow2 > 0) 750 return SRA; 751 WorkList.push_back(SRA.Val); 752 return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA); 753 } 754 // if integer divide is expensive and we satisfy the requirements, emit an 755 // alternate sequence. 756 if (N1C && (N1C->getSignExtended() < -1 || N1C->getSignExtended() > 1) && 757 !TLI.isIntDivCheap()) { 758 SDOperand Op = BuildSDIV(N); 759 if (Op.Val) return Op; 760 } 761 return SDOperand(); 762} 763 764SDOperand DAGCombiner::visitUDIV(SDNode *N) { 765 SDOperand N0 = N->getOperand(0); 766 SDOperand N1 = N->getOperand(1); 767 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 768 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 769 MVT::ValueType VT = N->getValueType(0); 770 771 // fold (udiv c1, c2) -> c1/c2 772 if (N0C && N1C && !N1C->isNullValue()) 773 return DAG.getNode(ISD::UDIV, VT, N0, N1); 774 // fold (udiv x, (1 << c)) -> x >>u c 775 if (N1C && isPowerOf2_64(N1C->getValue())) 776 return DAG.getNode(ISD::SRL, VT, N0, 777 DAG.getConstant(Log2_64(N1C->getValue()), 778 TLI.getShiftAmountTy())); 779 // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2 780 if (N1.getOpcode() == ISD::SHL) { 781 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 782 if (isPowerOf2_64(SHC->getValue())) { 783 MVT::ValueType ADDVT = N1.getOperand(1).getValueType(); 784 SDOperand Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1), 785 DAG.getConstant(Log2_64(SHC->getValue()), 786 ADDVT)); 787 WorkList.push_back(Add.Val); 788 return DAG.getNode(ISD::SRL, VT, N0, Add); 789 } 790 } 791 } 792 // fold (udiv x, c) -> alternate 793 if (N1C && N1C->getValue() && !TLI.isIntDivCheap()) { 794 SDOperand Op = BuildUDIV(N); 795 if (Op.Val) return Op; 796 } 797 return SDOperand(); 798} 799 800SDOperand DAGCombiner::visitSREM(SDNode *N) { 801 SDOperand N0 = N->getOperand(0); 802 SDOperand N1 = N->getOperand(1); 803 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 804 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 805 MVT::ValueType VT = N->getValueType(0); 806 807 // fold (srem c1, c2) -> c1%c2 808 if (N0C && N1C && !N1C->isNullValue()) 809 return DAG.getNode(ISD::SREM, VT, N0, N1); 810 // If we know the sign bits of both operands are zero, strength reduce to a 811 // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15 812 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1); 813 if (TLI.MaskedValueIsZero(N1, SignBit) && 814 TLI.MaskedValueIsZero(N0, SignBit)) 815 return DAG.getNode(ISD::UREM, VT, N0, N1); 816 return SDOperand(); 817} 818 819SDOperand DAGCombiner::visitUREM(SDNode *N) { 820 SDOperand N0 = N->getOperand(0); 821 SDOperand N1 = N->getOperand(1); 822 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 823 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 824 MVT::ValueType VT = N->getValueType(0); 825 826 // fold (urem c1, c2) -> c1%c2 827 if (N0C && N1C && !N1C->isNullValue()) 828 return DAG.getNode(ISD::UREM, VT, N0, N1); 829 // fold (urem x, pow2) -> (and x, pow2-1) 830 if (N1C && !N1C->isNullValue() && isPowerOf2_64(N1C->getValue())) 831 return DAG.getNode(ISD::AND, VT, N0, DAG.getConstant(N1C->getValue()-1,VT)); 832 // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1)) 833 if (N1.getOpcode() == ISD::SHL) { 834 if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) { 835 if (isPowerOf2_64(SHC->getValue())) { 836 SDOperand Add = DAG.getNode(ISD::ADD, VT, N1,DAG.getConstant(~0ULL,VT)); 837 WorkList.push_back(Add.Val); 838 return DAG.getNode(ISD::AND, VT, N0, Add); 839 } 840 } 841 } 842 return SDOperand(); 843} 844 845SDOperand DAGCombiner::visitMULHS(SDNode *N) { 846 SDOperand N0 = N->getOperand(0); 847 SDOperand N1 = N->getOperand(1); 848 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 849 850 // fold (mulhs x, 0) -> 0 851 if (N1C && N1C->isNullValue()) 852 return N1; 853 // fold (mulhs x, 1) -> (sra x, size(x)-1) 854 if (N1C && N1C->getValue() == 1) 855 return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 856 DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1, 857 TLI.getShiftAmountTy())); 858 return SDOperand(); 859} 860 861SDOperand DAGCombiner::visitMULHU(SDNode *N) { 862 SDOperand N0 = N->getOperand(0); 863 SDOperand N1 = N->getOperand(1); 864 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 865 866 // fold (mulhu x, 0) -> 0 867 if (N1C && N1C->isNullValue()) 868 return N1; 869 // fold (mulhu x, 1) -> 0 870 if (N1C && N1C->getValue() == 1) 871 return DAG.getConstant(0, N0.getValueType()); 872 return SDOperand(); 873} 874 875SDOperand DAGCombiner::visitAND(SDNode *N) { 876 SDOperand N0 = N->getOperand(0); 877 SDOperand N1 = N->getOperand(1); 878 SDOperand LL, LR, RL, RR, CC0, CC1, Old, New; 879 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 880 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 881 MVT::ValueType VT = N1.getValueType(); 882 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 883 884 // fold (and c1, c2) -> c1&c2 885 if (N0C && N1C) 886 return DAG.getNode(ISD::AND, VT, N0, N1); 887 // canonicalize constant to RHS 888 if (N0C && !N1C) 889 return DAG.getNode(ISD::AND, VT, N1, N0); 890 // fold (and x, -1) -> x 891 if (N1C && N1C->isAllOnesValue()) 892 return N0; 893 // if (and x, c) is known to be zero, return 0 894 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) 895 return DAG.getConstant(0, VT); 896 // fold (and x, c) -> x iff (x & ~c) == 0 897 if (N1C && 898 TLI.MaskedValueIsZero(N0, ~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) 899 return N0; 900 // reassociate and 901 SDOperand RAND = ReassociateOps(ISD::AND, N0, N1); 902 if (RAND.Val != 0) 903 return RAND; 904 // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF 905 if (N1C && N0.getOpcode() == ISD::OR) 906 if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) 907 if ((ORI->getValue() & N1C->getValue()) == N1C->getValue()) 908 return N1; 909 // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits. 910 if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) { 911 unsigned InBits = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 912 if (TLI.MaskedValueIsZero(N0.getOperand(0), 913 ~N1C->getValue() & ((1ULL << InBits)-1))) { 914 // We actually want to replace all uses of the any_extend with the 915 // zero_extend, to avoid duplicating things. This will later cause this 916 // AND to be folded. 917 CombineTo(N0.Val, DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(), 918 N0.getOperand(0))); 919 return SDOperand(); 920 } 921 } 922 // fold (and (setcc x), (setcc y)) -> (setcc (and x, y)) 923 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 924 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 925 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 926 927 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 928 MVT::isInteger(LL.getValueType())) { 929 // fold (X == 0) & (Y == 0) -> (X|Y == 0) 930 if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) { 931 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 932 WorkList.push_back(ORNode.Val); 933 return DAG.getSetCC(VT, ORNode, LR, Op1); 934 } 935 // fold (X == -1) & (Y == -1) -> (X&Y == -1) 936 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) { 937 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 938 WorkList.push_back(ANDNode.Val); 939 return DAG.getSetCC(VT, ANDNode, LR, Op1); 940 } 941 // fold (X > -1) & (Y > -1) -> (X|Y > -1) 942 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) { 943 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 944 WorkList.push_back(ORNode.Val); 945 return DAG.getSetCC(VT, ORNode, LR, Op1); 946 } 947 } 948 // canonicalize equivalent to ll == rl 949 if (LL == RR && LR == RL) { 950 Op1 = ISD::getSetCCSwappedOperands(Op1); 951 std::swap(RL, RR); 952 } 953 if (LL == RL && LR == RR) { 954 bool isInteger = MVT::isInteger(LL.getValueType()); 955 ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger); 956 if (Result != ISD::SETCC_INVALID) 957 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 958 } 959 } 960 // fold (and (zext x), (zext y)) -> (zext (and x, y)) 961 if (N0.getOpcode() == ISD::ZERO_EXTEND && 962 N1.getOpcode() == ISD::ZERO_EXTEND && 963 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 964 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 965 N0.getOperand(0), N1.getOperand(0)); 966 WorkList.push_back(ANDNode.Val); 967 return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode); 968 } 969 // fold (and (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (and x, y)) 970 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) || 971 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) || 972 (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) && 973 N0.getOperand(1) == N1.getOperand(1)) { 974 SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(), 975 N0.getOperand(0), N1.getOperand(0)); 976 WorkList.push_back(ANDNode.Val); 977 return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1)); 978 } 979 // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1) 980 // fold (and (sra)) -> (and (srl)) when possible. 981 if (TLI.DemandedBitsAreZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits), Old, 982 New, DAG)) { 983 WorkList.push_back(N); 984 CombineTo(Old.Val, New); 985 return SDOperand(); 986 } 987 // FIXME: DemandedBitsAreZero cannot currently handle AND with non-constant 988 // RHS and propagate known cleared bits to LHS. For this reason, we must keep 989 // this fold, for now, for the following testcase: 990 // 991 //int %test2(uint %mode.0.i.0) { 992 // %tmp.79 = cast uint %mode.0.i.0 to int 993 // %tmp.80 = shr int %tmp.79, ubyte 15 994 // %tmp.81 = shr uint %mode.0.i.0, ubyte 16 995 // %tmp.82 = cast uint %tmp.81 to int 996 // %tmp.83 = and int %tmp.80, %tmp.82 997 // ret int %tmp.83 998 //} 999 // fold (and (sra)) -> (and (srl)) when possible. 1000 if (N0.getOpcode() == ISD::SRA && N0.Val->hasOneUse()) { 1001 if (ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 1002 // If the RHS of the AND has zeros where the sign bits of the SRA will 1003 // land, turn the SRA into an SRL. 1004 if (TLI.MaskedValueIsZero(N1, (~0ULL << (OpSizeInBits-N01C->getValue())) & 1005 (~0ULL>>(64-OpSizeInBits)))) { 1006 WorkList.push_back(N); 1007 CombineTo(N0.Val, DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 1008 N0.getOperand(1))); 1009 return SDOperand(); 1010 } 1011 } 1012 } 1013 // fold (zext_inreg (extload x)) -> (zextload x) 1014 if (N0.getOpcode() == ISD::EXTLOAD) { 1015 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1016 // If we zero all the possible extended bits, then we can turn this into 1017 // a zextload if we are running before legalize or the operation is legal. 1018 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1019 (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) { 1020 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1021 N0.getOperand(1), N0.getOperand(2), 1022 EVT); 1023 WorkList.push_back(N); 1024 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1025 return SDOperand(); 1026 } 1027 } 1028 // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use 1029 if (N0.getOpcode() == ISD::SEXTLOAD && N0.hasOneUse()) { 1030 MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT(); 1031 // If we zero all the possible extended bits, then we can turn this into 1032 // a zextload if we are running before legalize or the operation is legal. 1033 if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) && 1034 (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) { 1035 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1036 N0.getOperand(1), N0.getOperand(2), 1037 EVT); 1038 WorkList.push_back(N); 1039 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1040 return SDOperand(); 1041 } 1042 } 1043 return SDOperand(); 1044} 1045 1046SDOperand DAGCombiner::visitOR(SDNode *N) { 1047 SDOperand N0 = N->getOperand(0); 1048 SDOperand N1 = N->getOperand(1); 1049 SDOperand LL, LR, RL, RR, CC0, CC1; 1050 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1051 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1052 MVT::ValueType VT = N1.getValueType(); 1053 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1054 1055 // fold (or c1, c2) -> c1|c2 1056 if (N0C && N1C) 1057 return DAG.getNode(ISD::OR, VT, N0, N1); 1058 // canonicalize constant to RHS 1059 if (N0C && !N1C) 1060 return DAG.getNode(ISD::OR, VT, N1, N0); 1061 // fold (or x, 0) -> x 1062 if (N1C && N1C->isNullValue()) 1063 return N0; 1064 // fold (or x, -1) -> -1 1065 if (N1C && N1C->isAllOnesValue()) 1066 return N1; 1067 // fold (or x, c) -> c iff (x & ~c) == 0 1068 if (N1C && 1069 TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)))) 1070 return N1; 1071 // reassociate or 1072 SDOperand ROR = ReassociateOps(ISD::OR, N0, N1); 1073 if (ROR.Val != 0) 1074 return ROR; 1075 // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2) 1076 if (N1C && N0.getOpcode() == ISD::AND && N0.Val->hasOneUse() && 1077 isa<ConstantSDNode>(N0.getOperand(1))) { 1078 ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1)); 1079 return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0), 1080 N1), 1081 DAG.getConstant(N1C->getValue() | C1->getValue(), VT)); 1082 } 1083 // fold (or (setcc x), (setcc y)) -> (setcc (or x, y)) 1084 if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){ 1085 ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get(); 1086 ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get(); 1087 1088 if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 && 1089 MVT::isInteger(LL.getValueType())) { 1090 // fold (X != 0) | (Y != 0) -> (X|Y != 0) 1091 // fold (X < 0) | (Y < 0) -> (X|Y < 0) 1092 if (cast<ConstantSDNode>(LR)->getValue() == 0 && 1093 (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) { 1094 SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL); 1095 WorkList.push_back(ORNode.Val); 1096 return DAG.getSetCC(VT, ORNode, LR, Op1); 1097 } 1098 // fold (X != -1) | (Y != -1) -> (X&Y != -1) 1099 // fold (X > -1) | (Y > -1) -> (X&Y > -1) 1100 if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 1101 (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) { 1102 SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL); 1103 WorkList.push_back(ANDNode.Val); 1104 return DAG.getSetCC(VT, ANDNode, LR, Op1); 1105 } 1106 } 1107 // canonicalize equivalent to ll == rl 1108 if (LL == RR && LR == RL) { 1109 Op1 = ISD::getSetCCSwappedOperands(Op1); 1110 std::swap(RL, RR); 1111 } 1112 if (LL == RL && LR == RR) { 1113 bool isInteger = MVT::isInteger(LL.getValueType()); 1114 ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger); 1115 if (Result != ISD::SETCC_INVALID) 1116 return DAG.getSetCC(N0.getValueType(), LL, LR, Result); 1117 } 1118 } 1119 // fold (or (zext x), (zext y)) -> (zext (or x, y)) 1120 if (N0.getOpcode() == ISD::ZERO_EXTEND && 1121 N1.getOpcode() == ISD::ZERO_EXTEND && 1122 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 1123 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(), 1124 N0.getOperand(0), N1.getOperand(0)); 1125 WorkList.push_back(ORNode.Val); 1126 return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode); 1127 } 1128 // fold (or (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (or x, y)) 1129 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) || 1130 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) || 1131 (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) && 1132 N0.getOperand(1) == N1.getOperand(1)) { 1133 SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(), 1134 N0.getOperand(0), N1.getOperand(0)); 1135 WorkList.push_back(ORNode.Val); 1136 return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1)); 1137 } 1138 // canonicalize shl to left side in a shl/srl pair, to match rotate 1139 if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL) 1140 std::swap(N0, N1); 1141 // check for rotl, rotr 1142 if (N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SRL && 1143 N0.getOperand(0) == N1.getOperand(0) && 1144 TLI.isOperationLegal(ISD::ROTL, VT) && TLI.isTypeLegal(VT)) { 1145 // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1) 1146 if (N0.getOperand(1).getOpcode() == ISD::Constant && 1147 N1.getOperand(1).getOpcode() == ISD::Constant) { 1148 uint64_t c1val = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1149 uint64_t c2val = cast<ConstantSDNode>(N1.getOperand(1))->getValue(); 1150 if ((c1val + c2val) == OpSizeInBits) 1151 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1)); 1152 } 1153 // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y) 1154 if (N1.getOperand(1).getOpcode() == ISD::SUB && 1155 N0.getOperand(1) == N1.getOperand(1).getOperand(1)) 1156 if (ConstantSDNode *SUBC = 1157 dyn_cast<ConstantSDNode>(N1.getOperand(1).getOperand(0))) 1158 if (SUBC->getValue() == OpSizeInBits) 1159 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1)); 1160 // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y) 1161 if (N0.getOperand(1).getOpcode() == ISD::SUB && 1162 N1.getOperand(1) == N0.getOperand(1).getOperand(1)) 1163 if (ConstantSDNode *SUBC = 1164 dyn_cast<ConstantSDNode>(N0.getOperand(1).getOperand(0))) 1165 if (SUBC->getValue() == OpSizeInBits) { 1166 if (TLI.isOperationLegal(ISD::ROTR, VT) && TLI.isTypeLegal(VT)) 1167 return DAG.getNode(ISD::ROTR, VT, N0.getOperand(0), 1168 N1.getOperand(1)); 1169 else 1170 return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), 1171 N0.getOperand(1)); 1172 } 1173 } 1174 return SDOperand(); 1175} 1176 1177SDOperand DAGCombiner::visitXOR(SDNode *N) { 1178 SDOperand N0 = N->getOperand(0); 1179 SDOperand N1 = N->getOperand(1); 1180 SDOperand LHS, RHS, CC; 1181 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1182 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1183 MVT::ValueType VT = N0.getValueType(); 1184 1185 // fold (xor c1, c2) -> c1^c2 1186 if (N0C && N1C) 1187 return DAG.getNode(ISD::XOR, VT, N0, N1); 1188 // canonicalize constant to RHS 1189 if (N0C && !N1C) 1190 return DAG.getNode(ISD::XOR, VT, N1, N0); 1191 // fold (xor x, 0) -> x 1192 if (N1C && N1C->isNullValue()) 1193 return N0; 1194 // reassociate xor 1195 SDOperand RXOR = ReassociateOps(ISD::XOR, N0, N1); 1196 if (RXOR.Val != 0) 1197 return RXOR; 1198 // fold !(x cc y) -> (x !cc y) 1199 if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) { 1200 bool isInt = MVT::isInteger(LHS.getValueType()); 1201 ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(), 1202 isInt); 1203 if (N0.getOpcode() == ISD::SETCC) 1204 return DAG.getSetCC(VT, LHS, RHS, NotCC); 1205 if (N0.getOpcode() == ISD::SELECT_CC) 1206 return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC); 1207 assert(0 && "Unhandled SetCC Equivalent!"); 1208 abort(); 1209 } 1210 // fold !(x or y) -> (!x and !y) iff x or y are setcc 1211 if (N1C && N1C->getValue() == 1 && 1212 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1213 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1214 if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) { 1215 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1216 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1217 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1218 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 1219 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1220 } 1221 } 1222 // fold !(x or y) -> (!x and !y) iff x or y are constants 1223 if (N1C && N1C->isAllOnesValue() && 1224 (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) { 1225 SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1); 1226 if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) { 1227 unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND; 1228 LHS = DAG.getNode(ISD::XOR, VT, LHS, N1); // RHS = ~LHS 1229 RHS = DAG.getNode(ISD::XOR, VT, RHS, N1); // RHS = ~RHS 1230 WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val); 1231 return DAG.getNode(NewOpcode, VT, LHS, RHS); 1232 } 1233 } 1234 // fold (xor (xor x, c1), c2) -> (xor x, c1^c2) 1235 if (N1C && N0.getOpcode() == ISD::XOR) { 1236 ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0)); 1237 ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1)); 1238 if (N00C) 1239 return DAG.getNode(ISD::XOR, VT, N0.getOperand(1), 1240 DAG.getConstant(N1C->getValue()^N00C->getValue(), VT)); 1241 if (N01C) 1242 return DAG.getNode(ISD::XOR, VT, N0.getOperand(0), 1243 DAG.getConstant(N1C->getValue()^N01C->getValue(), VT)); 1244 } 1245 // fold (xor x, x) -> 0 1246 if (N0 == N1) 1247 return DAG.getConstant(0, VT); 1248 // fold (xor (zext x), (zext y)) -> (zext (xor x, y)) 1249 if (N0.getOpcode() == ISD::ZERO_EXTEND && 1250 N1.getOpcode() == ISD::ZERO_EXTEND && 1251 N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) { 1252 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(), 1253 N0.getOperand(0), N1.getOperand(0)); 1254 WorkList.push_back(XORNode.Val); 1255 return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode); 1256 } 1257 // fold (xor (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (xor x, y)) 1258 if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) || 1259 (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) || 1260 (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) && 1261 N0.getOperand(1) == N1.getOperand(1)) { 1262 SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(), 1263 N0.getOperand(0), N1.getOperand(0)); 1264 WorkList.push_back(XORNode.Val); 1265 return DAG.getNode(N0.getOpcode(), VT, XORNode, N0.getOperand(1)); 1266 } 1267 return SDOperand(); 1268} 1269 1270SDOperand DAGCombiner::visitSHL(SDNode *N) { 1271 SDOperand N0 = N->getOperand(0); 1272 SDOperand N1 = N->getOperand(1); 1273 SDOperand Old = SDOperand(); 1274 SDOperand New = SDOperand(); 1275 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1276 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1277 MVT::ValueType VT = N0.getValueType(); 1278 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1279 1280 // fold (shl c1, c2) -> c1<<c2 1281 if (N0C && N1C) 1282 return DAG.getNode(ISD::SHL, VT, N0, N1); 1283 // fold (shl 0, x) -> 0 1284 if (N0C && N0C->isNullValue()) 1285 return N0; 1286 // fold (shl x, c >= size(x)) -> undef 1287 if (N1C && N1C->getValue() >= OpSizeInBits) 1288 return DAG.getNode(ISD::UNDEF, VT); 1289 // fold (shl x, 0) -> x 1290 if (N1C && N1C->isNullValue()) 1291 return N0; 1292 // if (shl x, c) is known to be zero, return 0 1293 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) 1294 return DAG.getConstant(0, VT); 1295 if (N1C && TLI.DemandedBitsAreZero(SDOperand(N,0), ~0ULL >> (64-OpSizeInBits), 1296 Old, New, DAG)) { 1297 WorkList.push_back(N); 1298 CombineTo(Old.Val, New); 1299 return SDOperand(); 1300 } 1301 // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2) 1302 if (N1C && N0.getOpcode() == ISD::SHL && 1303 N0.getOperand(1).getOpcode() == ISD::Constant) { 1304 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1305 uint64_t c2 = N1C->getValue(); 1306 if (c1 + c2 > OpSizeInBits) 1307 return DAG.getConstant(0, VT); 1308 return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 1309 DAG.getConstant(c1 + c2, N1.getValueType())); 1310 } 1311 // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or 1312 // (srl (and x, -1 << c1), c1-c2) 1313 if (N1C && N0.getOpcode() == ISD::SRL && 1314 N0.getOperand(1).getOpcode() == ISD::Constant) { 1315 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1316 uint64_t c2 = N1C->getValue(); 1317 SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1318 DAG.getConstant(~0ULL << c1, VT)); 1319 if (c2 > c1) 1320 return DAG.getNode(ISD::SHL, VT, Mask, 1321 DAG.getConstant(c2-c1, N1.getValueType())); 1322 else 1323 return DAG.getNode(ISD::SRL, VT, Mask, 1324 DAG.getConstant(c1-c2, N1.getValueType())); 1325 } 1326 // fold (shl (sra x, c1), c1) -> (and x, -1 << c1) 1327 if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1)) 1328 return DAG.getNode(ISD::AND, VT, N0.getOperand(0), 1329 DAG.getConstant(~0ULL << N1C->getValue(), VT)); 1330 return SDOperand(); 1331} 1332 1333SDOperand DAGCombiner::visitSRA(SDNode *N) { 1334 SDOperand N0 = N->getOperand(0); 1335 SDOperand N1 = N->getOperand(1); 1336 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1337 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1338 MVT::ValueType VT = N0.getValueType(); 1339 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1340 1341 // fold (sra c1, c2) -> c1>>c2 1342 if (N0C && N1C) 1343 return DAG.getNode(ISD::SRA, VT, N0, N1); 1344 // fold (sra 0, x) -> 0 1345 if (N0C && N0C->isNullValue()) 1346 return N0; 1347 // fold (sra -1, x) -> -1 1348 if (N0C && N0C->isAllOnesValue()) 1349 return N0; 1350 // fold (sra x, c >= size(x)) -> undef 1351 if (N1C && N1C->getValue() >= OpSizeInBits) 1352 return DAG.getNode(ISD::UNDEF, VT); 1353 // fold (sra x, 0) -> x 1354 if (N1C && N1C->isNullValue()) 1355 return N0; 1356 // If the sign bit is known to be zero, switch this to a SRL. 1357 if (TLI.MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)))) 1358 return DAG.getNode(ISD::SRL, VT, N0, N1); 1359 return SDOperand(); 1360} 1361 1362SDOperand DAGCombiner::visitSRL(SDNode *N) { 1363 SDOperand N0 = N->getOperand(0); 1364 SDOperand N1 = N->getOperand(1); 1365 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1366 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1367 MVT::ValueType VT = N0.getValueType(); 1368 unsigned OpSizeInBits = MVT::getSizeInBits(VT); 1369 1370 // fold (srl c1, c2) -> c1 >>u c2 1371 if (N0C && N1C) 1372 return DAG.getNode(ISD::SRL, VT, N0, N1); 1373 // fold (srl 0, x) -> 0 1374 if (N0C && N0C->isNullValue()) 1375 return N0; 1376 // fold (srl x, c >= size(x)) -> undef 1377 if (N1C && N1C->getValue() >= OpSizeInBits) 1378 return DAG.getNode(ISD::UNDEF, VT); 1379 // fold (srl x, 0) -> x 1380 if (N1C && N1C->isNullValue()) 1381 return N0; 1382 // if (srl x, c) is known to be zero, return 0 1383 if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits))) 1384 return DAG.getConstant(0, VT); 1385 // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2) 1386 if (N1C && N0.getOpcode() == ISD::SRL && 1387 N0.getOperand(1).getOpcode() == ISD::Constant) { 1388 uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue(); 1389 uint64_t c2 = N1C->getValue(); 1390 if (c1 + c2 > OpSizeInBits) 1391 return DAG.getConstant(0, VT); 1392 return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 1393 DAG.getConstant(c1 + c2, N1.getValueType())); 1394 } 1395 return SDOperand(); 1396} 1397 1398SDOperand DAGCombiner::visitCTLZ(SDNode *N) { 1399 SDOperand N0 = N->getOperand(0); 1400 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1401 MVT::ValueType VT = N->getValueType(0); 1402 1403 // fold (ctlz c1) -> c2 1404 if (N0C) 1405 return DAG.getNode(ISD::CTLZ, VT, N0); 1406 return SDOperand(); 1407} 1408 1409SDOperand DAGCombiner::visitCTTZ(SDNode *N) { 1410 SDOperand N0 = N->getOperand(0); 1411 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1412 MVT::ValueType VT = N->getValueType(0); 1413 1414 // fold (cttz c1) -> c2 1415 if (N0C) 1416 return DAG.getNode(ISD::CTTZ, VT, N0); 1417 return SDOperand(); 1418} 1419 1420SDOperand DAGCombiner::visitCTPOP(SDNode *N) { 1421 SDOperand N0 = N->getOperand(0); 1422 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1423 MVT::ValueType VT = N->getValueType(0); 1424 1425 // fold (ctpop c1) -> c2 1426 if (N0C) 1427 return DAG.getNode(ISD::CTPOP, VT, N0); 1428 return SDOperand(); 1429} 1430 1431SDOperand DAGCombiner::visitSELECT(SDNode *N) { 1432 SDOperand N0 = N->getOperand(0); 1433 SDOperand N1 = N->getOperand(1); 1434 SDOperand N2 = N->getOperand(2); 1435 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1436 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1437 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1438 MVT::ValueType VT = N->getValueType(0); 1439 1440 // fold select C, X, X -> X 1441 if (N1 == N2) 1442 return N1; 1443 // fold select true, X, Y -> X 1444 if (N0C && !N0C->isNullValue()) 1445 return N1; 1446 // fold select false, X, Y -> Y 1447 if (N0C && N0C->isNullValue()) 1448 return N2; 1449 // fold select C, 1, X -> C | X 1450 if (MVT::i1 == VT && N1C && N1C->getValue() == 1) 1451 return DAG.getNode(ISD::OR, VT, N0, N2); 1452 // fold select C, 0, X -> ~C & X 1453 // FIXME: this should check for C type == X type, not i1? 1454 if (MVT::i1 == VT && N1C && N1C->isNullValue()) { 1455 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1456 WorkList.push_back(XORNode.Val); 1457 return DAG.getNode(ISD::AND, VT, XORNode, N2); 1458 } 1459 // fold select C, X, 1 -> ~C | X 1460 if (MVT::i1 == VT && N2C && N2C->getValue() == 1) { 1461 SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT)); 1462 WorkList.push_back(XORNode.Val); 1463 return DAG.getNode(ISD::OR, VT, XORNode, N1); 1464 } 1465 // fold select C, X, 0 -> C & X 1466 // FIXME: this should check for C type == X type, not i1? 1467 if (MVT::i1 == VT && N2C && N2C->isNullValue()) 1468 return DAG.getNode(ISD::AND, VT, N0, N1); 1469 // fold X ? X : Y --> X ? 1 : Y --> X | Y 1470 if (MVT::i1 == VT && N0 == N1) 1471 return DAG.getNode(ISD::OR, VT, N0, N2); 1472 // fold X ? Y : X --> X ? Y : 0 --> X & Y 1473 if (MVT::i1 == VT && N0 == N2) 1474 return DAG.getNode(ISD::AND, VT, N0, N1); 1475 // If we can fold this based on the true/false value, do so. 1476 if (SimplifySelectOps(N, N1, N2)) 1477 return SDOperand(); 1478 // fold selects based on a setcc into other things, such as min/max/abs 1479 if (N0.getOpcode() == ISD::SETCC) 1480 // FIXME: 1481 // Check against MVT::Other for SELECT_CC, which is a workaround for targets 1482 // having to say they don't support SELECT_CC on every type the DAG knows 1483 // about, since there is no way to mark an opcode illegal at all value types 1484 if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other)) 1485 return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1), 1486 N1, N2, N0.getOperand(2)); 1487 else 1488 return SimplifySelect(N0, N1, N2); 1489 return SDOperand(); 1490} 1491 1492SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) { 1493 SDOperand N0 = N->getOperand(0); 1494 SDOperand N1 = N->getOperand(1); 1495 SDOperand N2 = N->getOperand(2); 1496 SDOperand N3 = N->getOperand(3); 1497 SDOperand N4 = N->getOperand(4); 1498 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1499 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 1500 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2); 1501 ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get(); 1502 1503 // Determine if the condition we're dealing with is constant 1504 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 1505 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 1506 1507 // fold select_cc lhs, rhs, x, x, cc -> x 1508 if (N2 == N3) 1509 return N2; 1510 1511 // If we can fold this based on the true/false value, do so. 1512 if (SimplifySelectOps(N, N2, N3)) 1513 return SDOperand(); 1514 1515 // fold select_cc into other things, such as min/max/abs 1516 return SimplifySelectCC(N0, N1, N2, N3, CC); 1517} 1518 1519SDOperand DAGCombiner::visitSETCC(SDNode *N) { 1520 return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1), 1521 cast<CondCodeSDNode>(N->getOperand(2))->get()); 1522} 1523 1524SDOperand DAGCombiner::visitADD_PARTS(SDNode *N) { 1525 SDOperand LHSLo = N->getOperand(0); 1526 SDOperand RHSLo = N->getOperand(2); 1527 MVT::ValueType VT = LHSLo.getValueType(); 1528 1529 // fold (a_Hi, 0) + (b_Hi, b_Lo) -> (b_Hi + a_Hi, b_Lo) 1530 if (TLI.MaskedValueIsZero(LHSLo, (1ULL << MVT::getSizeInBits(VT))-1)) { 1531 SDOperand Hi = DAG.getNode(ISD::ADD, VT, N->getOperand(1), 1532 N->getOperand(3)); 1533 WorkList.push_back(Hi.Val); 1534 CombineTo(N, RHSLo, Hi); 1535 return SDOperand(); 1536 } 1537 // fold (a_Hi, a_Lo) + (b_Hi, 0) -> (a_Hi + b_Hi, a_Lo) 1538 if (TLI.MaskedValueIsZero(RHSLo, (1ULL << MVT::getSizeInBits(VT))-1)) { 1539 SDOperand Hi = DAG.getNode(ISD::ADD, VT, N->getOperand(1), 1540 N->getOperand(3)); 1541 WorkList.push_back(Hi.Val); 1542 CombineTo(N, LHSLo, Hi); 1543 return SDOperand(); 1544 } 1545 return SDOperand(); 1546} 1547 1548SDOperand DAGCombiner::visitSUB_PARTS(SDNode *N) { 1549 SDOperand LHSLo = N->getOperand(0); 1550 SDOperand RHSLo = N->getOperand(2); 1551 MVT::ValueType VT = LHSLo.getValueType(); 1552 1553 // fold (a_Hi, a_Lo) - (b_Hi, 0) -> (a_Hi - b_Hi, a_Lo) 1554 if (TLI.MaskedValueIsZero(RHSLo, (1ULL << MVT::getSizeInBits(VT))-1)) { 1555 SDOperand Hi = DAG.getNode(ISD::SUB, VT, N->getOperand(1), 1556 N->getOperand(3)); 1557 WorkList.push_back(Hi.Val); 1558 CombineTo(N, LHSLo, Hi); 1559 return SDOperand(); 1560 } 1561 return SDOperand(); 1562} 1563 1564SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) { 1565 SDOperand N0 = N->getOperand(0); 1566 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1567 MVT::ValueType VT = N->getValueType(0); 1568 1569 // fold (sext c1) -> c1 1570 if (N0C) 1571 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0); 1572 // fold (sext (sext x)) -> (sext x) 1573 if (N0.getOpcode() == ISD::SIGN_EXTEND) 1574 return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)); 1575 // fold (sext (truncate x)) -> (sextinreg x) iff x size == sext size. 1576 if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&& 1577 (!AfterLegalize || 1578 TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, N0.getValueType()))) 1579 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), 1580 DAG.getValueType(N0.getValueType())); 1581 // fold (sext (load x)) -> (sext (truncate (sextload x))) 1582 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 1583 (!AfterLegalize||TLI.isOperationLegal(ISD::SEXTLOAD, N0.getValueType()))){ 1584 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1585 N0.getOperand(1), N0.getOperand(2), 1586 N0.getValueType()); 1587 CombineTo(N, ExtLoad); 1588 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1589 ExtLoad.getValue(1)); 1590 return SDOperand(); 1591 } 1592 1593 // fold (sext (sextload x)) -> (sext (truncate (sextload x))) 1594 // fold (sext ( extload x)) -> (sext (truncate (sextload x))) 1595 if ((N0.getOpcode() == ISD::SEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) && 1596 N0.hasOneUse()) { 1597 SDOperand ExtLoad = DAG.getNode(ISD::SEXTLOAD, VT, N0.getOperand(0), 1598 N0.getOperand(1), N0.getOperand(2), 1599 N0.getOperand(3)); 1600 CombineTo(N, ExtLoad); 1601 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1602 ExtLoad.getValue(1)); 1603 return SDOperand(); 1604 } 1605 1606 return SDOperand(); 1607} 1608 1609SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) { 1610 SDOperand N0 = N->getOperand(0); 1611 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1612 MVT::ValueType VT = N->getValueType(0); 1613 1614 // fold (zext c1) -> c1 1615 if (N0C) 1616 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 1617 // fold (zext (zext x)) -> (zext x) 1618 if (N0.getOpcode() == ISD::ZERO_EXTEND) 1619 return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)); 1620 // fold (zext (truncate x)) -> (zextinreg x) iff x size == zext size. 1621 if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&& 1622 (!AfterLegalize || TLI.isOperationLegal(ISD::AND, N0.getValueType()))) 1623 return DAG.getZeroExtendInReg(N0.getOperand(0), N0.getValueType()); 1624 // fold (zext (load x)) -> (zext (truncate (zextload x))) 1625 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() && 1626 (!AfterLegalize||TLI.isOperationLegal(ISD::ZEXTLOAD, N0.getValueType()))){ 1627 SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1628 N0.getOperand(1), N0.getOperand(2), 1629 N0.getValueType()); 1630 CombineTo(N, ExtLoad); 1631 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1632 ExtLoad.getValue(1)); 1633 return SDOperand(); 1634 } 1635 1636 // fold (zext (zextload x)) -> (zext (truncate (zextload x))) 1637 // fold (zext ( extload x)) -> (zext (truncate (zextload x))) 1638 if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) && 1639 N0.hasOneUse()) { 1640 SDOperand ExtLoad = DAG.getNode(ISD::ZEXTLOAD, VT, N0.getOperand(0), 1641 N0.getOperand(1), N0.getOperand(2), 1642 N0.getOperand(3)); 1643 CombineTo(N, ExtLoad); 1644 CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad), 1645 ExtLoad.getValue(1)); 1646 return SDOperand(); 1647 } 1648 return SDOperand(); 1649} 1650 1651SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { 1652 SDOperand N0 = N->getOperand(0); 1653 SDOperand N1 = N->getOperand(1); 1654 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1655 MVT::ValueType VT = N->getValueType(0); 1656 MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT(); 1657 unsigned EVTBits = MVT::getSizeInBits(EVT); 1658 1659 // fold (sext_in_reg c1) -> c1 1660 if (N0C) { 1661 SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT); 1662 return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate); 1663 } 1664 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1 1665 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1666 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) { 1667 return N0; 1668 } 1669 // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2 1670 if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 1671 EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) { 1672 return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1); 1673 } 1674 // fold (sext_in_reg (assert_sext x)) -> (assert_sext x) 1675 if (N0.getOpcode() == ISD::AssertSext && 1676 cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) { 1677 return N0; 1678 } 1679 // fold (sext_in_reg (sextload x)) -> (sextload x) 1680 if (N0.getOpcode() == ISD::SEXTLOAD && 1681 cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) { 1682 return N0; 1683 } 1684 // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1 1685 if (N0.getOpcode() == ISD::SETCC && 1686 TLI.getSetCCResultContents() == 1687 TargetLowering::ZeroOrNegativeOneSetCCResult) 1688 return N0; 1689 // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero 1690 if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1))) 1691 return DAG.getZeroExtendInReg(N0, EVT); 1692 // fold (sext_in_reg (srl x)) -> sra x 1693 if (N0.getOpcode() == ISD::SRL && 1694 N0.getOperand(1).getOpcode() == ISD::Constant && 1695 cast<ConstantSDNode>(N0.getOperand(1))->getValue() == EVTBits) { 1696 return DAG.getNode(ISD::SRA, N0.getValueType(), N0.getOperand(0), 1697 N0.getOperand(1)); 1698 } 1699 // fold (sext_inreg (extload x)) -> (sextload x) 1700 if (N0.getOpcode() == ISD::EXTLOAD && 1701 EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() && 1702 (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) { 1703 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1704 N0.getOperand(1), N0.getOperand(2), 1705 EVT); 1706 CombineTo(N, ExtLoad); 1707 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1708 return SDOperand(); 1709 } 1710 // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use 1711 if (N0.getOpcode() == ISD::ZEXTLOAD && N0.hasOneUse() && 1712 EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() && 1713 (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) { 1714 SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0), 1715 N0.getOperand(1), N0.getOperand(2), 1716 EVT); 1717 CombineTo(N, ExtLoad); 1718 CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1)); 1719 return SDOperand(); 1720 } 1721 return SDOperand(); 1722} 1723 1724SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) { 1725 SDOperand N0 = N->getOperand(0); 1726 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1727 MVT::ValueType VT = N->getValueType(0); 1728 1729 // noop truncate 1730 if (N0.getValueType() == N->getValueType(0)) 1731 return N0; 1732 // fold (truncate c1) -> c1 1733 if (N0C) 1734 return DAG.getNode(ISD::TRUNCATE, VT, N0); 1735 // fold (truncate (truncate x)) -> (truncate x) 1736 if (N0.getOpcode() == ISD::TRUNCATE) 1737 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1738 // fold (truncate (ext x)) -> (ext x) or (truncate x) or x 1739 if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){ 1740 if (N0.getValueType() < VT) 1741 // if the source is smaller than the dest, we still need an extend 1742 return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)); 1743 else if (N0.getValueType() > VT) 1744 // if the source is larger than the dest, than we just need the truncate 1745 return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)); 1746 else 1747 // if the source and dest are the same type, we can drop both the extend 1748 // and the truncate 1749 return N0.getOperand(0); 1750 } 1751 // fold (truncate (load x)) -> (smaller load x) 1752 if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) { 1753 assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) && 1754 "Cannot truncate to larger type!"); 1755 MVT::ValueType PtrType = N0.getOperand(1).getValueType(); 1756 // For big endian targets, we need to add an offset to the pointer to load 1757 // the correct bytes. For little endian systems, we merely need to read 1758 // fewer bytes from the same pointer. 1759 uint64_t PtrOff = 1760 (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8; 1761 SDOperand NewPtr = TLI.isLittleEndian() ? N0.getOperand(1) : 1762 DAG.getNode(ISD::ADD, PtrType, N0.getOperand(1), 1763 DAG.getConstant(PtrOff, PtrType)); 1764 WorkList.push_back(NewPtr.Val); 1765 SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), NewPtr,N0.getOperand(2)); 1766 WorkList.push_back(N); 1767 CombineTo(N0.Val, Load, Load.getValue(1)); 1768 return SDOperand(); 1769 } 1770 return SDOperand(); 1771} 1772 1773SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) { 1774 SDOperand N0 = N->getOperand(0); 1775 MVT::ValueType VT = N->getValueType(0); 1776 1777 // If the input is a constant, let getNode() fold it. 1778 if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) { 1779 SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0); 1780 if (Res.Val != N) return Res; 1781 } 1782 1783 if (N0.getOpcode() == ISD::BIT_CONVERT) // conv(conv(x,t1),t2) -> conv(x,t2) 1784 return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0)); 1785 1786 // fold (conv (load x)) -> (load (conv*)x) 1787 // FIXME: These xforms need to know that the resultant load doesn't need a 1788 // higher alignment than the original! 1789 if (0 && N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) { 1790 SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), N0.getOperand(1), 1791 N0.getOperand(2)); 1792 WorkList.push_back(N); 1793 CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load), 1794 Load.getValue(1)); 1795 return Load; 1796 } 1797 1798 return SDOperand(); 1799} 1800 1801SDOperand DAGCombiner::visitFADD(SDNode *N) { 1802 SDOperand N0 = N->getOperand(0); 1803 SDOperand N1 = N->getOperand(1); 1804 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1805 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 1806 MVT::ValueType VT = N->getValueType(0); 1807 1808 // fold (fadd c1, c2) -> c1+c2 1809 if (N0CFP && N1CFP) 1810 return DAG.getNode(ISD::FADD, VT, N0, N1); 1811 // canonicalize constant to RHS 1812 if (N0CFP && !N1CFP) 1813 return DAG.getNode(ISD::FADD, VT, N1, N0); 1814 // fold (A + (-B)) -> A-B 1815 if (N1.getOpcode() == ISD::FNEG) 1816 return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0)); 1817 // fold ((-A) + B) -> B-A 1818 if (N0.getOpcode() == ISD::FNEG) 1819 return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0)); 1820 return SDOperand(); 1821} 1822 1823SDOperand DAGCombiner::visitFSUB(SDNode *N) { 1824 SDOperand N0 = N->getOperand(0); 1825 SDOperand N1 = N->getOperand(1); 1826 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1827 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 1828 MVT::ValueType VT = N->getValueType(0); 1829 1830 // fold (fsub c1, c2) -> c1-c2 1831 if (N0CFP && N1CFP) 1832 return DAG.getNode(ISD::FSUB, VT, N0, N1); 1833 // fold (A-(-B)) -> A+B 1834 if (N1.getOpcode() == ISD::FNEG) 1835 return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0)); 1836 return SDOperand(); 1837} 1838 1839SDOperand DAGCombiner::visitFMUL(SDNode *N) { 1840 SDOperand N0 = N->getOperand(0); 1841 SDOperand N1 = N->getOperand(1); 1842 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1843 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 1844 MVT::ValueType VT = N->getValueType(0); 1845 1846 // fold (fmul c1, c2) -> c1*c2 1847 if (N0CFP && N1CFP) 1848 return DAG.getNode(ISD::FMUL, VT, N0, N1); 1849 // canonicalize constant to RHS 1850 if (N0CFP && !N1CFP) 1851 return DAG.getNode(ISD::FMUL, VT, N1, N0); 1852 // fold (fmul X, 2.0) -> (fadd X, X) 1853 if (N1CFP && N1CFP->isExactlyValue(+2.0)) 1854 return DAG.getNode(ISD::FADD, VT, N0, N0); 1855 return SDOperand(); 1856} 1857 1858SDOperand DAGCombiner::visitFDIV(SDNode *N) { 1859 SDOperand N0 = N->getOperand(0); 1860 SDOperand N1 = N->getOperand(1); 1861 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1862 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 1863 MVT::ValueType VT = N->getValueType(0); 1864 1865 // fold (fdiv c1, c2) -> c1/c2 1866 if (N0CFP && N1CFP) 1867 return DAG.getNode(ISD::FDIV, VT, N0, N1); 1868 return SDOperand(); 1869} 1870 1871SDOperand DAGCombiner::visitFREM(SDNode *N) { 1872 SDOperand N0 = N->getOperand(0); 1873 SDOperand N1 = N->getOperand(1); 1874 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1875 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1); 1876 MVT::ValueType VT = N->getValueType(0); 1877 1878 // fold (frem c1, c2) -> fmod(c1,c2) 1879 if (N0CFP && N1CFP) 1880 return DAG.getNode(ISD::FREM, VT, N0, N1); 1881 return SDOperand(); 1882} 1883 1884 1885SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) { 1886 SDOperand N0 = N->getOperand(0); 1887 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1888 MVT::ValueType VT = N->getValueType(0); 1889 1890 // fold (sint_to_fp c1) -> c1fp 1891 if (N0C) 1892 return DAG.getNode(ISD::SINT_TO_FP, VT, N0); 1893 return SDOperand(); 1894} 1895 1896SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) { 1897 SDOperand N0 = N->getOperand(0); 1898 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); 1899 MVT::ValueType VT = N->getValueType(0); 1900 1901 // fold (uint_to_fp c1) -> c1fp 1902 if (N0C) 1903 return DAG.getNode(ISD::UINT_TO_FP, VT, N0); 1904 return SDOperand(); 1905} 1906 1907SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) { 1908 SDOperand N0 = N->getOperand(0); 1909 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1910 MVT::ValueType VT = N->getValueType(0); 1911 1912 // fold (fp_to_sint c1fp) -> c1 1913 if (N0CFP) 1914 return DAG.getNode(ISD::FP_TO_SINT, VT, N0); 1915 return SDOperand(); 1916} 1917 1918SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) { 1919 SDOperand N0 = N->getOperand(0); 1920 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1921 MVT::ValueType VT = N->getValueType(0); 1922 1923 // fold (fp_to_uint c1fp) -> c1 1924 if (N0CFP) 1925 return DAG.getNode(ISD::FP_TO_UINT, VT, N0); 1926 return SDOperand(); 1927} 1928 1929SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) { 1930 SDOperand N0 = N->getOperand(0); 1931 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1932 MVT::ValueType VT = N->getValueType(0); 1933 1934 // fold (fp_round c1fp) -> c1fp 1935 if (N0CFP) 1936 return DAG.getNode(ISD::FP_ROUND, VT, N0); 1937 return SDOperand(); 1938} 1939 1940SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) { 1941 SDOperand N0 = N->getOperand(0); 1942 MVT::ValueType VT = N->getValueType(0); 1943 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 1944 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1945 1946 // fold (fp_round_inreg c1fp) -> c1fp 1947 if (N0CFP) { 1948 SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT); 1949 return DAG.getNode(ISD::FP_EXTEND, VT, Round); 1950 } 1951 return SDOperand(); 1952} 1953 1954SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) { 1955 SDOperand N0 = N->getOperand(0); 1956 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1957 MVT::ValueType VT = N->getValueType(0); 1958 1959 // fold (fp_extend c1fp) -> c1fp 1960 if (N0CFP) 1961 return DAG.getNode(ISD::FP_EXTEND, VT, N0); 1962 return SDOperand(); 1963} 1964 1965SDOperand DAGCombiner::visitFNEG(SDNode *N) { 1966 SDOperand N0 = N->getOperand(0); 1967 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1968 MVT::ValueType VT = N->getValueType(0); 1969 1970 // fold (fneg c1) -> -c1 1971 if (N0CFP) 1972 return DAG.getNode(ISD::FNEG, VT, N0); 1973 // fold (fneg (sub x, y)) -> (sub y, x) 1974 if (N->getOperand(0).getOpcode() == ISD::SUB) 1975 return DAG.getNode(ISD::SUB, VT, N->getOperand(1), N->getOperand(0)); 1976 // fold (fneg (fneg x)) -> x 1977 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1978 return N->getOperand(0).getOperand(0); 1979 return SDOperand(); 1980} 1981 1982SDOperand DAGCombiner::visitFABS(SDNode *N) { 1983 SDOperand N0 = N->getOperand(0); 1984 ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0); 1985 MVT::ValueType VT = N->getValueType(0); 1986 1987 // fold (fabs c1) -> fabs(c1) 1988 if (N0CFP) 1989 return DAG.getNode(ISD::FABS, VT, N0); 1990 // fold (fabs (fabs x)) -> (fabs x) 1991 if (N->getOperand(0).getOpcode() == ISD::FABS) 1992 return N->getOperand(0); 1993 // fold (fabs (fneg x)) -> (fabs x) 1994 if (N->getOperand(0).getOpcode() == ISD::FNEG) 1995 return DAG.getNode(ISD::FABS, VT, N->getOperand(0).getOperand(0)); 1996 return SDOperand(); 1997} 1998 1999SDOperand DAGCombiner::visitBRCOND(SDNode *N) { 2000 SDOperand Chain = N->getOperand(0); 2001 SDOperand N1 = N->getOperand(1); 2002 SDOperand N2 = N->getOperand(2); 2003 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2004 2005 // never taken branch, fold to chain 2006 if (N1C && N1C->isNullValue()) 2007 return Chain; 2008 // unconditional branch 2009 if (N1C && N1C->getValue() == 1) 2010 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 2011 // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal 2012 // on the target. 2013 if (N1.getOpcode() == ISD::SETCC && 2014 TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) { 2015 return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2), 2016 N1.getOperand(0), N1.getOperand(1), N2); 2017 } 2018 return SDOperand(); 2019} 2020 2021SDOperand DAGCombiner::visitBRCONDTWOWAY(SDNode *N) { 2022 SDOperand Chain = N->getOperand(0); 2023 SDOperand N1 = N->getOperand(1); 2024 SDOperand N2 = N->getOperand(2); 2025 SDOperand N3 = N->getOperand(3); 2026 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); 2027 2028 // unconditional branch to true mbb 2029 if (N1C && N1C->getValue() == 1) 2030 return DAG.getNode(ISD::BR, MVT::Other, Chain, N2); 2031 // unconditional branch to false mbb 2032 if (N1C && N1C->isNullValue()) 2033 return DAG.getNode(ISD::BR, MVT::Other, Chain, N3); 2034 // fold a brcondtwoway with a setcc condition into a BRTWOWAY_CC node if 2035 // BRTWOWAY_CC is legal on the target. 2036 if (N1.getOpcode() == ISD::SETCC && 2037 TLI.isOperationLegal(ISD::BRTWOWAY_CC, MVT::Other)) { 2038 std::vector<SDOperand> Ops; 2039 Ops.push_back(Chain); 2040 Ops.push_back(N1.getOperand(2)); 2041 Ops.push_back(N1.getOperand(0)); 2042 Ops.push_back(N1.getOperand(1)); 2043 Ops.push_back(N2); 2044 Ops.push_back(N3); 2045 return DAG.getNode(ISD::BRTWOWAY_CC, MVT::Other, Ops); 2046 } 2047 return SDOperand(); 2048} 2049 2050// Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB. 2051// 2052SDOperand DAGCombiner::visitBR_CC(SDNode *N) { 2053 CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1)); 2054 SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3); 2055 2056 // Use SimplifySetCC to simplify SETCC's. 2057 SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false); 2058 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val); 2059 2060 // fold br_cc true, dest -> br dest (unconditional branch) 2061 if (SCCC && SCCC->getValue()) 2062 return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0), 2063 N->getOperand(4)); 2064 // fold br_cc false, dest -> unconditional fall through 2065 if (SCCC && SCCC->isNullValue()) 2066 return N->getOperand(0); 2067 // fold to a simpler setcc 2068 if (Simp.Val && Simp.getOpcode() == ISD::SETCC) 2069 return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 2070 Simp.getOperand(2), Simp.getOperand(0), 2071 Simp.getOperand(1), N->getOperand(4)); 2072 return SDOperand(); 2073} 2074 2075SDOperand DAGCombiner::visitBRTWOWAY_CC(SDNode *N) { 2076 SDOperand Chain = N->getOperand(0); 2077 SDOperand CCN = N->getOperand(1); 2078 SDOperand LHS = N->getOperand(2); 2079 SDOperand RHS = N->getOperand(3); 2080 SDOperand N4 = N->getOperand(4); 2081 SDOperand N5 = N->getOperand(5); 2082 2083 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), LHS, RHS, 2084 cast<CondCodeSDNode>(CCN)->get(), false); 2085 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 2086 2087 // fold select_cc lhs, rhs, x, x, cc -> x 2088 if (N4 == N5) 2089 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 2090 // fold select_cc true, x, y -> x 2091 if (SCCC && SCCC->getValue()) 2092 return DAG.getNode(ISD::BR, MVT::Other, Chain, N4); 2093 // fold select_cc false, x, y -> y 2094 if (SCCC && SCCC->isNullValue()) 2095 return DAG.getNode(ISD::BR, MVT::Other, Chain, N5); 2096 // fold to a simpler setcc 2097 if (SCC.Val && SCC.getOpcode() == ISD::SETCC) { 2098 std::vector<SDOperand> Ops; 2099 Ops.push_back(Chain); 2100 Ops.push_back(SCC.getOperand(2)); 2101 Ops.push_back(SCC.getOperand(0)); 2102 Ops.push_back(SCC.getOperand(1)); 2103 Ops.push_back(N4); 2104 Ops.push_back(N5); 2105 return DAG.getNode(ISD::BRTWOWAY_CC, MVT::Other, Ops); 2106 } 2107 return SDOperand(); 2108} 2109 2110SDOperand DAGCombiner::visitLOAD(SDNode *N) { 2111 SDOperand Chain = N->getOperand(0); 2112 SDOperand Ptr = N->getOperand(1); 2113 SDOperand SrcValue = N->getOperand(2); 2114 2115 // If this load is directly stored, replace the load value with the stored 2116 // value. 2117 // TODO: Handle store large -> read small portion. 2118 // TODO: Handle TRUNCSTORE/EXTLOAD 2119 if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr && 2120 Chain.getOperand(1).getValueType() == N->getValueType(0)) 2121 return CombineTo(N, Chain.getOperand(1), Chain); 2122 2123 return SDOperand(); 2124} 2125 2126SDOperand DAGCombiner::visitSTORE(SDNode *N) { 2127 SDOperand Chain = N->getOperand(0); 2128 SDOperand Value = N->getOperand(1); 2129 SDOperand Ptr = N->getOperand(2); 2130 SDOperand SrcValue = N->getOperand(3); 2131 2132 // If this is a store that kills a previous store, remove the previous store. 2133 if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr && 2134 Chain.Val->hasOneUse() /* Avoid introducing DAG cycles */ && 2135 // Make sure that these stores are the same value type: 2136 // FIXME: we really care that the second store is >= size of the first. 2137 Value.getValueType() == Chain.getOperand(1).getValueType()) { 2138 // Create a new store of Value that replaces both stores. 2139 SDNode *PrevStore = Chain.Val; 2140 if (PrevStore->getOperand(1) == Value) // Same value multiply stored. 2141 return Chain; 2142 SDOperand NewStore = DAG.getNode(ISD::STORE, MVT::Other, 2143 PrevStore->getOperand(0), Value, Ptr, 2144 SrcValue); 2145 CombineTo(N, NewStore); // Nuke this store. 2146 CombineTo(PrevStore, NewStore); // Nuke the previous store. 2147 return SDOperand(N, 0); 2148 } 2149 2150 // If this is a store of a bit convert, store the input value. 2151 // FIXME: This needs to know that the resultant store does not need a 2152 // higher alignment than the original. 2153 if (0 && Value.getOpcode() == ISD::BIT_CONVERT) 2154 return DAG.getNode(ISD::STORE, MVT::Other, Chain, Value.getOperand(0), 2155 Ptr, SrcValue); 2156 2157 return SDOperand(); 2158} 2159 2160SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){ 2161 assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!"); 2162 2163 SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2, 2164 cast<CondCodeSDNode>(N0.getOperand(2))->get()); 2165 // If we got a simplified select_cc node back from SimplifySelectCC, then 2166 // break it down into a new SETCC node, and a new SELECT node, and then return 2167 // the SELECT node, since we were called with a SELECT node. 2168 if (SCC.Val) { 2169 // Check to see if we got a select_cc back (to turn into setcc/select). 2170 // Otherwise, just return whatever node we got back, like fabs. 2171 if (SCC.getOpcode() == ISD::SELECT_CC) { 2172 SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(), 2173 SCC.getOperand(0), SCC.getOperand(1), 2174 SCC.getOperand(4)); 2175 WorkList.push_back(SETCC.Val); 2176 return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2), 2177 SCC.getOperand(3), SETCC); 2178 } 2179 return SCC; 2180 } 2181 return SDOperand(); 2182} 2183 2184/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS 2185/// are the two values being selected between, see if we can simplify the 2186/// select. 2187/// 2188bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS, 2189 SDOperand RHS) { 2190 2191 // If this is a select from two identical things, try to pull the operation 2192 // through the select. 2193 if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){ 2194#if 0 2195 std::cerr << "SELECT: ["; LHS.Val->dump(); 2196 std::cerr << "] ["; RHS.Val->dump(); 2197 std::cerr << "]\n"; 2198#endif 2199 2200 // If this is a load and the token chain is identical, replace the select 2201 // of two loads with a load through a select of the address to load from. 2202 // This triggers in things like "select bool X, 10.0, 123.0" after the FP 2203 // constants have been dropped into the constant pool. 2204 if ((LHS.getOpcode() == ISD::LOAD || 2205 LHS.getOpcode() == ISD::EXTLOAD || 2206 LHS.getOpcode() == ISD::ZEXTLOAD || 2207 LHS.getOpcode() == ISD::SEXTLOAD) && 2208 // Token chains must be identical. 2209 LHS.getOperand(0) == RHS.getOperand(0) && 2210 // If this is an EXTLOAD, the VT's must match. 2211 (LHS.getOpcode() == ISD::LOAD || 2212 LHS.getOperand(3) == RHS.getOperand(3))) { 2213 // FIXME: this conflates two src values, discarding one. This is not 2214 // the right thing to do, but nothing uses srcvalues now. When they do, 2215 // turn SrcValue into a list of locations. 2216 SDOperand Addr; 2217 if (TheSelect->getOpcode() == ISD::SELECT) 2218 Addr = DAG.getNode(ISD::SELECT, LHS.getOperand(1).getValueType(), 2219 TheSelect->getOperand(0), LHS.getOperand(1), 2220 RHS.getOperand(1)); 2221 else 2222 Addr = DAG.getNode(ISD::SELECT_CC, LHS.getOperand(1).getValueType(), 2223 TheSelect->getOperand(0), 2224 TheSelect->getOperand(1), 2225 LHS.getOperand(1), RHS.getOperand(1), 2226 TheSelect->getOperand(4)); 2227 2228 SDOperand Load; 2229 if (LHS.getOpcode() == ISD::LOAD) 2230 Load = DAG.getLoad(TheSelect->getValueType(0), LHS.getOperand(0), 2231 Addr, LHS.getOperand(2)); 2232 else 2233 Load = DAG.getExtLoad(LHS.getOpcode(), TheSelect->getValueType(0), 2234 LHS.getOperand(0), Addr, LHS.getOperand(2), 2235 cast<VTSDNode>(LHS.getOperand(3))->getVT()); 2236 // Users of the select now use the result of the load. 2237 CombineTo(TheSelect, Load); 2238 2239 // Users of the old loads now use the new load's chain. We know the 2240 // old-load value is dead now. 2241 CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1)); 2242 CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1)); 2243 return true; 2244 } 2245 } 2246 2247 return false; 2248} 2249 2250SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 2251 SDOperand N2, SDOperand N3, 2252 ISD::CondCode CC) { 2253 2254 MVT::ValueType VT = N2.getValueType(); 2255 ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val); 2256 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 2257 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 2258 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 2259 2260 // Determine if the condition we're dealing with is constant 2261 SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false); 2262 ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val); 2263 2264 // fold select_cc true, x, y -> x 2265 if (SCCC && SCCC->getValue()) 2266 return N2; 2267 // fold select_cc false, x, y -> y 2268 if (SCCC && SCCC->getValue() == 0) 2269 return N3; 2270 2271 // Check to see if we can simplify the select into an fabs node 2272 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) { 2273 // Allow either -0.0 or 0.0 2274 if (CFP->getValue() == 0.0) { 2275 // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs 2276 if ((CC == ISD::SETGE || CC == ISD::SETGT) && 2277 N0 == N2 && N3.getOpcode() == ISD::FNEG && 2278 N2 == N3.getOperand(0)) 2279 return DAG.getNode(ISD::FABS, VT, N0); 2280 2281 // select (setl[te] X, +/-0.0), fneg(X), X -> fabs 2282 if ((CC == ISD::SETLT || CC == ISD::SETLE) && 2283 N0 == N3 && N2.getOpcode() == ISD::FNEG && 2284 N2.getOperand(0) == N3) 2285 return DAG.getNode(ISD::FABS, VT, N3); 2286 } 2287 } 2288 2289 // Check to see if we can perform the "gzip trick", transforming 2290 // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A 2291 if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() && 2292 MVT::isInteger(N0.getValueType()) && 2293 MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) { 2294 MVT::ValueType XType = N0.getValueType(); 2295 MVT::ValueType AType = N2.getValueType(); 2296 if (XType >= AType) { 2297 // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a 2298 // single-bit constant. 2299 if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) { 2300 unsigned ShCtV = Log2_64(N2C->getValue()); 2301 ShCtV = MVT::getSizeInBits(XType)-ShCtV-1; 2302 SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy()); 2303 SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt); 2304 WorkList.push_back(Shift.Val); 2305 if (XType > AType) { 2306 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 2307 WorkList.push_back(Shift.Val); 2308 } 2309 return DAG.getNode(ISD::AND, AType, Shift, N2); 2310 } 2311 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 2312 DAG.getConstant(MVT::getSizeInBits(XType)-1, 2313 TLI.getShiftAmountTy())); 2314 WorkList.push_back(Shift.Val); 2315 if (XType > AType) { 2316 Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift); 2317 WorkList.push_back(Shift.Val); 2318 } 2319 return DAG.getNode(ISD::AND, AType, Shift, N2); 2320 } 2321 } 2322 2323 // fold select C, 16, 0 -> shl C, 4 2324 if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) && 2325 TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) { 2326 // Get a SetCC of the condition 2327 // FIXME: Should probably make sure that setcc is legal if we ever have a 2328 // target where it isn't. 2329 SDOperand Temp, SCC = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 2330 WorkList.push_back(SCC.Val); 2331 // cast from setcc result type to select result type 2332 if (AfterLegalize) 2333 Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType()); 2334 else 2335 Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC); 2336 WorkList.push_back(Temp.Val); 2337 // shl setcc result by log2 n2c 2338 return DAG.getNode(ISD::SHL, N2.getValueType(), Temp, 2339 DAG.getConstant(Log2_64(N2C->getValue()), 2340 TLI.getShiftAmountTy())); 2341 } 2342 2343 // Check to see if this is the equivalent of setcc 2344 // FIXME: Turn all of these into setcc if setcc if setcc is legal 2345 // otherwise, go ahead with the folds. 2346 if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) { 2347 MVT::ValueType XType = N0.getValueType(); 2348 if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) { 2349 SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC); 2350 if (Res.getValueType() != VT) 2351 Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res); 2352 return Res; 2353 } 2354 2355 // seteq X, 0 -> srl (ctlz X, log2(size(X))) 2356 if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 2357 TLI.isOperationLegal(ISD::CTLZ, XType)) { 2358 SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0); 2359 return DAG.getNode(ISD::SRL, XType, Ctlz, 2360 DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)), 2361 TLI.getShiftAmountTy())); 2362 } 2363 // setgt X, 0 -> srl (and (-X, ~X), size(X)-1) 2364 if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 2365 SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType), 2366 N0); 2367 SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 2368 DAG.getConstant(~0ULL, XType)); 2369 return DAG.getNode(ISD::SRL, XType, 2370 DAG.getNode(ISD::AND, XType, NegN0, NotN0), 2371 DAG.getConstant(MVT::getSizeInBits(XType)-1, 2372 TLI.getShiftAmountTy())); 2373 } 2374 // setgt X, -1 -> xor (srl (X, size(X)-1), 1) 2375 if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) { 2376 SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0, 2377 DAG.getConstant(MVT::getSizeInBits(XType)-1, 2378 TLI.getShiftAmountTy())); 2379 return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType)); 2380 } 2381 } 2382 2383 // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X -> 2384 // Y = sra (X, size(X)-1); xor (add (X, Y), Y) 2385 if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) && 2386 N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) { 2387 if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) { 2388 MVT::ValueType XType = N0.getValueType(); 2389 if (SubC->isNullValue() && MVT::isInteger(XType)) { 2390 SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0, 2391 DAG.getConstant(MVT::getSizeInBits(XType)-1, 2392 TLI.getShiftAmountTy())); 2393 SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift); 2394 WorkList.push_back(Shift.Val); 2395 WorkList.push_back(Add.Val); 2396 return DAG.getNode(ISD::XOR, XType, Add, Shift); 2397 } 2398 } 2399 } 2400 2401 return SDOperand(); 2402} 2403 2404SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0, 2405 SDOperand N1, ISD::CondCode Cond, 2406 bool foldBooleans) { 2407 // These setcc operations always fold. 2408 switch (Cond) { 2409 default: break; 2410 case ISD::SETFALSE: 2411 case ISD::SETFALSE2: return DAG.getConstant(0, VT); 2412 case ISD::SETTRUE: 2413 case ISD::SETTRUE2: return DAG.getConstant(1, VT); 2414 } 2415 2416 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 2417 uint64_t C1 = N1C->getValue(); 2418 if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) { 2419 uint64_t C0 = N0C->getValue(); 2420 2421 // Sign extend the operands if required 2422 if (ISD::isSignedIntSetCC(Cond)) { 2423 C0 = N0C->getSignExtended(); 2424 C1 = N1C->getSignExtended(); 2425 } 2426 2427 switch (Cond) { 2428 default: assert(0 && "Unknown integer setcc!"); 2429 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 2430 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 2431 case ISD::SETULT: return DAG.getConstant(C0 < C1, VT); 2432 case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT); 2433 case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT); 2434 case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT); 2435 case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT); 2436 case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT); 2437 case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT); 2438 case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT); 2439 } 2440 } else { 2441 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 2442 if (N0.getOpcode() == ISD::ZERO_EXTEND) { 2443 unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType()); 2444 2445 // If the comparison constant has bits in the upper part, the 2446 // zero-extended value could never match. 2447 if (C1 & (~0ULL << InSize)) { 2448 unsigned VSize = MVT::getSizeInBits(N0.getValueType()); 2449 switch (Cond) { 2450 case ISD::SETUGT: 2451 case ISD::SETUGE: 2452 case ISD::SETEQ: return DAG.getConstant(0, VT); 2453 case ISD::SETULT: 2454 case ISD::SETULE: 2455 case ISD::SETNE: return DAG.getConstant(1, VT); 2456 case ISD::SETGT: 2457 case ISD::SETGE: 2458 // True if the sign bit of C1 is set. 2459 return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT); 2460 case ISD::SETLT: 2461 case ISD::SETLE: 2462 // True if the sign bit of C1 isn't set. 2463 return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT); 2464 default: 2465 break; 2466 } 2467 } 2468 2469 // Otherwise, we can perform the comparison with the low bits. 2470 switch (Cond) { 2471 case ISD::SETEQ: 2472 case ISD::SETNE: 2473 case ISD::SETUGT: 2474 case ISD::SETUGE: 2475 case ISD::SETULT: 2476 case ISD::SETULE: 2477 return DAG.getSetCC(VT, N0.getOperand(0), 2478 DAG.getConstant(C1, N0.getOperand(0).getValueType()), 2479 Cond); 2480 default: 2481 break; // todo, be more careful with signed comparisons 2482 } 2483 } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 2484 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 2485 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT(); 2486 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 2487 MVT::ValueType ExtDstTy = N0.getValueType(); 2488 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 2489 2490 // If the extended part has any inconsistent bits, it cannot ever 2491 // compare equal. In other words, they have to be all ones or all 2492 // zeros. 2493 uint64_t ExtBits = 2494 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 2495 if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits) 2496 return DAG.getConstant(Cond == ISD::SETNE, VT); 2497 2498 SDOperand ZextOp; 2499 MVT::ValueType Op0Ty = N0.getOperand(0).getValueType(); 2500 if (Op0Ty == ExtSrcTy) { 2501 ZextOp = N0.getOperand(0); 2502 } else { 2503 int64_t Imm = ~0ULL >> (64-ExtSrcTyBits); 2504 ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0), 2505 DAG.getConstant(Imm, Op0Ty)); 2506 } 2507 WorkList.push_back(ZextOp.Val); 2508 // Otherwise, make this a use of a zext. 2509 return DAG.getSetCC(VT, ZextOp, 2510 DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 2511 ExtDstTy), 2512 Cond); 2513 } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) && 2514 (Cond == ISD::SETEQ || Cond == ISD::SETNE) && 2515 (N0.getOpcode() == ISD::XOR || 2516 (N0.getOpcode() == ISD::AND && 2517 N0.getOperand(0).getOpcode() == ISD::XOR && 2518 N0.getOperand(1) == N0.getOperand(0).getOperand(1))) && 2519 isa<ConstantSDNode>(N0.getOperand(1)) && 2520 cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) { 2521 // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We can 2522 // only do this if the top bits are known zero. 2523 if (TLI.MaskedValueIsZero(N1, 2524 MVT::getIntVTBitMask(N0.getValueType())-1)) { 2525 // Okay, get the un-inverted input value. 2526 SDOperand Val; 2527 if (N0.getOpcode() == ISD::XOR) 2528 Val = N0.getOperand(0); 2529 else { 2530 assert(N0.getOpcode() == ISD::AND && 2531 N0.getOperand(0).getOpcode() == ISD::XOR); 2532 // ((X^1)&1)^1 -> X & 1 2533 Val = DAG.getNode(ISD::AND, N0.getValueType(), 2534 N0.getOperand(0).getOperand(0), N0.getOperand(1)); 2535 } 2536 return DAG.getSetCC(VT, Val, N1, 2537 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ); 2538 } 2539 } 2540 2541 uint64_t MinVal, MaxVal; 2542 unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0)); 2543 if (ISD::isSignedIntSetCC(Cond)) { 2544 MinVal = 1ULL << (OperandBitSize-1); 2545 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 2546 MaxVal = ~0ULL >> (65-OperandBitSize); 2547 else 2548 MaxVal = 0; 2549 } else { 2550 MinVal = 0; 2551 MaxVal = ~0ULL >> (64-OperandBitSize); 2552 } 2553 2554 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 2555 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 2556 if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true 2557 --C1; // X >= C0 --> X > (C0-1) 2558 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 2559 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 2560 } 2561 2562 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 2563 if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true 2564 ++C1; // X <= C0 --> X < (C0+1) 2565 return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()), 2566 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 2567 } 2568 2569 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal) 2570 return DAG.getConstant(0, VT); // X < MIN --> false 2571 2572 // Canonicalize setgt X, Min --> setne X, Min 2573 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal) 2574 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 2575 // Canonicalize setlt X, Max --> setne X, Max 2576 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal) 2577 return DAG.getSetCC(VT, N0, N1, ISD::SETNE); 2578 2579 // If we have setult X, 1, turn it into seteq X, 0 2580 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1) 2581 return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()), 2582 ISD::SETEQ); 2583 // If we have setugt X, Max-1, turn it into seteq X, Max 2584 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1) 2585 return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()), 2586 ISD::SETEQ); 2587 2588 // If we have "setcc X, C0", check to see if we can shrink the immediate 2589 // by changing cc. 2590 2591 // SETUGT X, SINTMAX -> SETLT X, 0 2592 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 2593 C1 == (~0ULL >> (65-OperandBitSize))) 2594 return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()), 2595 ISD::SETLT); 2596 2597 // FIXME: Implement the rest of these. 2598 2599 // Fold bit comparisons when we can. 2600 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 2601 VT == N0.getValueType() && N0.getOpcode() == ISD::AND) 2602 if (ConstantSDNode *AndRHS = 2603 dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 2604 if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 2605 // Perform the xform if the AND RHS is a single bit. 2606 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 2607 return DAG.getNode(ISD::SRL, VT, N0, 2608 DAG.getConstant(Log2_64(AndRHS->getValue()), 2609 TLI.getShiftAmountTy())); 2610 } 2611 } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) { 2612 // (X & 8) == 8 --> (X & 8) >> 3 2613 // Perform the xform if C1 is a single bit. 2614 if ((C1 & (C1-1)) == 0) { 2615 return DAG.getNode(ISD::SRL, VT, N0, 2616 DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy())); 2617 } 2618 } 2619 } 2620 } 2621 } else if (isa<ConstantSDNode>(N0.Val)) { 2622 // Ensure that the constant occurs on the RHS. 2623 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 2624 } 2625 2626 if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val)) 2627 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) { 2628 double C0 = N0C->getValue(), C1 = N1C->getValue(); 2629 2630 switch (Cond) { 2631 default: break; // FIXME: Implement the rest of these! 2632 case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT); 2633 case ISD::SETNE: return DAG.getConstant(C0 != C1, VT); 2634 case ISD::SETLT: return DAG.getConstant(C0 < C1, VT); 2635 case ISD::SETGT: return DAG.getConstant(C0 > C1, VT); 2636 case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT); 2637 case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT); 2638 } 2639 } else { 2640 // Ensure that the constant occurs on the RHS. 2641 return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond)); 2642 } 2643 2644 if (N0 == N1) { 2645 // We can always fold X == Y for integer setcc's. 2646 if (MVT::isInteger(N0.getValueType())) 2647 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 2648 unsigned UOF = ISD::getUnorderedFlavor(Cond); 2649 if (UOF == 2) // FP operators that are undefined on NaNs. 2650 return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT); 2651 if (UOF == unsigned(ISD::isTrueWhenEqual(Cond))) 2652 return DAG.getConstant(UOF, VT); 2653 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 2654 // if it is not already. 2655 ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO; 2656 if (NewCond != Cond) 2657 return DAG.getSetCC(VT, N0, N1, NewCond); 2658 } 2659 2660 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 2661 MVT::isInteger(N0.getValueType())) { 2662 if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB || 2663 N0.getOpcode() == ISD::XOR) { 2664 // Simplify (X+Y) == (X+Z) --> Y == Z 2665 if (N0.getOpcode() == N1.getOpcode()) { 2666 if (N0.getOperand(0) == N1.getOperand(0)) 2667 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond); 2668 if (N0.getOperand(1) == N1.getOperand(1)) 2669 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond); 2670 if (isCommutativeBinOp(N0.getOpcode())) { 2671 // If X op Y == Y op X, try other combinations. 2672 if (N0.getOperand(0) == N1.getOperand(1)) 2673 return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond); 2674 if (N0.getOperand(1) == N1.getOperand(0)) 2675 return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond); 2676 } 2677 } 2678 2679 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) { 2680 if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) { 2681 // Turn (X+C1) == C2 --> X == C2-C1 2682 if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) { 2683 return DAG.getSetCC(VT, N0.getOperand(0), 2684 DAG.getConstant(RHSC->getValue()-LHSR->getValue(), 2685 N0.getValueType()), Cond); 2686 } 2687 2688 // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0. 2689 if (N0.getOpcode() == ISD::XOR) 2690 // If we know that all of the inverted bits are zero, don't bother 2691 // performing the inversion. 2692 if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue())) 2693 return DAG.getSetCC(VT, N0.getOperand(0), 2694 DAG.getConstant(LHSR->getValue()^RHSC->getValue(), 2695 N0.getValueType()), Cond); 2696 } 2697 2698 // Turn (C1-X) == C2 --> X == C1-C2 2699 if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) { 2700 if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) { 2701 return DAG.getSetCC(VT, N0.getOperand(1), 2702 DAG.getConstant(SUBC->getValue()-RHSC->getValue(), 2703 N0.getValueType()), Cond); 2704 } 2705 } 2706 } 2707 2708 // Simplify (X+Z) == X --> Z == 0 2709 if (N0.getOperand(0) == N1) 2710 return DAG.getSetCC(VT, N0.getOperand(1), 2711 DAG.getConstant(0, N0.getValueType()), Cond); 2712 if (N0.getOperand(1) == N1) { 2713 if (isCommutativeBinOp(N0.getOpcode())) 2714 return DAG.getSetCC(VT, N0.getOperand(0), 2715 DAG.getConstant(0, N0.getValueType()), Cond); 2716 else { 2717 assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!"); 2718 // (Z-X) == X --> Z == X<<1 2719 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), 2720 N1, 2721 DAG.getConstant(1,TLI.getShiftAmountTy())); 2722 WorkList.push_back(SH.Val); 2723 return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond); 2724 } 2725 } 2726 } 2727 2728 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 2729 N1.getOpcode() == ISD::XOR) { 2730 // Simplify X == (X+Z) --> Z == 0 2731 if (N1.getOperand(0) == N0) { 2732 return DAG.getSetCC(VT, N1.getOperand(1), 2733 DAG.getConstant(0, N1.getValueType()), Cond); 2734 } else if (N1.getOperand(1) == N0) { 2735 if (isCommutativeBinOp(N1.getOpcode())) { 2736 return DAG.getSetCC(VT, N1.getOperand(0), 2737 DAG.getConstant(0, N1.getValueType()), Cond); 2738 } else { 2739 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 2740 // X == (Z-X) --> X<<1 == Z 2741 SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 2742 DAG.getConstant(1,TLI.getShiftAmountTy())); 2743 WorkList.push_back(SH.Val); 2744 return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond); 2745 } 2746 } 2747 } 2748 } 2749 2750 // Fold away ALL boolean setcc's. 2751 SDOperand Temp; 2752 if (N0.getValueType() == MVT::i1 && foldBooleans) { 2753 switch (Cond) { 2754 default: assert(0 && "Unknown integer setcc!"); 2755 case ISD::SETEQ: // X == Y -> (X^Y)^1 2756 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 2757 N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1)); 2758 WorkList.push_back(Temp.Val); 2759 break; 2760 case ISD::SETNE: // X != Y --> (X^Y) 2761 N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1); 2762 break; 2763 case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y 2764 case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y 2765 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 2766 N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp); 2767 WorkList.push_back(Temp.Val); 2768 break; 2769 case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X 2770 case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X 2771 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 2772 N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp); 2773 WorkList.push_back(Temp.Val); 2774 break; 2775 case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y 2776 case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y 2777 Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1)); 2778 N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp); 2779 WorkList.push_back(Temp.Val); 2780 break; 2781 case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X 2782 case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X 2783 Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1)); 2784 N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp); 2785 break; 2786 } 2787 if (VT != MVT::i1) { 2788 WorkList.push_back(N0.Val); 2789 // FIXME: If running after legalize, we probably can't do this. 2790 N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0); 2791 } 2792 return N0; 2793 } 2794 2795 // Could not fold it. 2796 return SDOperand(); 2797} 2798 2799/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 2800/// return a DAG expression to select that will generate the same value by 2801/// multiplying by a magic number. See: 2802/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 2803SDOperand DAGCombiner::BuildSDIV(SDNode *N) { 2804 MVT::ValueType VT = N->getValueType(0); 2805 2806 // Check to see if we can do this. 2807 if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 2808 return SDOperand(); // BuildSDIV only operates on i32 or i64 2809 if (!TLI.isOperationLegal(ISD::MULHS, VT)) 2810 return SDOperand(); // Make sure the target supports MULHS. 2811 2812 int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended(); 2813 ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d); 2814 2815 // Multiply the numerator (operand 0) by the magic value 2816 SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0), 2817 DAG.getConstant(magics.m, VT)); 2818 // If d > 0 and m < 0, add the numerator 2819 if (d > 0 && magics.m < 0) { 2820 Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0)); 2821 WorkList.push_back(Q.Val); 2822 } 2823 // If d < 0 and m > 0, subtract the numerator. 2824 if (d < 0 && magics.m > 0) { 2825 Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0)); 2826 WorkList.push_back(Q.Val); 2827 } 2828 // Shift right algebraic if shift value is nonzero 2829 if (magics.s > 0) { 2830 Q = DAG.getNode(ISD::SRA, VT, Q, 2831 DAG.getConstant(magics.s, TLI.getShiftAmountTy())); 2832 WorkList.push_back(Q.Val); 2833 } 2834 // Extract the sign bit and add it to the quotient 2835 SDOperand T = 2836 DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1, 2837 TLI.getShiftAmountTy())); 2838 WorkList.push_back(T.Val); 2839 return DAG.getNode(ISD::ADD, VT, Q, T); 2840} 2841 2842/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 2843/// return a DAG expression to select that will generate the same value by 2844/// multiplying by a magic number. See: 2845/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 2846SDOperand DAGCombiner::BuildUDIV(SDNode *N) { 2847 MVT::ValueType VT = N->getValueType(0); 2848 2849 // Check to see if we can do this. 2850 if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 2851 return SDOperand(); // BuildUDIV only operates on i32 or i64 2852 if (!TLI.isOperationLegal(ISD::MULHU, VT)) 2853 return SDOperand(); // Make sure the target supports MULHU. 2854 2855 uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue(); 2856 mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d); 2857 2858 // Multiply the numerator (operand 0) by the magic value 2859 SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0), 2860 DAG.getConstant(magics.m, VT)); 2861 WorkList.push_back(Q.Val); 2862 2863 if (magics.a == 0) { 2864 return DAG.getNode(ISD::SRL, VT, Q, 2865 DAG.getConstant(magics.s, TLI.getShiftAmountTy())); 2866 } else { 2867 SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q); 2868 WorkList.push_back(NPQ.Val); 2869 NPQ = DAG.getNode(ISD::SRL, VT, NPQ, 2870 DAG.getConstant(1, TLI.getShiftAmountTy())); 2871 WorkList.push_back(NPQ.Val); 2872 NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q); 2873 WorkList.push_back(NPQ.Val); 2874 return DAG.getNode(ISD::SRL, VT, NPQ, 2875 DAG.getConstant(magics.s-1, TLI.getShiftAmountTy())); 2876 } 2877} 2878 2879// SelectionDAG::Combine - This is the entry point for the file. 2880// 2881void SelectionDAG::Combine(bool RunningAfterLegalize) { 2882 /// run - This is the main entry point to this class. 2883 /// 2884 DAGCombiner(*this).Run(RunningAfterLegalize); 2885} 2886