SelectionDAG.cpp revision bbe2b709480f1b89d9ac4d42c2c29e7c29dca3bc
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/GlobalVariable.h" 17#include "llvm/Intrinsics.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/Assembly/Writer.h" 20#include "llvm/CodeGen/MachineBasicBlock.h" 21#include "llvm/CodeGen/MachineConstantPool.h" 22#include "llvm/Support/MathExtras.h" 23#include "llvm/Target/MRegisterInfo.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/Target/TargetLowering.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/ADT/SetVector.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/StringExtras.h" 32#include <algorithm> 33#include <cmath> 34using namespace llvm; 35 36/// makeVTList - Return an instance of the SDVTList struct initialized with the 37/// specified members. 38static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) { 39 SDVTList Res = {VTs, NumVTs}; 40 return Res; 41} 42 43//===----------------------------------------------------------------------===// 44// ConstantFPSDNode Class 45//===----------------------------------------------------------------------===// 46 47/// isExactlyValue - We don't rely on operator== working on double values, as 48/// it returns true for things that are clearly not equal, like -0.0 and 0.0. 49/// As such, this method can be used to do an exact bit-for-bit comparison of 50/// two floating point values. 51bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const { 52 return Value.bitwiseIsEqual(V); 53} 54 55bool ConstantFPSDNode::isValueValidForType(MVT::ValueType VT, 56 const APFloat& Val) { 57 // convert modifies in place, so make a copy. 58 APFloat Val2 = APFloat(Val); 59 switch (VT) { 60 default: 61 return false; // These can't be represented as floating point! 62 63 // FIXME rounding mode needs to be more flexible 64 case MVT::f32: 65 return &Val2.getSemantics() == &APFloat::IEEEsingle || 66 Val2.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven) == 67 APFloat::opOK; 68 case MVT::f64: 69 return &Val2.getSemantics() == &APFloat::IEEEsingle || 70 &Val2.getSemantics() == &APFloat::IEEEdouble || 71 Val2.convert(APFloat::IEEEdouble, APFloat::rmNearestTiesToEven) == 72 APFloat::opOK; 73 // TODO: Figure out how to test if we can use a shorter type instead! 74 case MVT::f80: 75 case MVT::f128: 76 case MVT::ppcf128: 77 return true; 78 } 79} 80 81//===----------------------------------------------------------------------===// 82// ISD Namespace 83//===----------------------------------------------------------------------===// 84 85/// isBuildVectorAllOnes - Return true if the specified node is a 86/// BUILD_VECTOR where all of the elements are ~0 or undef. 87bool ISD::isBuildVectorAllOnes(const SDNode *N) { 88 // Look through a bit convert. 89 if (N->getOpcode() == ISD::BIT_CONVERT) 90 N = N->getOperand(0).Val; 91 92 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 93 94 unsigned i = 0, e = N->getNumOperands(); 95 96 // Skip over all of the undef values. 97 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 98 ++i; 99 100 // Do not accept an all-undef vector. 101 if (i == e) return false; 102 103 // Do not accept build_vectors that aren't all constants or which have non-~0 104 // elements. 105 SDOperand NotZero = N->getOperand(i); 106 if (isa<ConstantSDNode>(NotZero)) { 107 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 108 return false; 109 } else if (isa<ConstantFPSDNode>(NotZero)) { 110 MVT::ValueType VT = NotZero.getValueType(); 111 if (VT== MVT::f64) { 112 if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 113 (uint64_t)-1) 114 return false; 115 } else { 116 if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 117 (uint32_t)-1) 118 return false; 119 } 120 } else 121 return false; 122 123 // Okay, we have at least one ~0 value, check to see if the rest match or are 124 // undefs. 125 for (++i; i != e; ++i) 126 if (N->getOperand(i) != NotZero && 127 N->getOperand(i).getOpcode() != ISD::UNDEF) 128 return false; 129 return true; 130} 131 132 133/// isBuildVectorAllZeros - Return true if the specified node is a 134/// BUILD_VECTOR where all of the elements are 0 or undef. 135bool ISD::isBuildVectorAllZeros(const SDNode *N) { 136 // Look through a bit convert. 137 if (N->getOpcode() == ISD::BIT_CONVERT) 138 N = N->getOperand(0).Val; 139 140 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 141 142 unsigned i = 0, e = N->getNumOperands(); 143 144 // Skip over all of the undef values. 145 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 146 ++i; 147 148 // Do not accept an all-undef vector. 149 if (i == e) return false; 150 151 // Do not accept build_vectors that aren't all constants or which have non-~0 152 // elements. 153 SDOperand Zero = N->getOperand(i); 154 if (isa<ConstantSDNode>(Zero)) { 155 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 156 return false; 157 } else if (isa<ConstantFPSDNode>(Zero)) { 158 if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0)) 159 return false; 160 } else 161 return false; 162 163 // Okay, we have at least one ~0 value, check to see if the rest match or are 164 // undefs. 165 for (++i; i != e; ++i) 166 if (N->getOperand(i) != Zero && 167 N->getOperand(i).getOpcode() != ISD::UNDEF) 168 return false; 169 return true; 170} 171 172/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 173/// when given the operation for (X op Y). 174ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 175 // To perform this operation, we just need to swap the L and G bits of the 176 // operation. 177 unsigned OldL = (Operation >> 2) & 1; 178 unsigned OldG = (Operation >> 1) & 1; 179 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 180 (OldL << 1) | // New G bit 181 (OldG << 2)); // New L bit. 182} 183 184/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 185/// 'op' is a valid SetCC operation. 186ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 187 unsigned Operation = Op; 188 if (isInteger) 189 Operation ^= 7; // Flip L, G, E bits, but not U. 190 else 191 Operation ^= 15; // Flip all of the condition bits. 192 if (Operation > ISD::SETTRUE2) 193 Operation &= ~8; // Don't let N and U bits get set. 194 return ISD::CondCode(Operation); 195} 196 197 198/// isSignedOp - For an integer comparison, return 1 if the comparison is a 199/// signed operation and 2 if the result is an unsigned comparison. Return zero 200/// if the operation does not depend on the sign of the input (setne and seteq). 201static int isSignedOp(ISD::CondCode Opcode) { 202 switch (Opcode) { 203 default: assert(0 && "Illegal integer setcc operation!"); 204 case ISD::SETEQ: 205 case ISD::SETNE: return 0; 206 case ISD::SETLT: 207 case ISD::SETLE: 208 case ISD::SETGT: 209 case ISD::SETGE: return 1; 210 case ISD::SETULT: 211 case ISD::SETULE: 212 case ISD::SETUGT: 213 case ISD::SETUGE: return 2; 214 } 215} 216 217/// getSetCCOrOperation - Return the result of a logical OR between different 218/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 219/// returns SETCC_INVALID if it is not possible to represent the resultant 220/// comparison. 221ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 222 bool isInteger) { 223 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 224 // Cannot fold a signed integer setcc with an unsigned integer setcc. 225 return ISD::SETCC_INVALID; 226 227 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 228 229 // If the N and U bits get set then the resultant comparison DOES suddenly 230 // care about orderedness, and is true when ordered. 231 if (Op > ISD::SETTRUE2) 232 Op &= ~16; // Clear the U bit if the N bit is set. 233 234 // Canonicalize illegal integer setcc's. 235 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 236 Op = ISD::SETNE; 237 238 return ISD::CondCode(Op); 239} 240 241/// getSetCCAndOperation - Return the result of a logical AND between different 242/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 243/// function returns zero if it is not possible to represent the resultant 244/// comparison. 245ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 246 bool isInteger) { 247 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 248 // Cannot fold a signed setcc with an unsigned setcc. 249 return ISD::SETCC_INVALID; 250 251 // Combine all of the condition bits. 252 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 253 254 // Canonicalize illegal integer setcc's. 255 if (isInteger) { 256 switch (Result) { 257 default: break; 258 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 259 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 260 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 261 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 262 } 263 } 264 265 return Result; 266} 267 268const TargetMachine &SelectionDAG::getTarget() const { 269 return TLI.getTargetMachine(); 270} 271 272//===----------------------------------------------------------------------===// 273// SDNode Profile Support 274//===----------------------------------------------------------------------===// 275 276/// AddNodeIDOpcode - Add the node opcode to the NodeID data. 277/// 278static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) { 279 ID.AddInteger(OpC); 280} 281 282/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them 283/// solely with their pointer. 284void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { 285 ID.AddPointer(VTList.VTs); 286} 287 288/// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 289/// 290static void AddNodeIDOperands(FoldingSetNodeID &ID, 291 const SDOperand *Ops, unsigned NumOps) { 292 for (; NumOps; --NumOps, ++Ops) { 293 ID.AddPointer(Ops->Val); 294 ID.AddInteger(Ops->ResNo); 295 } 296} 297 298static void AddNodeIDNode(FoldingSetNodeID &ID, 299 unsigned short OpC, SDVTList VTList, 300 const SDOperand *OpList, unsigned N) { 301 AddNodeIDOpcode(ID, OpC); 302 AddNodeIDValueTypes(ID, VTList); 303 AddNodeIDOperands(ID, OpList, N); 304} 305 306/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID 307/// data. 308static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) { 309 AddNodeIDOpcode(ID, N->getOpcode()); 310 // Add the return value info. 311 AddNodeIDValueTypes(ID, N->getVTList()); 312 // Add the operand info. 313 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands()); 314 315 // Handle SDNode leafs with special info. 316 switch (N->getOpcode()) { 317 default: break; // Normal nodes don't need extra info. 318 case ISD::TargetConstant: 319 case ISD::Constant: 320 ID.AddInteger(cast<ConstantSDNode>(N)->getValue()); 321 break; 322 case ISD::TargetConstantFP: 323 case ISD::ConstantFP: 324 ID.AddDouble(cast<ConstantFPSDNode>(N)->getValue()); 325 break; 326 case ISD::TargetGlobalAddress: 327 case ISD::GlobalAddress: 328 case ISD::TargetGlobalTLSAddress: 329 case ISD::GlobalTLSAddress: { 330 GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N); 331 ID.AddPointer(GA->getGlobal()); 332 ID.AddInteger(GA->getOffset()); 333 break; 334 } 335 case ISD::BasicBlock: 336 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock()); 337 break; 338 case ISD::Register: 339 ID.AddInteger(cast<RegisterSDNode>(N)->getReg()); 340 break; 341 case ISD::SRCVALUE: { 342 SrcValueSDNode *SV = cast<SrcValueSDNode>(N); 343 ID.AddPointer(SV->getValue()); 344 ID.AddInteger(SV->getOffset()); 345 break; 346 } 347 case ISD::FrameIndex: 348 case ISD::TargetFrameIndex: 349 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex()); 350 break; 351 case ISD::JumpTable: 352 case ISD::TargetJumpTable: 353 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex()); 354 break; 355 case ISD::ConstantPool: 356 case ISD::TargetConstantPool: { 357 ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N); 358 ID.AddInteger(CP->getAlignment()); 359 ID.AddInteger(CP->getOffset()); 360 if (CP->isMachineConstantPoolEntry()) 361 CP->getMachineCPVal()->AddSelectionDAGCSEId(ID); 362 else 363 ID.AddPointer(CP->getConstVal()); 364 break; 365 } 366 case ISD::LOAD: { 367 LoadSDNode *LD = cast<LoadSDNode>(N); 368 ID.AddInteger(LD->getAddressingMode()); 369 ID.AddInteger(LD->getExtensionType()); 370 ID.AddInteger(LD->getLoadedVT()); 371 ID.AddPointer(LD->getSrcValue()); 372 ID.AddInteger(LD->getSrcValueOffset()); 373 ID.AddInteger(LD->getAlignment()); 374 ID.AddInteger(LD->isVolatile()); 375 break; 376 } 377 case ISD::STORE: { 378 StoreSDNode *ST = cast<StoreSDNode>(N); 379 ID.AddInteger(ST->getAddressingMode()); 380 ID.AddInteger(ST->isTruncatingStore()); 381 ID.AddInteger(ST->getStoredVT()); 382 ID.AddPointer(ST->getSrcValue()); 383 ID.AddInteger(ST->getSrcValueOffset()); 384 ID.AddInteger(ST->getAlignment()); 385 ID.AddInteger(ST->isVolatile()); 386 break; 387 } 388 } 389} 390 391//===----------------------------------------------------------------------===// 392// SelectionDAG Class 393//===----------------------------------------------------------------------===// 394 395/// RemoveDeadNodes - This method deletes all unreachable nodes in the 396/// SelectionDAG. 397void SelectionDAG::RemoveDeadNodes() { 398 // Create a dummy node (which is not added to allnodes), that adds a reference 399 // to the root node, preventing it from being deleted. 400 HandleSDNode Dummy(getRoot()); 401 402 SmallVector<SDNode*, 128> DeadNodes; 403 404 // Add all obviously-dead nodes to the DeadNodes worklist. 405 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 406 if (I->use_empty()) 407 DeadNodes.push_back(I); 408 409 // Process the worklist, deleting the nodes and adding their uses to the 410 // worklist. 411 while (!DeadNodes.empty()) { 412 SDNode *N = DeadNodes.back(); 413 DeadNodes.pop_back(); 414 415 // Take the node out of the appropriate CSE map. 416 RemoveNodeFromCSEMaps(N); 417 418 // Next, brutally remove the operand list. This is safe to do, as there are 419 // no cycles in the graph. 420 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 421 SDNode *Operand = I->Val; 422 Operand->removeUser(N); 423 424 // Now that we removed this operand, see if there are no uses of it left. 425 if (Operand->use_empty()) 426 DeadNodes.push_back(Operand); 427 } 428 if (N->OperandsNeedDelete) 429 delete[] N->OperandList; 430 N->OperandList = 0; 431 N->NumOperands = 0; 432 433 // Finally, remove N itself. 434 AllNodes.erase(N); 435 } 436 437 // If the root changed (e.g. it was a dead load, update the root). 438 setRoot(Dummy.getValue()); 439} 440 441void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) { 442 SmallVector<SDNode*, 16> DeadNodes; 443 DeadNodes.push_back(N); 444 445 // Process the worklist, deleting the nodes and adding their uses to the 446 // worklist. 447 while (!DeadNodes.empty()) { 448 SDNode *N = DeadNodes.back(); 449 DeadNodes.pop_back(); 450 451 // Take the node out of the appropriate CSE map. 452 RemoveNodeFromCSEMaps(N); 453 454 // Next, brutally remove the operand list. This is safe to do, as there are 455 // no cycles in the graph. 456 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 457 SDNode *Operand = I->Val; 458 Operand->removeUser(N); 459 460 // Now that we removed this operand, see if there are no uses of it left. 461 if (Operand->use_empty()) 462 DeadNodes.push_back(Operand); 463 } 464 if (N->OperandsNeedDelete) 465 delete[] N->OperandList; 466 N->OperandList = 0; 467 N->NumOperands = 0; 468 469 // Finally, remove N itself. 470 Deleted.push_back(N); 471 AllNodes.erase(N); 472 } 473} 474 475void SelectionDAG::DeleteNode(SDNode *N) { 476 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 477 478 // First take this out of the appropriate CSE map. 479 RemoveNodeFromCSEMaps(N); 480 481 // Finally, remove uses due to operands of this node, remove from the 482 // AllNodes list, and delete the node. 483 DeleteNodeNotInCSEMaps(N); 484} 485 486void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 487 488 // Remove it from the AllNodes list. 489 AllNodes.remove(N); 490 491 // Drop all of the operands and decrement used nodes use counts. 492 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 493 I->Val->removeUser(N); 494 if (N->OperandsNeedDelete) 495 delete[] N->OperandList; 496 N->OperandList = 0; 497 N->NumOperands = 0; 498 499 delete N; 500} 501 502/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 503/// correspond to it. This is useful when we're about to delete or repurpose 504/// the node. We don't want future request for structurally identical nodes 505/// to return N anymore. 506void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 507 bool Erased = false; 508 switch (N->getOpcode()) { 509 case ISD::HANDLENODE: return; // noop. 510 case ISD::STRING: 511 Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue()); 512 break; 513 case ISD::CONDCODE: 514 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 515 "Cond code doesn't exist!"); 516 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 517 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 518 break; 519 case ISD::ExternalSymbol: 520 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 521 break; 522 case ISD::TargetExternalSymbol: 523 Erased = 524 TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 525 break; 526 case ISD::VALUETYPE: 527 Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0; 528 ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0; 529 break; 530 default: 531 // Remove it from the CSE Map. 532 Erased = CSEMap.RemoveNode(N); 533 break; 534 } 535#ifndef NDEBUG 536 // Verify that the node was actually in one of the CSE maps, unless it has a 537 // flag result (which cannot be CSE'd) or is one of the special cases that are 538 // not subject to CSE. 539 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 540 !N->isTargetOpcode()) { 541 N->dump(this); 542 cerr << "\n"; 543 assert(0 && "Node is not in map!"); 544 } 545#endif 546} 547 548/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It 549/// has been taken out and modified in some way. If the specified node already 550/// exists in the CSE maps, do not modify the maps, but return the existing node 551/// instead. If it doesn't exist, add it and return null. 552/// 553SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { 554 assert(N->getNumOperands() && "This is a leaf node!"); 555 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 556 return 0; // Never add these nodes. 557 558 // Check that remaining values produced are not flags. 559 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 560 if (N->getValueType(i) == MVT::Flag) 561 return 0; // Never CSE anything that produces a flag. 562 563 SDNode *New = CSEMap.GetOrInsertNode(N); 564 if (New != N) return New; // Node already existed. 565 return 0; 566} 567 568/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 569/// were replaced with those specified. If this node is never memoized, 570/// return null, otherwise return a pointer to the slot it would take. If a 571/// node already exists with these operands, the slot will be non-null. 572SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op, 573 void *&InsertPos) { 574 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 575 return 0; // Never add these nodes. 576 577 // Check that remaining values produced are not flags. 578 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 579 if (N->getValueType(i) == MVT::Flag) 580 return 0; // Never CSE anything that produces a flag. 581 582 SDOperand Ops[] = { Op }; 583 FoldingSetNodeID ID; 584 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1); 585 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 586} 587 588/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 589/// were replaced with those specified. If this node is never memoized, 590/// return null, otherwise return a pointer to the slot it would take. If a 591/// node already exists with these operands, the slot will be non-null. 592SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 593 SDOperand Op1, SDOperand Op2, 594 void *&InsertPos) { 595 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 596 return 0; // Never add these nodes. 597 598 // Check that remaining values produced are not flags. 599 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 600 if (N->getValueType(i) == MVT::Flag) 601 return 0; // Never CSE anything that produces a flag. 602 603 SDOperand Ops[] = { Op1, Op2 }; 604 FoldingSetNodeID ID; 605 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2); 606 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 607} 608 609 610/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 611/// were replaced with those specified. If this node is never memoized, 612/// return null, otherwise return a pointer to the slot it would take. If a 613/// node already exists with these operands, the slot will be non-null. 614SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 615 const SDOperand *Ops,unsigned NumOps, 616 void *&InsertPos) { 617 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 618 return 0; // Never add these nodes. 619 620 // Check that remaining values produced are not flags. 621 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 622 if (N->getValueType(i) == MVT::Flag) 623 return 0; // Never CSE anything that produces a flag. 624 625 FoldingSetNodeID ID; 626 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps); 627 628 if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 629 ID.AddInteger(LD->getAddressingMode()); 630 ID.AddInteger(LD->getExtensionType()); 631 ID.AddInteger(LD->getLoadedVT()); 632 ID.AddPointer(LD->getSrcValue()); 633 ID.AddInteger(LD->getSrcValueOffset()); 634 ID.AddInteger(LD->getAlignment()); 635 ID.AddInteger(LD->isVolatile()); 636 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 637 ID.AddInteger(ST->getAddressingMode()); 638 ID.AddInteger(ST->isTruncatingStore()); 639 ID.AddInteger(ST->getStoredVT()); 640 ID.AddPointer(ST->getSrcValue()); 641 ID.AddInteger(ST->getSrcValueOffset()); 642 ID.AddInteger(ST->getAlignment()); 643 ID.AddInteger(ST->isVolatile()); 644 } 645 646 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 647} 648 649 650SelectionDAG::~SelectionDAG() { 651 while (!AllNodes.empty()) { 652 SDNode *N = AllNodes.begin(); 653 N->SetNextInBucket(0); 654 if (N->OperandsNeedDelete) 655 delete [] N->OperandList; 656 N->OperandList = 0; 657 N->NumOperands = 0; 658 AllNodes.pop_front(); 659 } 660} 661 662SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { 663 if (Op.getValueType() == VT) return Op; 664 int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT)); 665 return getNode(ISD::AND, Op.getValueType(), Op, 666 getConstant(Imm, Op.getValueType())); 667} 668 669SDOperand SelectionDAG::getString(const std::string &Val) { 670 StringSDNode *&N = StringNodes[Val]; 671 if (!N) { 672 N = new StringSDNode(Val); 673 AllNodes.push_back(N); 674 } 675 return SDOperand(N, 0); 676} 677 678SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) { 679 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 680 assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); 681 682 // Mask out any bits that are not valid for this constant. 683 Val &= MVT::getIntVTBitMask(VT); 684 685 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; 686 FoldingSetNodeID ID; 687 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 688 ID.AddInteger(Val); 689 void *IP = 0; 690 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 691 return SDOperand(E, 0); 692 SDNode *N = new ConstantSDNode(isT, Val, VT); 693 CSEMap.InsertNode(N, IP); 694 AllNodes.push_back(N); 695 return SDOperand(N, 0); 696} 697 698SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT::ValueType VT, 699 bool isTarget) { 700 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 701 702 MVT::ValueType EltVT = 703 MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT; 704 bool isDouble = (EltVT == MVT::f64); 705 double Val = isDouble ? V.convertToDouble() : (double)V.convertToFloat(); 706 707 // Do the map lookup using the actual bit pattern for the floating point 708 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 709 // we don't have issues with SNANs. 710 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; 711 // ?? Should we store float/double/longdouble separately in ID? 712 FoldingSetNodeID ID; 713 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); 714 ID.AddDouble(Val); 715 void *IP = 0; 716 SDNode *N = NULL; 717 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 718 if (!MVT::isVector(VT)) 719 return SDOperand(N, 0); 720 if (!N) { 721 N = new ConstantFPSDNode(isTarget, Val, EltVT); 722 CSEMap.InsertNode(N, IP); 723 AllNodes.push_back(N); 724 } 725 726 SDOperand Result(N, 0); 727 if (MVT::isVector(VT)) { 728 SmallVector<SDOperand, 8> Ops; 729 Ops.assign(MVT::getVectorNumElements(VT), Result); 730 Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size()); 731 } 732 return Result; 733} 734 735SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT, 736 bool isTarget) { 737 MVT::ValueType EltVT = 738 MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT; 739 if (EltVT==MVT::f32) 740 return getConstantFP(APFloat((float)Val), VT, isTarget); 741 else 742 return getConstantFP(APFloat(Val), VT, isTarget); 743} 744 745SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 746 MVT::ValueType VT, int Offset, 747 bool isTargetGA) { 748 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV); 749 unsigned Opc; 750 if (GVar && GVar->isThreadLocal()) 751 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress; 752 else 753 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; 754 FoldingSetNodeID ID; 755 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 756 ID.AddPointer(GV); 757 ID.AddInteger(Offset); 758 void *IP = 0; 759 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 760 return SDOperand(E, 0); 761 SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset); 762 CSEMap.InsertNode(N, IP); 763 AllNodes.push_back(N); 764 return SDOperand(N, 0); 765} 766 767SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT, 768 bool isTarget) { 769 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; 770 FoldingSetNodeID ID; 771 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 772 ID.AddInteger(FI); 773 void *IP = 0; 774 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 775 return SDOperand(E, 0); 776 SDNode *N = new FrameIndexSDNode(FI, VT, isTarget); 777 CSEMap.InsertNode(N, IP); 778 AllNodes.push_back(N); 779 return SDOperand(N, 0); 780} 781 782SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){ 783 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; 784 FoldingSetNodeID ID; 785 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 786 ID.AddInteger(JTI); 787 void *IP = 0; 788 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 789 return SDOperand(E, 0); 790 SDNode *N = new JumpTableSDNode(JTI, VT, isTarget); 791 CSEMap.InsertNode(N, IP); 792 AllNodes.push_back(N); 793 return SDOperand(N, 0); 794} 795 796SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, 797 unsigned Alignment, int Offset, 798 bool isTarget) { 799 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 800 FoldingSetNodeID ID; 801 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 802 ID.AddInteger(Alignment); 803 ID.AddInteger(Offset); 804 ID.AddPointer(C); 805 void *IP = 0; 806 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 807 return SDOperand(E, 0); 808 SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); 809 CSEMap.InsertNode(N, IP); 810 AllNodes.push_back(N); 811 return SDOperand(N, 0); 812} 813 814 815SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, 816 MVT::ValueType VT, 817 unsigned Alignment, int Offset, 818 bool isTarget) { 819 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 820 FoldingSetNodeID ID; 821 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 822 ID.AddInteger(Alignment); 823 ID.AddInteger(Offset); 824 C->AddSelectionDAGCSEId(ID); 825 void *IP = 0; 826 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 827 return SDOperand(E, 0); 828 SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); 829 CSEMap.InsertNode(N, IP); 830 AllNodes.push_back(N); 831 return SDOperand(N, 0); 832} 833 834 835SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 836 FoldingSetNodeID ID; 837 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0); 838 ID.AddPointer(MBB); 839 void *IP = 0; 840 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 841 return SDOperand(E, 0); 842 SDNode *N = new BasicBlockSDNode(MBB); 843 CSEMap.InsertNode(N, IP); 844 AllNodes.push_back(N); 845 return SDOperand(N, 0); 846} 847 848SDOperand SelectionDAG::getValueType(MVT::ValueType VT) { 849 if ((unsigned)VT >= ValueTypeNodes.size()) 850 ValueTypeNodes.resize(VT+1); 851 if (ValueTypeNodes[VT] == 0) { 852 ValueTypeNodes[VT] = new VTSDNode(VT); 853 AllNodes.push_back(ValueTypeNodes[VT]); 854 } 855 856 return SDOperand(ValueTypeNodes[VT], 0); 857} 858 859SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 860 SDNode *&N = ExternalSymbols[Sym]; 861 if (N) return SDOperand(N, 0); 862 N = new ExternalSymbolSDNode(false, Sym, VT); 863 AllNodes.push_back(N); 864 return SDOperand(N, 0); 865} 866 867SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, 868 MVT::ValueType VT) { 869 SDNode *&N = TargetExternalSymbols[Sym]; 870 if (N) return SDOperand(N, 0); 871 N = new ExternalSymbolSDNode(true, Sym, VT); 872 AllNodes.push_back(N); 873 return SDOperand(N, 0); 874} 875 876SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { 877 if ((unsigned)Cond >= CondCodeNodes.size()) 878 CondCodeNodes.resize(Cond+1); 879 880 if (CondCodeNodes[Cond] == 0) { 881 CondCodeNodes[Cond] = new CondCodeSDNode(Cond); 882 AllNodes.push_back(CondCodeNodes[Cond]); 883 } 884 return SDOperand(CondCodeNodes[Cond], 0); 885} 886 887SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { 888 FoldingSetNodeID ID; 889 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0); 890 ID.AddInteger(RegNo); 891 void *IP = 0; 892 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 893 return SDOperand(E, 0); 894 SDNode *N = new RegisterSDNode(RegNo, VT); 895 CSEMap.InsertNode(N, IP); 896 AllNodes.push_back(N); 897 return SDOperand(N, 0); 898} 899 900SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 901 assert((!V || isa<PointerType>(V->getType())) && 902 "SrcValue is not a pointer?"); 903 904 FoldingSetNodeID ID; 905 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0); 906 ID.AddPointer(V); 907 ID.AddInteger(Offset); 908 void *IP = 0; 909 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 910 return SDOperand(E, 0); 911 SDNode *N = new SrcValueSDNode(V, Offset); 912 CSEMap.InsertNode(N, IP); 913 AllNodes.push_back(N); 914 return SDOperand(N, 0); 915} 916 917SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1, 918 SDOperand N2, ISD::CondCode Cond) { 919 // These setcc operations always fold. 920 switch (Cond) { 921 default: break; 922 case ISD::SETFALSE: 923 case ISD::SETFALSE2: return getConstant(0, VT); 924 case ISD::SETTRUE: 925 case ISD::SETTRUE2: return getConstant(1, VT); 926 927 case ISD::SETOEQ: 928 case ISD::SETOGT: 929 case ISD::SETOGE: 930 case ISD::SETOLT: 931 case ISD::SETOLE: 932 case ISD::SETONE: 933 case ISD::SETO: 934 case ISD::SETUO: 935 case ISD::SETUEQ: 936 case ISD::SETUNE: 937 assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!"); 938 break; 939 } 940 941 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 942 uint64_t C2 = N2C->getValue(); 943 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 944 uint64_t C1 = N1C->getValue(); 945 946 // Sign extend the operands if required 947 if (ISD::isSignedIntSetCC(Cond)) { 948 C1 = N1C->getSignExtended(); 949 C2 = N2C->getSignExtended(); 950 } 951 952 switch (Cond) { 953 default: assert(0 && "Unknown integer setcc!"); 954 case ISD::SETEQ: return getConstant(C1 == C2, VT); 955 case ISD::SETNE: return getConstant(C1 != C2, VT); 956 case ISD::SETULT: return getConstant(C1 < C2, VT); 957 case ISD::SETUGT: return getConstant(C1 > C2, VT); 958 case ISD::SETULE: return getConstant(C1 <= C2, VT); 959 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 960 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 961 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 962 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 963 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 964 } 965 } 966 } 967 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 968 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 969 double C1 = N1C->getValue(), C2 = N2C->getValue(); 970 971 switch (Cond) { 972 default: break; // FIXME: Implement the rest of these! 973 case ISD::SETEQ: return getConstant(C1 == C2, VT); 974 case ISD::SETNE: return getConstant(C1 != C2, VT); 975 case ISD::SETLT: return getConstant(C1 < C2, VT); 976 case ISD::SETGT: return getConstant(C1 > C2, VT); 977 case ISD::SETLE: return getConstant(C1 <= C2, VT); 978 case ISD::SETGE: return getConstant(C1 >= C2, VT); 979 } 980 } else { 981 // Ensure that the constant occurs on the RHS. 982 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 983 } 984 985 // Could not fold it. 986 return SDOperand(); 987} 988 989/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 990/// this predicate to simplify operations downstream. Mask is known to be zero 991/// for bits that V cannot have. 992bool SelectionDAG::MaskedValueIsZero(SDOperand Op, uint64_t Mask, 993 unsigned Depth) const { 994 // The masks are not wide enough to represent this type! Should use APInt. 995 if (Op.getValueType() == MVT::i128) 996 return false; 997 998 uint64_t KnownZero, KnownOne; 999 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 1000 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1001 return (KnownZero & Mask) == Mask; 1002} 1003 1004/// ComputeMaskedBits - Determine which of the bits specified in Mask are 1005/// known to be either zero or one and return them in the KnownZero/KnownOne 1006/// bitsets. This code only analyzes bits in Mask, in order to short-circuit 1007/// processing. 1008void SelectionDAG::ComputeMaskedBits(SDOperand Op, uint64_t Mask, 1009 uint64_t &KnownZero, uint64_t &KnownOne, 1010 unsigned Depth) const { 1011 KnownZero = KnownOne = 0; // Don't know anything. 1012 if (Depth == 6 || Mask == 0) 1013 return; // Limit search depth. 1014 1015 // The masks are not wide enough to represent this type! Should use APInt. 1016 if (Op.getValueType() == MVT::i128) 1017 return; 1018 1019 uint64_t KnownZero2, KnownOne2; 1020 1021 switch (Op.getOpcode()) { 1022 case ISD::Constant: 1023 // We know all of the bits for a constant! 1024 KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; 1025 KnownZero = ~KnownOne & Mask; 1026 return; 1027 case ISD::AND: 1028 // If either the LHS or the RHS are Zero, the result is zero. 1029 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1030 Mask &= ~KnownZero; 1031 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 1032 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1033 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1034 1035 // Output known-1 bits are only known if set in both the LHS & RHS. 1036 KnownOne &= KnownOne2; 1037 // Output known-0 are known to be clear if zero in either the LHS | RHS. 1038 KnownZero |= KnownZero2; 1039 return; 1040 case ISD::OR: 1041 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1042 Mask &= ~KnownOne; 1043 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 1044 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1045 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1046 1047 // Output known-0 bits are only known if clear in both the LHS & RHS. 1048 KnownZero &= KnownZero2; 1049 // Output known-1 are known to be set if set in either the LHS | RHS. 1050 KnownOne |= KnownOne2; 1051 return; 1052 case ISD::XOR: { 1053 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1054 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 1055 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1056 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1057 1058 // Output known-0 bits are known if clear or set in both the LHS & RHS. 1059 uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 1060 // Output known-1 are known to be set if set in only one of the LHS, RHS. 1061 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 1062 KnownZero = KnownZeroOut; 1063 return; 1064 } 1065 case ISD::SELECT: 1066 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 1067 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 1068 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1069 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1070 1071 // Only known if known in both the LHS and RHS. 1072 KnownOne &= KnownOne2; 1073 KnownZero &= KnownZero2; 1074 return; 1075 case ISD::SELECT_CC: 1076 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 1077 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 1078 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1079 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1080 1081 // Only known if known in both the LHS and RHS. 1082 KnownOne &= KnownOne2; 1083 KnownZero &= KnownZero2; 1084 return; 1085 case ISD::SETCC: 1086 // If we know the result of a setcc has the top bits zero, use this info. 1087 if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 1088 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 1089 return; 1090 case ISD::SHL: 1091 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 1092 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1093 ComputeMaskedBits(Op.getOperand(0), Mask >> SA->getValue(), 1094 KnownZero, KnownOne, Depth+1); 1095 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1096 KnownZero <<= SA->getValue(); 1097 KnownOne <<= SA->getValue(); 1098 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 1099 } 1100 return; 1101 case ISD::SRL: 1102 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 1103 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1104 MVT::ValueType VT = Op.getValueType(); 1105 unsigned ShAmt = SA->getValue(); 1106 1107 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 1108 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt) & TypeMask, 1109 KnownZero, KnownOne, Depth+1); 1110 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1111 KnownZero &= TypeMask; 1112 KnownOne &= TypeMask; 1113 KnownZero >>= ShAmt; 1114 KnownOne >>= ShAmt; 1115 1116 uint64_t HighBits = (1ULL << ShAmt)-1; 1117 HighBits <<= MVT::getSizeInBits(VT)-ShAmt; 1118 KnownZero |= HighBits; // High bits known zero. 1119 } 1120 return; 1121 case ISD::SRA: 1122 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1123 MVT::ValueType VT = Op.getValueType(); 1124 unsigned ShAmt = SA->getValue(); 1125 1126 // Compute the new bits that are at the top now. 1127 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 1128 1129 uint64_t InDemandedMask = (Mask << ShAmt) & TypeMask; 1130 // If any of the demanded bits are produced by the sign extension, we also 1131 // demand the input sign bit. 1132 uint64_t HighBits = (1ULL << ShAmt)-1; 1133 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 1134 if (HighBits & Mask) 1135 InDemandedMask |= MVT::getIntVTSignBit(VT); 1136 1137 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, 1138 Depth+1); 1139 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1140 KnownZero &= TypeMask; 1141 KnownOne &= TypeMask; 1142 KnownZero >>= ShAmt; 1143 KnownOne >>= ShAmt; 1144 1145 // Handle the sign bits. 1146 uint64_t SignBit = MVT::getIntVTSignBit(VT); 1147 SignBit >>= ShAmt; // Adjust to where it is now in the mask. 1148 1149 if (KnownZero & SignBit) { 1150 KnownZero |= HighBits; // New bits are known zero. 1151 } else if (KnownOne & SignBit) { 1152 KnownOne |= HighBits; // New bits are known one. 1153 } 1154 } 1155 return; 1156 case ISD::SIGN_EXTEND_INREG: { 1157 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1158 1159 // Sign extension. Compute the demanded bits in the result that are not 1160 // present in the input. 1161 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; 1162 1163 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 1164 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); 1165 1166 // If the sign extended bits are demanded, we know that the sign 1167 // bit is demanded. 1168 if (NewBits) 1169 InputDemandedBits |= InSignBit; 1170 1171 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 1172 KnownZero, KnownOne, Depth+1); 1173 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1174 1175 // If the sign bit of the input is known set or clear, then we know the 1176 // top bits of the result. 1177 if (KnownZero & InSignBit) { // Input sign bit known clear 1178 KnownZero |= NewBits; 1179 KnownOne &= ~NewBits; 1180 } else if (KnownOne & InSignBit) { // Input sign bit known set 1181 KnownOne |= NewBits; 1182 KnownZero &= ~NewBits; 1183 } else { // Input sign bit unknown 1184 KnownZero &= ~NewBits; 1185 KnownOne &= ~NewBits; 1186 } 1187 return; 1188 } 1189 case ISD::CTTZ: 1190 case ISD::CTLZ: 1191 case ISD::CTPOP: { 1192 MVT::ValueType VT = Op.getValueType(); 1193 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 1194 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 1195 KnownOne = 0; 1196 return; 1197 } 1198 case ISD::LOAD: { 1199 if (ISD::isZEXTLoad(Op.Val)) { 1200 LoadSDNode *LD = cast<LoadSDNode>(Op); 1201 MVT::ValueType VT = LD->getLoadedVT(); 1202 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; 1203 } 1204 return; 1205 } 1206 case ISD::ZERO_EXTEND: { 1207 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 1208 uint64_t NewBits = (~InMask) & Mask; 1209 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 1210 KnownOne, Depth+1); 1211 KnownZero |= NewBits & Mask; 1212 KnownOne &= ~NewBits; 1213 return; 1214 } 1215 case ISD::SIGN_EXTEND: { 1216 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 1217 unsigned InBits = MVT::getSizeInBits(InVT); 1218 uint64_t InMask = MVT::getIntVTBitMask(InVT); 1219 uint64_t InSignBit = 1ULL << (InBits-1); 1220 uint64_t NewBits = (~InMask) & Mask; 1221 uint64_t InDemandedBits = Mask & InMask; 1222 1223 // If any of the sign extended bits are demanded, we know that the sign 1224 // bit is demanded. 1225 if (NewBits & Mask) 1226 InDemandedBits |= InSignBit; 1227 1228 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, 1229 KnownOne, Depth+1); 1230 // If the sign bit is known zero or one, the top bits match. 1231 if (KnownZero & InSignBit) { 1232 KnownZero |= NewBits; 1233 KnownOne &= ~NewBits; 1234 } else if (KnownOne & InSignBit) { 1235 KnownOne |= NewBits; 1236 KnownZero &= ~NewBits; 1237 } else { // Otherwise, top bits aren't known. 1238 KnownOne &= ~NewBits; 1239 KnownZero &= ~NewBits; 1240 } 1241 return; 1242 } 1243 case ISD::ANY_EXTEND: { 1244 MVT::ValueType VT = Op.getOperand(0).getValueType(); 1245 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), 1246 KnownZero, KnownOne, Depth+1); 1247 return; 1248 } 1249 case ISD::TRUNCATE: { 1250 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 1251 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1252 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); 1253 KnownZero &= OutMask; 1254 KnownOne &= OutMask; 1255 break; 1256 } 1257 case ISD::AssertZext: { 1258 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1259 uint64_t InMask = MVT::getIntVTBitMask(VT); 1260 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 1261 KnownOne, Depth+1); 1262 KnownZero |= (~InMask) & Mask; 1263 return; 1264 } 1265 case ISD::ADD: { 1266 // If either the LHS or the RHS are Zero, the result is zero. 1267 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1268 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 1269 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1270 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1271 1272 // Output known-0 bits are known if clear or set in both the low clear bits 1273 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 1274 // low 3 bits clear. 1275 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), 1276 CountTrailingZeros_64(~KnownZero2)); 1277 1278 KnownZero = (1ULL << KnownZeroOut) - 1; 1279 KnownOne = 0; 1280 return; 1281 } 1282 case ISD::SUB: { 1283 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); 1284 if (!CLHS) return; 1285 1286 // We know that the top bits of C-X are clear if X contains less bits 1287 // than C (i.e. no wrap-around can happen). For example, 20-X is 1288 // positive if we can prove that X is >= 0 and < 16. 1289 MVT::ValueType VT = CLHS->getValueType(0); 1290 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear 1291 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 1292 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit 1293 MaskV = ~MaskV & MVT::getIntVTBitMask(VT); 1294 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); 1295 1296 // If all of the MaskV bits are known to be zero, then we know the output 1297 // top bits are zero, because we now know that the output is from [0-C]. 1298 if ((KnownZero & MaskV) == MaskV) { 1299 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 1300 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. 1301 KnownOne = 0; // No one bits known. 1302 } else { 1303 KnownZero = KnownOne = 0; // Otherwise, nothing known. 1304 } 1305 } 1306 return; 1307 } 1308 default: 1309 // Allow the target to implement this method for its nodes. 1310 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { 1311 case ISD::INTRINSIC_WO_CHAIN: 1312 case ISD::INTRINSIC_W_CHAIN: 1313 case ISD::INTRINSIC_VOID: 1314 TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this); 1315 } 1316 return; 1317 } 1318} 1319 1320/// ComputeNumSignBits - Return the number of times the sign bit of the 1321/// register is replicated into the other bits. We know that at least 1 bit 1322/// is always equal to the sign bit (itself), but other cases can give us 1323/// information. For example, immediately after an "SRA X, 2", we know that 1324/// the top 3 bits are all equal to each other, so we return 3. 1325unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ 1326 MVT::ValueType VT = Op.getValueType(); 1327 assert(MVT::isInteger(VT) && "Invalid VT!"); 1328 unsigned VTBits = MVT::getSizeInBits(VT); 1329 unsigned Tmp, Tmp2; 1330 1331 if (Depth == 6) 1332 return 1; // Limit search depth. 1333 1334 switch (Op.getOpcode()) { 1335 default: break; 1336 case ISD::AssertSext: 1337 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1338 return VTBits-Tmp+1; 1339 case ISD::AssertZext: 1340 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1341 return VTBits-Tmp; 1342 1343 case ISD::Constant: { 1344 uint64_t Val = cast<ConstantSDNode>(Op)->getValue(); 1345 // If negative, invert the bits, then look at it. 1346 if (Val & MVT::getIntVTSignBit(VT)) 1347 Val = ~Val; 1348 1349 // Shift the bits so they are the leading bits in the int64_t. 1350 Val <<= 64-VTBits; 1351 1352 // Return # leading zeros. We use 'min' here in case Val was zero before 1353 // shifting. We don't want to return '64' as for an i32 "0". 1354 return std::min(VTBits, CountLeadingZeros_64(Val)); 1355 } 1356 1357 case ISD::SIGN_EXTEND: 1358 Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType()); 1359 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 1360 1361 case ISD::SIGN_EXTEND_INREG: 1362 // Max of the input and what this extends. 1363 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1364 Tmp = VTBits-Tmp+1; 1365 1366 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1367 return std::max(Tmp, Tmp2); 1368 1369 case ISD::SRA: 1370 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1371 // SRA X, C -> adds C sign bits. 1372 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1373 Tmp += C->getValue(); 1374 if (Tmp > VTBits) Tmp = VTBits; 1375 } 1376 return Tmp; 1377 case ISD::SHL: 1378 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1379 // shl destroys sign bits. 1380 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1381 if (C->getValue() >= VTBits || // Bad shift. 1382 C->getValue() >= Tmp) break; // Shifted all sign bits out. 1383 return Tmp - C->getValue(); 1384 } 1385 break; 1386 case ISD::AND: 1387 case ISD::OR: 1388 case ISD::XOR: // NOT is handled here. 1389 // Logical binary ops preserve the number of sign bits. 1390 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1391 if (Tmp == 1) return 1; // Early out. 1392 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1393 return std::min(Tmp, Tmp2); 1394 1395 case ISD::SELECT: 1396 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1397 if (Tmp == 1) return 1; // Early out. 1398 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1399 return std::min(Tmp, Tmp2); 1400 1401 case ISD::SETCC: 1402 // If setcc returns 0/-1, all bits are sign bits. 1403 if (TLI.getSetCCResultContents() == 1404 TargetLowering::ZeroOrNegativeOneSetCCResult) 1405 return VTBits; 1406 break; 1407 case ISD::ROTL: 1408 case ISD::ROTR: 1409 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1410 unsigned RotAmt = C->getValue() & (VTBits-1); 1411 1412 // Handle rotate right by N like a rotate left by 32-N. 1413 if (Op.getOpcode() == ISD::ROTR) 1414 RotAmt = (VTBits-RotAmt) & (VTBits-1); 1415 1416 // If we aren't rotating out all of the known-in sign bits, return the 1417 // number that are left. This handles rotl(sext(x), 1) for example. 1418 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1419 if (Tmp > RotAmt+1) return Tmp-RotAmt; 1420 } 1421 break; 1422 case ISD::ADD: 1423 // Add can have at most one carry bit. Thus we know that the output 1424 // is, at worst, one more bit than the inputs. 1425 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1426 if (Tmp == 1) return 1; // Early out. 1427 1428 // Special case decrementing a value (ADD X, -1): 1429 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1430 if (CRHS->isAllOnesValue()) { 1431 uint64_t KnownZero, KnownOne; 1432 uint64_t Mask = MVT::getIntVTBitMask(VT); 1433 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 1434 1435 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1436 // sign bits set. 1437 if ((KnownZero|1) == Mask) 1438 return VTBits; 1439 1440 // If we are subtracting one from a positive number, there is no carry 1441 // out of the result. 1442 if (KnownZero & MVT::getIntVTSignBit(VT)) 1443 return Tmp; 1444 } 1445 1446 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1447 if (Tmp2 == 1) return 1; 1448 return std::min(Tmp, Tmp2)-1; 1449 break; 1450 1451 case ISD::SUB: 1452 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1453 if (Tmp2 == 1) return 1; 1454 1455 // Handle NEG. 1456 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1457 if (CLHS->getValue() == 0) { 1458 uint64_t KnownZero, KnownOne; 1459 uint64_t Mask = MVT::getIntVTBitMask(VT); 1460 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1461 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1462 // sign bits set. 1463 if ((KnownZero|1) == Mask) 1464 return VTBits; 1465 1466 // If the input is known to be positive (the sign bit is known clear), 1467 // the output of the NEG has the same number of sign bits as the input. 1468 if (KnownZero & MVT::getIntVTSignBit(VT)) 1469 return Tmp2; 1470 1471 // Otherwise, we treat this like a SUB. 1472 } 1473 1474 // Sub can have at most one carry bit. Thus we know that the output 1475 // is, at worst, one more bit than the inputs. 1476 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1477 if (Tmp == 1) return 1; // Early out. 1478 return std::min(Tmp, Tmp2)-1; 1479 break; 1480 case ISD::TRUNCATE: 1481 // FIXME: it's tricky to do anything useful for this, but it is an important 1482 // case for targets like X86. 1483 break; 1484 } 1485 1486 // Handle LOADX separately here. EXTLOAD case will fallthrough. 1487 if (Op.getOpcode() == ISD::LOAD) { 1488 LoadSDNode *LD = cast<LoadSDNode>(Op); 1489 unsigned ExtType = LD->getExtensionType(); 1490 switch (ExtType) { 1491 default: break; 1492 case ISD::SEXTLOAD: // '17' bits known 1493 Tmp = MVT::getSizeInBits(LD->getLoadedVT()); 1494 return VTBits-Tmp+1; 1495 case ISD::ZEXTLOAD: // '16' bits known 1496 Tmp = MVT::getSizeInBits(LD->getLoadedVT()); 1497 return VTBits-Tmp; 1498 } 1499 } 1500 1501 // Allow the target to implement this method for its nodes. 1502 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 1503 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1504 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1505 Op.getOpcode() == ISD::INTRINSIC_VOID) { 1506 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth); 1507 if (NumBits > 1) return NumBits; 1508 } 1509 1510 // Finally, if we can prove that the top bits of the result are 0's or 1's, 1511 // use this information. 1512 uint64_t KnownZero, KnownOne; 1513 uint64_t Mask = MVT::getIntVTBitMask(VT); 1514 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 1515 1516 uint64_t SignBit = MVT::getIntVTSignBit(VT); 1517 if (KnownZero & SignBit) { // SignBit is 0 1518 Mask = KnownZero; 1519 } else if (KnownOne & SignBit) { // SignBit is 1; 1520 Mask = KnownOne; 1521 } else { 1522 // Nothing known. 1523 return 1; 1524 } 1525 1526 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1527 // the number of identical bits in the top of the input value. 1528 Mask ^= ~0ULL; 1529 Mask <<= 64-VTBits; 1530 // Return # leading zeros. We use 'min' here in case Val was zero before 1531 // shifting. We don't want to return '64' as for an i32 "0". 1532 return std::min(VTBits, CountLeadingZeros_64(Mask)); 1533} 1534 1535 1536/// getNode - Gets or creates the specified node. 1537/// 1538SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 1539 FoldingSetNodeID ID; 1540 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0); 1541 void *IP = 0; 1542 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1543 return SDOperand(E, 0); 1544 SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT)); 1545 CSEMap.InsertNode(N, IP); 1546 1547 AllNodes.push_back(N); 1548 return SDOperand(N, 0); 1549} 1550 1551SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1552 SDOperand Operand) { 1553 unsigned Tmp1; 1554 // Constant fold unary operations with an integer constant operand. 1555 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 1556 uint64_t Val = C->getValue(); 1557 switch (Opcode) { 1558 default: break; 1559 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 1560 case ISD::ANY_EXTEND: 1561 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 1562 case ISD::TRUNCATE: return getConstant(Val, VT); 1563 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 1564 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 1565 case ISD::BIT_CONVERT: 1566 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 1567 return getConstantFP(BitsToFloat(Val), VT); 1568 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 1569 return getConstantFP(BitsToDouble(Val), VT); 1570 break; 1571 case ISD::BSWAP: 1572 switch(VT) { 1573 default: assert(0 && "Invalid bswap!"); break; 1574 case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT); 1575 case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT); 1576 case MVT::i64: return getConstant(ByteSwap_64(Val), VT); 1577 } 1578 break; 1579 case ISD::CTPOP: 1580 switch(VT) { 1581 default: assert(0 && "Invalid ctpop!"); break; 1582 case MVT::i1: return getConstant(Val != 0, VT); 1583 case MVT::i8: 1584 Tmp1 = (unsigned)Val & 0xFF; 1585 return getConstant(CountPopulation_32(Tmp1), VT); 1586 case MVT::i16: 1587 Tmp1 = (unsigned)Val & 0xFFFF; 1588 return getConstant(CountPopulation_32(Tmp1), VT); 1589 case MVT::i32: 1590 return getConstant(CountPopulation_32((unsigned)Val), VT); 1591 case MVT::i64: 1592 return getConstant(CountPopulation_64(Val), VT); 1593 } 1594 case ISD::CTLZ: 1595 switch(VT) { 1596 default: assert(0 && "Invalid ctlz!"); break; 1597 case MVT::i1: return getConstant(Val == 0, VT); 1598 case MVT::i8: 1599 Tmp1 = (unsigned)Val & 0xFF; 1600 return getConstant(CountLeadingZeros_32(Tmp1)-24, VT); 1601 case MVT::i16: 1602 Tmp1 = (unsigned)Val & 0xFFFF; 1603 return getConstant(CountLeadingZeros_32(Tmp1)-16, VT); 1604 case MVT::i32: 1605 return getConstant(CountLeadingZeros_32((unsigned)Val), VT); 1606 case MVT::i64: 1607 return getConstant(CountLeadingZeros_64(Val), VT); 1608 } 1609 case ISD::CTTZ: 1610 switch(VT) { 1611 default: assert(0 && "Invalid cttz!"); break; 1612 case MVT::i1: return getConstant(Val == 0, VT); 1613 case MVT::i8: 1614 Tmp1 = (unsigned)Val | 0x100; 1615 return getConstant(CountTrailingZeros_32(Tmp1), VT); 1616 case MVT::i16: 1617 Tmp1 = (unsigned)Val | 0x10000; 1618 return getConstant(CountTrailingZeros_32(Tmp1), VT); 1619 case MVT::i32: 1620 return getConstant(CountTrailingZeros_32((unsigned)Val), VT); 1621 case MVT::i64: 1622 return getConstant(CountTrailingZeros_64(Val), VT); 1623 } 1624 } 1625 } 1626 1627 // Constant fold unary operations with an floating point constant operand. 1628 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 1629 switch (Opcode) { 1630 case ISD::FNEG: 1631 return getConstantFP(-C->getValue(), VT); 1632 case ISD::FABS: 1633 return getConstantFP(fabs(C->getValue()), VT); 1634 case ISD::FP_ROUND: 1635 case ISD::FP_EXTEND: 1636 return getConstantFP(C->getValue(), VT); 1637 case ISD::FP_TO_SINT: 1638 return getConstant((int64_t)C->getValue(), VT); 1639 case ISD::FP_TO_UINT: 1640 return getConstant((uint64_t)C->getValue(), VT); 1641 case ISD::BIT_CONVERT: 1642 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 1643 return getConstant(FloatToBits(C->getValue()), VT); 1644 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 1645 return getConstant(DoubleToBits(C->getValue()), VT); 1646 break; 1647 } 1648 1649 unsigned OpOpcode = Operand.Val->getOpcode(); 1650 switch (Opcode) { 1651 case ISD::TokenFactor: 1652 return Operand; // Factor of one node? No factor. 1653 case ISD::FP_ROUND: 1654 case ISD::FP_EXTEND: 1655 assert(MVT::isFloatingPoint(VT) && 1656 MVT::isFloatingPoint(Operand.getValueType()) && "Invalid FP cast!"); 1657 break; 1658 case ISD::SIGN_EXTEND: 1659 assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) && 1660 "Invalid SIGN_EXTEND!"); 1661 if (Operand.getValueType() == VT) return Operand; // noop extension 1662 assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!"); 1663 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 1664 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1665 break; 1666 case ISD::ZERO_EXTEND: 1667 assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) && 1668 "Invalid ZERO_EXTEND!"); 1669 if (Operand.getValueType() == VT) return Operand; // noop extension 1670 assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!"); 1671 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 1672 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 1673 break; 1674 case ISD::ANY_EXTEND: 1675 assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) && 1676 "Invalid ANY_EXTEND!"); 1677 if (Operand.getValueType() == VT) return Operand; // noop extension 1678 assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!"); 1679 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 1680 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 1681 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1682 break; 1683 case ISD::TRUNCATE: 1684 assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) && 1685 "Invalid TRUNCATE!"); 1686 if (Operand.getValueType() == VT) return Operand; // noop truncate 1687 assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!"); 1688 if (OpOpcode == ISD::TRUNCATE) 1689 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 1690 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 1691 OpOpcode == ISD::ANY_EXTEND) { 1692 // If the source is smaller than the dest, we still need an extend. 1693 if (Operand.Val->getOperand(0).getValueType() < VT) 1694 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 1695 else if (Operand.Val->getOperand(0).getValueType() > VT) 1696 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 1697 else 1698 return Operand.Val->getOperand(0); 1699 } 1700 break; 1701 case ISD::BIT_CONVERT: 1702 // Basic sanity checking. 1703 assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType()) 1704 && "Cannot BIT_CONVERT between types of different sizes!"); 1705 if (VT == Operand.getValueType()) return Operand; // noop conversion. 1706 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 1707 return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); 1708 if (OpOpcode == ISD::UNDEF) 1709 return getNode(ISD::UNDEF, VT); 1710 break; 1711 case ISD::SCALAR_TO_VECTOR: 1712 assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) && 1713 MVT::getVectorElementType(VT) == Operand.getValueType() && 1714 "Illegal SCALAR_TO_VECTOR node!"); 1715 break; 1716 case ISD::FNEG: 1717 if (OpOpcode == ISD::FSUB) // -(X-Y) -> (Y-X) 1718 return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1), 1719 Operand.Val->getOperand(0)); 1720 if (OpOpcode == ISD::FNEG) // --X -> X 1721 return Operand.Val->getOperand(0); 1722 break; 1723 case ISD::FABS: 1724 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 1725 return getNode(ISD::FABS, VT, Operand.Val->getOperand(0)); 1726 break; 1727 } 1728 1729 SDNode *N; 1730 SDVTList VTs = getVTList(VT); 1731 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 1732 FoldingSetNodeID ID; 1733 SDOperand Ops[1] = { Operand }; 1734 AddNodeIDNode(ID, Opcode, VTs, Ops, 1); 1735 void *IP = 0; 1736 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1737 return SDOperand(E, 0); 1738 N = new UnarySDNode(Opcode, VTs, Operand); 1739 CSEMap.InsertNode(N, IP); 1740 } else { 1741 N = new UnarySDNode(Opcode, VTs, Operand); 1742 } 1743 AllNodes.push_back(N); 1744 return SDOperand(N, 0); 1745} 1746 1747 1748 1749SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1750 SDOperand N1, SDOperand N2) { 1751#ifndef NDEBUG 1752 switch (Opcode) { 1753 case ISD::TokenFactor: 1754 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 1755 N2.getValueType() == MVT::Other && "Invalid token factor!"); 1756 break; 1757 case ISD::AND: 1758 case ISD::OR: 1759 case ISD::XOR: 1760 case ISD::UDIV: 1761 case ISD::UREM: 1762 case ISD::MULHU: 1763 case ISD::MULHS: 1764 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 1765 // fall through 1766 case ISD::ADD: 1767 case ISD::SUB: 1768 case ISD::MUL: 1769 case ISD::SDIV: 1770 case ISD::SREM: 1771 assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops"); 1772 // fall through. 1773 case ISD::FADD: 1774 case ISD::FSUB: 1775 case ISD::FMUL: 1776 case ISD::FDIV: 1777 case ISD::FREM: 1778 assert(N1.getValueType() == N2.getValueType() && 1779 N1.getValueType() == VT && "Binary operator types must match!"); 1780 break; 1781 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 1782 assert(N1.getValueType() == VT && 1783 MVT::isFloatingPoint(N1.getValueType()) && 1784 MVT::isFloatingPoint(N2.getValueType()) && 1785 "Invalid FCOPYSIGN!"); 1786 break; 1787 case ISD::SHL: 1788 case ISD::SRA: 1789 case ISD::SRL: 1790 case ISD::ROTL: 1791 case ISD::ROTR: 1792 assert(VT == N1.getValueType() && 1793 "Shift operators return type must be the same as their first arg"); 1794 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 1795 VT != MVT::i1 && "Shifts only work on integers"); 1796 break; 1797 case ISD::FP_ROUND_INREG: { 1798 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1799 assert(VT == N1.getValueType() && "Not an inreg round!"); 1800 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 1801 "Cannot FP_ROUND_INREG integer types"); 1802 assert(EVT <= VT && "Not rounding down!"); 1803 break; 1804 } 1805 case ISD::AssertSext: 1806 case ISD::AssertZext: 1807 case ISD::SIGN_EXTEND_INREG: { 1808 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1809 assert(VT == N1.getValueType() && "Not an inreg extend!"); 1810 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 1811 "Cannot *_EXTEND_INREG FP types"); 1812 assert(EVT <= VT && "Not extending!"); 1813 } 1814 1815 default: break; 1816 } 1817#endif 1818 1819 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1820 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1821 if (N1C) { 1822 if (Opcode == ISD::SIGN_EXTEND_INREG) { 1823 int64_t Val = N1C->getValue(); 1824 unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT()); 1825 Val <<= 64-FromBits; 1826 Val >>= 64-FromBits; 1827 return getConstant(Val, VT); 1828 } 1829 1830 if (N2C) { 1831 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 1832 switch (Opcode) { 1833 case ISD::ADD: return getConstant(C1 + C2, VT); 1834 case ISD::SUB: return getConstant(C1 - C2, VT); 1835 case ISD::MUL: return getConstant(C1 * C2, VT); 1836 case ISD::UDIV: 1837 if (C2) return getConstant(C1 / C2, VT); 1838 break; 1839 case ISD::UREM : 1840 if (C2) return getConstant(C1 % C2, VT); 1841 break; 1842 case ISD::SDIV : 1843 if (C2) return getConstant(N1C->getSignExtended() / 1844 N2C->getSignExtended(), VT); 1845 break; 1846 case ISD::SREM : 1847 if (C2) return getConstant(N1C->getSignExtended() % 1848 N2C->getSignExtended(), VT); 1849 break; 1850 case ISD::AND : return getConstant(C1 & C2, VT); 1851 case ISD::OR : return getConstant(C1 | C2, VT); 1852 case ISD::XOR : return getConstant(C1 ^ C2, VT); 1853 case ISD::SHL : return getConstant(C1 << C2, VT); 1854 case ISD::SRL : return getConstant(C1 >> C2, VT); 1855 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 1856 case ISD::ROTL : 1857 return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)), 1858 VT); 1859 case ISD::ROTR : 1860 return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 1861 VT); 1862 default: break; 1863 } 1864 } else { // Cannonicalize constant to RHS if commutative 1865 if (isCommutativeBinOp(Opcode)) { 1866 std::swap(N1C, N2C); 1867 std::swap(N1, N2); 1868 } 1869 } 1870 } 1871 1872 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 1873 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 1874 if (N1CFP) { 1875 if (N2CFP) { 1876 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 1877 switch (Opcode) { 1878 case ISD::FADD: return getConstantFP(C1 + C2, VT); 1879 case ISD::FSUB: return getConstantFP(C1 - C2, VT); 1880 case ISD::FMUL: return getConstantFP(C1 * C2, VT); 1881 case ISD::FDIV: 1882 if (C2) return getConstantFP(C1 / C2, VT); 1883 break; 1884 case ISD::FREM : 1885 if (C2) return getConstantFP(fmod(C1, C2), VT); 1886 break; 1887 case ISD::FCOPYSIGN: { 1888 union { 1889 double F; 1890 uint64_t I; 1891 } u1; 1892 u1.F = C1; 1893 if (int64_t(DoubleToBits(C2)) < 0) // Sign bit of RHS set? 1894 u1.I |= 1ULL << 63; // Set the sign bit of the LHS. 1895 else 1896 u1.I &= (1ULL << 63)-1; // Clear the sign bit of the LHS. 1897 return getConstantFP(u1.F, VT); 1898 } 1899 default: break; 1900 } 1901 } else { // Cannonicalize constant to RHS if commutative 1902 if (isCommutativeBinOp(Opcode)) { 1903 std::swap(N1CFP, N2CFP); 1904 std::swap(N1, N2); 1905 } 1906 } 1907 } 1908 1909 // Canonicalize an UNDEF to the RHS, even over a constant. 1910 if (N1.getOpcode() == ISD::UNDEF) { 1911 if (isCommutativeBinOp(Opcode)) { 1912 std::swap(N1, N2); 1913 } else { 1914 switch (Opcode) { 1915 case ISD::FP_ROUND_INREG: 1916 case ISD::SIGN_EXTEND_INREG: 1917 case ISD::SUB: 1918 case ISD::FSUB: 1919 case ISD::FDIV: 1920 case ISD::FREM: 1921 case ISD::SRA: 1922 return N1; // fold op(undef, arg2) -> undef 1923 case ISD::UDIV: 1924 case ISD::SDIV: 1925 case ISD::UREM: 1926 case ISD::SREM: 1927 case ISD::SRL: 1928 case ISD::SHL: 1929 if (!MVT::isVector(VT)) 1930 return getConstant(0, VT); // fold op(undef, arg2) -> 0 1931 // For vectors, we can't easily build an all zero vector, just return 1932 // the LHS. 1933 return N2; 1934 } 1935 } 1936 } 1937 1938 // Fold a bunch of operators when the RHS is undef. 1939 if (N2.getOpcode() == ISD::UNDEF) { 1940 switch (Opcode) { 1941 case ISD::ADD: 1942 case ISD::ADDC: 1943 case ISD::ADDE: 1944 case ISD::SUB: 1945 case ISD::FADD: 1946 case ISD::FSUB: 1947 case ISD::FMUL: 1948 case ISD::FDIV: 1949 case ISD::FREM: 1950 case ISD::UDIV: 1951 case ISD::SDIV: 1952 case ISD::UREM: 1953 case ISD::SREM: 1954 case ISD::XOR: 1955 return N2; // fold op(arg1, undef) -> undef 1956 case ISD::MUL: 1957 case ISD::AND: 1958 case ISD::SRL: 1959 case ISD::SHL: 1960 if (!MVT::isVector(VT)) 1961 return getConstant(0, VT); // fold op(arg1, undef) -> 0 1962 // For vectors, we can't easily build an all zero vector, just return 1963 // the LHS. 1964 return N1; 1965 case ISD::OR: 1966 if (!MVT::isVector(VT)) 1967 return getConstant(MVT::getIntVTBitMask(VT), VT); 1968 // For vectors, we can't easily build an all one vector, just return 1969 // the LHS. 1970 return N1; 1971 case ISD::SRA: 1972 return N1; 1973 } 1974 } 1975 1976 // Fold operations. 1977 switch (Opcode) { 1978 case ISD::TokenFactor: 1979 // Fold trivial token factors. 1980 if (N1.getOpcode() == ISD::EntryToken) return N2; 1981 if (N2.getOpcode() == ISD::EntryToken) return N1; 1982 break; 1983 1984 case ISD::AND: 1985 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's 1986 // worth handling here. 1987 if (N2C && N2C->getValue() == 0) 1988 return N2; 1989 break; 1990 case ISD::OR: 1991 case ISD::XOR: 1992 // (X ^| 0) -> X. This commonly occurs when legalizing i64 values, so it's 1993 // worth handling here. 1994 if (N2C && N2C->getValue() == 0) 1995 return N1; 1996 break; 1997 case ISD::FP_ROUND_INREG: 1998 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 1999 break; 2000 case ISD::SIGN_EXTEND_INREG: { 2001 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 2002 if (EVT == VT) return N1; // Not actually extending 2003 break; 2004 } 2005 case ISD::EXTRACT_VECTOR_ELT: 2006 assert(N2C && "Bad EXTRACT_VECTOR_ELT!"); 2007 2008 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is 2009 // expanding copies of large vectors from registers. 2010 if (N1.getOpcode() == ISD::CONCAT_VECTORS && 2011 N1.getNumOperands() > 0) { 2012 unsigned Factor = 2013 MVT::getVectorNumElements(N1.getOperand(0).getValueType()); 2014 return getNode(ISD::EXTRACT_VECTOR_ELT, VT, 2015 N1.getOperand(N2C->getValue() / Factor), 2016 getConstant(N2C->getValue() % Factor, N2.getValueType())); 2017 } 2018 2019 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is 2020 // expanding large vector constants. 2021 if (N1.getOpcode() == ISD::BUILD_VECTOR) 2022 return N1.getOperand(N2C->getValue()); 2023 2024 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector 2025 // operations are lowered to scalars. 2026 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) 2027 if (ConstantSDNode *IEC = dyn_cast<ConstantSDNode>(N1.getOperand(2))) { 2028 if (IEC == N2C) 2029 return N1.getOperand(1); 2030 else 2031 return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2); 2032 } 2033 break; 2034 case ISD::EXTRACT_ELEMENT: 2035 assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!"); 2036 2037 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding 2038 // 64-bit integers into 32-bit parts. Instead of building the extract of 2039 // the BUILD_PAIR, only to have legalize rip it apart, just do it now. 2040 if (N1.getOpcode() == ISD::BUILD_PAIR) 2041 return N1.getOperand(N2C->getValue()); 2042 2043 // EXTRACT_ELEMENT of a constant int is also very common. 2044 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) { 2045 unsigned Shift = MVT::getSizeInBits(VT) * N2C->getValue(); 2046 return getConstant(C->getValue() >> Shift, VT); 2047 } 2048 break; 2049 2050 // FIXME: figure out how to safely handle things like 2051 // int foo(int x) { return 1 << (x & 255); } 2052 // int bar() { return foo(256); } 2053#if 0 2054 case ISD::SHL: 2055 case ISD::SRL: 2056 case ISD::SRA: 2057 if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG && 2058 cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1) 2059 return getNode(Opcode, VT, N1, N2.getOperand(0)); 2060 else if (N2.getOpcode() == ISD::AND) 2061 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) { 2062 // If the and is only masking out bits that cannot effect the shift, 2063 // eliminate the and. 2064 unsigned NumBits = MVT::getSizeInBits(VT); 2065 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 2066 return getNode(Opcode, VT, N1, N2.getOperand(0)); 2067 } 2068 break; 2069#endif 2070 } 2071 2072 // Memoize this node if possible. 2073 SDNode *N; 2074 SDVTList VTs = getVTList(VT); 2075 if (VT != MVT::Flag) { 2076 SDOperand Ops[] = { N1, N2 }; 2077 FoldingSetNodeID ID; 2078 AddNodeIDNode(ID, Opcode, VTs, Ops, 2); 2079 void *IP = 0; 2080 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2081 return SDOperand(E, 0); 2082 N = new BinarySDNode(Opcode, VTs, N1, N2); 2083 CSEMap.InsertNode(N, IP); 2084 } else { 2085 N = new BinarySDNode(Opcode, VTs, N1, N2); 2086 } 2087 2088 AllNodes.push_back(N); 2089 return SDOperand(N, 0); 2090} 2091 2092SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 2093 SDOperand N1, SDOperand N2, SDOperand N3) { 2094 // Perform various simplifications. 2095 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 2096 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 2097 switch (Opcode) { 2098 case ISD::SETCC: { 2099 // Use FoldSetCC to simplify SETCC's. 2100 SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get()); 2101 if (Simp.Val) return Simp; 2102 break; 2103 } 2104 case ISD::SELECT: 2105 if (N1C) 2106 if (N1C->getValue()) 2107 return N2; // select true, X, Y -> X 2108 else 2109 return N3; // select false, X, Y -> Y 2110 2111 if (N2 == N3) return N2; // select C, X, X -> X 2112 break; 2113 case ISD::BRCOND: 2114 if (N2C) 2115 if (N2C->getValue()) // Unconditional branch 2116 return getNode(ISD::BR, MVT::Other, N1, N3); 2117 else 2118 return N1; // Never-taken branch 2119 break; 2120 case ISD::VECTOR_SHUFFLE: 2121 assert(VT == N1.getValueType() && VT == N2.getValueType() && 2122 MVT::isVector(VT) && MVT::isVector(N3.getValueType()) && 2123 N3.getOpcode() == ISD::BUILD_VECTOR && 2124 MVT::getVectorNumElements(VT) == N3.getNumOperands() && 2125 "Illegal VECTOR_SHUFFLE node!"); 2126 break; 2127 case ISD::BIT_CONVERT: 2128 // Fold bit_convert nodes from a type to themselves. 2129 if (N1.getValueType() == VT) 2130 return N1; 2131 break; 2132 } 2133 2134 // Memoize node if it doesn't produce a flag. 2135 SDNode *N; 2136 SDVTList VTs = getVTList(VT); 2137 if (VT != MVT::Flag) { 2138 SDOperand Ops[] = { N1, N2, N3 }; 2139 FoldingSetNodeID ID; 2140 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 2141 void *IP = 0; 2142 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2143 return SDOperand(E, 0); 2144 N = new TernarySDNode(Opcode, VTs, N1, N2, N3); 2145 CSEMap.InsertNode(N, IP); 2146 } else { 2147 N = new TernarySDNode(Opcode, VTs, N1, N2, N3); 2148 } 2149 AllNodes.push_back(N); 2150 return SDOperand(N, 0); 2151} 2152 2153SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 2154 SDOperand N1, SDOperand N2, SDOperand N3, 2155 SDOperand N4) { 2156 SDOperand Ops[] = { N1, N2, N3, N4 }; 2157 return getNode(Opcode, VT, Ops, 4); 2158} 2159 2160SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 2161 SDOperand N1, SDOperand N2, SDOperand N3, 2162 SDOperand N4, SDOperand N5) { 2163 SDOperand Ops[] = { N1, N2, N3, N4, N5 }; 2164 return getNode(Opcode, VT, Ops, 5); 2165} 2166 2167SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 2168 SDOperand Chain, SDOperand Ptr, 2169 const Value *SV, int SVOffset, 2170 bool isVolatile, unsigned Alignment) { 2171 if (Alignment == 0) { // Ensure that codegen never sees alignment 0 2172 const Type *Ty = 0; 2173 if (VT != MVT::iPTR) { 2174 Ty = MVT::getTypeForValueType(VT); 2175 } else if (SV) { 2176 const PointerType *PT = dyn_cast<PointerType>(SV->getType()); 2177 assert(PT && "Value for load must be a pointer"); 2178 Ty = PT->getElementType(); 2179 } 2180 assert(Ty && "Could not get type information for load"); 2181 Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); 2182 } 2183 SDVTList VTs = getVTList(VT, MVT::Other); 2184 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 2185 SDOperand Ops[] = { Chain, Ptr, Undef }; 2186 FoldingSetNodeID ID; 2187 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 2188 ID.AddInteger(ISD::UNINDEXED); 2189 ID.AddInteger(ISD::NON_EXTLOAD); 2190 ID.AddInteger(VT); 2191 ID.AddPointer(SV); 2192 ID.AddInteger(SVOffset); 2193 ID.AddInteger(Alignment); 2194 ID.AddInteger(isVolatile); 2195 void *IP = 0; 2196 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2197 return SDOperand(E, 0); 2198 SDNode *N = new LoadSDNode(Ops, VTs, ISD::UNINDEXED, 2199 ISD::NON_EXTLOAD, VT, SV, SVOffset, Alignment, 2200 isVolatile); 2201 CSEMap.InsertNode(N, IP); 2202 AllNodes.push_back(N); 2203 return SDOperand(N, 0); 2204} 2205 2206SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 2207 SDOperand Chain, SDOperand Ptr, 2208 const Value *SV, 2209 int SVOffset, MVT::ValueType EVT, 2210 bool isVolatile, unsigned Alignment) { 2211 // If they are asking for an extending load from/to the same thing, return a 2212 // normal load. 2213 if (VT == EVT) 2214 ExtType = ISD::NON_EXTLOAD; 2215 2216 if (MVT::isVector(VT)) 2217 assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!"); 2218 else 2219 assert(EVT < VT && "Should only be an extending load, not truncating!"); 2220 assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) && 2221 "Cannot sign/zero extend a FP/Vector load!"); 2222 assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && 2223 "Cannot convert from FP to Int or Int -> FP!"); 2224 2225 if (Alignment == 0) { // Ensure that codegen never sees alignment 0 2226 const Type *Ty = 0; 2227 if (VT != MVT::iPTR) { 2228 Ty = MVT::getTypeForValueType(VT); 2229 } else if (SV) { 2230 const PointerType *PT = dyn_cast<PointerType>(SV->getType()); 2231 assert(PT && "Value for load must be a pointer"); 2232 Ty = PT->getElementType(); 2233 } 2234 assert(Ty && "Could not get type information for load"); 2235 Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); 2236 } 2237 SDVTList VTs = getVTList(VT, MVT::Other); 2238 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 2239 SDOperand Ops[] = { Chain, Ptr, Undef }; 2240 FoldingSetNodeID ID; 2241 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 2242 ID.AddInteger(ISD::UNINDEXED); 2243 ID.AddInteger(ExtType); 2244 ID.AddInteger(EVT); 2245 ID.AddPointer(SV); 2246 ID.AddInteger(SVOffset); 2247 ID.AddInteger(Alignment); 2248 ID.AddInteger(isVolatile); 2249 void *IP = 0; 2250 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2251 return SDOperand(E, 0); 2252 SDNode *N = new LoadSDNode(Ops, VTs, ISD::UNINDEXED, ExtType, EVT, 2253 SV, SVOffset, Alignment, isVolatile); 2254 CSEMap.InsertNode(N, IP); 2255 AllNodes.push_back(N); 2256 return SDOperand(N, 0); 2257} 2258 2259SDOperand 2260SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 2261 SDOperand Offset, ISD::MemIndexedMode AM) { 2262 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad); 2263 assert(LD->getOffset().getOpcode() == ISD::UNDEF && 2264 "Load is already a indexed load!"); 2265 MVT::ValueType VT = OrigLoad.getValueType(); 2266 SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other); 2267 SDOperand Ops[] = { LD->getChain(), Base, Offset }; 2268 FoldingSetNodeID ID; 2269 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 2270 ID.AddInteger(AM); 2271 ID.AddInteger(LD->getExtensionType()); 2272 ID.AddInteger(LD->getLoadedVT()); 2273 ID.AddPointer(LD->getSrcValue()); 2274 ID.AddInteger(LD->getSrcValueOffset()); 2275 ID.AddInteger(LD->getAlignment()); 2276 ID.AddInteger(LD->isVolatile()); 2277 void *IP = 0; 2278 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2279 return SDOperand(E, 0); 2280 SDNode *N = new LoadSDNode(Ops, VTs, AM, 2281 LD->getExtensionType(), LD->getLoadedVT(), 2282 LD->getSrcValue(), LD->getSrcValueOffset(), 2283 LD->getAlignment(), LD->isVolatile()); 2284 CSEMap.InsertNode(N, IP); 2285 AllNodes.push_back(N); 2286 return SDOperand(N, 0); 2287} 2288 2289SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val, 2290 SDOperand Ptr, const Value *SV, int SVOffset, 2291 bool isVolatile, unsigned Alignment) { 2292 MVT::ValueType VT = Val.getValueType(); 2293 2294 if (Alignment == 0) { // Ensure that codegen never sees alignment 0 2295 const Type *Ty = 0; 2296 if (VT != MVT::iPTR) { 2297 Ty = MVT::getTypeForValueType(VT); 2298 } else if (SV) { 2299 const PointerType *PT = dyn_cast<PointerType>(SV->getType()); 2300 assert(PT && "Value for store must be a pointer"); 2301 Ty = PT->getElementType(); 2302 } 2303 assert(Ty && "Could not get type information for store"); 2304 Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); 2305 } 2306 SDVTList VTs = getVTList(MVT::Other); 2307 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 2308 SDOperand Ops[] = { Chain, Val, Ptr, Undef }; 2309 FoldingSetNodeID ID; 2310 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 2311 ID.AddInteger(ISD::UNINDEXED); 2312 ID.AddInteger(false); 2313 ID.AddInteger(VT); 2314 ID.AddPointer(SV); 2315 ID.AddInteger(SVOffset); 2316 ID.AddInteger(Alignment); 2317 ID.AddInteger(isVolatile); 2318 void *IP = 0; 2319 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2320 return SDOperand(E, 0); 2321 SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false, 2322 VT, SV, SVOffset, Alignment, isVolatile); 2323 CSEMap.InsertNode(N, IP); 2324 AllNodes.push_back(N); 2325 return SDOperand(N, 0); 2326} 2327 2328SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val, 2329 SDOperand Ptr, const Value *SV, 2330 int SVOffset, MVT::ValueType SVT, 2331 bool isVolatile, unsigned Alignment) { 2332 MVT::ValueType VT = Val.getValueType(); 2333 bool isTrunc = VT != SVT; 2334 2335 assert(VT > SVT && "Not a truncation?"); 2336 assert(MVT::isInteger(VT) == MVT::isInteger(SVT) && 2337 "Can't do FP-INT conversion!"); 2338 2339 if (Alignment == 0) { // Ensure that codegen never sees alignment 0 2340 const Type *Ty = 0; 2341 if (VT != MVT::iPTR) { 2342 Ty = MVT::getTypeForValueType(VT); 2343 } else if (SV) { 2344 const PointerType *PT = dyn_cast<PointerType>(SV->getType()); 2345 assert(PT && "Value for store must be a pointer"); 2346 Ty = PT->getElementType(); 2347 } 2348 assert(Ty && "Could not get type information for store"); 2349 Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); 2350 } 2351 SDVTList VTs = getVTList(MVT::Other); 2352 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 2353 SDOperand Ops[] = { Chain, Val, Ptr, Undef }; 2354 FoldingSetNodeID ID; 2355 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 2356 ID.AddInteger(ISD::UNINDEXED); 2357 ID.AddInteger(isTrunc); 2358 ID.AddInteger(SVT); 2359 ID.AddPointer(SV); 2360 ID.AddInteger(SVOffset); 2361 ID.AddInteger(Alignment); 2362 ID.AddInteger(isVolatile); 2363 void *IP = 0; 2364 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2365 return SDOperand(E, 0); 2366 SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, isTrunc, 2367 SVT, SV, SVOffset, Alignment, isVolatile); 2368 CSEMap.InsertNode(N, IP); 2369 AllNodes.push_back(N); 2370 return SDOperand(N, 0); 2371} 2372 2373SDOperand 2374SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base, 2375 SDOperand Offset, ISD::MemIndexedMode AM) { 2376 StoreSDNode *ST = cast<StoreSDNode>(OrigStore); 2377 assert(ST->getOffset().getOpcode() == ISD::UNDEF && 2378 "Store is already a indexed store!"); 2379 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other); 2380 SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; 2381 FoldingSetNodeID ID; 2382 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 2383 ID.AddInteger(AM); 2384 ID.AddInteger(ST->isTruncatingStore()); 2385 ID.AddInteger(ST->getStoredVT()); 2386 ID.AddPointer(ST->getSrcValue()); 2387 ID.AddInteger(ST->getSrcValueOffset()); 2388 ID.AddInteger(ST->getAlignment()); 2389 ID.AddInteger(ST->isVolatile()); 2390 void *IP = 0; 2391 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2392 return SDOperand(E, 0); 2393 SDNode *N = new StoreSDNode(Ops, VTs, AM, 2394 ST->isTruncatingStore(), ST->getStoredVT(), 2395 ST->getSrcValue(), ST->getSrcValueOffset(), 2396 ST->getAlignment(), ST->isVolatile()); 2397 CSEMap.InsertNode(N, IP); 2398 AllNodes.push_back(N); 2399 return SDOperand(N, 0); 2400} 2401 2402SDOperand SelectionDAG::getVAArg(MVT::ValueType VT, 2403 SDOperand Chain, SDOperand Ptr, 2404 SDOperand SV) { 2405 SDOperand Ops[] = { Chain, Ptr, SV }; 2406 return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3); 2407} 2408 2409SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 2410 const SDOperand *Ops, unsigned NumOps) { 2411 switch (NumOps) { 2412 case 0: return getNode(Opcode, VT); 2413 case 1: return getNode(Opcode, VT, Ops[0]); 2414 case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); 2415 case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); 2416 default: break; 2417 } 2418 2419 switch (Opcode) { 2420 default: break; 2421 case ISD::SELECT_CC: { 2422 assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); 2423 assert(Ops[0].getValueType() == Ops[1].getValueType() && 2424 "LHS and RHS of condition must have same type!"); 2425 assert(Ops[2].getValueType() == Ops[3].getValueType() && 2426 "True and False arms of SelectCC must have same type!"); 2427 assert(Ops[2].getValueType() == VT && 2428 "select_cc node must be of same type as true and false value!"); 2429 break; 2430 } 2431 case ISD::BR_CC: { 2432 assert(NumOps == 5 && "BR_CC takes 5 operands!"); 2433 assert(Ops[2].getValueType() == Ops[3].getValueType() && 2434 "LHS/RHS of comparison should match types!"); 2435 break; 2436 } 2437 } 2438 2439 // Memoize nodes. 2440 SDNode *N; 2441 SDVTList VTs = getVTList(VT); 2442 if (VT != MVT::Flag) { 2443 FoldingSetNodeID ID; 2444 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); 2445 void *IP = 0; 2446 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2447 return SDOperand(E, 0); 2448 N = new SDNode(Opcode, VTs, Ops, NumOps); 2449 CSEMap.InsertNode(N, IP); 2450 } else { 2451 N = new SDNode(Opcode, VTs, Ops, NumOps); 2452 } 2453 AllNodes.push_back(N); 2454 return SDOperand(N, 0); 2455} 2456 2457SDOperand SelectionDAG::getNode(unsigned Opcode, 2458 std::vector<MVT::ValueType> &ResultTys, 2459 const SDOperand *Ops, unsigned NumOps) { 2460 return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(), 2461 Ops, NumOps); 2462} 2463 2464SDOperand SelectionDAG::getNode(unsigned Opcode, 2465 const MVT::ValueType *VTs, unsigned NumVTs, 2466 const SDOperand *Ops, unsigned NumOps) { 2467 if (NumVTs == 1) 2468 return getNode(Opcode, VTs[0], Ops, NumOps); 2469 return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps); 2470} 2471 2472SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, 2473 const SDOperand *Ops, unsigned NumOps) { 2474 if (VTList.NumVTs == 1) 2475 return getNode(Opcode, VTList.VTs[0], Ops, NumOps); 2476 2477 switch (Opcode) { 2478 // FIXME: figure out how to safely handle things like 2479 // int foo(int x) { return 1 << (x & 255); } 2480 // int bar() { return foo(256); } 2481#if 0 2482 case ISD::SRA_PARTS: 2483 case ISD::SRL_PARTS: 2484 case ISD::SHL_PARTS: 2485 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 2486 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 2487 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 2488 else if (N3.getOpcode() == ISD::AND) 2489 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 2490 // If the and is only masking out bits that cannot effect the shift, 2491 // eliminate the and. 2492 unsigned NumBits = MVT::getSizeInBits(VT)*2; 2493 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 2494 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 2495 } 2496 break; 2497#endif 2498 } 2499 2500 // Memoize the node unless it returns a flag. 2501 SDNode *N; 2502 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 2503 FoldingSetNodeID ID; 2504 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 2505 void *IP = 0; 2506 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2507 return SDOperand(E, 0); 2508 if (NumOps == 1) 2509 N = new UnarySDNode(Opcode, VTList, Ops[0]); 2510 else if (NumOps == 2) 2511 N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); 2512 else if (NumOps == 3) 2513 N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); 2514 else 2515 N = new SDNode(Opcode, VTList, Ops, NumOps); 2516 CSEMap.InsertNode(N, IP); 2517 } else { 2518 if (NumOps == 1) 2519 N = new UnarySDNode(Opcode, VTList, Ops[0]); 2520 else if (NumOps == 2) 2521 N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]); 2522 else if (NumOps == 3) 2523 N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]); 2524 else 2525 N = new SDNode(Opcode, VTList, Ops, NumOps); 2526 } 2527 AllNodes.push_back(N); 2528 return SDOperand(N, 0); 2529} 2530 2531SDVTList SelectionDAG::getVTList(MVT::ValueType VT) { 2532 if (!MVT::isExtendedVT(VT)) 2533 return makeVTList(SDNode::getValueTypeList(VT), 1); 2534 2535 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 2536 E = VTList.end(); I != E; ++I) { 2537 if (I->size() == 1 && (*I)[0] == VT) 2538 return makeVTList(&(*I)[0], 1); 2539 } 2540 std::vector<MVT::ValueType> V; 2541 V.push_back(VT); 2542 VTList.push_front(V); 2543 return makeVTList(&(*VTList.begin())[0], 1); 2544} 2545 2546SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) { 2547 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 2548 E = VTList.end(); I != E; ++I) { 2549 if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) 2550 return makeVTList(&(*I)[0], 2); 2551 } 2552 std::vector<MVT::ValueType> V; 2553 V.push_back(VT1); 2554 V.push_back(VT2); 2555 VTList.push_front(V); 2556 return makeVTList(&(*VTList.begin())[0], 2); 2557} 2558SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2, 2559 MVT::ValueType VT3) { 2560 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 2561 E = VTList.end(); I != E; ++I) { 2562 if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 && 2563 (*I)[2] == VT3) 2564 return makeVTList(&(*I)[0], 3); 2565 } 2566 std::vector<MVT::ValueType> V; 2567 V.push_back(VT1); 2568 V.push_back(VT2); 2569 V.push_back(VT3); 2570 VTList.push_front(V); 2571 return makeVTList(&(*VTList.begin())[0], 3); 2572} 2573 2574SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) { 2575 switch (NumVTs) { 2576 case 0: assert(0 && "Cannot have nodes without results!"); 2577 case 1: return getVTList(VTs[0]); 2578 case 2: return getVTList(VTs[0], VTs[1]); 2579 case 3: return getVTList(VTs[0], VTs[1], VTs[2]); 2580 default: break; 2581 } 2582 2583 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 2584 E = VTList.end(); I != E; ++I) { 2585 if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue; 2586 2587 bool NoMatch = false; 2588 for (unsigned i = 2; i != NumVTs; ++i) 2589 if (VTs[i] != (*I)[i]) { 2590 NoMatch = true; 2591 break; 2592 } 2593 if (!NoMatch) 2594 return makeVTList(&*I->begin(), NumVTs); 2595 } 2596 2597 VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs)); 2598 return makeVTList(&*VTList.begin()->begin(), NumVTs); 2599} 2600 2601 2602/// UpdateNodeOperands - *Mutate* the specified node in-place to have the 2603/// specified operands. If the resultant node already exists in the DAG, 2604/// this does not modify the specified node, instead it returns the node that 2605/// already exists. If the resultant node does not exist in the DAG, the 2606/// input node is returned. As a degenerate case, if you specify the same 2607/// input operands as the node already has, the input node is returned. 2608SDOperand SelectionDAG:: 2609UpdateNodeOperands(SDOperand InN, SDOperand Op) { 2610 SDNode *N = InN.Val; 2611 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 2612 2613 // Check to see if there is no change. 2614 if (Op == N->getOperand(0)) return InN; 2615 2616 // See if the modified node already exists. 2617 void *InsertPos = 0; 2618 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) 2619 return SDOperand(Existing, InN.ResNo); 2620 2621 // Nope it doesn't. Remove the node from it's current place in the maps. 2622 if (InsertPos) 2623 RemoveNodeFromCSEMaps(N); 2624 2625 // Now we update the operands. 2626 N->OperandList[0].Val->removeUser(N); 2627 Op.Val->addUser(N); 2628 N->OperandList[0] = Op; 2629 2630 // If this gets put into a CSE map, add it. 2631 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 2632 return InN; 2633} 2634 2635SDOperand SelectionDAG:: 2636UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { 2637 SDNode *N = InN.Val; 2638 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 2639 2640 // Check to see if there is no change. 2641 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 2642 return InN; // No operands changed, just return the input node. 2643 2644 // See if the modified node already exists. 2645 void *InsertPos = 0; 2646 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) 2647 return SDOperand(Existing, InN.ResNo); 2648 2649 // Nope it doesn't. Remove the node from it's current place in the maps. 2650 if (InsertPos) 2651 RemoveNodeFromCSEMaps(N); 2652 2653 // Now we update the operands. 2654 if (N->OperandList[0] != Op1) { 2655 N->OperandList[0].Val->removeUser(N); 2656 Op1.Val->addUser(N); 2657 N->OperandList[0] = Op1; 2658 } 2659 if (N->OperandList[1] != Op2) { 2660 N->OperandList[1].Val->removeUser(N); 2661 Op2.Val->addUser(N); 2662 N->OperandList[1] = Op2; 2663 } 2664 2665 // If this gets put into a CSE map, add it. 2666 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 2667 return InN; 2668} 2669 2670SDOperand SelectionDAG:: 2671UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 2672 SDOperand Ops[] = { Op1, Op2, Op3 }; 2673 return UpdateNodeOperands(N, Ops, 3); 2674} 2675 2676SDOperand SelectionDAG:: 2677UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 2678 SDOperand Op3, SDOperand Op4) { 2679 SDOperand Ops[] = { Op1, Op2, Op3, Op4 }; 2680 return UpdateNodeOperands(N, Ops, 4); 2681} 2682 2683SDOperand SelectionDAG:: 2684UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 2685 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 2686 SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 }; 2687 return UpdateNodeOperands(N, Ops, 5); 2688} 2689 2690 2691SDOperand SelectionDAG:: 2692UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { 2693 SDNode *N = InN.Val; 2694 assert(N->getNumOperands() == NumOps && 2695 "Update with wrong number of operands"); 2696 2697 // Check to see if there is no change. 2698 bool AnyChange = false; 2699 for (unsigned i = 0; i != NumOps; ++i) { 2700 if (Ops[i] != N->getOperand(i)) { 2701 AnyChange = true; 2702 break; 2703 } 2704 } 2705 2706 // No operands changed, just return the input node. 2707 if (!AnyChange) return InN; 2708 2709 // See if the modified node already exists. 2710 void *InsertPos = 0; 2711 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) 2712 return SDOperand(Existing, InN.ResNo); 2713 2714 // Nope it doesn't. Remove the node from it's current place in the maps. 2715 if (InsertPos) 2716 RemoveNodeFromCSEMaps(N); 2717 2718 // Now we update the operands. 2719 for (unsigned i = 0; i != NumOps; ++i) { 2720 if (N->OperandList[i] != Ops[i]) { 2721 N->OperandList[i].Val->removeUser(N); 2722 Ops[i].Val->addUser(N); 2723 N->OperandList[i] = Ops[i]; 2724 } 2725 } 2726 2727 // If this gets put into a CSE map, add it. 2728 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 2729 return InN; 2730} 2731 2732 2733/// MorphNodeTo - This frees the operands of the current node, resets the 2734/// opcode, types, and operands to the specified value. This should only be 2735/// used by the SelectionDAG class. 2736void SDNode::MorphNodeTo(unsigned Opc, SDVTList L, 2737 const SDOperand *Ops, unsigned NumOps) { 2738 NodeType = Opc; 2739 ValueList = L.VTs; 2740 NumValues = L.NumVTs; 2741 2742 // Clear the operands list, updating used nodes to remove this from their 2743 // use list. 2744 for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) 2745 I->Val->removeUser(this); 2746 2747 // If NumOps is larger than the # of operands we currently have, reallocate 2748 // the operand list. 2749 if (NumOps > NumOperands) { 2750 if (OperandsNeedDelete) 2751 delete [] OperandList; 2752 OperandList = new SDOperand[NumOps]; 2753 OperandsNeedDelete = true; 2754 } 2755 2756 // Assign the new operands. 2757 NumOperands = NumOps; 2758 2759 for (unsigned i = 0, e = NumOps; i != e; ++i) { 2760 OperandList[i] = Ops[i]; 2761 SDNode *N = OperandList[i].Val; 2762 N->Uses.push_back(this); 2763 } 2764} 2765 2766/// SelectNodeTo - These are used for target selectors to *mutate* the 2767/// specified node to have the specified return type, Target opcode, and 2768/// operands. Note that target opcodes are stored as 2769/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 2770/// 2771/// Note that SelectNodeTo returns the resultant node. If there is already a 2772/// node of the specified opcode and operands, it returns that node instead of 2773/// the current one. 2774SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2775 MVT::ValueType VT) { 2776 SDVTList VTs = getVTList(VT); 2777 FoldingSetNodeID ID; 2778 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, 0, 0); 2779 void *IP = 0; 2780 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2781 return ON; 2782 2783 RemoveNodeFromCSEMaps(N); 2784 2785 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, 0, 0); 2786 2787 CSEMap.InsertNode(N, IP); 2788 return N; 2789} 2790 2791SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2792 MVT::ValueType VT, SDOperand Op1) { 2793 // If an identical node already exists, use it. 2794 SDVTList VTs = getVTList(VT); 2795 SDOperand Ops[] = { Op1 }; 2796 2797 FoldingSetNodeID ID; 2798 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1); 2799 void *IP = 0; 2800 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2801 return ON; 2802 2803 RemoveNodeFromCSEMaps(N); 2804 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1); 2805 CSEMap.InsertNode(N, IP); 2806 return N; 2807} 2808 2809SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2810 MVT::ValueType VT, SDOperand Op1, 2811 SDOperand Op2) { 2812 // If an identical node already exists, use it. 2813 SDVTList VTs = getVTList(VT); 2814 SDOperand Ops[] = { Op1, Op2 }; 2815 2816 FoldingSetNodeID ID; 2817 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); 2818 void *IP = 0; 2819 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2820 return ON; 2821 2822 RemoveNodeFromCSEMaps(N); 2823 2824 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); 2825 2826 CSEMap.InsertNode(N, IP); // Memoize the new node. 2827 return N; 2828} 2829 2830SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2831 MVT::ValueType VT, SDOperand Op1, 2832 SDOperand Op2, SDOperand Op3) { 2833 // If an identical node already exists, use it. 2834 SDVTList VTs = getVTList(VT); 2835 SDOperand Ops[] = { Op1, Op2, Op3 }; 2836 FoldingSetNodeID ID; 2837 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); 2838 void *IP = 0; 2839 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2840 return ON; 2841 2842 RemoveNodeFromCSEMaps(N); 2843 2844 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); 2845 2846 CSEMap.InsertNode(N, IP); // Memoize the new node. 2847 return N; 2848} 2849 2850SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2851 MVT::ValueType VT, const SDOperand *Ops, 2852 unsigned NumOps) { 2853 // If an identical node already exists, use it. 2854 SDVTList VTs = getVTList(VT); 2855 FoldingSetNodeID ID; 2856 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps); 2857 void *IP = 0; 2858 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2859 return ON; 2860 2861 RemoveNodeFromCSEMaps(N); 2862 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps); 2863 2864 CSEMap.InsertNode(N, IP); // Memoize the new node. 2865 return N; 2866} 2867 2868SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2869 MVT::ValueType VT1, MVT::ValueType VT2, 2870 SDOperand Op1, SDOperand Op2) { 2871 SDVTList VTs = getVTList(VT1, VT2); 2872 FoldingSetNodeID ID; 2873 SDOperand Ops[] = { Op1, Op2 }; 2874 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); 2875 void *IP = 0; 2876 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2877 return ON; 2878 2879 RemoveNodeFromCSEMaps(N); 2880 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2); 2881 CSEMap.InsertNode(N, IP); // Memoize the new node. 2882 return N; 2883} 2884 2885SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 2886 MVT::ValueType VT1, MVT::ValueType VT2, 2887 SDOperand Op1, SDOperand Op2, 2888 SDOperand Op3) { 2889 // If an identical node already exists, use it. 2890 SDVTList VTs = getVTList(VT1, VT2); 2891 SDOperand Ops[] = { Op1, Op2, Op3 }; 2892 FoldingSetNodeID ID; 2893 AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); 2894 void *IP = 0; 2895 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2896 return ON; 2897 2898 RemoveNodeFromCSEMaps(N); 2899 2900 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3); 2901 CSEMap.InsertNode(N, IP); // Memoize the new node. 2902 return N; 2903} 2904 2905 2906/// getTargetNode - These are used for target selectors to create a new node 2907/// with specified return type(s), target opcode, and operands. 2908/// 2909/// Note that getTargetNode returns the resultant node. If there is already a 2910/// node of the specified opcode and operands, it returns that node instead of 2911/// the current one. 2912SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) { 2913 return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val; 2914} 2915SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2916 SDOperand Op1) { 2917 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val; 2918} 2919SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2920 SDOperand Op1, SDOperand Op2) { 2921 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val; 2922} 2923SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2924 SDOperand Op1, SDOperand Op2, 2925 SDOperand Op3) { 2926 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; 2927} 2928SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2929 const SDOperand *Ops, unsigned NumOps) { 2930 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val; 2931} 2932SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2933 MVT::ValueType VT2, SDOperand Op1) { 2934 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2935 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val; 2936} 2937SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2938 MVT::ValueType VT2, SDOperand Op1, 2939 SDOperand Op2) { 2940 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2941 SDOperand Ops[] = { Op1, Op2 }; 2942 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val; 2943} 2944SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2945 MVT::ValueType VT2, SDOperand Op1, 2946 SDOperand Op2, SDOperand Op3) { 2947 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2948 SDOperand Ops[] = { Op1, Op2, Op3 }; 2949 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val; 2950} 2951SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2952 MVT::ValueType VT2, 2953 const SDOperand *Ops, unsigned NumOps) { 2954 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2955 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val; 2956} 2957SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2958 MVT::ValueType VT2, MVT::ValueType VT3, 2959 SDOperand Op1, SDOperand Op2) { 2960 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); 2961 SDOperand Ops[] = { Op1, Op2 }; 2962 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val; 2963} 2964SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2965 MVT::ValueType VT2, MVT::ValueType VT3, 2966 SDOperand Op1, SDOperand Op2, 2967 SDOperand Op3) { 2968 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); 2969 SDOperand Ops[] = { Op1, Op2, Op3 }; 2970 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val; 2971} 2972SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2973 MVT::ValueType VT2, MVT::ValueType VT3, 2974 const SDOperand *Ops, unsigned NumOps) { 2975 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); 2976 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val; 2977} 2978 2979/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2980/// This can cause recursive merging of nodes in the DAG. 2981/// 2982/// This version assumes From/To have a single result value. 2983/// 2984void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN, 2985 std::vector<SDNode*> *Deleted) { 2986 SDNode *From = FromN.Val, *To = ToN.Val; 2987 assert(From->getNumValues() == 1 && To->getNumValues() == 1 && 2988 "Cannot replace with this method!"); 2989 assert(From != To && "Cannot replace uses of with self"); 2990 2991 while (!From->use_empty()) { 2992 // Process users until they are all gone. 2993 SDNode *U = *From->use_begin(); 2994 2995 // This node is about to morph, remove its old self from the CSE maps. 2996 RemoveNodeFromCSEMaps(U); 2997 2998 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2999 I != E; ++I) 3000 if (I->Val == From) { 3001 From->removeUser(U); 3002 I->Val = To; 3003 To->addUser(U); 3004 } 3005 3006 // Now that we have modified U, add it back to the CSE maps. If it already 3007 // exists there, recursively merge the results together. 3008 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 3009 ReplaceAllUsesWith(U, Existing, Deleted); 3010 // U is now dead. 3011 if (Deleted) Deleted->push_back(U); 3012 DeleteNodeNotInCSEMaps(U); 3013 } 3014 } 3015} 3016 3017/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 3018/// This can cause recursive merging of nodes in the DAG. 3019/// 3020/// This version assumes From/To have matching types and numbers of result 3021/// values. 3022/// 3023void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 3024 std::vector<SDNode*> *Deleted) { 3025 assert(From != To && "Cannot replace uses of with self"); 3026 assert(From->getNumValues() == To->getNumValues() && 3027 "Cannot use this version of ReplaceAllUsesWith!"); 3028 if (From->getNumValues() == 1) { // If possible, use the faster version. 3029 ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted); 3030 return; 3031 } 3032 3033 while (!From->use_empty()) { 3034 // Process users until they are all gone. 3035 SDNode *U = *From->use_begin(); 3036 3037 // This node is about to morph, remove its old self from the CSE maps. 3038 RemoveNodeFromCSEMaps(U); 3039 3040 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 3041 I != E; ++I) 3042 if (I->Val == From) { 3043 From->removeUser(U); 3044 I->Val = To; 3045 To->addUser(U); 3046 } 3047 3048 // Now that we have modified U, add it back to the CSE maps. If it already 3049 // exists there, recursively merge the results together. 3050 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 3051 ReplaceAllUsesWith(U, Existing, Deleted); 3052 // U is now dead. 3053 if (Deleted) Deleted->push_back(U); 3054 DeleteNodeNotInCSEMaps(U); 3055 } 3056 } 3057} 3058 3059/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 3060/// This can cause recursive merging of nodes in the DAG. 3061/// 3062/// This version can replace From with any result values. To must match the 3063/// number and types of values returned by From. 3064void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 3065 const SDOperand *To, 3066 std::vector<SDNode*> *Deleted) { 3067 if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) { 3068 // Degenerate case handled above. 3069 ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); 3070 return; 3071 } 3072 3073 while (!From->use_empty()) { 3074 // Process users until they are all gone. 3075 SDNode *U = *From->use_begin(); 3076 3077 // This node is about to morph, remove its old self from the CSE maps. 3078 RemoveNodeFromCSEMaps(U); 3079 3080 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 3081 I != E; ++I) 3082 if (I->Val == From) { 3083 const SDOperand &ToOp = To[I->ResNo]; 3084 From->removeUser(U); 3085 *I = ToOp; 3086 ToOp.Val->addUser(U); 3087 } 3088 3089 // Now that we have modified U, add it back to the CSE maps. If it already 3090 // exists there, recursively merge the results together. 3091 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 3092 ReplaceAllUsesWith(U, Existing, Deleted); 3093 // U is now dead. 3094 if (Deleted) Deleted->push_back(U); 3095 DeleteNodeNotInCSEMaps(U); 3096 } 3097 } 3098} 3099 3100/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 3101/// uses of other values produced by From.Val alone. The Deleted vector is 3102/// handled the same was as for ReplaceAllUsesWith. 3103void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 3104 std::vector<SDNode*> &Deleted) { 3105 assert(From != To && "Cannot replace a value with itself"); 3106 // Handle the simple, trivial, case efficiently. 3107 if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) { 3108 ReplaceAllUsesWith(From, To, &Deleted); 3109 return; 3110 } 3111 3112 // Get all of the users of From.Val. We want these in a nice, 3113 // deterministically ordered and uniqued set, so we use a SmallSetVector. 3114 SmallSetVector<SDNode*, 16> Users(From.Val->use_begin(), From.Val->use_end()); 3115 3116 while (!Users.empty()) { 3117 // We know that this user uses some value of From. If it is the right 3118 // value, update it. 3119 SDNode *User = Users.back(); 3120 Users.pop_back(); 3121 3122 for (SDOperand *Op = User->OperandList, 3123 *E = User->OperandList+User->NumOperands; Op != E; ++Op) { 3124 if (*Op == From) { 3125 // Okay, we know this user needs to be updated. Remove its old self 3126 // from the CSE maps. 3127 RemoveNodeFromCSEMaps(User); 3128 3129 // Update all operands that match "From". 3130 for (; Op != E; ++Op) { 3131 if (*Op == From) { 3132 From.Val->removeUser(User); 3133 *Op = To; 3134 To.Val->addUser(User); 3135 } 3136 } 3137 3138 // Now that we have modified User, add it back to the CSE maps. If it 3139 // already exists there, recursively merge the results together. 3140 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) { 3141 unsigned NumDeleted = Deleted.size(); 3142 ReplaceAllUsesWith(User, Existing, &Deleted); 3143 3144 // User is now dead. 3145 Deleted.push_back(User); 3146 DeleteNodeNotInCSEMaps(User); 3147 3148 // We have to be careful here, because ReplaceAllUsesWith could have 3149 // deleted a user of From, which means there may be dangling pointers 3150 // in the "Users" setvector. Scan over the deleted node pointers and 3151 // remove them from the setvector. 3152 for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i) 3153 Users.remove(Deleted[i]); 3154 } 3155 break; // Exit the operand scanning loop. 3156 } 3157 } 3158 } 3159} 3160 3161 3162/// AssignNodeIds - Assign a unique node id for each node in the DAG based on 3163/// their allnodes order. It returns the maximum id. 3164unsigned SelectionDAG::AssignNodeIds() { 3165 unsigned Id = 0; 3166 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){ 3167 SDNode *N = I; 3168 N->setNodeId(Id++); 3169 } 3170 return Id; 3171} 3172 3173/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 3174/// based on their topological order. It returns the maximum id and a vector 3175/// of the SDNodes* in assigned order by reference. 3176unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) { 3177 unsigned DAGSize = AllNodes.size(); 3178 std::vector<unsigned> InDegree(DAGSize); 3179 std::vector<SDNode*> Sources; 3180 3181 // Use a two pass approach to avoid using a std::map which is slow. 3182 unsigned Id = 0; 3183 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){ 3184 SDNode *N = I; 3185 N->setNodeId(Id++); 3186 unsigned Degree = N->use_size(); 3187 InDegree[N->getNodeId()] = Degree; 3188 if (Degree == 0) 3189 Sources.push_back(N); 3190 } 3191 3192 TopOrder.clear(); 3193 while (!Sources.empty()) { 3194 SDNode *N = Sources.back(); 3195 Sources.pop_back(); 3196 TopOrder.push_back(N); 3197 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 3198 SDNode *P = I->Val; 3199 unsigned Degree = --InDegree[P->getNodeId()]; 3200 if (Degree == 0) 3201 Sources.push_back(P); 3202 } 3203 } 3204 3205 // Second pass, assign the actual topological order as node ids. 3206 Id = 0; 3207 for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end(); 3208 TI != TE; ++TI) 3209 (*TI)->setNodeId(Id++); 3210 3211 return Id; 3212} 3213 3214 3215 3216//===----------------------------------------------------------------------===// 3217// SDNode Class 3218//===----------------------------------------------------------------------===// 3219 3220// Out-of-line virtual method to give class a home. 3221void SDNode::ANCHOR() {} 3222void UnarySDNode::ANCHOR() {} 3223void BinarySDNode::ANCHOR() {} 3224void TernarySDNode::ANCHOR() {} 3225void HandleSDNode::ANCHOR() {} 3226void StringSDNode::ANCHOR() {} 3227void ConstantSDNode::ANCHOR() {} 3228void ConstantFPSDNode::ANCHOR() {} 3229void GlobalAddressSDNode::ANCHOR() {} 3230void FrameIndexSDNode::ANCHOR() {} 3231void JumpTableSDNode::ANCHOR() {} 3232void ConstantPoolSDNode::ANCHOR() {} 3233void BasicBlockSDNode::ANCHOR() {} 3234void SrcValueSDNode::ANCHOR() {} 3235void RegisterSDNode::ANCHOR() {} 3236void ExternalSymbolSDNode::ANCHOR() {} 3237void CondCodeSDNode::ANCHOR() {} 3238void VTSDNode::ANCHOR() {} 3239void LoadSDNode::ANCHOR() {} 3240void StoreSDNode::ANCHOR() {} 3241 3242HandleSDNode::~HandleSDNode() { 3243 SDVTList VTs = { 0, 0 }; 3244 MorphNodeTo(ISD::HANDLENODE, VTs, 0, 0); // Drops operand uses. 3245} 3246 3247GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, 3248 MVT::ValueType VT, int o) 3249 : SDNode(isa<GlobalVariable>(GA) && 3250 cast<GlobalVariable>(GA)->isThreadLocal() ? 3251 // Thread Local 3252 (isTarget ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress) : 3253 // Non Thread Local 3254 (isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress), 3255 getSDVTList(VT)), Offset(o) { 3256 TheGlobal = const_cast<GlobalValue*>(GA); 3257} 3258 3259/// Profile - Gather unique data for the node. 3260/// 3261void SDNode::Profile(FoldingSetNodeID &ID) { 3262 AddNodeIDNode(ID, this); 3263} 3264 3265/// getValueTypeList - Return a pointer to the specified value type. 3266/// 3267MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { 3268 static MVT::ValueType VTs[MVT::LAST_VALUETYPE]; 3269 VTs[VT] = VT; 3270 return &VTs[VT]; 3271} 3272 3273/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 3274/// indicated value. This method ignores uses of other values defined by this 3275/// operation. 3276bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 3277 assert(Value < getNumValues() && "Bad value!"); 3278 3279 // If there is only one value, this is easy. 3280 if (getNumValues() == 1) 3281 return use_size() == NUses; 3282 if (use_size() < NUses) return false; 3283 3284 SDOperand TheValue(const_cast<SDNode *>(this), Value); 3285 3286 SmallPtrSet<SDNode*, 32> UsersHandled; 3287 3288 for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { 3289 SDNode *User = *UI; 3290 if (User->getNumOperands() == 1 || 3291 UsersHandled.insert(User)) // First time we've seen this? 3292 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 3293 if (User->getOperand(i) == TheValue) { 3294 if (NUses == 0) 3295 return false; // too many uses 3296 --NUses; 3297 } 3298 } 3299 3300 // Found exactly the right number of uses? 3301 return NUses == 0; 3302} 3303 3304 3305/// hasAnyUseOfValue - Return true if there are any use of the indicated 3306/// value. This method ignores uses of other values defined by this operation. 3307bool SDNode::hasAnyUseOfValue(unsigned Value) const { 3308 assert(Value < getNumValues() && "Bad value!"); 3309 3310 if (use_size() == 0) return false; 3311 3312 SDOperand TheValue(const_cast<SDNode *>(this), Value); 3313 3314 SmallPtrSet<SDNode*, 32> UsersHandled; 3315 3316 for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { 3317 SDNode *User = *UI; 3318 if (User->getNumOperands() == 1 || 3319 UsersHandled.insert(User)) // First time we've seen this? 3320 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 3321 if (User->getOperand(i) == TheValue) { 3322 return true; 3323 } 3324 } 3325 3326 return false; 3327} 3328 3329 3330/// isOnlyUse - Return true if this node is the only use of N. 3331/// 3332bool SDNode::isOnlyUse(SDNode *N) const { 3333 bool Seen = false; 3334 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 3335 SDNode *User = *I; 3336 if (User == this) 3337 Seen = true; 3338 else 3339 return false; 3340 } 3341 3342 return Seen; 3343} 3344 3345/// isOperand - Return true if this node is an operand of N. 3346/// 3347bool SDOperand::isOperand(SDNode *N) const { 3348 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 3349 if (*this == N->getOperand(i)) 3350 return true; 3351 return false; 3352} 3353 3354bool SDNode::isOperand(SDNode *N) const { 3355 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 3356 if (this == N->OperandList[i].Val) 3357 return true; 3358 return false; 3359} 3360 3361static void findPredecessor(SDNode *N, const SDNode *P, bool &found, 3362 SmallPtrSet<SDNode *, 32> &Visited) { 3363 if (found || !Visited.insert(N)) 3364 return; 3365 3366 for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) { 3367 SDNode *Op = N->getOperand(i).Val; 3368 if (Op == P) { 3369 found = true; 3370 return; 3371 } 3372 findPredecessor(Op, P, found, Visited); 3373 } 3374} 3375 3376/// isPredecessor - Return true if this node is a predecessor of N. This node 3377/// is either an operand of N or it can be reached by recursively traversing 3378/// up the operands. 3379/// NOTE: this is an expensive method. Use it carefully. 3380bool SDNode::isPredecessor(SDNode *N) const { 3381 SmallPtrSet<SDNode *, 32> Visited; 3382 bool found = false; 3383 findPredecessor(N, this, found, Visited); 3384 return found; 3385} 3386 3387uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 3388 assert(Num < NumOperands && "Invalid child # of SDNode!"); 3389 return cast<ConstantSDNode>(OperandList[Num])->getValue(); 3390} 3391 3392std::string SDNode::getOperationName(const SelectionDAG *G) const { 3393 switch (getOpcode()) { 3394 default: 3395 if (getOpcode() < ISD::BUILTIN_OP_END) 3396 return "<<Unknown DAG Node>>"; 3397 else { 3398 if (G) { 3399 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 3400 if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) 3401 return TII->getName(getOpcode()-ISD::BUILTIN_OP_END); 3402 3403 TargetLowering &TLI = G->getTargetLoweringInfo(); 3404 const char *Name = 3405 TLI.getTargetNodeName(getOpcode()); 3406 if (Name) return Name; 3407 } 3408 3409 return "<<Unknown Target Node>>"; 3410 } 3411 3412 case ISD::PCMARKER: return "PCMarker"; 3413 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 3414 case ISD::SRCVALUE: return "SrcValue"; 3415 case ISD::EntryToken: return "EntryToken"; 3416 case ISD::TokenFactor: return "TokenFactor"; 3417 case ISD::AssertSext: return "AssertSext"; 3418 case ISD::AssertZext: return "AssertZext"; 3419 3420 case ISD::STRING: return "String"; 3421 case ISD::BasicBlock: return "BasicBlock"; 3422 case ISD::VALUETYPE: return "ValueType"; 3423 case ISD::Register: return "Register"; 3424 3425 case ISD::Constant: return "Constant"; 3426 case ISD::ConstantFP: return "ConstantFP"; 3427 case ISD::GlobalAddress: return "GlobalAddress"; 3428 case ISD::GlobalTLSAddress: return "GlobalTLSAddress"; 3429 case ISD::FrameIndex: return "FrameIndex"; 3430 case ISD::JumpTable: return "JumpTable"; 3431 case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; 3432 case ISD::RETURNADDR: return "RETURNADDR"; 3433 case ISD::FRAMEADDR: return "FRAMEADDR"; 3434 case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET"; 3435 case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR"; 3436 case ISD::EHSELECTION: return "EHSELECTION"; 3437 case ISD::EH_RETURN: return "EH_RETURN"; 3438 case ISD::ConstantPool: return "ConstantPool"; 3439 case ISD::ExternalSymbol: return "ExternalSymbol"; 3440 case ISD::INTRINSIC_WO_CHAIN: { 3441 unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue(); 3442 return Intrinsic::getName((Intrinsic::ID)IID); 3443 } 3444 case ISD::INTRINSIC_VOID: 3445 case ISD::INTRINSIC_W_CHAIN: { 3446 unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue(); 3447 return Intrinsic::getName((Intrinsic::ID)IID); 3448 } 3449 3450 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 3451 case ISD::TargetConstant: return "TargetConstant"; 3452 case ISD::TargetConstantFP:return "TargetConstantFP"; 3453 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 3454 case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress"; 3455 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 3456 case ISD::TargetJumpTable: return "TargetJumpTable"; 3457 case ISD::TargetConstantPool: return "TargetConstantPool"; 3458 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 3459 3460 case ISD::CopyToReg: return "CopyToReg"; 3461 case ISD::CopyFromReg: return "CopyFromReg"; 3462 case ISD::UNDEF: return "undef"; 3463 case ISD::MERGE_VALUES: return "merge_values"; 3464 case ISD::INLINEASM: return "inlineasm"; 3465 case ISD::LABEL: return "label"; 3466 case ISD::HANDLENODE: return "handlenode"; 3467 case ISD::FORMAL_ARGUMENTS: return "formal_arguments"; 3468 case ISD::CALL: return "call"; 3469 3470 // Unary operators 3471 case ISD::FABS: return "fabs"; 3472 case ISD::FNEG: return "fneg"; 3473 case ISD::FSQRT: return "fsqrt"; 3474 case ISD::FSIN: return "fsin"; 3475 case ISD::FCOS: return "fcos"; 3476 case ISD::FPOWI: return "fpowi"; 3477 3478 // Binary operators 3479 case ISD::ADD: return "add"; 3480 case ISD::SUB: return "sub"; 3481 case ISD::MUL: return "mul"; 3482 case ISD::MULHU: return "mulhu"; 3483 case ISD::MULHS: return "mulhs"; 3484 case ISD::SDIV: return "sdiv"; 3485 case ISD::UDIV: return "udiv"; 3486 case ISD::SREM: return "srem"; 3487 case ISD::UREM: return "urem"; 3488 case ISD::AND: return "and"; 3489 case ISD::OR: return "or"; 3490 case ISD::XOR: return "xor"; 3491 case ISD::SHL: return "shl"; 3492 case ISD::SRA: return "sra"; 3493 case ISD::SRL: return "srl"; 3494 case ISD::ROTL: return "rotl"; 3495 case ISD::ROTR: return "rotr"; 3496 case ISD::FADD: return "fadd"; 3497 case ISD::FSUB: return "fsub"; 3498 case ISD::FMUL: return "fmul"; 3499 case ISD::FDIV: return "fdiv"; 3500 case ISD::FREM: return "frem"; 3501 case ISD::FCOPYSIGN: return "fcopysign"; 3502 3503 case ISD::SETCC: return "setcc"; 3504 case ISD::SELECT: return "select"; 3505 case ISD::SELECT_CC: return "select_cc"; 3506 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 3507 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 3508 case ISD::CONCAT_VECTORS: return "concat_vectors"; 3509 case ISD::EXTRACT_SUBVECTOR: return "extract_subvector"; 3510 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 3511 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 3512 case ISD::CARRY_FALSE: return "carry_false"; 3513 case ISD::ADDC: return "addc"; 3514 case ISD::ADDE: return "adde"; 3515 case ISD::SUBC: return "subc"; 3516 case ISD::SUBE: return "sube"; 3517 case ISD::SHL_PARTS: return "shl_parts"; 3518 case ISD::SRA_PARTS: return "sra_parts"; 3519 case ISD::SRL_PARTS: return "srl_parts"; 3520 3521 case ISD::EXTRACT_SUBREG: return "extract_subreg"; 3522 case ISD::INSERT_SUBREG: return "insert_subreg"; 3523 3524 // Conversion operators. 3525 case ISD::SIGN_EXTEND: return "sign_extend"; 3526 case ISD::ZERO_EXTEND: return "zero_extend"; 3527 case ISD::ANY_EXTEND: return "any_extend"; 3528 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 3529 case ISD::TRUNCATE: return "truncate"; 3530 case ISD::FP_ROUND: return "fp_round"; 3531 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 3532 case ISD::FP_EXTEND: return "fp_extend"; 3533 3534 case ISD::SINT_TO_FP: return "sint_to_fp"; 3535 case ISD::UINT_TO_FP: return "uint_to_fp"; 3536 case ISD::FP_TO_SINT: return "fp_to_sint"; 3537 case ISD::FP_TO_UINT: return "fp_to_uint"; 3538 case ISD::BIT_CONVERT: return "bit_convert"; 3539 3540 // Control flow instructions 3541 case ISD::BR: return "br"; 3542 case ISD::BRIND: return "brind"; 3543 case ISD::BR_JT: return "br_jt"; 3544 case ISD::BRCOND: return "brcond"; 3545 case ISD::BR_CC: return "br_cc"; 3546 case ISD::RET: return "ret"; 3547 case ISD::CALLSEQ_START: return "callseq_start"; 3548 case ISD::CALLSEQ_END: return "callseq_end"; 3549 3550 // Other operators 3551 case ISD::LOAD: return "load"; 3552 case ISD::STORE: return "store"; 3553 case ISD::VAARG: return "vaarg"; 3554 case ISD::VACOPY: return "vacopy"; 3555 case ISD::VAEND: return "vaend"; 3556 case ISD::VASTART: return "vastart"; 3557 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 3558 case ISD::EXTRACT_ELEMENT: return "extract_element"; 3559 case ISD::BUILD_PAIR: return "build_pair"; 3560 case ISD::STACKSAVE: return "stacksave"; 3561 case ISD::STACKRESTORE: return "stackrestore"; 3562 3563 // Block memory operations. 3564 case ISD::MEMSET: return "memset"; 3565 case ISD::MEMCPY: return "memcpy"; 3566 case ISD::MEMMOVE: return "memmove"; 3567 3568 // Bit manipulation 3569 case ISD::BSWAP: return "bswap"; 3570 case ISD::CTPOP: return "ctpop"; 3571 case ISD::CTTZ: return "cttz"; 3572 case ISD::CTLZ: return "ctlz"; 3573 3574 // Debug info 3575 case ISD::LOCATION: return "location"; 3576 case ISD::DEBUG_LOC: return "debug_loc"; 3577 3578 // Trampolines 3579 case ISD::ADJUST_TRAMP: return "adjust_tramp"; 3580 case ISD::TRAMPOLINE: return "trampoline"; 3581 3582 case ISD::CONDCODE: 3583 switch (cast<CondCodeSDNode>(this)->get()) { 3584 default: assert(0 && "Unknown setcc condition!"); 3585 case ISD::SETOEQ: return "setoeq"; 3586 case ISD::SETOGT: return "setogt"; 3587 case ISD::SETOGE: return "setoge"; 3588 case ISD::SETOLT: return "setolt"; 3589 case ISD::SETOLE: return "setole"; 3590 case ISD::SETONE: return "setone"; 3591 3592 case ISD::SETO: return "seto"; 3593 case ISD::SETUO: return "setuo"; 3594 case ISD::SETUEQ: return "setue"; 3595 case ISD::SETUGT: return "setugt"; 3596 case ISD::SETUGE: return "setuge"; 3597 case ISD::SETULT: return "setult"; 3598 case ISD::SETULE: return "setule"; 3599 case ISD::SETUNE: return "setune"; 3600 3601 case ISD::SETEQ: return "seteq"; 3602 case ISD::SETGT: return "setgt"; 3603 case ISD::SETGE: return "setge"; 3604 case ISD::SETLT: return "setlt"; 3605 case ISD::SETLE: return "setle"; 3606 case ISD::SETNE: return "setne"; 3607 } 3608 } 3609} 3610 3611const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) { 3612 switch (AM) { 3613 default: 3614 return ""; 3615 case ISD::PRE_INC: 3616 return "<pre-inc>"; 3617 case ISD::PRE_DEC: 3618 return "<pre-dec>"; 3619 case ISD::POST_INC: 3620 return "<post-inc>"; 3621 case ISD::POST_DEC: 3622 return "<post-dec>"; 3623 } 3624} 3625 3626void SDNode::dump() const { dump(0); } 3627void SDNode::dump(const SelectionDAG *G) const { 3628 cerr << (void*)this << ": "; 3629 3630 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 3631 if (i) cerr << ","; 3632 if (getValueType(i) == MVT::Other) 3633 cerr << "ch"; 3634 else 3635 cerr << MVT::getValueTypeString(getValueType(i)); 3636 } 3637 cerr << " = " << getOperationName(G); 3638 3639 cerr << " "; 3640 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 3641 if (i) cerr << ", "; 3642 cerr << (void*)getOperand(i).Val; 3643 if (unsigned RN = getOperand(i).ResNo) 3644 cerr << ":" << RN; 3645 } 3646 3647 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 3648 cerr << "<" << CSDN->getValue() << ">"; 3649 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 3650 cerr << "<" << CSDN->getValue() << ">"; 3651 } else if (const GlobalAddressSDNode *GADN = 3652 dyn_cast<GlobalAddressSDNode>(this)) { 3653 int offset = GADN->getOffset(); 3654 cerr << "<"; 3655 WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">"; 3656 if (offset > 0) 3657 cerr << " + " << offset; 3658 else 3659 cerr << " " << offset; 3660 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 3661 cerr << "<" << FIDN->getIndex() << ">"; 3662 } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) { 3663 cerr << "<" << JTDN->getIndex() << ">"; 3664 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 3665 int offset = CP->getOffset(); 3666 if (CP->isMachineConstantPoolEntry()) 3667 cerr << "<" << *CP->getMachineCPVal() << ">"; 3668 else 3669 cerr << "<" << *CP->getConstVal() << ">"; 3670 if (offset > 0) 3671 cerr << " + " << offset; 3672 else 3673 cerr << " " << offset; 3674 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 3675 cerr << "<"; 3676 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 3677 if (LBB) 3678 cerr << LBB->getName() << " "; 3679 cerr << (const void*)BBDN->getBasicBlock() << ">"; 3680 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 3681 if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { 3682 cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg()); 3683 } else { 3684 cerr << " #" << R->getReg(); 3685 } 3686 } else if (const ExternalSymbolSDNode *ES = 3687 dyn_cast<ExternalSymbolSDNode>(this)) { 3688 cerr << "'" << ES->getSymbol() << "'"; 3689 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 3690 if (M->getValue()) 3691 cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; 3692 else 3693 cerr << "<null:" << M->getOffset() << ">"; 3694 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 3695 cerr << ":" << MVT::getValueTypeString(N->getVT()); 3696 } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) { 3697 bool doExt = true; 3698 switch (LD->getExtensionType()) { 3699 default: doExt = false; break; 3700 case ISD::EXTLOAD: 3701 cerr << " <anyext "; 3702 break; 3703 case ISD::SEXTLOAD: 3704 cerr << " <sext "; 3705 break; 3706 case ISD::ZEXTLOAD: 3707 cerr << " <zext "; 3708 break; 3709 } 3710 if (doExt) 3711 cerr << MVT::getValueTypeString(LD->getLoadedVT()) << ">"; 3712 3713 const char *AM = getIndexedModeName(LD->getAddressingMode()); 3714 if (*AM) 3715 cerr << " " << AM; 3716 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) { 3717 if (ST->isTruncatingStore()) 3718 cerr << " <trunc " 3719 << MVT::getValueTypeString(ST->getStoredVT()) << ">"; 3720 3721 const char *AM = getIndexedModeName(ST->getAddressingMode()); 3722 if (*AM) 3723 cerr << " " << AM; 3724 } 3725} 3726 3727static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 3728 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 3729 if (N->getOperand(i).Val->hasOneUse()) 3730 DumpNodes(N->getOperand(i).Val, indent+2, G); 3731 else 3732 cerr << "\n" << std::string(indent+2, ' ') 3733 << (void*)N->getOperand(i).Val << ": <multiple use>"; 3734 3735 3736 cerr << "\n" << std::string(indent, ' '); 3737 N->dump(G); 3738} 3739 3740void SelectionDAG::dump() const { 3741 cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 3742 std::vector<const SDNode*> Nodes; 3743 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 3744 I != E; ++I) 3745 Nodes.push_back(I); 3746 3747 std::sort(Nodes.begin(), Nodes.end()); 3748 3749 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 3750 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 3751 DumpNodes(Nodes[i], 2, this); 3752 } 3753 3754 if (getRoot().Val) DumpNodes(getRoot().Val, 2, this); 3755 3756 cerr << "\n\n"; 3757} 3758 3759const Type *ConstantPoolSDNode::getType() const { 3760 if (isMachineConstantPoolEntry()) 3761 return Val.MachineCPVal->getType(); 3762 return Val.ConstVal->getType(); 3763} 3764