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