SelectionDAG.cpp revision a83385fb7bdb325921d091729d95e2e1f4d49cc1
1//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the SelectionDAG class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/SelectionDAG.h" 15#include "llvm/Constants.h" 16#include "llvm/GlobalValue.h" 17#include "llvm/Intrinsics.h" 18#include "llvm/Assembly/Writer.h" 19#include "llvm/CodeGen/MachineBasicBlock.h" 20#include "llvm/Support/MathExtras.h" 21#include "llvm/Target/MRegisterInfo.h" 22#include "llvm/Target/TargetLowering.h" 23#include "llvm/Target/TargetInstrInfo.h" 24#include "llvm/Target/TargetMachine.h" 25#include "llvm/ADT/SetVector.h" 26#include "llvm/ADT/StringExtras.h" 27#include <iostream> 28#include <set> 29#include <cmath> 30#include <algorithm> 31using namespace llvm; 32 33static bool isCommutativeBinOp(unsigned Opcode) { 34 switch (Opcode) { 35 case ISD::ADD: 36 case ISD::MUL: 37 case ISD::MULHU: 38 case ISD::MULHS: 39 case ISD::FADD: 40 case ISD::FMUL: 41 case ISD::AND: 42 case ISD::OR: 43 case ISD::XOR: return true; 44 default: return false; // FIXME: Need commutative info for user ops! 45 } 46} 47 48// isInvertibleForFree - Return true if there is no cost to emitting the logical 49// inverse of this node. 50static bool isInvertibleForFree(SDOperand N) { 51 if (isa<ConstantSDNode>(N.Val)) return true; 52 if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse()) 53 return true; 54 return false; 55} 56 57//===----------------------------------------------------------------------===// 58// ConstantFPSDNode Class 59//===----------------------------------------------------------------------===// 60 61/// isExactlyValue - We don't rely on operator== working on double values, as 62/// it returns true for things that are clearly not equal, like -0.0 and 0.0. 63/// As such, this method can be used to do an exact bit-for-bit comparison of 64/// two floating point values. 65bool ConstantFPSDNode::isExactlyValue(double V) const { 66 return DoubleToBits(V) == DoubleToBits(Value); 67} 68 69//===----------------------------------------------------------------------===// 70// ISD Namespace 71//===----------------------------------------------------------------------===// 72 73/// isBuildVectorAllOnes - Return true if the specified node is a 74/// BUILD_VECTOR where all of the elements are ~0 or undef. 75bool ISD::isBuildVectorAllOnes(const SDNode *N) { 76 // Look through a bit convert. 77 if (N->getOpcode() == ISD::BIT_CONVERT) 78 N = N->getOperand(0).Val; 79 80 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 81 82 unsigned i = 0, e = N->getNumOperands(); 83 84 // Skip over all of the undef values. 85 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 86 ++i; 87 88 // Do not accept an all-undef vector. 89 if (i == e) return false; 90 91 // Do not accept build_vectors that aren't all constants or which have non-~0 92 // elements. 93 SDOperand NotZero = N->getOperand(i); 94 if (isa<ConstantSDNode>(NotZero)) { 95 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 96 return false; 97 } else if (isa<ConstantFPSDNode>(NotZero)) { 98 MVT::ValueType VT = NotZero.getValueType(); 99 if (VT== MVT::f64) { 100 if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 101 (uint64_t)-1) 102 return false; 103 } else { 104 if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 105 (uint32_t)-1) 106 return false; 107 } 108 } else 109 return false; 110 111 // Okay, we have at least one ~0 value, check to see if the rest match or are 112 // undefs. 113 for (++i; i != e; ++i) 114 if (N->getOperand(i) != NotZero && 115 N->getOperand(i).getOpcode() != ISD::UNDEF) 116 return false; 117 return true; 118} 119 120 121/// isBuildVectorAllZeros - Return true if the specified node is a 122/// BUILD_VECTOR where all of the elements are 0 or undef. 123bool ISD::isBuildVectorAllZeros(const SDNode *N) { 124 // Look through a bit convert. 125 if (N->getOpcode() == ISD::BIT_CONVERT) 126 N = N->getOperand(0).Val; 127 128 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 129 130 unsigned i = 0, e = N->getNumOperands(); 131 132 // Skip over all of the undef values. 133 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 134 ++i; 135 136 // Do not accept an all-undef vector. 137 if (i == e) return false; 138 139 // Do not accept build_vectors that aren't all constants or which have non-~0 140 // elements. 141 SDOperand Zero = N->getOperand(i); 142 if (isa<ConstantSDNode>(Zero)) { 143 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 144 return false; 145 } else if (isa<ConstantFPSDNode>(Zero)) { 146 if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0)) 147 return false; 148 } else 149 return false; 150 151 // Okay, we have at least one ~0 value, check to see if the rest match or are 152 // undefs. 153 for (++i; i != e; ++i) 154 if (N->getOperand(i) != Zero && 155 N->getOperand(i).getOpcode() != ISD::UNDEF) 156 return false; 157 return true; 158} 159 160/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 161/// when given the operation for (X op Y). 162ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 163 // To perform this operation, we just need to swap the L and G bits of the 164 // operation. 165 unsigned OldL = (Operation >> 2) & 1; 166 unsigned OldG = (Operation >> 1) & 1; 167 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 168 (OldL << 1) | // New G bit 169 (OldG << 2)); // New L bit. 170} 171 172/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 173/// 'op' is a valid SetCC operation. 174ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 175 unsigned Operation = Op; 176 if (isInteger) 177 Operation ^= 7; // Flip L, G, E bits, but not U. 178 else 179 Operation ^= 15; // Flip all of the condition bits. 180 if (Operation > ISD::SETTRUE2) 181 Operation &= ~8; // Don't let N and U bits get set. 182 return ISD::CondCode(Operation); 183} 184 185 186/// isSignedOp - For an integer comparison, return 1 if the comparison is a 187/// signed operation and 2 if the result is an unsigned comparison. Return zero 188/// if the operation does not depend on the sign of the input (setne and seteq). 189static int isSignedOp(ISD::CondCode Opcode) { 190 switch (Opcode) { 191 default: assert(0 && "Illegal integer setcc operation!"); 192 case ISD::SETEQ: 193 case ISD::SETNE: return 0; 194 case ISD::SETLT: 195 case ISD::SETLE: 196 case ISD::SETGT: 197 case ISD::SETGE: return 1; 198 case ISD::SETULT: 199 case ISD::SETULE: 200 case ISD::SETUGT: 201 case ISD::SETUGE: return 2; 202 } 203} 204 205/// getSetCCOrOperation - Return the result of a logical OR between different 206/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 207/// returns SETCC_INVALID if it is not possible to represent the resultant 208/// comparison. 209ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 210 bool isInteger) { 211 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 212 // Cannot fold a signed integer setcc with an unsigned integer setcc. 213 return ISD::SETCC_INVALID; 214 215 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 216 217 // If the N and U bits get set then the resultant comparison DOES suddenly 218 // care about orderedness, and is true when ordered. 219 if (Op > ISD::SETTRUE2) 220 Op &= ~16; // Clear the N bit. 221 return ISD::CondCode(Op); 222} 223 224/// getSetCCAndOperation - Return the result of a logical AND between different 225/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 226/// function returns zero if it is not possible to represent the resultant 227/// comparison. 228ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 229 bool isInteger) { 230 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 231 // Cannot fold a signed setcc with an unsigned setcc. 232 return ISD::SETCC_INVALID; 233 234 // Combine all of the condition bits. 235 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 236 237 // Canonicalize illegal integer setcc's. 238 if (isInteger) { 239 switch (Result) { 240 default: break; 241 case ISD::SETUO: // e.g. SETUGT & SETULT 242 Result = ISD::SETFALSE; 243 break; 244 case ISD::SETUEQ: // e.g. SETUGE & SETULE 245 Result = ISD::SETEQ; 246 break; 247 } 248 } 249 250 return Result; 251} 252 253const TargetMachine &SelectionDAG::getTarget() const { 254 return TLI.getTargetMachine(); 255} 256 257//===----------------------------------------------------------------------===// 258// SelectionDAG Class 259//===----------------------------------------------------------------------===// 260 261/// RemoveDeadNodes - This method deletes all unreachable nodes in the 262/// SelectionDAG, including nodes (like loads) that have uses of their token 263/// chain but no other uses and no side effect. If a node is passed in as an 264/// argument, it is used as the seed for node deletion. 265void SelectionDAG::RemoveDeadNodes(SDNode *N) { 266 // Create a dummy node (which is not added to allnodes), that adds a reference 267 // to the root node, preventing it from being deleted. 268 HandleSDNode Dummy(getRoot()); 269 270 bool MadeChange = false; 271 272 // If we have a hint to start from, use it. 273 if (N && N->use_empty()) { 274 DestroyDeadNode(N); 275 MadeChange = true; 276 } 277 278 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 279 if (I->use_empty() && I->getOpcode() != 65535) { 280 // Node is dead, recursively delete newly dead uses. 281 DestroyDeadNode(I); 282 MadeChange = true; 283 } 284 285 // Walk the nodes list, removing the nodes we've marked as dead. 286 if (MadeChange) { 287 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) { 288 SDNode *N = I++; 289 if (N->use_empty()) 290 AllNodes.erase(N); 291 } 292 } 293 294 // If the root changed (e.g. it was a dead load, update the root). 295 setRoot(Dummy.getValue()); 296} 297 298/// DestroyDeadNode - We know that N is dead. Nuke it from the CSE maps for the 299/// graph. If it is the last user of any of its operands, recursively process 300/// them the same way. 301/// 302void SelectionDAG::DestroyDeadNode(SDNode *N) { 303 // Okay, we really are going to delete this node. First take this out of the 304 // appropriate CSE map. 305 RemoveNodeFromCSEMaps(N); 306 307 // Next, brutally remove the operand list. This is safe to do, as there are 308 // no cycles in the graph. 309 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 310 SDNode *O = I->Val; 311 O->removeUser(N); 312 313 // Now that we removed this operand, see if there are no uses of it left. 314 if (O->use_empty()) 315 DestroyDeadNode(O); 316 } 317 delete[] N->OperandList; 318 N->OperandList = 0; 319 N->NumOperands = 0; 320 321 // Mark the node as dead. 322 N->MorphNodeTo(65535); 323} 324 325void SelectionDAG::DeleteNode(SDNode *N) { 326 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 327 328 // First take this out of the appropriate CSE map. 329 RemoveNodeFromCSEMaps(N); 330 331 // Finally, remove uses due to operands of this node, remove from the 332 // AllNodes list, and delete the node. 333 DeleteNodeNotInCSEMaps(N); 334} 335 336void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 337 338 // Remove it from the AllNodes list. 339 AllNodes.remove(N); 340 341 // Drop all of the operands and decrement used nodes use counts. 342 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 343 I->Val->removeUser(N); 344 delete[] N->OperandList; 345 N->OperandList = 0; 346 N->NumOperands = 0; 347 348 delete N; 349} 350 351/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 352/// correspond to it. This is useful when we're about to delete or repurpose 353/// the node. We don't want future request for structurally identical nodes 354/// to return N anymore. 355void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 356 bool Erased = false; 357 switch (N->getOpcode()) { 358 case ISD::HANDLENODE: return; // noop. 359 case ISD::Constant: 360 Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(), 361 N->getValueType(0))); 362 break; 363 case ISD::TargetConstant: 364 Erased = TargetConstants.erase(std::make_pair( 365 cast<ConstantSDNode>(N)->getValue(), 366 N->getValueType(0))); 367 break; 368 case ISD::ConstantFP: { 369 uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()); 370 Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0))); 371 break; 372 } 373 case ISD::TargetConstantFP: { 374 uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()); 375 Erased = TargetConstantFPs.erase(std::make_pair(V, N->getValueType(0))); 376 break; 377 } 378 case ISD::STRING: 379 Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue()); 380 break; 381 case ISD::CONDCODE: 382 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 383 "Cond code doesn't exist!"); 384 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 385 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 386 break; 387 case ISD::GlobalAddress: { 388 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 389 Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(), 390 GN->getOffset())); 391 break; 392 } 393 case ISD::TargetGlobalAddress: { 394 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 395 Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(), 396 GN->getOffset())); 397 break; 398 } 399 case ISD::FrameIndex: 400 Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 401 break; 402 case ISD::TargetFrameIndex: 403 Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 404 break; 405 case ISD::JumpTable: 406 Erased = JumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex()); 407 break; 408 case ISD::TargetJumpTable: 409 Erased = 410 TargetJumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex()); 411 break; 412 case ISD::ConstantPool: 413 Erased = ConstantPoolIndices. 414 erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(), 415 std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(), 416 cast<ConstantPoolSDNode>(N)->getAlignment()))); 417 break; 418 case ISD::TargetConstantPool: 419 Erased = TargetConstantPoolIndices. 420 erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(), 421 std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(), 422 cast<ConstantPoolSDNode>(N)->getAlignment()))); 423 break; 424 case ISD::BasicBlock: 425 Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock()); 426 break; 427 case ISD::ExternalSymbol: 428 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 429 break; 430 case ISD::TargetExternalSymbol: 431 Erased = 432 TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 433 break; 434 case ISD::VALUETYPE: 435 Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0; 436 ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0; 437 break; 438 case ISD::Register: 439 Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(), 440 N->getValueType(0))); 441 break; 442 case ISD::SRCVALUE: { 443 SrcValueSDNode *SVN = cast<SrcValueSDNode>(N); 444 Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset())); 445 break; 446 } 447 case ISD::LOAD: 448 Erased = Loads.erase(std::make_pair(N->getOperand(1), 449 std::make_pair(N->getOperand(0), 450 N->getValueType(0)))); 451 break; 452 default: 453 if (N->getNumValues() == 1) { 454 if (N->getNumOperands() == 0) { 455 Erased = NullaryOps.erase(std::make_pair(N->getOpcode(), 456 N->getValueType(0))); 457 } else if (N->getNumOperands() == 1) { 458 Erased = 459 UnaryOps.erase(std::make_pair(N->getOpcode(), 460 std::make_pair(N->getOperand(0), 461 N->getValueType(0)))); 462 } else if (N->getNumOperands() == 2) { 463 Erased = 464 BinaryOps.erase(std::make_pair(N->getOpcode(), 465 std::make_pair(N->getOperand(0), 466 N->getOperand(1)))); 467 } else { 468 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 469 Erased = 470 OneResultNodes.erase(std::make_pair(N->getOpcode(), 471 std::make_pair(N->getValueType(0), 472 Ops))); 473 } 474 } else { 475 // Remove the node from the ArbitraryNodes map. 476 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 477 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 478 Erased = 479 ArbitraryNodes.erase(std::make_pair(N->getOpcode(), 480 std::make_pair(RV, Ops))); 481 } 482 break; 483 } 484#ifndef NDEBUG 485 // Verify that the node was actually in one of the CSE maps, unless it has a 486 // flag result (which cannot be CSE'd) or is one of the special cases that are 487 // not subject to CSE. 488 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 489 !N->isTargetOpcode()) { 490 N->dump(); 491 assert(0 && "Node is not in map!"); 492 } 493#endif 494} 495 496/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It 497/// has been taken out and modified in some way. If the specified node already 498/// exists in the CSE maps, do not modify the maps, but return the existing node 499/// instead. If it doesn't exist, add it and return null. 500/// 501SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { 502 assert(N->getNumOperands() && "This is a leaf node!"); 503 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 504 return 0; // Never add these nodes. 505 506 // Check that remaining values produced are not flags. 507 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 508 if (N->getValueType(i) == MVT::Flag) 509 return 0; // Never CSE anything that produces a flag. 510 511 if (N->getNumValues() == 1) { 512 if (N->getNumOperands() == 1) { 513 SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(), 514 std::make_pair(N->getOperand(0), 515 N->getValueType(0)))]; 516 if (U) return U; 517 U = N; 518 } else if (N->getNumOperands() == 2) { 519 SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(), 520 std::make_pair(N->getOperand(0), 521 N->getOperand(1)))]; 522 if (B) return B; 523 B = N; 524 } else { 525 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 526 SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(), 527 std::make_pair(N->getValueType(0), Ops))]; 528 if (ORN) return ORN; 529 ORN = N; 530 } 531 } else { 532 if (N->getOpcode() == ISD::LOAD) { 533 SDNode *&L = Loads[std::make_pair(N->getOperand(1), 534 std::make_pair(N->getOperand(0), 535 N->getValueType(0)))]; 536 if (L) return L; 537 L = N; 538 } else { 539 // Remove the node from the ArbitraryNodes map. 540 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 541 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 542 SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(), 543 std::make_pair(RV, Ops))]; 544 if (AN) return AN; 545 AN = N; 546 } 547 } 548 return 0; 549} 550 551/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 552/// were replaced with those specified. If this node is never memoized, 553/// return null, otherwise return a pointer to the slot it would take. If a 554/// node already exists with these operands, the slot will be non-null. 555SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op) { 556 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 557 return 0; // Never add these nodes. 558 559 // Check that remaining values produced are not flags. 560 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 561 if (N->getValueType(i) == MVT::Flag) 562 return 0; // Never CSE anything that produces a flag. 563 564 if (N->getNumValues() == 1) { 565 return &UnaryOps[std::make_pair(N->getOpcode(), 566 std::make_pair(Op, N->getValueType(0)))]; 567 } else { 568 // Remove the node from the ArbitraryNodes map. 569 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 570 std::vector<SDOperand> Ops; 571 Ops.push_back(Op); 572 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 573 std::make_pair(RV, Ops))]; 574 } 575 return 0; 576} 577 578/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 579/// were replaced with those specified. If this node is never memoized, 580/// return null, otherwise return a pointer to the slot it would take. If a 581/// node already exists with these operands, the slot will be non-null. 582SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 583 SDOperand Op1, SDOperand Op2) { 584 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 585 return 0; // Never add these nodes. 586 587 // Check that remaining values produced are not flags. 588 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 589 if (N->getValueType(i) == MVT::Flag) 590 return 0; // Never CSE anything that produces a flag. 591 592 if (N->getNumValues() == 1) { 593 return &BinaryOps[std::make_pair(N->getOpcode(), 594 std::make_pair(Op1, Op2))]; 595 } else { 596 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 597 std::vector<SDOperand> Ops; 598 Ops.push_back(Op1); 599 Ops.push_back(Op2); 600 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 601 std::make_pair(RV, Ops))]; 602 } 603 return 0; 604} 605 606 607/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 608/// were replaced with those specified. If this node is never memoized, 609/// return null, otherwise return a pointer to the slot it would take. If a 610/// node already exists with these operands, the slot will be non-null. 611SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 612 const std::vector<SDOperand> &Ops) { 613 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 614 return 0; // Never add these nodes. 615 616 // Check that remaining values produced are not flags. 617 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 618 if (N->getValueType(i) == MVT::Flag) 619 return 0; // Never CSE anything that produces a flag. 620 621 if (N->getNumValues() == 1) { 622 if (N->getNumOperands() == 1) { 623 return &UnaryOps[std::make_pair(N->getOpcode(), 624 std::make_pair(Ops[0], 625 N->getValueType(0)))]; 626 } else if (N->getNumOperands() == 2) { 627 return &BinaryOps[std::make_pair(N->getOpcode(), 628 std::make_pair(Ops[0], Ops[1]))]; 629 } else { 630 return &OneResultNodes[std::make_pair(N->getOpcode(), 631 std::make_pair(N->getValueType(0), 632 Ops))]; 633 } 634 } else { 635 if (N->getOpcode() == ISD::LOAD) { 636 return &Loads[std::make_pair(Ops[1], 637 std::make_pair(Ops[0], N->getValueType(0)))]; 638 } else { 639 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 640 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 641 std::make_pair(RV, Ops))]; 642 } 643 } 644 return 0; 645} 646 647 648SelectionDAG::~SelectionDAG() { 649 while (!AllNodes.empty()) { 650 SDNode *N = AllNodes.begin(); 651 delete [] N->OperandList; 652 N->OperandList = 0; 653 N->NumOperands = 0; 654 AllNodes.pop_front(); 655 } 656} 657 658SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { 659 if (Op.getValueType() == VT) return Op; 660 int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT)); 661 return getNode(ISD::AND, Op.getValueType(), Op, 662 getConstant(Imm, Op.getValueType())); 663} 664 665SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 666 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 667 assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); 668 669 // Mask out any bits that are not valid for this constant. 670 if (VT != MVT::i64) 671 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 672 673 SDNode *&N = Constants[std::make_pair(Val, VT)]; 674 if (N) return SDOperand(N, 0); 675 N = new ConstantSDNode(false, Val, VT); 676 AllNodes.push_back(N); 677 return SDOperand(N, 0); 678} 679 680SDOperand SelectionDAG::getString(const std::string &Val) { 681 StringSDNode *&N = StringNodes[Val]; 682 if (!N) { 683 N = new StringSDNode(Val); 684 AllNodes.push_back(N); 685 } 686 return SDOperand(N, 0); 687} 688 689SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) { 690 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 691 // Mask out any bits that are not valid for this constant. 692 if (VT != MVT::i64) 693 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 694 695 SDNode *&N = TargetConstants[std::make_pair(Val, VT)]; 696 if (N) return SDOperand(N, 0); 697 N = new ConstantSDNode(true, Val, VT); 698 AllNodes.push_back(N); 699 return SDOperand(N, 0); 700} 701 702SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 703 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 704 if (VT == MVT::f32) 705 Val = (float)Val; // Mask out extra precision. 706 707 // Do the map lookup using the actual bit pattern for the floating point 708 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 709 // we don't have issues with SNANs. 710 SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; 711 if (N) return SDOperand(N, 0); 712 N = new ConstantFPSDNode(false, Val, VT); 713 AllNodes.push_back(N); 714 return SDOperand(N, 0); 715} 716 717SDOperand SelectionDAG::getTargetConstantFP(double Val, MVT::ValueType VT) { 718 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 719 if (VT == MVT::f32) 720 Val = (float)Val; // Mask out extra precision. 721 722 // Do the map lookup using the actual bit pattern for the floating point 723 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 724 // we don't have issues with SNANs. 725 SDNode *&N = TargetConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; 726 if (N) return SDOperand(N, 0); 727 N = new ConstantFPSDNode(true, Val, VT); 728 AllNodes.push_back(N); 729 return SDOperand(N, 0); 730} 731 732SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 733 MVT::ValueType VT, int offset) { 734 SDNode *&N = GlobalValues[std::make_pair(GV, offset)]; 735 if (N) return SDOperand(N, 0); 736 N = new GlobalAddressSDNode(false, GV, VT, offset); 737 AllNodes.push_back(N); 738 return SDOperand(N, 0); 739} 740 741SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV, 742 MVT::ValueType VT, int offset) { 743 SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)]; 744 if (N) return SDOperand(N, 0); 745 N = new GlobalAddressSDNode(true, GV, VT, offset); 746 AllNodes.push_back(N); 747 return SDOperand(N, 0); 748} 749 750SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 751 SDNode *&N = FrameIndices[FI]; 752 if (N) return SDOperand(N, 0); 753 N = new FrameIndexSDNode(FI, VT, false); 754 AllNodes.push_back(N); 755 return SDOperand(N, 0); 756} 757 758SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) { 759 SDNode *&N = TargetFrameIndices[FI]; 760 if (N) return SDOperand(N, 0); 761 N = new FrameIndexSDNode(FI, VT, true); 762 AllNodes.push_back(N); 763 return SDOperand(N, 0); 764} 765 766SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT) { 767 SDNode *&N = JumpTableIndices[JTI]; 768 if (N) return SDOperand(N, 0); 769 N = new JumpTableSDNode(JTI, VT, false); 770 AllNodes.push_back(N); 771 return SDOperand(N, 0); 772} 773 774SDOperand SelectionDAG::getTargetJumpTable(int JTI, MVT::ValueType VT) { 775 SDNode *&N = TargetJumpTableIndices[JTI]; 776 if (N) return SDOperand(N, 0); 777 N = new JumpTableSDNode(JTI, VT, true); 778 AllNodes.push_back(N); 779 return SDOperand(N, 0); 780} 781 782SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, 783 unsigned Alignment, int Offset) { 784 SDNode *&N = ConstantPoolIndices[std::make_pair(C, 785 std::make_pair(Offset, Alignment))]; 786 if (N) return SDOperand(N, 0); 787 N = new ConstantPoolSDNode(false, C, VT, Offset, Alignment); 788 AllNodes.push_back(N); 789 return SDOperand(N, 0); 790} 791 792SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT, 793 unsigned Alignment, int Offset) { 794 SDNode *&N = TargetConstantPoolIndices[std::make_pair(C, 795 std::make_pair(Offset, Alignment))]; 796 if (N) return SDOperand(N, 0); 797 N = new ConstantPoolSDNode(true, C, VT, Offset, Alignment); 798 AllNodes.push_back(N); 799 return SDOperand(N, 0); 800} 801 802SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 803 SDNode *&N = BBNodes[MBB]; 804 if (N) return SDOperand(N, 0); 805 N = new BasicBlockSDNode(MBB); 806 AllNodes.push_back(N); 807 return SDOperand(N, 0); 808} 809 810SDOperand SelectionDAG::getValueType(MVT::ValueType VT) { 811 if ((unsigned)VT >= ValueTypeNodes.size()) 812 ValueTypeNodes.resize(VT+1); 813 if (ValueTypeNodes[VT] == 0) { 814 ValueTypeNodes[VT] = new VTSDNode(VT); 815 AllNodes.push_back(ValueTypeNodes[VT]); 816 } 817 818 return SDOperand(ValueTypeNodes[VT], 0); 819} 820 821SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 822 SDNode *&N = ExternalSymbols[Sym]; 823 if (N) return SDOperand(N, 0); 824 N = new ExternalSymbolSDNode(false, Sym, VT); 825 AllNodes.push_back(N); 826 return SDOperand(N, 0); 827} 828 829SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, 830 MVT::ValueType VT) { 831 SDNode *&N = TargetExternalSymbols[Sym]; 832 if (N) return SDOperand(N, 0); 833 N = new ExternalSymbolSDNode(true, Sym, VT); 834 AllNodes.push_back(N); 835 return SDOperand(N, 0); 836} 837 838SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { 839 if ((unsigned)Cond >= CondCodeNodes.size()) 840 CondCodeNodes.resize(Cond+1); 841 842 if (CondCodeNodes[Cond] == 0) { 843 CondCodeNodes[Cond] = new CondCodeSDNode(Cond); 844 AllNodes.push_back(CondCodeNodes[Cond]); 845 } 846 return SDOperand(CondCodeNodes[Cond], 0); 847} 848 849SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { 850 RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)]; 851 if (!Reg) { 852 Reg = new RegisterSDNode(RegNo, VT); 853 AllNodes.push_back(Reg); 854 } 855 return SDOperand(Reg, 0); 856} 857 858SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, 859 SDOperand N2, ISD::CondCode Cond) { 860 // These setcc operations always fold. 861 switch (Cond) { 862 default: break; 863 case ISD::SETFALSE: 864 case ISD::SETFALSE2: return getConstant(0, VT); 865 case ISD::SETTRUE: 866 case ISD::SETTRUE2: return getConstant(1, VT); 867 868 case ISD::SETOEQ: 869 case ISD::SETOGT: 870 case ISD::SETOGE: 871 case ISD::SETOLT: 872 case ISD::SETOLE: 873 case ISD::SETONE: 874 case ISD::SETO: 875 case ISD::SETUO: 876 case ISD::SETUEQ: 877 case ISD::SETUNE: 878 assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!"); 879 break; 880 } 881 882 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 883 uint64_t C2 = N2C->getValue(); 884 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 885 uint64_t C1 = N1C->getValue(); 886 887 // Sign extend the operands if required 888 if (ISD::isSignedIntSetCC(Cond)) { 889 C1 = N1C->getSignExtended(); 890 C2 = N2C->getSignExtended(); 891 } 892 893 switch (Cond) { 894 default: assert(0 && "Unknown integer setcc!"); 895 case ISD::SETEQ: return getConstant(C1 == C2, VT); 896 case ISD::SETNE: return getConstant(C1 != C2, VT); 897 case ISD::SETULT: return getConstant(C1 < C2, VT); 898 case ISD::SETUGT: return getConstant(C1 > C2, VT); 899 case ISD::SETULE: return getConstant(C1 <= C2, VT); 900 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 901 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 902 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 903 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 904 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 905 } 906 } else { 907 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 908 if (N1.getOpcode() == ISD::ZERO_EXTEND) { 909 unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType()); 910 911 // If the comparison constant has bits in the upper part, the 912 // zero-extended value could never match. 913 if (C2 & (~0ULL << InSize)) { 914 unsigned VSize = MVT::getSizeInBits(N1.getValueType()); 915 switch (Cond) { 916 case ISD::SETUGT: 917 case ISD::SETUGE: 918 case ISD::SETEQ: return getConstant(0, VT); 919 case ISD::SETULT: 920 case ISD::SETULE: 921 case ISD::SETNE: return getConstant(1, VT); 922 case ISD::SETGT: 923 case ISD::SETGE: 924 // True if the sign bit of C2 is set. 925 return getConstant((C2 & (1ULL << VSize)) != 0, VT); 926 case ISD::SETLT: 927 case ISD::SETLE: 928 // True if the sign bit of C2 isn't set. 929 return getConstant((C2 & (1ULL << VSize)) == 0, VT); 930 default: 931 break; 932 } 933 } 934 935 // Otherwise, we can perform the comparison with the low bits. 936 switch (Cond) { 937 case ISD::SETEQ: 938 case ISD::SETNE: 939 case ISD::SETUGT: 940 case ISD::SETUGE: 941 case ISD::SETULT: 942 case ISD::SETULE: 943 return getSetCC(VT, N1.getOperand(0), 944 getConstant(C2, N1.getOperand(0).getValueType()), 945 Cond); 946 default: 947 break; // todo, be more careful with signed comparisons 948 } 949 } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG && 950 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 951 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT(); 952 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 953 MVT::ValueType ExtDstTy = N1.getValueType(); 954 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 955 956 // If the extended part has any inconsistent bits, it cannot ever 957 // compare equal. In other words, they have to be all ones or all 958 // zeros. 959 uint64_t ExtBits = 960 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 961 if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits) 962 return getConstant(Cond == ISD::SETNE, VT); 963 964 // Otherwise, make this a use of a zext. 965 return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy), 966 getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy), 967 Cond); 968 } 969 970 uint64_t MinVal, MaxVal; 971 unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0)); 972 if (ISD::isSignedIntSetCC(Cond)) { 973 MinVal = 1ULL << (OperandBitSize-1); 974 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 975 MaxVal = ~0ULL >> (65-OperandBitSize); 976 else 977 MaxVal = 0; 978 } else { 979 MinVal = 0; 980 MaxVal = ~0ULL >> (64-OperandBitSize); 981 } 982 983 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 984 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 985 if (C2 == MinVal) return getConstant(1, VT); // X >= MIN --> true 986 --C2; // X >= C1 --> X > (C1-1) 987 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 988 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 989 } 990 991 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 992 if (C2 == MaxVal) return getConstant(1, VT); // X <= MAX --> true 993 ++C2; // X <= C1 --> X < (C1+1) 994 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 995 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 996 } 997 998 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal) 999 return getConstant(0, VT); // X < MIN --> false 1000 1001 // Canonicalize setgt X, Min --> setne X, Min 1002 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal) 1003 return getSetCC(VT, N1, N2, ISD::SETNE); 1004 1005 // If we have setult X, 1, turn it into seteq X, 0 1006 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1) 1007 return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()), 1008 ISD::SETEQ); 1009 // If we have setugt X, Max-1, turn it into seteq X, Max 1010 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1) 1011 return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()), 1012 ISD::SETEQ); 1013 1014 // If we have "setcc X, C1", check to see if we can shrink the immediate 1015 // by changing cc. 1016 1017 // SETUGT X, SINTMAX -> SETLT X, 0 1018 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 1019 C2 == (~0ULL >> (65-OperandBitSize))) 1020 return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT); 1021 1022 // FIXME: Implement the rest of these. 1023 1024 1025 // Fold bit comparisons when we can. 1026 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 1027 VT == N1.getValueType() && N1.getOpcode() == ISD::AND) 1028 if (ConstantSDNode *AndRHS = 1029 dyn_cast<ConstantSDNode>(N1.getOperand(1))) { 1030 if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 1031 // Perform the xform if the AND RHS is a single bit. 1032 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 1033 return getNode(ISD::SRL, VT, N1, 1034 getConstant(Log2_64(AndRHS->getValue()), 1035 TLI.getShiftAmountTy())); 1036 } 1037 } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) { 1038 // (X & 8) == 8 --> (X & 8) >> 3 1039 // Perform the xform if C2 is a single bit. 1040 if ((C2 & (C2-1)) == 0) { 1041 return getNode(ISD::SRL, VT, N1, 1042 getConstant(Log2_64(C2),TLI.getShiftAmountTy())); 1043 } 1044 } 1045 } 1046 } 1047 } else if (isa<ConstantSDNode>(N1.Val)) { 1048 // Ensure that the constant occurs on the RHS. 1049 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 1050 } 1051 1052 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 1053 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 1054 double C1 = N1C->getValue(), C2 = N2C->getValue(); 1055 1056 switch (Cond) { 1057 default: break; // FIXME: Implement the rest of these! 1058 case ISD::SETEQ: return getConstant(C1 == C2, VT); 1059 case ISD::SETNE: return getConstant(C1 != C2, VT); 1060 case ISD::SETLT: return getConstant(C1 < C2, VT); 1061 case ISD::SETGT: return getConstant(C1 > C2, VT); 1062 case ISD::SETLE: return getConstant(C1 <= C2, VT); 1063 case ISD::SETGE: return getConstant(C1 >= C2, VT); 1064 } 1065 } else { 1066 // Ensure that the constant occurs on the RHS. 1067 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 1068 } 1069 1070 // Could not fold it. 1071 return SDOperand(); 1072} 1073 1074/// getNode - Gets or creates the specified node. 1075/// 1076SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 1077 SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)]; 1078 if (!N) { 1079 N = new SDNode(Opcode, VT); 1080 AllNodes.push_back(N); 1081 } 1082 return SDOperand(N, 0); 1083} 1084 1085SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1086 SDOperand Operand) { 1087 unsigned Tmp1; 1088 // Constant fold unary operations with an integer constant operand. 1089 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 1090 uint64_t Val = C->getValue(); 1091 switch (Opcode) { 1092 default: break; 1093 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 1094 case ISD::ANY_EXTEND: 1095 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 1096 case ISD::TRUNCATE: return getConstant(Val, VT); 1097 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 1098 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 1099 case ISD::BIT_CONVERT: 1100 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 1101 return getConstantFP(BitsToFloat(Val), VT); 1102 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 1103 return getConstantFP(BitsToDouble(Val), VT); 1104 break; 1105 case ISD::BSWAP: 1106 switch(VT) { 1107 default: assert(0 && "Invalid bswap!"); break; 1108 case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT); 1109 case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT); 1110 case MVT::i64: return getConstant(ByteSwap_64(Val), VT); 1111 } 1112 break; 1113 case ISD::CTPOP: 1114 switch(VT) { 1115 default: assert(0 && "Invalid ctpop!"); break; 1116 case MVT::i1: return getConstant(Val != 0, VT); 1117 case MVT::i8: 1118 Tmp1 = (unsigned)Val & 0xFF; 1119 return getConstant(CountPopulation_32(Tmp1), VT); 1120 case MVT::i16: 1121 Tmp1 = (unsigned)Val & 0xFFFF; 1122 return getConstant(CountPopulation_32(Tmp1), VT); 1123 case MVT::i32: 1124 return getConstant(CountPopulation_32((unsigned)Val), VT); 1125 case MVT::i64: 1126 return getConstant(CountPopulation_64(Val), VT); 1127 } 1128 case ISD::CTLZ: 1129 switch(VT) { 1130 default: assert(0 && "Invalid ctlz!"); break; 1131 case MVT::i1: return getConstant(Val == 0, VT); 1132 case MVT::i8: 1133 Tmp1 = (unsigned)Val & 0xFF; 1134 return getConstant(CountLeadingZeros_32(Tmp1)-24, VT); 1135 case MVT::i16: 1136 Tmp1 = (unsigned)Val & 0xFFFF; 1137 return getConstant(CountLeadingZeros_32(Tmp1)-16, VT); 1138 case MVT::i32: 1139 return getConstant(CountLeadingZeros_32((unsigned)Val), VT); 1140 case MVT::i64: 1141 return getConstant(CountLeadingZeros_64(Val), VT); 1142 } 1143 case ISD::CTTZ: 1144 switch(VT) { 1145 default: assert(0 && "Invalid cttz!"); break; 1146 case MVT::i1: return getConstant(Val == 0, VT); 1147 case MVT::i8: 1148 Tmp1 = (unsigned)Val | 0x100; 1149 return getConstant(CountTrailingZeros_32(Tmp1), VT); 1150 case MVT::i16: 1151 Tmp1 = (unsigned)Val | 0x10000; 1152 return getConstant(CountTrailingZeros_32(Tmp1), VT); 1153 case MVT::i32: 1154 return getConstant(CountTrailingZeros_32((unsigned)Val), VT); 1155 case MVT::i64: 1156 return getConstant(CountTrailingZeros_64(Val), VT); 1157 } 1158 } 1159 } 1160 1161 // Constant fold unary operations with an floating point constant operand. 1162 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 1163 switch (Opcode) { 1164 case ISD::FNEG: 1165 return getConstantFP(-C->getValue(), VT); 1166 case ISD::FABS: 1167 return getConstantFP(fabs(C->getValue()), VT); 1168 case ISD::FP_ROUND: 1169 case ISD::FP_EXTEND: 1170 return getConstantFP(C->getValue(), VT); 1171 case ISD::FP_TO_SINT: 1172 return getConstant((int64_t)C->getValue(), VT); 1173 case ISD::FP_TO_UINT: 1174 return getConstant((uint64_t)C->getValue(), VT); 1175 case ISD::BIT_CONVERT: 1176 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 1177 return getConstant(FloatToBits(C->getValue()), VT); 1178 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 1179 return getConstant(DoubleToBits(C->getValue()), VT); 1180 break; 1181 } 1182 1183 unsigned OpOpcode = Operand.Val->getOpcode(); 1184 switch (Opcode) { 1185 case ISD::TokenFactor: 1186 return Operand; // Factor of one node? No factor. 1187 case ISD::SIGN_EXTEND: 1188 if (Operand.getValueType() == VT) return Operand; // noop extension 1189 assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!"); 1190 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 1191 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1192 break; 1193 case ISD::ZERO_EXTEND: 1194 if (Operand.getValueType() == VT) return Operand; // noop extension 1195 assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!"); 1196 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 1197 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 1198 break; 1199 case ISD::ANY_EXTEND: 1200 if (Operand.getValueType() == VT) return Operand; // noop extension 1201 assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!"); 1202 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 1203 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 1204 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1205 break; 1206 case ISD::TRUNCATE: 1207 if (Operand.getValueType() == VT) return Operand; // noop truncate 1208 assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!"); 1209 if (OpOpcode == ISD::TRUNCATE) 1210 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 1211 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 1212 OpOpcode == ISD::ANY_EXTEND) { 1213 // If the source is smaller than the dest, we still need an extend. 1214 if (Operand.Val->getOperand(0).getValueType() < VT) 1215 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1216 else if (Operand.Val->getOperand(0).getValueType() > VT) 1217 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 1218 else 1219 return Operand.Val->getOperand(0); 1220 } 1221 break; 1222 case ISD::BIT_CONVERT: 1223 // Basic sanity checking. 1224 assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType()) 1225 && "Cannot BIT_CONVERT between two different types!"); 1226 if (VT == Operand.getValueType()) return Operand; // noop conversion. 1227 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 1228 return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); 1229 if (OpOpcode == ISD::UNDEF) 1230 return getNode(ISD::UNDEF, VT); 1231 break; 1232 case ISD::SCALAR_TO_VECTOR: 1233 assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) && 1234 MVT::getVectorBaseType(VT) == Operand.getValueType() && 1235 "Illegal SCALAR_TO_VECTOR node!"); 1236 break; 1237 case ISD::FNEG: 1238 if (OpOpcode == ISD::FSUB) // -(X-Y) -> (Y-X) 1239 return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1), 1240 Operand.Val->getOperand(0)); 1241 if (OpOpcode == ISD::FNEG) // --X -> X 1242 return Operand.Val->getOperand(0); 1243 break; 1244 case ISD::FABS: 1245 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 1246 return getNode(ISD::FABS, VT, Operand.Val->getOperand(0)); 1247 break; 1248 } 1249 1250 SDNode *N; 1251 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 1252 SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; 1253 if (E) return SDOperand(E, 0); 1254 E = N = new SDNode(Opcode, Operand); 1255 } else { 1256 N = new SDNode(Opcode, Operand); 1257 } 1258 N->setValueTypes(VT); 1259 AllNodes.push_back(N); 1260 return SDOperand(N, 0); 1261} 1262 1263 1264 1265SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1266 SDOperand N1, SDOperand N2) { 1267#ifndef NDEBUG 1268 switch (Opcode) { 1269 case ISD::TokenFactor: 1270 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 1271 N2.getValueType() == MVT::Other && "Invalid token factor!"); 1272 break; 1273 case ISD::AND: 1274 case ISD::OR: 1275 case ISD::XOR: 1276 case ISD::UDIV: 1277 case ISD::UREM: 1278 case ISD::MULHU: 1279 case ISD::MULHS: 1280 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 1281 // fall through 1282 case ISD::ADD: 1283 case ISD::SUB: 1284 case ISD::MUL: 1285 case ISD::SDIV: 1286 case ISD::SREM: 1287 assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops"); 1288 // fall through. 1289 case ISD::FADD: 1290 case ISD::FSUB: 1291 case ISD::FMUL: 1292 case ISD::FDIV: 1293 case ISD::FREM: 1294 assert(N1.getValueType() == N2.getValueType() && 1295 N1.getValueType() == VT && "Binary operator types must match!"); 1296 break; 1297 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 1298 assert(N1.getValueType() == VT && 1299 MVT::isFloatingPoint(N1.getValueType()) && 1300 MVT::isFloatingPoint(N2.getValueType()) && 1301 "Invalid FCOPYSIGN!"); 1302 break; 1303 case ISD::SHL: 1304 case ISD::SRA: 1305 case ISD::SRL: 1306 case ISD::ROTL: 1307 case ISD::ROTR: 1308 assert(VT == N1.getValueType() && 1309 "Shift operators return type must be the same as their first arg"); 1310 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 1311 VT != MVT::i1 && "Shifts only work on integers"); 1312 break; 1313 case ISD::FP_ROUND_INREG: { 1314 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1315 assert(VT == N1.getValueType() && "Not an inreg round!"); 1316 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 1317 "Cannot FP_ROUND_INREG integer types"); 1318 assert(EVT <= VT && "Not rounding down!"); 1319 break; 1320 } 1321 case ISD::AssertSext: 1322 case ISD::AssertZext: 1323 case ISD::SIGN_EXTEND_INREG: { 1324 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1325 assert(VT == N1.getValueType() && "Not an inreg extend!"); 1326 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 1327 "Cannot *_EXTEND_INREG FP types"); 1328 assert(EVT <= VT && "Not extending!"); 1329 } 1330 1331 default: break; 1332 } 1333#endif 1334 1335 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1336 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1337 if (N1C) { 1338 if (N2C) { 1339 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 1340 switch (Opcode) { 1341 case ISD::ADD: return getConstant(C1 + C2, VT); 1342 case ISD::SUB: return getConstant(C1 - C2, VT); 1343 case ISD::MUL: return getConstant(C1 * C2, VT); 1344 case ISD::UDIV: 1345 if (C2) return getConstant(C1 / C2, VT); 1346 break; 1347 case ISD::UREM : 1348 if (C2) return getConstant(C1 % C2, VT); 1349 break; 1350 case ISD::SDIV : 1351 if (C2) return getConstant(N1C->getSignExtended() / 1352 N2C->getSignExtended(), VT); 1353 break; 1354 case ISD::SREM : 1355 if (C2) return getConstant(N1C->getSignExtended() % 1356 N2C->getSignExtended(), VT); 1357 break; 1358 case ISD::AND : return getConstant(C1 & C2, VT); 1359 case ISD::OR : return getConstant(C1 | C2, VT); 1360 case ISD::XOR : return getConstant(C1 ^ C2, VT); 1361 case ISD::SHL : return getConstant(C1 << C2, VT); 1362 case ISD::SRL : return getConstant(C1 >> C2, VT); 1363 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 1364 case ISD::ROTL : 1365 return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)), 1366 VT); 1367 case ISD::ROTR : 1368 return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 1369 VT); 1370 default: break; 1371 } 1372 } else { // Cannonicalize constant to RHS if commutative 1373 if (isCommutativeBinOp(Opcode)) { 1374 std::swap(N1C, N2C); 1375 std::swap(N1, N2); 1376 } 1377 } 1378 } 1379 1380 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 1381 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 1382 if (N1CFP) { 1383 if (N2CFP) { 1384 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 1385 switch (Opcode) { 1386 case ISD::FADD: return getConstantFP(C1 + C2, VT); 1387 case ISD::FSUB: return getConstantFP(C1 - C2, VT); 1388 case ISD::FMUL: return getConstantFP(C1 * C2, VT); 1389 case ISD::FDIV: 1390 if (C2) return getConstantFP(C1 / C2, VT); 1391 break; 1392 case ISD::FREM : 1393 if (C2) return getConstantFP(fmod(C1, C2), VT); 1394 break; 1395 case ISD::FCOPYSIGN: { 1396 union { 1397 double F; 1398 uint64_t I; 1399 } u1; 1400 union { 1401 double F; 1402 int64_t I; 1403 } u2; 1404 u1.F = C1; 1405 u2.F = C2; 1406 if (u2.I < 0) // Sign bit of RHS set? 1407 u1.I |= 1ULL << 63; // Set the sign bit of the LHS. 1408 else 1409 u1.I &= (1ULL << 63)-1; // Clear the sign bit of the LHS. 1410 return getConstantFP(u1.F, VT); 1411 } 1412 default: break; 1413 } 1414 } else { // Cannonicalize constant to RHS if commutative 1415 if (isCommutativeBinOp(Opcode)) { 1416 std::swap(N1CFP, N2CFP); 1417 std::swap(N1, N2); 1418 } 1419 } 1420 } 1421 1422 // Canonicalize an UNDEF to the RHS, even over a constant. 1423 if (N1.getOpcode() == ISD::UNDEF) { 1424 if (isCommutativeBinOp(Opcode)) { 1425 std::swap(N1, N2); 1426 } else { 1427 switch (Opcode) { 1428 case ISD::FP_ROUND_INREG: 1429 case ISD::SIGN_EXTEND_INREG: 1430 case ISD::SUB: 1431 case ISD::FSUB: 1432 case ISD::FDIV: 1433 case ISD::FREM: 1434 return N1; // fold op(undef, arg2) -> undef 1435 case ISD::UDIV: 1436 case ISD::SDIV: 1437 case ISD::UREM: 1438 case ISD::SREM: 1439 return getConstant(0, VT); // fold op(undef, arg2) -> 0 1440 } 1441 } 1442 } 1443 1444 // Fold a bunch of operators that 1445 if (N2.getOpcode() == ISD::UNDEF) { 1446 switch (Opcode) { 1447 case ISD::ADD: 1448 case ISD::SUB: 1449 case ISD::FADD: 1450 case ISD::FSUB: 1451 case ISD::FMUL: 1452 case ISD::FDIV: 1453 case ISD::FREM: 1454 case ISD::UDIV: 1455 case ISD::SDIV: 1456 case ISD::UREM: 1457 case ISD::SREM: 1458 case ISD::XOR: 1459 return N2; // fold op(arg1, undef) -> undef 1460 case ISD::MUL: 1461 case ISD::AND: 1462 return getConstant(0, VT); // fold op(arg1, undef) -> 0 1463 case ISD::OR: 1464 return getConstant(MVT::getIntVTBitMask(VT), VT); 1465 } 1466 } 1467 1468 // Finally, fold operations that do not require constants. 1469 switch (Opcode) { 1470 case ISD::FP_ROUND_INREG: 1471 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 1472 break; 1473 case ISD::SIGN_EXTEND_INREG: { 1474 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1475 if (EVT == VT) return N1; // Not actually extending 1476 break; 1477 } 1478 1479 // FIXME: figure out how to safely handle things like 1480 // int foo(int x) { return 1 << (x & 255); } 1481 // int bar() { return foo(256); } 1482#if 0 1483 case ISD::SHL: 1484 case ISD::SRL: 1485 case ISD::SRA: 1486 if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG && 1487 cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1) 1488 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1489 else if (N2.getOpcode() == ISD::AND) 1490 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) { 1491 // If the and is only masking out bits that cannot effect the shift, 1492 // eliminate the and. 1493 unsigned NumBits = MVT::getSizeInBits(VT); 1494 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1495 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1496 } 1497 break; 1498#endif 1499 } 1500 1501 // Memoize this node if possible. 1502 SDNode *N; 1503 if (VT != MVT::Flag) { 1504 SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 1505 if (BON) return SDOperand(BON, 0); 1506 1507 BON = N = new SDNode(Opcode, N1, N2); 1508 } else { 1509 N = new SDNode(Opcode, N1, N2); 1510 } 1511 1512 N->setValueTypes(VT); 1513 AllNodes.push_back(N); 1514 return SDOperand(N, 0); 1515} 1516 1517SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1518 SDOperand N1, SDOperand N2, SDOperand N3) { 1519 // Perform various simplifications. 1520 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1521 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1522 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 1523 switch (Opcode) { 1524 case ISD::SETCC: { 1525 // Use SimplifySetCC to simplify SETCC's. 1526 SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get()); 1527 if (Simp.Val) return Simp; 1528 break; 1529 } 1530 case ISD::SELECT: 1531 if (N1C) 1532 if (N1C->getValue()) 1533 return N2; // select true, X, Y -> X 1534 else 1535 return N3; // select false, X, Y -> Y 1536 1537 if (N2 == N3) return N2; // select C, X, X -> X 1538 break; 1539 case ISD::BRCOND: 1540 if (N2C) 1541 if (N2C->getValue()) // Unconditional branch 1542 return getNode(ISD::BR, MVT::Other, N1, N3); 1543 else 1544 return N1; // Never-taken branch 1545 break; 1546 case ISD::VECTOR_SHUFFLE: 1547 assert(VT == N1.getValueType() && VT == N2.getValueType() && 1548 MVT::isVector(VT) && MVT::isVector(N3.getValueType()) && 1549 N3.getOpcode() == ISD::BUILD_VECTOR && 1550 MVT::getVectorNumElements(VT) == N3.getNumOperands() && 1551 "Illegal VECTOR_SHUFFLE node!"); 1552 break; 1553 } 1554 1555 std::vector<SDOperand> Ops; 1556 Ops.reserve(3); 1557 Ops.push_back(N1); 1558 Ops.push_back(N2); 1559 Ops.push_back(N3); 1560 1561 // Memoize node if it doesn't produce a flag. 1562 SDNode *N; 1563 if (VT != MVT::Flag) { 1564 SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))]; 1565 if (E) return SDOperand(E, 0); 1566 E = N = new SDNode(Opcode, N1, N2, N3); 1567 } else { 1568 N = new SDNode(Opcode, N1, N2, N3); 1569 } 1570 N->setValueTypes(VT); 1571 AllNodes.push_back(N); 1572 return SDOperand(N, 0); 1573} 1574 1575SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1576 SDOperand N1, SDOperand N2, SDOperand N3, 1577 SDOperand N4) { 1578 std::vector<SDOperand> Ops; 1579 Ops.reserve(4); 1580 Ops.push_back(N1); 1581 Ops.push_back(N2); 1582 Ops.push_back(N3); 1583 Ops.push_back(N4); 1584 return getNode(Opcode, VT, Ops); 1585} 1586 1587SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1588 SDOperand N1, SDOperand N2, SDOperand N3, 1589 SDOperand N4, SDOperand N5) { 1590 std::vector<SDOperand> Ops; 1591 Ops.reserve(5); 1592 Ops.push_back(N1); 1593 Ops.push_back(N2); 1594 Ops.push_back(N3); 1595 Ops.push_back(N4); 1596 Ops.push_back(N5); 1597 return getNode(Opcode, VT, Ops); 1598} 1599 1600SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 1601 SDOperand Chain, SDOperand Ptr, 1602 SDOperand SV) { 1603 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 1604 if (N) return SDOperand(N, 0); 1605 N = new SDNode(ISD::LOAD, Chain, Ptr, SV); 1606 1607 // Loads have a token chain. 1608 setNodeValueTypes(N, VT, MVT::Other); 1609 AllNodes.push_back(N); 1610 return SDOperand(N, 0); 1611} 1612 1613SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, 1614 SDOperand Chain, SDOperand Ptr, 1615 SDOperand SV) { 1616 std::vector<SDOperand> Ops; 1617 Ops.reserve(5); 1618 Ops.push_back(Chain); 1619 Ops.push_back(Ptr); 1620 Ops.push_back(SV); 1621 Ops.push_back(getConstant(Count, MVT::i32)); 1622 Ops.push_back(getValueType(EVT)); 1623 std::vector<MVT::ValueType> VTs; 1624 VTs.reserve(2); 1625 VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other); // Add token chain. 1626 return getNode(ISD::VLOAD, VTs, Ops); 1627} 1628 1629SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT, 1630 SDOperand Chain, SDOperand Ptr, SDOperand SV, 1631 MVT::ValueType EVT) { 1632 std::vector<SDOperand> Ops; 1633 Ops.reserve(4); 1634 Ops.push_back(Chain); 1635 Ops.push_back(Ptr); 1636 Ops.push_back(SV); 1637 Ops.push_back(getValueType(EVT)); 1638 std::vector<MVT::ValueType> VTs; 1639 VTs.reserve(2); 1640 VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. 1641 return getNode(Opcode, VTs, Ops); 1642} 1643 1644SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 1645 assert((!V || isa<PointerType>(V->getType())) && 1646 "SrcValue is not a pointer?"); 1647 SDNode *&N = ValueNodes[std::make_pair(V, Offset)]; 1648 if (N) return SDOperand(N, 0); 1649 1650 N = new SrcValueSDNode(V, Offset); 1651 AllNodes.push_back(N); 1652 return SDOperand(N, 0); 1653} 1654 1655SDOperand SelectionDAG::getVAArg(MVT::ValueType VT, 1656 SDOperand Chain, SDOperand Ptr, 1657 SDOperand SV) { 1658 std::vector<SDOperand> Ops; 1659 Ops.reserve(3); 1660 Ops.push_back(Chain); 1661 Ops.push_back(Ptr); 1662 Ops.push_back(SV); 1663 std::vector<MVT::ValueType> VTs; 1664 VTs.reserve(2); 1665 VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. 1666 return getNode(ISD::VAARG, VTs, Ops); 1667} 1668 1669SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1670 std::vector<SDOperand> &Ops) { 1671 switch (Ops.size()) { 1672 case 0: return getNode(Opcode, VT); 1673 case 1: return getNode(Opcode, VT, Ops[0]); 1674 case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); 1675 case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); 1676 default: break; 1677 } 1678 1679 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Ops[1].Val); 1680 switch (Opcode) { 1681 default: break; 1682 case ISD::TRUNCSTORE: { 1683 assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!"); 1684 MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT(); 1685#if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store 1686 // If this is a truncating store of a constant, convert to the desired type 1687 // and store it instead. 1688 if (isa<Constant>(Ops[0])) { 1689 SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1); 1690 if (isa<Constant>(Op)) 1691 N1 = Op; 1692 } 1693 // Also for ConstantFP? 1694#endif 1695 if (Ops[0].getValueType() == EVT) // Normal store? 1696 return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]); 1697 assert(Ops[1].getValueType() > EVT && "Not a truncation?"); 1698 assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) && 1699 "Can't do FP-INT conversion!"); 1700 break; 1701 } 1702 case ISD::SELECT_CC: { 1703 assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!"); 1704 assert(Ops[0].getValueType() == Ops[1].getValueType() && 1705 "LHS and RHS of condition must have same type!"); 1706 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1707 "True and False arms of SelectCC must have same type!"); 1708 assert(Ops[2].getValueType() == VT && 1709 "select_cc node must be of same type as true and false value!"); 1710 break; 1711 } 1712 case ISD::BR_CC: { 1713 assert(Ops.size() == 5 && "BR_CC takes 5 operands!"); 1714 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1715 "LHS/RHS of comparison should match types!"); 1716 break; 1717 } 1718 } 1719 1720 // Memoize nodes. 1721 SDNode *N; 1722 if (VT != MVT::Flag) { 1723 SDNode *&E = 1724 OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))]; 1725 if (E) return SDOperand(E, 0); 1726 E = N = new SDNode(Opcode, Ops); 1727 } else { 1728 N = new SDNode(Opcode, Ops); 1729 } 1730 N->setValueTypes(VT); 1731 AllNodes.push_back(N); 1732 return SDOperand(N, 0); 1733} 1734 1735SDOperand SelectionDAG::getNode(unsigned Opcode, 1736 std::vector<MVT::ValueType> &ResultTys, 1737 std::vector<SDOperand> &Ops) { 1738 if (ResultTys.size() == 1) 1739 return getNode(Opcode, ResultTys[0], Ops); 1740 1741 switch (Opcode) { 1742 case ISD::EXTLOAD: 1743 case ISD::SEXTLOAD: 1744 case ISD::ZEXTLOAD: { 1745 MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT(); 1746 assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!"); 1747 // If they are asking for an extending load from/to the same thing, return a 1748 // normal load. 1749 if (ResultTys[0] == EVT) 1750 return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]); 1751 if (MVT::isVector(ResultTys[0])) { 1752 assert(EVT == MVT::getVectorBaseType(ResultTys[0]) && 1753 "Invalid vector extload!"); 1754 } else { 1755 assert(EVT < ResultTys[0] && 1756 "Should only be an extending load, not truncating!"); 1757 } 1758 assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) && 1759 "Cannot sign/zero extend a FP/Vector load!"); 1760 assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) && 1761 "Cannot convert from FP to Int or Int -> FP!"); 1762 break; 1763 } 1764 1765 // FIXME: figure out how to safely handle things like 1766 // int foo(int x) { return 1 << (x & 255); } 1767 // int bar() { return foo(256); } 1768#if 0 1769 case ISD::SRA_PARTS: 1770 case ISD::SRL_PARTS: 1771 case ISD::SHL_PARTS: 1772 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 1773 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 1774 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1775 else if (N3.getOpcode() == ISD::AND) 1776 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 1777 // If the and is only masking out bits that cannot effect the shift, 1778 // eliminate the and. 1779 unsigned NumBits = MVT::getSizeInBits(VT)*2; 1780 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1781 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1782 } 1783 break; 1784#endif 1785 } 1786 1787 // Memoize the node unless it returns a flag. 1788 SDNode *N; 1789 if (ResultTys.back() != MVT::Flag) { 1790 SDNode *&E = 1791 ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))]; 1792 if (E) return SDOperand(E, 0); 1793 E = N = new SDNode(Opcode, Ops); 1794 } else { 1795 N = new SDNode(Opcode, Ops); 1796 } 1797 setNodeValueTypes(N, ResultTys); 1798 AllNodes.push_back(N); 1799 return SDOperand(N, 0); 1800} 1801 1802void SelectionDAG::setNodeValueTypes(SDNode *N, 1803 std::vector<MVT::ValueType> &RetVals) { 1804 switch (RetVals.size()) { 1805 case 0: return; 1806 case 1: N->setValueTypes(RetVals[0]); return; 1807 case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return; 1808 default: break; 1809 } 1810 1811 std::list<std::vector<MVT::ValueType> >::iterator I = 1812 std::find(VTList.begin(), VTList.end(), RetVals); 1813 if (I == VTList.end()) { 1814 VTList.push_front(RetVals); 1815 I = VTList.begin(); 1816 } 1817 1818 N->setValueTypes(&(*I)[0], I->size()); 1819} 1820 1821void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1, 1822 MVT::ValueType VT2) { 1823 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 1824 E = VTList.end(); I != E; ++I) { 1825 if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) { 1826 N->setValueTypes(&(*I)[0], 2); 1827 return; 1828 } 1829 } 1830 std::vector<MVT::ValueType> V; 1831 V.push_back(VT1); 1832 V.push_back(VT2); 1833 VTList.push_front(V); 1834 N->setValueTypes(&(*VTList.begin())[0], 2); 1835} 1836 1837/// UpdateNodeOperands - *Mutate* the specified node in-place to have the 1838/// specified operands. If the resultant node already exists in the DAG, 1839/// this does not modify the specified node, instead it returns the node that 1840/// already exists. If the resultant node does not exist in the DAG, the 1841/// input node is returned. As a degenerate case, if you specify the same 1842/// input operands as the node already has, the input node is returned. 1843SDOperand SelectionDAG:: 1844UpdateNodeOperands(SDOperand InN, SDOperand Op) { 1845 SDNode *N = InN.Val; 1846 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 1847 1848 // Check to see if there is no change. 1849 if (Op == N->getOperand(0)) return InN; 1850 1851 // See if the modified node already exists. 1852 SDNode **NewSlot = FindModifiedNodeSlot(N, Op); 1853 if (NewSlot && *NewSlot) 1854 return SDOperand(*NewSlot, InN.ResNo); 1855 1856 // Nope it doesn't. Remove the node from it's current place in the maps. 1857 if (NewSlot) 1858 RemoveNodeFromCSEMaps(N); 1859 1860 // Now we update the operands. 1861 N->OperandList[0].Val->removeUser(N); 1862 Op.Val->addUser(N); 1863 N->OperandList[0] = Op; 1864 1865 // If this gets put into a CSE map, add it. 1866 if (NewSlot) *NewSlot = N; 1867 return InN; 1868} 1869 1870SDOperand SelectionDAG:: 1871UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { 1872 SDNode *N = InN.Val; 1873 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 1874 1875 // Check to see if there is no change. 1876 bool AnyChange = false; 1877 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 1878 return InN; // No operands changed, just return the input node. 1879 1880 // See if the modified node already exists. 1881 SDNode **NewSlot = FindModifiedNodeSlot(N, Op1, Op2); 1882 if (NewSlot && *NewSlot) 1883 return SDOperand(*NewSlot, InN.ResNo); 1884 1885 // Nope it doesn't. Remove the node from it's current place in the maps. 1886 if (NewSlot) 1887 RemoveNodeFromCSEMaps(N); 1888 1889 // Now we update the operands. 1890 if (N->OperandList[0] != Op1) { 1891 N->OperandList[0].Val->removeUser(N); 1892 Op1.Val->addUser(N); 1893 N->OperandList[0] = Op1; 1894 } 1895 if (N->OperandList[1] != Op2) { 1896 N->OperandList[1].Val->removeUser(N); 1897 Op2.Val->addUser(N); 1898 N->OperandList[1] = Op2; 1899 } 1900 1901 // If this gets put into a CSE map, add it. 1902 if (NewSlot) *NewSlot = N; 1903 return InN; 1904} 1905 1906SDOperand SelectionDAG:: 1907UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 1908 std::vector<SDOperand> Ops; 1909 Ops.push_back(Op1); 1910 Ops.push_back(Op2); 1911 Ops.push_back(Op3); 1912 return UpdateNodeOperands(N, Ops); 1913} 1914 1915SDOperand SelectionDAG:: 1916UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 1917 SDOperand Op3, SDOperand Op4) { 1918 std::vector<SDOperand> Ops; 1919 Ops.push_back(Op1); 1920 Ops.push_back(Op2); 1921 Ops.push_back(Op3); 1922 Ops.push_back(Op4); 1923 return UpdateNodeOperands(N, Ops); 1924} 1925 1926SDOperand SelectionDAG:: 1927UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 1928 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 1929 std::vector<SDOperand> Ops; 1930 Ops.push_back(Op1); 1931 Ops.push_back(Op2); 1932 Ops.push_back(Op3); 1933 Ops.push_back(Op4); 1934 Ops.push_back(Op5); 1935 return UpdateNodeOperands(N, Ops); 1936} 1937 1938 1939SDOperand SelectionDAG:: 1940UpdateNodeOperands(SDOperand InN, const std::vector<SDOperand> &Ops) { 1941 SDNode *N = InN.Val; 1942 assert(N->getNumOperands() == Ops.size() && 1943 "Update with wrong number of operands"); 1944 1945 // Check to see if there is no change. 1946 unsigned NumOps = Ops.size(); 1947 bool AnyChange = false; 1948 for (unsigned i = 0; i != NumOps; ++i) { 1949 if (Ops[i] != N->getOperand(i)) { 1950 AnyChange = true; 1951 break; 1952 } 1953 } 1954 1955 // No operands changed, just return the input node. 1956 if (!AnyChange) return InN; 1957 1958 // See if the modified node already exists. 1959 SDNode **NewSlot = FindModifiedNodeSlot(N, Ops); 1960 if (NewSlot && *NewSlot) 1961 return SDOperand(*NewSlot, InN.ResNo); 1962 1963 // Nope it doesn't. Remove the node from it's current place in the maps. 1964 if (NewSlot) 1965 RemoveNodeFromCSEMaps(N); 1966 1967 // Now we update the operands. 1968 for (unsigned i = 0; i != NumOps; ++i) { 1969 if (N->OperandList[i] != Ops[i]) { 1970 N->OperandList[i].Val->removeUser(N); 1971 Ops[i].Val->addUser(N); 1972 N->OperandList[i] = Ops[i]; 1973 } 1974 } 1975 1976 // If this gets put into a CSE map, add it. 1977 if (NewSlot) *NewSlot = N; 1978 return InN; 1979} 1980 1981 1982 1983 1984/// SelectNodeTo - These are used for target selectors to *mutate* the 1985/// specified node to have the specified return type, Target opcode, and 1986/// operands. Note that target opcodes are stored as 1987/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 1988/// 1989/// Note that SelectNodeTo returns the resultant node. If there is already a 1990/// node of the specified opcode and operands, it returns that node instead of 1991/// the current one. 1992SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1993 MVT::ValueType VT) { 1994 // If an identical node already exists, use it. 1995 SDNode *&ON = NullaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, VT)]; 1996 if (ON) return SDOperand(ON, 0); 1997 1998 RemoveNodeFromCSEMaps(N); 1999 2000 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2001 N->setValueTypes(VT); 2002 2003 ON = N; // Memoize the new node. 2004 return SDOperand(N, 0); 2005} 2006 2007SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2008 MVT::ValueType VT, SDOperand Op1) { 2009 // If an identical node already exists, use it. 2010 SDNode *&ON = UnaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2011 std::make_pair(Op1, VT))]; 2012 if (ON) return SDOperand(ON, 0); 2013 2014 RemoveNodeFromCSEMaps(N); 2015 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2016 N->setValueTypes(VT); 2017 N->setOperands(Op1); 2018 2019 ON = N; // Memoize the new node. 2020 return SDOperand(N, 0); 2021} 2022 2023SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2024 MVT::ValueType VT, SDOperand Op1, 2025 SDOperand Op2) { 2026 // If an identical node already exists, use it. 2027 SDNode *&ON = BinaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2028 std::make_pair(Op1, Op2))]; 2029 if (ON) return SDOperand(ON, 0); 2030 2031 RemoveNodeFromCSEMaps(N); 2032 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2033 N->setValueTypes(VT); 2034 N->setOperands(Op1, Op2); 2035 2036 ON = N; // Memoize the new node. 2037 return SDOperand(N, 0); 2038} 2039 2040SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2041 MVT::ValueType VT, SDOperand Op1, 2042 SDOperand Op2, SDOperand Op3) { 2043 // If an identical node already exists, use it. 2044 std::vector<SDOperand> OpList; 2045 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2046 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2047 std::make_pair(VT, OpList))]; 2048 if (ON) return SDOperand(ON, 0); 2049 2050 RemoveNodeFromCSEMaps(N); 2051 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2052 N->setValueTypes(VT); 2053 N->setOperands(Op1, Op2, Op3); 2054 2055 ON = N; // Memoize the new node. 2056 return SDOperand(N, 0); 2057} 2058 2059SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2060 MVT::ValueType VT, SDOperand Op1, 2061 SDOperand Op2, SDOperand Op3, 2062 SDOperand Op4) { 2063 // If an identical node already exists, use it. 2064 std::vector<SDOperand> OpList; 2065 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2066 OpList.push_back(Op4); 2067 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2068 std::make_pair(VT, OpList))]; 2069 if (ON) return SDOperand(ON, 0); 2070 2071 RemoveNodeFromCSEMaps(N); 2072 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2073 N->setValueTypes(VT); 2074 N->setOperands(Op1, Op2, Op3, Op4); 2075 2076 ON = N; // Memoize the new node. 2077 return SDOperand(N, 0); 2078} 2079 2080SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2081 MVT::ValueType VT, SDOperand Op1, 2082 SDOperand Op2, SDOperand Op3,SDOperand Op4, 2083 SDOperand Op5) { 2084 // If an identical node already exists, use it. 2085 std::vector<SDOperand> OpList; 2086 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2087 OpList.push_back(Op4); OpList.push_back(Op5); 2088 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2089 std::make_pair(VT, OpList))]; 2090 if (ON) return SDOperand(ON, 0); 2091 2092 RemoveNodeFromCSEMaps(N); 2093 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2094 N->setValueTypes(VT); 2095 N->setOperands(Op1, Op2, Op3, Op4, Op5); 2096 2097 ON = N; // Memoize the new node. 2098 return SDOperand(N, 0); 2099} 2100 2101SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2102 MVT::ValueType VT, SDOperand Op1, 2103 SDOperand Op2, SDOperand Op3,SDOperand Op4, 2104 SDOperand Op5, SDOperand Op6) { 2105 // If an identical node already exists, use it. 2106 std::vector<SDOperand> OpList; 2107 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2108 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 2109 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2110 std::make_pair(VT, OpList))]; 2111 if (ON) return SDOperand(ON, 0); 2112 2113 RemoveNodeFromCSEMaps(N); 2114 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2115 N->setValueTypes(VT); 2116 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6); 2117 2118 ON = N; // Memoize the new node. 2119 return SDOperand(N, 0); 2120} 2121 2122SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2123 MVT::ValueType VT, SDOperand Op1, 2124 SDOperand Op2, SDOperand Op3,SDOperand Op4, 2125 SDOperand Op5, SDOperand Op6, 2126 SDOperand Op7) { 2127 // If an identical node already exists, use it. 2128 std::vector<SDOperand> OpList; 2129 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2130 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 2131 OpList.push_back(Op7); 2132 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2133 std::make_pair(VT, OpList))]; 2134 if (ON) return SDOperand(ON, 0); 2135 2136 RemoveNodeFromCSEMaps(N); 2137 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2138 N->setValueTypes(VT); 2139 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7); 2140 2141 ON = N; // Memoize the new node. 2142 return SDOperand(N, 0); 2143} 2144SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2145 MVT::ValueType VT, SDOperand Op1, 2146 SDOperand Op2, SDOperand Op3,SDOperand Op4, 2147 SDOperand Op5, SDOperand Op6, 2148 SDOperand Op7, SDOperand Op8) { 2149 // If an identical node already exists, use it. 2150 std::vector<SDOperand> OpList; 2151 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2152 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 2153 OpList.push_back(Op7); OpList.push_back(Op8); 2154 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2155 std::make_pair(VT, OpList))]; 2156 if (ON) return SDOperand(ON, 0); 2157 2158 RemoveNodeFromCSEMaps(N); 2159 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2160 N->setValueTypes(VT); 2161 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8); 2162 2163 ON = N; // Memoize the new node. 2164 return SDOperand(N, 0); 2165} 2166 2167SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2168 MVT::ValueType VT1, MVT::ValueType VT2, 2169 SDOperand Op1, SDOperand Op2) { 2170 // If an identical node already exists, use it. 2171 std::vector<SDOperand> OpList; 2172 OpList.push_back(Op1); OpList.push_back(Op2); 2173 std::vector<MVT::ValueType> VTList; 2174 VTList.push_back(VT1); VTList.push_back(VT2); 2175 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2176 std::make_pair(VTList, OpList))]; 2177 if (ON) return SDOperand(ON, 0); 2178 2179 RemoveNodeFromCSEMaps(N); 2180 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2181 setNodeValueTypes(N, VT1, VT2); 2182 N->setOperands(Op1, Op2); 2183 2184 ON = N; // Memoize the new node. 2185 return SDOperand(N, 0); 2186} 2187 2188SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2189 MVT::ValueType VT1, MVT::ValueType VT2, 2190 SDOperand Op1, SDOperand Op2, 2191 SDOperand Op3) { 2192 // If an identical node already exists, use it. 2193 std::vector<SDOperand> OpList; 2194 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2195 std::vector<MVT::ValueType> VTList; 2196 VTList.push_back(VT1); VTList.push_back(VT2); 2197 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2198 std::make_pair(VTList, OpList))]; 2199 if (ON) return SDOperand(ON, 0); 2200 2201 RemoveNodeFromCSEMaps(N); 2202 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2203 setNodeValueTypes(N, VT1, VT2); 2204 N->setOperands(Op1, Op2, Op3); 2205 2206 ON = N; // Memoize the new node. 2207 return SDOperand(N, 0); 2208} 2209 2210SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2211 MVT::ValueType VT1, MVT::ValueType VT2, 2212 SDOperand Op1, SDOperand Op2, 2213 SDOperand Op3, SDOperand Op4) { 2214 // If an identical node already exists, use it. 2215 std::vector<SDOperand> OpList; 2216 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2217 OpList.push_back(Op4); 2218 std::vector<MVT::ValueType> VTList; 2219 VTList.push_back(VT1); VTList.push_back(VT2); 2220 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2221 std::make_pair(VTList, OpList))]; 2222 if (ON) return SDOperand(ON, 0); 2223 2224 RemoveNodeFromCSEMaps(N); 2225 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2226 setNodeValueTypes(N, VT1, VT2); 2227 N->setOperands(Op1, Op2, Op3, Op4); 2228 2229 ON = N; // Memoize the new node. 2230 return SDOperand(N, 0); 2231} 2232 2233SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2234 MVT::ValueType VT1, MVT::ValueType VT2, 2235 SDOperand Op1, SDOperand Op2, 2236 SDOperand Op3, SDOperand Op4, 2237 SDOperand Op5) { 2238 // If an identical node already exists, use it. 2239 std::vector<SDOperand> OpList; 2240 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 2241 OpList.push_back(Op4); OpList.push_back(Op5); 2242 std::vector<MVT::ValueType> VTList; 2243 VTList.push_back(VT1); VTList.push_back(VT2); 2244 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 2245 std::make_pair(VTList, OpList))]; 2246 if (ON) return SDOperand(ON, 0); 2247 2248 RemoveNodeFromCSEMaps(N); 2249 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2250 setNodeValueTypes(N, VT1, VT2); 2251 N->setOperands(Op1, Op2, Op3, Op4, Op5); 2252 2253 ON = N; // Memoize the new node. 2254 return SDOperand(N, 0); 2255} 2256 2257/// getTargetNode - These are used for target selectors to create a new node 2258/// with specified return type(s), target opcode, and operands. 2259/// 2260/// Note that getTargetNode returns the resultant node. If there is already a 2261/// node of the specified opcode and operands, it returns that node instead of 2262/// the current one. 2263SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) { 2264 return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val; 2265} 2266SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2267 SDOperand Op1) { 2268 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val; 2269} 2270SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2271 SDOperand Op1, SDOperand Op2) { 2272 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val; 2273} 2274SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2275 SDOperand Op1, SDOperand Op2, SDOperand Op3) { 2276 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; 2277} 2278SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2279 SDOperand Op1, SDOperand Op2, SDOperand Op3, 2280 SDOperand Op4) { 2281 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val; 2282} 2283SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2284 SDOperand Op1, SDOperand Op2, SDOperand Op3, 2285 SDOperand Op4, SDOperand Op5) { 2286 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val; 2287} 2288SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2289 SDOperand Op1, SDOperand Op2, SDOperand Op3, 2290 SDOperand Op4, SDOperand Op5, SDOperand Op6) { 2291 std::vector<SDOperand> Ops; 2292 Ops.reserve(6); 2293 Ops.push_back(Op1); 2294 Ops.push_back(Op2); 2295 Ops.push_back(Op3); 2296 Ops.push_back(Op4); 2297 Ops.push_back(Op5); 2298 Ops.push_back(Op6); 2299 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 2300} 2301SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2302 SDOperand Op1, SDOperand Op2, SDOperand Op3, 2303 SDOperand Op4, SDOperand Op5, SDOperand Op6, 2304 SDOperand Op7) { 2305 std::vector<SDOperand> Ops; 2306 Ops.reserve(7); 2307 Ops.push_back(Op1); 2308 Ops.push_back(Op2); 2309 Ops.push_back(Op3); 2310 Ops.push_back(Op4); 2311 Ops.push_back(Op5); 2312 Ops.push_back(Op6); 2313 Ops.push_back(Op7); 2314 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 2315} 2316SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2317 SDOperand Op1, SDOperand Op2, SDOperand Op3, 2318 SDOperand Op4, SDOperand Op5, SDOperand Op6, 2319 SDOperand Op7, SDOperand Op8) { 2320 std::vector<SDOperand> Ops; 2321 Ops.reserve(8); 2322 Ops.push_back(Op1); 2323 Ops.push_back(Op2); 2324 Ops.push_back(Op3); 2325 Ops.push_back(Op4); 2326 Ops.push_back(Op5); 2327 Ops.push_back(Op6); 2328 Ops.push_back(Op7); 2329 Ops.push_back(Op8); 2330 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 2331} 2332SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2333 std::vector<SDOperand> &Ops) { 2334 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 2335} 2336SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2337 MVT::ValueType VT2, SDOperand Op1) { 2338 std::vector<MVT::ValueType> ResultTys; 2339 ResultTys.push_back(VT1); 2340 ResultTys.push_back(VT2); 2341 std::vector<SDOperand> Ops; 2342 Ops.push_back(Op1); 2343 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2344} 2345SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2346 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) { 2347 std::vector<MVT::ValueType> ResultTys; 2348 ResultTys.push_back(VT1); 2349 ResultTys.push_back(VT2); 2350 std::vector<SDOperand> Ops; 2351 Ops.push_back(Op1); 2352 Ops.push_back(Op2); 2353 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2354} 2355SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2356 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 2357 SDOperand Op3) { 2358 std::vector<MVT::ValueType> ResultTys; 2359 ResultTys.push_back(VT1); 2360 ResultTys.push_back(VT2); 2361 std::vector<SDOperand> Ops; 2362 Ops.push_back(Op1); 2363 Ops.push_back(Op2); 2364 Ops.push_back(Op3); 2365 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2366} 2367SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2368 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 2369 SDOperand Op3, SDOperand Op4) { 2370 std::vector<MVT::ValueType> ResultTys; 2371 ResultTys.push_back(VT1); 2372 ResultTys.push_back(VT2); 2373 std::vector<SDOperand> Ops; 2374 Ops.push_back(Op1); 2375 Ops.push_back(Op2); 2376 Ops.push_back(Op3); 2377 Ops.push_back(Op4); 2378 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2379} 2380SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2381 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 2382 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 2383 std::vector<MVT::ValueType> ResultTys; 2384 ResultTys.push_back(VT1); 2385 ResultTys.push_back(VT2); 2386 std::vector<SDOperand> Ops; 2387 Ops.push_back(Op1); 2388 Ops.push_back(Op2); 2389 Ops.push_back(Op3); 2390 Ops.push_back(Op4); 2391 Ops.push_back(Op5); 2392 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2393} 2394SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2395 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 2396 SDOperand Op3, SDOperand Op4, SDOperand Op5, 2397 SDOperand Op6) { 2398 std::vector<MVT::ValueType> ResultTys; 2399 ResultTys.push_back(VT1); 2400 ResultTys.push_back(VT2); 2401 std::vector<SDOperand> Ops; 2402 Ops.push_back(Op1); 2403 Ops.push_back(Op2); 2404 Ops.push_back(Op3); 2405 Ops.push_back(Op4); 2406 Ops.push_back(Op5); 2407 Ops.push_back(Op6); 2408 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2409} 2410SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2411 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 2412 SDOperand Op3, SDOperand Op4, SDOperand Op5, 2413 SDOperand Op6, SDOperand Op7) { 2414 std::vector<MVT::ValueType> ResultTys; 2415 ResultTys.push_back(VT1); 2416 ResultTys.push_back(VT2); 2417 std::vector<SDOperand> Ops; 2418 Ops.push_back(Op1); 2419 Ops.push_back(Op2); 2420 Ops.push_back(Op3); 2421 Ops.push_back(Op4); 2422 Ops.push_back(Op5); 2423 Ops.push_back(Op6); 2424 Ops.push_back(Op7); 2425 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2426} 2427SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2428 MVT::ValueType VT2, MVT::ValueType VT3, 2429 SDOperand Op1, SDOperand Op2) { 2430 std::vector<MVT::ValueType> ResultTys; 2431 ResultTys.push_back(VT1); 2432 ResultTys.push_back(VT2); 2433 ResultTys.push_back(VT3); 2434 std::vector<SDOperand> Ops; 2435 Ops.push_back(Op1); 2436 Ops.push_back(Op2); 2437 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2438} 2439SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2440 MVT::ValueType VT2, MVT::ValueType VT3, 2441 SDOperand Op1, SDOperand Op2, 2442 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 2443 std::vector<MVT::ValueType> ResultTys; 2444 ResultTys.push_back(VT1); 2445 ResultTys.push_back(VT2); 2446 ResultTys.push_back(VT3); 2447 std::vector<SDOperand> Ops; 2448 Ops.push_back(Op1); 2449 Ops.push_back(Op2); 2450 Ops.push_back(Op3); 2451 Ops.push_back(Op4); 2452 Ops.push_back(Op5); 2453 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2454} 2455SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2456 MVT::ValueType VT2, MVT::ValueType VT3, 2457 SDOperand Op1, SDOperand Op2, 2458 SDOperand Op3, SDOperand Op4, SDOperand Op5, 2459 SDOperand Op6) { 2460 std::vector<MVT::ValueType> ResultTys; 2461 ResultTys.push_back(VT1); 2462 ResultTys.push_back(VT2); 2463 ResultTys.push_back(VT3); 2464 std::vector<SDOperand> Ops; 2465 Ops.push_back(Op1); 2466 Ops.push_back(Op2); 2467 Ops.push_back(Op3); 2468 Ops.push_back(Op4); 2469 Ops.push_back(Op5); 2470 Ops.push_back(Op6); 2471 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2472} 2473SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2474 MVT::ValueType VT2, MVT::ValueType VT3, 2475 SDOperand Op1, SDOperand Op2, 2476 SDOperand Op3, SDOperand Op4, SDOperand Op5, 2477 SDOperand Op6, SDOperand Op7) { 2478 std::vector<MVT::ValueType> ResultTys; 2479 ResultTys.push_back(VT1); 2480 ResultTys.push_back(VT2); 2481 ResultTys.push_back(VT3); 2482 std::vector<SDOperand> Ops; 2483 Ops.push_back(Op1); 2484 Ops.push_back(Op2); 2485 Ops.push_back(Op3); 2486 Ops.push_back(Op4); 2487 Ops.push_back(Op5); 2488 Ops.push_back(Op6); 2489 Ops.push_back(Op7); 2490 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2491} 2492SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2493 MVT::ValueType VT2, std::vector<SDOperand> &Ops) { 2494 std::vector<MVT::ValueType> ResultTys; 2495 ResultTys.push_back(VT1); 2496 ResultTys.push_back(VT2); 2497 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 2498} 2499 2500// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2501/// This can cause recursive merging of nodes in the DAG. 2502/// 2503/// This version assumes From/To have a single result value. 2504/// 2505void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN, 2506 std::vector<SDNode*> *Deleted) { 2507 SDNode *From = FromN.Val, *To = ToN.Val; 2508 assert(From->getNumValues() == 1 && To->getNumValues() == 1 && 2509 "Cannot replace with this method!"); 2510 assert(From != To && "Cannot replace uses of with self"); 2511 2512 while (!From->use_empty()) { 2513 // Process users until they are all gone. 2514 SDNode *U = *From->use_begin(); 2515 2516 // This node is about to morph, remove its old self from the CSE maps. 2517 RemoveNodeFromCSEMaps(U); 2518 2519 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2520 I != E; ++I) 2521 if (I->Val == From) { 2522 From->removeUser(U); 2523 I->Val = To; 2524 To->addUser(U); 2525 } 2526 2527 // Now that we have modified U, add it back to the CSE maps. If it already 2528 // exists there, recursively merge the results together. 2529 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2530 ReplaceAllUsesWith(U, Existing, Deleted); 2531 // U is now dead. 2532 if (Deleted) Deleted->push_back(U); 2533 DeleteNodeNotInCSEMaps(U); 2534 } 2535 } 2536} 2537 2538/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2539/// This can cause recursive merging of nodes in the DAG. 2540/// 2541/// This version assumes From/To have matching types and numbers of result 2542/// values. 2543/// 2544void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 2545 std::vector<SDNode*> *Deleted) { 2546 assert(From != To && "Cannot replace uses of with self"); 2547 assert(From->getNumValues() == To->getNumValues() && 2548 "Cannot use this version of ReplaceAllUsesWith!"); 2549 if (From->getNumValues() == 1) { // If possible, use the faster version. 2550 ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted); 2551 return; 2552 } 2553 2554 while (!From->use_empty()) { 2555 // Process users until they are all gone. 2556 SDNode *U = *From->use_begin(); 2557 2558 // This node is about to morph, remove its old self from the CSE maps. 2559 RemoveNodeFromCSEMaps(U); 2560 2561 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2562 I != E; ++I) 2563 if (I->Val == From) { 2564 From->removeUser(U); 2565 I->Val = To; 2566 To->addUser(U); 2567 } 2568 2569 // Now that we have modified U, add it back to the CSE maps. If it already 2570 // exists there, recursively merge the results together. 2571 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2572 ReplaceAllUsesWith(U, Existing, Deleted); 2573 // U is now dead. 2574 if (Deleted) Deleted->push_back(U); 2575 DeleteNodeNotInCSEMaps(U); 2576 } 2577 } 2578} 2579 2580/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2581/// This can cause recursive merging of nodes in the DAG. 2582/// 2583/// This version can replace From with any result values. To must match the 2584/// number and types of values returned by From. 2585void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 2586 const std::vector<SDOperand> &To, 2587 std::vector<SDNode*> *Deleted) { 2588 assert(From->getNumValues() == To.size() && 2589 "Incorrect number of values to replace with!"); 2590 if (To.size() == 1 && To[0].Val->getNumValues() == 1) { 2591 // Degenerate case handled above. 2592 ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); 2593 return; 2594 } 2595 2596 while (!From->use_empty()) { 2597 // Process users until they are all gone. 2598 SDNode *U = *From->use_begin(); 2599 2600 // This node is about to morph, remove its old self from the CSE maps. 2601 RemoveNodeFromCSEMaps(U); 2602 2603 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2604 I != E; ++I) 2605 if (I->Val == From) { 2606 const SDOperand &ToOp = To[I->ResNo]; 2607 From->removeUser(U); 2608 *I = ToOp; 2609 ToOp.Val->addUser(U); 2610 } 2611 2612 // Now that we have modified U, add it back to the CSE maps. If it already 2613 // exists there, recursively merge the results together. 2614 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2615 ReplaceAllUsesWith(U, Existing, Deleted); 2616 // U is now dead. 2617 if (Deleted) Deleted->push_back(U); 2618 DeleteNodeNotInCSEMaps(U); 2619 } 2620 } 2621} 2622 2623/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 2624/// uses of other values produced by From.Val alone. The Deleted vector is 2625/// handled the same was as for ReplaceAllUsesWith. 2626void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 2627 std::vector<SDNode*> &Deleted) { 2628 assert(From != To && "Cannot replace a value with itself"); 2629 // Handle the simple, trivial, case efficiently. 2630 if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) { 2631 ReplaceAllUsesWith(From, To, &Deleted); 2632 return; 2633 } 2634 2635 // Get all of the users in a nice, deterministically ordered, uniqued set. 2636 SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end()); 2637 2638 while (!Users.empty()) { 2639 // We know that this user uses some value of From. If it is the right 2640 // value, update it. 2641 SDNode *User = Users.back(); 2642 Users.pop_back(); 2643 2644 for (SDOperand *Op = User->OperandList, 2645 *E = User->OperandList+User->NumOperands; Op != E; ++Op) { 2646 if (*Op == From) { 2647 // Okay, we know this user needs to be updated. Remove its old self 2648 // from the CSE maps. 2649 RemoveNodeFromCSEMaps(User); 2650 2651 // Update all operands that match "From". 2652 for (; Op != E; ++Op) { 2653 if (*Op == From) { 2654 From.Val->removeUser(User); 2655 *Op = To; 2656 To.Val->addUser(User); 2657 } 2658 } 2659 2660 // Now that we have modified User, add it back to the CSE maps. If it 2661 // already exists there, recursively merge the results together. 2662 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) { 2663 unsigned NumDeleted = Deleted.size(); 2664 ReplaceAllUsesWith(User, Existing, &Deleted); 2665 2666 // User is now dead. 2667 Deleted.push_back(User); 2668 DeleteNodeNotInCSEMaps(User); 2669 2670 // We have to be careful here, because ReplaceAllUsesWith could have 2671 // deleted a user of From, which means there may be dangling pointers 2672 // in the "Users" setvector. Scan over the deleted node pointers and 2673 // remove them from the setvector. 2674 for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i) 2675 Users.remove(Deleted[i]); 2676 } 2677 break; // Exit the operand scanning loop. 2678 } 2679 } 2680 } 2681} 2682 2683 2684//===----------------------------------------------------------------------===// 2685// SDNode Class 2686//===----------------------------------------------------------------------===// 2687 2688 2689/// getValueTypeList - Return a pointer to the specified value type. 2690/// 2691MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { 2692 static MVT::ValueType VTs[MVT::LAST_VALUETYPE]; 2693 VTs[VT] = VT; 2694 return &VTs[VT]; 2695} 2696 2697/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 2698/// indicated value. This method ignores uses of other values defined by this 2699/// operation. 2700bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 2701 assert(Value < getNumValues() && "Bad value!"); 2702 2703 // If there is only one value, this is easy. 2704 if (getNumValues() == 1) 2705 return use_size() == NUses; 2706 if (Uses.size() < NUses) return false; 2707 2708 SDOperand TheValue(const_cast<SDNode *>(this), Value); 2709 2710 std::set<SDNode*> UsersHandled; 2711 2712 for (std::vector<SDNode*>::const_iterator UI = Uses.begin(), E = Uses.end(); 2713 UI != E; ++UI) { 2714 SDNode *User = *UI; 2715 if (User->getNumOperands() == 1 || 2716 UsersHandled.insert(User).second) // First time we've seen this? 2717 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 2718 if (User->getOperand(i) == TheValue) { 2719 if (NUses == 0) 2720 return false; // too many uses 2721 --NUses; 2722 } 2723 } 2724 2725 // Found exactly the right number of uses? 2726 return NUses == 0; 2727} 2728 2729 2730// isOnlyUse - Return true if this node is the only use of N. 2731bool SDNode::isOnlyUse(SDNode *N) const { 2732 bool Seen = false; 2733 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 2734 SDNode *User = *I; 2735 if (User == this) 2736 Seen = true; 2737 else 2738 return false; 2739 } 2740 2741 return Seen; 2742} 2743 2744// isOperand - Return true if this node is an operand of N. 2745bool SDOperand::isOperand(SDNode *N) const { 2746 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 2747 if (*this == N->getOperand(i)) 2748 return true; 2749 return false; 2750} 2751 2752bool SDNode::isOperand(SDNode *N) const { 2753 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 2754 if (this == N->OperandList[i].Val) 2755 return true; 2756 return false; 2757} 2758 2759const char *SDNode::getOperationName(const SelectionDAG *G) const { 2760 switch (getOpcode()) { 2761 default: 2762 if (getOpcode() < ISD::BUILTIN_OP_END) 2763 return "<<Unknown DAG Node>>"; 2764 else { 2765 if (G) { 2766 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 2767 if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) 2768 return TII->getName(getOpcode()-ISD::BUILTIN_OP_END); 2769 2770 TargetLowering &TLI = G->getTargetLoweringInfo(); 2771 const char *Name = 2772 TLI.getTargetNodeName(getOpcode()); 2773 if (Name) return Name; 2774 } 2775 2776 return "<<Unknown Target Node>>"; 2777 } 2778 2779 case ISD::PCMARKER: return "PCMarker"; 2780 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 2781 case ISD::SRCVALUE: return "SrcValue"; 2782 case ISD::EntryToken: return "EntryToken"; 2783 case ISD::TokenFactor: return "TokenFactor"; 2784 case ISD::AssertSext: return "AssertSext"; 2785 case ISD::AssertZext: return "AssertZext"; 2786 2787 case ISD::STRING: return "String"; 2788 case ISD::BasicBlock: return "BasicBlock"; 2789 case ISD::VALUETYPE: return "ValueType"; 2790 case ISD::Register: return "Register"; 2791 2792 case ISD::Constant: return "Constant"; 2793 case ISD::ConstantFP: return "ConstantFP"; 2794 case ISD::GlobalAddress: return "GlobalAddress"; 2795 case ISD::FrameIndex: return "FrameIndex"; 2796 case ISD::JumpTable: return "JumpTable"; 2797 case ISD::ConstantPool: return "ConstantPool"; 2798 case ISD::ExternalSymbol: return "ExternalSymbol"; 2799 case ISD::INTRINSIC_WO_CHAIN: { 2800 unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue(); 2801 return Intrinsic::getName((Intrinsic::ID)IID); 2802 } 2803 case ISD::INTRINSIC_VOID: 2804 case ISD::INTRINSIC_W_CHAIN: { 2805 unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue(); 2806 return Intrinsic::getName((Intrinsic::ID)IID); 2807 } 2808 2809 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 2810 case ISD::TargetConstant: return "TargetConstant"; 2811 case ISD::TargetConstantFP:return "TargetConstantFP"; 2812 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 2813 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 2814 case ISD::TargetJumpTable: return "TargetJumpTable"; 2815 case ISD::TargetConstantPool: return "TargetConstantPool"; 2816 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 2817 2818 case ISD::CopyToReg: return "CopyToReg"; 2819 case ISD::CopyFromReg: return "CopyFromReg"; 2820 case ISD::UNDEF: return "undef"; 2821 case ISD::MERGE_VALUES: return "mergevalues"; 2822 case ISD::INLINEASM: return "inlineasm"; 2823 case ISD::HANDLENODE: return "handlenode"; 2824 case ISD::FORMAL_ARGUMENTS: return "formal_arguments"; 2825 2826 // Unary operators 2827 case ISD::FABS: return "fabs"; 2828 case ISD::FNEG: return "fneg"; 2829 case ISD::FSQRT: return "fsqrt"; 2830 case ISD::FSIN: return "fsin"; 2831 case ISD::FCOS: return "fcos"; 2832 2833 // Binary operators 2834 case ISD::ADD: return "add"; 2835 case ISD::SUB: return "sub"; 2836 case ISD::MUL: return "mul"; 2837 case ISD::MULHU: return "mulhu"; 2838 case ISD::MULHS: return "mulhs"; 2839 case ISD::SDIV: return "sdiv"; 2840 case ISD::UDIV: return "udiv"; 2841 case ISD::SREM: return "srem"; 2842 case ISD::UREM: return "urem"; 2843 case ISD::AND: return "and"; 2844 case ISD::OR: return "or"; 2845 case ISD::XOR: return "xor"; 2846 case ISD::SHL: return "shl"; 2847 case ISD::SRA: return "sra"; 2848 case ISD::SRL: return "srl"; 2849 case ISD::ROTL: return "rotl"; 2850 case ISD::ROTR: return "rotr"; 2851 case ISD::FADD: return "fadd"; 2852 case ISD::FSUB: return "fsub"; 2853 case ISD::FMUL: return "fmul"; 2854 case ISD::FDIV: return "fdiv"; 2855 case ISD::FREM: return "frem"; 2856 case ISD::FCOPYSIGN: return "fcopysign"; 2857 case ISD::VADD: return "vadd"; 2858 case ISD::VSUB: return "vsub"; 2859 case ISD::VMUL: return "vmul"; 2860 case ISD::VSDIV: return "vsdiv"; 2861 case ISD::VUDIV: return "vudiv"; 2862 case ISD::VAND: return "vand"; 2863 case ISD::VOR: return "vor"; 2864 case ISD::VXOR: return "vxor"; 2865 2866 case ISD::SETCC: return "setcc"; 2867 case ISD::SELECT: return "select"; 2868 case ISD::SELECT_CC: return "select_cc"; 2869 case ISD::VSELECT: return "vselect"; 2870 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 2871 case ISD::VINSERT_VECTOR_ELT: return "vinsert_vector_elt"; 2872 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 2873 case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt"; 2874 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 2875 case ISD::VBUILD_VECTOR: return "vbuild_vector"; 2876 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 2877 case ISD::VVECTOR_SHUFFLE: return "vvector_shuffle"; 2878 case ISD::VBIT_CONVERT: return "vbit_convert"; 2879 case ISD::ADDC: return "addc"; 2880 case ISD::ADDE: return "adde"; 2881 case ISD::SUBC: return "subc"; 2882 case ISD::SUBE: return "sube"; 2883 case ISD::SHL_PARTS: return "shl_parts"; 2884 case ISD::SRA_PARTS: return "sra_parts"; 2885 case ISD::SRL_PARTS: return "srl_parts"; 2886 2887 // Conversion operators. 2888 case ISD::SIGN_EXTEND: return "sign_extend"; 2889 case ISD::ZERO_EXTEND: return "zero_extend"; 2890 case ISD::ANY_EXTEND: return "any_extend"; 2891 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 2892 case ISD::TRUNCATE: return "truncate"; 2893 case ISD::FP_ROUND: return "fp_round"; 2894 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 2895 case ISD::FP_EXTEND: return "fp_extend"; 2896 2897 case ISD::SINT_TO_FP: return "sint_to_fp"; 2898 case ISD::UINT_TO_FP: return "uint_to_fp"; 2899 case ISD::FP_TO_SINT: return "fp_to_sint"; 2900 case ISD::FP_TO_UINT: return "fp_to_uint"; 2901 case ISD::BIT_CONVERT: return "bit_convert"; 2902 2903 // Control flow instructions 2904 case ISD::BR: return "br"; 2905 case ISD::BRIND: return "brind"; 2906 case ISD::BRCOND: return "brcond"; 2907 case ISD::BR_CC: return "br_cc"; 2908 case ISD::RET: return "ret"; 2909 case ISD::CALLSEQ_START: return "callseq_start"; 2910 case ISD::CALLSEQ_END: return "callseq_end"; 2911 2912 // Other operators 2913 case ISD::LOAD: return "load"; 2914 case ISD::STORE: return "store"; 2915 case ISD::VLOAD: return "vload"; 2916 case ISD::EXTLOAD: return "extload"; 2917 case ISD::SEXTLOAD: return "sextload"; 2918 case ISD::ZEXTLOAD: return "zextload"; 2919 case ISD::TRUNCSTORE: return "truncstore"; 2920 case ISD::VAARG: return "vaarg"; 2921 case ISD::VACOPY: return "vacopy"; 2922 case ISD::VAEND: return "vaend"; 2923 case ISD::VASTART: return "vastart"; 2924 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 2925 case ISD::EXTRACT_ELEMENT: return "extract_element"; 2926 case ISD::BUILD_PAIR: return "build_pair"; 2927 case ISD::STACKSAVE: return "stacksave"; 2928 case ISD::STACKRESTORE: return "stackrestore"; 2929 2930 // Block memory operations. 2931 case ISD::MEMSET: return "memset"; 2932 case ISD::MEMCPY: return "memcpy"; 2933 case ISD::MEMMOVE: return "memmove"; 2934 2935 // Bit manipulation 2936 case ISD::BSWAP: return "bswap"; 2937 case ISD::CTPOP: return "ctpop"; 2938 case ISD::CTTZ: return "cttz"; 2939 case ISD::CTLZ: return "ctlz"; 2940 2941 // Debug info 2942 case ISD::LOCATION: return "location"; 2943 case ISD::DEBUG_LOC: return "debug_loc"; 2944 case ISD::DEBUG_LABEL: return "debug_label"; 2945 2946 case ISD::CONDCODE: 2947 switch (cast<CondCodeSDNode>(this)->get()) { 2948 default: assert(0 && "Unknown setcc condition!"); 2949 case ISD::SETOEQ: return "setoeq"; 2950 case ISD::SETOGT: return "setogt"; 2951 case ISD::SETOGE: return "setoge"; 2952 case ISD::SETOLT: return "setolt"; 2953 case ISD::SETOLE: return "setole"; 2954 case ISD::SETONE: return "setone"; 2955 2956 case ISD::SETO: return "seto"; 2957 case ISD::SETUO: return "setuo"; 2958 case ISD::SETUEQ: return "setue"; 2959 case ISD::SETUGT: return "setugt"; 2960 case ISD::SETUGE: return "setuge"; 2961 case ISD::SETULT: return "setult"; 2962 case ISD::SETULE: return "setule"; 2963 case ISD::SETUNE: return "setune"; 2964 2965 case ISD::SETEQ: return "seteq"; 2966 case ISD::SETGT: return "setgt"; 2967 case ISD::SETGE: return "setge"; 2968 case ISD::SETLT: return "setlt"; 2969 case ISD::SETLE: return "setle"; 2970 case ISD::SETNE: return "setne"; 2971 } 2972 } 2973} 2974 2975void SDNode::dump() const { dump(0); } 2976void SDNode::dump(const SelectionDAG *G) const { 2977 std::cerr << (void*)this << ": "; 2978 2979 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 2980 if (i) std::cerr << ","; 2981 if (getValueType(i) == MVT::Other) 2982 std::cerr << "ch"; 2983 else 2984 std::cerr << MVT::getValueTypeString(getValueType(i)); 2985 } 2986 std::cerr << " = " << getOperationName(G); 2987 2988 std::cerr << " "; 2989 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 2990 if (i) std::cerr << ", "; 2991 std::cerr << (void*)getOperand(i).Val; 2992 if (unsigned RN = getOperand(i).ResNo) 2993 std::cerr << ":" << RN; 2994 } 2995 2996 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 2997 std::cerr << "<" << CSDN->getValue() << ">"; 2998 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 2999 std::cerr << "<" << CSDN->getValue() << ">"; 3000 } else if (const GlobalAddressSDNode *GADN = 3001 dyn_cast<GlobalAddressSDNode>(this)) { 3002 int offset = GADN->getOffset(); 3003 std::cerr << "<"; 3004 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 3005 if (offset > 0) 3006 std::cerr << " + " << offset; 3007 else 3008 std::cerr << " " << offset; 3009 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 3010 std::cerr << "<" << FIDN->getIndex() << ">"; 3011 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 3012 int offset = CP->getOffset(); 3013 std::cerr << "<" << *CP->get() << ">"; 3014 if (offset > 0) 3015 std::cerr << " + " << offset; 3016 else 3017 std::cerr << " " << offset; 3018 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 3019 std::cerr << "<"; 3020 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 3021 if (LBB) 3022 std::cerr << LBB->getName() << " "; 3023 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 3024 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 3025 if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { 3026 std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg()); 3027 } else { 3028 std::cerr << " #" << R->getReg(); 3029 } 3030 } else if (const ExternalSymbolSDNode *ES = 3031 dyn_cast<ExternalSymbolSDNode>(this)) { 3032 std::cerr << "'" << ES->getSymbol() << "'"; 3033 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 3034 if (M->getValue()) 3035 std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; 3036 else 3037 std::cerr << "<null:" << M->getOffset() << ">"; 3038 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 3039 std::cerr << ":" << getValueTypeString(N->getVT()); 3040 } 3041} 3042 3043static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 3044 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 3045 if (N->getOperand(i).Val->hasOneUse()) 3046 DumpNodes(N->getOperand(i).Val, indent+2, G); 3047 else 3048 std::cerr << "\n" << std::string(indent+2, ' ') 3049 << (void*)N->getOperand(i).Val << ": <multiple use>"; 3050 3051 3052 std::cerr << "\n" << std::string(indent, ' '); 3053 N->dump(G); 3054} 3055 3056void SelectionDAG::dump() const { 3057 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 3058 std::vector<const SDNode*> Nodes; 3059 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 3060 I != E; ++I) 3061 Nodes.push_back(I); 3062 3063 std::sort(Nodes.begin(), Nodes.end()); 3064 3065 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 3066 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 3067 DumpNodes(Nodes[i], 2, this); 3068 } 3069 3070 DumpNodes(getRoot().Val, 2, this); 3071 3072 std::cerr << "\n\n"; 3073} 3074 3075/// InsertISelMapEntry - A helper function to insert a key / element pair 3076/// into a SDOperand to SDOperand map. This is added to avoid the map 3077/// insertion operator from being inlined. 3078void SelectionDAG::InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map, 3079 SDNode *Key, unsigned KeyResNo, 3080 SDNode *Element, unsigned ElementResNo) { 3081 Map.insert(std::make_pair(SDOperand(Key, KeyResNo), 3082 SDOperand(Element, ElementResNo))); 3083} 3084